1use super::{
 2    hash::rpo::{Rpo256, RpoDigest},
 3    utils::collections::{vec, BTreeMap, BTreeSet, Vec},
 4    Felt, StarkField, Word, WORD_SIZE, ZERO,
 5};
 6use core::fmt;
 7
 8// REEXPORTS
 9// ================================================================================================
10
11mod empty_roots;
12pub use empty_roots::EmptySubtreeRoots;
13use empty_roots::EMPTY_WORD;
14
15mod index;
16pub use index::NodeIndex;
17
18mod merkle_tree;
19pub use merkle_tree::{path_to_text, tree_to_text, MerkleTree};
20
21mod path;
22pub use path::{MerklePath, RootPath, ValuePath};
23
24mod path_set;
25pub use path_set::MerklePathSet;
26
27mod simple_smt;
28pub use simple_smt::SimpleSmt;
29
30mod tiered_smt;
31pub use tiered_smt::TieredSmt;
32
33mod mmr;
34pub use mmr::{Mmr, MmrPeaks, MmrProof};
35
36mod store;
37pub use store::MerkleStore;
38
39mod node;
40pub use node::InnerNodeInfo;
41
42// ERRORS
43// ================================================================================================
44
45#[derive(Clone, Debug, PartialEq, Eq)]
46pub enum MerkleError {
47    ConflictingRoots(Vec<Word>),
48    DepthTooSmall(u8),
49    DepthTooBig(u64),
50    DuplicateValuesForKey(u64),
51    NodeNotInStore(Word, NodeIndex),
52    NumLeavesNotPowerOfTwo(usize),
53    InvalidIndex { depth: u8, value: u64 },
54    InvalidDepth { expected: u8, provided: u8 },
55    InvalidPath(MerklePath),
56    InvalidNumEntries(usize, usize),
57    NodeNotInSet(u64),
58    RootNotInStore(Word),
59}
60
61impl fmt::Display for MerkleError {
62    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
63        use MerkleError::*;
64        match self {
65            ConflictingRoots(roots) => write!(f, "the merkle paths roots do not match {roots:?}"),
66            DepthTooSmall(depth) => write!(f, "the provided depth {depth} is too small"),
67            DepthTooBig(depth) => write!(f, "the provided depth {depth} is too big"),
68            DuplicateValuesForKey(key) => write!(f, "multiple values provided for key {key}"),
69            NumLeavesNotPowerOfTwo(leaves) => {
70                write!(f, "the leaves count {leaves} is not a power of 2")
71            }
72            InvalidIndex{ depth, value} => write!(
73                f,
74                "the index value {value} is not valid for the depth {depth}"
75            ),
76            InvalidDepth { expected, provided } => write!(
77                f,
78                "the provided depth {provided} is not valid for {expected}"
79            ),
80            InvalidPath(_path) => write!(f, "the provided path is not valid"),
81            InvalidNumEntries(max, provided) => write!(f, "the provided number of entries is {provided}, but the maximum for the given depth is {max}"),
82            NodeNotInSet(index) => write!(f, "the node indexed by {index} is not in the set"),
83            NodeNotInStore(hash, index) => write!(f, "the node {:?} indexed by {} and depth {} is not in the store", hash, index.value(), index.depth(),),
84            RootNotInStore(root) => write!(f, "the root {:?} is not in the store", root),
85        }
86    }
87}
88
89#[cfg(feature = "std")]
90impl std::error::Error for MerkleError {}
91
92// HELPER FUNCTIONS
93// ================================================================================================
94
95#[cfg(test)]
96const fn int_to_node(value: u64) -> Word {
97    [Felt::new(value), ZERO, ZERO, ZERO]
98}