D7791: rust-nodemap: NodeMap trait with simplest implementor

[martinvonz (Martin von Zweigbergk)]

martinvonz added inline comments.

INLINE COMMENTS

> gracinet wrote in nodemap.rs:150
> I've looked into trait alias while working on this, for the exact same 
> reason, and went through most you guys are saying about that.
> 
> Seems that this is complicated for the language because they'd like to have 
> the
> possibility to `impl` it.

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.

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 implementor

[gracinet (Georges Racinet)]

gracinet added inline comments.

INLINE COMMENTS

> martinvonz wrote in nodemap.rs:150
> I find `Deref + Send` hard to understand. I think it would 
> be helpful to name it. Could we at least define an alias for it?
> 
> Perhaps it's even better to define a trait for it and add named methods on 
> that, but if those methods would just be `len()` and `index()` it probably 
> doesn't make any sense to define the trait.

I've looked into trait alias while working on this, for the exact same reason, 
and went through most you guys are saying about that.

Seems that this is complicated for the language because they'd like to have the
possibility to `impl` it.

> martinvonz wrote in nodemap.rs:150
> Do we need `Send`? Maybe it later when you need it (unless you actually need 
> it now and I'm just mistaken, of course).

About `Send`, without it we can't expose `NodeTree` to the Python layer, IIRC

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 implementor

[Raphaël Gomès]

Alphare added inline comments.

INLINE COMMENTS

> martinvonz wrote in nodemap.rs:150
> > Alas, trait aliases are not stable: rust#55628.
> 
> I didn't know about trait aliases, but I think you can already do this:
> 
>   trait Thing : Deref + Send  {}
> 
> 
> 
> > ... since this is a single occurrence in a private field, I find it 
> > reasonable.
> 
> It's one instance right now. It's 7 instances of `Box>` at the 
> end of the series...

> I didn't know about trait aliases, but I think you can already do this:
>  `trait Thing : Deref + Send  {}`

Using an empty supertrait will not work because fat pointers have different 
metadata.
https://play.rust-lang.org/?version=nightly=debug=2018=4f1d374e426c9791cbf73421160dc7c3

> It's one instance right now. It's 7 instances of Box> at the 
> end of the series...

Ah true, that is indeed verbose, but manageable. Unfortunately, from a language 
perspective, I think that a type macro would be our only choice, but my opinion 
is that 1) it's ugly and more code to maintain and 2) I'm not even sure it 
would work.

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 implementor

[martinvonz (Martin von Zweigbergk)]

martinvonz added inline comments.

INLINE COMMENTS

> Alphare wrote in nodemap.rs:150
> > I find Deref + Send hard to understand. I think it would 
> > be helpful to name it. Could we at least define an alias for it?
> 
> Alas, trait aliases are not stable: rust#55628 
> .
> 
> On a more subjective note, I find this syntax quite readable as it is (as 
> readable as Rust usually is), and since this is a single occurrence in a 
> private field, I find it reasonable.

> Alas, trait aliases are not stable: rust#55628.

I didn't know about trait aliases, but I think you can already do this:

  trait Thing : Deref + Send  {}



> ... since this is a single occurrence in a private field, I find it 
> reasonable.

It's one instance right now. It's 7 instances of `Box>` at the 
end of the series...

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 implementor

[Raphaël Gomès]

Alphare added inline comments.

INLINE COMMENTS

> martinvonz wrote in nodemap.rs:150
> I find `Deref + Send` hard to understand. I think it would 
> be helpful to name it. Could we at least define an alias for it?
> 
> Perhaps it's even better to define a trait for it and add named methods on 
> that, but if those methods would just be `len()` and `index()` it probably 
> doesn't make any sense to define the trait.

> I find Deref + Send hard to understand. I think it would be 
> helpful to name it. Could we at least define an alias for it?

Alas, trait aliases are not stable: rust#55628 
.

On a more subjective note, I find this syntax quite readable as it is (as 
readable as Rust usually is), and since this is a single occurrence in a 
private field, I find it reasonable.

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 implementor

[martinvonz (Martin von Zweigbergk)]

martinvonz added inline comments.

INLINE COMMENTS

> nodemap.rs:150
> +pub struct NodeTree {
> +readonly: Box + Send>,
> +}

I find `Deref + Send` hard to understand. I think it would be 
helpful to name it. Could we at least define an alias for it?

Perhaps it's even better to define a trait for it and add named methods on 
that, but if those methods would just be `len()` and `index()` it probably 
doesn't make any sense to define the trait.

> nodemap.rs:150
> +pub struct NodeTree {
> +readonly: Box + Send>,
> +}

