changeset 46431:645ee7225fab

rust: Make NodePrefix allocation-free and Copy, remove NodePrefixRef The `*Ref` struct only existed to avoid allocating `Vec`s when cloning `NodePrefix`, but we can avoid having `Vec` in the first place by using an inline array instead. This makes `NodePrefix` 21 bytes (with 1 for the length) which is smaller than before as `Vec` alone is 24 bytes. Differential Revision: https://phab.mercurial-scm.org/D9863
author Simon Sapin <simon.sapin@octobus.net>
date Mon, 25 Jan 2021 11:48:47 +0100
parents b84c3d43ff2e
children 18a261b11b20
files rust/Cargo.lock rust/hg-core/Cargo.toml rust/hg-core/src/operations/cat.rs rust/hg-core/src/operations/debugdata.rs rust/hg-core/src/operations/list_tracked_files.rs rust/hg-core/src/revlog.rs rust/hg-core/src/revlog/changelog.rs rust/hg-core/src/revlog/manifest.rs rust/hg-core/src/revlog/node.rs rust/hg-core/src/revlog/nodemap.rs rust/hg-core/src/revlog/revlog.rs rust/hg-cpython/src/revlog.rs
diffstat 12 files changed, 152 insertions(+), 181 deletions(-) [+]
line wrap: on
line diff
--- a/rust/Cargo.lock	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/Cargo.lock	Mon Jan 25 11:48:47 2021 +0100
@@ -286,11 +286,6 @@
 ]
 
 [[package]]
-name = "hex"
-version = "0.4.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-
-[[package]]
 name = "hg-core"
 version = "0.1.0"
 dependencies = [
@@ -300,7 +295,6 @@
  "crossbeam-channel 0.4.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "flate2 1.0.19 (registry+https://github.com/rust-lang/crates.io-index)",
  "format-bytes 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
- "hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "log 0.4.11 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -956,7 +950,6 @@
 "checksum getrandom 0.1.15 (registry+https://github.com/rust-lang/crates.io-index)" = "fc587bc0ec293155d5bfa6b9891ec18a1e330c234f896ea47fbada4cadbe47e6"
 "checksum glob 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "9b919933a397b79c37e33b77bb2aa3dc8eb6e165ad809e58ff75bc7db2e34574"
 "checksum hermit-abi 0.1.17 (registry+https://github.com/rust-lang/crates.io-index)" = "5aca5565f760fb5b220e499d72710ed156fdb74e631659e99377d9ebfbd13ae8"
-"checksum hex 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)" = "644f9158b2f133fd50f5fb3242878846d9eb792e445c893805ff0e3824006e35"
 "checksum humantime 1.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "df004cfca50ef23c36850aaaa59ad52cc70d0e90243c3c7737a4dd32dc7a3c4f"
 "checksum im-rc 15.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3ca8957e71f04a205cb162508f9326aea04676c8dfd0711220190d6b83664f3f"
 "checksum itertools 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "284f18f85651fe11e8a991b2adb42cb078325c996ed026d994719efcfca1d54b"
--- a/rust/hg-core/Cargo.toml	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/Cargo.toml	Mon Jan 25 11:48:47 2021 +0100
@@ -11,7 +11,6 @@
 [dependencies]
 bytes-cast = "0.1"
 byteorder = "1.3.4"
-hex = "0.4.2"
 im-rc = "15.0.*"
 lazy_static = "1.4.0"
 memchr = "2.3.3"
--- a/rust/hg-core/src/operations/cat.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/operations/cat.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -88,13 +88,13 @@
         _ => {
             let changelog_node = NodePrefix::from_hex(&rev)
                 .map_err(|_| CatRevErrorKind::InvalidRevision)?;
-            changelog.get_node(changelog_node.borrow())?
+            changelog.get_node(changelog_node)?
         }
     };
     let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?)
         .map_err(|_| CatRevErrorKind::CorruptedRevlog)?;
 
-    let manifest_entry = manifest.get_node((&manifest_node).into())?;
+    let manifest_entry = manifest.get_node(manifest_node.into())?;
     let mut bytes = vec![];
 
     for (manifest_file, node_bytes) in manifest_entry.files_with_nodes() {
@@ -107,7 +107,7 @@
                     Revlog::open(repo, &index_path, Some(&data_path))?;
                 let file_node = Node::from_hex(node_bytes)
                     .map_err(|_| CatRevErrorKind::CorruptedRevlog)?;
-                let file_rev = file_log.get_node_rev((&file_node).into())?;
+                let file_rev = file_log.get_node_rev(file_node.into())?;
                 let data = file_log.get_rev_data(file_rev)?;
                 if data.starts_with(&METADATA_DELIMITER) {
                     let end_delimiter_position = data
--- a/rust/hg-core/src/operations/debugdata.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/operations/debugdata.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -93,7 +93,7 @@
         _ => {
             let node = NodePrefix::from_hex(&rev)
                 .map_err(|_| DebugDataErrorKind::InvalidRevision)?;
-            let rev = revlog.get_node_rev(node.borrow())?;
+            let rev = revlog.get_node_rev(node)?;
             revlog.get_rev_data(rev)?
         }
     };
--- a/rust/hg-core/src/operations/list_tracked_files.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/operations/list_tracked_files.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -147,12 +147,12 @@
         _ => {
             let changelog_node = NodePrefix::from_hex(&rev)
                 .or(Err(ListRevTrackedFilesErrorKind::InvalidRevision))?;
-            changelog.get_node(changelog_node.borrow())?
+            changelog.get_node(changelog_node)?
         }
     };
     let manifest_node = Node::from_hex(&changelog_entry.manifest_node()?)
         .or(Err(ListRevTrackedFilesErrorKind::CorruptedRevlog))?;
