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 Superseded
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
phabricator - Jan. 27, 2020, 3:54 p.m.
gracinet added inline comments.
gracinet marked 2 inline comments as done.

INLINE COMMENTS

> martinvonz wrote in nodemap.rs:264-269
> 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`.

I understand your concern, but `<Option<Option<Revision>>` would defeat the purpose of not having a dead match arm to fill with a "can't happen" comment in the future `insert()`.

Fortunately, @kevincox suggestion of having `NodeTreeVisitor` emit  a `struct` provides us with the best of both worlds, since it can have methods.

It should be fully transparent performance-wise, I just hope that is really true.

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
phabricator - Jan. 27, 2020, 7 p.m.
martinvonz added inline comments.
martinvonz accepted this revision.

INLINE COMMENTS

> nodemap.rs:300
> +    prefix: NodePrefixRef<'p>,
> +    visit: usize,
> +    nybble_idx: usize,

would something like `block_index` be clearer?

> nodemap.rs:312
> +
> +impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
> +    type Item = NodeTreeVisitItem;

can these lifetimes be anonymous?

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, martinvonz
Cc: martinvonz, durin42, kevincox, mercurial-devel
phabricator - Jan. 27, 2020, 7:09 p.m.
gracinet added inline comments.
gracinet marked 2 inline comments as done.

INLINE COMMENTS

> martinvonz wrote in nodemap.rs:300
> would something like `block_index` be clearer?

I found it to be clearer for the emitter, but in the iterator implementation, it expresses what's to be done next, same as in many cases I've seeen in Mercurial

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