jj-lib 0.46.0

// Copyright 2025 The Jujutsu Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use std::assert_matches;
use std::sync::Arc;

use jj_lib::backend::CommitId;
use jj_lib::bisect::BisectionResult;
use jj_lib::bisect::Bisector;
use jj_lib::bisect::Evaluation;
use jj_lib::bisect::NextStep;
use jj_lib::repo::Repo;
use jj_lib::revset::ResolvedRevsetExpression;
use pollster::FutureExt as _;
use testutils::TestRepo;
use testutils::write_random_commit;
use testutils::write_random_commit_with_parents;

fn test_bisection<'a>(
    repo: &dyn Repo,
    input_range: &Arc<ResolvedRevsetExpression>,
    results: impl IntoIterator<Item = (&'a CommitId, Evaluation)>,
    verify_preconditions: bool,
) -> BisectionResult {
    let mut bisector = Bisector::new(repo, input_range.clone(), verify_preconditions)
        .block_on()
        .unwrap();
    let mut iter = results.into_iter().enumerate();
    loop {
        match bisector.next_step().block_on().unwrap() {
            NextStep::Verify {
                commit,
                expected_evaluation: evaluation,
            } => {
                let (i, (expected_id, expected_evaluation)) =
                    iter.next().expect("More commits than expected were tested");
                let description = commit.description();
                assert_eq!(
                    commit.id(),
                    expected_id,
                    "Attempt to test unexpected commit at iteration {i}: {commit:#?} with \
                     description {description}"
                );
                assert_eq!(
                    evaluation, expected_evaluation,
                    "Pre-bisection check at iteration {i} was {evaluation:#?}; should've been \
                     {expected_evaluation:#?}"
                );
            }
            NextStep::Evaluate(commit) => {
                let (i, (expected_id, result)) =
                    iter.next().expect("More commits than expected were tested");
                assert_eq!(
                    commit.id(),
                    expected_id,
                    "Attempt to test unexpected commit at iteration {i}"
                );
                bisector.mark(commit.id().clone(), result);
            }
            NextStep::Done(bisection_result) => {
                assert!(iter.next().is_none(), "Finished earlier than expected");
                return bisection_result;
            }
        }
    }
}

#[test]
fn test_bisect_empty_input() {
    let test_repo = TestRepo::init();
    let repo = &test_repo.repo;

    let input_range = ResolvedRevsetExpression::none();
    let expected_tests = [];
    let result = test_bisection(repo.as_ref(), &input_range, expected_tests, true);
    assert_matches!(result, BisectionResult::Indeterminate);
}

#[test]
fn test_bisect_linear() {
    let test_repo = TestRepo::init();
    let repo = &test_repo.repo;

    let mut tx = repo.start_transaction();
    let root_commit = repo.store().root_commit();
    let commit1 = write_random_commit(tx.repo_mut());
    let commit2 = write_random_commit_with_parents(tx.repo_mut(), &[&commit1]);
    let commit3 = write_random_commit_with_parents(tx.repo_mut(), &[&commit2]);
    let commit4 = write_random_commit_with_parents(tx.repo_mut(), &[&commit3]);
    let commit5 = write_random_commit_with_parents(tx.repo_mut(), &[&commit4]);
    let commit6 = write_random_commit_with_parents(tx.repo_mut(), &[&commit5]);
    let commit7 = write_random_commit_with_parents(tx.repo_mut(), &[&commit6]);

    let input_range = ResolvedRevsetExpression::commit(commit7.id().clone()).ancestors();

    // Root commit is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Bad),
        (commit1.id(), Evaluation::Bad),
        (root_commit.id(), Evaluation::Bad),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![root_commit.clone()]));

    // Commit 1 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Bad),
        (commit1.id(), Evaluation::Bad),
        (root_commit.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit1.clone()]));

    // Commit 3 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Bad),
        (commit1.id(), Evaluation::Good),
        (commit2.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit3.clone()]));

    // Commit 5 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Good),
        (commit5.id(), Evaluation::Bad),
        (commit4.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit5.clone()]));

    // Commit 7 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Good),
        (commit5.id(), Evaluation::Good),
        (commit6.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit7.clone()]));

    // Commit 2 is the first bad commit but commit 3 is skipped
    let expected_tests = [
        (commit3.id(), Evaluation::Skip),
        (commit2.id(), Evaluation::Bad),
        (root_commit.id(), Evaluation::Good),
        (commit1.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit2.clone()]));

    // Commit 4 is the first bad commit but commit 3 is skipped
    let expected_tests = [
        (commit3.id(), Evaluation::Skip),
        (commit2.id(), Evaluation::Good),
        (commit5.id(), Evaluation::Bad),
        (commit4.id(), Evaluation::Bad),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(
        result,
        BisectionResult::FoundDespiteSkips {
            bad_commits: vec![commit4.clone()],
            possibly_bad: vec![commit3.clone()]
        }
    );

    // commit2 is the first bad commit; its parent and child commits were skipped
    // * commit1 is a possibly_bad commit: it's between a bad and a good commit
    // * commit3 is NOT a possibly_bad commit: it's implicitly bad due to commit2
    let expected_tests = [
        (commit3.id(), Evaluation::Skip),
        (commit2.id(), Evaluation::Bad),
        (root_commit.id(), Evaluation::Good),
        (commit1.id(), Evaluation::Skip),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(
        result,
        BisectionResult::FoundDespiteSkips {
            bad_commits: vec![commit2.clone()],
            possibly_bad: vec![commit1.clone()]
        }
    );

    // Commit 7 is the first bad commit but commits before 6 were skipped
    // TODO: Avoid testing every commit near first skipped commit. Test e.g. commit
    // 1 and commit 5 once we see that commit 3 was indeterminate.
    let expected_tests = [
        (commit3.id(), Evaluation::Skip),
        (commit2.id(), Evaluation::Skip),
        (commit4.id(), Evaluation::Skip),
        (commit1.id(), Evaluation::Skip),
        (commit5.id(), Evaluation::Skip),
        (root_commit.id(), Evaluation::Skip),
        (commit6.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit7.clone()]));

    // Tests with gap in the input
    {
        // Gaps in the input range are allowed
        let input_range = ResolvedRevsetExpression::commits(vec![
            commit7.id().clone(),
            commit4.id().clone(),
            commit2.id().clone(),
            commit1.id().clone(),
        ]);

        // Commit 4 is the first bad commit
        let bisection_result = BisectionResult::Found(vec![commit4.clone()]);

        let bisection_steps = [
            (commit2.id(), Evaluation::Good),
            (commit4.id(), Evaluation::Bad),
        ];
        let result = test_bisection(tx.repo(), &input_range, bisection_steps.clone(), false);
        assert_eq!(result, bisection_result);

        // Same, but now verifying preconditions
        let expected_tests = [
            (commit7.id(), Evaluation::Bad),
            (root_commit.id(), Evaluation::Good),
        ]
        .into_iter()
        .chain(bisection_steps);
        let result = test_bisection(tx.repo(), &input_range, expected_tests, true);
        assert_eq!(result, bisection_result);
    }
}

