// Copyright 2023 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::cell::RefCell;use std::cmp::Ordering;use std::cmp::Reverse;use std::collections::BinaryHeap;use std::collections::HashSet;use std::convert::Infallible;use std::fmt;use std::iter;use std::ops::Range;use std::rc::Rc;use std::sync::Arc; use bstr::BString;use futures::StreamExt as _;use itertools::Itertools as _;use pollster::FutureExt as _; use super::composite::AsCompositeIndex;use super::composite::CompositeIndex;use super::entry::GlobalCommitPosition;use super::rev_walk::EagerRevWalk;use super::rev_walk::PeekableRevWalk;use super::rev_walk::RevWalk;use super::rev_walk::RevWalkBuilder;use super::revset_graph_iterator::RevsetGraphWalk;use crate::backend::BackendResult;use crate::backend::ChangeId;use crate::backend::CommitId;use crate::backend::MillisSinceEpoch;use crate::commit::Commit;use crate::conflicts::MaterializedTreeValue;use crate::conflicts::materialize_tree_value;use crate::diff::ContentDiff;use crate::diff::DiffHunkKind;use crate::files;use crate::graph::GraphNode;use crate::matchers::FilesMatcher;use crate::matchers::Matcher;use crate::matchers::Visit;use crate::merge::Merge;use crate::object_id::ObjectId as _;use crate::repo_path::RepoPath;use crate::revset::GENERATION_RANGE_FULL;use crate::revset::ResolvedExpression;use crate::revset::ResolvedPredicateExpression;use crate::revset::Revset;use crate::revset::RevsetContainingFn;use crate::revset::RevsetEvaluationError;use crate::revset::RevsetFilterPredicate;use crate::rewrite;use crate::store::Store;use crate::str_util::StringPattern;use crate::tree_merge::MergeOptions;use crate::tree_merge::resolve_file_values;use crate::union_find; type BoxedPredicateFn<'a> = Box<    dyn FnMut(&CompositeIndex, GlobalCommitPosition) -> Result<bool, RevsetEvaluationError> + 'a,>;pub(super) type BoxedRevWalk<'a> = Box<    dyn RevWalk<CompositeIndex, Item = Result<GlobalCommitPosition, RevsetEvaluationError>> + 'a,>; trait ToPredicateFn: fmt::Debug {    /// Creates function that tests if the given entry is included in the set.    ///    /// The predicate function is evaluated in order of `RevsetIterator`.    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a;} impl<T: ToPredicateFn + ?Sized> ToPredicateFn for Box<T> {    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        <T as ToPredicateFn>::to_predicate_fn(self)    }} trait InternalRevset: fmt::Debug + ToPredicateFn {    // All revsets currently iterate in order of descending index position    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a;} impl<T: InternalRevset + ?Sized> InternalRevset for Box<T> {    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a,    {        <T as InternalRevset>::positions(self)    }} pub(super) struct RevsetImpl<I> {    inner: Box<dyn InternalRevset>,    index: I,} impl<I: AsCompositeIndex + Clone> RevsetImpl<I> {    fn new(inner: Box<dyn InternalRevset>, index: I) -> Self {        Self { inner, index }    }     fn positions(        &self,    ) -> impl Iterator<Item = Result<GlobalCommitPosition, RevsetEvaluationError>> {        self.inner.positions().attach(self.index.as_composite())    }     pub fn iter_graph_impl(        &self,        skip_transitive_edges: bool,    ) -> impl Iterator<Item = Result<GraphNode<CommitId>, RevsetEvaluationError>> + use<I> {        let index = self.index.clone();        let walk = self.inner.positions();        let mut graph_walk = RevsetGraphWalk::new(walk, skip_transitive_edges);        iter::from_fn(move || graph_walk.next(index.as_composite()))    }} impl<I> fmt::Debug for RevsetImpl<I> {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        f.debug_struct("RevsetImpl")            .field("inner", &self.inner)            .finish_non_exhaustive()    }} impl<I: AsCompositeIndex + Clone> Revset for RevsetImpl<I> {    fn iter<'a>(&self) -> Box<dyn Iterator<Item = Result<CommitId, RevsetEvaluationError>> + 'a>    where        Self: 'a,    {        let index = self.index.clone();        let mut walk = self            .inner            .positions()            .map(|index, pos| Ok(index.commits().entry_by_pos(pos?).commit_id()));        Box::new(iter::from_fn(move || walk.next(index.as_composite())))    }     fn commit_change_ids<'a>(        &self,    ) -> Box<dyn Iterator<Item = Result<(CommitId, ChangeId), RevsetEvaluationError>> + 'a>    where        Self: 'a,    {        let index = self.index.clone();        let mut walk = self.inner.positions().map(|index, pos| {            let entry = index.commits().entry_by_pos(pos?);            Ok((entry.commit_id(), entry.change_id()))        });        Box::new(iter::from_fn(move || walk.next(index.as_composite())))    }     fn iter_graph<'a>(        &self,    ) -> Box<dyn Iterator<Item = Result<GraphNode<CommitId>, RevsetEvaluationError>> + 'a>    where        Self: 'a,    {        let skip_transitive_edges = true;        Box::new(self.iter_graph_impl(skip_transitive_edges))    }     fn is_empty(&self) -> bool {        self.positions().next().is_none()    }     fn count_estimate(&self) -> Result<(usize, Option<usize>), RevsetEvaluationError> {        if cfg!(feature = "testing") {            // Exercise the estimation feature in tests. (If we ever have a Revset            // implementation in production code that returns estimates, we can probably            // remove this and rewrite the associated tests.)            let count = self                .positions()                .take(10)                .process_results(|iter| iter.count())?;            if count < 10 {                Ok((count, Some(count)))            } else {                Ok((10, None))            }        } else {            let count = self.positions().process_results(|iter| iter.count())?;            Ok((count, Some(count)))        }    }     fn containing_fn<'a>(&self) -> Box<RevsetContainingFn<'a>>    where        Self: 'a,    {        let positions = PositionsAccumulator::new(self.index.clone(), self.inner.positions());        Box::new(move |commit_id| positions.contains(commit_id))    }} /// Incrementally consumes `RevWalk` of the revset collecting positions.struct PositionsAccumulator<'a, I> {    index: I,    inner: RefCell<PositionsAccumulatorInner<'a>>,} impl<'a, I: AsCompositeIndex> PositionsAccumulator<'a, I> {    fn new(index: I, walk: BoxedRevWalk<'a>) -> Self {        let inner = RefCell::new(PositionsAccumulatorInner {            walk,            consumed_positions: Vec::new(),        });        Self { index, inner }    }     /// Checks whether the commit is in the revset.    fn contains(&self, commit_id: &CommitId) -> Result<bool, RevsetEvaluationError> {        let index = self.index.as_composite();        let Some(position) = index.commits().commit_id_to_pos(commit_id) else {            return Ok(false);        };         let mut inner = self.inner.borrow_mut();        inner.consume_to(index, position)?;        let found = inner            .consumed_positions            .binary_search_by(|p| p.cmp(&position).reverse())            .is_ok();        Ok(found)    }     #[cfg(test)]    fn consumed_len(&self) -> usize {        self.inner.borrow().consumed_positions.len()    }} /// Helper struct for [`PositionsAccumulator`] to simplify interior mutability.struct PositionsAccumulatorInner<'a> {    walk: BoxedRevWalk<'a>,    consumed_positions: Vec<GlobalCommitPosition>,} impl PositionsAccumulatorInner<'_> {    /// Consumes `RevWalk` to a desired position but not deeper.    fn consume_to(        &mut self,        index: &CompositeIndex,        desired_position: GlobalCommitPosition,    ) -> Result<(), RevsetEvaluationError> {        let last_position = self.consumed_positions.last();        if last_position.is_some_and(|&pos| pos <= desired_position) {            return Ok(());        }        while let Some(position) = self.walk.next(index).transpose()? {            self.consumed_positions.push(position);            if position <= desired_position {                return Ok(());            }        }        Ok(())    }} /// Adapter for precomputed `GlobalCommitPosition`s.#[derive(Debug)]struct EagerRevset {    positions: Vec<GlobalCommitPosition>,} impl EagerRevset {    pub const fn empty() -> Self {        Self {            positions: Vec::new(),        }    }} impl InternalRevset for EagerRevset {    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a,    {        let walk = EagerRevWalk::new(self.positions.clone().into_iter());        Box::new(walk.map(|_index, pos| Ok(pos)))    }} impl ToPredicateFn for EagerRevset {    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        let walk = EagerRevWalk::new(self.positions.clone().into_iter());        predicate_fn_from_rev_walk(walk)    }} /// Adapter for infallible `RevWalk` of `GlobalCommitPosition`s.struct RevWalkRevset<W> {    walk: W,} impl<W> fmt::Debug for RevWalkRevset<W> {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        f.debug_struct("RevWalkRevset").finish_non_exhaustive()    }} impl<W> InternalRevset for RevWalkRevset<W>where    W: RevWalk<CompositeIndex, Item = GlobalCommitPosition> + Clone,{    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a,    {        Box::new(self.walk.clone().map(|_index, pos| Ok(pos)))    }} impl<W> ToPredicateFn for RevWalkRevset<W>where    W: RevWalk<CompositeIndex, Item = GlobalCommitPosition> + Clone,{    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        predicate_fn_from_rev_walk(self.walk.clone())    }} fn predicate_fn_from_rev_walk<'a, W>(walk: W) -> BoxedPredicateFn<'a>where    W: RevWalk<CompositeIndex, Item = GlobalCommitPosition> + 'a,{    let mut walk = walk.peekable();    Box::new(move |index, entry_pos| {        while walk.next_if(index, |&pos| pos > entry_pos).is_some() {            continue;        }        Ok(walk.next_if(index, |&pos| pos == entry_pos).is_some())    })} #[derive(Debug)]struct FilterRevset<S, P> {    candidates: S,    predicate: P,} impl<S, P> InternalRevset for FilterRevset<S, P>where    S: InternalRevset,    P: ToPredicateFn,{    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a,    {        let mut p = self.predicate.to_predicate_fn();        Box::new(self.candidates.positions().filter_map(move |index, pos| {            pos.and_then(|pos| Ok(p(index, pos)?.then_some(pos)))                .transpose()        }))    }} impl<S, P> ToPredicateFn for FilterRevset<S, P>where    S: ToPredicateFn,    P: ToPredicateFn,{    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        let mut p1 = self.candidates.to_predicate_fn();        let mut p2 = self.predicate.to_predicate_fn();        Box::new(move |index, pos| Ok(p1(index, pos)? && p2(index, pos)?))    }} #[derive(Debug)]struct NotInPredicate<S>(S); impl<S: ToPredicateFn> ToPredicateFn for NotInPredicate<S> {    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        let mut p = self.0.to_predicate_fn();        Box::new(move |index, pos| Ok(!p(index, pos)?))    }} #[derive(Debug)]struct UnionRevset<S1, S2> {    set1: S1,    set2: S2,} impl<S1, S2> InternalRevset for UnionRevset<S1, S2>where    S1: InternalRevset,    S2: InternalRevset,{    fn positions<'a>(&self) -> BoxedRevWalk<'a>    where        Self: 'a,    {        Box::new(union_by(            self.set1.positions(),            self.set2.positions(),            |pos1, pos2| pos1.cmp(pos2).reverse(),        ))    }} impl<S1, S2> ToPredicateFn for UnionRevset<S1, S2>where    S1: ToPredicateFn,    S2: ToPredicateFn,{    fn to_predicate_fn<'a>(&self) -> BoxedPredicateFn<'a>    where        Self: 'a,    {        let mut p1 = self.set1.to_predicate_fn();        let mut p2 = self.set2.to_predicate_fn();        Box::new(move |index, pos| Ok(p1(index, pos)? || p2(index, pos)?))    }} /// `RevWalk` node that merges two sorted walk nodes.////// The input items should be sorted in ascending order by the `cmp` function.struct UnionRevWalk<I: ?Sized, W1: RevWalk<I>, W2: RevWalk<I>, C> {    walk1: PeekableRevWalk<I, W1>,    walk2: PeekableRevWalk<I, W2>,    cmp: C,} impl<I, T, E, W1, W2, C> RevWalk<I> for UnionRevWalk<I, W1, W2, C>where    I: ?Sized,    W1: RevWalk<I, Item = Result<T, E>>,    W2: RevWalk<I, Item = Result<T, E>>,    C: FnMut(&T, &T) -> Ordering,{    type Item = W1::Item;     fn next(&mut self, index: &I) -> Option<Self::Item> {        match (self.walk1.peek(index), self.walk2.peek(index)) {            (None, _) => self.walk2.next(index),            (_, None) => self.walk1.next(index),            (Some(Ok(item1)), Some(Ok(item2))) => match (self.cmp)(item1, item2) {                Ordering::Less => self.walk1.next(index),                Ordering::Equal => {                    self.walk2.next(index);                    self.walk1.next(index)                }                Ordering::Greater => self.walk2.next(index),            },            (Some(Err(_)), _) => self.walk1.next(index),            (_, Some(Err(_))) => self.walk2.next(index),        }    }} fn union_by<I, T, E, W1, W2, C>(walk1: W1, walk2: W2, cmp: C) -> UnionRevWalk<I, W1, W2, C>where    I: ?Sized,    W1: RevWalk<I, Item = Result<T, E>>,    W2: RevWalk<I, Item = Result<T, E>>,    C: FnMut(&T, &T) -> Ordering,{    UnionRevWalk {        walk1: walk1.peekable(),        walk2: walk2.peekable(),        cmp,    }}

Lines 1–500 of 1924. Load more