1use std::fmt::Debug;
23use serde::{Deserialize, Serialize};
45use crate::prelude::*;
67use frontier::tier::Nested;
89/// The frontier of the top level of some part of the commitment tree, which may be empty, but may
10/// not be finalized or hashed.
11#[derive(Derivative, Serialize, Deserialize)]
12#[derivative(
13 Debug(bound = "Item: Debug, Item::Complete: Debug"),
14 Clone(bound = "Item: Clone, Item::Complete: Clone")
15)]
16#[serde(bound(
17 serialize = "Item: Serialize, Item::Complete: Serialize",
18 deserialize = "Item: Deserialize<'de>, Item::Complete: Deserialize<'de>"
19))]
20pub struct Top<Item: Focus + Clone>
21where
22Item::Complete: Clone,
23{
24 track_forgotten: TrackForgotten,
25 inner: Option<Nested<Item>>,
26}
2728/// Whether or not to track forgotten elements of the tree.
29///
30/// This is set to `Yes` for trees, but to `No` for epoch and block builders, because when they are
31/// inserted all at once, there would be no meaning to their internal forgotten versions, and the
32/// tree wouldn't have known about any elements that were forgotten before the builder was inserted,
33/// so it doesn't need to track them.
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
35pub enum TrackForgotten {
36/// Do keep track of what things are forgotten.
37Yes,
38/// Do not keep track of what things are forgotten.
39No,
40}
4142impl<Item: Focus + Clone> Top<Item>
43where
44Item::Complete: Clone,
45{
46/// Create a new top-level frontier tier.
47#[allow(unused)]
48pub fn new(track_forgotten: TrackForgotten) -> Self {
49Self {
50 track_forgotten,
51 inner: None,
52 }
53 }
5455/// Insert an item or its hash into this frontier tier.
56 ///
57 /// If the tier is full, return the input item without inserting it.
58#[inline]
59pub fn insert(&mut self, item: Item) -> Result<(), Item> {
60// Temporarily replace the inside with `None` (it will get put back right away, this is just
61 // to satisfy the borrow checker)
62let inner = std::mem::take(&mut self.inner);
6364let (result, inner) = if let Some(inner) = inner {
65if inner.is_full() {
66// Don't even try inserting when we know it will fail: this means that there is *no
67 // implicit finalization* of the frontier, even when it is full
68(Err(item), inner)
69 } else {
70// If it's not full, then insert the item into it (which we know will succeed)
71let inner = inner
72 .insert_owned(item)
73 .unwrap_or_else(|_| panic!("frontier is not full, so insert must succeed"));
74 (Ok(()), inner)
75 }
76 } else {
77// If the tier was empty, create a new frontier containing only the inserted item
78let inner = Nested::new(item);
79 (Ok(()), inner)
80 };
8182// Put the inner back
83self.inner = Some(inner);
8485 result
86 }
8788/// Forgot the commitment at the given index.
89 ///
90 /// This isn't an implementation of [`Forget`] because unlike [`Forget`], this doesn't require
91 /// an input forgotten version, since it calculates it based on the forgotten versions at this
92 /// top level.
93#[inline]
94pub fn forget(&mut self, index: impl Into<u64>) -> bool
95where
96Item: Forget,
97 Item::Complete: ForgetOwned,
98 {
99let forgotten = self.forgotten();
100101if let Some(ref mut inner) = self.inner {
102 inner.forget(forgotten, index)
103 } else {
104false
105}
106 }
107108/// Count the number of times something has been forgotten from this tree.
109#[inline]
110pub fn forgotten(&self) -> Option<Forgotten> {
111if let TrackForgotten::Yes = self.track_forgotten {
112Some(
113self.inner
114 .iter()
115 .flat_map(|inner| inner.forgotten().iter().copied())
116 .max()
117 .unwrap_or_default(),
118 )
119 } else {
120None
121}
122 }
123124/// Update the currently focused `Item` (i.e. the most-recently-[`insert`](Self::insert)ed one),
125 /// returning the result of the function.
126 ///
127 /// If this top-level tier is empty or the most recently inserted item is a hash, returns
128 /// `None`.
129#[inline]
130pub fn update<T>(&mut self, f: impl FnOnce(&mut Item) -> T) -> Option<T> {
131self.inner.as_mut().and_then(|inner| inner.update(f))
132 }
133134/// Get a reference to the focused `Insert<Item>`, if there is one.
135 ///
136 /// If this top-level tier is empty or the focus is a hash, returns `None`.
137#[inline]
138pub fn focus(&self) -> Option<&Item> {
139if let Some(ref inner) = self.inner {
140 inner.focus()
141 } else {
142None
143}
144 }
145146/// Finalize the top tier into either a summary root hash or a complete tier.
147#[inline]
148pub fn finalize(self) -> Insert<complete::Top<Item::Complete>> {
149if let Some(inner) = self.inner {
150 inner.finalize_owned().map(|inner| complete::Top { inner })
151 } else {
152// The hash of an empty top-level tier is 1
153Insert::Hash(Hash::one())
154 }
155 }
156157/// Check whether this top-level tier is full.
158#[inline]
159pub fn is_full(&self) -> bool {
160if let Some(ref inner) = self.inner {
161 inner.is_full()
162 } else {
163false
164}
165 }
166167/// Check whether this top-level tier is empty.
168#[inline]
169pub fn is_empty(&self) -> bool {
170self.inner.is_none()
171 }
172}
173174impl<Item: Focus + Clone> Height for Top<Item>
175where
176Item::Complete: Clone,
177{
178type Height = <Nested<Item> as Height>::Height;
179}
180181impl<Item: Focus + GetPosition + Clone> GetPosition for Top<Item>
182where
183Item::Complete: Clone,
184{
185#[inline]
186fn position(&self) -> Option<u64> {
187if let Some(ref frontier) = self.inner {
188 frontier.position()
189 } else {
190Some(0)
191 }
192 }
193}
194195impl<Item: Focus + Clone> GetHash for Top<Item>
196where
197Item::Complete: Clone,
198{
199#[inline]
200fn hash(&self) -> Hash {
201if let Some(ref inner) = self.inner {
202 inner.hash()
203 } else {
204 Hash::zero()
205 }
206 }
207208#[inline]
209fn cached_hash(&self) -> Option<Hash> {
210if let Some(ref inner) = self.inner {
211 inner.cached_hash()
212 } else {
213Some(Hash::zero())
214 }
215 }
216}
217218impl<Item: Focus + Witness + Clone> Witness for Top<Item>
219where
220Item::Complete: Witness + Clone,
221{
222fn witness(&self, index: impl Into<u64>) -> Option<(AuthPath<Self>, Hash)> {
223if let Some(ref inner) = self.inner {
224 inner.witness(index)
225 } else {
226None
227}
228 }
229}
230231impl<'tree, Item: Focus + GetPosition + Height + structure::Any<'tree> + Clone>
232 structure::Any<'tree> for Top<Item>
233where
234Item::Complete: structure::Any<'tree> + Clone,
235{
236fn kind(&self) -> Kind {
237 Kind::Internal {
238 height: <Self as Height>::Height::HEIGHT,
239 }
240 }
241242fn forgotten(&self) -> Forgotten {
243self.forgotten().unwrap_or_default()
244 }
245246fn children(&'tree self) -> Vec<HashOrNode<'tree>> {
247self.inner
248 .as_ref()
249 .map(structure::Any::children)
250 .unwrap_or_default()
251 }
252}
253254impl<Item: Focus + Height + OutOfOrder + Clone> OutOfOrder for Top<Item>
255where
256Item::Complete: OutOfOrderOwned + Clone,
257{
258fn uninitialized(position: Option<u64>, forgotten: Forgotten) -> Self {
259let inner = if position == Some(0) {
260// If the position is zero, there's no frontier to manifest
261None
262} else {
263// Otherwise, create a frontier
264Some(Nested::uninitialized(position, forgotten))
265 };
266267Self {
268 inner,
269// Track forgotten things by default (we only deserialize entire full trees, which
270 // always have this flipped on)
271track_forgotten: TrackForgotten::Yes,
272 }
273 }
274275fn uninitialized_out_of_order_insert_commitment(
276&mut self,
277 index: u64,
278 commitment: StateCommitment,
279 ) {
280if let Some(ref mut inner) = self.inner {
281 inner.uninitialized_out_of_order_insert_commitment(index, commitment);
282 }
283 }
284}
285286impl<Item: Focus + Height + UncheckedSetHash + Clone> UncheckedSetHash for Top<Item>
287where
288Item::Complete: UncheckedSetHash + Clone,
289{
290fn unchecked_set_hash(&mut self, index: u64, height: u8, hash: Hash) {
291if let Some(ref mut inner) = self.inner {
292 inner.unchecked_set_hash(index, height, hash);
293 }
294 }
295296fn finish_initialize(&mut self) {
297if let Some(ref mut inner) = self.inner {
298 inner.finish_initialize();
299 }
300 }
301}
302303#[cfg(test)]
304mod test {
305use super::*;
306307#[test]
308fn position_advances_by_one() {
309let mut top: Top<Item> = Top::new(TrackForgotten::No);
310for expected_position in 0..=(u16::MAX as u64) {
311assert_eq!(top.position(), Some(expected_position));
312 top.insert(Hash::zero().into()).unwrap();
313 }
314assert_eq!(top.position(), None);
315 }
316}