1use super::RpoDigest;
  2
  3// NODE INDEX
  4// ================================================================================================
  5
  6/// A Merkle tree address to an arbitrary node.
  7#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Hash)]
  8pub struct NodeIndex {
  9    depth: u8,
 10    value: u64,
 11}
 12
 13impl NodeIndex {
 14    // CONSTRUCTORS
 15    // --------------------------------------------------------------------------------------------
 16
 17    /// Creates a new node index.
 18    pub const fn new(depth: u8, value: u64) -> Self {
 19        Self { depth, value }
 20    }
 21
 22    /// Creates a new node index pointing to the root of the tree.
 23    pub const fn root() -> Self {
 24        Self { depth: 0, value: 0 }
 25    }
 26
 27    /// Mutates the instance and returns it, replacing the depth.
 28    pub const fn with_depth(mut self, depth: u8) -> Self {
 29        self.depth = depth;
 30        self
 31    }
 32
 33    /// Computes the value of the sibling of the current node.
 34    pub fn sibling(mut self) -> Self {
 35        self.value ^= 1;
 36        self
 37    }
 38
 39    // PROVIDERS
 40    // --------------------------------------------------------------------------------------------
 41
 42    /// Builds a node to be used as input of a hash function when computing a Merkle path.
 43    ///
 44    /// Will evaluate the parity of the current instance to define the result.
 45    pub const fn build_node(&self, slf: RpoDigest, sibling: RpoDigest) -> [RpoDigest; 2] {
 46        if self.is_value_odd() {
 47            [sibling, slf]
 48        } else {
 49            [slf, sibling]
 50        }
 51    }
 52
 53    /// Returns the scalar representation of the depth/value pair.
 54    ///
 55    /// It is computed as `2^depth + value`.
 56    pub const fn to_scalar_index(&self) -> u64 {
 57        (1 << self.depth as u64) + self.value
 58    }
 59
 60    /// Returns the depth of the current instance.
 61    pub const fn depth(&self) -> u8 {
 62        self.depth
 63    }
 64
 65    /// Returns the value of the current depth.
 66    pub const fn value(&self) -> u64 {
 67        self.value
 68    }
 69
 70    /// Returns true if the current value fits the current depth for a binary tree.
 71    pub const fn is_valid(&self) -> bool {
 72        self.value < (1 << self.depth as u64)
 73    }
 74
 75    /// Returns true if the current instance points to a right sibling node.
 76    pub const fn is_value_odd(&self) -> bool {
 77        (self.value & 1) == 1
 78    }
 79
 80    /// Returns `true` if the depth is `0`.
 81    pub const fn is_root(&self) -> bool {
 82        self.depth == 0
 83    }
 84
 85    // STATE MUTATORS
 86    // --------------------------------------------------------------------------------------------
 87
 88    /// Traverse one level towards the root, decrementing the depth by `1`.
 89    pub fn move_up(&mut self) -> &mut Self {
 90        self.depth = self.depth.saturating_sub(1);
 91        self.value >>= 1;
 92        self
 93    }
 94}
 95
 96#[cfg(test)]
 97mod tests {
 98    use super::*;
 99    use proptest::prelude::*;
100
101    proptest! {
102        #[test]
103        fn arbitrary_index_wont_panic_on_move_up(
104            depth in prop::num::u8::ANY,
105            value in prop::num::u64::ANY,
106            count in prop::num::u8::ANY,
107        ) {
108            let mut index = NodeIndex::new(depth, value);
109            for _ in 0..count {
110                index.move_up();
111            }
112        }
113    }
114}