// 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::cmp::Reverse;use std::cmp::max;use std::collections::HashMap;use std::collections::HashSet;use std::iter::Fuse;use std::iter::FusedIterator;use std::ops::Range; use smallvec::SmallVec; use super::composite::CompositeCommitIndex;use super::composite::CompositeIndex;use super::entry::GlobalCommitPosition;use super::entry::SmallGlobalCommitPositionsVec;use super::rev_walk_queue::RevWalkQueue;use super::rev_walk_queue::RevWalkWorkItem;use crate::revset::PARENTS_RANGE_FULL; /// Like `Iterator`, but doesn't borrow the `index` internally.pub(super) trait RevWalk<I: ?Sized> {    type Item;     /// Advances the iteration and returns the next item.    ///    /// The caller must provide the same `index` instance.    ///    /// Returns `None` when the iteration is finished. Once `None` is returned,    /// this will never resume. In other words, a `RevWalk` is fused.    fn next(&mut self, index: &I) -> Option<Self::Item>;     // The following methods are provided for convenience. They are not supposed    // to be reimplemented.     /// Wraps in adapter that will filter and transform items by the given    /// function.    fn filter_map<B, F>(self, f: F) -> FilterMapRevWalk<Self, F>    where        Self: Sized,        F: FnMut(&I, Self::Item) -> Option<B>,    {        FilterMapRevWalk { walk: self, f }    }     /// Wraps in adapter that will transform items by the given function.    fn map<B, F>(self, f: F) -> MapRevWalk<Self, F>    where        Self: Sized,        F: FnMut(&I, Self::Item) -> B,    {        MapRevWalk { walk: self, f }    }     /// Wraps in adapter that can peek one more item without consuming.    fn peekable(self) -> PeekableRevWalk<I, Self>    where        Self: Sized,    {        PeekableRevWalk {            walk: self,            peeked: None,        }    }     /// Reattaches the underlying `index`.    fn attach(self, index: &I) -> RevWalkBorrowedIndexIter<'_, I, Self>    where        Self: Sized,    {        RevWalkBorrowedIndexIter { index, walk: self }    }} impl<I: ?Sized, W: RevWalk<I> + ?Sized> RevWalk<I> for Box<W> {    type Item = W::Item;     fn next(&mut self, index: &I) -> Option<Self::Item> {        <W as RevWalk<I>>::next(self, index)    }} /// Adapter that turns `Iterator` into `RevWalk` by dropping index argument.////// As the name suggests, the source object is usually a slice or `Vec`.#[derive(Clone, Debug)]pub(super) struct EagerRevWalk<T> {    iter: Fuse<T>,} impl<T: Iterator> EagerRevWalk<T> {    pub fn new(iter: T) -> Self {        Self { iter: iter.fuse() }    }} impl<I: ?Sized, T: Iterator> RevWalk<I> for EagerRevWalk<T> {    type Item = T::Item;     fn next(&mut self, _index: &I) -> Option<Self::Item> {        self.iter.next()    }} #[derive(Clone, Debug)]#[must_use]pub(super) struct FilterMapRevWalk<W, F> {    walk: W,    f: F,} impl<B, I, W, F> RevWalk<I> for FilterMapRevWalk<W, F>where    I: ?Sized,    W: RevWalk<I>,    F: FnMut(&I, W::Item) -> Option<B>,{    type Item = B;     fn next(&mut self, index: &I) -> Option<Self::Item> {        while let Some(item) = self.walk.next(index) {            if let Some(new_item) = (self.f)(index, item) {                return Some(new_item);            }        }        None    }} #[derive(Clone, Debug)]#[must_use]pub(super) struct MapRevWalk<W, F> {    walk: W,    f: F,} impl<B, I, W, F> RevWalk<I> for MapRevWalk<W, F>where    I: ?Sized,    W: RevWalk<I>,    F: FnMut(&I, W::Item) -> B,{    type Item = B;     fn next(&mut self, index: &I) -> Option<Self::Item> {        self.walk.next(index).map(|item| (self.f)(index, item))    }} #[derive(Clone, Debug)]#[must_use]pub(super) struct PeekableRevWalk<I: ?Sized, W: RevWalk<I>> {    walk: W,    // Since RevWalk is fused, we don't need a nested Option<Option<_>>.    peeked: Option<W::Item>,} impl<I: ?Sized, W: RevWalk<I>> PeekableRevWalk<I, W> {    pub fn peek(&mut self, index: &I) -> Option<&W::Item> {        if self.peeked.is_none() {            self.peeked = self.walk.next(index);        }        self.peeked.as_ref()    }     pub fn next_if(        &mut self,        index: &I,        predicate: impl FnOnce(&W::Item) -> bool,    ) -> Option<W::Item> {        match self.next(index) {            Some(item) if predicate(&item) => Some(item),            other => {                assert!(self.peeked.is_none());                self.peeked = other;                None            }        }    }} impl<I: ?Sized, W: RevWalk<I>> RevWalk<I> for PeekableRevWalk<I, W> {    type Item = W::Item;     fn next(&mut self, index: &I) -> Option<Self::Item> {        self.peeked.take().or_else(|| self.walk.next(index))    }} /// Adapter that turns `RevWalk` into `Iterator` by attaching borrowed `index`.#[derive(Clone, Debug)]#[must_use]pub(super) struct RevWalkBorrowedIndexIter<'a, I: ?Sized, W> {    index: &'a I,    walk: W,} impl<I: ?Sized, W> RevWalkBorrowedIndexIter<'_, I, W> {    /// Turns into `'static`-lifetime walk object by detaching the index.    pub fn detach(self) -> W {        self.walk    }} impl<I: ?Sized, W: RevWalk<I>> Iterator for RevWalkBorrowedIndexIter<'_, I, W> {    type Item = W::Item;     fn next(&mut self) -> Option<Self::Item> {        self.walk.next(self.index)    }} impl<I: ?Sized, W: RevWalk<I>> FusedIterator for RevWalkBorrowedIndexIter<'_, I, W> {} /// Adapter that turns `RevWalk` into `Iterator` by attaching owned `index`.#[derive(Clone, Debug)]#[must_use]pub(super) struct RevWalkOwnedIndexIter<I, W> {    index: I,    walk: W,} impl<I, W: RevWalk<I>> Iterator for RevWalkOwnedIndexIter<I, W> {    type Item = W::Item;     fn next(&mut self) -> Option<Self::Item> {        self.walk.next(&self.index)    }} impl<I, W: RevWalk<I>> FusedIterator for RevWalkOwnedIndexIter<I, W> {} pub(super) trait RevWalkIndex {    type Position: Copy + Ord;    type AdjacentPositions: IntoIterator<Item = Self::Position> + AsRef<[Self::Position]>;     fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions;} impl RevWalkIndex for CompositeIndex {    type Position = GlobalCommitPosition;    type AdjacentPositions = SmallGlobalCommitPositionsVec;     fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions {        self.commits().entry_by_pos(pos).parent_positions()    }} #[derive(Clone)]pub(super) struct RevWalkDescendantsIndex {    children_map: HashMap<GlobalCommitPosition, DescendantIndexPositionsVec>,} // See SmallGlobalCommitPositionsVec for the array size.type DescendantIndexPositionsVec = SmallVec<[Reverse<GlobalCommitPosition>; 4]>; impl RevWalkDescendantsIndex {    fn build(        index: &CompositeCommitIndex,        positions: impl IntoIterator<Item = GlobalCommitPosition>,    ) -> Self {        // For dense set, it's probably cheaper to use `Vec` instead of `HashMap`.        let mut children_map: HashMap<GlobalCommitPosition, DescendantIndexPositionsVec> =            HashMap::new();        for pos in positions {            children_map.entry(pos).or_default(); // mark head node            for parent_pos in index.entry_by_pos(pos).parent_positions() {                let parent = children_map.entry(parent_pos).or_default();                parent.push(Reverse(pos));            }        }         Self { children_map }    }     fn contains_pos(&self, pos: GlobalCommitPosition) -> bool {        self.children_map.contains_key(&pos)    }} impl RevWalkIndex for RevWalkDescendantsIndex {    type Position = Reverse<GlobalCommitPosition>;    type AdjacentPositions = DescendantIndexPositionsVec;     fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions {        self.children_map[&pos.0].clone()    }} #[derive(Clone)]#[must_use]pub(super) struct RevWalkBuilder<'a> {    index: &'a CompositeIndex,    wanted: Vec<GlobalCommitPosition>,    unwanted: Vec<GlobalCommitPosition>,    wanted_parents_range: Range<u32>,} impl<'a> RevWalkBuilder<'a> {    pub fn new(index: &'a CompositeIndex) -> Self {        Self {            index,            wanted: Vec::new(),            unwanted: Vec::new(),            wanted_parents_range: PARENTS_RANGE_FULL,        }    }     /// Sets head positions to be included.    pub fn wanted_heads(mut self, positions: Vec<GlobalCommitPosition>) -> Self {        self.wanted = positions;        self    }     /// Sets range of parents to iterate over for wanted heads.    pub fn wanted_parents_range(mut self, wanted_parents_range: Range<u32>) -> Self {        assert!(wanted_parents_range.start <= wanted_parents_range.end);        self.wanted_parents_range = wanted_parents_range;        self    }     /// Sets root positions to be excluded. The roots precede the heads.    pub fn unwanted_roots(mut self, positions: Vec<GlobalCommitPosition>) -> Self {        self.unwanted = positions;        self    }     /// Walks ancestors.    pub fn ancestors(self) -> RevWalkAncestors<'a> {        self.ancestors_with_min_pos(GlobalCommitPosition::MIN)    }     fn ancestors_with_min_pos(self, min_pos: GlobalCommitPosition) -> RevWalkAncestors<'a> {        let index = self.index;        let wanted_parents_range = self.wanted_parents_range;        let mut wanted_queue = RevWalkQueue::with_min_pos(min_pos);        let mut unwanted_queue = RevWalkQueue::with_min_pos(min_pos);        wanted_queue.extend(self.wanted, ());        unwanted_queue.extend(self.unwanted, ());        RevWalkBorrowedIndexIter {            index,            walk: RevWalkImpl {                wanted_queue,                unwanted_queue,                wanted_parents_range,            },        }    }     /// Walks ancestors within the `generation_range`.    ///    /// A generation number counts from the heads.    pub fn ancestors_filtered_by_generation(        self,        generation_range: Range<u32>,    ) -> RevWalkAncestorsGenerationRange<'a> {        let index = self.index;        let wanted_parents_range = self.wanted_parents_range;        let mut wanted_queue = RevWalkQueue::with_min_pos(GlobalCommitPosition::MIN);        let mut unwanted_queue = RevWalkQueue::with_min_pos(GlobalCommitPosition::MIN);        let item_range = RevWalkItemGenerationRange::from_filter_range(generation_range.clone());        wanted_queue.extend(self.wanted, Reverse(item_range));        unwanted_queue.extend(self.unwanted, ());        RevWalkBorrowedIndexIter {            index,            walk: RevWalkGenerationRangeImpl {                wanted_queue,                unwanted_queue,                wanted_parents_range,                generation_end: generation_range.end,            },        }    }     /// Walks ancestors until all of the reachable roots in `root_positions` get    /// visited.    ///    /// Use this if you are only interested in descendants of the given roots.    /// The caller still needs to filter out unwanted entries.    pub fn ancestors_until_roots(        self,        root_positions: impl IntoIterator<Item = GlobalCommitPosition>,    ) -> RevWalkAncestors<'a> {        // We can also make it stop visiting based on the generation number. Maybe        // it will perform better for unbalanced branchy history.        // https://github.com/jj-vcs/jj/pull/1492#discussion_r1160678325        let min_pos = root_positions            .into_iter()            .min()            .unwrap_or(GlobalCommitPosition::MAX);        self.ancestors_with_min_pos(min_pos)    }     /// Fully consumes ancestors and walks back from the `root_positions`.    ///    /// The returned iterator yields entries in order of ascending index    /// position.    pub fn descendants(        self,        root_positions: HashSet<GlobalCommitPosition>,    ) -> RevWalkDescendants<'a> {        let index = self.index;        let candidate_positions = self            .ancestors_until_roots(root_positions.iter().copied())            .collect();        RevWalkBorrowedIndexIter {            index,            walk: RevWalkDescendantsImpl {                candidate_positions,                root_positions,                reachable_positions: HashSet::new(),            },        }    }     /// Fully consumes ancestors and walks back from the `root_positions` within    /// the `generation_range`.    ///    /// A generation number counts from the roots.    ///    /// The returned iterator yields entries in order of ascending index    /// position.    pub fn descendants_filtered_by_generation(        self,        root_positions: Vec<GlobalCommitPosition>,        generation_range: Range<u32>,    ) -> RevWalkDescendantsGenerationRange {        let index = self.index;        let positions = self.ancestors_until_roots(root_positions.iter().copied());        let descendants_index = RevWalkDescendantsIndex::build(index.commits(), positions);         let mut wanted_queue = RevWalkQueue::with_min_pos(Reverse(GlobalCommitPosition::MAX));        let unwanted_queue = RevWalkQueue::with_min_pos(Reverse(GlobalCommitPosition::MAX));        let item_range = RevWalkItemGenerationRange::from_filter_range(generation_range.clone());        for pos in root_positions {            // Do not add unreachable roots which shouldn't be visited            if descendants_index.contains_pos(pos) {                wanted_queue.push(Reverse(pos), Reverse(item_range));            }        }        RevWalkOwnedIndexIter {            index: descendants_index,            walk: RevWalkGenerationRangeImpl {                wanted_queue,                unwanted_queue,                // Since we're using the descendants index, this actually is a range for the                // children instead of the parents.                wanted_parents_range: PARENTS_RANGE_FULL,                generation_end: generation_range.end,            },        }    }} pub(super) type RevWalkAncestors<'a> =    RevWalkBorrowedIndexIter<'a, CompositeIndex, RevWalkImpl<GlobalCommitPosition>>; #[derive(Clone)]#[must_use]pub(super) struct RevWalkImpl<P> {    wanted_queue: RevWalkQueue<P, ()>,    unwanted_queue: RevWalkQueue<P, ()>,    wanted_parents_range: Range<u32>,} impl<I: RevWalkIndex + ?Sized> RevWalk<I> for RevWalkImpl<I::Position> {    type Item = I::Position;     fn next(&mut self, index: &I) -> Option<Self::Item> {        while let Some(item) = self.wanted_queue.pop() {            self.wanted_queue.skip_while_eq(&item.pos);            if flush_queue_until(&mut self.unwanted_queue, index, item.pos).is_some() {                continue;            }            let parents = index.adjacent_positions(item.pos);            self.wanted_queue.extend(                filter_slice_by_range(parents.as_ref(), &self.wanted_parents_range)                    .iter()                    .copied(),                (),            );            return Some(item.pos);        }        None    }} pub(super) type RevWalkAncestorsGenerationRange<'a> =

Lines 1–500 of 1162. Load more