This is an archive of the discontinued Mercurial Phabricator instance.

Differential D7790

rust-node: handling binary Node prefix
ClosedPublic

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

Details

Reviewers
martinvonz
Group Reviewers
hg-reviewers
Commits
rHG9896a8d0d3d2: rust-node: handling binary Node prefix
Summary

Parallel to the inner signatures of the nodetree functions in
revlog.c, we'll have to handle prefixes of Node in binary
form.

Another motivation is that it allows to convert from full Node
references to NodePrefixRef without copy. This is expected to
be by far the most common case in practice.

There's a slight complication due to the fact that we'll be sometimes
interested in prefixes with an odd number of hexadecimal digits,
which translates in binary form by a last byte in which only the
highest weight 4 bits are considered. This is totally transparent for
callers and could be revised once we have proper means to measure
performance.

The C implementation does the same, passing the length in nybbles as
function arguments. Because Rust byte slices already have a length, we carry
the even/odd informaton as a boolean, to avoid introducing logical
redundancies and the related potential inconsistency bugs.

There are a few candidates for inlining here, but we refrain from
such premature optimizations, letting the compiler decide.

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
martinvonz added a subscriber: martinvonz.Jan 17 2020, 11:16 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/node.rs
242–244

Did you consider using a full u8 for each nibble instead? It seems like that would be simpler. I'd appreciate it if you could spend a few minutes to try that (if you haven't already).

gracinet added a comment.Jan 20 2020, 8:25 AM

@martinvonz in this code, we're in competition with the C implementation, which does something similar.

Switching to a full u8 per nybble is more than a few minutes, it means changing the ownership model completely. Also, it introduces a new allocation and a copy instead of merely taking a reference.

So, it's more work and has performance impact that we have no means to measure.

The odd/even thing is not *that* complicated. It's very bad for readability in the C code, but it's nicely encapsulated in the Rust case and fully tested. I'd be more comfortable trying what you're suggesting once we have real-life measurements.

martinvonz added inline comments.Jan 21 2020, 12:55 PM
rust/hg-core/src/revlog/node.rs
259

Why not use (len + 1) / 2 as capacity?

269

Is this lifetime parameter needed?

316

What does the &* do? Specifically, what's different if you drop that part?

martinvonz added a comment.Jan 21 2020, 12:55 PM
In D7790#116757, @gracinet wrote:

@martinvonz in this code, we're in competition with the C implementation, which does something similar.
Switching to a full u8 per nybble is more than a few minutes, it means changing the ownership model completely. Also, it introduces a new allocation and a copy instead of merely taking a reference.

Depends on the definition of NodePrefixRef. I don't think there would be any extra allocation if you define it like this:

