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
Lint
Lint Skipped
Unit
Unit Tests Skipped

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 (40 lines)

Diff 20027

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 16-ary radix tree that is //! This provides a variation on the 16-ary radix tree 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, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, node::NULL_NODE, Node, NodeError, NodePrefix, 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;
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())
/// ///
/// A `NodeTree` always has at least the mutable root block. /// A `NodeTree` always has at least the mutable root block.
#[allow(dead_code)] #[allow(dead_code)]
fn is_empty(&self) -> bool { fn is_empty(&self) -> bool {
false false
} }
/// 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 visit_item in self.visit(prefix) { for visit_item in self.visit(prefix) {
if let Some(opt) = visit_item.final_revision() { if let Some(opt) = visit_item.final_revision() {
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::{hex_pad_right, Node}; use crate::revlog::node::{hex_pad_right, 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,
} }