diff -r b84c3d43ff2e -r 645ee7225fab rust/hg-core/src/revlog/node.rs --- a/rust/hg-core/src/revlog/node.rs Sat Jan 30 18:30:11 2021 +0800 +++ b/rust/hg-core/src/revlog/node.rs Mon Jan 25 11:48:47 2021 +0100 @@ -9,8 +9,7 @@ //! of a revision. use bytes_cast::BytesCast; -use hex::{self, FromHex}; -use std::convert::TryFrom; +use std::convert::{TryFrom, TryInto}; use std::fmt; /// The length in bytes of a `Node` @@ -50,7 +49,7 @@ /// the size or return an error at runtime. /// /// [`nybbles_len`]: #method.nybbles_len -#[derive(Clone, Debug, PartialEq, BytesCast)] +#[derive(Copy, Clone, Debug, PartialEq, BytesCast)] #[repr(transparent)] pub struct Node { data: NodeData, @@ -72,7 +71,7 @@ type Error = (); #[inline] - fn try_from(bytes: &'a [u8]) -> Result<&'a Node, Self::Error> { + fn try_from(bytes: &'a [u8]) -> Result { match Node::from_bytes(bytes) { Ok((node, rest)) if rest.is_empty() => Ok(node), _ => Err(()), @@ -80,6 +79,17 @@ } } +/// Return an error if the slice has an unexpected length +impl TryFrom<&'_ [u8]> for Node { + type Error = std::array::TryFromSliceError; + + #[inline] + fn try_from(bytes: &'_ [u8]) -> Result { + let data = bytes.try_into()?; + Ok(Self { data }) + } +} + impl fmt::LowerHex for Node { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { for &byte in &self.data { @@ -124,9 +134,12 @@ /// 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 { - Ok(NodeData::from_hex(hex.as_ref()) - .map_err(|_| FromHexError)? - .into()) + let prefix = NodePrefix::from_hex(hex)?; + if prefix.nybbles_len() == NODE_NYBBLES_LENGTH { + Ok(Self { data: prefix.data }) + } else { + Err(FromHexError) + } } /// Provide access to binary data @@ -143,10 +156,14 @@ /// 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)] +#[derive(Debug, PartialEq, Copy, Clone)] pub struct NodePrefix { - buf: Vec, - is_odd: bool, + /// In `1..=NODE_NYBBLES_LENGTH` + nybbles_len: u8, + /// The first `4 * length_in_nybbles` bits are used (considering bits + /// within a bytes in big-endian: most significant first), the rest + /// are zero. + data: NodeData, } impl NodePrefix { @@ -164,52 +181,35 @@ return Err(FromHexError); } - let is_odd = len % 2 == 1; - let even_part = if is_odd { &hex[..len - 1] } else { hex }; - let mut buf: Vec = - Vec::from_hex(&even_part).map_err(|_| FromHexError)?; - - if is_odd { - let latest_char = char::from(hex[len - 1]); - let latest_nybble = - latest_char.to_digit(16).ok_or_else(|| FromHexError)? as u8; - buf.push(latest_nybble << 4); + let mut data = [0; NODE_BYTES_LENGTH]; + let mut nybbles_len = 0; + for &ascii_byte in hex { + let nybble = match char::from(ascii_byte).to_digit(16) { + Some(digit) => digit as u8, + None => return Err(FromHexError), + }; + // Fill in the upper half of a byte first, then the lower half. + let shift = if nybbles_len % 2 == 0 { 4 } else { 0 }; + data[nybbles_len as usize / 2] |= nybble << shift; + nybbles_len += 1; } - Ok(NodePrefix { buf, is_odd }) + Ok(Self { data, nybbles_len }) } - 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 nybbles_len(&self) -> usize { + self.nybbles_len as _ } 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) + let full_bytes = self.nybbles_len() / 2; + if self.data[..full_bytes] != node.data[..full_bytes] { + return false; } + if self.nybbles_len() % 2 == 0 { + return true; + } + let last = self.nybbles_len() - 1; + self.get_nybble(last) == node.get_nybble(last) } /// Retrieve the `i`th half-byte from the prefix. @@ -217,8 +217,12 @@ /// 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 { - assert!(i < self.len()); - get_nybble(self.buf, i) + assert!(i < self.nybbles_len()); + get_nybble(&self.data, i) + } + + fn iter_nybbles(&self) -> impl Iterator + '_ { + (0..self.nybbles_len()).map(move |i| get_nybble(&self.data, i)) } /// Return the index first nybble that's different from `node` @@ -229,42 +233,49 @@ /// /// Returned index is as in `get_nybble`, i.e., starting at 0. pub fn first_different_nybble(&self, node: &Node) -> Option { - let buf = self.buf; - let until = if self.is_odd { - buf.len() - 1 - } else { - buf.len() - }; - for (i, item) in buf.iter().enumerate().take(until) { - if *item != node.data[i] { - return if *item & 0xf0 == node.data[i] & 0xf0 { - Some(2 * i + 1) - } else { - Some(2 * i) - }; - } + self.iter_nybbles() + .zip(NodePrefix::from(*node).iter_nybbles()) + .position(|(a, b)| a != b) + } +} + +impl fmt::LowerHex for NodePrefix { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let full_bytes = self.nybbles_len() / 2; + for &byte in &self.data[..full_bytes] { + write!(f, "{:02x}", byte)? } - if self.is_odd && buf[until] & 0xf0 != node.data[until] & 0xf0 { - Some(until * 2) - } else { - None + if self.nybbles_len() % 2 == 1 { + let last = self.nybbles_len() - 1; + write!(f, "{:x}", self.get_nybble(last))? + } + Ok(()) + } +} + +/// A shortcut for full `Node` references +impl From<&'_ Node> for NodePrefix { + fn from(node: &'_ Node) -> Self { + NodePrefix { + nybbles_len: node.nybbles_len() as _, + data: node.data, } } } /// 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, +impl From for NodePrefix { + fn from(node: Node) -> Self { + NodePrefix { + nybbles_len: node.nybbles_len() as _, + data: node.data, } } } -impl PartialEq for NodePrefixRef<'_> { +impl PartialEq for NodePrefix { fn eq(&self, other: &Node) -> bool { - !self.is_odd && self.buf == other.data + Self::from(*other) == *self } } @@ -272,18 +283,16 @@ mod tests { use super::*; - fn sample_node() -> Node { - let mut data = [0; NODE_BYTES_LENGTH]; - data.copy_from_slice(&[ + const SAMPLE_NODE_HEX: &str = "0123456789abcdeffedcba9876543210deadbeef"; + const SAMPLE_NODE: Node = Node { + data: [ 0x01, 0x23, 0x45, 0x67, 0x89, 0xab, 0xcd, 0xef, 0xfe, 0xdc, 0xba, 0x98, 0x76, 0x54, 0x32, 0x10, 0xde, 0xad, 0xbe, 0xef, - ]); - data.into() - } + ], + }; /// Pad an hexadecimal string to reach `NODE_NYBBLES_LENGTH` - ///check_hash - /// The padding is made with zeros + /// The padding is made with zeros. pub fn hex_pad_right(hex: &str) -> String { let mut res = hex.to_string(); while res.len() < NODE_NYBBLES_LENGTH { @@ -292,55 +301,30 @@ res } - fn sample_node_hex() -> String { - hex_pad_right("0123456789abcdeffedcba9876543210deadbeef") - } - #[test] fn test_node_from_hex() { - assert_eq!(Node::from_hex(&sample_node_hex()).unwrap(), sample_node()); - - let mut short = hex_pad_right("0123"); - short.pop(); - short.pop(); - assert!(Node::from_hex(&short).is_err()); - - let not_hex = hex_pad_right("012... oops"); - assert!(Node::from_hex(¬_hex).is_err(),); + let not_hex = "012... oops"; + let too_short = "0123"; + let too_long = format!("{}0", SAMPLE_NODE_HEX); + assert_eq!(Node::from_hex(SAMPLE_NODE_HEX).unwrap(), SAMPLE_NODE); + assert!(Node::from_hex(not_hex).is_err()); + assert!(Node::from_hex(too_short).is_err()); + assert!(Node::from_hex(&too_long).is_err()); } #[test] fn test_node_encode_hex() { - assert_eq!(format!("{:x}", sample_node()), sample_node_hex()); + assert_eq!(format!("{:x}", SAMPLE_NODE), SAMPLE_NODE_HEX); } #[test] - fn test_prefix_from_hex() -> Result<(), FromHexError> { - assert_eq!( - NodePrefix::from_hex("0e1")?, - NodePrefix { - buf: vec![14, 16], - is_odd: true - } - ); + fn test_prefix_from_to_hex() -> Result<(), FromHexError> { + assert_eq!(format!("{:x}", NodePrefix::from_hex("0e1")?), "0e1"); + assert_eq!(format!("{:x}", NodePrefix::from_hex("0e1a")?), "0e1a"); assert_eq!( - NodePrefix::from_hex("0e1a")?, - NodePrefix { - buf: vec![14, 26], - is_odd: false - } + format!("{:x}", NodePrefix::from_hex(SAMPLE_NODE_HEX)?), + SAMPLE_NODE_HEX ); - - // checking limit case - let node_as_vec = sample_node().data.iter().cloned().collect(); - assert_eq!( - NodePrefix::from_hex(sample_node_hex())?, - NodePrefix { - buf: node_as_vec, - is_odd: false - } - ); - Ok(()) } @@ -358,49 +342,47 @@ 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)); + assert!(NodePrefix::from_hex("12")?.is_prefix_of(&node)); + assert!(!NodePrefix::from_hex("1a")?.is_prefix_of(&node)); + assert!(NodePrefix::from_hex("12c")?.is_prefix_of(&node)); + assert!(!NodePrefix::from_hex("12d")?.is_prefix_of(&node)); Ok(()) } #[test] fn test_get_nybble() -> Result<(), FromHexError> { let prefix = NodePrefix::from_hex("dead6789cafe")?; - assert_eq!(prefix.borrow().get_nybble(0), 13); - assert_eq!(prefix.borrow().get_nybble(7), 9); + assert_eq!(prefix.get_nybble(0), 13); + assert_eq!(prefix.get_nybble(7), 9); Ok(()) } #[test] fn test_first_different_nybble_even_prefix() { let prefix = NodePrefix::from_hex("12ca").unwrap(); - let prefref = prefix.borrow(); let mut node = Node::from([0; NODE_BYTES_LENGTH]); - assert_eq!(prefref.first_different_nybble(&node), Some(0)); + assert_eq!(prefix.first_different_nybble(&node), Some(0)); node.data[0] = 0x13; - assert_eq!(prefref.first_different_nybble(&node), Some(1)); + assert_eq!(prefix.first_different_nybble(&node), Some(1)); node.data[0] = 0x12; - assert_eq!(prefref.first_different_nybble(&node), Some(2)); + assert_eq!(prefix.first_different_nybble(&node), Some(2)); node.data[1] = 0xca; // now it is a prefix - assert_eq!(prefref.first_different_nybble(&node), None); + assert_eq!(prefix.first_different_nybble(&node), None); } #[test] fn test_first_different_nybble_odd_prefix() { let prefix = NodePrefix::from_hex("12c").unwrap(); - let prefref = prefix.borrow(); let mut node = Node::from([0; NODE_BYTES_LENGTH]); - assert_eq!(prefref.first_different_nybble(&node), Some(0)); + assert_eq!(prefix.first_different_nybble(&node), Some(0)); node.data[0] = 0x13; - assert_eq!(prefref.first_different_nybble(&node), Some(1)); + assert_eq!(prefix.first_different_nybble(&node), Some(1)); node.data[0] = 0x12; - assert_eq!(prefref.first_different_nybble(&node), Some(2)); + assert_eq!(prefix.first_different_nybble(&node), Some(2)); node.data[1] = 0xca; // now it is a prefix - assert_eq!(prefref.first_different_nybble(&node), None); + assert_eq!(prefix.first_different_nybble(&node), None); } }