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 mmr;
31pub use mmr::{Mmr, MmrPeaks, MmrProof};
32
33mod store;
34pub use store::MerkleStore;
35
36mod node;
37pub use node::InnerNodeInfo;
38
39// ERRORS
40// ================================================================================================
41
42#[derive(Clone, Debug, PartialEq, Eq)]
43pub enum MerkleError {
44    ConflictingRoots(Vec<Word>),
45    DepthTooSmall(u8),
46    DepthTooBig(u64),
47    DuplicateValuesForKey(u64),
48    NodeNotInStore(Word, NodeIndex),
49    NumLeavesNotPowerOfTwo(usize),
50    InvalidIndex { depth: u8, value: u64 },
51    InvalidDepth { expected: u8, provided: u8 },
52    InvalidPath(MerklePath),
53    InvalidNumEntries(usize, usize),
54    NodeNotInSet(u64),
55    RootNotInStore(Word),
56}
57
58impl fmt::Display for MerkleError {
59    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60        use MerkleError::*;
61        match self {
62            ConflictingRoots(roots) => write!(f, "the merkle paths roots do not match {roots:?}"),
63            DepthTooSmall(depth) => write!(f, "the provided depth {depth} is too small"),
64            DepthTooBig(depth) => write!(f, "the provided depth {depth} is too big"),
65            DuplicateValuesForKey(key) => write!(f, "multiple values provided for key {key}"),
66            NumLeavesNotPowerOfTwo(leaves) => {
67                write!(f, "the leaves count {leaves} is not a power of 2")
68            }
69            InvalidIndex{ depth, value} => write!(
70                f,
71                "the index value {value} is not valid for the depth {depth}"
72            ),
73            InvalidDepth { expected, provided } => write!(
74                f,
75                "the provided depth {provided} is not valid for {expected}"
76            ),
77            InvalidPath(_path) => write!(f, "the provided path is not valid"),
78            InvalidNumEntries(max, provided) => write!(f, "the provided number of entries is {provided}, but the maximum for the given depth is {max}"),
79            NodeNotInSet(index) => write!(f, "the node indexed by {index} is not in the set"),
80            NodeNotInStore(hash, index) => write!(f, "the node {:?} indexed by {} and depth {} is not in the store", hash, index.value(), index.depth(),),
81            RootNotInStore(root) => write!(f, "the root {:?} is not in the store", root),
82        }
83    }
84}
85
86#[cfg(feature = "std")]
87impl std::error::Error for MerkleError {}
88
89// HELPER FUNCTIONS
90// ================================================================================================
91
92#[cfg(test)]
93const fn int_to_node(value: u64) -> Word {
94    [Felt::new(value), ZERO, ZERO, ZERO]
95}