alloy_trie/nodes/
leaf.rs

1use super::{super::Nibbles, encode_path_leaf, unpack_path_to_nibbles, RlpNode};
2use alloy_primitives::{hex, Bytes};
3use alloy_rlp::{length_of_length, BufMut, Decodable, Encodable, Header};
4use core::fmt;
5
6#[allow(unused_imports)]
7use alloc::vec::Vec;
8
9/// A leaf node represents the endpoint or terminal node in the trie. In other words, a leaf node is
10/// where actual values are stored.
11///
12/// A leaf node consists of two parts: the key (or path) and the value. The key is typically the
13/// remaining portion of the key after following the path through the trie, and the value is the
14/// data associated with the full key. When searching the trie for a specific key, reaching a leaf
15/// node means that the search has successfully found the value associated with that key.
16#[derive(PartialEq, Eq, Clone)]
17#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
18pub struct LeafNode {
19    /// The key for this leaf node.
20    pub key: Nibbles,
21    /// The node value.
22    pub value: Vec<u8>,
23}
24
25impl fmt::Debug for LeafNode {
26    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27        f.debug_struct("LeafNode")
28            .field("key", &self.key)
29            .field("value", &hex::encode(&self.value))
30            .finish()
31    }
32}
33
34impl Encodable for LeafNode {
35    #[inline]
36    fn encode(&self, out: &mut dyn BufMut) {
37        self.as_ref().encode(out)
38    }
39
40    #[inline]
41    fn length(&self) -> usize {
42        self.as_ref().length()
43    }
44}
45
46impl Decodable for LeafNode {
47    fn decode(buf: &mut &[u8]) -> alloy_rlp::Result<Self> {
48        let mut bytes = Header::decode_bytes(buf, true)?;
49        let encoded_key = Bytes::decode(&mut bytes)?;
50        if encoded_key.is_empty() {
51            return Err(alloy_rlp::Error::Custom("leaf node key empty"));
52        }
53
54        // Retrieve first byte. If it's [Some], then the nibbles are odd.
55        let first = match encoded_key[0] & 0xf0 {
56            Self::ODD_FLAG => Some(encoded_key[0] & 0x0f),
57            Self::EVEN_FLAG => None,
58            _ => return Err(alloy_rlp::Error::Custom("node is not leaf")),
59        };
60
61        let key = unpack_path_to_nibbles(first, &encoded_key[1..]);
62        let value = Bytes::decode(&mut bytes)?.into();
63        Ok(Self { key, value })
64    }
65}
66
67impl LeafNode {
68    /// The flag representing the even number of nibbles in the leaf key.
69    pub const EVEN_FLAG: u8 = 0x20;
70
71    /// The flag representing the odd number of nibbles in the leaf key.
72    pub const ODD_FLAG: u8 = 0x30;
73
74    /// Creates a new leaf node with the given key and value.
75    pub const fn new(key: Nibbles, value: Vec<u8>) -> Self {
76        Self { key, value }
77    }
78
79    /// Return leaf node as [LeafNodeRef].
80    pub fn as_ref(&self) -> LeafNodeRef<'_> {
81        LeafNodeRef { key: &self.key, value: &self.value }
82    }
83}
84
85/// Reference to the leaf node. See [LeafNode] from more information.
86pub struct LeafNodeRef<'a> {
87    /// The key for this leaf node.
88    pub key: &'a Nibbles,
89    /// The node value.
90    pub value: &'a [u8],
91}
92
93impl fmt::Debug for LeafNodeRef<'_> {
94    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
95        f.debug_struct("LeafNodeRef")
96            .field("key", &self.key)
97            .field("value", &hex::encode(self.value))
98            .finish()
99    }
100}
101
102/// Manual implementation of encoding for the leaf node of Merkle Patricia Trie.
103impl Encodable for LeafNodeRef<'_> {
104    #[inline]
105    fn encode(&self, out: &mut dyn BufMut) {
106        Header { list: true, payload_length: self.rlp_payload_length() }.encode(out);
107        encode_path_leaf(self.key, true).as_slice().encode(out);
108        self.value.encode(out);
109    }
110
111    #[inline]
112    fn length(&self) -> usize {
113        let payload_length = self.rlp_payload_length();
114        payload_length + length_of_length(payload_length)
115    }
116}
117
118impl<'a> LeafNodeRef<'a> {
119    /// Creates a new leaf node with the given key and value.
120    pub const fn new(key: &'a Nibbles, value: &'a [u8]) -> Self {
121        Self { key, value }
122    }
123
124    /// RLP-encodes the node and returns either `rlp(node)` or `rlp(keccak(rlp(node)))`.
125    #[inline]
126    pub fn rlp(&self, rlp: &mut Vec<u8>) -> RlpNode {
127        self.encode(rlp);
128        RlpNode::from_rlp(rlp)
129    }
130
131    /// Returns the length of RLP encoded fields of leaf node.
132    #[inline]
133    fn rlp_payload_length(&self) -> usize {
134        let mut encoded_key_len = self.key.len() / 2 + 1;
135        // For leaf nodes the first byte cannot be greater than 0x80.
136        if encoded_key_len != 1 {
137            encoded_key_len += length_of_length(encoded_key_len);
138        }
139        encoded_key_len + Encodable::length(&self.value)
140    }
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    // From manual regression test
148    #[test]
149    fn encode_leaf_node_nibble() {
150        let nibbles = Nibbles::from_nibbles_unchecked(hex!("0604060f"));
151        let encoded = encode_path_leaf(&nibbles, true);
152        assert_eq!(encoded[..], hex!("20646f"));
153    }
154
155    #[test]
156    fn rlp_leaf_node_roundtrip() {
157        let nibble = Nibbles::from_nibbles_unchecked(hex!("0604060f"));
158        let val = hex!("76657262");
159        let leaf = LeafNode::new(nibble, val.to_vec());
160        let rlp = leaf.as_ref().rlp(&mut vec![]);
161        assert_eq!(rlp.as_ref(), hex!("c98320646f8476657262"));
162        assert_eq!(LeafNode::decode(&mut &rlp[..]).unwrap(), leaf);
163    }
164}
alloy_trie/nodes/leaf.rs

alloy_trie/nodes/
leaf.rs
