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

reth_trie_common/
nibbles.rs
