// 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. #![allow(missing_docs)] use std::cmp::{Ordering, Reverse};use std::collections::{BTreeSet, BinaryHeap, HashSet};use std::fmt;use std::iter::Peekable;use std::ops::Range;use std::sync::Arc; use itertools::Itertools; use super::revset_graph_iterator::RevsetGraphIterator;use crate::backend::{ChangeId, CommitId, MillisSinceEpoch};use crate::default_index::{AsCompositeIndex, CompositeIndex, IndexEntry, IndexPosition};use crate::matchers::{EverythingMatcher, Matcher, PrefixMatcher, Visit};use crate::repo_path::RepoPath;use crate::revset::{    ResolvedExpression, ResolvedPredicateExpression, Revset, RevsetEvaluationError,    RevsetFilterPredicate, GENERATION_RANGE_FULL,};use crate::revset_graph::RevsetGraphEdge;use crate::rewrite;use crate::store::Store; 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, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a>;} impl<T: ToPredicateFn + ?Sized> ToPredicateFn for Box<T> {    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        <T as ToPredicateFn>::to_predicate_fn(self, index)    }} trait InternalRevset: fmt::Debug + ToPredicateFn {    // All revsets currently iterate in order of descending index position    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a>;     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a>;     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a;} impl<T: InternalRevset + ?Sized> InternalRevset for Box<T> {    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        <T as InternalRevset>::entries(self, index)    }     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        <T as InternalRevset>::positions(self, index)    }     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a,    {        <T as InternalRevset>::into_predicate(*self)    }} pub struct RevsetImpl<I> {    inner: Box<dyn InternalRevset>,    index: I,} impl<I: AsCompositeIndex> RevsetImpl<I> {    fn new(inner: Box<dyn InternalRevset>, index: I) -> Self {        Self { inner, index }    }     fn entries(&self) -> Box<dyn Iterator<Item = IndexEntry<'_>> + '_> {        self.inner.entries(self.index.as_composite())    }     fn positions(&self) -> Box<dyn Iterator<Item = IndexPosition> + '_> {        self.inner.positions(self.index.as_composite())    }     pub fn iter_graph_impl(&self) -> RevsetGraphIterator<'_, '_> {        RevsetGraphIterator::new(self.index.as_composite(), self.entries())    }} 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> Revset for RevsetImpl<I> {    fn iter(&self) -> Box<dyn Iterator<Item = CommitId> + '_> {        Box::new(self.entries().map(|index_entry| index_entry.commit_id()))    }     fn commit_change_ids(&self) -> Box<dyn Iterator<Item = (CommitId, ChangeId)> + '_> {        Box::new(            self.entries()                .map(|index_entry| (index_entry.commit_id(), index_entry.change_id())),        )    }     fn iter_graph(&self) -> Box<dyn Iterator<Item = (CommitId, Vec<RevsetGraphEdge>)> + '_> {        Box::new(self.iter_graph_impl())    }     fn is_empty(&self) -> bool {        self.positions().next().is_none()    }     fn count_estimate(&self) -> (usize, Option<usize>) {        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).count();            if count < 10 {                (count, Some(count))            } else {                (10, None)            }        } else {            let count = self.positions().count();            (count, Some(count))        }    }} #[derive(Debug)]struct EagerRevset {    positions: Vec<IndexPosition>,} impl EagerRevset {    pub const fn empty() -> Self {        EagerRevset {            positions: Vec::new(),        }    }} impl InternalRevset for EagerRevset {    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        let entries = self            .positions            .iter()            .map(move |&pos| index.entry_by_pos(pos));        Box::new(entries)    }     fn positions<'a, 'index: 'a>(        &'a self,        _index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        Box::new(self.positions.iter().copied())    }     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a,    {        self    }} impl ToPredicateFn for EagerRevset {    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        _index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        predicate_fn_from_positions(self.positions.iter().copied())    }} struct RevWalkRevset<F> {    walk: F,} impl<F> RevWalkRevset<F>where    // Returns trait object because we can't express the following constraints    // without using named lifetime and type parameter:    //    //     for<'index>    //         F: Fn(CompositeIndex<'index>) -> _,    //         F::Output: Iterator<Item = IndexEntry<'index>> + 'index    //    // There's a workaround, but it doesn't help infer closure types.    // https://github.com/rust-lang/rust/issues/47815    // https://users.rust-lang.org/t/hrtb-on-multiple-generics/34255    F: Fn(CompositeIndex<'_>) -> Box<dyn Iterator<Item = IndexEntry<'_>> + '_>,{    fn new(walk: F) -> Self {        RevWalkRevset { walk }    }} impl<F> fmt::Debug for RevWalkRevset<F> {    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {        f.debug_struct("RevWalkRevset").finish_non_exhaustive()    }} impl<F> InternalRevset for RevWalkRevset<F>where    F: Fn(CompositeIndex<'_>) -> Box<dyn Iterator<Item = IndexEntry<'_>> + '_>,{    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        (self.walk)(index)    }     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        Box::new(self.entries(index).map(|entry| entry.position()))    }     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a,    {        self    }} impl<F> ToPredicateFn for RevWalkRevset<F>where    F: Fn(CompositeIndex<'_>) -> Box<dyn Iterator<Item = IndexEntry<'_>> + '_>,{    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        predicate_fn_from_entries(self.entries(index))    }} fn predicate_fn_from_entries<'index, 'iter>(    iter: impl Iterator<Item = IndexEntry<'index>> + 'iter,) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'iter> {    predicate_fn_from_positions(iter.map(|entry| entry.position()))} fn predicate_fn_from_positions<'iter>(    iter: impl Iterator<Item = IndexPosition> + 'iter,) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'iter> {    let mut iter = iter.fuse().peekable();    Box::new(move |entry| {        while iter.next_if(|&pos| pos > entry.position()).is_some() {            continue;        }        iter.next_if(|&pos| pos == entry.position()).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 entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        let p = self.predicate.to_predicate_fn(index);        Box::new(self.candidates.entries(index).filter(p))    }     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        Box::new(self.entries(index).map(|entry| entry.position()))    }     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a,    {        self    }} impl<S, P> ToPredicateFn for FilterRevset<S, P>where    S: ToPredicateFn,    P: ToPredicateFn,{    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        let mut p1 = self.candidates.to_predicate_fn(index);        let mut p2 = self.predicate.to_predicate_fn(index);        Box::new(move |entry| p1(entry) && p2(entry))    }} #[derive(Debug)]struct NotInPredicate<S>(S); impl<S: ToPredicateFn> ToPredicateFn for NotInPredicate<S> {    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        let mut p = self.0.to_predicate_fn(index);        Box::new(move |entry| !p(entry))    }} #[derive(Debug)]struct UnionRevset<S1, S2> {    set1: S1,    set2: S2,} impl<S1, S2> InternalRevset for UnionRevset<S1, S2>where    S1: InternalRevset,    S2: InternalRevset,{    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        Box::new(union_by(            self.set1.entries(index),            self.set2.entries(index),            |entry1, entry2| entry1.position().cmp(&entry2.position()).reverse(),        ))    }     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        Box::new(union_by(            self.set1.positions(index),            self.set2.positions(index),            |pos1, pos2| pos1.cmp(pos2).reverse(),        ))    }     fn into_predicate<'a>(self: Box<Self>) -> Box<dyn ToPredicateFn + 'a>    where        Self: 'a,    {        self    }} impl<S1, S2> ToPredicateFn for UnionRevset<S1, S2>where    S1: ToPredicateFn,    S2: ToPredicateFn,{    fn to_predicate_fn<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn FnMut(&IndexEntry<'_>) -> bool + 'a> {        let mut p1 = self.set1.to_predicate_fn(index);        let mut p2 = self.set2.to_predicate_fn(index);        Box::new(move |entry| p1(entry) || p2(entry))    }} /// Iterator that merges two sorted iterators.////// The input items should be sorted in ascending order by the `cmp` function.struct UnionByIterator<I1: Iterator, I2: Iterator, C> {    iter1: Peekable<I1>,    iter2: Peekable<I2>,    cmp: C,} impl<I1, I2, C> Iterator for UnionByIterator<I1, I2, C>where    I1: Iterator,    I2: Iterator<Item = I1::Item>,    C: FnMut(&I1::Item, &I2::Item) -> Ordering,{    type Item = I1::Item;     fn next(&mut self) -> Option<Self::Item> {        match (self.iter1.peek(), self.iter2.peek()) {            (None, _) => self.iter2.next(),            (_, None) => self.iter1.next(),            (Some(item1), Some(item2)) => match (self.cmp)(item1, item2) {                Ordering::Less => self.iter1.next(),                Ordering::Equal => {                    self.iter2.next();                    self.iter1.next()                }                Ordering::Greater => self.iter2.next(),            },        }    }} fn union_by<I1, I2, C>(    iter1: I1,    iter2: I2,    cmp: C,) -> UnionByIterator<I1::IntoIter, I2::IntoIter, C>where    I1: IntoIterator,    I2: IntoIterator<Item = I1::Item>,    C: FnMut(&I1::Item, &I2::Item) -> Ordering,{    UnionByIterator {        iter1: iter1.into_iter().peekable(),        iter2: iter2.into_iter().peekable(),        cmp,    }} #[derive(Debug)]struct IntersectionRevset<S1, S2> {    set1: S1,    set2: S2,} impl<S1, S2> InternalRevset for IntersectionRevset<S1, S2>where    S1: InternalRevset,    S2: InternalRevset,{    fn entries<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexEntry<'index>> + 'a> {        Box::new(intersection_by(            self.set1.entries(index),            self.set2.positions(index),            |entry1, pos2| entry1.position().cmp(pos2).reverse(),        ))    }     fn positions<'a, 'index: 'a>(        &'a self,        index: CompositeIndex<'index>,    ) -> Box<dyn Iterator<Item = IndexPosition> + 'a> {        Box::new(intersection_by(            self.set1.positions(index),            self.set2.positions(index),            |pos1, pos2| pos1.cmp(pos2).reverse(),        ))    }

Lines 1–500 of 1234. Load more