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.

Download Raw Diff

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

Herald added a reviewer: hg-reviewers. · View Herald TranscriptJan 6 2020, 2:25 PM

Herald added subscribers: mercurial-devel, kevincox, durin42. · View Herald Transcript

gracinet added a child revision: D7791: rust-nodemap: NodeMap trait with simplest implementation.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).

@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?

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.

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

			Path	Packages
M			rust/hg-core/src/revlog.rs (2 lines)
M			rust/hg-core/src/revlog/node.rs (181 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	19039		Jan 6 2020, 2:25 PM	★	★
Diff 2	19630		Jan 27 2020, 10:49 AM	★	★
Diff 3	19643	rHG9896a8d0d3d27efb2d9d7bafff860fb308fb1bec	Dec 27 2019, 5:04 PM	★	★

Status	Author	Revision
Closed	marmoute	D8098 rust-nodemap: a method for full invalidation
Closed	marmoute	D8097 rust-nodemap: accounting for dead blocks
Closed	gracinet	D7819 rust-nodemap: core implementation for shortest
Closed	gracinet	D7798 rust-nodemap: special case for prefixes of NULL_NODE
Closed	gracinet	D7797 rust-nodemap: pure Rust example
Closed	gracinet	D7796 rust-nodemap: input/output primitives
Closed	gracinet	D7795 rust-nodemap: insert method
Closed	gracinet	D7794 rust-nodemap: generic NodeTreeVisitor
Closed	gracinet	D7793 rust-nodemap: mutable NodeTree data structure
Closed	gracinet	D7792 rust-nodemap: abstracting the indexing
Closed	gracinet	D7791 rust-nodemap: NodeMap trait with simplest implementation
Closed	gracinet	D7790 rust-node: handling binary Node prefix
Closed	gracinet	D7789 rust-revlog: a trait for the revlog index
Closed	gracinet	D7788 rust-node: binary Node ID and conversion utilities
Closed	gracinet	D7787 rust-nodemap: building blocks for nodetree structures

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(())
				}
	}			}