zcash_history/
tree.rs

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

zcash_history/
tree.rs
