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

Branch

default

Lint

No Linters Available

Unit

No Unit Test Coverage

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
62–64	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
79	Why not use `(len + 1) / 2` as capacity?
89	Is this lifetime parameter needed?
136	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
79	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).
89	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.
136	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
103	The lifetime parameter doesn't seem to be used, so make it anonymous? (I.e., remove it from `impl` and use `<'_>` on the type.
146	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.

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
146	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
146	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 (147 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	★	★

Commit	Parents	Author	Summary	Date
9147c5620477	dfb7a59e6651	Georges Racinet		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 19039

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

	pub type Node = [u8; 20];			pub type Node = [u8; 20];

	/// The node value for NULL_REVISION			/// The node value for NULL_REVISION
	pub const NULL_NODE: Node = [0; 20];			pub const NULL_NODE: Node = [0; 20];

	#[derive(Debug, PartialEq)]			#[derive(Debug, PartialEq)]
	pub enum NodeError {			pub enum NodeError {
	ExactLengthRequired(String),			ExactLengthRequired(String),
				PrefixTooLong(String),
	NotHexadecimal,			NotHexadecimal,
	}			}

	pub fn node_from_hex(hex: &str) -> Result<Node, NodeError> {			pub fn node_from_hex(hex: &str) -> Result<Node, NodeError> {
	if hex.len() != 40 {			if hex.len() != 40 {
	return Err(NodeError::ExactLengthRequired(hex.to_string()));			return Err(NodeError::ExactLengthRequired(hex.to_string()));
	}			}
	let mut node = [0; 20];			let mut node = [0; 20];
	}			}

	impl From<ParseIntError> for NodeError {			impl From<ParseIntError> for NodeError {
	fn from(_: ParseIntError) -> Self {			fn from(_: ParseIntError) -> Self {
	NodeError::NotHexadecimal			NodeError::NotHexadecimal
	}			}
	}			}

				/// 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.
				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.
				#[derive(Debug, PartialEq)]
				pub struct NodePrefix {
				buf: Vec<u8>,
				is_odd: bool,
				}

				impl NodePrefix {
				/// Conversion from hexadecimal string representation
				pub fn from_hex(hex: &str) -> Result<Self, NodeError> {
				let len = hex.len();
				if len > 40 {
				return Err(NodeError::PrefixTooLong(hex.to_string()));
				}
				let is_odd = len % 2 == 1;
				let mut buf: Vec<u8> = Vec::with_capacity(20);
				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…
				for i in 0..len / 2 {
				buf.push(u8::from_str_radix(&hex[i * 2..i * 2 + 2], 16)?);
				}
				if is_odd {
				buf.push(u8::from_str_radix(&hex[len - 1..], 16)? << 4);
				}
				Ok(NodePrefix { buf, is_odd })
				}

				pub fn borrow<'a>(&'a self) -> NodePrefixRef<'a> {
				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…
				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> {
				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…
				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.starts_with(buf.split_at(last_pos).0)
				&& node[last_pos] >> 4 == buf[last_pos] >> 4
				} else {
				node.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(i, self.buf)
				}
				}

				/// A shortcut for full `Node` references
				impl<'a> From<&'a Node> for NodePrefixRef<'a> {
				fn from(node: &'a Node) -> Self {
				NodePrefixRef {
				buf: &*node,
				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.
				is_odd: false,
				}
				}
				}

	#[cfg(test)]			#[cfg(test)]
	mod tests {			mod tests {
	use super::*;			use super::*;

	const SAMPLE_NODE_HEX: &str = "0123456789abcdeffedcba9876543210deadbeef";			const SAMPLE_NODE_HEX: &str = "0123456789abcdeffedcba9876543210deadbeef";
				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…

	#[test]			#[test]
	fn test_node_from_hex() {			fn test_node_from_hex() {
	assert_eq!(			assert_eq!(
	node_from_hex(SAMPLE_NODE_HEX),			node_from_hex(SAMPLE_NODE_HEX),
	Ok([			Ok([
	0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc,			0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc,
	0xba, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef			0xba, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef
	assert_eq!(			assert_eq!(
	node_to_hex(&[			node_to_hex(&[
	0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc,			0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc,
	0xba, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef			0xba, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef
	]),			]),
	SAMPLE_NODE_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
				assert_eq!(
				NodePrefix::from_hex(SAMPLE_NODE_HEX)?,
				NodePrefix {
				buf: node_from_hex(SAMPLE_NODE_HEX)?.iter().cloned().collect(),
				is_odd: false
				}
				);

				Ok(())
				}

				#[test]
				fn test_prefix_from_hex_errors() {
				assert_eq!(
				NodePrefix::from_hex("testgr"),
				Err(NodeError::NotHexadecimal)
				);
				let long = "000000000000000000000000000000000000000000000";
				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: Node = [0; 20];
				node[0] = 0x12;
				node[1] = 0xca;
				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(())
				}
	}			}