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

commonware_storage/merkle/
path.rs
