jj_lib/

bisect.rs

// 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::fmt;
use std::iter;
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, PartialEq, Eq, Clone)]
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,
        }
    }

    /// Returns the inverted evaluation if `condition` is true.
    pub fn invert_if(self, condition: bool) -> Self {
        if condition { self.invert() } else { self }
    }
}
impl fmt::Display for Evaluation {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}",
            match self {
                Self::Good => "good",
                Self::Bad => "bad",
                Self::Skip => "skipped",
                Self::Abort => "aborted",
            }
        )
    }
}

/// 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,
    verifications: Vec<(CommitId, Evaluation)>,
}

/// 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,
    /// Bisection preconditions were not met.
    VerificationFailed,
}

/// The next bisection step.
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum NextStep {
    /// The commit must evaluate a certain way.
    Verify {
        /// The commit being verified.
        commit: Commit,
        /// If the commit does not evaluate to this, bisection isn't possible.
        expected_evaluation: Evaluation,
    },
    /// 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.
    /// If `verify_preconditions` is true, these assumptions are verified.
    pub async fn new(
        repo: &'repo dyn Repo,
        input_range: Arc<ResolvedRevsetExpression>,
        verify_preconditions: bool,
    ) -> Result<Self, BisectionError> {
        let bad_commits: Vec<CommitId> = input_range
            .heads()
            .evaluate(repo)?
            .stream()
            .try_collect()
            .await?;
        let good_commits: Vec<CommitId> = input_range
            .connected()
            .parents()
            .minus(&input_range.connected())
            .evaluate(repo)?
            .stream()
            .try_collect()
            .await?;

        let verifications: Vec<(CommitId, Evaluation)> = if verify_preconditions {
            // these will be run in reverse order
            iter::empty()
                .chain(
                    good_commits
                        .iter()
                        .map(|commit_id| (commit_id.clone(), Evaluation::Good)),
                )
                .chain(
                    bad_commits
                        .iter()
                        .map(|commit_id| (commit_id.clone(), Evaluation::Bad)),
                )
                .collect()
        } else {
            vec![]
        };

        Ok(Self {
            repo,
            input_range,
            verifications,
            bad_commits: HashSet::from_iter(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>, 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(verification) = self.verifications.pop() {
            let commit = self.repo.store().get_commit_async(&verification.0).await?;
            Ok(NextStep::Verify {
                commit,
                expected_evaluation: verification.1,
            })
        } else 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,
                    }))
                }
            }
        }
    }
}