Do we need `Send`? Maybe it later when you need it (unless you actually need it 
now and I'm just mistaken, of course).

> nodemap.rs:153
> +
> +/// Return `None` unless the `Node` for `rev` has given prefix in `index`.
> +fn has_prefix_or_none<'p>(

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?

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: 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 implementor

[kevincox (Kevin Cox)]

kevincox added inline comments.
kevincox accepted this revision.

INLINE COMMENTS

> nodemap.rs:37
> +/// whose data should not be owned by the `NodeMap`.
> +pub trait NodeMap {
> +fn find_bin<'a>(

Can you please add doc-comments for this? I find that documenting trait methods 
is especially important.

> nodemap.rs:205
> +impl fmt::Debug for NodeTree {
> +fn fmt(, f:  fmt::Formatter<'_>) -> fmt::Result {
> +let blocks: &[Block] = &*self.readonly;

I don't think the `<'_>` is necessary.

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: 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 implementor

[gracinet (Georges Racinet)]

gracinet updated this revision to Diff 19324.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D7791?vs=19134=19324

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/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 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>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+fn find_hex(
+,
+idx:  RevlogIndex,
+prefix: ,
+) -> Result, NodeMapError> {
+self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+}
+}
 
 /// Low level NodeTree [`Blocks`] elements
 ///
@@ -110,9 +145,87 @@
 }
 }
 
+/// 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) => visit = idx,
+}
+}
+Err(NodeMapError::MultipleResults)
+}
+}
+
+impl From> for NodeTree {
+fn from(vec: Vec) -> Self {
+NodeTree {
+readonly: Box::new(vec),
+}
+}
+}
+
+impl fmt::Debug for NodeTree {
+fn fmt(, f:  fmt::Formatter<'_>) -> fmt::Result {
+let blocks: &[Block] = &*self.readonly;
+write!(f, "readonly: {:?}", blocks)
+}
+}
+
+impl NodeMap for NodeTree {
+fn find_bin<'a>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, 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 {
@@ -157,4 +270,70 @@
 assert_eq!(block.get(2), Element::Rev(0));
 assert_eq!(block.get(4), Element::Rev(1));
 }
+
+type TestIndex = HashMap;
+
+impl RevlogIndex for TestIndex {
+fn node(, rev: Revision) -> Option<> {
+self.get()
+}
+
+fn len() -> 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:  TestIndex, rev: Revision, hex: ) {
+idx.insert(rev, node_from_hex(!("{: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 

D7791: rust-nodemap: NodeMap trait with simplest implementor

[gracinet (Georges Racinet)]

gracinet updated this revision to Diff 19134.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D7791?vs=19040=19134

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/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 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>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+fn find_hex(
+,
+idx:  RevlogIndex,
+prefix: ,
+) -> Result, 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 + 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].read(nybble) {
+Element::None => return Ok(None),
+Element::Rev(r) => return Ok(Some(r)),
+Element::Block(idx) => visit = idx,
+}
+}
+Err(NodeMapError::MultipleResults)
+}
+}
+
+impl From> for NodeTree {
+fn from(vec: Vec) -> Self {
+NodeTree {
+readonly: Box::new(vec),
+}
+}
+}
+
+impl fmt::Debug for NodeTree {
+fn fmt(, f:  fmt::Formatter<'_>) -> fmt::Result {
+let blocks: &[Block] = &*self.readonly;
+write!(f, "readonly: {:?}", blocks)
+}
+}
+
+impl NodeMap for NodeTree {
+fn find_bin<'a>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, 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 {
@@ -159,4 +272,70 @@
 assert_eq!(block.read(2), Element::Rev(0));
 assert_eq!(block.read(4), Element::Rev(1));
 }
+
+type TestIndex = HashMap;
+
+impl RevlogIndex for TestIndex {
+fn node(, rev: Revision) -> Option<> {
+self.get()
+}
+
+fn len() -> 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:  TestIndex, rev: Revision, hex: ) {
+idx.insert(rev, node_from_hex(!("{: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 

D7791: rust-nodemap: NodeMap trait with simplest implementor

[gracinet (Georges Racinet)]

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 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>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, NodeMapError>;
+
+fn find_hex(
+,
+idx:  RevlogIndex,
+prefix: ,
+) -> Result, 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 + 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].read(nybble) {
+Element::None => return Ok(None),
+Element::Rev(r) => return Ok(Some(r)),
+Element::Block(idx) => visit = idx,
+}
+}
+Err(NodeMapError::MultipleResults)
+}
+}
+
+impl From> for NodeTree {
+fn from(vec: Vec) -> Self {
+NodeTree {
+readonly: Box::new(vec),
+}
+}
+}
+
+impl fmt::Debug for NodeTree {
+fn fmt(, f:  fmt::Formatter<'_>) -> fmt::Result {
+let blocks: &[Block] = &*self.readonly;
+write!(f, "readonly: {:?}", blocks)
+}
+}
+
+impl NodeMap for NodeTree {
+fn find_bin<'a>(
+,
+idx:  RevlogIndex,
+prefix: NodePrefixRef<'a>,
+) -> Result, 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;
+
+impl RevlogIndex for TestIndex {
+fn node(, rev: Revision) -> Option<> {
+self.get()
+}
+
+fn len() -> 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:  TestIndex, rev: Revision,