fuel_merkle/common/position.rs
1use crate::common::{
2 node::{
3 ChildKeyResult,
4 Node,
5 ParentNode,
6 },
7 Bytes8,
8 PositionPath,
9};
10use core::convert::Infallible;
11
12use super::{
13 node::{
14 ChildError,
15 ChildResult,
16 },
17 path::Side,
18};
19
20/// # Position
21///
22/// A `Position` represents a node's position in a binary tree by encapsulating
23/// the node's index data. Indices are calculated through in-order traversal of
24/// the nodes, starting with the first leaf node. Indexing starts at 0.
25///
26/// Merkle Trees
27///
28/// In the context of Merkle trees, trees are constructed "upwards" from leaf
29/// nodes. Therefore, indexing is done from the bottom up, starting with the
30/// leaves, rather than top down, starting with the root, and we can guarantee a
31/// deterministic construction of index data.
32///
33/// ```text
34/// 07
35/// / \
36/// / \
37/// / \
38/// / \
39/// / \
40/// / \
41/// 03 11
42/// / \ / \
43/// / \ / \
44/// 01 05 09 13
45/// / \ / \ / \ / \
46/// 00 02 04 06 08 10 12 14
47/// ```
48///
49/// In-order indices can be considered internal to the `Position` struct and are
50/// used to facilitate the calculation of positional attributes and the
51/// construction of other nodes. Leaf nodes have both an in-order index as part
52/// of the tree, and a leaf index determined by its position in the bottom row.
53/// Because of the in-order traversal used to calculate the in-order indices,
54/// leaf nodes have the property that their in-order index is always equal to
55/// their leaf index multiplied by 2.
56///
57/// ```text
58/// / \ / \ / \ / \
59/// Leaf indices: 00 01 02 03 04 05 06 07
60/// In-order indices: 00 02 04 06 08 10 12 14
61/// ```
62///
63/// This allows us to construct a `Position` (and its in-order index) by
64/// providing either an in-order index directly or, in the case of a leaf, a
65/// leaf index. This functionality is captured by `from_in_order_index()` and
66/// `from_leaf_index()` respectively.
67///
68/// Traversal of a Merkle Tree can be performed by the methods on a given
69/// `Position` to retrieve its sibling, parent, or uncle `Position`.
70///
71/// Merkle Mountain Ranges
72///
73/// Because the `Position` indices are calculated from in-order traversal
74/// starting with the leaves, the deterministic quality of the indices holds
75/// true for imbalanced binary trees, including Merkle Mountain Ranges. Consider
76/// the following binary tree construction composed of seven leaves (with leaf
77/// indices 0 through 6):
78///
79/// ```text
80/// 03
81/// / \
82/// / \
83/// 01 05 09
84/// / \ / \ / \
85/// 00 02 04 06 08 10 12
86/// ```
87///
88/// Note the absence of internal nodes that would be present in a fully balanced
89/// tree: inner nodes with indices 7 and 11 are absent. This is owing to the
90/// fact that node indices are calculated deterministically through in-order
91/// traversal, not calculated as a sequence.
92///
93/// Traversal of a Merkle Mountain Range is still done in the same manner as a
94/// balanced Merkle tree, using methods to retrieve a `Position's` sibling,
95/// parent, or uncle `Position`. However, in such cases, the corresponding
96/// sibling or uncle nodes are not guaranteed to exist in the tree.
97#[derive(Copy, Clone, Debug, PartialEq, Eq)]
98#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
99pub struct Position(u64);
100
101impl Position {
102 pub fn in_order_index(self) -> u64 {
103 self.0
104 }
105
106 pub fn leaf_index(self) -> u64 {
107 assert!(self.is_leaf());
108 self.in_order_index() / 2
109 }
110
111 /// Construct a position from an in-order index.
112 pub fn from_in_order_index(index: u64) -> Self {
113 Position(index)
114 }
115
116 /// Construct a position from a leaf index. The in-order index corresponding
117 /// to the leaf index will always equal the leaf index multiplied by 2.
118 /// Panics if index is too large to fit into u64.
119 pub fn from_leaf_index(index: u64) -> Option<Self> {
120 Some(Position(index.checked_mul(2)?))
121 }
122
123 #[cfg(test)]
124 pub(crate) fn from_leaf_index_unwrap(index: u64) -> Self {
125 Self::from_leaf_index(index).expect("Index too large")
126 }
127
128 /// The parent position.
129 /// The parent position has a height less 1 relative to this position.
130 pub fn parent(self) -> Result<Self, GetNodeError> {
131 let shift = 1u64
132 .checked_shl(self.height())
133 .ok_or(GetNodeError::CannotExist)?;
134 let this = self.in_order_index();
135 Ok(Self::from_in_order_index(match self.orientation()? {
136 Side::Left => this.checked_sub(shift).ok_or(GetNodeError::CannotExist)?,
137 Side::Right => this.checked_add(shift).ok_or(GetNodeError::CannotExist)?,
138 }))
139 }
140
141 /// The sibling position.
142 /// A position shares the same parent and height as its sibling.
143 #[cfg(test)]
144 pub fn sibling(self) -> Result<Self, GetNodeError> {
145 #[allow(clippy::arithmetic_side_effects)] // height() <= 64
146 let shift = 1u64
147 .checked_shl(self.height() + 1)
148 .ok_or(GetNodeError::CannotExist)?;
149 let this = self.in_order_index();
150 Ok(Self::from_in_order_index(match self.orientation()? {
151 Side::Left => this.checked_sub(shift).ok_or(GetNodeError::CannotExist)?,
152 Side::Right => this.checked_add(shift).ok_or(GetNodeError::CannotExist)?,
153 }))
154 }
155
156 /// The uncle position.
157 /// The uncle position is the sibling of the parent and has a height less 1
158 /// relative to this position.
159 #[cfg(test)]
160 pub fn uncle(self) -> Result<Self, GetNodeError> {
161 self.parent()?.sibling()
162 }
163
164 /// The child position of the current position given by the direction.
165 /// A child position has a height less 1 than the current position.
166 ///
167 /// A child position is calculated as a function of the current position's
168 /// index and height, and the supplied direction. The left child
169 /// position has the in-order index arriving before the current index;
170 /// the right child position has the in-order index arriving after the
171 /// current index.
172 pub fn child(self, side: Side) -> Result<Self, GetNodeError> {
173 if !self.is_node() {
174 return Err(GetNodeError::IsLeaf);
175 }
176 let shift = 1u64
177 .checked_shl(
178 self.height()
179 .checked_sub(1)
180 .ok_or(GetNodeError::CannotExist)?,
181 )
182 .ok_or(GetNodeError::CannotExist)?;
183 let this = self.in_order_index();
184 Ok(Self::from_in_order_index(match side {
185 Side::Left => this.checked_sub(shift).ok_or(GetNodeError::CannotExist)?,
186 Side::Right => this.checked_add(shift).ok_or(GetNodeError::CannotExist)?,
187 }))
188 }
189
190 /// Returns the left child of the current position.
191 pub fn left_child(self) -> Result<Self, GetNodeError> {
192 self.child(Side::Left)
193 }
194
195 /// Returns the right child of the current position.
196 pub fn right_child(self) -> Result<Self, GetNodeError> {
197 self.child(Side::Right)
198 }
199
200 /// The height of the index in a binary tree.
201 /// Leaf nodes represent height 0. A leaf's parent represents height 1.
202 /// Height values monotonically increase as you ascend the tree.
203 ///
204 /// Height is deterministically calculated as the number of trailing zeros
205 /// of the complement of the position's index. The following table
206 /// demonstrates the relationship between a position's height and the
207 /// trailing zeros.
208 ///
209 /// | Index (Dec) | Index (Bin) | !Index (Bin) | Trailing 0s | Height |
210 /// |-------------|-------------|--------------|-------------|--------|
211 /// | 0 | 0000 | 1111 | 0 | 0 |
212 /// | 2 | 0010 | 1101 | 0 | 0 |
213 /// | 4 | 0100 | 1011 | 0 | 0 |
214 /// | 1 | 0001 | 1110 | 1 | 1 |
215 /// | 5 | 0101 | 1010 | 1 | 1 |
216 /// | 9 | 1001 | 0110 | 1 | 1 |
217 /// | 3 | 0011 | 1100 | 2 | 2 |
218 /// | 11 | 1011 | 0100 | 2 | 2 |
219 pub fn height(self) -> u32 {
220 (!self.in_order_index()).trailing_zeros()
221 }
222
223 /// Whether or not this position represents a leaf node.
224 /// Returns `true` if the position is a leaf node.
225 /// Returns `false` if the position is an internal node.
226 ///
227 /// A position is a leaf node if and only if its in-order index is even. A
228 /// position is an internal node if and only if its in-order index is
229 /// odd.
230 pub fn is_leaf(self) -> bool {
231 self.in_order_index() % 2 == 0
232 }
233
234 /// Whether or not this position represents an internal node.
235 /// Returns `false` if the position is a leaf node.
236 /// Returns `true` if the position is an internal node.
237 ///
238 /// When a position is an internal node, the position will have both a left
239 /// and right child.
240 pub fn is_node(self) -> bool {
241 !self.is_leaf()
242 }
243
244 /// Given a leaf position and the total count of leaves in a tree, get the
245 /// path from this position to the given leaf position. The shape of the
246 /// tree is defined by the `leaves_count` parameter and constrains the
247 /// path. See [PositionPath](crate::common::PositionPath).
248 pub fn path(self, leaf: &Self, leaves_count: u64) -> PositionPath {
249 debug_assert!(leaves_count > 0);
250 PositionPath::new(self, *leaf, leaves_count)
251 }
252
253 /// Orientation of the position index relative to its parent.
254 ///
255 /// The orientation is determined by the reading the `n`th rightmost digit
256 /// of the index's binary value, where `n` = the height of the position
257 /// `+ 1`. The following table demonstrates the relationships between a
258 /// position's index, height, and orientation.
259 ///
260 /// | Index (Dec) | Index (Bin) | Height | Orientation |
261 /// |-------------|-------------|--------|-------------|
262 /// | 0 | 0000 | 0 | L |
263 /// | 2 | 0010 | 0 | R |
264 /// | 4 | 0100 | 0 | L |
265 /// | 6 | 0110 | 0 | R |
266 /// | 1 | 0001 | 1 | L |
267 /// | 5 | 0101 | 1 | R |
268 /// | 9 | 1001 | 1 | L |
269 /// | 13 | 1101 | 1 | R |
270 fn orientation(self) -> Result<Side, GetNodeError> {
271 #[allow(clippy::arithmetic_side_effects)] // height() <= 64
272 let shift = 1u64
273 .checked_shl(self.height() + 1)
274 .ok_or(GetNodeError::CannotExist)?;
275 Ok(match self.in_order_index() & shift {
276 0 => Side::Right,
277 _ => Side::Left,
278 })
279 }
280}
281
282impl Node for Position {
283 type Key = Bytes8;
284
285 fn height(&self) -> u32 {
286 Position::height(*self)
287 }
288
289 #[allow(clippy::arithmetic_side_effects, clippy::cast_possible_truncation)] // const
290 fn key_size_bits() -> u32 {
291 core::mem::size_of::<Self::Key>() as u32 * 8
292 }
293
294 fn leaf_key(&self) -> Self::Key {
295 Position::leaf_index(*self).to_be_bytes()
296 }
297
298 fn is_leaf(&self) -> bool {
299 Position::is_leaf(*self)
300 }
301
302 fn is_node(&self) -> bool {
303 Position::is_node(*self)
304 }
305}
306
307#[derive(Debug, Clone, Copy, PartialEq, Eq)]
308pub enum GetNodeError {
309 /// The operation requires a node that can have children.
310 /// This is a leaf, and cannot have children.
311 IsLeaf,
312 /// The requested node cannot exists as it would be out of bounds.
313 CannotExist,
314}
315
316impl ParentNode for Position {
317 type ChildKey = u64;
318 type Error = Infallible;
319
320 fn key(&self) -> Self::ChildKey {
321 self.in_order_index()
322 }
323
324 fn left_child(&self) -> ChildResult<Self> {
325 match self.child(Side::Left) {
326 Ok(child) => Ok(child),
327 Err(GetNodeError::IsLeaf) => Err(ChildError::NodeIsLeaf),
328 Err(GetNodeError::CannotExist) => Err(ChildError::ChildCannotExist),
329 }
330 }
331
332 fn left_child_key(&self) -> ChildKeyResult<Self> {
333 ParentNode::left_child(self).map(|child| child.in_order_index())
334 }
335
336 fn right_child(&self) -> ChildResult<Self> {
337 match self.child(Side::Right) {
338 Ok(child) => Ok(child),
339 Err(GetNodeError::IsLeaf) => Err(ChildError::NodeIsLeaf),
340 Err(GetNodeError::CannotExist) => Err(ChildError::ChildCannotExist),
341 }
342 }
343
344 fn right_child_key(&self) -> ChildKeyResult<Self> {
345 ParentNode::right_child(self).map(|child| child.in_order_index())
346 }
347}
348
349#[cfg(test)]
350mod test {
351 use super::*;
352
353 #[test]
354 fn test_from_in_order_index() {
355 assert_eq!(Position::from_in_order_index(0).in_order_index(), 0);
356 assert_eq!(Position::from_in_order_index(1).in_order_index(), 1);
357 assert_eq!(Position::from_in_order_index(!0u64).in_order_index(), !0u64);
358 }
359
360 #[test]
361 fn test_from_leaf_index_unwrap() {
362 assert_eq!(Position::from_leaf_index_unwrap(0).in_order_index(), 0);
363 assert_eq!(Position::from_leaf_index_unwrap(1).in_order_index(), 2);
364 assert_eq!(
365 Position::from_leaf_index_unwrap((!0u64) >> 1).in_order_index(),
366 !0u64 - 1
367 );
368 }
369
370 #[test]
371 fn test_equality_returns_true_for_two_equal_positions() {
372 assert_eq!(Position(0), Position(0));
373 assert_eq!(Position::from_in_order_index(0), Position(0));
374 assert_eq!(Position::from_leaf_index_unwrap(1), Position(2));
375 }
376
377 #[test]
378 fn test_equality_returns_false_for_two_unequal_positions() {
379 assert_ne!(Position(0), Position(1));
380 assert_ne!(Position::from_in_order_index(0), Position(1));
381 assert_ne!(Position::from_leaf_index_unwrap(0), Position(2));
382 }
383
384 #[test]
385 fn test_height() {
386 assert_eq!(Position(0).height(), 0);
387 assert_eq!(Position(2).height(), 0);
388 assert_eq!(Position(4).height(), 0);
389
390 assert_eq!(Position(1).height(), 1);
391 assert_eq!(Position(5).height(), 1);
392 assert_eq!(Position(9).height(), 1);
393
394 assert_eq!(Position(3).height(), 2);
395 assert_eq!(Position(11).height(), 2);
396 assert_eq!(Position(19).height(), 2);
397 }
398
399 #[test]
400 fn test_sibling() {
401 assert_eq!(Position(0).sibling(), Ok(Position(2)));
402 assert_eq!(Position(2).sibling(), Ok(Position(0)));
403
404 assert_eq!(Position(1).sibling(), Ok(Position(5)));
405 assert_eq!(Position(5).sibling(), Ok(Position(1)));
406
407 assert_eq!(Position(3).sibling(), Ok(Position(11)));
408 assert_eq!(Position(11).sibling(), Ok(Position(3)));
409 }
410
411 #[test]
412 fn test_parent() {
413 assert_eq!(Position(0).parent(), Ok(Position(1)));
414 assert_eq!(Position(2).parent(), Ok(Position(1)));
415
416 assert_eq!(Position(1).parent(), Ok(Position(3)));
417 assert_eq!(Position(5).parent(), Ok(Position(3)));
418
419 assert_eq!(Position(3).parent(), Ok(Position(7)));
420 assert_eq!(Position(11).parent(), Ok(Position(7)));
421 }
422
423 #[test]
424 fn test_uncle() {
425 assert_eq!(Position(0).uncle(), Ok(Position(5)));
426 assert_eq!(Position(2).uncle(), Ok(Position(5)));
427 assert_eq!(Position(4).uncle(), Ok(Position(1)));
428 assert_eq!(Position(6).uncle(), Ok(Position(1)));
429
430 assert_eq!(Position(1).uncle(), Ok(Position(11)));
431 assert_eq!(Position(5).uncle(), Ok(Position(11)));
432 assert_eq!(Position(9).uncle(), Ok(Position(3)));
433 assert_eq!(Position(13).uncle(), Ok(Position(3)));
434 }
435
436 #[test]
437 fn test_left_child() {
438 assert_eq!(Position(7).left_child(), Ok(Position(3)));
439 assert_eq!(Position(3).left_child(), Ok(Position(1)));
440 assert_eq!(Position(1).left_child(), Ok(Position(0)));
441 assert_eq!(Position(11).left_child(), Ok(Position(9)));
442 assert_eq!(Position(9).left_child(), Ok(Position(8)));
443 }
444
445 #[test]
446 fn test_right_child() {
447 assert_eq!(Position(7).right_child(), Ok(Position(11)));
448 assert_eq!(Position(3).right_child(), Ok(Position(5)));
449 assert_eq!(Position(1).right_child(), Ok(Position(2)));
450 assert_eq!(Position(11).right_child(), Ok(Position(13)));
451 assert_eq!(Position(9).right_child(), Ok(Position(10)));
452 }
453
454 #[test]
455 fn test_is_leaf() {
456 assert_eq!(Position(0).is_leaf(), true);
457 assert_eq!(Position(2).is_leaf(), true);
458 assert_eq!(Position(4).is_leaf(), true);
459 assert_eq!(Position(6).is_leaf(), true);
460
461 assert_eq!(Position(1).is_leaf(), false);
462 assert_eq!(Position(5).is_leaf(), false);
463 assert_eq!(Position(9).is_leaf(), false);
464 assert_eq!(Position(13).is_leaf(), false);
465 }
466
467 #[test]
468 fn test_is_node() {
469 assert_eq!(Position(0).is_node(), false);
470 assert_eq!(Position(2).is_node(), false);
471 assert_eq!(Position(4).is_node(), false);
472 assert_eq!(Position(6).is_node(), false);
473
474 assert_eq!(Position(1).is_node(), true);
475 assert_eq!(Position(5).is_node(), true);
476 assert_eq!(Position(9).is_node(), true);
477 assert_eq!(Position(13).is_node(), true);
478 }
479}