This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7793

rust-nodemap: mutable NodeTree data structure
ClosedPublic

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

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGa19331456d48: rust-nodemap: mutable NodeTree data structure
Summary

Thanks to the previously indexing abstraction,
the only difference in the lookup algorithm is that we
don't need the special case for an empty NodeTree any more.

We've considered making the mutable root an Option<Block>,
but that leads to unpleasant checks and unwrap() unless we
abstract it as typestate patterns (NodeTree<Immutable> and
NodeTree<Mutated>) which seem exaggerated in that
case.

The initial copy of the root block is a very minor
performance penalty, given that it typically occurs just once
per transaction.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

gracinet created this revision.Jan 6 2020, 2:25 PM
gracinet updated this revision to Diff 19136.Jan 10 2020, 10:03 AM
gracinet updated this revision to Diff 19326.Jan 15 2020, 6:47 PM
kevincox accepted this revision.Jan 16 2020, 5:15 AM
kevincox added inline comments.
rust/hg-core/src/revlog/nodemap.rs
203

This strikes me as a weird name. The fact that it is an adjective rather than a noun is a hint. Can you rename to answer "Growable what?"

301

I would use https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_struct for consistency unless you really want to avoid printing the struct name.

gracinet updated this revision to Diff 19633.Jan 27 2020, 10:49 AM
gracinet added inline comments.Jan 27 2020, 10:54 AM
rust/hg-core/src/revlog/nodemap.rs
203

In a previous version, I was calling it mutable (also an adjective, btw), but that became just wrong with the introduction of the separate root block. I don't have many ideas:

  • added_inner_blocks ? actually, these are added on top of the readonly part and often mask some of the readonly blocks
  • added_non_root_blocks ? Eww
  • mutable_inner_blocks ?

I'm no native speaker, but the adjective thing doesn't deter me, I would expect it to be rather clear that it refers to blocks, given the type.
Open to suggestions, leaving as is for the time being

301

sadly, Formatter.debug_struct doesn't tale ?Sized arguments (at least in our target 1.34 version):

   --> hg-core/src/revlog/nodemap.rs:298:32
    |
298 |             .field("readonly", readonly)
    |                                ^^^^^^^^ doesn't have a size known at compile-time
    |
    = help: the trait `std::marker::Sized` is not implemented for `[revlog::nodemap::Block]`

Kept it as it was for the time being, just dropped the unneeded anonymous lifetime

Omitting the struct name was indeed on purpose, to make it more manageable in test data. That was useful in early versions. I would have been willing to drop it for the final form. Anyone using this for real data wouldn't care about just a few bytes at the beginning.

gracinet added a commit: rHGa19331456d48: rust-nodemap: mutable NodeTree data structure.Jan 27 2020, 2:13 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGa19331456d48: rust-nodemap: mutable NodeTree data structure (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 (87 lines)

Diff 19646

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

.entries((0..16).filter_map(|i| match self.get(i) { .entries((0..16).filter_map(|i| match self.get(i) {
Element::None => None, Element::None => None,
element => Some((i, element)), element => Some((i, element)),
})) }))
.finish() .finish()
} }
} }
/// A 16-radix tree with the root block at the end /// A mutable 16-radix tree with the root block logically at the end
///
/// Because of the append only nature of our node trees, we need to
/// keep the original untouched and store new blocks separately.
///
/// The mutable root `Block` is kept apart so that we don't have to rebump
/// it on each insertion.
pub struct NodeTree { pub struct NodeTree {
readonly: Box<dyn Deref<Target = [Block]> + Send>, readonly: Box<dyn Deref<Target = [Block]> + Send>,
growable: Vec<Block>,
kevincoxUnsubmitted
Not Done

This strikes me as a weird name. The fact that it is an adjective rather than a noun is a hint. Can you rename to answer "Growable what?"

kevincox: This strikes me as a weird name. The fact that it is an adjective rather than a noun is a hint.
gracinetAuthorUnsubmitted
Done

In a previous version, I was calling it mutable (also an adjective, btw), but that became just wrong with the introduction of the separate root block. I don't have many ideas:

