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
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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 25426

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 bytes_cast::{unaligned, BytesCast}; use bytes_cast::{unaligned, BytesCast};
use std::cmp::max; use std::cmp::max;
use std::fmt; use std::fmt;
use std::mem::{self, align_of, size_of}; use std::mem::{self, align_of, size_of};
use std::ops::Deref; use std::ops::Deref;
use std::ops::Index; use std::ops::Index;
#[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)?;