D7794: rust-nodemap: generic NodeTreeVisitor
Closed by commit rHG796d05f3fa84: rust-nodemap: generic NodeTreeVisitor
(authored by gracinet).
gracinet marked an inline comment as done.
This revision was automatically updated to reflect the committed changes.
This revision was not accepted when it landed; it landed in state "Needs
Review".
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7794?vs=19634&id=19647
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7794/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7794
AFFECTED FILES
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
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
@@ -272,17 +272,82 @@
&self,
prefix: NodePrefixRef<'p>,
) -> Result, NodeMapError> {
-let mut visit = self.len() - 1;
-for i in 0..prefix.len() {
-let nybble = prefix.get_nybble(i);
-match self[visit].get(nybble) {
-Element::None => return Ok(None),
-Element::Rev(r) => return Ok(Some(r)),
-Element::Block(idx) => visit = idx,
+for visit_item in self.visit(prefix) {
+if let Some(opt) = visit_item.final_revision() {
+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,
+}
+
+#[derive(Debug, PartialEq, Clone)]
+struct NodeTreeVisitItem {
+block_idx: usize,
+nybble: u8,
+element: Element,
+}
+
+impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
+type Item = NodeTreeVisitItem;
+
+fn next(&mut self) -> Option {
+if self.done || self.nybble_idx >= self.prefix.len() {
+return None;
+}
+
+let nybble = self.prefix.get_nybble(self.nybble_idx);
+self.nybble_idx += 1;
+
+let visit = self.visit;
+let element = self.nt[visit].get(nybble);
+if let Element::Block(idx) = element {
+self.visit = idx;
+} else {
+self.done = true;
+}
+
+Some(NodeTreeVisitItem {
+block_idx: visit,
+nybble: nybble,
+element: element,
+})
+}
+}
+
+impl NodeTreeVisitItem {
+// Return `Some(opt)` if this item is final, with `opt` being the
+// `Revision` that it may represent.
+//
+// If the item is not terminal, return `None`
+fn final_revision(&self) -> Option> {
+match self.element {
+Element::Block(_) => None,
+Element::Rev(r) => Some(Some(r)),
+Element::None => Some(None),
+}
+}
}
impl From> for NodeTree {
To: gracinet, #hg-reviewers, kevincox, martinvonz
Cc: martinvonz, durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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 ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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>` so the caller > cannot mistake a `opt=None` for "missing" when `leaf=false`. I understand your concern, but `>` 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 ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
gracinet edited the summary of this revision.
gracinet updated this revision to Diff 19634.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7794?vs=19327&id=19634
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7794/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7794
AFFECTED FILES
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
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
@@ -272,17 +272,82 @@
&self,
prefix: NodePrefixRef<'p>,
) -> Result, NodeMapError> {
-let mut visit = self.len() - 1;
-for i in 0..prefix.len() {
-let nybble = prefix.get_nybble(i);
-match self[visit].get(nybble) {
-Element::None => return Ok(None),
-Element::Rev(r) => return Ok(Some(r)),
-Element::Block(idx) => visit = idx,
+for visit_item in self.visit(prefix) {
+if let Some(opt) = visit_item.final_revision() {
+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,
+}
+
+#[derive(Debug, PartialEq, Clone)]
+struct NodeTreeVisitItem {
+block_idx: usize,
+nybble: u8,
+element: Element,
+}
+
+impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
+type Item = NodeTreeVisitItem;
+
+fn next(&mut self) -> Option {
+if self.done || self.nybble_idx >= self.prefix.len() {
+return None;
+}
+
+let nybble = self.prefix.get_nybble(self.nybble_idx);
+self.nybble_idx += 1;
+
+let visit = self.visit;
+let element = self.nt[visit].get(nybble);
+if let Element::Block(idx) = element {
+self.visit = idx;
+} else {
+self.done = true;
+}
+
+Some(NodeTreeVisitItem {
+block_idx: visit,
+nybble: nybble,
+element: element,
+})
+}
+}
+
+impl NodeTreeVisitItem {
+// Return `Some(opt)` if this item is final, with `opt` being the
+// `Revision` that it may represent.
+//
+// If the item is not terminal, return `None`
+fn final_revision(&self) -> Option> {
+match self.element {
+Element::Block(_) => None,
+Element::Rev(r) => Some(Some(r)),
+Element::None => Some(None),
+}
+}
}
impl From> for NodeTree {
To: gracinet, #hg-reviewers, kevincox
Cc: martinvonz, durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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>` 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
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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);
> +
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
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
gracinet updated this revision to Diff 19327.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7794?vs=19043&id=19327
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7794/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7794
AFFECTED FILES
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
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
@@ -220,17 +220,58 @@
&self,
prefix: NodePrefixRef<'p>,
) -> Result, NodeMapError> {
-let mut visit = self.len() - 1;
-for i in 0..prefix.len() {
-let nybble = prefix.get_nybble(i);
-match self[visit].get(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);
+
+fn next(&mut self) -> Option {
+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].get(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> for NodeTree {
To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7794: rust-nodemap: generic NodeTreeVisitor
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` 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
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, 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);
+
+fn next(&mut self) -> Option {
+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> for NodeTree {
To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
