// 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::max;use std::cmp::Reverse;use std::collections::BinaryHeap;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::CompositeIndex;use super::entry::IndexPosition;use super::entry::SmallIndexPositionsVec; /// 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 { EagerRevWalk { 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>; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions;} impl RevWalkIndex for CompositeIndex { type Position = IndexPosition; type AdjacentPositions = SmallIndexPositionsVec; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions { self.entry_by_pos(pos).parent_positions() }} #[derive(Clone)]pub(super) struct RevWalkDescendantsIndex { children_map: HashMap<IndexPosition, DescendantIndexPositionsVec>,} // See SmallIndexPositionsVec for the array size.type DescendantIndexPositionsVec = SmallVec<[Reverse<IndexPosition>; 4]>; impl RevWalkDescendantsIndex { fn build(index: &CompositeIndex, positions: impl IntoIterator<Item = IndexPosition>) -> Self { // For dense set, it's probably cheaper to use `Vec` instead of `HashMap`. let mut children_map: HashMap<IndexPosition, 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)); } } RevWalkDescendantsIndex { children_map } } fn contains_pos(&self, pos: IndexPosition) -> bool { self.children_map.contains_key(&pos) }} impl RevWalkIndex for RevWalkDescendantsIndex { type Position = Reverse<IndexPosition>; type AdjacentPositions = DescendantIndexPositionsVec; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions { self.children_map[&pos.0].clone() }} #[derive(Clone, Eq, PartialEq, Ord, PartialOrd)]struct RevWalkWorkItem<P, T> { pos: P, state: RevWalkWorkItemState<T>,} #[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]enum RevWalkWorkItemState<T> { // Order matters: Unwanted should appear earlier in the max-heap. Wanted(T), Unwanted,} impl<P, T> RevWalkWorkItem<P, T> { fn is_wanted(&self) -> bool { matches!(self.state, RevWalkWorkItemState::Wanted(_)) }} #[derive(Clone)]struct RevWalkQueue<P, T> { items: BinaryHeap<RevWalkWorkItem<P, T>>, min_pos: P, unwanted_count: usize,} impl<P: Ord, T: Ord> RevWalkQueue<P, T> { fn with_min_pos(min_pos: P) -> Self { Self { items: BinaryHeap::new(), min_pos, unwanted_count: 0, } } fn push_wanted(&mut self, pos: P, t: T) { if pos < self.min_pos { return; } let state = RevWalkWorkItemState::Wanted(t); self.items.push(RevWalkWorkItem { pos, state }); } fn push_unwanted(&mut self, pos: P) { if pos < self.min_pos { return; } let state = RevWalkWorkItemState::Unwanted; self.items.push(RevWalkWorkItem { pos, state }); self.unwanted_count += 1; } fn extend_wanted(&mut self, positions: impl IntoIterator<Item = P>, t: T) where T: Clone, { // positions typically contains one item, and single BinaryHeap::push() // appears to be slightly faster than .extend() as of rustc 1.73.0. for pos in positions { self.push_wanted(pos, t.clone()); } } fn extend_unwanted(&mut self, positions: impl IntoIterator<Item = P>) { for pos in positions { self.push_unwanted(pos); } } fn pop(&mut self) -> Option<RevWalkWorkItem<P, T>> { if let Some(x) = self.items.pop() { self.unwanted_count -= !x.is_wanted() as usize; Some(x) } else { None } } fn pop_eq(&mut self, pos: &P) -> Option<RevWalkWorkItem<P, T>> { if let Some(x) = self.items.peek() { (x.pos == *pos).then(|| self.pop().unwrap()) } else { None } } fn skip_while_eq(&mut self, pos: &P) { while self.pop_eq(pos).is_some() { continue; } }} #[derive(Clone)]#[must_use]pub(super) struct RevWalkBuilder<'a> { index: &'a CompositeIndex, wanted: Vec<IndexPosition>, unwanted: Vec<IndexPosition>,} impl<'a> RevWalkBuilder<'a> { pub fn new(index: &'a CompositeIndex) -> Self { RevWalkBuilder { index, wanted: Vec::new(), unwanted: Vec::new(), } } /// Sets head positions to be included. pub fn wanted_heads(mut self, positions: Vec<IndexPosition>) -> Self { self.wanted = positions; self } /// Sets root positions to be excluded. The roots precede the heads. pub fn unwanted_roots(mut self, positions: Vec<IndexPosition>) -> Self { self.unwanted = positions; self } /// Walks ancestors. pub fn ancestors(self) -> RevWalkAncestors<'a> { self.ancestors_with_min_pos(IndexPosition::MIN) } fn ancestors_with_min_pos(self, min_pos: IndexPosition) -> RevWalkAncestors<'a> { let index = self.index; let mut queue = RevWalkQueue::with_min_pos(min_pos); queue.extend_wanted(self.wanted, ()); queue.extend_unwanted(self.unwanted); RevWalkBorrowedIndexIter { index, walk: RevWalkImpl { queue }, } } /// 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 mut queue = RevWalkQueue::with_min_pos(IndexPosition::MIN); let item_range = RevWalkItemGenerationRange::from_filter_range(generation_range.clone()); queue.extend_wanted(self.wanted, Reverse(item_range)); queue.extend_unwanted(self.unwanted); RevWalkBorrowedIndexIter { index, walk: RevWalkGenerationRangeImpl { queue, 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 = IndexPosition>, ) -> 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(IndexPosition::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<IndexPosition>) -> 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.Lines 1–500 of 1396. Load more
// 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::max; use std::cmp::Reverse; use std::collections::BinaryHeap; 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::CompositeIndex; use super::entry::IndexPosition; use super::entry::SmallIndexPositionsVec; /// 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 { EagerRevWalk { 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>; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions; } impl RevWalkIndex for CompositeIndex { type Position = IndexPosition; type AdjacentPositions = SmallIndexPositionsVec; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions { self.entry_by_pos(pos).parent_positions() } } #[derive(Clone)] pub(super) struct RevWalkDescendantsIndex { children_map: HashMap<IndexPosition, DescendantIndexPositionsVec>, } // See SmallIndexPositionsVec for the array size. type DescendantIndexPositionsVec = SmallVec<[Reverse<IndexPosition>; 4]>; impl RevWalkDescendantsIndex { fn build(index: &CompositeIndex, positions: impl IntoIterator<Item = IndexPosition>) -> Self { // For dense set, it's probably cheaper to use `Vec` instead of `HashMap`. let mut children_map: HashMap<IndexPosition, 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)); } } RevWalkDescendantsIndex { children_map } } fn contains_pos(&self, pos: IndexPosition) -> bool { self.children_map.contains_key(&pos) } } impl RevWalkIndex for RevWalkDescendantsIndex { type Position = Reverse<IndexPosition>; type AdjacentPositions = DescendantIndexPositionsVec; fn adjacent_positions(&self, pos: Self::Position) -> Self::AdjacentPositions { self.children_map[&pos.0].clone() } } #[derive(Clone, Eq, PartialEq, Ord, PartialOrd)] struct RevWalkWorkItem<P, T> { pos: P, state: RevWalkWorkItemState<T>, } #[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)] enum RevWalkWorkItemState<T> { // Order matters: Unwanted should appear earlier in the max-heap. Wanted(T), Unwanted, } impl<P, T> RevWalkWorkItem<P, T> { fn is_wanted(&self) -> bool { matches!(self.state, RevWalkWorkItemState::Wanted(_)) } } #[derive(Clone)] struct RevWalkQueue<P, T> { items: BinaryHeap<RevWalkWorkItem<P, T>>, min_pos: P, unwanted_count: usize, } impl<P: Ord, T: Ord> RevWalkQueue<P, T> { fn with_min_pos(min_pos: P) -> Self { Self { items: BinaryHeap::new(), min_pos, unwanted_count: 0, } } fn push_wanted(&mut self, pos: P, t: T) { if pos < self.min_pos { return; } let state = RevWalkWorkItemState::Wanted(t); self.items.push(RevWalkWorkItem { pos, state }); } fn push_unwanted(&mut self, pos: P) { if pos < self.min_pos { return; } let state = RevWalkWorkItemState::Unwanted; self.items.push(RevWalkWorkItem { pos, state }); self.unwanted_count += 1; } fn extend_wanted(&mut self, positions: impl IntoIterator<Item = P>, t: T) where T: Clone, { // positions typically contains one item, and single BinaryHeap::push() // appears to be slightly faster than .extend() as of rustc 1.73.0. for pos in positions { self.push_wanted(pos, t.clone()); } } fn extend_unwanted(&mut self, positions: impl IntoIterator<Item = P>) { for pos in positions { self.push_unwanted(pos); } } fn pop(&mut self) -> Option<RevWalkWorkItem<P, T>> { if let Some(x) = self.items.pop() { self.unwanted_count -= !x.is_wanted() as usize; Some(x) } else { None } } fn pop_eq(&mut self, pos: &P) -> Option<RevWalkWorkItem<P, T>> { if let Some(x) = self.items.peek() { (x.pos == *pos).then(|| self.pop().unwrap()) } else { None } } fn skip_while_eq(&mut self, pos: &P) { while self.pop_eq(pos).is_some() { continue; } } } #[derive(Clone)] #[must_use] pub(super) struct RevWalkBuilder<'a> { index: &'a CompositeIndex, wanted: Vec<IndexPosition>, unwanted: Vec<IndexPosition>, } impl<'a> RevWalkBuilder<'a> { pub fn new(index: &'a CompositeIndex) -> Self { RevWalkBuilder { index, wanted: Vec::new(), unwanted: Vec::new(), } } /// Sets head positions to be included. pub fn wanted_heads(mut self, positions: Vec<IndexPosition>) -> Self { self.wanted = positions; self } /// Sets root positions to be excluded. The roots precede the heads. pub fn unwanted_roots(mut self, positions: Vec<IndexPosition>) -> Self { self.unwanted = positions; self } /// Walks ancestors. pub fn ancestors(self) -> RevWalkAncestors<'a> { self.ancestors_with_min_pos(IndexPosition::MIN) } fn ancestors_with_min_pos(self, min_pos: IndexPosition) -> RevWalkAncestors<'a> { let index = self.index; let mut queue = RevWalkQueue::with_min_pos(min_pos); queue.extend_wanted(self.wanted, ()); queue.extend_unwanted(self.unwanted); RevWalkBorrowedIndexIter { index, walk: RevWalkImpl { queue }, } } /// 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 mut queue = RevWalkQueue::with_min_pos(IndexPosition::MIN); let item_range = RevWalkItemGenerationRange::from_filter_range(generation_range.clone()); queue.extend_wanted(self.wanted, Reverse(item_range)); queue.extend_unwanted(self.unwanted); RevWalkBorrowedIndexIter { index, walk: RevWalkGenerationRangeImpl { queue, 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 = IndexPosition>, ) -> 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(IndexPosition::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<IndexPosition>) -> 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.