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