#[test]
fn test_bisect_nonlinear() {
    let test_repo = TestRepo::init();
    let repo = &test_repo.repo;

    // 7
    // |\
    // 5 6
    // | |
    // 3 4
    // | |
    // 1 2
    // |/
    // 0
    let mut tx = repo.start_transaction();
    let root_commit = repo.store().root_commit();
    let commit1 = write_random_commit(tx.repo_mut());
    let commit2 = write_random_commit(tx.repo_mut());
    let commit3 = write_random_commit_with_parents(tx.repo_mut(), &[&commit1]);
    let commit4 = write_random_commit_with_parents(tx.repo_mut(), &[&commit2]);
    let commit5 = write_random_commit_with_parents(tx.repo_mut(), &[&commit3]);
    let commit6 = write_random_commit_with_parents(tx.repo_mut(), &[&commit4]);
    let commit7 = write_random_commit_with_parents(tx.repo_mut(), &[&commit5, &commit6]);

    let root_commit_expr = ResolvedRevsetExpression::commit(root_commit.id().clone());
    let commit6_expr = ResolvedRevsetExpression::commit(commit6.id().clone());
    let commit7_expr = ResolvedRevsetExpression::commit(commit7.id().clone());

    let input_range = commit7_expr.ancestors();
    let input_range_without_root = input_range.minus(&root_commit_expr);
    let input_range_without_merge = input_range.minus(&commit7_expr);
    let input_range_single_branch = root_commit_expr.range(&commit6_expr).union(&commit7_expr);

    // Test with the full diamond
    {
        let bisection_result = BisectionResult::Found(vec![root_commit.clone()]);

        let bisection_tests = [
            (commit3.id(), Evaluation::Bad),
            (root_commit.id(), Evaluation::Bad),
        ];
        let result = test_bisection(tx.repo(), &input_range, bisection_tests.clone(), false);
        assert_eq!(result, bisection_result);

        // If the root commit is part of the revset, it's allowed to be bad
        // No commit gets checked to be Good
        let expected_tests = [(commit7.id(), Evaluation::Bad)]
            .into_iter()
            .chain(bisection_tests.clone());
        let result = test_bisection(tx.repo(), &input_range, expected_tests, true);
        assert_eq!(result, bisection_result);
    }

    // Commit 4 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Good),
        (commit4.id(), Evaluation::Bad),
        (commit2.id(), Evaluation::Good),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Found(vec![commit4.clone()]));

    // Commit 6 is the first bad commit
    let expected_tests = [
        (commit3.id(), Evaluation::Good),
        (commit4.id(), Evaluation::Good),
        (commit5.id(), Evaluation::Good),
        (commit6.id(), Evaluation::Bad),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests.clone(), false);
    assert_eq!(result, BisectionResult::Found(vec![commit6.clone()]));

    // Test without the base of the diamond
    {
        let bisection_result = BisectionResult::Found(vec![commit3.clone()]);

        let bisection_tests = [
            (commit3.id(), Evaluation::Bad),
            (commit1.id(), Evaluation::Good),
        ];
        let result = test_bisection(
            tx.repo(),
            &input_range_without_root,
            bisection_tests.clone(),
            false,
        );
        assert_eq!(result, bisection_result);

        let expected_tests = [
            (commit7.id(), Evaluation::Bad),
            // root_commit is also verified
            (root_commit.id(), Evaluation::Good),
        ]
        .into_iter()
        .chain(bisection_tests.clone());
        let result = test_bisection(tx.repo(), &input_range_without_root, expected_tests, true);
        assert_eq!(result, bisection_result);
    }

    // Tests with just one side of the diamond (0::6|7)
    {
        let bisection_result = BisectionResult::Found(vec![commit6.clone()]);

        let bisection_tests = [
            (commit4.id(), Evaluation::Good),
            (commit6.id(), Evaluation::Bad),
        ];
        let result = test_bisection(
            tx.repo(),
            &input_range_single_branch,
            bisection_tests.clone(),
            false,
        );
        assert_eq!(result, bisection_result);

        let expected_tests = [
            (commit7.id(), Evaluation::Bad),
            (root_commit.id(), Evaluation::Good),
            // the head of the other side is also checked
            (commit5.id(), Evaluation::Good),
        ]
        .into_iter()
        .chain(bisection_tests);
        let result = test_bisection(tx.repo(), &input_range_single_branch, expected_tests, true);
        assert_eq!(result, bisection_result);
    }

    // Test without the head of the diamond
    {
        // We need bad commits on both sides!
        // See test_bisect_command::test_bisect_run_nonlinear_no_merge for a test case
        // where only either of these commits is bad
        let bisection_result = BisectionResult::Found(vec![commit5.clone(), commit2.clone()]);

        let bisection_tests = [
            (commit2.id(), Evaluation::Bad),
            (commit1.id(), Evaluation::Good),
            (commit3.id(), Evaluation::Good),
        ];
        let result = test_bisection(
            tx.repo(),
            &input_range_without_merge,
            bisection_tests.clone(),
            false,
        );
        assert_eq!(result, bisection_result);

        let expected_tests = [
            (commit5.id(), Evaluation::Bad),
            (commit6.id(), Evaluation::Bad),
        ]
        .into_iter()
        .chain(bisection_tests);
        let result = test_bisection(tx.repo(), &input_range_without_merge, expected_tests, true);
        assert_eq!(result, bisection_result);
    }
}

