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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

use crate::prelude::*;

/// The hash of the most-recently-inserted item, stored at the tip of the frontier.
#[derive(Debug, Clone, Copy, Derivative, Serialize, Deserialize)]
pub struct Item {
    item: Insert<(StateCommitment, Hash)>,
}

impl From<StateCommitment> for Item {
    fn from(commitment: StateCommitment) -> Self {
        Self {
            item: Insert::Keep((commitment, Hash::of(commitment))),
        }
    }
}

impl From<Hash> for Item {
    fn from(hash: Hash) -> Self {
        Self {
            item: Insert::Hash(hash),
        }
    }
}

impl GetHash for Item {
    #[inline]
    fn hash(&self) -> Hash {
        match self.item {
            Insert::Hash(hash) => hash,
            Insert::Keep((_, hash)) => hash,
        }
    }

    #[inline]
    fn cached_hash(&self) -> Option<Hash> {
        Some(self.hash())
    }
}

impl Height for Item {
    type Height = Zero;
}

impl Focus for Item {
    type Complete = complete::Item;

    #[inline]
    fn finalize_owned(self) -> Insert<Self::Complete> {
        self.item
            .map(|(commitment, hash)| complete::Item::new(hash, commitment))
    }
}

impl Witness for Item {
    #[inline]
    fn witness(&self, index: impl Into<u64>) -> Option<(AuthPath<Self>, Hash)> {
        debug_assert_eq!(index.into(), 0, "non-zero index when witnessing leaf");
        Some((path::Leaf, self.hash()))
    }
}

impl GetPosition for Item {
    #[inline]
    fn position(&self) -> Option<u64> {
        None
    }
}

impl Forget for Item {
    #[inline]
    fn forget(&mut self, _forgotten: Option<Forgotten>, index: impl Into<u64>) -> bool {
        if index.into() == 0 {
            if let Insert::Keep((_, hash)) = self.item {
                self.item = Insert::Hash(hash);
                true
            } else {
                false
            }
        } else {
            panic!("non-zero index when forgetting item");
        }
    }
}

impl<'tree> structure::Any<'tree> for Item {
    fn kind(&self) -> Kind {
        Kind::Leaf {
            commitment: self.item.keep().map(|(commitment, _)| commitment),
        }
    }

    fn forgotten(&self) -> Forgotten {
        Forgotten::default()
    }

    fn children(&self) -> Vec<HashOrNode<'tree>> {
        vec![]
    }
}

impl OutOfOrder for Item {
    fn uninitialized(_position: Option<u64>, _forgotten: Forgotten) -> Self {
        Self {
            item: Insert::Hash(Hash::uninitialized()),
        }
    }

    fn uninitialized_out_of_order_insert_commitment(
        &mut self,
        index: u64,
        commitment: StateCommitment,
    ) {
        if index == 0 {
            let hash = match self.item {
                Insert::Keep((_drop_old_commitment, hash)) => hash,
                Insert::Hash(hash) => hash,
            };
            self.item = Insert::Keep((commitment, hash));
        } else {
            panic!("non-zero index when inserting commitment");
        }
    }
}

impl UncheckedSetHash for Item {
    fn unchecked_set_hash(&mut self, index: u64, height: u8, hash: Hash) {
        if index != 0 {
            panic!("non-zero index when setting hash");
        }
        if height != 0 {
            panic!("non-zero height when setting hash");
        }
        self.item = match self.item {
            Insert::Keep((commitment, _drop_old_hash)) => Insert::Keep((commitment, hash)),
            Insert::Hash(_drop_old_hash) => Insert::Hash(hash),
        }
    }

    fn finish_initialize(&mut self) {
        match self.item {
            Insert::Keep((commitment, ref mut hash)) => {
                if hash.is_uninitialized() {
                    *hash = Hash::of(commitment);
                }
            }
            Insert::Hash(ref mut hash) => {
                if hash.is_uninitialized() {
                    // An uninitialized frontier hash should be set to the zero hash, which is the
                    // empty hash for the frontier
                    *hash = Hash::zero();
                }
            }
        }
    }
}