gracinet created this revision. Herald added subscribers: mercurial-devel, kevincox, durin42. Herald added a reviewer: hg-reviewers.
REVISION SUMMARY 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. REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D6230 AFFECTED FILES rust/hg-core/src/dagops.rs CHANGE DETAILS diff --git a/rust/hg-core/src/dagops.rs b/rust/hg-core/src/dagops.rs --- a/rust/hg-core/src/dagops.rs +++ b/rust/hg-core/src/dagops.rs @@ -81,6 +81,26 @@ 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() + .all(|p| *p == NULL_REVISION || !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>`. @@ -205,6 +225,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, To: gracinet, #hg-reviewers Cc: durin42, kevincox, mercurial-devel _______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel