pathfinder_common/
trie.rs

1use bitvec::prelude::Msb0;
2use bitvec::vec::BitVec;
3use pathfinder_crypto::Felt;
4
5use crate::hash::FeltHash;
6
7/// A node in a Starknet patricia-merkle trie.
8///
9/// See pathfinders merkle-tree crate for more information.
10#[derive(Debug, Clone, PartialEq, Eq, Hash)]
11pub enum TrieNode {
12    Binary { left: Felt, right: Felt },
13    Edge { child: Felt, path: BitVec<u8, Msb0> },
14}
15
16impl TrieNode {
17    pub fn hash<H: FeltHash>(&self) -> Felt {
18        match self {
19            TrieNode::Binary { left, right } => H::hash(*left, *right),
20            TrieNode::Edge { child, path } => {
21                let mut length = [0; 32];
22                // Safe as len() is guaranteed to be <= 251
23                length[31] = path.len() as u8;
24                let path = Felt::from_bits(path).unwrap();
25
26                let length = Felt::from_be_bytes(length).unwrap();
27                H::hash(*child, path) + length
28            }
29        }
30    }
31}