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