// 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. //! Bisect a range of commits. use std::collections::HashSet;use std::collections::VecDeque;use std::pin::pin;use std::sync::Arc; use futures::TryStreamExt as _;use thiserror::Error; use crate::backend::BackendError;use crate::backend::CommitId;use crate::commit::Commit;use crate::repo::Repo;use crate::revset::ResolvedRevsetExpression;use crate::revset::Revset;use crate::revset::RevsetEvaluationError;use crate::revset::RevsetExpression;use crate::revset::RevsetStreamExt as _; /// An error that occurred while bisecting#[derive(Error, Debug)]pub enum BisectionError { /// Failed to read data from the backend #[error("Failed to read data from the backend involved in bisection")] BackendError(#[from] BackendError), /// Failed to evaluate a revset #[error("Failed to evaluate a revset involved in bisection")] RevsetEvaluationError(#[from] RevsetEvaluationError),} /// Indicates whether a given commit was good, bad, or if it could not be/// determined.#[derive(Debug)]pub enum Evaluation { /// The commit was good Good, /// The commit was bad Bad, /// It could not be determined whether the commit was good or bad Skip, /// The commit caused an abort Abort,} impl Evaluation { /// Maps the current evaluation to its inverse. /// /// Maps `Good`->`Bad`, `Bad`->`Good`, and keeps `Skip` as is. pub fn invert(self) -> Self { use Evaluation::*; match self { Good => Bad, Bad => Good, Skip => Skip, Abort => Abort, } }} /// Performs bisection to find the first bad commit in a range.pub struct Bisector<'repo> { repo: &'repo dyn Repo, input_range: Arc<ResolvedRevsetExpression>, good_commits: HashSet<CommitId>, bad_commits: HashSet<CommitId>, skipped_commits: HashSet<CommitId>, aborted: bool,} /// The result of bisection.#[derive(Debug, PartialEq, Eq, Clone)]pub enum BisectionResult { /// Found the first bad commit(s). It should be exactly one unless the input /// range had multiple disjoint heads. Found(Vec<Commit>), /// The bisection frontier is blurred by the presence of skipped commits FoundDespiteSkips { /// The first commit(s) that did evaluate as bad bad_commits: Vec<Commit>, /// Skipped commits sandwiched between good and bad commits /// Are they good or bad? We couldn't tell. possibly_bad: Vec<Commit>, }, /// Could not determine the first bad commit because it was in a /// skipped range. Indeterminate, /// Bisection was aborted. Abort,} /// The next bisection step.#[derive(Debug, PartialEq, Eq, Clone)]pub enum NextStep { /// The commit must be evaluated. Evaluate(Commit), /// Bisection is complete. Done(BisectionResult),} impl<'repo> Bisector<'repo> { /// Create a new bisector. The range's heads are assumed to be bad. /// Parents of the range's roots are assumed to be good. pub async fn new( repo: &'repo dyn Repo, input_range: Arc<ResolvedRevsetExpression>, ) -> Result<Self, BisectionError> { let bad_commits = input_range .heads() .evaluate(repo)? .stream() .try_collect() .await?; Ok(Self { repo, input_range, bad_commits, good_commits: HashSet::new(), skipped_commits: HashSet::new(), aborted: false, }) } /// Mark a commit good. pub fn mark_good(&mut self, id: CommitId) { assert!(!self.bad_commits.contains(&id)); assert!(!self.skipped_commits.contains(&id)); assert!(!self.aborted); self.good_commits.insert(id); } /// Mark a commit bad. pub fn mark_bad(&mut self, id: CommitId) { assert!(!self.good_commits.contains(&id)); assert!(!self.skipped_commits.contains(&id)); assert!(!self.aborted); self.bad_commits.insert(id); } /// Mark a commit as skipped (cannot be determined if it's good or bad). pub fn mark_skipped(&mut self, id: CommitId) { assert!(!self.good_commits.contains(&id)); assert!(!self.bad_commits.contains(&id)); assert!(!self.aborted); self.skipped_commits.insert(id); } /// Mark a commit as causing an abort pub fn mark_abort(&mut self, id: CommitId) { // TODO: Right now, we only use this state for triggering an abort. // A potential improvement would be to make the CLI print out the revset with // the current status of each change, making it possible for a user // to restart an aborted bisect in progress. assert!(!self.good_commits.contains(&id)); assert!(!self.bad_commits.contains(&id)); assert!(!self.skipped_commits.contains(&id)); self.aborted = true; } /// Mark a commit as good, bad, or skipped, according to the outcome in /// `evaluation`. pub fn mark(&mut self, id: CommitId, evaluation: Evaluation) { match evaluation { Evaluation::Good => self.mark_good(id), Evaluation::Bad => self.mark_bad(id), Evaluation::Skip => self.mark_skipped(id), Evaluation::Abort => self.mark_abort(id), } } /// The commits that were marked good. pub fn good_commits(&self) -> &HashSet<CommitId> { &self.good_commits } /// The commits that were marked bad. pub fn bad_commits(&self) -> &HashSet<CommitId> { &self.bad_commits } /// The commits that were skipped. pub fn skipped_commits(&self) -> &HashSet<CommitId> { &self.skipped_commits } fn candidates(&self) -> Arc<ResolvedRevsetExpression> { let good_expr = RevsetExpression::commits(self.good_commits.iter().cloned().collect()); let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect()); let skipped_expr = RevsetExpression::commits(self.skipped_commits.iter().cloned().collect()); self.input_range .intersection(&good_expr.heads().range(&bad_expr.roots())) .minus(&bad_expr) .minus(&skipped_expr) } /// Returns the evaluated revset representing the remaining candidate /// commits. Can be used for getting an estimate of how many commits are /// left to evaluate. pub async fn remaining_revset(&self) -> Result<Box<dyn Revset + 'repo>, BisectionError> { Ok(self.candidates().evaluate(self.repo)?) } /// Find the next commit to evaluate, or determine that there are no more /// steps. pub async fn next_step(&mut self) -> Result<NextStep, BisectionError> { if self.aborted { return Ok(NextStep::Done(BisectionResult::Abort)); } // Intersect the input range with the current bad range and then bisect it to // find the next commit to evaluate. // Skipped revisions are simply subtracted from the set. // TODO: Handle long ranges of skipped revisions better let to_evaluate_expr = self.candidates().bisect().latest(1); let to_evaluate_set = to_evaluate_expr.evaluate(self.repo)?; if let Some(commit_id) = pin!(to_evaluate_set.stream()).try_next().await? { let commit = self.repo.store().get_commit_async(&commit_id).await?; Ok(NextStep::Evaluate(commit)) } else { let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect()); let bad_roots = bad_expr.roots().evaluate(self.repo)?; let bad_commits: Vec<_> = bad_roots .stream() .commits(self.repo.store()) .try_collect() .await?; if bad_commits.is_empty() { Ok(NextStep::Done(BisectionResult::Indeterminate)) } else { // were any commits skipped that could also be bad? let mut todo: VecDeque<Commit> = VecDeque::from(bad_commits.clone()); let mut possibly_bad: Vec<Commit> = Vec::new(); while let Some(commit) = todo.pop_front() { for parent in commit.parents().await? { if self.skipped_commits.contains(parent.id()) { possibly_bad.push(parent.clone()); todo.push_back(parent); } } } if possibly_bad.is_empty() { Ok(NextStep::Done(BisectionResult::Found(bad_commits))) } else { Ok(NextStep::Done(BisectionResult::FoundDespiteSkips { bad_commits, possibly_bad, })) } } } }}
// 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.
//! Bisect a range of commits.
use std::collections::HashSet;
use std::collections::VecDeque;
use std::pin::pin;
use std::sync::Arc;
use futures::TryStreamExt as _;
use thiserror::Error;
use crate::backend::BackendError;
use crate::backend::CommitId;
use crate::commit::Commit;
use crate::repo::Repo;
use crate::revset::ResolvedRevsetExpression;
use crate::revset::Revset;
use crate::revset::RevsetEvaluationError;
use crate::revset::RevsetExpression;
use crate::revset::RevsetStreamExt as _;
/// An error that occurred while bisecting
#[derive(Error, Debug)]
pub enum BisectionError {
/// Failed to read data from the backend
#[error("Failed to read data from the backend involved in bisection")]
BackendError(#[from] BackendError),
/// Failed to evaluate a revset
#[error("Failed to evaluate a revset involved in bisection")]
RevsetEvaluationError(#[from] RevsetEvaluationError),
}
/// Indicates whether a given commit was good, bad, or if it could not be
/// determined.
#[derive(Debug)]
pub enum Evaluation {
/// The commit was good
Good,
/// The commit was bad
Bad,
/// It could not be determined whether the commit was good or bad
Skip,
/// The commit caused an abort
Abort,
}
impl Evaluation {
/// Maps the current evaluation to its inverse.
///
/// Maps `Good`->`Bad`, `Bad`->`Good`, and keeps `Skip` as is.
pub fn invert(self) -> Self {
use Evaluation::*;
match self {
Good => Bad,
Bad => Good,
Skip => Skip,
Abort => Abort,
}
}
}
/// Performs bisection to find the first bad commit in a range.
pub struct Bisector<'repo> {
repo: &'repo dyn Repo,
input_range: Arc<ResolvedRevsetExpression>,
good_commits: HashSet<CommitId>,
bad_commits: HashSet<CommitId>,
skipped_commits: HashSet<CommitId>,
aborted: bool,
}
/// The result of bisection.
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum BisectionResult {
/// Found the first bad commit(s). It should be exactly one unless the input
/// range had multiple disjoint heads.
Found(Vec<Commit>),
/// The bisection frontier is blurred by the presence of skipped commits
FoundDespiteSkips {
/// The first commit(s) that did evaluate as bad
bad_commits: Vec<Commit>,
/// Skipped commits sandwiched between good and bad commits
/// Are they good or bad? We couldn't tell.
possibly_bad: Vec<Commit>,
},
/// Could not determine the first bad commit because it was in a
/// skipped range.
Indeterminate,
/// Bisection was aborted.
Abort,
}
/// The next bisection step.
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum NextStep {
/// The commit must be evaluated.
Evaluate(Commit),
/// Bisection is complete.
Done(BisectionResult),
}
impl<'repo> Bisector<'repo> {
/// Create a new bisector. The range's heads are assumed to be bad.
/// Parents of the range's roots are assumed to be good.
pub async fn new(
repo: &'repo dyn Repo,
input_range: Arc<ResolvedRevsetExpression>,
) -> Result<Self, BisectionError> {
let bad_commits = input_range
.heads()
.evaluate(repo)?
.stream()
.try_collect()
.await?;
Ok(Self {
repo,
input_range,
bad_commits,
good_commits: HashSet::new(),
skipped_commits: HashSet::new(),
aborted: false,
})
}
/// Mark a commit good.
pub fn mark_good(&mut self, id: CommitId) {
assert!(!self.bad_commits.contains(&id));
assert!(!self.skipped_commits.contains(&id));
assert!(!self.aborted);
self.good_commits.insert(id);
}
/// Mark a commit bad.
pub fn mark_bad(&mut self, id: CommitId) {
assert!(!self.good_commits.contains(&id));
assert!(!self.skipped_commits.contains(&id));
assert!(!self.aborted);
self.bad_commits.insert(id);
}
/// Mark a commit as skipped (cannot be determined if it's good or bad).
pub fn mark_skipped(&mut self, id: CommitId) {
assert!(!self.good_commits.contains(&id));
assert!(!self.bad_commits.contains(&id));
assert!(!self.aborted);
self.skipped_commits.insert(id);
}
/// Mark a commit as causing an abort
pub fn mark_abort(&mut self, id: CommitId) {
// TODO: Right now, we only use this state for triggering an abort.
// A potential improvement would be to make the CLI print out the revset with
// the current status of each change, making it possible for a user
// to restart an aborted bisect in progress.
assert!(!self.good_commits.contains(&id));
assert!(!self.bad_commits.contains(&id));
assert!(!self.skipped_commits.contains(&id));
self.aborted = true;
}
/// Mark a commit as good, bad, or skipped, according to the outcome in
/// `evaluation`.
pub fn mark(&mut self, id: CommitId, evaluation: Evaluation) {
match evaluation {
Evaluation::Good => self.mark_good(id),
Evaluation::Bad => self.mark_bad(id),
Evaluation::Skip => self.mark_skipped(id),
Evaluation::Abort => self.mark_abort(id),
}
}
/// The commits that were marked good.
pub fn good_commits(&self) -> &HashSet<CommitId> {
&self.good_commits
}
/// The commits that were marked bad.
pub fn bad_commits(&self) -> &HashSet<CommitId> {
&self.bad_commits
}
/// The commits that were skipped.
pub fn skipped_commits(&self) -> &HashSet<CommitId> {
&self.skipped_commits
}
fn candidates(&self) -> Arc<ResolvedRevsetExpression> {
let good_expr = RevsetExpression::commits(self.good_commits.iter().cloned().collect());
let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect());
let skipped_expr =
RevsetExpression::commits(self.skipped_commits.iter().cloned().collect());
self.input_range
.intersection(&good_expr.heads().range(&bad_expr.roots()))
.minus(&bad_expr)
.minus(&skipped_expr)
}
/// Returns the evaluated revset representing the remaining candidate
/// commits. Can be used for getting an estimate of how many commits are
/// left to evaluate.
pub async fn remaining_revset(&self) -> Result<Box<dyn Revset + 'repo>, BisectionError> {
Ok(self.candidates().evaluate(self.repo)?)
}
/// Find the next commit to evaluate, or determine that there are no more
/// steps.
pub async fn next_step(&mut self) -> Result<NextStep, BisectionError> {
if self.aborted {
return Ok(NextStep::Done(BisectionResult::Abort));
}
// Intersect the input range with the current bad range and then bisect it to
// find the next commit to evaluate.
// Skipped revisions are simply subtracted from the set.
// TODO: Handle long ranges of skipped revisions better
let to_evaluate_expr = self.candidates().bisect().latest(1);
let to_evaluate_set = to_evaluate_expr.evaluate(self.repo)?;
if let Some(commit_id) = pin!(to_evaluate_set.stream()).try_next().await? {
let commit = self.repo.store().get_commit_async(&commit_id).await?;
Ok(NextStep::Evaluate(commit))
} else {
let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect());
let bad_roots = bad_expr.roots().evaluate(self.repo)?;
let bad_commits: Vec<_> = bad_roots
.stream()
.commits(self.repo.store())
.try_collect()
.await?;
if bad_commits.is_empty() {
Ok(NextStep::Done(BisectionResult::Indeterminate))
} else {
// were any commits skipped that could also be bad?
let mut todo: VecDeque<Commit> = VecDeque::from(bad_commits.clone());
let mut possibly_bad: Vec<Commit> = Vec::new();
while let Some(commit) = todo.pop_front() {
for parent in commit.parents().await? {
if self.skipped_commits.contains(parent.id()) {
possibly_bad.push(parent.clone());
todo.push_back(parent);
}
}
}
if possibly_bad.is_empty() {
Ok(NextStep::Done(BisectionResult::Found(bad_commits)))
} else {
Ok(NextStep::Done(BisectionResult::FoundDespiteSkips {
bad_commits,
possibly_bad,
}))
}
}
}
}
}