D7791: rust-nodemap: NodeMap trait with simplest implementation
Closed by commit rHGe52401a95b94: rust-nodemap: NodeMap trait with simplest
implementation (authored by gracinet).
gracinet marked 2 inline comments 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/D7791?vs=19631=19644
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7791/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7791
AFFECTED FILES
rust/hg-core/src/revlog/node.rs
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
@@ -12,8 +12,88 @@
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.
-use super::Revision;
+use super::{
+Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
+};
use std::fmt;
+use std::ops::Deref;
+
+#[derive(Debug, PartialEq)]
+pub enum NodeMapError {
+MultipleResults,
+InvalidNodePrefix(NodeError),
+/// A `Revision` stored in the nodemap could not be found in the index
+RevisionNotInIndex(Revision),
+}
+
+impl From for NodeMapError {
+fn from(err: NodeError) -> Self {
+NodeMapError::InvalidNodePrefix(err)
+}
+}
+
+/// Mapping system from Mercurial nodes to revision numbers.
+///
+/// ## `RevlogIndex` and `NodeMap`
+///
+/// One way to think about their relationship is that
+/// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
+/// carried by a [`RevlogIndex`].
+///
+/// Many of the methods in this trait take a `RevlogIndex` argument
+/// which is used for validation of their results. This index must naturally
+/// be the one the `NodeMap` is about, and it must be consistent.
+///
+/// Notably, the `NodeMap` must not store
+/// information about more `Revision` values than there are in the index.
+/// In these methods, an encountered `Revision` is not in the index, a
+/// [`RevisionNotInIndex`] error is returned.
+///
+/// In insert operations, the rule is thus that the `NodeMap` must always
+/// be updated after the `RevlogIndex`
+/// be updated first, and the `NodeMap` second.
+///
+/// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
+/// [`RevlogIndex`]: ../trait.RevlogIndex.html
+pub trait NodeMap {
+/// Find the unique `Revision` having the given `Node`
+///
+/// If no Revision matches the given `Node`, `Ok(None)` is returned.
+fn find_node(
+,
+index: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.find_bin(index, node.into())
+}
+
+/// Find the unique Revision whose `Node` starts with a given binary prefix
+///
+/// If no Revision matches the given prefix, `Ok(None)` is returned.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn find_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Find the unique Revision whose `Node` hexadecimal string representation
+/// starts with a given prefix
+///
+/// If no Revision matches the given prefix, `Ok(None)` is returned.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn find_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+}
/// Low level NodeTree [`Blocks`] elements
///
@@ -110,9 +190,86 @@
}
}
+/// A 16-radix tree with the root block at the end
+pub struct NodeTree {
+readonly: Box + Send>,
+}
+
+/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
+fn has_prefix_or_none<'p>(
+idx: RevlogIndex,
+prefix: NodePrefixRef<'p>,
+rev: Revision,
+) -> Result, NodeMapError> {
+idx.node(rev)
+.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
+.map(|node| {
+if prefix.is_prefix_of(node) {
+Some(rev)
+} else {
+None
+}
+})
+}
+
+impl NodeTree {
+/// Main working method for `NodeTree` searches
+///
+/// This partial implementation lacks special cases for NULL_REVISION
+fn lookup<'p>(
+,
+prefix: NodePrefixRef<'p>,
+) -> Result, NodeMapError> {
+let blocks: &[Block] = &*self.readonly;
+if blocks.is_empty() {
+return Ok(None);
+}
+let mut visit = blocks.len() - 1;
+for i in 0..prefix.len() {
+let nybble = prefix.get_nybble(i);
+match blocks[visit].get(nybble) {
+Element::None => return Ok(None),
+
D7791: rust-nodemap: NodeMap trait with simplest implementation
martinvonz added inline comments.
INLINE COMMENTS
> gracinet wrote in nodemap.rs:153
> Perhaps a better name would be better than this `has_` that indeed feels
> boolean?
>
> `check_prefix`? `confirm` ?
>
> Previous naming was `validate_candidate`, but that very same name is used at
> the end of the series when it becomes involved with `NULL_NODE` etc. Then
> this `has_prefix_or_none` becomes one step in the final verification.
>
> Returning a `bool` would mean adding a closure to the callers. making it less
> obvious that they are just chaining the maturation of the response.
>
> I'm leaving unchanged for now, not sure what the best is. Still note that
> this is a private function, there's no risk an external caller would be
> confused by what it does.
Yes, `validate_candidate` sounds much better. Could you send a follow-up with a
better name for it?
> gracinet wrote in nodemap.rs:205
> Removed
Still there? Or maybe it's a different one, but I think you can remove the
`<'_>` from the `fm::Formatter<'_>`.
> nodemap.rs:76
> +/// error is returned.
> +fn find_bin<'a>(
> +,
can the explicit lifetime be dropped?
> nodemap.rs:199
> +/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
> +fn has_prefix_or_none<'p>(
> +idx: RevlogIndex,
can the explicit lifetime be dropped?
> nodemap.rs:219
> +/// This partial implementation lacks special cases for NULL_REVISION
> +fn lookup<'p>(
> +,
can the explicit lifetime be dropped?
> nodemap.rs:256
> +impl NodeMap for NodeTree {
> +fn find_bin<'a>(
> +,
can the explicit lifetime be dropped?
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7791/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7791
To: gracinet, #hg-reviewers, kevincox
Cc: Alphare, martinvonz, durin42, kevincox, mercurial-devel
___
Mercurial-devel mailing list
Mercurial-devel@mercurial-scm.org
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7791: rust-nodemap: NodeMap trait with simplest implementation
gracinet added inline comments. gracinet marked 3 inline comments as done. INLINE COMMENTS > kevincox wrote in nodemap.rs:37 > Can you please add doc-comments for this? I find that documenting trait > methods is especially important. Sure, indeed it's more important than with the `impl`. > martinvonz wrote in nodemap.rs:150 > How about something like this then? > > type BlockSource = Box + Send>; > type ByteSource = Box + Send>; > > I won't insist, so up to you if you think it helps. Missed the type (not trait) alias suggestion. Maybe for the next update, then > martinvonz wrote in nodemap.rs:153 > I understand that you picked this interface because it works well for the > caller, but it feel a little weird to always return `None` or `Some(rev)` > where `rev` is one of the function inputs. It's practically a boolean-valued > function. Do the callers get much harder to read if you actually make it > boolean-valued? Perhaps a better name would be better than this `has_` that indeed feels boolean? `check_prefix`? `confirm` ? Previous naming was `validate_candidate`, but that very same name is used at the end of the series when it becomes involved with `NULL_NODE` etc. Then this `has_prefix_or_none` becomes one step in the final verification. Returning a `bool` would mean adding a closure to the callers. making it less obvious that they are just chaining the maturation of the response. I'm leaving unchanged for now, not sure what the best is. Still note that this is a private function, there's no risk an external caller would be confused by what it does. > kevincox wrote in nodemap.rs:205 > I don't think the `<'_>` is necessary. Removed REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7791/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7791 To: gracinet, #hg-reviewers, kevincox Cc: Alphare, martinvonz, durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7791: rust-nodemap: NodeMap trait with simplest implementation
gracinet retitled this revision from "rust-nodemap: NodeMap trait with simplest
implementor" to "rust-nodemap: NodeMap trait with simplest implementation".
gracinet updated this revision to Diff 19631.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7791?vs=19324=19631
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7791/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7791
AFFECTED FILES
rust/hg-core/src/revlog/node.rs
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
@@ -12,8 +12,88 @@
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.
-use super::Revision;
+use super::{
+Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
+};
use std::fmt;
+use std::ops::Deref;
+
+#[derive(Debug, PartialEq)]
+pub enum NodeMapError {
+MultipleResults,
+InvalidNodePrefix(NodeError),
+/// A `Revision` stored in the nodemap could not be found in the index
+RevisionNotInIndex(Revision),
+}
+
+impl From for NodeMapError {
+fn from(err: NodeError) -> Self {
+NodeMapError::InvalidNodePrefix(err)
+}
+}
+
+/// Mapping system from Mercurial nodes to revision numbers.
+///
+/// ## `RevlogIndex` and `NodeMap`
+///
+/// One way to think about their relationship is that
+/// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
+/// carried by a [`RevlogIndex`].
+///
+/// Many of the methods in this trait take a `RevlogIndex` argument
+/// which is used for validation of their results. This index must naturally
+/// be the one the `NodeMap` is about, and it must be consistent.
+///
+/// Notably, the `NodeMap` must not store
+/// information about more `Revision` values than there are in the index.
+/// In these methods, an encountered `Revision` is not in the index, a
+/// [`RevisionNotInIndex`] error is returned.
+///
+/// In insert operations, the rule is thus that the `NodeMap` must always
+/// be updated after the `RevlogIndex`
+/// be updated first, and the `NodeMap` second.
+///
+/// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
+/// [`RevlogIndex`]: ../trait.RevlogIndex.html
+pub trait NodeMap {
+/// Find the unique `Revision` having the given `Node`
+///
+/// If no Revision matches the given `Node`, `Ok(None)` is returned.
+fn find_node(
+,
+index: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.find_bin(index, node.into())
+}
+
+/// Find the unique Revision whose `Node` starts with a given binary prefix
+///
+/// If no Revision matches the given prefix, `Ok(None)` is returned.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn find_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Find the unique Revision whose `Node` hexadecimal string representation
+/// starts with a given prefix
+///
+/// If no Revision matches the given prefix, `Ok(None)` is returned.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn find_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+}
/// Low level NodeTree [`Blocks`] elements
///
@@ -110,9 +190,86 @@
}
}
+/// A 16-radix tree with the root block at the end
+pub struct NodeTree {
+readonly: Box + Send>,
+}
+
+/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
+fn has_prefix_or_none<'p>(
+idx: RevlogIndex,
+prefix: NodePrefixRef<'p>,
+rev: Revision,
+) -> Result, NodeMapError> {
+idx.node(rev)
+.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
+.map(|node| {
+if prefix.is_prefix_of(node) {
+Some(rev)
+} else {
+None
+}
+})
+}
+
+impl NodeTree {
+/// Main working method for `NodeTree` searches
+///
+/// This partial implementation lacks special cases for NULL_REVISION
+fn lookup<'p>(
+,
+prefix: NodePrefixRef<'p>,
+) -> Result, NodeMapError> {
+let blocks: &[Block] = &*self.readonly;
+if blocks.is_empty() {
+return Ok(None);
+}
+let mut visit = blocks.len() - 1;
+for i in 0..prefix.len() {
+let nybble = prefix.get_nybble(i);
+match blocks[visit].get(nybble) {
+Element::None => return Ok(None),
+Element::Rev(r) => return Ok(Some(r)),
+Element::Block(idx) =>
