D6230: rust-dagops: roots

gracinet (Georges Racinet) phabricator at mercurial-scm.org
Mon Apr 15 06:10:58 EDT 2019


gracinet updated this revision to Diff 14741.
gracinet marked an inline comment as done.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D6230?vs=14719&id=14741

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,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,



To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel


More information about the Mercurial-devel mailing list