Mercurial > hg
diff rust/hg-core/src/dagops.rs @ 42177:be0733552984
rust-dagops: roots
Unsuprisingly, the algorithm is much easier than for heads, provided
we work on a set in the first place.
To improve the signature, a trait for set-likes object would be useful,
but that's not an immediate concern.
Differential Revision: https://phab.mercurial-scm.org/D6230
author | Georges Racinet <georges.racinet@octobus.net> |
---|---|
date | Wed, 20 Feb 2019 18:33:53 +0100 |
parents | 3bdb21bbf791 |
children | ce6797ef6eab |
line wrap: on
line diff
--- a/rust/hg-core/src/dagops.rs Tue Feb 19 23:41:57 2019 +0100 +++ b/rust/hg-core/src/dagops.rs Wed Feb 20 18:33:53 2019 +0100 @@ -81,6 +81,27 @@ Ok(()) } +/// Roots of `revs`, passed as a `HashSet` +/// +/// They are returned in arbitrary order +pub fn roots<G: Graph>( + graph: &G, + revs: &HashSet<Revision>, +) -> Result<Vec<Revision>, GraphError> { + let mut roots: Vec<Revision> = Vec::new(); + for rev in revs { + if graph + .parents(*rev)? + .iter() + .filter(|p| **p != NULL_REVISION) + .all(|p| !revs.contains(p)) + { + roots.push(*rev); + } + } + Ok(roots) +} + /// Compute the topological range between two collections of revisions /// /// This is equivalent to the revset `<roots>::<heads>`. @@ -203,6 +224,30 @@ Ok(()) } + /// Apply `roots()` and sort the result for easier comparison + fn roots_sorted( + graph: &impl Graph, + revs: &[Revision], + ) -> Result<Vec<Revision>, GraphError> { + let mut as_vec = roots(graph, &revs.iter().cloned().collect())?; + as_vec.sort(); + Ok(as_vec) + } + + #[test] + fn test_roots() -> Result<(), GraphError> { + assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]); + assert_eq!( + roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, + vec![0, 4, 12] + ); + assert_eq!( + roots_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?, + vec![1, 8] + ); + Ok(()) + } + /// Apply `range()` and convert the result into a Vec for easier comparison fn range_vec( graph: impl Graph + Clone,