Patchwork D7794: rust-nodemap: generic NodeTreeVisitor

login
register
mail settings
Submitter phabricator
Date Jan. 6, 2020, 7:26 p.m.
Message ID <differential-rev-PHID-DREV-mjlbzz7yqykeapqseku7-req@mercurial-scm.org>
Download mbox | patch
Permalink /patch/44153/
State New
Headers show

Comments

phabricator - Jan. 6, 2020, 7:26 p.m.
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  This iterator will help avoid code duplication when we'll
  implement `insert()`, in which we will need to
  traverse the node tree, and to remember the visited blocks.
  
  The iterator converts the three variants of `Element` into the
  boolean `leaf` and `Option<Revision>` instead of just emitting the
  variant it's seen. The motivation is to avoid a dead match arm
  in the future `insert()`.

REPOSITORY
  rHG Mercurial

BRANCH
  default

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

AFFECTED FILES
  rust/hg-core/src/revlog/nodemap.rs

CHANGE DETAILS




To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
phabricator - Jan. 16, 2020, 10:16 a.m.
This revision now requires changes to proceed.
kevincox added inline comments.
kevincox requested changes to this revision.

INLINE COMMENTS

> nodemap.rs:254
> +impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
> +    type Item = (bool, usize, u8, Option<Revision>);
> +

I would prefer making this a struct so that you can name the fields. You can still pattern match the fields if you want to.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST ACTION
  https://phab.mercurial-scm.org/D7794/new/

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

To: gracinet, #hg-reviewers, kevincox
Cc: durin42, kevincox, mercurial-devel
phabricator - Jan. 22, 2020, 7:18 p.m.
martinvonz added inline comments.

INLINE COMMENTS

> nodemap.rs:264-269
> +            Element::None => (true, None),
> +            Element::Rev(r) => (true, Some(r)),
> +            Element::Block(idx) => {
> +                self.visit = idx;
> +                (false, None)
> +            }

There will only be a valid result if this is a leaf, so it might be better to combine `leaf` and `opt` into one `Option<Option<Revision>>` so the caller cannot mistake a `opt=None` for "missing" when `leaf=false`.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST ACTION
  https://phab.mercurial-scm.org/D7794/new/

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

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

Patch

diff --git a/rust/hg-core/src/revlog/nodemap.rs b/rust/hg-core/src/revlog/nodemap.rs
--- a/rust/hg-core/src/revlog/nodemap.rs
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -222,17 +222,58 @@ 
         &self,
         prefix: NodePrefixRef<'p>,
     ) -> Result<Option<Revision>, NodeMapError> {
-        let mut visit = self.len() - 1;
-        for i in 0..prefix.len() {
-            let nybble = prefix.get_nybble(i);
-            match self[visit].read(nybble) {
-                Element::None => return Ok(None),
-                Element::Rev(r) => return Ok(Some(r)),
-                Element::Block(idx) => visit = idx,
+        for (leaf, _, _, opt) in self.visit(prefix) {
+            if leaf {
+                return Ok(opt);
             }
         }
         Err(NodeMapError::MultipleResults)
     }
+
+    fn visit<'n, 'p>(
+        &'n self,
+        prefix: NodePrefixRef<'p>,
+    ) -> NodeTreeVisitor<'n, 'p> {
+        NodeTreeVisitor {
+            nt: self,
+            prefix: prefix,
+            visit: self.len() - 1,
+            nybble_idx: 0,
+            done: false,
+        }
+    }
+}
+
+struct NodeTreeVisitor<'n, 'p> {
+    nt: &'n NodeTree,
+    prefix: NodePrefixRef<'p>,
+    visit: usize,
+    nybble_idx: usize,
+    done: bool,
+}
+
+impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
+    type Item = (bool, usize, u8, Option<Revision>);
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.done || self.nybble_idx >= self.prefix.len() {
+            return None;
+        }
+
+        let nybble = self.prefix.get_nybble(self.nybble_idx);
+        let visit = self.visit;
+        let (leaf, opt) = match self.nt[visit].read(nybble) {
+            Element::None => (true, None),
+            Element::Rev(r) => (true, Some(r)),
+            Element::Block(idx) => {
+                self.visit = idx;
+                (false, None)
+            }
+        };
+        self.nybble_idx += 1;
+        self.done = leaf;
+        Some((leaf, visit, nybble, opt))
+    }
 }
 
 impl From<Vec<Block>> for NodeTree {