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