#[test]
fn test_bisect_disjoint_sets() {
    let test_repo = TestRepo::init();
    let repo = &test_repo.repo;

    // 1 2
    // |/
    // 0
    let mut tx = repo.start_transaction();
    let root_commit = repo.store().root_commit();
    let commit1 = write_random_commit(tx.repo_mut());
    let commit2 = write_random_commit(tx.repo_mut());

    let input_range =
        ResolvedRevsetExpression::commits(vec![commit1.id().clone(), commit2.id().clone()]);

    // Both commit 1 and commit 2 are (implicitly) the first bad commits
    let expected_tests = [];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(
        result,
        BisectionResult::Found(vec![commit2.clone(), commit1.clone()])
    );

    // Both commit 1 and commit 2 are (implicitly) the first bad commits
    test_bisection(
        tx.repo(),
        &input_range,
        [
            (commit1.id(), Evaluation::Bad),
            (commit2.id(), Evaluation::Bad),
            (root_commit.id(), Evaluation::Good),
        ],
        true,
    );
}

#[test]
fn test_bisect_abort() {
    let test_repo = TestRepo::init();
    let repo = &test_repo.repo;

    let mut tx = repo.start_transaction();
    let commit1 = write_random_commit(tx.repo_mut());
    let commit2 = write_random_commit_with_parents(tx.repo_mut(), &[&commit1]);
    let commit3 = write_random_commit_with_parents(tx.repo_mut(), &[&commit2]);
    let commit4 = write_random_commit_with_parents(tx.repo_mut(), &[&commit3]);
    let commit5 = write_random_commit_with_parents(tx.repo_mut(), &[&commit4]);
    let commit6 = write_random_commit_with_parents(tx.repo_mut(), &[&commit5]);
    let commit7 = write_random_commit_with_parents(tx.repo_mut(), &[&commit6]);

    let input_range = ResolvedRevsetExpression::commit(commit7.id().clone()).ancestors();

    // Commit 5 is an abort commit
    let expected_tests = [
        (commit3.id(), Evaluation::Good),
        (commit5.id(), Evaluation::Abort),
    ];
    let result = test_bisection(tx.repo(), &input_range, expected_tests, false);
    assert_eq!(result, BisectionResult::Abort);
}