-    let manifest_entry = manifest.get_node((&manifest_node).into())?;
+    let manifest_entry = manifest.get_node(manifest_node.into())?;
     Ok(FilesForRev(manifest_entry))
 }
 
--- a/rust/hg-core/src/revlog.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/revlog.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -9,7 +9,7 @@
 pub mod nodemap;
 mod nodemap_docket;
 pub mod path_encode;
-pub use node::{FromHexError, Node, NodePrefix, NodePrefixRef};
+pub use node::{FromHexError, Node, NodePrefix};
 pub mod changelog;
 pub mod index;
 pub mod manifest;
--- a/rust/hg-core/src/revlog/changelog.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/revlog/changelog.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -1,6 +1,6 @@
 use crate::repo::Repo;
 use crate::revlog::revlog::{Revlog, RevlogError};
-use crate::revlog::NodePrefixRef;
+use crate::revlog::NodePrefix;
 use crate::revlog::Revision;
 
 /// A specialized `Revlog` to work with `changelog` data format.
@@ -19,7 +19,7 @@
     /// Return the `ChangelogEntry` a given node id.
     pub fn get_node(
         &self,
-        node: NodePrefixRef,
+        node: NodePrefix,
     ) -> Result<ChangelogEntry, RevlogError> {
         let rev = self.revlog.get_node_rev(node)?;
         self.get_rev(rev)
--- a/rust/hg-core/src/revlog/manifest.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/revlog/manifest.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -1,6 +1,6 @@
 use crate::repo::Repo;
 use crate::revlog::revlog::{Revlog, RevlogError};
-use crate::revlog::NodePrefixRef;
+use crate::revlog::NodePrefix;
 use crate::revlog::Revision;
 use crate::utils::hg_path::HgPath;
 
@@ -20,7 +20,7 @@
     /// Return the `ManifestEntry` of a given node id.
     pub fn get_node(
         &self,
-        node: NodePrefixRef,
+        node: NodePrefix,
     ) -> Result<ManifestEntry, RevlogError> {
         let rev = self.revlog.get_node_rev(node)?;
         self.get_rev(rev)
--- 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<Self, Self::Error> {
         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<Self, Self::Error> {
+        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<Node, FromHexError> {
-        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<u8>,
-    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<u8> =
-            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<Item = u8> + '_ {
+        (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<usize> {
-        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<Node> for NodePrefix {
+    fn from(node: Node) -> Self {
+        NodePrefix {
+            nybbles_len: node.nybbles_len() as _,
+            data: node.data,
         }
     }
 }
 
-impl PartialEq<Node> for NodePrefixRef<'_> {
+impl PartialEq<Node> 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(&not_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);
     }
 }
 
--- a/rust/hg-core/src/revlog/nodemap.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/revlog/nodemap.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -13,8 +13,8 @@
 //! is used in a more abstract context.
 
 use super::{
-    node::NULL_NODE, FromHexError, Node, NodePrefix, NodePrefixRef, Revision,
-    RevlogIndex, NULL_REVISION,
+    node::NULL_NODE, FromHexError, Node, NodePrefix, Revision, RevlogIndex,
+    NULL_REVISION,
 };
 
 use bytes_cast::{unaligned, BytesCast};
@@ -82,7 +82,7 @@
     fn find_bin<'a>(
         &self,
         idx: &impl RevlogIndex,
-        prefix: NodePrefixRef<'a>,
+        prefix: NodePrefix,
     ) -> Result<Option<Revision>, NodeMapError>;
 
     /// Find the unique Revision whose `Node` hexadecimal string representation
@@ -97,7 +97,7 @@
         idx: &impl RevlogIndex,
         prefix: &str,
     ) -> Result<Option<Revision>, NodeMapError> {
-        self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+        self.find_bin(idx, NodePrefix::from_hex(prefix)?)
     }
 
     /// Give the size of the shortest node prefix that determines
@@ -114,7 +114,7 @@
     fn unique_prefix_len_bin<'a>(
         &self,
         idx: &impl RevlogIndex,
-        node_prefix: NodePrefixRef<'a>,
+        node_prefix: NodePrefix,
     ) -> Result<Option<usize>, NodeMapError>;
 
     /// Same as `unique_prefix_len_bin`, with the hexadecimal representation
@@ -124,7 +124,7 @@
         idx: &impl RevlogIndex,
         prefix: &str,
     ) -> Result<Option<usize>, NodeMapError> {
-        self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
+        self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?)
     }
 
     /// Same as `unique_prefix_len_bin`, with a full `Node` as input
