Patchwork D6230: rust-dagops: roots

login
register
mail settings
Submitter phabricator
Date April 12, 2019, 6:33 p.m.
Message ID <differential-rev-PHID-DREV-22bog3uhhflxebhowm5b-req@phab.mercurial-scm.org>
Download mbox | patch
Permalink /patch/39575/
State Superseded
Headers show

Comments

phabricator - April 12, 2019, 6:33 p.m.
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




To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
phabricator - April 14, 2019, 7:51 p.m.
kevincox accepted this revision.
kevincox added inline comments.

INLINE COMMENTS

> dagops.rs:96
> +            .iter()
> +            .all(|p| *p == NULL_REVISION || !revs.contains(p))
> +        {

I think it is more clear to write `.iter().filter(|p| *p != NULL_REVISION).all(|p| !revs.contains(p))`. This separates the NULLs from the revs you care about and makes that condition easier to parse.

REPOSITORY
  rHG Mercurial

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

To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel
phabricator - April 15, 2019, 10:11 a.m.
gracinet added inline comments.

INLINE COMMENTS

> kevincox wrote in dagops.rs:96
> I think it is more clear to write `.iter().filter(|p| *p != NULL_REVISION).all(|p| !revs.contains(p))`. This separates the NULLs from the revs you care about and makes that condition easier to parse.

Thanks for the suggestion.

Anticipating on a discussion to have later, I'd like eventually the `Graph::parents()` returns an iterator. The advantages will be made obvious by the (not submitted yet) final changesets of the` PartialDiscovery`  implementation in `hg-core`.  In other words, `NULL_REVISION` and the fact to have exactly two parents should be considered implementation details of the underlying storage.

REPOSITORY
  rHG Mercurial

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

To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel
phabricator - April 15, 2019, 10:23 a.m.
kevincox added inline comments.

INLINE COMMENTS

> gracinet wrote in dagops.rs:96
> Thanks for the suggestion.
> 
> Anticipating on a discussion to have later, I'd like eventually the `Graph::parents()` returns an iterator. The advantages will be made obvious by the (not submitted yet) final changesets of the` PartialDiscovery`  implementation in `hg-core`.  In other words, `NULL_REVISION` and the fact to have exactly two parents should be considered implementation details of the underlying storage.

That sounds great. `NULL_REVISION` always seemed quite messy to me. It would definitely be best to filter it out as soon as possible.

REPOSITORY
  rHG Mercurial

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

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