milhouse 0.9.0

Persistent binary merkle tree
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

use crate::tests::proptest::Large;
use crate::{Arc, List, level_iter::LevelNode};
use tree_hash::Hash256;
use typenum::{U8, U32};

#[test]
fn level_iter_pop_front_basic_packed() {
    let vec = vec![10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
    let list = List::<u64, U32>::new(vec.clone()).unwrap();
    assert_eq!(list.len(), 11);

    for from in 4..vec.len() {
        let mut list = list.clone();
        for (i, level) in list.level_iter_from(from).unwrap().enumerate() {
            match level {
                LevelNode::PackedLeaf(leaf) => {
                    assert!(from.trailing_zeros() < 2, "from = {from}");
                    assert_eq!(*leaf, vec[i + from]);
                }
                LevelNode::Internal(node) => {
                    let level = if from == 0 { 5 } else { from.trailing_zeros() };
                    assert!(level >= 2);
                    assert!(node.compute_len() <= 1 << level);
                }
            }
        }

        list.pop_front(from).unwrap();
        assert_eq!(list.len(), vec.len() - from);
        assert_eq!(list.to_vec().as_slice(), &vec[from..]);
    }
}

#[test]
fn level_iter_pop_front_basic_packed_17() {
    let vec = vec![
        10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 0, 0, 0, 0, 0, 666,
    ];
    let list = List::<u64, U32>::new(vec.clone()).unwrap();
    assert_eq!(list.len(), 17);

    for from in 0..vec.len() {
        let mut list = list.clone();
        for (i, level) in list.level_iter_from(from).unwrap().enumerate() {
            match level {
                LevelNode::PackedLeaf(leaf) => {
                    assert!(from.trailing_zeros() < 2);
                    assert_eq!(*leaf, vec[i + from]);
                }
                LevelNode::Internal(node) => {
                    let level = if from == 0 { 5 } else { from.trailing_zeros() };
                    assert!(level >= 2);
                    assert!(node.compute_len() <= 1 << level);
                }
            }
        }

        list.pop_front(from).unwrap();
        assert_eq!(list.len(), vec.len() - from);
        assert_eq!(list.to_vec().as_slice(), &vec[from..]);
    }
}

#[test]
fn level_iter_pop_front_basic_large() {
    let vec = (0..7u8)
        .map(|i| Large {
            a: i as u64,
            b: i,
            c: Hash256::repeat_byte(i),
            d: List::empty(),
        })
        .collect::<Vec<_>>();
    let list = List::<Large, U8>::new(vec.clone()).unwrap();
    assert_eq!(list.len(), 7);

    for from in 0..vec.len() {
        let mut list = list.clone();
        list.pop_front(from).unwrap();
        assert_eq!(list.len(), vec.len() - from);
        assert_eq!(list.to_vec().as_slice(), &vec[from..]);
    }
}

#[test]
fn pop_front_zero_noop() {
    let vec = vec![10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
    let mut list = List::<u64, U32>::new(vec.clone()).unwrap();

    list.apply_updates().unwrap();
    let mut popped_list = list.clone();
    popped_list.pop_front(0).unwrap();

    for (a, b) in list
        .level_iter_from(0)
        .unwrap()
        .zip(popped_list.level_iter_from(0).unwrap())
    {
        let LevelNode::Internal(a) = a else {
            panic!("internal node expected")
        };
        let LevelNode::Internal(b) = b else {
            panic!("internal node expected")
        };
        assert!(Arc::ptr_eq(a, b));
    }
}