@@ -278,7 +278,7 @@
 /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
 fn has_prefix_or_none(
     idx: &impl RevlogIndex,
-    prefix: NodePrefixRef,
+    prefix: NodePrefix,
     rev: Revision,
 ) -> Result<Option<Revision>, NodeMapError> {
     idx.node(rev)
@@ -299,7 +299,7 @@
 /// revision is the only one for a *subprefix* of the one being looked up.
 fn validate_candidate(
     idx: &impl RevlogIndex,
-    prefix: NodePrefixRef,
+    prefix: NodePrefix,
     candidate: (Option<Revision>, usize),
 ) -> Result<(Option<Revision>, usize), NodeMapError> {
     let (rev, steps) = candidate;
@@ -426,7 +426,7 @@
     /// `NodeTree`).
     fn lookup(
         &self,
-        prefix: NodePrefixRef,
+        prefix: NodePrefix,
     ) -> Result<(Option<Revision>, usize), NodeMapError> {
         for (i, visit_item) in self.visit(prefix).enumerate() {
             if let Some(opt) = visit_item.final_revision() {
@@ -436,10 +436,7 @@
         Err(NodeMapError::MultipleResults)
     }
 
-    fn visit<'n, 'p>(
-        &'n self,
-        prefix: NodePrefixRef<'p>,
-    ) -> NodeTreeVisitor<'n, 'p> {
+    fn visit<'n>(&'n self, prefix: NodePrefix) -> NodeTreeVisitor<'n> {
         NodeTreeVisitor {
             nt: self,
             prefix,
@@ -617,9 +614,9 @@
     }
 }
 
-struct NodeTreeVisitor<'n, 'p> {
+struct NodeTreeVisitor<'n> {
     nt: &'n NodeTree,
-    prefix: NodePrefixRef<'p>,
+    prefix: NodePrefix,
     visit: usize,
     nybble_idx: usize,
     done: bool,
@@ -632,11 +629,11 @@
     element: Element,
 }
 
-impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
+impl<'n> Iterator for NodeTreeVisitor<'n> {
     type Item = NodeTreeVisitItem;
 
     fn next(&mut self) -> Option<Self::Item> {
-        if self.done || self.nybble_idx >= self.prefix.len() {
+        if self.done || self.nybble_idx >= self.prefix.nybbles_len() {
             return None;
         }
 
@@ -701,18 +698,18 @@
     fn find_bin<'a>(
         &self,
         idx: &impl RevlogIndex,
-        prefix: NodePrefixRef<'a>,
+        prefix: NodePrefix,
     ) -> Result<Option<Revision>, NodeMapError> {
-        validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+        validate_candidate(idx, prefix, self.lookup(prefix)?)
             .map(|(opt, _shortest)| opt)
     }
 
     fn unique_prefix_len_bin<'a>(
         &self,
         idx: &impl RevlogIndex,
-        prefix: NodePrefixRef<'a>,
+        prefix: NodePrefix,
     ) -> Result<Option<usize>, NodeMapError> {
-        validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
+        validate_candidate(idx, prefix, self.lookup(prefix)?)
             .map(|(opt, shortest)| opt.map(|_rev| shortest))
     }
 }
--- a/rust/hg-core/src/revlog/revlog.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-core/src/revlog/revlog.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -11,7 +11,7 @@
 use zstd;
 
 use super::index::Index;
-use super::node::{NodePrefixRef, NODE_BYTES_LENGTH, NULL_NODE};
+use super::node::{NodePrefix, NODE_BYTES_LENGTH, NULL_NODE};
 use super::nodemap;
 use super::nodemap::NodeMap;
 use super::nodemap_docket::NodeMapDocket;
@@ -117,7 +117,7 @@
     #[timed]
     pub fn get_node_rev(
         &self,
-        node: NodePrefixRef,
+        node: NodePrefix,
     ) -> Result<Revision, RevlogError> {
         if let Some(nodemap) = &self.nodemap {
             return nodemap
--- a/rust/hg-cpython/src/revlog.rs	Sat Jan 30 18:30:11 2021 +0800
+++ b/rust/hg-cpython/src/revlog.rs	Mon Jan 25 11:48:47 2021 +0100
@@ -64,7 +64,7 @@
         let nt = opt.as_ref().unwrap();
         let idx = &*self.cindex(py).borrow();
         let node = node_from_py_bytes(py, &node)?;
-        nt.find_bin(idx, (&node).into()).map_err(|e| nodemap_error(py, e))
+        nt.find_bin(idx, node.into()).map_err(|e| nodemap_error(py, e))
     }
 
     /// same as `get_rev()` but raises a bare `error.RevlogError` if node