zcash_history/
tree.rs

1use alloc::collections::BTreeMap;
2use alloc::vec::Vec;
3
4use crate::{Entry, EntryKind, EntryLink, Error, Version};
5
6/// Represents partially loaded tree.
7///
8/// Some kind of "view" into the array representation of the MMR tree.
9/// With only some of the leaves/nodes pre-loaded / pre-generated.
10/// Exact amount of the loaded data can be calculated by the constructing party,
11/// depending on the length of the tree and maximum amount of operations that are going
12/// to happen after construction. `Tree` should not be used as self-contained data structure,
13/// since it's internal state can grow indefinitely after serial operations.
14/// Intended use of this `Tree` is to instantiate it based on partially loaded data (see example
15/// how to pick right nodes from the array representation of MMR Tree), perform several operations
16/// (append-s/delete-s) and then drop it.
17pub struct Tree<V: Version> {
18    stored: BTreeMap<u32, Entry<V>>,
19
20    // This can grow indefinitely if `Tree` is misused as a self-contained data structure
21    generated: Vec<Entry<V>>,
22
23    // number of persistent(!) tree entries
24    stored_count: u32,
25
26    root: EntryLink,
27}
28
29impl<V: Version> Tree<V> {
30    /// Resolve link originated from this tree
31    pub fn resolve_link(&self, link: EntryLink) -> Result<IndexedNode<'_, V>, Error> {
32        match link {
33            EntryLink::Generated(index) => self.generated.get(index as usize),
34            EntryLink::Stored(index) => self.stored.get(&index),
35        }
36        .map(|node| IndexedNode { node, link })
37        .ok_or(Error::ExpectedInMemory(link))
38    }
39
40    fn push(&mut self, data: Entry<V>) -> EntryLink {
41        let idx = self.stored_count;
42        self.stored_count += 1;
43        self.stored.insert(idx, data);
44        EntryLink::Stored(idx)
45    }
46
47    fn push_generated(&mut self, data: Entry<V>) -> EntryLink {
48        self.generated.push(data);
49        EntryLink::Generated(self.generated.len() as u32 - 1)
50    }
51
52    /// Populate tree with plain list of the leaves/nodes. For now, only for tests,
53    /// since this `Tree` structure is for partially loaded tree (but it might change)
54    #[cfg(test)]
55    pub fn populate(loaded: Vec<Entry<V>>, root: EntryLink) -> Self {
56        let mut result = Tree::invalid();
57        result.stored_count = loaded.len() as u32;
58        for (idx, item) in loaded.into_iter().enumerate() {
59            result.stored.insert(idx as u32, item);
60        }
61        result.root = root;
62
63        result
64    }
65
66    // Empty tree with invalid root
67    fn invalid() -> Self {
68        Tree {
69            root: EntryLink::Generated(0),
70            generated: Default::default(),
71            stored: Default::default(),
72            stored_count: 0,
73        }
74    }
75
76    /// New view into the tree array representation
77    ///
78    /// `length` is total length of the array representation (is generally not a sum of
79    ///     peaks.len + extra.len)
80    /// `peaks` is peaks of the mmr tree
81    /// `extra` is some extra nodes that calculated to be required during next one or more
82    /// operations on the tree.
83    ///
84    /// # Panics
85    ///
86    /// Will panic if `peaks` is empty.
87    pub fn new(length: u32, peaks: Vec<(u32, Entry<V>)>, extra: Vec<(u32, Entry<V>)>) -> Self {
88        assert!(!peaks.is_empty());
89
90        let mut result = Tree::invalid();
91
92        result.stored_count = length;
93
94        let mut root = EntryLink::Stored(peaks[0].0);
95        for (r#gen, (idx, node)) in peaks.into_iter().enumerate() {
96            result.stored.insert(idx, node);
97            if r#gen != 0 {
98                let next_generated = combine_nodes(
99                    result
100                        .resolve_link(root)
101                        .expect("Inserted before, cannot fail; qed"),
102                    result
103                        .resolve_link(EntryLink::Stored(idx))
104                        .expect("Inserted before, cannot fail; qed"),
105                );
106                root = result.push_generated(next_generated);
107            }
108        }
109
110        for (idx, node) in extra {
111            result.stored.insert(idx, node);
112        }
113
114        result.root = root;
115
116        result
117    }
118
119    pub(crate) fn get_peaks(
120        &self,
121        root: EntryLink,
122        target: &mut Vec<EntryLink>,
123    ) -> Result<(), Error> {
124        let (left_child_link, right_child_link) = {
125            let root = self.resolve_link(root)?;
126            if root.node.complete() {
127                target.push(root.link);
128                return Ok(());
129            }
130            (root.left()?, root.right()?)
131        };
132
133        self.get_peaks(left_child_link, target)?;
134        self.get_peaks(right_child_link, target)?;
135        Ok(())
136    }
137
138    /// Append one leaf to the tree.
139    ///
140    /// Returns links to actual nodes that has to be persisted as the result of the append.
141    /// If completed without error, at least one link to the appended
142    /// node (with metadata provided in `new_leaf`) will be returned.
143    pub fn append_leaf(&mut self, new_leaf: V::NodeData) -> Result<Vec<EntryLink>, Error> {
144        let root = self.root;
145        let new_leaf_link = self.push(Entry::new_leaf(new_leaf));
146        let mut appended = vec![new_leaf_link];
147
148        let mut peaks = Vec::new();
149        self.get_peaks(root, &mut peaks)?;
150
151        let mut merge_stack = vec![new_leaf_link];
152
153        // Scan the peaks right-to-left, merging together equal-sized adjacent
154        // complete subtrees. After this, merge_stack only contains peaks of
155        // unequal-sized subtrees.
156        while let Some(next_peak) = peaks.pop() {
157            let next_merge = merge_stack
158                .pop()
159                .expect("there should be at least one, initial or re-pushed");
160
161            if let Some(stored) = {
162                let peak = self.resolve_link(next_peak)?;
163                let m = self.resolve_link(next_merge)?;
164                if peak.node.leaf_count() == m.node.leaf_count() {
165                    Some(combine_nodes(peak, m))
166                } else {
167                    None
168                }
169            } {
170                let link = self.push(stored);
171                merge_stack.push(link);
172                appended.push(link);
173                continue;
174            } else {
175                merge_stack.push(next_merge);
176                merge_stack.push(next_peak);
177            }
178        }
179
180        let mut new_root = merge_stack
181            .pop()
182            .expect("Loop above cannot reduce the merge_stack");
183        // Scan the peaks left-to-right, producing new generated nodes that
184        // connect the subtrees
185        while let Some(next_child) = merge_stack.pop() {
186            new_root = self.push_generated(combine_nodes(
187                self.resolve_link(new_root)?,
188                self.resolve_link(next_child)?,
189            ))
190        }
191
192        self.root = new_root;
193
194        Ok(appended)
195    }
196
197    #[cfg(test)]
198    fn for_children<F: Fn(EntryLink, EntryLink)>(&self, node: EntryLink, f: F) {
199        let (left, right) = {
200            let link = self
201                .resolve_link(node)
202                .expect("Failed to resolve link in test");
203            (
204                link.left().expect("Failed to find node in test"),
205                link.right().expect("Failed to find node in test"),
206            )
207        };
208        f(left, right);
209    }
210
211    fn pop(&mut self) {
212        self.stored.remove(&(self.stored_count - 1));
213        self.stored_count -= 1;
214    }
215
216    /// Truncate one leaf from the end of the tree.
217    ///
218    /// Returns actual number of nodes that should be removed by the caller
219    /// from the end of the array representation.
220    pub fn truncate_leaf(&mut self) -> Result<u32, Error> {
221        let root = {
222            let (leaves, root_left_child) = {
223                let n = self.resolve_link(self.root)?;
224                (n.node.leaf_count(), n.node.left()?)
225            };
226            if leaves & 1 != 0 {
227                self.pop();
228                self.root = root_left_child;
229                return Ok(1);
230            } else {
231                self.resolve_link(self.root)?
232            }
233        };
234
235        let mut peaks = vec![root.left()?];
236        let mut subtree_root_link = root.right()?;
237        let mut truncated = 1;
238
239        loop {
240            let left_link = self.resolve_link(subtree_root_link)?.node;
241            if let EntryKind::Node(left, right) = left_link.kind {
242                peaks.push(left);
243                subtree_root_link = right;
244                truncated += 1;
245            } else {
246                if root.node.complete() {
247                    truncated += 1;
248                }
249                break;
250            }
251        }
252
253        let mut new_root = *peaks.first().expect("At lest 1 elements in peaks");
254
255        for next_peak in peaks.into_iter().skip(1) {
256            new_root = self.push_generated(combine_nodes(
257                self.resolve_link(new_root)?,
258                self.resolve_link(next_peak)?,
259            ));
260        }
261
262        for _ in 0..truncated {
263            self.pop();
264        }
265
266        self.root = new_root;
267
268        Ok(truncated)
269    }
270
271    /// Length of array representation of the tree.
272    pub fn len(&self) -> u32 {
273        self.stored_count
274    }
275
276    /// Link to the root node
277    pub fn root(&self) -> EntryLink {
278        self.root
279    }
280
281    /// Reference to the root node.
282    pub fn root_node(&self) -> Result<IndexedNode<'_, V>, Error> {
283        self.resolve_link(self.root)
284    }
285
286    /// If this tree is empty.
287    pub fn is_empty(&self) -> bool {
288        self.stored_count == 0
289    }
290}
291
292/// Reference to the node with link attached.
293#[derive(Debug)]
294pub struct IndexedNode<'a, V: Version> {
295    node: &'a Entry<V>,
296    link: EntryLink,
297}
298
299impl<V: Version> IndexedNode<'_, V> {
300    fn left(&self) -> Result<EntryLink, Error> {
301        self.node.left().map_err(|e| e.augment(self.link))
302    }
303
304    fn right(&self) -> Result<EntryLink, Error> {
305        self.node.right().map_err(|e| e.augment(self.link))
306    }
307
308    /// Reference to the entry struct.
309    pub fn node(&self) -> &Entry<V> {
310        self.node
311    }
312
313    /// Reference to the entry metadata.
314    pub fn data(&self) -> &V::NodeData {
315        &self.node.data
316    }
317
318    /// Actual link by what this node was resolved.
319    pub fn link(&self) -> EntryLink {
320        self.link
321    }
322}
323
324fn combine_nodes<'a, V: Version>(left: IndexedNode<'a, V>, right: IndexedNode<'a, V>) -> Entry<V> {
325    Entry {
326        kind: EntryKind::Node(left.link, right.link),
327        data: V::combine(&left.node.data, &right.node.data),
328    }
329}
330
331#[cfg(test)]
332mod tests {
333    use super::{Entry, EntryKind, EntryLink, Tree};
334    use crate::{NodeData, NodeDataV2, NodeDataV3, V2, V3, Version};
335
336    use assert_matches::assert_matches;
337    use proptest::prelude::*;
338
339    fn leaf(height: u32) -> NodeDataV2 {
340        NodeDataV2 {
341            v1: NodeData {
342                consensus_branch_id: 1,
343                subtree_commitment: [0u8; 32],
344                start_time: 0,
345                end_time: 0,
346                start_target: 0,
347                end_target: 0,
348                start_sapling_root: [0u8; 32],
349                end_sapling_root: [0u8; 32],
350                subtree_total_work: 0.into(),
351                start_height: height as u64,
352                end_height: height as u64,
353                sapling_tx: 7,
354            },
355            start_orchard_root: [0u8; 32],
356            end_orchard_root: [0u8; 32],
357            orchard_tx: 42,
358        }
359    }
360
361    fn ironwood_leaf(height: u32) -> NodeDataV3 {
362        NodeDataV3 {
363            v2: leaf(height),
364            start_ironwood_root: [height as u8; 32],
365            end_ironwood_root: [height as u8; 32],
366            ironwood_tx: u64::from(height),
367        }
368    }
369
370    fn initial() -> Tree<V2> {
371        let node1 = Entry::new_leaf(leaf(1));
372        let node2 = Entry::new_leaf(leaf(2));
373
374        let node3 = Entry {
375            data: V2::combine(&node1.data, &node2.data),
376            kind: EntryKind::Leaf,
377        };
378
379        Tree::populate(vec![node1, node2, node3], EntryLink::Stored(2))
380    }
381
382    // returns tree with specified number of leafs and it's root
383    fn generated(length: u32) -> Tree<V2> {
384        assert!(length >= 3);
385        let mut tree = initial();
386        for i in 2..length {
387            tree.append_leaf(leaf(i + 1)).expect("Failed to append");
388        }
389
390        tree
391    }
392
393    fn ironwood_initial() -> Tree<V3> {
394        let node1 = Entry::new_leaf(ironwood_leaf(1));
395        let node2 = Entry::new_leaf(ironwood_leaf(2));
396
397        let node3 = Entry {
398            data: V3::combine(&node1.data, &node2.data),
399            kind: EntryKind::Leaf,
400        };
401
402        Tree::populate(vec![node1, node2, node3], EntryLink::Stored(2))
403    }
404
405    #[test]
406    fn discrete_append() {
407        let mut tree = initial();
408
409        // ** APPEND 3 **
410        let appended = tree.append_leaf(leaf(3)).expect("Failed to append");
411        let new_root = tree.root_node().expect("Failed to resolve root").node;
412
413        // initial tree:  (2)
414        //               /   \
415        //             (0)   (1)
416        //
417        // new tree:
418        //                (4g)
419        //               /   \
420        //             (2)    \
421        //             /  \    \
422        //           (0)  (1)  (3)
423        //
424        // so only (3) is added as real leaf
425        // while new root, (4g) is generated one
426        assert_eq!(new_root.data.v1.end_height, 3);
427        assert_eq!(appended.len(), 1);
428
429        // ** APPEND 4 **
430        let appended = tree.append_leaf(leaf(4)).expect("Failed to append");
431
432        let new_root = tree.root_node().expect("Failed to resolve root").node;
433
434        // intermediate tree:
435        //                (4g)
436        //               /   \
437        //             (2)    \
438        //             /  \    \
439        //           (0)  (1)  (3)
440        //
441        // new tree:
442        //                 ( 6 )
443        //                /     \
444        //             (2)       (5)
445        //             /  \     /   \
446        //           (0)  (1) (3)   (4)
447        //
448        // so (4), (5), (6) are added as real leaves
449        // and new root, (6) is stored one
450        assert_eq!(new_root.data.v1.end_height, 4);
451        assert_eq!(appended.len(), 3);
452        assert_matches!(tree.root(), EntryLink::Stored(6));
453
454        // ** APPEND 5 **
455
456        let appended = tree.append_leaf(leaf(5)).expect("Failed to append");
457        let new_root = tree.root_node().expect("Failed to resolve root").node;
458
459        // intermediate tree:
460        //                 ( 6 )
461        //                /     \
462        //             (2)       (5)
463        //             /  \     /   \
464        //           (0)  (1) (3)   (4)
465        //
466        // new tree:
467        //                     ( 8g )
468        //                    /      \
469        //                 ( 6 )      \
470        //                /     \      \
471        //             (2)       (5)    \
472        //             /  \     /   \    \
473        //           (0)  (1) (3)   (4)  (7)
474        //
475        // so (7) is added as real leaf
476        // and new root, (8g) is generated one
477        assert_eq!(new_root.data.v1.end_height, 5);
478        assert_eq!(appended.len(), 1);
479        assert_matches!(tree.root(), EntryLink::Generated(_));
480        tree.for_children(tree.root(), |l, r| {
481            assert_matches!(l, EntryLink::Stored(6));
482            assert_matches!(r, EntryLink::Stored(7));
483        });
484
485        // *** APPEND #6 ***
486        let appended = tree.append_leaf(leaf(6)).expect("Failed to append");
487        let new_root = tree.root_node().expect("Failed to resolve root").node;
488
489        // intermediate tree:
490        //                     ( 8g )
491        //                    /      \
492        //                 ( 6 )      \
493        //                /     \      \
494        //             (2)       (5)    \
495        //             /  \     /   \    \
496        //           (0)  (1) (3)   (4)  (7)
497        //
498        // new tree:
499        //                     (---10g--)
500        //                    /          \
501        //                 ( 6 )          \
502        //                /     \          \
503        //             (2)       (5)       (9)
504        //             /  \     /   \     /   \
505        //           (0)  (1) (3)   (4)  (7)  (8)
506        //
507        // so (7) is added as real leaf
508        // and new root, (10g) is generated one
509        assert_eq!(new_root.data.v1.end_height, 6);
510        assert_eq!(appended.len(), 2);
511        assert_matches!(tree.root(), EntryLink::Generated(_));
512        tree.for_children(tree.root(), |l, r| {
513            assert_matches!(l, EntryLink::Stored(6));
514            assert_matches!(r, EntryLink::Stored(9));
515        });
516
517        // *** APPEND #7 ***
518
519        let appended = tree.append_leaf(leaf(7)).expect("Failed to append");
520        let new_root = tree.root_node().expect("Failed to resolve root").node;
521
522        // intermediate tree:
523        //                     (---8g---)
524        //                    /          \
525        //                 ( 6 )          \
526        //                /     \          \
527        //             (2)       (5)       (9)
528        //             /  \     /   \     /   \
529        //           (0)  (1) (3)   (4)  (7)  (8)
530        //
531        // new tree:
532        //                          (---12g--)
533        //                         /          \
534        //                    (---11g---)      \
535        //                   /           \      \
536        //                 ( 6 )          \      \
537        //                /     \          \      \
538        //             (2)       (5)       (9)     \
539        //             /  \     /   \     /   \     \
540        //           (0)  (1) (3)   (4) (7)   (8)  (10)
541        //
542        // so (10) is added as real leaf
543        // and new root, (12g) is generated one
544        assert_eq!(new_root.data.v1.end_height, 7);
545        assert_eq!(appended.len(), 1);
546        assert_matches!(tree.root(), EntryLink::Generated(_));
547        tree.for_children(tree.root(), |l, r| {
548            assert_matches!(l, EntryLink::Generated(_));
549            tree.for_children(l, |l, r| {
550                assert_matches!((l, r), (EntryLink::Stored(6), EntryLink::Stored(9)))
551            });
552            assert_matches!(r, EntryLink::Stored(10));
553        });
554    }
555
556    #[test]
557    fn truncate_simple() {
558        let mut tree = generated(9);
559        let total_truncated = tree.truncate_leaf().expect("Failed to truncate");
560
561        // initial tree:
562        //
563        //                               (-------16g------)
564        //                              /                  \
565        //                    (--------14-------)           \
566        //                   /                   \           \
567        //                 ( 6 )              (  13  )        \
568        //                /     \            /        \        \
569        //             (2)       (5)       (9)        (12)      \
570        //             /  \     /   \     /   \      /    \      \
571        //           (0)  (1) (3)   (4) (7)   (8)  (10)  (11)    (15)
572        //
573        // new tree:
574        //                    (--------14-------)
575        //                   /                   \
576        //                 ( 6 )              (  13  )
577        //                /     \            /        \
578        //             (2)       (5)       (9)        (12)
579        //             /  \     /   \     /   \      /    \
580        //           (0)  (1) (3)   (4) (7)   (8)  (10)  (11)
581        //
582        // so (15) is truncated
583        // and new root, (14) is a stored one now
584
585        assert_matches!(tree.root(), EntryLink::Stored(14));
586        assert_eq!(total_truncated, 1);
587        assert_eq!(tree.len(), 15);
588    }
589
590    #[test]
591    fn truncate_generated() {
592        let mut tree = generated(10);
593        let deleted = tree.truncate_leaf().expect("Failed to truncate");
594
595        // initial tree:
596        //
597        //                               (--------18g--------)
598        //                              /                     \
599        //                    (--------14-------)              \
600        //                   /                   \              \
601        //                 ( 6 )              (  13  )           \
602        //                /     \            /        \           \
603        //             (2)       (5)       (9)        (12)        (17)
604        //             /  \     /   \     /   \      /    \      /    \
605        //           (0)  (1) (3)   (4) (7)   (8)  (10)  (11)  (15)  (16)
606        //
607        // new tree:
608        //                               (-------16g------)
609        //                              /                  \
610        //                    (--------14-------)           \
611        //                   /                   \           \
612        //                 ( 6 )              (  13  )        \
613        //                /     \            /        \        \
614        //             (2)       (5)       (9)        (12)      \
615        //             /  \     /   \     /   \      /    \      \
616        //           (0)  (1) (3)   (4) (7)   (8)  (10)  (11)    (15)
617
618        // new root is generated
619
620        assert_matches!(tree.root(), EntryLink::Generated(_));
621
622        tree.for_children(tree.root(), |left, right| {
623            assert_matches!(
624                (left, right),
625                (EntryLink::Stored(14), EntryLink::Stored(15))
626            )
627        });
628
629        // two stored nodes should leave us (leaf 16 and no longer needed node 17)
630        assert_eq!(deleted, 2);
631        assert_eq!(tree.len(), 16);
632    }
633
634    #[test]
635    fn ironwood_version_append_and_truncate() {
636        let mut tree = ironwood_initial();
637
638        let appended = tree
639            .append_leaf(ironwood_leaf(3))
640            .expect("Failed to append");
641        let root = tree.root_node().expect("Failed to resolve root").node;
642
643        assert_eq!(appended.len(), 1);
644        assert_eq!(root.data.v2.v1.start_height, 1);
645        assert_eq!(root.data.v2.v1.end_height, 3);
646        assert_eq!(root.data.start_ironwood_root, [1; 32]);
647        assert_eq!(root.data.end_ironwood_root, [3; 32]);
648        assert_eq!(root.data.ironwood_tx, 6);
649
650        let truncated = tree.truncate_leaf().expect("Failed to truncate");
651        let root = tree.root_node().expect("Failed to resolve root").node;
652
653        assert_eq!(truncated, 1);
654        assert_eq!(root.data.v2.v1.start_height, 1);
655        assert_eq!(root.data.v2.v1.end_height, 2);
656        assert_eq!(root.data.start_ironwood_root, [1; 32]);
657        assert_eq!(root.data.end_ironwood_root, [2; 32]);
658        assert_eq!(root.data.ironwood_tx, 3);
659    }
660
661    #[test]
662    fn tree_len() {
663        let mut tree = initial();
664
665        assert_eq!(tree.len(), 3);
666
667        for i in 0..2 {
668            tree.append_leaf(leaf(i + 3)).expect("Failed to append");
669        }
670        assert_eq!(tree.len(), 7);
671
672        tree.truncate_leaf().expect("Failed to truncate");
673
674        assert_eq!(tree.len(), 4);
675    }
676
677    #[test]
678    fn tree_len_long() {
679        let mut tree = initial();
680
681        assert_eq!(tree.len(), 3);
682
683        for i in 0..4094 {
684            tree.append_leaf(leaf(i + 3)).expect("Failed to append");
685        }
686        assert_eq!(tree.len(), 8191); // 4096*2-1 (full tree)
687
688        for _ in 0..2049 {
689            tree.truncate_leaf().expect("Failed to truncate");
690        }
691
692        assert_eq!(tree.len(), 4083); // 4095 - log2(4096)
693    }
694
695    proptest! {
696        #[test]
697        fn prop_there_and_back(number in 0u32..=1024) {
698            let mut tree = initial();
699            for i in 0..number {
700                tree.append_leaf(leaf(i+3)).expect("Failed to append");
701            }
702            for _ in 0..number {
703                tree.truncate_leaf().expect("Failed to truncate");
704            }
705
706            assert_matches!(tree.root(), EntryLink::Stored(2));
707        }
708
709        #[test]
710        fn prop_leaf_count(number in 3u32..=1024) {
711            let mut tree = initial();
712            for i in 1..(number-1) {
713                tree.append_leaf(leaf(i+2)).expect("Failed to append");
714            }
715
716            assert_eq!(tree.root_node().expect("no root").node.leaf_count(), number as u64);
717        }
718
719        #[test]
720        fn prop_parity(number in 3u32..=2048) {
721            let mut tree = initial();
722            for i in 1..(number-1) {
723                tree.append_leaf(leaf(i+2)).expect("Failed to append");
724            }
725
726            if number & (number - 1) == 0 {
727                assert_matches!(tree.root(), EntryLink::Stored(_));
728            } else {
729                assert_matches!(tree.root(), EntryLink::Generated(_));
730            }
731        }
732
733        #[test]
734        fn prop_parity_with_truncate(
735            add_and_delete in (0u32..=2048).prop_flat_map(
736                |add| (Just(add), 0..=add)
737            )
738        ) {
739            let (add, delete) = add_and_delete;
740            // First we add `add` number of leaves, then delete `delete` number of leaves
741            // What is left should be consistent with generated-stored structure
742            let mut tree = initial();
743            for i in 0..add {
744                tree.append_leaf(leaf(i+3)).expect("Failed to append");
745            }
746            for _ in 0..delete {
747                tree.truncate_leaf().expect("Failed to truncate");
748            }
749
750            let total = add - delete + 2;
751
752            if total & (total - 1) == 0 {
753                assert_matches!(tree.root(), EntryLink::Stored(_));
754            } else {
755                assert_matches!(tree.root(), EntryLink::Generated(_));
756            }
757        }
758
759        #[test]
760        fn prop_stored_length(
761            add_and_delete in (0u32..=2048).prop_flat_map(
762                |add| (Just(add), 0..=add)
763            )
764        ) {
765            let (add, delete) = add_and_delete;
766            let mut tree = initial();
767            for i in 0..add {
768                tree.append_leaf(leaf(i+3)).expect("Failed to append");
769            }
770            for _ in 0..delete {
771                tree.truncate_leaf().expect("Failed to truncate");
772            }
773
774            let total = add - delete + 2;
775
776            assert!(total * total > tree.len())
777        }
778    }
779}
zcash_history/tree.rs

zcash_history/
tree.rs
