D7819: rust-nodemap: core implementation for shortest
Closed by commit rHG0e8a9c0fbc8c: rust-nodemap: core implementation for
shortest (authored by gracinet).
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/D7819?vs=20283=20313
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -279,20 +316,24 @@
fn validate_candidate(
idx: RevlogIndex,
prefix: NodePrefixRef,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -387,13 +428,26 @@
}
/// Main working method for `NodeTree` searches
-fn lookup<'p>(
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
+fn lookup(
,
-prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+prefix: NodePrefixRef,
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -638,6 +692,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
D7819: rust-nodemap: core implementation for shortest
Alphare updated this revision to Diff 20283.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=20278=20283
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -279,20 +316,24 @@
fn validate_candidate(
idx: RevlogIndex,
prefix: NodePrefixRef,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -387,13 +428,26 @@
}
/// Main working method for `NodeTree` searches
-fn lookup<'p>(
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
+fn lookup(
,
-prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+prefix: NodePrefixRef,
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -638,6 +692,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+
D7819: rust-nodemap: core implementation for shortest
Alphare updated this revision to Diff 20278.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=20237=20278
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -277,20 +314,24 @@
fn validate_candidate(
idx: RevlogIndex,
prefix: NodePrefixRef,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -384,13 +425,26 @@
}
/// Main working method for `NodeTree` searches
-fn lookup<'p>(
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
+fn lookup(
,
-prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+prefix: NodePrefixRef,
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -635,6 +689,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+
D7819: rust-nodemap: core implementation for shortest
Alphare updated this revision to Diff 20237.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=20218=20237
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -277,20 +314,24 @@
fn validate_candidate(
idx: RevlogIndex,
prefix: NodePrefixRef,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -384,13 +425,26 @@
}
/// Main working method for `NodeTree` searches
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -635,6 +689,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result,
D7819: rust-nodemap: core implementation for shortest
Alphare updated this revision to Diff 20218.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=20028=20218
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -259,20 +296,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -365,13 +406,26 @@
}
/// Main working method for `NodeTree` searches
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -616,6 +670,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) ->
D7819: rust-nodemap: core implementation for shortest
marmoute updated this revision to Diff 20028.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=19640=20028
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -259,20 +296,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -356,13 +397,26 @@
}
/// Main working method for `NodeTree` searches
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -607,6 +661,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result,
D7819: rust-nodemap: core implementation for shortest
marmoute added a comment. marmoute accepted this revision. It seems like all the feedback have been applied, and the changeset looks good to me. REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7819/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7819 To: gracinet, #hg-reviewers, kevincox, marmoute Cc: marmoute, martinvonz, durin42, kevincox, mercurial-devel ___ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
D7819: rust-nodemap: core implementation for shortest
gracinet marked an inline comment as done.
gracinet updated this revision to Diff 19640.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=19639=19640
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -259,20 +296,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+candidate: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = candidate;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -356,13 +397,26 @@
}
/// Main working method for `NodeTree` searches
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -607,6 +661,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+
D7819: rust-nodemap: core implementation for shortest
gracinet added inline comments. gracinet marked 3 inline comments as done. INLINE COMMENTS > kevincox wrote in nodemap.rs:337 > Can you describe the return value in the doc comment. Done > martinvonz wrote in nodemap.rs:575 > I'm fine with either. We'll expose it as "shortest" in the python API anyway, > I assume. Feel free to change as far as I'm concerned. Okay, I've settled with `unique_prefix_len_bin` etc, keeping the convention that it's `something_bin`, `something_hex`, etc. REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7819/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7819 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
D7819: rust-nodemap: core implementation for shortest
gracinet updated this revision to Diff 19639.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=19331=19639
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -17,6 +17,7 @@
RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -98,6 +99,42 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+///
+/// If several Revisions match the given prefix, a [`MultipleResults`]
+/// error is returned.
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
+/// of the prefix as input.
+fn unique_prefix_len_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+
+/// Same as `unique_prefix_len_bin`, with a full `Node` as input
+fn unique_prefix_len_node(
+,
+idx: RevlogIndex,
+node: ,
+) -> Result, NodeMapError> {
+self.unique_prefix_len_bin(idx, node.into())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -259,20 +296,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+cand: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = cand;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -356,13 +397,26 @@
}
/// Main working method for `NodeTree` searches
+///
+/// The first returned value is the result of analysing `NodeTree` data
+/// *alone*: whereas `None` guarantees that the given prefix is absent
+/// from the `NodeTree` data (but still could match `NULL_NODE`), with
+/// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
+/// that could match the prefix. Actually, all that can be inferred from
+/// the `NodeTree` data is that `rev` is the revision with the longest
+/// common node prefix with the given prefix.
+///
+/// The second returned value is the size of the smallest subprefix
+/// of `prefix` that would give the same result, i.e. not the
+/// `MultipleResults` error variant (again, using only the data of the
+/// `NodeTree`).
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for visit_item in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, visit_item) in self.visit(prefix).enumerate() {
if let Some(opt) = visit_item.final_revision() {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -607,6 +661,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn unique_prefix_len_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result,
D7819: rust-nodemap: core implementation for shortest
martinvonz added inline comments. INLINE COMMENTS > gracinet wrote in nodemap.rs:575 > I have personally nothing against this, and actually find this `shortest` not > to be clear, but… it's also the name in the C implementation and the Python > API, IIRC. > > @martinvonz I see you subscribed, what do you think ? I'm fine with either. We'll expose it as "shortest" in the python API anyway, I assume. Feel free to change as far as I'm concerned. REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7819/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7819 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
D7819: rust-nodemap: core implementation for shortest
gracinet added inline comments. INLINE COMMENTS > kevincox wrote in nodemap.rs:575 > How about `unique_bin_prefix_len`? I have personally nothing against this, and actually find this `shortest` not to be clear, but… it's also the name in the C implementation and the Python API, IIRC. @martinvonz I see you subscribed, what do you think ? REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7819/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7819 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
D7819: rust-nodemap: core implementation for shortest
martinvonz added inline comments.
INLINE COMMENTS
> nodemap.rs:59
> +/// Returns `None` if no `Revision` could be found for the prefix.
> +fn shortest_bin<'a>(
> +,
can the explicit lifetime be dropped?
> nodemap.rs:243
> prefix: NodePrefixRef<'p>,
> -rev: Option,
> -) -> Result, NodeMapError> {
> -if prefix.is_prefix_of(_NODE) {
> -// NULL_REVISION always matches a prefix made only of zeros
> +cand: (Option, usize),
> +) -> Result<(Option, usize), NodeMapError> {
s/cand/candidate/? I prefer to avoid unusual abbreviations.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
D7819: rust-nodemap: core implementation for shortest
kevincox added inline comments. kevincox accepted this revision. INLINE COMMENTS > nodemap.rs:337 > /// Main working method for `NodeTree` searches > fn lookup<'p>( > , Can you describe the return value in the doc comment. > nodemap.rs:575 > + > +fn shortest_bin<'a>( > +, How about `unique_bin_prefix_len`? > nodemap.rs:766 > > +fn shortest_hex( > +, `unique_bin_prefix_len`? REPOSITORY rHG Mercurial CHANGES SINCE LAST ACTION https://phab.mercurial-scm.org/D7819/new/ REVISION DETAIL https://phab.mercurial-scm.org/D7819 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
D7819: rust-nodemap: core implementation for shortest
gracinet updated this revision to Diff 19331.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D7819?vs=19139=19331
BRANCH
default
CHANGES SINCE LAST ACTION
https://phab.mercurial-scm.org/D7819/new/
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -16,6 +16,7 @@
node::get_nybble, node::NULL_NODE, Node, NodeError, NodePrefix,
NodePrefixRef, Revision, RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -47,6 +48,20 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError>;
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+fn shortest_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
fn find_hex(
,
idx: RevlogIndex,
@@ -54,6 +69,16 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Same as `shortest_bin`, with the hexadecimal representation of the
+/// prefix as input.
+fn shortest_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.shortest_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -215,20 +240,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+cand: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = cand;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -308,10 +337,10 @@
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
-for (leaf, _, _, opt) in self.visit(prefix) {
+) -> Result<(Option, usize), NodeMapError> {
+for (i, (leaf, _, _, opt)) in self.visit(prefix).enumerate() {
if leaf {
-return Ok(opt);
+return Ok((opt, i + 1));
}
}
Err(NodeMapError::MultipleResults)
@@ -540,6 +569,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn shortest_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError> {
+validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, shortest)| opt.map(|_rev| shortest))
}
}
@@ -665,6 +704,7 @@
assert_eq!(nt.find_hex(, "01"), Ok(Some(9)));
assert_eq!(nt.find_hex(, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(, "00a"), Ok(Some(0)));
+assert_eq!(nt.shortest_hex(, "00a"), Ok(Some(3)));
assert_eq!(nt.find_hex(, "000"), Ok(Some(NULL_REVISION)));
}
@@ -684,8 +724,10 @@
};
assert_eq!(nt.find_hex(, "10")?, Some(1));
assert_eq!(nt.find_hex(, "c")?, Some(2));
+assert_eq!(nt.shortest_hex(, "c")?, Some(1));
assert_eq!(nt.find_hex(, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(, "000")?, Some(NULL_REVISION));
+assert_eq!(nt.shortest_hex(, "000")?, Some(3));
assert_eq!(nt.find_hex(, "01")?, Some(9));
Ok(())
}
@@ -721,6 +763,13 @@
self.nt.find_hex(, prefix)
}
+fn
D7819: rust-nodemap: core implementation for shortest
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.
REVISION SUMMARY
In this implementation, we just make `lookup()` return also the number
of steps that have been needed to come to a conclusion from the
nodetree data, and `validate_candidate()` takes care of the special
cases related to `NULL_NODE`.
This way of doing minimizes code duplication, but it means that
the comparatively slower finding of first non zero nybble will run
for all calls to `find()` where it is not needed.
Still running on the file generated for the mozilla-central repository,
it seems indeed that we now get more ofter 320 ns than 310. The odds that
this could have a significant impact on real life Mercurial performance
are still looking low. Let's wait for actual benchmark runs to see if
an optimization is needed here.
REPOSITORY
rHG Mercurial
BRANCH
default
REVISION DETAIL
https://phab.mercurial-scm.org/D7819
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
@@ -16,6 +16,7 @@
node::get_nybble, node::NULL_NODE, Node, NodeError, NodePrefix,
NodePrefixRef, Revision, RevlogIndex, NULL_REVISION,
};
+use std::cmp::max;
use std::fmt;
use std::mem;
use std::ops::Deref;
@@ -47,6 +48,20 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError>;
+/// Give the size of the shortest node prefix that determines
+/// the revision uniquely.
+///
+/// From a binary node prefix, if it is matched in the node map, this
+/// returns the number of hexadecimal digits that would had sufficed
+/// to find the revision uniquely.
+///
+/// Returns `None` if no `Revision` could be found for the prefix.
+fn shortest_bin<'a>(
+,
+idx: RevlogIndex,
+node_prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
fn find_hex(
,
idx: RevlogIndex,
@@ -54,6 +69,16 @@
) -> Result, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
}
+
+/// Same as `shortest_bin`, with the hexadecimal representation of the
+/// prefix as input.
+fn shortest_hex(
+,
+idx: RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.shortest_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
}
pub trait MutableNodeMap: NodeMap {
@@ -217,20 +242,24 @@
fn validate_candidate<'p>(
idx: RevlogIndex,
prefix: NodePrefixRef<'p>,
-rev: Option,
-) -> Result, NodeMapError> {
-if prefix.is_prefix_of(_NODE) {
-// NULL_REVISION always matches a prefix made only of zeros
+cand: (Option, usize),
+) -> Result<(Option, usize), NodeMapError> {
+let (rev, steps) = cand;
+if let Some(nz_nybble) = prefix.first_different_nybble(_NODE) {
+rev.map_or(Ok((None, steps)), |r| {
+has_prefix_or_none(idx, prefix, r)
+.map(|opt| (opt, max(steps, nz_nybble + 1)))
+})
+} else {
+// the prefix is only made of zeros; NULL_REVISION always matches it
// and any other *valid* result is an ambiguity
match rev {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
-None => Ok(Some(NULL_REVISION)),
+None => Ok((Some(NULL_REVISION), steps + 1)),
_ => Err(NodeMapError::MultipleResults),
},
}
-} else {
-rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
@@ -310,11 +339,13 @@
fn lookup<'p>(
,
prefix: NodePrefixRef<'p>,
-) -> Result, NodeMapError> {
+) -> Result<(Option, usize), NodeMapError> {
+let mut i = 1;
for (leaf, _, _, opt) in self.visit(prefix) {
if leaf {
-return Ok(opt);
+return Ok((opt, i));
}
+i += 1;
}
Err(NodeMapError::MultipleResults)
}
@@ -542,6 +573,16 @@
prefix: NodePrefixRef<'a>,
) -> Result, NodeMapError> {
validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, _shortest)| opt)
+}
+
+fn shortest_bin<'a>(
+,
+idx: RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError> {
+validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+.map(|(opt, shortest)| opt.map(|_rev| shortest))
}
}
@@ -667,6 +708,7 @@
assert_eq!(nt.find_hex(, "01"), Ok(Some(9)));
assert_eq!(nt.find_hex(, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(, "00a"),
