This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9864

rust: Remove hex parsing from the nodemap
ClosedPublic

Authored by SimonSapin on Jan 25 2021, 4:13 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG18a261b11b20: rust: Remove hex parsing from the nodemap
Summary

Separating concerns simplifies error types.

Diff Detail

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

Event Timeline

SimonSapin created this revision.Jan 25 2021, 4:13 PM
SimonSapin updated this revision to Diff 25352.Jan 28 2021, 2:39 PM
Alphare accepted this revision.Jan 29 2021, 6:53 AM
SimonSapin added a commit: rHG18a261b11b20: rust: Remove hex parsing from the nodemap.Feb 1 2021, 12:34 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG18a261b11b20: rust: Remove hex parsing from the nodemap (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 25246

rust/hg-core/examples/nodemap/main.rs

eprintln!("Nodemap constructed in RAM in {:?}", start.elapsed()); eprintln!("Nodemap constructed in RAM in {:?}", start.elapsed());
file.write(&nm.into_readonly_and_added_bytes().1)?; file.write(&nm.into_readonly_and_added_bytes().1)?;
eprintln!("Nodemap written to disk"); eprintln!("Nodemap written to disk");
Ok(()) Ok(())
} }
fn query(index: &Index, nm: &NodeTree, prefix: &str) { fn query(index: &Index, nm: &NodeTree, prefix: &str) {
let start = Instant::now(); let start = Instant::now();
let res = nm.find_hex(index, prefix); let res = NodePrefix::from_hex(prefix).map(|p| nm.find_bin(index, p));
println!("Result found in {:?}: {:?}", start.elapsed(), res); println!("Result found in {:?}: {:?}", start.elapsed(), res);
} }
fn bench(index: &Index, nm: &NodeTree, queries: usize) { fn bench(index: &Index, nm: &NodeTree, queries: usize) {
let len = index.len() as u32; let len = index.len() as u32;
let mut rng = rand::thread_rng(); let mut rng = rand::thread_rng();
let nodes: Vec<Node> = (0..queries) let nodes: Vec<Node> = (0..queries)
.map(|_| { .map(|_| {

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::NULL_NODE, FromHexError, Node, NodePrefix, Revision, RevlogIndex, node::NULL_NODE, Node, NodePrefix, Revision, RevlogIndex, NULL_REVISION,
NULL_REVISION,
}; };
use std::cmp::max; use std::cmp::max;
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)]
pub enum NodeMapError { pub enum NodeMapError {
MultipleResults, MultipleResults,
InvalidNodePrefix,
/// A `Revision` stored in the nodemap could not be found in the index /// A `Revision` stored in the nodemap could not be found in the index
RevisionNotInIndex(Revision), RevisionNotInIndex(Revision),
} }
impl From<FromHexError> for NodeMapError {
fn from(_: FromHexError) -> Self {
NodeMapError::InvalidNodePrefix
}
}
/// Mapping system from Mercurial nodes to revision numbers. /// Mapping system from Mercurial nodes to revision numbers.
/// ///
/// ## `RevlogIndex` and `NodeMap` /// ## `RevlogIndex` and `NodeMap`
/// ///
/// One way to think about their relationship is that /// One way to think about their relationship is that
/// the `NodeMap` is a prefix-oriented reverse index of the `Node` information /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
/// carried by a [`RevlogIndex`]. /// carried by a [`RevlogIndex`].
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn find_bin<'a>( fn find_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
prefix: NodePrefix, prefix: NodePrefix,
) -> Result<Option<Revision>, NodeMapError>; ) -> Result<Option<Revision>, NodeMapError>;
/// Find the unique Revision whose `Node` hexadecimal string representation
/// starts with a given prefix
///
/// If no Revision matches the given prefix, `Ok(None)` is returned.
///
/// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned.
fn find_hex(
&self,
idx: &impl RevlogIndex,
prefix: &str,
) -> Result<Option<Revision>, NodeMapError> {
self.find_bin(idx, NodePrefix::from_hex(prefix)?)
}
/// Give the size of the shortest node prefix that determines /// Give the size of the shortest node prefix that determines
/// the revision uniquely. /// the revision uniquely.
/// ///
/// From a binary node prefix, if it is matched in the node map, this /// From a binary node prefix, if it is matched in the node map, this
/// returns the number of hexadecimal digits that would had sufficed /// returns the number of hexadecimal digits that would had sufficed
/// to find the revision uniquely. /// to find the revision uniquely.
/// ///
/// Returns `None` if no `Revision` could be found for the prefix. /// Returns `None` if no `Revision` could be found for the prefix.
/// ///
/// If several Revisions match the given prefix, a [`MultipleResults`] /// If several Revisions match the given prefix, a [`MultipleResults`]
/// error is returned. /// error is returned.
fn unique_prefix_len_bin<'a>( fn unique_prefix_len_bin<'a>(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
node_prefix: NodePrefix, node_prefix: NodePrefix,
) -> Result<Option<usize>, NodeMapError>; ) -> Result<Option<usize>, NodeMapError>;
/// Same as `unique_prefix_len_bin`, with the hexadecimal representation
/// of the prefix as input.
fn unique_prefix_len_hex(
&self,
idx: &impl RevlogIndex,
prefix: &str,
) -> Result<Option<usize>, NodeMapError> {
self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?)
}
/// Same as `unique_prefix_len_bin`, with a full `Node` as input /// Same as `unique_prefix_len_bin`, with a full `Node` as input
fn unique_prefix_len_node( fn unique_prefix_len_node(
&self, &self,
idx: &impl RevlogIndex, idx: &impl RevlogIndex,
node: &Node, node: &Node,
) -> Result<Option<usize>, NodeMapError> { ) -> Result<Option<usize>, NodeMapError> {
self.unique_prefix_len_bin(idx, node.into()) self.unique_prefix_len_bin(idx, node.into())
} }
fn sample_nodetree() -> NodeTree { fn sample_nodetree() -> NodeTree {
NodeTree::from(vec![ NodeTree::from(vec![
block![0: Rev(9)], block![0: Rev(9)],
block![0: Rev(0), 1: Rev(9)], block![0: Rev(0), 1: Rev(9)],
block![0: Block(1), 1:Rev(1)], block![0: Block(1), 1:Rev(1)],
]) ])
} }
fn hex(s: &str) -> NodePrefix {
NodePrefix::from_hex(s).unwrap()
}
#[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: [], \ growable: [], \
root: {0: Block(1), 1: Rev(1)}", 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_bin(&idx, hex("1"))?, Some(1));
assert_eq!(nt.find_hex(&idx, "12")?, Some(1)); assert_eq!(nt.find_bin(&idx, hex("12"))?, Some(1));
assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1)); assert_eq!(nt.find_bin(&idx, hex("1234de"))?, Some(1));
assert_eq!(nt.find_hex(&idx, "1a")?, None); assert_eq!(nt.find_bin(&idx, hex("1a"))?, None);
assert_eq!(nt.find_hex(&idx, "ab")?, None); assert_eq!(nt.find_bin(&idx, hex("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 unknown = Node::from_hex(&hex_pad_right("3d")).unwrap(); let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap();
assert_eq!(nt.find_node(&idx, &unknown)?, None); assert_eq!(nt.find_node(&idx, &unknown)?, None);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_immutable_find_one_jump() { fn test_immutable_find_one_jump() {
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_bin(&idx, hex("0")), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); assert_eq!(nt.find_bin(&idx, hex("01")), Ok(Some(9)));
assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); assert_eq!(nt.find_bin(&idx, hex("00a")), Ok(Some(0)));
assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3))); assert_eq!(nt.unique_prefix_len_bin(&idx, hex("00a")), Ok(Some(3)));
assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION))); assert_eq!(nt.find_bin(&idx, hex("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)],
masked_inner_blocks: 1, masked_inner_blocks: 1,
}; };
assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); assert_eq!(nt.find_bin(&idx, hex("10"))?, Some(1));
assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); assert_eq!(nt.find_bin(&idx, hex("c"))?, Some(2));
assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1)); assert_eq!(nt.unique_prefix_len_bin(&idx, hex("c"))?, Some(1));
assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); assert_eq!(nt.find_bin(&idx, hex("00")), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION)); assert_eq!(nt.find_bin(&idx, hex("000"))?, Some(NULL_REVISION));
assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3)); assert_eq!(nt.unique_prefix_len_bin(&idx, hex("000"))?, Some(3));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); assert_eq!(nt.find_bin(&idx, hex("01"))?, Some(9));
assert_eq!(nt.masked_readonly_blocks(), 2); assert_eq!(nt.masked_readonly_blocks(), 2);
Ok(()) Ok(())
} }
struct TestNtIndex { struct TestNtIndex {
index: TestIndex, index: TestIndex,
nt: NodeTree, nt: NodeTree,
} }
self.nt.insert(&self.index, &node, rev)?; self.nt.insert(&self.index, &node, rev)?;
Ok(()) Ok(())
} }
fn find_hex( fn find_hex(
&self, &self,
prefix: &str, prefix: &str,
) -> Result<Option<Revision>, NodeMapError> { ) -> Result<Option<Revision>, NodeMapError> {
self.nt.find_hex(&self.index, prefix) self.nt.find_bin(&self.index, hex(prefix))
} }
fn unique_prefix_len_hex( fn unique_prefix_len_hex(
&self, &self,
prefix: &str, prefix: &str,
) -> Result<Option<usize>, NodeMapError> { ) -> Result<Option<usize>, NodeMapError> {
self.nt.unique_prefix_len_hex(&self.index, prefix) self.nt.unique_prefix_len_bin(&self.index, hex(prefix))
} }
/// Drain `added` and restart a new one /// Drain `added` and restart a new one
fn commit(self) -> Self { fn commit(self) -> Self {
let mut as_vec: Vec<Block> = let mut as_vec: Vec<Block> =
self.nt.readonly.iter().map(|block| block.clone()).collect(); self.nt.readonly.iter().map(|block| block.clone()).collect();
as_vec.extend(self.nt.growable); as_vec.extend(self.nt.growable);
as_vec.push(self.nt.root); as_vec.push(self.nt.root);

rust/hg-cpython/src/revlog.rs

use cpython::{ use cpython::{
buffer::{Element, PyBuffer}, buffer::{Element, PyBuffer},
exc::{IndexError, ValueError}, exc::{IndexError, ValueError},
ObjectProtocol, PyBytes, PyClone, PyDict, PyErr, PyModule, PyObject, ObjectProtocol, PyBytes, PyClone, PyDict, PyErr, PyModule, PyObject,
PyResult, PyString, PyTuple, Python, PythonObject, ToPyObject, PyResult, PyString, PyTuple, Python, PythonObject, ToPyObject,
}; };
use hg::{ use hg::{
nodemap::{Block, NodeMapError, NodeTree}, nodemap::{Block, NodeMapError, NodeTree},
revlog::{nodemap::NodeMap, RevlogIndex}, revlog::{nodemap::NodeMap, NodePrefix, RevlogIndex},
Revision, Revision,
}; };
use std::cell::RefCell; use std::cell::RefCell;
/// Return a Struct implementing the Graph trait /// Return a Struct implementing the Graph trait
pub(crate) fn pyindex_to_graph( pub(crate) fn pyindex_to_graph(
py: Python, py: Python,
index: PyObject, index: PyObject,
let node_as_string = if cfg!(feature = "python3-sys") { let node_as_string = if cfg!(feature = "python3-sys") {
node.cast_as::<PyString>(py)?.to_string(py)?.to_string() node.cast_as::<PyString>(py)?.to_string(py)?.to_string()
} }
else { else {
let node = node.extract::<PyBytes>(py)?; let node = node.extract::<PyBytes>(py)?;
String::from_utf8_lossy(node.data(py)).to_string() String::from_utf8_lossy(node.data(py)).to_string()
}; };
nt.find_hex(idx, &node_as_string) let prefix = NodePrefix::from_hex(&node_as_string).map_err(|_| PyErr::new::<ValueError, _>(py, "Invalid node or prefix"))?;
nt.find_bin(idx, prefix)
// TODO make an inner API returning the node directly // TODO make an inner API returning the node directly
.map(|opt| opt.map( .map(|opt| opt.map(
|rev| PyBytes::new(py, idx.node(rev).unwrap().as_bytes()))) |rev| PyBytes::new(py, idx.node(rev).unwrap().as_bytes())))
.map_err(|e| nodemap_error(py, e)) .map_err(|e| nodemap_error(py, e))
} }
/// append an index entry /// append an index entry
) )
} }
/// Standard treatment of NodeMapError /// Standard treatment of NodeMapError
fn nodemap_error(py: Python, err: NodeMapError) -> PyErr { fn nodemap_error(py: Python, err: NodeMapError) -> PyErr {
match err { match err {
NodeMapError::MultipleResults => revlog_error(py), NodeMapError::MultipleResults => revlog_error(py),
NodeMapError::RevisionNotInIndex(r) => rev_not_in_index(py, r), NodeMapError::RevisionNotInIndex(r) => rev_not_in_index(py, r),
NodeMapError::InvalidNodePrefix => {
PyErr::new::<ValueError, _>(py, "Invalid node or prefix")
}
} }
} }
/// Create the module, with __package__ given from parent /// Create the module, with __package__ given from parent
pub fn init_module(py: Python, package: &str) -> PyResult<PyModule> { pub fn init_module(py: Python, package: &str) -> PyResult<PyModule> {
let dotted_name = &format!("{}.revlog", package); let dotted_name = &format!("{}.revlog", package);
let m = PyModule::new(py, dotted_name)?; let m = PyModule::new(py, dotted_name)?;
m.add(py, "__package__", package)?; m.add(py, "__package__", package)?;