Patchwork D6230: rust-dagops: roots

login
register
mail settings
Submitter phabricator
Date April 18, 2019, 11:26 p.m.
Message ID <006523f983648445c01f20f4aa113efd@localhost.localdomain>
Download mbox | patch
Permalink /patch/39751/
State Not Applicable
Headers show

Comments

phabricator - April 18, 2019, 11:26 p.m.
This revision was automatically updated to reflect the committed changes.
Closed by commit rHGbe0733552984: rust-dagops: roots (authored by gracinet, committed by ).

REPOSITORY
  rHG Mercurial

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

REVISION DETAIL
  https://phab.mercurial-scm.org/D6230

AFFECTED FILES
  rust/hg-core/src/dagops.rs

CHANGE DETAILS




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

Patch

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,