commonware_storage/merkle/
path.rs

1//! Generic peak-to-leaf path iterator for Merkle-family data structures.
2//!
3//! [`Iterator`] traverses the path from a peak to a leaf within a perfect binary tree,
4//! yielding `(parent_pos, sibling_pos, height)` tuples at each level. The traversal is top-down
5//! (peak first), using [`Family::children`] for child positions and leaf locations for the
6//! left/right decision at each level.
7
8use crate::merkle::{Family, Location, Position};
9
10/// Maximum number of items a [`Iterator`] can yield. A peak of height `h` has `2^h`
11/// leaves, and leaf counts are stored as `u64`, so the maximum peak height is `u64::BITS - 1`.
12pub(super) const MAX_PATH_LEN: usize = u64::BITS as usize - 1;
13
14/// Yields `(parent_pos, sibling_pos, height)` for each internal node on the path from a peak
15/// to a designated leaf, in top-down order (peak first). The peak itself is the first parent
16/// yielded; the leaf is never yielded.
17///
18/// For example, consider an MMR tree and the path from the peak to leaf at location 2
19/// (position 3):
20///
21/// ```text
22///          6
23///        /   \
24///       2     5
25///      / \   / \
26///     0   1 3   4
27/// ```
28///
29/// `path::Iterator` yields: `[(6, 2, 2), (5, 4, 1)]`
30/// - Node 6 (height 2): left child 2 is the sibling, right child 5 is on the path.
31/// - Node 5 (height 1): right child 4 is the sibling, left child 3 is the target leaf.
32#[derive(Debug)]
33pub struct Iterator<F: Family> {
34    target_loc: Location<F>, // leaf we are navigating toward
35    node_pos: Position<F>,   // current node on the path (starts at peak)
36    first_leaf: u64,         // location of the leftmost leaf in the current subtree
37    height: u32,             // height of the current node
38}
39
40impl<F: Family> Iterator<F> {
41    /// Create a new path iterator from a peak to a leaf.
42    ///
43    /// - `peak_pos`: position of the peak node.
44    /// - `height`: height of the peak.
45    /// - `first_leaf_loc`: location of the leftmost leaf in this peak's subtree.
46    /// - `target_loc`: location of the target leaf.
47    pub const fn new(
48        peak_pos: Position<F>,
49        height: u32,
50        first_leaf_loc: Location<F>,
51        target_loc: Location<F>,
52    ) -> Self {
53        Self {
54            target_loc,
55            node_pos: peak_pos,
56            first_leaf: first_leaf_loc.as_u64(),
57            height,
58        }
59    }
60}
61
62impl<F: Family> core::iter::Iterator for Iterator<F> {
63    /// `(parent_pos, sibling_pos, height)` where height is the parent's height.
64    type Item = (Position<F>, Position<F>, u32);
65
66    fn next(&mut self) -> Option<Self::Item> {
67        if self.height == 0 {
68            return None;
69        }
70
71        let parent_pos = self.node_pos;
72        let parent_height = self.height;
73        let (left, right) = F::children(parent_pos, parent_height);
74
75        let mid = self.first_leaf + (1u64 << (parent_height - 1));
76        self.height -= 1;
77
78        if self.target_loc.as_u64() < mid {
79            // Target is in the left subtree.
80            self.node_pos = left;
81            Some((parent_pos, right, parent_height))
82        } else {
83            // Target is in the right subtree.
84            self.node_pos = right;
85            self.first_leaf = mid;
86            Some((parent_pos, left, parent_height))
87        }
88    }
89}
commonware_storage/merkle/path.rs

commonware_storage/merkle/
path.rs
