jj_lib/
bisect.rs

1// Copyright 2025 The Jujutsu Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Bisect a range of commits.
16
17use std::collections::HashSet;
18use std::collections::VecDeque;
19use std::pin::pin;
20use std::sync::Arc;
21
22use futures::TryStreamExt as _;
23use thiserror::Error;
24
25use crate::backend::BackendError;
26use crate::backend::CommitId;
27use crate::commit::Commit;
28use crate::repo::Repo;
29use crate::revset::ResolvedRevsetExpression;
30use crate::revset::Revset;
31use crate::revset::RevsetEvaluationError;
32use crate::revset::RevsetExpression;
33use crate::revset::RevsetStreamExt as _;
34
35/// An error that occurred while bisecting
36#[derive(Error, Debug)]
37pub enum BisectionError {
38    /// Failed to read data from the backend
39    #[error("Failed to read data from the backend involved in bisection")]
40    BackendError(#[from] BackendError),
41    /// Failed to evaluate a revset
42    #[error("Failed to evaluate a revset involved in bisection")]
43    RevsetEvaluationError(#[from] RevsetEvaluationError),
44}
45
46/// Indicates whether a given commit was good, bad, or if it could not be
47/// determined.
48#[derive(Debug)]
49pub enum Evaluation {
50    /// The commit was good
51    Good,
52    /// The commit was bad
53    Bad,
54    /// It could not be determined whether the commit was good or bad
55    Skip,
56    /// The commit caused an abort
57    Abort,
58}
59
60impl Evaluation {
61    /// Maps the current evaluation to its inverse.
62    ///
63    /// Maps `Good`->`Bad`, `Bad`->`Good`, and keeps `Skip` as is.
64    pub fn invert(self) -> Self {
65        use Evaluation::*;
66        match self {
67            Good => Bad,
68            Bad => Good,
69            Skip => Skip,
70            Abort => Abort,
71        }
72    }
73}
74
75/// Performs bisection to find the first bad commit in a range.
76pub struct Bisector<'repo> {
77    repo: &'repo dyn Repo,
78    input_range: Arc<ResolvedRevsetExpression>,
79    good_commits: HashSet<CommitId>,
80    bad_commits: HashSet<CommitId>,
81    skipped_commits: HashSet<CommitId>,
82    aborted: bool,
83}
84
85/// The result of bisection.
86#[derive(Debug, PartialEq, Eq, Clone)]
87pub enum BisectionResult {
88    /// Found the first bad commit(s). It should be exactly one unless the input
89    /// range had multiple disjoint heads.
90    Found(Vec<Commit>),
91    /// The bisection frontier is blurred by the presence of skipped commits
92    FoundDespiteSkips {
93        /// The first commit(s) that did evaluate as bad
94        bad_commits: Vec<Commit>,
95        /// Skipped commits sandwiched between good and bad commits
96        /// Are they good or bad? We couldn't tell.
97        possibly_bad: Vec<Commit>,
98    },
99    /// Could not determine the first bad commit because it was in a
100    /// skipped range.
101    Indeterminate,
102    /// Bisection was aborted.
103    Abort,
104}
105
106/// The next bisection step.
107#[derive(Debug, PartialEq, Eq, Clone)]
108pub enum NextStep {
109    /// The commit must be evaluated.
110    Evaluate(Commit),
111    /// Bisection is complete.
112    Done(BisectionResult),
113}
114
115impl<'repo> Bisector<'repo> {
116    /// Create a new bisector. The range's heads are assumed to be bad.
117    /// Parents of the range's roots are assumed to be good.
118    pub async fn new(
119        repo: &'repo dyn Repo,
120        input_range: Arc<ResolvedRevsetExpression>,
121    ) -> Result<Self, BisectionError> {
122        let bad_commits = input_range
123            .heads()
124            .evaluate(repo)?
125            .stream()
126            .try_collect()
127            .await?;
128        Ok(Self {
129            repo,
130            input_range,
131            bad_commits,
132            good_commits: HashSet::new(),
133            skipped_commits: HashSet::new(),
134            aborted: false,
135        })
136    }
137
138    /// Mark a commit good.
139    pub fn mark_good(&mut self, id: CommitId) {
140        assert!(!self.bad_commits.contains(&id));
141        assert!(!self.skipped_commits.contains(&id));
142        assert!(!self.aborted);
143        self.good_commits.insert(id);
144    }
145
146    /// Mark a commit bad.
147    pub fn mark_bad(&mut self, id: CommitId) {
148        assert!(!self.good_commits.contains(&id));
149        assert!(!self.skipped_commits.contains(&id));
150        assert!(!self.aborted);
151        self.bad_commits.insert(id);
152    }
153
154    /// Mark a commit as skipped (cannot be determined if it's good or bad).
155    pub fn mark_skipped(&mut self, id: CommitId) {
156        assert!(!self.good_commits.contains(&id));
157        assert!(!self.bad_commits.contains(&id));
158        assert!(!self.aborted);
159        self.skipped_commits.insert(id);
160    }
161
162    /// Mark a commit as causing an abort
163    pub fn mark_abort(&mut self, id: CommitId) {
164        // TODO: Right now, we only use this state for triggering an abort.
165        // A potential improvement would be to make the CLI print out the revset with
166        // the current status of each change, making it possible for a user
167        // to restart an aborted bisect in progress.
168        assert!(!self.good_commits.contains(&id));
169        assert!(!self.bad_commits.contains(&id));
170        assert!(!self.skipped_commits.contains(&id));
171        self.aborted = true;
172    }
173
174    /// Mark a commit as good, bad, or skipped, according to the outcome in
175    /// `evaluation`.
176    pub fn mark(&mut self, id: CommitId, evaluation: Evaluation) {
177        match evaluation {
178            Evaluation::Good => self.mark_good(id),
179            Evaluation::Bad => self.mark_bad(id),
180            Evaluation::Skip => self.mark_skipped(id),
181            Evaluation::Abort => self.mark_abort(id),
182        }
183    }
184
185    /// The commits that were marked good.
186    pub fn good_commits(&self) -> &HashSet<CommitId> {
187        &self.good_commits
188    }
189
190    /// The commits that were marked bad.
191    pub fn bad_commits(&self) -> &HashSet<CommitId> {
192        &self.bad_commits
193    }
194
195    /// The commits that were skipped.
196    pub fn skipped_commits(&self) -> &HashSet<CommitId> {
197        &self.skipped_commits
198    }
199
200    fn candidates(&self) -> Arc<ResolvedRevsetExpression> {
201        let good_expr = RevsetExpression::commits(self.good_commits.iter().cloned().collect());
202        let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect());
203        let skipped_expr =
204            RevsetExpression::commits(self.skipped_commits.iter().cloned().collect());
205
206        self.input_range
207            .intersection(&good_expr.heads().range(&bad_expr.roots()))
208            .minus(&bad_expr)
209            .minus(&skipped_expr)
210    }
211
212    /// Returns the evaluated revset representing the remaining candidate
213    /// commits. Can be used for getting an estimate of how many commits are
214    /// left to evaluate.
215    pub async fn remaining_revset(&self) -> Result<Box<dyn Revset + 'repo>, BisectionError> {
216        Ok(self.candidates().evaluate(self.repo)?)
217    }
218
219    /// Find the next commit to evaluate, or determine that there are no more
220    /// steps.
221    pub async fn next_step(&mut self) -> Result<NextStep, BisectionError> {
222        if self.aborted {
223            return Ok(NextStep::Done(BisectionResult::Abort));
224        }
225        // Intersect the input range with the current bad range and then bisect it to
226        // find the next commit to evaluate.
227        // Skipped revisions are simply subtracted from the set.
228        // TODO: Handle long ranges of skipped revisions better
229        let to_evaluate_expr = self.candidates().bisect().latest(1);
230        let to_evaluate_set = to_evaluate_expr.evaluate(self.repo)?;
231        if let Some(commit_id) = pin!(to_evaluate_set.stream()).try_next().await? {
232            let commit = self.repo.store().get_commit_async(&commit_id).await?;
233            Ok(NextStep::Evaluate(commit))
234        } else {
235            let bad_expr = RevsetExpression::commits(self.bad_commits.iter().cloned().collect());
236            let bad_roots = bad_expr.roots().evaluate(self.repo)?;
237            let bad_commits: Vec<_> = bad_roots
238                .stream()
239                .commits(self.repo.store())
240                .try_collect()
241                .await?;
242            if bad_commits.is_empty() {
243                Ok(NextStep::Done(BisectionResult::Indeterminate))
244            } else {
245                // were any commits skipped that could also be bad?
246                let mut todo: VecDeque<Commit> = VecDeque::from(bad_commits.clone());
247                let mut possibly_bad: Vec<Commit> = Vec::new();
248                while let Some(commit) = todo.pop_front() {
249                    for parent in commit.parents().await? {
250                        if self.skipped_commits.contains(parent.id()) {
251                            possibly_bad.push(parent.clone());
252                            todo.push_back(parent);
253                        }
254                    }
255                }
256                if possibly_bad.is_empty() {
257                    Ok(NextStep::Done(BisectionResult::Found(bad_commits)))
258                } else {
259                    Ok(NextStep::Done(BisectionResult::FoundDespiteSkips {
260                        bad_commits,
261                        possibly_bad,
262                    }))
263                }
264            }
265        }
266    }
267}
jj_lib/bisect.rs

jj_lib/
bisect.rs
