This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7798

rust-nodemap: special case for prefixes of NULL_NODE
ClosedPublic

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

Details

Reviewers
kevincox
marmoute
Group Reviewers
hg-reviewers
Commits
rHG00d251d32007: rust-nodemap: special case for prefixes of NULL_NODE
rHG895934342631: rust-nodemap: special case for prefixes of NULL_NODE
Summary

We have to behave as though NULL_NODE was stored in the node tree,
although we don't store it.

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

gracinet created this revision.Jan 6 2020, 2:26 PM
gracinet updated this revision to Diff 19330.Jan 15 2020, 6:48 PM
kevincox accepted this revision.Jan 16 2020, 7:16 AM
gracinet updated this revision to Diff 19638.Jan 27 2020, 10:50 AM
marmoute accepted this revision.Feb 7 2020, 2:51 PM
marmoute added a subscriber: marmoute.

looks good to me too.

marmoute updated this revision to Diff 20027.Feb 8 2020, 12:45 PM
Alphare updated this revision to Diff 20217.Feb 14 2020, 6:02 AM
Alphare updated this revision to Diff 20236.Feb 15 2020, 6:49 AM
Alphare updated this revision to Diff 20282.Feb 24 2020, 8:15 AM
gracinet added a commit: rHG895934342631: rust-nodemap: special case for prefixes of NULL_NODE.Feb 26 2020, 10:33 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG895934342631: rust-nodemap: special case for prefixes of NULL_NODE (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 (42 lines)

Diff 19138

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

// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors // and Mercurial contributors
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Indexing facilities for fast retrieval of `Revision` from `Node` //! Indexing facilities for fast retrieval of `Revision` from `Node`
//! //!
//! This provides a variation on the radix tree with valency 16 that is //! This provides a variation on the radix tree with valency 16 that is
//! provided as "nodetree" in revlog.c, ready for append-only persistence //! provided as "nodetree" in revlog.c, ready for append-only persistence
//! on disk. //! on disk.
//! //!
//! Following existing implicit conventions, the "nodemap" terminology //! Following existing implicit conventions, the "nodemap" terminology
//! is used in a more abstract context. //! is used in a more abstract context.
use super::{ use super::{
node::get_nybble, Node, NodeError, NodePrefix, NodePrefixRef, Revision, node::get_nybble, node::NULL_NODE, Node, NodeError, NodePrefix,
RevlogIndex, NodePrefixRef, Revision, RevlogIndex, NULL_REVISION,
}; };
use std::fmt; use std::fmt;
use std::mem; use std::mem;
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index; use std::ops::Index;
use std::slice; use std::slice;
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
if prefix.is_prefix_of(node) { if prefix.is_prefix_of(node) {
Some(rev) Some(rev)
} else { } else {
None None
} }
}) })
} }
/// validate that the candidate's node starts indeed with given prefix,
/// and treat ambiguities related to `NULL_REVISION`.
///
/// From the data in the NodeTree, one can only conclude that some
/// revision is the only one for a *subprefix* of the one being looked up.
fn validate_candidate<'p>(
idx: &impl RevlogIndex,
prefix: NodePrefixRef<'p>,
rev: Option<Revision>,
) -> Result<Option<Revision>, NodeMapError> {
if prefix.is_prefix_of(&NULL_NODE) {
// NULL_REVISION always matches a prefix made only of zeros
// and any other *valid* result is an ambiguity
match rev {
None => Ok(Some(NULL_REVISION)),
Some(r) => match has_prefix_or_none(idx, prefix, r)? {
None => Ok(Some(NULL_REVISION)),
_ => Err(NodeMapError::MultipleResults),
},
}
} else {
rev.map_or(Ok(None), |r| has_prefix_or_none(idx, prefix, r))
}
}
impl NodeTree { impl NodeTree {
/// Initiate a NodeTree from an immutable slice-like of `Block` /// Initiate a NodeTree from an immutable slice-like of `Block`
/// ///
/// We keep `readonly` and clone its root block if it isn't empty. /// We keep `readonly` and clone its root block if it isn't empty.
fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
let root = readonly let root = readonly
.last() .last()
.map(|b| b.clone()) .map(|b| b.clone())
} }
/// Total number of blocks /// Total number of blocks
fn len(&self) -> usize { fn len(&self) -> usize {
self.readonly.len() + self.growable.len() + 1 self.readonly.len() + self.growable.len() + 1
} }
/// Main working method for `NodeTree` searches /// Main working method for `NodeTree` searches
///
/// 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> {
for (leaf, _, _, opt) in self.visit(prefix) { for (leaf, _, _, opt) in self.visit(prefix) {
if leaf { if leaf {
return Ok(opt); return Ok(opt);
} }
} }
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>,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
self.lookup(prefix.clone()).and_then(|opt| { validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev))
})
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::NodeMapError::*; use super::NodeMapError::*;
use super::*; use super::*;
use crate::revlog::node::{node_from_hex, Node}; use crate::revlog::node::{node_from_hex, Node};
let mut idx = TestIndex::new(); let mut idx = TestIndex::new();
pad_insert(&mut idx, 9, "012"); pad_insert(&mut idx, 9, "012");
pad_insert(&mut idx, 0, "00a"); pad_insert(&mut idx, 0, "00a");
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"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
} }
#[test] #[test]
fn test_mutated_find() -> Result<(), NodeMapError> { fn test_mutated_find() -> Result<(), NodeMapError> {
let mut idx = TestIndex::new(); let mut idx = TestIndex::new();
pad_insert(&mut idx, 9, "012"); pad_insert(&mut idx, 9, "012");
pad_insert(&mut idx, 0, "00a"); pad_insert(&mut idx, 0, "00a");
pad_insert(&mut idx, 2, "cafe"); pad_insert(&mut idx, 2, "cafe");
pad_insert(&mut idx, 3, "15"); pad_insert(&mut idx, 3, "15");
pad_insert(&mut idx, 1, "10"); pad_insert(&mut idx, 1, "10");
let nt = NodeTree { let nt = NodeTree {
readonly: sample_nodetree().readonly, readonly: sample_nodetree().readonly,
growable: vec![block![0: Rev(1), 5: Rev(3)]], growable: vec![block![0: Rev(1), 5: Rev(3)]],
root: block![0: Block(1), 1:Block(3), 12: Rev(2)], 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, "10")?, Some(1));
assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
assert_eq!(nt.find_hex(&idx, "00")?, Some(0)); assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
Ok(()) Ok(())
} }
struct TestNtIndex { struct TestNtIndex {
index: TestIndex, index: TestIndex,
nt: NodeTree, nt: NodeTree,
} }