| SimonSapin | |
| Alphare |
| hg-reviewers |
… Which has been moved to the vcsgraph crate.
AncestorsIterator cannot yet be removed because it is still being used in
hg-core.
| No Linters Available |
| No Unit Test Coverage |
| Path | Packages | |||
|---|---|---|---|---|
| M | rust/hg-core/src/ancestors.rs (85 lines) | |||
| M | rust/hg-core/src/lib.rs (2 lines) |
| Commit | Parents | Author | Summary | Date |
|---|---|---|---|---|
| 430e9a6a63a3 | 639aa1919886 | pacien | Dec 10 2021, 10:25 AM |
| /// bindings evolve over time | /// bindings evolve over time | ||||
| pub struct AncestorsIterator<G: Graph> { | pub struct AncestorsIterator<G: Graph> { | ||||
| graph: G, | graph: G, | ||||
| visit: BinaryHeap<Revision>, | visit: BinaryHeap<Revision>, | ||||
| seen: HashSet<Revision>, | seen: HashSet<Revision>, | ||||
| stoprev: Revision, | stoprev: Revision, | ||||
| } | } | ||||
| /// Lazy ancestors set, backed by AncestorsIterator | |||||
| pub struct LazyAncestors<G: Graph + Clone> { | |||||
| graph: G, | |||||
| containsiter: AncestorsIterator<G>, | |||||
| initrevs: Vec<Revision>, | |||||
| stoprev: Revision, | |||||
| inclusive: bool, | |||||
| } | |||||
| pub struct MissingAncestors<G: Graph> { | pub struct MissingAncestors<G: Graph> { | ||||
| graph: G, | graph: G, | ||||
| bases: HashSet<Revision>, | bases: HashSet<Revision>, | ||||
| max_base: Revision, | max_base: Revision, | ||||
| } | } | ||||
| impl<G: Graph> AncestorsIterator<G> { | impl<G: Graph> AncestorsIterator<G> { | ||||
| /// Constructor. | /// Constructor. | ||||
| *(self.visit.peek_mut().unwrap()) = p1; | *(self.visit.peek_mut().unwrap()) = p1; | ||||
| }; | }; | ||||
| self.conditionally_push_rev(p2); | self.conditionally_push_rev(p2); | ||||
| Some(Ok(current)) | Some(Ok(current)) | ||||
| } | } | ||||
| } | } | ||||
| impl<G: Graph + Clone> LazyAncestors<G> { | |||||
| pub fn new( | |||||
| graph: G, | |||||
| initrevs: impl IntoIterator<Item = Revision>, | |||||
| stoprev: Revision, | |||||
| inclusive: bool, | |||||
| ) -> Result<Self, GraphError> { | |||||
| let v: Vec<Revision> = initrevs.into_iter().collect(); | |||||
| Ok(LazyAncestors { | |||||
| graph: graph.clone(), | |||||
| containsiter: AncestorsIterator::new( | |||||
| graph, | |||||
| v.iter().cloned(), | |||||
| stoprev, | |||||
| inclusive, | |||||
| )?, | |||||
| initrevs: v, | |||||
| stoprev, | |||||
| inclusive, | |||||
| }) | |||||
| } | |||||
| pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> { | |||||
| self.containsiter.contains(rev) | |||||
| } | |||||
| pub fn is_empty(&self) -> bool { | |||||
| self.containsiter.is_empty() | |||||
| } | |||||
| pub fn iter(&self) -> AncestorsIterator<G> { | |||||
| // the arguments being the same as for self.containsiter, we know | |||||
| // for sure that AncestorsIterator constructor can't fail | |||||
| AncestorsIterator::new( | |||||
| self.graph.clone(), | |||||
| self.initrevs.iter().cloned(), | |||||
| self.stoprev, | |||||
| self.inclusive, | |||||
| ) | |||||
| .unwrap() | |||||
| } | |||||
| } | |||||
| impl<G: Graph> MissingAncestors<G> { | impl<G: Graph> MissingAncestors<G> { | ||||
| pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { | pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { | ||||
| let mut created = MissingAncestors { | let mut created = MissingAncestors { | ||||
| graph, | graph, | ||||
| bases: HashSet::new(), | bases: HashSet::new(), | ||||
| max_base: NULL_REVISION, | max_base: NULL_REVISION, | ||||
| }; | }; | ||||
| created.add_bases(bases); | created.add_bases(bases); | ||||
| fn test_next_out_of_range() { | fn test_next_out_of_range() { | ||||
| // inclusive=false looks up initrev's parents right away | // inclusive=false looks up initrev's parents right away | ||||
| let mut iter = | let mut iter = | ||||
| AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); | AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); | ||||
| assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); | assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); | ||||
| } | } | ||||
| #[test] | #[test] | ||||
| fn test_lazy_iter_contains() { | |||||
| let mut lazy = | |||||
| LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); | |||||
| let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); | |||||
| // compare with iterator tests on the same initial revisions | |||||
| assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); | |||||
| // contains() results are correct, unaffected by the fact that | |||||
| // we consumed entirely an iterator out of lazy | |||||
| assert_eq!(lazy.contains(2), Ok(true)); | |||||
| assert_eq!(lazy.contains(9), Ok(false)); | |||||
| } | |||||
| #[test] | |||||
| fn test_lazy_contains_iter() { | |||||
| let mut lazy = | |||||
| LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0] | |||||
| assert_eq!(lazy.contains(2), Ok(true)); | |||||
| assert_eq!(lazy.contains(6), Ok(false)); | |||||
| // after consumption of 2 by the inner iterator, results stay | |||||
| // consistent | |||||
| assert_eq!(lazy.contains(2), Ok(true)); | |||||
| assert_eq!(lazy.contains(5), Ok(false)); | |||||
| // iter() still gives us a fresh iterator | |||||
| let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); | |||||
| assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); | |||||
| } | |||||
| #[test] | |||||
| /// Test constructor, add/get bases and heads | /// Test constructor, add/get bases and heads | ||||
| fn test_missing_bases() -> Result<(), GraphError> { | fn test_missing_bases() -> Result<(), GraphError> { | ||||
| let mut missing_ancestors = | let mut missing_ancestors = | ||||
| MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); | MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); | ||||
| let mut as_vec: Vec<Revision> = | let mut as_vec: Vec<Revision> = | ||||
| missing_ancestors.get_bases().iter().cloned().collect(); | missing_ancestors.get_bases().iter().cloned().collect(); | ||||
| as_vec.sort(); | as_vec.sort(); | ||||
| assert_eq!(as_vec, [1, 3, 5]); | assert_eq!(as_vec, [1, 3, 5]); | ||||
| // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> | ||||
| // and Mercurial contributors | // and Mercurial contributors | ||||
| // | // | ||||
| // This software may be used and distributed according to the terms of the | // This software may be used and distributed according to the terms of the | ||||
| // GNU General Public License version 2 or any later version. | // GNU General Public License version 2 or any later version. | ||||
| mod ancestors; | mod ancestors; | ||||
| pub mod dagops; | pub mod dagops; | ||||
| pub mod errors; | pub mod errors; | ||||
| pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; | pub use ancestors::{AncestorsIterator, MissingAncestors}; | ||||
| pub mod dirstate; | pub mod dirstate; | ||||
| pub mod dirstate_tree; | pub mod dirstate_tree; | ||||
| pub mod discovery; | pub mod discovery; | ||||
| pub mod exit_codes; | pub mod exit_codes; | ||||
| pub mod requirements; | pub mod requirements; | ||||
| pub mod testing; // unconditionally built, for use from integration tests | pub mod testing; // unconditionally built, for use from integration tests | ||||
| pub use dirstate::{ | pub use dirstate::{ | ||||
| dirs_multiset::{DirsMultiset, DirsMultisetIter}, | dirs_multiset::{DirsMultiset, DirsMultisetIter}, | ||||