This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7794

rust-nodemap: generic NodeTreeVisitor
ClosedPublic

Authored by gracinet on Jan 6 2020, 2:25 PM.

Details

Reviewers
kevincox
martinvonz
Group Reviewers
hg-reviewers
Commits
rHG796d05f3fa84: rust-nodemap: generic NodeTreeVisitor
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 structured iterator item will allow different usages from
lookup() and the upcoming insert().

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

gracinet created this revision.Jan 6 2020, 2:25 PM
gracinet updated this revision to Diff 19327.Jan 15 2020, 6:47 PM
kevincox requested changes to this revision.Jan 16 2020, 5:16 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
254

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.

This revision now requires changes to proceed.Jan 16 2020, 5:16 AM
martinvonz added a subscriber: martinvonz.Jan 22 2020, 2:18 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/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.

gracinet edited the summary of this revision. (Show Details)Jan 27 2020, 10:49 AM
gracinet updated this revision to Diff 19634.
gracinet marked 2 inline comments as done.Jan 27 2020, 10:54 AM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
264–269

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.

martinvonz accepted this revision.Jan 27 2020, 2:00 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/nodemap.rs
248

would something like block_index be clearer?

260

can these lifetimes be anonymous?

gracinet marked 2 inline comments as done.Jan 27 2020, 2:09 PM
gracinet added inline comments.
rust/hg-core/src/revlog/nodemap.rs
248

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

gracinet marked an inline comment as done.Jan 27 2020, 2:13 PM
gracinet added a commit: rHG796d05f3fa84: rust-nodemap: generic NodeTreeVisitor.
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG796d05f3fa84: rust-nodemap: generic NodeTreeVisitor (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/revlog/nodemap.rs (55 lines)

Diff 19327

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

/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
/// ///
/// This partial implementation lacks /// This partial implementation lacks
/// - special cases for NULL_REVISION /// - special cases for NULL_REVISION
fn lookup<'p>( fn lookup<'p>(
&self, &self,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
let mut visit = self.len() - 1; for (leaf, _, _, opt) in self.visit(prefix) {
for i in 0..prefix.len() { if leaf {
let nybble = prefix.get_nybble(i); return Ok(opt);
match self[visit].get(nybble) {
Element::None => return Ok(None),
Element::Rev(r) => return Ok(Some(r)),
Element::Block(idx) => visit = idx,
} }
} }
Err(NodeMapError::MultipleResults) 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,
martinvonzUnsubmitted
Done

would something like block_index be clearer?

martinvonz: would something like `block_index` be clearer?
gracinetAuthorUnsubmitted
Done

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

gracinet: I found it to be clearer for the emitter, but in the iterator implementation, it expresses…
nybble_idx: usize,
done: bool,
}
impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
type Item = (bool, usize, u8, Option<Revision>);
kevincoxUnsubmitted
Done

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.

kevincox: I would prefer making this a struct so that you can name the fields. You can still pattern…
fn next(&mut self) -> Option<Self::Item> {
if self.done || self.nybble_idx >= self.prefix.len() {
return None;
}
martinvonzUnsubmitted
Not Done

can these lifetimes be anonymous?

martinvonz: can these lifetimes be anonymous?
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)
}
martinvonzUnsubmitted
Done

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.

martinvonz: There will only be a valid result if this is a leaf, so it might be better to combine `leaf`…
gracinetAuthorUnsubmitted
Done

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.

gracinet: I understand your concern, but `<Option<Option<Revision>>` would defeat the purpose of not…
};
self.nybble_idx += 1;
self.done = leaf;
Some((leaf, visit, nybble, opt))
}
} }
impl From<Vec<Block>> for NodeTree { impl From<Vec<Block>> for NodeTree {
fn from(vec: Vec<Block>) -> Self { fn from(vec: Vec<Block>) -> Self {
Self::new(Box::new(vec)) Self::new(Box::new(vec))
} }
} }