pub enum NodePrefixRef<'a> {
    Full(&'a Node),
    Prefix(&'a NodePrefix),
}

So, it's more work and has performance impact that we have no means to measure.
The odd/even thing is not *that* complicated. It's very bad for readability in the C code, but it's nicely encapsulated in the Rust case and fully tested. I'd be more comfortable trying what you're suggesting once we have real-life measurements.

Sure, please revisit it when you can do measurements.

gracinet edited the summary of this revision. (Show Details)Jan 27 2020, 10:49 AM
gracinet updated this revision to Diff 19630.
gracinet added a comment.Jan 27 2020, 10:51 AM

Depends on the definition of NodePrefixRef. I don't think there would be any extra allocation if you define it like this:

pub enum NodePrefixRef<'a> {
    Full(&'a Node),
    Prefix(&'a NodePrefix),
}

That's an interesting idea, another possibility would be to define a trait (essentially for get_nybble) and implement it for &Node and &NodePrefix. We'll see when we're pass preliminary tests, thanks.

rust/hg-core/src/revlog/node.rs
259

Just thought 20 would be the simplest one-size-fit-all. With the preparations for different hash length (and potentially even somewhat dynamic), it's really obsolete now (switched to actual len based, yes).

269

ah yes indeed the compiler seems to be able to infer that &self and Nodeprefix.buf have the same lifteime, and that it must then be equal to the lifetime parameter of NodePrefix itself.

316

These are conversions that need to be explicit when the compiler doesn't insert them magically. Usually, I try to avoid them, but it can happen that they become non necessary in the final form after some changes.

Not needed in the new form with a real struct.

martinvonz accepted this revision.Jan 27 2020, 1:24 PM
martinvonz added inline comments.
rust/hg-core/src/revlog/node.rs
226

Should we check here that i < self.len()? I'm especially thinking of the case of an odd-length prefix where we would otherwise silently return 0.

283

The lifetime parameter doesn't seem to be used, so make it anonymous? (I.e., remove it from impl and use <'_> on the type.

This revision is now accepted and ready to land.Jan 27 2020, 1:24 PM
gracinet added a commit: rHG9896a8d0d3d2: rust-node: handling binary Node prefix.Jan 27 2020, 1:36 PM
Closed by commit rHG9896a8d0d3d2: rust-node: handling binary Node prefix (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.
gracinet added inline comments.Jan 27 2020, 2:04 PM
rust/hg-core/src/revlog/node.rs
226

yes, indeed.

current callers from nodemap work either on full Nodes or (the visitor) by explicitely bounding with prefix.len(), but it's safer to protect it inconditonally.

I think a simple assert! is enough though: that's already what slicing does anyway.

martinvonz added inline comments.Jan 27 2020, 2:09 PM
rust/hg-core/src/revlog/node.rs
226

Yes, an assert! is probably what I had in mind. I've already queued this, so please send in a follow-up.

Revision Contents
Changeset List

Diff 19643

rust/hg-core/src/revlog.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.
//! Mercurial concepts for handling revision history //! Mercurial concepts for handling revision history
pub mod node; pub mod node;
pub mod nodemap; pub mod nodemap;
pub use node::{Node, NodeError}; pub use node::{Node, NodeError, NodePrefix, NodePrefixRef};
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
/// As noted in revlog.c, revision numbers are actually encoded in /// As noted in revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32 /// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32; pub type Revision = i32;
/// Marker expressing the absence of a parent /// Marker expressing the absence of a parent

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

fn from(data: NodeData) -> Node { fn from(data: NodeData) -> Node {
Node { data } Node { data }
} }
} }
#[derive(Debug, PartialEq)] #[derive(Debug, PartialEq)]
pub enum NodeError { pub enum NodeError {
ExactLengthRequired(usize, String), ExactLengthRequired(usize, String),
PrefixTooLong(String),
HexError(FromHexError, String), HexError(FromHexError, String),
} }
/// Low level utility function, also for prefixes /// Low level utility function, also for prefixes
fn get_nybble(s: &[u8], i: usize) -> u8 { fn get_nybble(s: &[u8], i: usize) -> u8 {
if i % 2 == 0 { if i % 2 == 0 {
s[i / 2] >> 4 s[i / 2] >> 4
} else { } else {
/// ///
/// This is needed by FFI layers, for instance to return expected /// This is needed by FFI layers, for instance to return expected
/// binary values to Python. /// binary values to Python.
pub fn as_bytes(&self) -> &[u8] { pub fn as_bytes(&self) -> &[u8] {
&self.data &self.data
} }
} }
impl From<(FromHexError, &str)> for NodeError { impl<T: AsRef<str>> From<(FromHexError, T)> for NodeError {
fn from(err_offender: (FromHexError, &str)) -> Self { fn from(err_offender: (FromHexError, T)) -> Self {
let (err, offender) = err_offender; let (err, offender) = err_offender;
match err { match err {
FromHexError::InvalidStringLength => { FromHexError::InvalidStringLength => {
NodeError::ExactLengthRequired( NodeError::ExactLengthRequired(
NODE_NYBBLES_LENGTH, NODE_NYBBLES_LENGTH,
offender.to_string(), offender.as_ref().to_owned(),
) )
} }
_ => NodeError::HexError(err, offender.to_string()), _ => NodeError::HexError(err, offender.as_ref().to_owned()),
}
}
}
/// The beginning of a binary revision SHA.
///
/// Since it can potentially come from an hexadecimal representation with
/// odd length, it needs to carry around whether the last 4 bits are relevant
/// or not.
#[derive(Debug, PartialEq)]
pub struct NodePrefix {
buf: Vec<u8>,
is_odd: bool,
}
impl NodePrefix {
/// Convert from hexadecimal string representation
///
/// Similarly to `hex::decode`, can be used with Unicode string types
/// (`String`, `&str`) as well as bytes.
///
/// To be used in FFI and I/O only, in order to facilitate future
/// changes of hash format.
pub fn from_hex(hex: impl AsRef<[u8]>) -> Result<Self, NodeError> {
let hex = hex.as_ref();
let len = hex.len();
if len > NODE_NYBBLES_LENGTH {
return Err(NodeError::PrefixTooLong(
String::from_utf8_lossy(hex).to_owned().to_string(),
));
}
let is_odd = len % 2 == 1;
let even_part = if is_odd { &hex[..len - 1] } else { hex };
let mut buf: Vec<u8> = Vec::from_hex(&even_part)
.map_err(|e| (e, String::from_utf8_lossy(hex)))?;
if is_odd {
let latest_char = char::from(hex[len - 1]);
let latest_nybble = latest_char.to_digit(16).ok_or_else(|| {
(
FromHexError::InvalidHexCharacter {
c: latest_char,
index: len - 1,
},
String::from_utf8_lossy(hex),
)
})? as u8;
buf.push(latest_nybble << 4);
}
Ok(NodePrefix { buf, is_odd })
}
pub fn borrow(&self) -> NodePrefixRef {
NodePrefixRef {
buf: &self.buf,
is_odd: self.is_odd,
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct NodePrefixRef<'a> {
buf: &'a [u8],
is_odd: bool,
}
impl<'a> NodePrefixRef<'a> {
pub fn len(&self) -> usize {
if self.is_odd {
self.buf.len() * 2 - 1
} else {
self.buf.len() * 2
}
}
pub fn is_prefix_of(&self, node: &Node) -> bool {
if self.is_odd {
let buf = self.buf;
let last_pos = buf.len() - 1;
node.data.starts_with(buf.split_at(last_pos).0)
&& node.data[last_pos] >> 4 == buf[last_pos] >> 4
} else {
node.data.starts_with(self.buf)
}
}
/// Retrieve the `i`th half-byte from the prefix.
///
/// This is also the `i`th hexadecimal digit in numeric form,
/// also called a [nybble](https://en.wikipedia.org/wiki/Nibble).
pub fn get_nybble(&self, i: usize) -> u8 {
get_nybble(self.buf, i)
martinvonzUnsubmitted
Not Done

Should we check here that i < self.len()? I'm especially thinking of the case of an odd-length prefix where we would otherwise silently return 0.

martinvonz: Should we check here that `i < self.len()`? I'm especially thinking of the case of an odd…
gracinetAuthorUnsubmitted
Done

yes, indeed.

current callers from nodemap work either on full Nodes or (the visitor) by explicitely bounding with prefix.len(), but it's safer to protect it inconditonally.

I think a simple assert! is enough though: that's already what slicing does anyway.

gracinet: yes, indeed. current callers from `nodemap` work either on full Nodes or (the visitor) by…
martinvonzUnsubmitted
Not Done

Yes, an assert! is probably what I had in mind. I've already queued this, so please send in a follow-up.

martinvonz: Yes, an `assert!` is probably what I had in mind. I've already queued this, so please send in a…
}
}
/// A shortcut for full `Node` references
impl<'a> From<&'a Node> for NodePrefixRef<'a> {
fn from(node: &'a Node) -> Self {
NodePrefixRef {
buf: &node.data,
is_odd: false,
} }
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
fn sample_node() -> Node { fn sample_node() -> Node {
martinvonzUnsubmitted
Not Done

Did you consider using a full u8 for each nibble instead? It seems like that would be simpler. I'd appreciate it if you could spend a few minutes to try that (if you haven't already).

martinvonz: Did you consider using a full u8 for each nibble instead? It seems like that would be simpler.
let mut data = [0; NODE_BYTES_LENGTH]; let mut data = [0; NODE_BYTES_LENGTH];
data.copy_from_slice(&[ data.copy_from_slice(&[
0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba,
0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef,
]); ]);
data.into() data.into()
} }
/// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH`
/// ///
/// The padding is made with zeros /// The padding is made with zeros
fn hex_pad_right(hex: &str) -> String { fn hex_pad_right(hex: &str) -> String {
let mut res = hex.to_string(); let mut res = hex.to_string();
while res.len() < NODE_NYBBLES_LENGTH { while res.len() < NODE_NYBBLES_LENGTH {
res.push('0'); res.push('0');
martinvonzUnsubmitted
Not Done

Why not use (len + 1) / 2 as capacity?

martinvonz: Why not use `(len + 1) / 2` as capacity?
gracinetAuthorUnsubmitted
Done

Just thought 20 would be the simplest one-size-fit-all. With the preparations for different hash length (and potentially even somewhat dynamic), it's really obsolete now (switched to actual len based, yes).

gracinet: Just thought 20 would be the simplest one-size-fit-all. With the preparations for different…
} }
res res
} }
fn sample_node_hex() -> String { fn sample_node_hex() -> String {
hex_pad_right("0123456789abcdeffedcba9876543210deadbeef") hex_pad_right("0123456789abcdeffedcba9876543210deadbeef")
} }
#[test] #[test]
fn test_node_from_hex() { fn test_node_from_hex() {
martinvonzUnsubmitted
Not Done

Is this lifetime parameter needed?

martinvonz: Is this lifetime parameter needed?
gracinetAuthorUnsubmitted
Done

ah yes indeed the compiler seems to be able to infer that &self and Nodeprefix.buf have the same lifteime, and that it must then be equal to the lifetime parameter of NodePrefix itself.

gracinet: ah yes indeed the compiler seems to be able to infer that `&self` and `Nodeprefix.buf` have the…
assert_eq!(Node::from_hex(&sample_node_hex()), Ok(sample_node())); assert_eq!(Node::from_hex(&sample_node_hex()), Ok(sample_node()));
let mut short = hex_pad_right("0123"); let mut short = hex_pad_right("0123");
short.pop(); short.pop();
short.pop(); short.pop();
assert_eq!( assert_eq!(
Node::from_hex(&short), Node::from_hex(&short),
Err(NodeError::ExactLengthRequired(NODE_NYBBLES_LENGTH, short)), Err(NodeError::ExactLengthRequired(NODE_NYBBLES_LENGTH, short)),
); );
let not_hex = hex_pad_right("012... oops"); let not_hex = hex_pad_right("012... oops");
assert_eq!( assert_eq!(
Node::from_hex(&not_hex), Node::from_hex(&not_hex),
Err(NodeError::HexError( Err(NodeError::HexError(
martinvonzUnsubmitted
Not Done

The lifetime parameter doesn't seem to be used, so make it anonymous? (I.e., remove it from impl and use <'_> on the type.

martinvonz: The lifetime parameter doesn't seem to be used, so make it anonymous? (I.e., remove it from…
FromHexError::InvalidHexCharacter { c: '.', index: 3 }, FromHexError::InvalidHexCharacter { c: '.', index: 3 },
not_hex, not_hex,
)), )),
); );
} }
#[test] #[test]
fn test_node_encode_hex() { fn test_node_encode_hex() {
assert_eq!(sample_node().encode_hex(), sample_node_hex()); assert_eq!(sample_node().encode_hex(), sample_node_hex());
} }
#[test]
fn test_prefix_from_hex() -> Result<(), NodeError> {
assert_eq!(
NodePrefix::from_hex("0e1")?,
NodePrefix {
buf: vec![14, 16],
is_odd: true
}
);
assert_eq!(
NodePrefix::from_hex("0e1a")?,
NodePrefix {
buf: vec![14, 26],
is_odd: false
}
);
// checking limit case
let node_as_vec = sample_node().data.iter().cloned().collect();
assert_eq!(
NodePrefix::from_hex(sample_node_hex())?,
NodePrefix {
martinvonzUnsubmitted
Not Done

What does the &* do? Specifically, what's different if you drop that part?

martinvonz: What does the `&*` do? Specifically, what's different if you drop that part?
gracinetAuthorUnsubmitted
Done

These are conversions that need to be explicit when the compiler doesn't insert them magically. Usually, I try to avoid them, but it can happen that they become non necessary in the final form after some changes.

Not needed in the new form with a real struct.

gracinet: These are conversions that need to be explicit when the compiler doesn't insert them magically.
buf: node_as_vec,
is_odd: false
}
);
Ok(())
}
#[test]
fn test_prefix_from_hex_errors() {
assert_eq!(
NodePrefix::from_hex("testgr"),
Err(NodeError::HexError(
FromHexError::InvalidHexCharacter { c: 't', index: 0 },
"testgr".to_string()
))
);
let mut long = NULL_NODE.encode_hex();
long.push('c');
match NodePrefix::from_hex(&long)
.expect_err("should be refused as too long")
{
NodeError::PrefixTooLong(s) => assert_eq!(s, long),
err => panic!(format!("Should have been TooLong, got {:?}", err)),
}
}
#[test]
fn test_is_prefix_of() -> Result<(), NodeError> {
let mut node_data = [0; NODE_BYTES_LENGTH];
node_data[0] = 0x12;
node_data[1] = 0xca;
let node = Node::from(node_data);
assert!(NodePrefix::from_hex("12")?.borrow().is_prefix_of(&node));
assert!(!NodePrefix::from_hex("1a")?.borrow().is_prefix_of(&node));
assert!(NodePrefix::from_hex("12c")?.borrow().is_prefix_of(&node));
assert!(!NodePrefix::from_hex("12d")?.borrow().is_prefix_of(&node));
Ok(())
}
#[test]
fn test_get_nybble() -> Result<(), NodeError> {
let prefix = NodePrefix::from_hex("dead6789cafe")?;
assert_eq!(prefix.borrow().get_nybble(0), 13);
assert_eq!(prefix.borrow().get_nybble(7), 9);
Ok(())
}
} }