D7790: rust-node: handling binary Node prefix
gracinet (Georges Racinet)
phabricator at mercurial-scm.org
Mon Jan 6 19:25:46 UTC 2020
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.
REVISION SUMMARY
Parallel to the inner signatures of the nodetree functions in
revlog.c, we'll have to handle prefixes of `Node` in binary
form.
There's a 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.
There are a few candidates for inlining here, but we refrain from
such premature optimizations, letting the compiler decide.
REPOSITORY
rHG Mercurial
BRANCH
default
REVISION DETAIL
https://phab.mercurial-scm.org/D7790
AFFECTED FILES
rust/hg-core/src/revlog.rs
rust/hg-core/src/revlog/node.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/node.rs b/rust/hg-core/src/revlog/node.rs
--- a/rust/hg-core/src/revlog/node.rs
+++ b/rust/hg-core/src/revlog/node.rs
@@ -19,6 +19,7 @@
#[derive(Debug, PartialEq)]
pub enum NodeError {
ExactLengthRequired(String),
+ PrefixTooLong(String),
NotHexadecimal,
}
@@ -56,6 +57,88 @@
}
}
+/// 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 {
+ /// 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);
+ 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> {
+ 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.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,
+ is_odd: false,
+ }
+ }
+}
+
#[cfg(test)]
mod tests {
use super::*;
@@ -88,4 +171,68 @@
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(())
+ }
}
diff --git a/rust/hg-core/src/revlog.rs b/rust/hg-core/src/revlog.rs
--- a/rust/hg-core/src/revlog.rs
+++ b/rust/hg-core/src/revlog.rs
@@ -7,7 +7,7 @@
pub mod node;
pub mod nodemap;
-pub use node::{Node, NodeError};
+pub use node::{Node, NodeError, NodePrefix, NodePrefixRef};
/// Mercurial revision numbers
///
To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
More information about the Mercurial-devel
mailing list