reth_trie_common/
nibbles.rs

1use alloc::vec::Vec;
2use core::cmp::Ordering;
3use derive_more::Deref;
4pub use nybbles::Nibbles;
5
6/// Compares two [`Nibbles`] in depth-first order.
7///
8/// In depth-first ordering:
9/// - Descendants come before their ancestors (children before parents)
10/// - Siblings are ordered lexicographically
11pub fn depth_first_cmp(a: &Nibbles, b: &Nibbles) -> Ordering {
12    if a.len() == b.len() {
13        return a.cmp(b)
14    }
15
16    let common_prefix_len = a.common_prefix_length(b);
17    if a.len() == common_prefix_len {
18        return Ordering::Greater
19    } else if b.len() == common_prefix_len {
20        return Ordering::Less
21    }
22
23    a.get_unchecked(common_prefix_len).cmp(&b.get_unchecked(common_prefix_len))
24}
25
26/// The representation of nibbles of the merkle trie stored in the database.
27#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash, derive_more::Index)]
28#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
29#[cfg_attr(feature = "test-utils", derive(arbitrary::Arbitrary))]
30pub struct StoredNibbles(pub Nibbles);
31
32impl From<Nibbles> for StoredNibbles {
33    #[inline]
34    fn from(value: Nibbles) -> Self {
35        Self(value)
36    }
37}
38
39impl From<Vec<u8>> for StoredNibbles {
40    #[inline]
41    fn from(value: Vec<u8>) -> Self {
42        Self(Nibbles::from_nibbles_unchecked(value))
43    }
44}
45
46#[cfg(any(test, feature = "reth-codec"))]
47impl reth_codecs::Compact for StoredNibbles {
48    fn to_compact<B>(&self, buf: &mut B) -> usize
49    where
50        B: bytes::BufMut + AsMut<[u8]>,
51    {
52        let bytes = self.0.iter().collect::<arrayvec::ArrayVec<u8, 64>>();
53        buf.put_slice(&bytes);
54        bytes.len()
55    }
56
57    fn from_compact(mut buf: &[u8], len: usize) -> (Self, &[u8]) {
58        use bytes::Buf;
59
60        let nibbles = &buf[..len];
61        buf.advance(len);
62        (Self(Nibbles::from_nibbles_unchecked(nibbles)), buf)
63    }
64}
65
66#[cfg(any(test, feature = "reth-codec"))]
67reth_codecs::impl_compression_for_compact!(StoredNibbles);
68
69/// The representation of nibbles of the merkle trie stored in the database.
70#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Deref)]
71#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
72#[cfg_attr(feature = "test-utils", derive(arbitrary::Arbitrary))]
73pub struct StoredNibblesSubKey(pub Nibbles);
74
75impl From<Nibbles> for StoredNibblesSubKey {
76    #[inline]
77    fn from(value: Nibbles) -> Self {
78        Self(value)
79    }
80}
81
82impl From<Vec<u8>> for StoredNibblesSubKey {
83    #[inline]
84    fn from(value: Vec<u8>) -> Self {
85        Self(Nibbles::from_nibbles_unchecked(value))
86    }
87}
88
89impl From<StoredNibblesSubKey> for Nibbles {
90    #[inline]
91    fn from(value: StoredNibblesSubKey) -> Self {
92        value.0
93    }
94}
95
96impl StoredNibblesSubKey {
97    /// Encodes the nibbles into a fixed-size `[u8; 65]` array.
98    ///
99    /// The first 64 bytes contain the nibble values (right-padded with zeros),
100    /// and the 65th byte stores the actual nibble count.
101    pub fn to_compact_array(&self) -> [u8; 65] {
102        assert!(self.0.len() <= 64);
103        let mut buf = [0u8; 65];
104        for (i, nibble) in self.0.iter().enumerate() {
105            buf[i] = nibble;
106        }
107        buf[64] = self.0.len() as u8;
108        buf
109    }
110}
111
112#[cfg(any(test, feature = "reth-codec"))]
113impl reth_codecs::Compact for StoredNibblesSubKey {
114    fn to_compact<B>(&self, buf: &mut B) -> usize
115    where
116        B: bytes::BufMut + AsMut<[u8]>,
117    {
118        assert!(self.0.len() <= 64);
119
120        let bytes = self.0.iter().collect::<arrayvec::ArrayVec<u8, 64>>();
121        buf.put_slice(&bytes);
122
123        // Right-pad with zeros
124        static ZERO: &[u8; 64] = &[0; 64];
125        buf.put_slice(&ZERO[bytes.len()..]);
126
127        buf.put_u8(bytes.len() as u8);
128        64 + 1
129    }
130
131    fn from_compact(buf: &[u8], _len: usize) -> (Self, &[u8]) {
132        let len = buf[64] as usize;
133        (Self(Nibbles::from_nibbles_unchecked(&buf[..len])), &buf[65..])
134    }
135}
136
137#[cfg(any(test, feature = "reth-codec"))]
138reth_codecs::impl_compression_for_compact!(StoredNibblesSubKey);
139
140/// Packed representation of nibbles for the `AccountsTrie` (storage v2).
141///
142/// Stores 2 nibbles per byte via [`Nibbles::pack`], right-padded to 32 bytes + 1 nibble-count
143/// byte = 33 bytes fixed. This halves the key size compared to [`StoredNibbles`] while
144/// preserving sort order under `memcmp`.
145#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash, derive_more::Index)]
146#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
147#[cfg_attr(feature = "test-utils", derive(arbitrary::Arbitrary))]
148pub struct PackedStoredNibbles(pub Nibbles);
149
150impl From<Nibbles> for PackedStoredNibbles {
151    #[inline]
152    fn from(value: Nibbles) -> Self {
153        Self(value)
154    }
155}
156
157impl From<Vec<u8>> for PackedStoredNibbles {
158    #[inline]
159    fn from(value: Vec<u8>) -> Self {
160        Self(Nibbles::from_nibbles_unchecked(value))
161    }
162}
163
164impl From<StoredNibbles> for PackedStoredNibbles {
165    #[inline]
166    fn from(value: StoredNibbles) -> Self {
167        Self(value.0)
168    }
169}
170
171impl From<PackedStoredNibbles> for StoredNibbles {
172    #[inline]
173    fn from(value: PackedStoredNibbles) -> Self {
174        Self(value.0)
175    }
176}
177
178impl PackedStoredNibbles {
179    /// Encodes the nibbles into a fixed-size `[u8; 33]` array.
180    ///
181    /// The first 32 bytes contain the packed nibbles (2 per byte, right-padded with zeros),
182    /// and the 33rd byte stores the actual nibble count.
183    pub fn to_compact_array(&self) -> [u8; 33] {
184        assert!(self.0.len() <= 64);
185        let mut buf = [0u8; 33];
186        self.0.pack_to(&mut buf[..32]);
187        buf[32] = self.0.len() as u8;
188        buf
189    }
190}
191
192#[cfg(any(test, feature = "reth-codec"))]
193impl reth_codecs::Compact for PackedStoredNibbles {
194    fn to_compact<B>(&self, buf: &mut B) -> usize
195    where
196        B: bytes::BufMut + AsMut<[u8]>,
197    {
198        assert!(self.0.len() <= 64);
199
200        let mut packed = [0u8; 32];
201        self.0.pack_to(&mut packed);
202        buf.put_slice(&packed);
203        buf.put_u8(self.0.len() as u8);
204        33
205    }
206
207    fn from_compact(buf: &[u8], _len: usize) -> (Self, &[u8]) {
208        let nibble_count = buf[32] as usize;
209        let packed_len = nibble_count.div_ceil(2);
210        (Self(Nibbles::unpack(&buf[..packed_len]).slice(..nibble_count)), &buf[33..])
211    }
212}
213
214#[cfg(any(test, feature = "reth-codec"))]
215reth_codecs::impl_compression_for_compact!(PackedStoredNibbles);
216
217/// Packed representation of nibbles as a `DupSort` subkey for `StoragesTrie` (storage v2).
218///
219/// Stores 2 nibbles per byte via [`Nibbles::pack`], right-padded to 32 bytes + 1 nibble-count
220/// byte = 33 bytes fixed. This halves the subkey size compared to [`StoredNibblesSubKey`]
221/// (65 → 33 bytes) while preserving sort order under `memcmp`.
222#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Deref)]
223#[cfg_attr(any(test, feature = "serde"), derive(serde::Serialize, serde::Deserialize))]
224#[cfg_attr(feature = "test-utils", derive(arbitrary::Arbitrary))]
225pub struct PackedStoredNibblesSubKey(pub Nibbles);
226
227impl From<Nibbles> for PackedStoredNibblesSubKey {
228    #[inline]
229    fn from(value: Nibbles) -> Self {
230        Self(value)
231    }
232}
233
234impl From<Vec<u8>> for PackedStoredNibblesSubKey {
235    #[inline]
236    fn from(value: Vec<u8>) -> Self {
237        Self(Nibbles::from_nibbles_unchecked(value))
238    }
239}
240
241impl From<PackedStoredNibblesSubKey> for Nibbles {
242    #[inline]
243    fn from(value: PackedStoredNibblesSubKey) -> Self {
244        value.0
245    }
246}
247
248impl From<StoredNibblesSubKey> for PackedStoredNibblesSubKey {
249    #[inline]
250    fn from(value: StoredNibblesSubKey) -> Self {
251        Self(value.0)
252    }
253}
254
255impl From<PackedStoredNibblesSubKey> for StoredNibblesSubKey {
256    #[inline]
257    fn from(value: PackedStoredNibblesSubKey) -> Self {
258        Self(value.0)
259    }
260}
261
262impl PackedStoredNibblesSubKey {
263    /// Encodes the nibbles into a fixed-size `[u8; 33]` array.
264    ///
265    /// The first 32 bytes contain the packed nibbles (2 per byte, right-padded with zeros),
266    /// and the 33rd byte stores the actual nibble count.
267    pub fn to_compact_array(&self) -> [u8; 33] {
268        assert!(self.0.len() <= 64);
269        let mut buf = [0u8; 33];
270        self.0.pack_to(&mut buf[..32]);
271        buf[32] = self.0.len() as u8;
272        buf
273    }
274}
275
276#[cfg(any(test, feature = "reth-codec"))]
277impl reth_codecs::Compact for PackedStoredNibblesSubKey {
278    fn to_compact<B>(&self, buf: &mut B) -> usize
279    where
280        B: bytes::BufMut + AsMut<[u8]>,
281    {
282        assert!(self.0.len() <= 64);
283
284        let mut packed = [0u8; 32];
285        self.0.pack_to(&mut packed);
286        buf.put_slice(&packed);
287        buf.put_u8(self.0.len() as u8);
288        33
289    }
290
291    fn from_compact(buf: &[u8], _len: usize) -> (Self, &[u8]) {
292        let nibble_count = buf[32] as usize;
293        let packed_len = nibble_count.div_ceil(2);
294        (Self(Nibbles::unpack(&buf[..packed_len]).slice(..nibble_count)), &buf[33..])
295    }
296}
297
298#[cfg(any(test, feature = "reth-codec"))]
299reth_codecs::impl_compression_for_compact!(PackedStoredNibblesSubKey);
300
301#[cfg(test)]
302mod tests {
303    use super::*;
304    use bytes::BytesMut;
305    use reth_codecs::Compact;
306
307    #[test]
308    fn test_stored_nibbles_from_nibbles() {
309        let nibbles = Nibbles::from_nibbles_unchecked(vec![0x02, 0x04, 0x06]);
310        let stored = StoredNibbles::from(nibbles);
311        assert_eq!(stored.0, nibbles);
312    }
313
314    #[test]
315    fn test_stored_nibbles_from_vec() {
316        let bytes = vec![0x02, 0x04, 0x06];
317        let stored = StoredNibbles::from(bytes.clone());
318        assert_eq!(stored.0.to_vec(), bytes);
319    }
320
321    #[test]
322    fn test_stored_nibbles_to_compact() {
323        let stored = StoredNibbles::from(vec![0x02, 0x04]);
324        let mut buf = BytesMut::with_capacity(10);
325        let len = stored.to_compact(&mut buf);
326        assert_eq!(len, 2);
327        assert_eq!(buf, &vec![0x02, 0x04][..]);
328    }
329
330    #[test]
331    fn test_stored_nibbles_from_compact() {
332        let buf = vec![0x02, 0x04, 0x06];
333        let (stored, remaining) = StoredNibbles::from_compact(&buf, 2);
334        assert_eq!(stored.0.to_vec(), vec![0x02, 0x04]);
335        assert_eq!(remaining, &[0x06]);
336    }
337
338    #[test]
339    fn test_stored_nibbles_subkey_to_compact() {
340        let subkey = StoredNibblesSubKey::from(vec![0x02, 0x04]);
341        let mut buf = BytesMut::with_capacity(65);
342        let len = subkey.to_compact(&mut buf);
343        assert_eq!(len, 65);
344        assert_eq!(buf[..2], [0x02, 0x04]);
345        assert_eq!(buf[64], 2); // Length byte
346    }
347
348    #[test]
349    fn test_stored_nibbles_subkey_from_compact() {
350        let mut buf = vec![0x02, 0x04];
351        buf.resize(65, 0);
352        buf[64] = 2;
353        let (subkey, remaining) = StoredNibblesSubKey::from_compact(&buf, 65);
354        assert_eq!(subkey.0.to_vec(), vec![0x02, 0x04]);
355        assert_eq!(remaining, &[] as &[u8]);
356    }
357
358    #[test]
359    fn test_packed_stored_nibbles_roundtrip() {
360        let stored = PackedStoredNibbles::from(vec![0x0A, 0x0B, 0x0C]);
361        let mut buf = BytesMut::with_capacity(33);
362        let len = stored.to_compact(&mut buf);
363        assert_eq!(len, 33);
364        assert_eq!(buf[0], 0xAB);
365        assert_eq!(buf[1], 0xC0);
366        assert_eq!(buf[32], 3);
367
368        let (roundtrip, _) = PackedStoredNibbles::from_compact(&buf, 33);
369        assert_eq!(roundtrip.0.to_vec(), vec![0x0A, 0x0B, 0x0C]);
370    }
371
372    #[test]
373    fn test_packed_stored_nibbles_subkey_roundtrip() {
374        let subkey = PackedStoredNibblesSubKey::from(vec![0x02, 0x04]);
375        let mut buf = BytesMut::with_capacity(33);
376        let len = subkey.to_compact(&mut buf);
377        assert_eq!(len, 33);
378        assert_eq!(buf[0], 0x24);
379        assert_eq!(buf[32], 2);
380
381        let (roundtrip, _) = PackedStoredNibblesSubKey::from_compact(&buf, 33);
382        assert_eq!(roundtrip.0.to_vec(), vec![0x02, 0x04]);
383    }
384
385    #[test]
386    fn test_packed_sort_order_preserved() {
387        let cases: Vec<Vec<u8>> = vec![
388            vec![0x01],
389            vec![0x01, 0x00],
390            vec![0x01, 0x02],
391            vec![0x02],
392            vec![0x03, 0x0A],
393            vec![0x03, 0x0B],
394            vec![0x04, 0x00],
395            vec![0x0A, 0x0B, 0x0C, 0x0D],
396        ];
397
398        let mut packed_bufs: Vec<Vec<u8>> = Vec::new();
399        for nibbles in &cases {
400            let subkey = PackedStoredNibblesSubKey::from(nibbles.clone());
401            let mut buf = BytesMut::with_capacity(33);
402            subkey.to_compact(&mut buf);
403            packed_bufs.push(buf.to_vec());
404        }
405
406        for i in 1..packed_bufs.len() {
407            assert!(
408                packed_bufs[i - 1] < packed_bufs[i],
409                "sort order broken: {:?} should be < {:?}",
410                cases[i - 1],
411                cases[i]
412            );
413        }
414    }
415
416    #[test]
417    fn test_packed_legacy_conversion() {
418        let nibbles = vec![0x0A, 0x0B, 0x0C, 0x0D];
419        let legacy = StoredNibblesSubKey::from(nibbles);
420        let packed: PackedStoredNibblesSubKey = legacy.clone().into();
421        let back: StoredNibblesSubKey = packed.into();
422        assert_eq!(legacy, back);
423    }
424
425    #[test]
426    fn test_packed_stored_nibbles_compact_array_empty() {
427        let stored = PackedStoredNibbles::from(vec![]);
428        let arr = stored.to_compact_array();
429        assert_eq!(arr, [0u8; 33]);
430    }
431
432    #[test]
433    fn test_packed_stored_nibbles_compact_array_full() {
434        let nibbles: Vec<u8> = (0..64).map(|i| i % 16).collect();
435        let stored = PackedStoredNibbles::from(nibbles);
436        let arr = stored.to_compact_array();
437        assert_eq!(arr[32], 64);
438        let (recovered, rest) = PackedStoredNibbles::from_compact(&arr, 33);
439        assert_eq!(recovered, stored);
440        assert!(rest.is_empty());
441    }
442
443    #[test]
444    fn test_packed_stored_nibbles_compact_array_roundtrip() {
445        let stored = PackedStoredNibbles::from(vec![0x0A, 0x0B, 0x0C]);
446        let arr = stored.to_compact_array();
447        let (recovered, rest) = PackedStoredNibbles::from_compact(&arr, 33);
448        assert_eq!(recovered, stored);
449        assert!(rest.is_empty());
450    }
451
452    #[test]
453    fn test_packed_stored_nibbles_compact_array_matches_to_compact() {
454        for len in [0, 1, 2, 31, 32, 33, 63, 64] {
455            let nibbles: Vec<u8> = (0..len).map(|i| (i % 16) as u8).collect();
456            let stored = PackedStoredNibbles::from(nibbles);
457            let arr = stored.to_compact_array();
458            let mut compact_buf = BytesMut::with_capacity(33);
459            stored.to_compact(&mut compact_buf);
460            assert_eq!(&arr[..], &compact_buf[..], "mismatch at nibble length {len}");
461        }
462    }
463
464    #[test]
465    fn test_packed_stored_nibbles_subkey_compact_array_empty() {
466        let subkey = PackedStoredNibblesSubKey::from(vec![]);
467        let arr = subkey.to_compact_array();
468        assert_eq!(arr, [0u8; 33]);
469    }
470
471    #[test]
472    fn test_packed_stored_nibbles_subkey_compact_array_full() {
473        let nibbles: Vec<u8> = (0..64).map(|i| i % 16).collect();
474        let subkey = PackedStoredNibblesSubKey::from(nibbles);
475        let arr = subkey.to_compact_array();
476        assert_eq!(arr[32], 64);
477        let (recovered, rest) = PackedStoredNibblesSubKey::from_compact(&arr, 33);
478        assert_eq!(recovered, subkey);
479        assert!(rest.is_empty());
480    }
481
482    #[test]
483    fn test_packed_stored_nibbles_subkey_compact_array_roundtrip() {
484        let subkey = PackedStoredNibblesSubKey::from(vec![0x0A, 0x0B, 0x0C]);
485        let arr = subkey.to_compact_array();
486        let (recovered, rest) = PackedStoredNibblesSubKey::from_compact(&arr, 33);
487        assert_eq!(recovered, subkey);
488        assert!(rest.is_empty());
489    }
490
491    #[test]
492    fn test_packed_stored_nibbles_subkey_compact_array_matches_to_compact() {
493        for len in [0, 1, 2, 31, 32, 33, 63, 64] {
494            let nibbles: Vec<u8> = (0..len).map(|i| (i % 16) as u8).collect();
495            let subkey = PackedStoredNibblesSubKey::from(nibbles);
496            let arr = subkey.to_compact_array();
497            let mut compact_buf = BytesMut::with_capacity(33);
498            subkey.to_compact(&mut compact_buf);
499            assert_eq!(&arr[..], &compact_buf[..], "mismatch at nibble length {len}");
500        }
501    }
502
503    #[test]
504    fn test_packed_stored_nibbles_subkey_compact_array_padding_is_zero() {
505        let subkey = PackedStoredNibblesSubKey::from(vec![0x0F; 10]);
506        let arr = subkey.to_compact_array();
507        assert!(arr[5..32].iter().all(|&b| b == 0), "padding bytes must be zero");
508    }
509
510    #[test]
511    fn test_serialization_stored_nibbles() {
512        let stored = StoredNibbles::from(vec![0x02, 0x04]);
513        let serialized = serde_json::to_string(&stored).unwrap();
514        let deserialized: StoredNibbles = serde_json::from_str(&serialized).unwrap();
515        assert_eq!(stored, deserialized);
516    }
517
518    #[test]
519    fn test_serialization_stored_nibbles_subkey() {
520        let subkey = StoredNibblesSubKey::from(vec![0x02, 0x04]);
521        let serialized = serde_json::to_string(&subkey).unwrap();
522        let deserialized: StoredNibblesSubKey = serde_json::from_str(&serialized).unwrap();
523        assert_eq!(subkey, deserialized);
524    }
525
526    #[test]
527    fn test_stored_nibbles_subkey_compact_array_empty() {
528        let subkey = StoredNibblesSubKey::from(vec![]);
529        let arr = subkey.to_compact_array();
530        assert_eq!(arr, [0u8; 65]);
531    }
532
533    #[test]
534    fn test_stored_nibbles_subkey_compact_array_full() {
535        let nibbles: Vec<u8> = (0..64).map(|i| i % 16).collect();
536        let subkey = StoredNibblesSubKey::from(nibbles.clone());
537        let arr = subkey.to_compact_array();
538        assert_eq!(&arr[..64], &nibbles[..]);
539        assert_eq!(arr[64], 64);
540    }
541
542    #[test]
543    fn test_stored_nibbles_subkey_compact_array_roundtrip() {
544        let subkey = StoredNibblesSubKey::from(vec![0x0A, 0x0B, 0x0C]);
545        let arr = subkey.to_compact_array();
546        let (recovered, rest) = StoredNibblesSubKey::from_compact(&arr, 65);
547        assert_eq!(recovered, subkey);
548        assert!(rest.is_empty());
549    }
550
551    #[test]
552    fn test_stored_nibbles_subkey_compact_array_matches_to_compact() {
553        for len in [0, 1, 2, 31, 32, 33, 63, 64] {
554            let nibbles: Vec<u8> = (0..len).map(|i| (i % 16) as u8).collect();
555            let subkey = StoredNibblesSubKey::from(nibbles);
556
557            let arr = subkey.to_compact_array();
558
559            let mut compact_buf = BytesMut::with_capacity(65);
560            subkey.to_compact(&mut compact_buf);
561
562            assert_eq!(&arr[..], &compact_buf[..], "mismatch at nibble length {len}");
563        }
564    }
565
566    #[test]
567    fn test_stored_nibbles_subkey_compact_array_padding_is_zero() {
568        let subkey = StoredNibblesSubKey::from(vec![0x0F; 10]);
569        let arr = subkey.to_compact_array();
570        assert!(arr[10..64].iter().all(|&b| b == 0), "padding bytes must be zero");
571    }
572}
reth_trie_common/nibbles.rs

reth_trie_common/
nibbles.rs