  • added_inner_blocks ? actually, these are added on top of the readonly part and often mask some of the readonly blocks
  • added_non_root_blocks ? Eww
  • mutable_inner_blocks ?

I'm no native speaker, but the adjective thing doesn't deter me, I would expect it to be rather clear that it refers to blocks, given the type.
Open to suggestions, leaving as is for the time being

gracinet: In a previous version, I was calling it `mutable` (also an adjective, btw), but that became…
root: Block,
} }
impl Index<usize> for NodeTree { impl Index<usize> for NodeTree {
type Output = Block; type Output = Block;
fn index(&self, i: usize) -> &Block { fn index(&self, i: usize) -> &Block {
let ro_len = self.readonly.len();
if i < ro_len {
&self.readonly[i] &self.readonly[i]
} else if i == ro_len + self.growable.len() {
&self.root
} else {
&self.growable[i - ro_len]
}
} }
} }
/// Return `None` unless the `Node` for `rev` has given prefix in `index`. /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
fn has_prefix_or_none<'p>( fn has_prefix_or_none<'p>(
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'p>, prefix: NodePrefixRef<'p>,
rev: Revision, rev: Revision,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
idx.node(rev) idx.node(rev)
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev))
.map(|node| { .map(|node| {
if prefix.is_prefix_of(node) { if prefix.is_prefix_of(node) {
Some(rev) Some(rev)
} else { } else {
None None
} }
}) })
} }
impl NodeTree { impl NodeTree {
/// Initiate a NodeTree from an immutable slice-like of `Block`
///
/// We keep `readonly` and clone its root block if it isn't empty.
fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
let root = readonly
.last()
.map(|b| b.clone())
.unwrap_or_else(|| Block::new());
NodeTree {
readonly: readonly,
growable: Vec::new(),
root: root,
}
}
/// Total number of blocks
fn len(&self) -> usize { fn len(&self) -> usize {
self.readonly.len() self.readonly.len() + self.growable.len() + 1
} }
/// Implemented for completeness
///
/// A `NodeTree` always has at least the mutable root block.
#[allow(dead_code)]
fn is_empty(&self) -> bool { fn is_empty(&self) -> bool {
self.len() == 0 false
} }
/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
/// ///
/// This partial implementation lacks special cases for NULL_REVISION /// This partial implementation lacks 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> {
if self.is_empty() {
return Ok(None);
}
let mut visit = self.len() - 1; let mut visit = self.len() - 1;
for i in 0..prefix.len() { for i in 0..prefix.len() {
let nybble = prefix.get_nybble(i); let nybble = prefix.get_nybble(i);
match self[visit].get(nybble) { match self[visit].get(nybble) {
Element::None => return Ok(None), Element::None => return Ok(None),
Element::Rev(r) => return Ok(Some(r)), Element::Rev(r) => return Ok(Some(r)),
Element::Block(idx) => visit = idx, Element::Block(idx) => visit = idx,
} }
} }
Err(NodeMapError::MultipleResults) Err(NodeMapError::MultipleResults)
} }
} }
impl From<Vec<Block>> for NodeTree { impl From<Vec<Block>> for NodeTree {
fn from(vec: Vec<Block>) -> Self { fn from(vec: Vec<Block>) -> Self {
NodeTree { Self::new(Box::new(vec))
readonly: Box::new(vec),
}
} }
} }
impl fmt::Debug for NodeTree { impl fmt::Debug for NodeTree {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let blocks: &[Block] = &*self.readonly; let readonly: &[Block] = &*self.readonly;
write!(f, "readonly: {:?}", blocks) write!(
f,
"readonly: {:?}, growable: {:?}, root: {:?}",
readonly, self.growable, self.root
)
kevincoxUnsubmitted
Not Done

I would use https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_struct for consistency unless you really want to avoid printing the struct name.

kevincox: I would use https://doc.rust-lang.org/std/fmt/struct.Formatter.html#method.debug_struct for…
gracinetAuthorUnsubmitted
Done

sadly, Formatter.debug_struct doesn't tale ?Sized arguments (at least in our target 1.34 version):

   --> hg-core/src/revlog/nodemap.rs:298:32
    |
298 |             .field("readonly", readonly)
    |                                ^^^^^^^^ doesn't have a size known at compile-time
    |
    = help: the trait `std::marker::Sized` is not implemented for `[revlog::nodemap::Block]`

Kept it as it was for the time being, just dropped the unneeded anonymous lifetime

Omitting the struct name was indeed on purpose, to make it more manageable in test data. That was useful in early versions. I would have been willing to drop it for the final form. Anyone using this for real data wouldn't care about just a few bytes at the beginning.

gracinet: sadly, `Formatter.debug_struct` doesn't tale `?Sized` arguments (at least in our target 1.34…
} }
} }
impl NodeMap for NodeTree { impl NodeMap for NodeTree {
fn find_bin<'a>( fn find_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefixRef<'a>, prefix: NodePrefixRef<'a>,
} }
#[test] #[test]
fn test_nt_debug() { fn test_nt_debug() {
let nt = sample_nodetree(); let nt = sample_nodetree();
assert_eq!( assert_eq!(
format!("{:?}", nt), format!("{:?}", nt),
"readonly: \ "readonly: \
[{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]" [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \
growable: [], \
root: {0: Block(1), 1: Rev(1)}",
); );
} }
#[test] #[test]
fn test_immutable_find_simplest() -> Result<(), NodeMapError> { fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
let mut idx: TestIndex = HashMap::new(); let mut idx: TestIndex = HashMap::new();
pad_insert(&mut idx, 1, "1234deadcafe"); pad_insert(&mut idx, 1, "1234deadcafe");
let nt = NodeTree::from(vec![block![1: Rev(1)]]); let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
assert_eq!(nt.find_hex(&idx, "1")?, Some(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, "12")?, Some(1));
assert_eq!(nt.find_hex(&idx, "1234de")?, 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, "1a")?, None);
assert_eq!(nt.find_hex(&idx, "ab")?, None); assert_eq!(nt.find_hex(&idx, "ab")?, None);
// and with full binary Nodes // and with full binary Nodes
assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1)); assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1));
let nt = sample_nodetree(); let nt = sample_nodetree();
assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); 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, "01"), Ok(Some(9)));
assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0))); assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
} }
#[test]
fn test_mutated_find() -> Result<(), NodeMapError> {
let mut idx = TestIndex::new();
pad_insert(&mut idx, 9, "012");
pad_insert(&mut idx, 0, "00a");
pad_insert(&mut idx, 2, "cafe");
pad_insert(&mut idx, 3, "15");
pad_insert(&mut idx, 1, "10");
let nt = NodeTree {
readonly: sample_nodetree().readonly,
growable: vec![block![0: Rev(1), 5: Rev(3)]],
root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
};
assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
Ok(())
}
} }