mirror of
https://github.com/jj-vcs/jj.git
synced 2025-12-23 06:01:01 +00:00
5b83c9899c
We want these to be `Send` and `Sync` so we can send them between threads in our multi-threaded backend. This requires a bunch of subsequent (but obvious) changes throughout cli and the tests. Co-authored-by: Benjamin Brittain <ben@ersc.io> Signed-off-by: Austin Seipp <austin@ersc.io> Signed-off-by: Austin Seipp <aseipp@pobox.com>
267 lines
9.9 KiB
Rust
267 lines
9.9 KiB
Rust
// 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::sync::Arc;
|
|
|
|
use assert_matches::assert_matches;
|
|
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 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)>,
|
|
) -> BisectionResult {
|
|
let mut bisector = Bisector::new(repo, input_range.clone()).unwrap();
|
|
let mut iter = results.into_iter().enumerate();
|
|
loop {
|
|
match bisector.next_step().unwrap() {
|
|
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);
|
|
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);
|
|
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);
|
|
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);
|
|
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);
|
|
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);
|
|
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);
|
|
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);
|
|
// TODO: Indicate in the result that we're unsure if commit4 was the first bad
|
|
// commit because the commit before it in the set was skipped.
|
|
assert_eq!(result, BisectionResult::Found(vec![commit4.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);
|
|
assert_eq!(result, BisectionResult::Found(vec![commit7.clone()]));
|
|
|
|
// 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 expected_tests = [
|
|
(commit2.id(), Evaluation::Good),
|
|
(commit4.id(), Evaluation::Bad),
|
|
];
|
|
let result = test_bisection(tx.repo(), &input_range, expected_tests);
|
|
assert_eq!(result, BisectionResult::Found(vec![commit4.clone()]));
|
|
}
|
|
|
|
#[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 input_range = ResolvedRevsetExpression::commit(commit7.id().clone()).ancestors();
|
|
|
|
// Root commit is the first bad commit
|
|
let expected_tests = [
|
|
(commit3.id(), Evaluation::Bad),
|
|
(root_commit.id(), Evaluation::Bad),
|
|
];
|
|
let result = test_bisection(tx.repo(), &input_range, expected_tests);
|
|
assert_eq!(result, BisectionResult::Found(vec![root_commit.clone()]));
|
|
|
|
// Commit 3 is the first bad commit
|
|
let expected_tests = [
|
|
(commit3.id(), Evaluation::Bad),
|
|
(root_commit.id(), Evaluation::Good),
|
|
(commit1.id(), Evaluation::Good),
|
|
];
|
|
let result = test_bisection(tx.repo(), &input_range, expected_tests);
|
|
assert_eq!(result, BisectionResult::Found(vec![commit3.clone()]));
|
|
|
|
// 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);
|
|
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);
|
|
assert_eq!(result, BisectionResult::Found(vec![commit6.clone()]));
|
|
}
|
|
|
|
#[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 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);
|
|
assert_eq!(
|
|
result,
|
|
BisectionResult::Found(vec![commit2.clone(), commit1.clone()])
|
|
);
|
|
}
|