D7791: rust-nodemap: NodeMap trait with simplest implementor
gracinet (Georges Racinet)
phabricator at mercurial-scm.org
Mon Jan 6 19:25:44 UTC 2020
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.
REVISION SUMMARY
We're defining here only a small part of the immutable
methods it will have at the end. This is so we can
focus in the following changesets on the needed abstractions
for a mutable append-only serializable version.
The first implementor exposes the actual lookup
algorithm in its simplest form. It will have to be expanded
to account for the missing methods, and the special cases
related to NULL_NODE.
REPOSITORY
rHG Mercurial
BRANCH
default
REVISION DETAIL
https://phab.mercurial-scm.org/D7791
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
@@ -12,8 +12,43 @@
//! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context.
-use super::Revision;
+use super::{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<NodeError> for NodeMapError {
+ fn from(err: NodeError) -> Self {
+ NodeMapError::InvalidNodePrefix(err)
+ }
+}
+
+/// Mapping system from Mercurial nodes to revision numbers.
+///
+/// Many methods in this trait work in conjunction with a `RevlogIndex`
+/// whose data should not be owned by the `NodeMap`.
+pub trait NodeMap {
+ fn find_bin<'a>(
+ &self,
+ idx: &impl RevlogIndex,
+ prefix: NodePrefixRef<'a>,
+ ) -> Result<Option<Revision>, NodeMapError>;
+
+ fn find_hex(
+ &self,
+ idx: &impl RevlogIndex,
+ prefix: &str,
+ ) -> Result<Option<Revision>, NodeMapError> {
+ self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+ }
+}
/// Low level NodeTree [`Blocks`] elements
///
@@ -112,9 +147,87 @@
}
}
+/// A 16-radix tree with the root block at the end
+pub struct NodeTree {
+ readonly: Box<dyn Deref<Target = [Block]> + Send>,
+}
+
+/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
+fn has_prefix_or_none<'p>(
+ idx: &impl RevlogIndex,
+ prefix: NodePrefixRef<'p>,
+ rev: Revision,
+) -> Result<Option<Revision>, 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>(
+ &self,
+ prefix: NodePrefixRef<'p>,
+ ) -> Result<Option<Revision>, 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].read(nybble) {
+ Element::None => return Ok(None),
+ Element::Rev(r) => return Ok(Some(r)),
+ Element::Block(idx) => visit = idx,
+ }
+ }
+ Err(NodeMapError::MultipleResults)
+ }
+}
+
+impl From<Vec<Block>> for NodeTree {
+ fn from(vec: Vec<Block>) -> Self {
+ NodeTree {
+ readonly: Box::new(vec),
+ }
+ }
+}
+
+impl fmt::Debug for NodeTree {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let blocks: &[Block] = &*self.readonly;
+ write!(f, "readonly: {:?}", blocks)
+ }
+}
+
+impl NodeMap for NodeTree {
+ fn find_bin<'a>(
+ &self,
+ idx: &impl RevlogIndex,
+ prefix: NodePrefixRef<'a>,
+ ) -> Result<Option<Revision>, NodeMapError> {
+ self.lookup(prefix.clone()).and_then(|opt| {
+ opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev))
+ })
+ }
+}
+
#[cfg(test)]
mod tests {
+ use super::NodeMapError::*;
use super::*;
+ use crate::revlog::node::{node_from_hex, Node};
+ use std::collections::HashMap;
/// Creates a `Block` using a syntax close to the `Debug` output
macro_rules! block {
@@ -160,4 +273,70 @@
assert_eq!(block.read(4), Element::Rev(1));
}
+ type TestIndex = HashMap<Revision, Node>;
+
+ impl RevlogIndex for TestIndex {
+ fn node(&self, rev: Revision) -> Option<&Node> {
+ self.get(&rev)
+ }
+
+ fn len(&self) -> usize {
+ self.len()
+ }
+ }
+
+ /// Pad hexadecimal Node prefix with zeros on the right, then insert
+ ///
+ /// This is just to avoid having to repeatedly write 40 hexadecimal
+ /// digits for test data.
+ fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
+ idx.insert(rev, node_from_hex(&format!("{:0<40}", hex)).unwrap());
+ }
+
+ fn sample_nodetree() -> NodeTree {
+ NodeTree::from(vec![
+ block![0: Rev(9)],
+ block![0: Rev(0), 1: Rev(9)],
+ block![0: Block(1), 1:Rev(1)],
+ ])
+ }
+
+ #[test]
+ fn test_nt_debug() {
+ let nt = sample_nodetree();
+ assert_eq!(
+ format!("{:?}", nt),
+ "readonly: \
+ [[0: Rev(9)], [0: Rev(0), 1: Rev(9)], [0: Block(1), 1: Rev(1)]]"
+ );
+ }
+
+ #[test]
+ fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
+ let mut idx: TestIndex = HashMap::new();
+ pad_insert(&mut idx, 1, "1234deadcafe");
+
+ let nt = NodeTree::from(vec![block![1: Rev(1)]]);
+ assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
+ assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
+ assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
+ assert_eq!(nt.find_hex(&idx, "1a")?, None);
+ assert_eq!(nt.find_hex(&idx, "ab")?, None);
+ Ok(())
+ }
+
+ #[test]
+ fn test_immutable_find_one_jump() {
+ let mut idx = TestIndex::new();
+ pad_insert(&mut idx, 9, "012");
+ pad_insert(&mut idx, 0, "00a");
+
+ let nt = sample_nodetree();
+
+ assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
+ assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
+ assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
+ assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
+ }
+
}
To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
More information about the Mercurial-devel
mailing list