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