penumbra_sdk_tct/internal/complete/node/
children.rs

1//! Enumeration of the possible shapes of the children of a [`Node`](super::Node).
2//!
3//! Each complete node must have at least one child, but some other children may be missing because
4//! they have been pruned from the sparse tree.
5//!
6//! The reason for this enumeration is to save heap space in the case of many nodes: because
7//! different nodes can have different sizes, we save on average a few words of memory by placing
8//! the box inside each enum variant rather than outside the whole enum (which would end up
9//! occupying the space of its largest variant).
10
11#![allow(non_camel_case_types, clippy::upper_case_acronyms)]
12
13use std::{fmt::Debug, sync::Arc};
14
15mod shape;
16pub use shape::*;
17
18use crate::prelude::*;
19
20/// The children of a [`Node`](super::Node).
21#[derive(Clone, PartialEq, Eq, Serialize, Deserialize)]
22pub enum Children<Child> {
23    /// Children of a node having children in the positions: 3.
24    ___C(Arc<___C<Child>>),
25    /// Children of a node having children in the positions: 2.
26    __C_(Arc<__C_<Child>>),
27    /// Children of a node having children in the positions: 2, 3.
28    __CC(Arc<__CC<Child>>),
29    /// Children of a node having children in the positions: 1.
30    _C__(Arc<_C__<Child>>),
31    /// Children of a node having children in the positions: 1, 3.
32    _C_C(Arc<_C_C<Child>>),
33    /// Children of a node having children in the positions: 1, 2.
34    _CC_(Arc<_CC_<Child>>),
35    /// Children of a node having children in the positions: 1, 2, 3.
36    _CCC(Arc<_CCC<Child>>),
37    /// Children of a node having children in the positions: 0.
38    C___(Arc<C___<Child>>),
39    /// Children of a node having children in the positions: 0, 3.
40    C__C(Arc<C__C<Child>>),
41    /// Children of a node having children in the positions: 0, 2.
42    C_C_(Arc<C_C_<Child>>),
43    /// Children of a node having children in the positions: 0, 2, 3.
44    C_CC(Arc<C_CC<Child>>),
45    /// Children of a node having children in the positions: 0, 1.
46    CC__(Arc<CC__<Child>>),
47    /// Children of a node having children in the positions: 0, 1, 3.
48    CC_C(Arc<CC_C<Child>>),
49    /// Children of a node having children in the positions: 0, 1, 2.
50    CCC_(Arc<CCC_<Child>>),
51    /// Children of a node having children in the positions: 0, 1, 2, 3.
52    CCCC(Arc<CCCC<Child>>),
53}
54
55impl<Child: Debug + Clone> Debug for Children<Child> {
56    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
57        self.children().fmt(f)
58    }
59}
60
61impl<Child: Height> Height for Children<Child> {
62    type Height = Succ<<Child as Height>::Height>;
63}
64
65impl<Child: Height + GetHash + Clone> GetHash for Children<Child> {
66    fn hash(&self) -> Hash {
67        let [a, b, c, d] = self.children().map(|x| x.hash());
68        Hash::node(<Self as Height>::Height::HEIGHT, a, b, c, d)
69    }
70
71    fn cached_hash(&self) -> Option<Hash> {
72        None
73    }
74}
75
76impl<Child> TryFrom<[Insert<Child>; 4]> for Children<Child>
77where
78    Child: Height,
79{
80    type Error = [Hash; 4];
81
82    fn try_from(children: [Insert<Child>; 4]) -> Result<Self, Self::Error> {
83        use shape::*;
84        use Insert::*;
85
86        Ok(match children {
87            // All the children are hashes, so we should prune this node (we just hand back the
88            // hashes so the parent can implement pruning):
89            [Hash(a), Hash(b), Hash(c), Hash(d)] => return Err([a, b, c, d]),
90            // There is at least one witnessed child:
91            [Hash(a), Hash(b), Hash(c), Keep(d)] => Children::___C(Arc::new(___C(a, b, c, d))),
92            [Hash(a), Hash(b), Keep(c), Hash(d)] => Children::__C_(Arc::new(__C_(a, b, c, d))),
93            [Hash(a), Hash(b), Keep(c), Keep(d)] => Children::__CC(Arc::new(__CC(a, b, c, d))),
94            [Hash(a), Keep(b), Hash(c), Hash(d)] => Children::_C__(Arc::new(_C__(a, b, c, d))),
95            [Hash(a), Keep(b), Hash(c), Keep(d)] => Children::_C_C(Arc::new(_C_C(a, b, c, d))),
96            [Hash(a), Keep(b), Keep(c), Hash(d)] => Children::_CC_(Arc::new(_CC_(a, b, c, d))),
97            [Hash(a), Keep(b), Keep(c), Keep(d)] => Children::_CCC(Arc::new(_CCC(a, b, c, d))),
98            [Keep(a), Hash(b), Hash(c), Hash(d)] => Children::C___(Arc::new(C___(a, b, c, d))),
99            [Keep(a), Hash(b), Hash(c), Keep(d)] => Children::C__C(Arc::new(C__C(a, b, c, d))),
100            [Keep(a), Hash(b), Keep(c), Hash(d)] => Children::C_C_(Arc::new(C_C_(a, b, c, d))),
101            [Keep(a), Hash(b), Keep(c), Keep(d)] => Children::C_CC(Arc::new(C_CC(a, b, c, d))),
102            [Keep(a), Keep(b), Hash(c), Hash(d)] => Children::CC__(Arc::new(CC__(a, b, c, d))),
103            [Keep(a), Keep(b), Hash(c), Keep(d)] => Children::CC_C(Arc::new(CC_C(a, b, c, d))),
104            [Keep(a), Keep(b), Keep(c), Hash(d)] => Children::CCC_(Arc::new(CCC_(a, b, c, d))),
105            [Keep(a), Keep(b), Keep(c), Keep(d)] => Children::CCCC(Arc::new(CCCC(a, b, c, d))),
106        })
107    }
108}
109
110impl<Child: Clone> Children<Child> {
111    /// Get an array of references to the children or hashes stored in this [`Children`].
112    pub fn children(&self) -> [Insert<&Child>; 4] {
113        use Children::*;
114        use Insert::*;
115
116        match self {
117            ___C(c) => [Hash(c.0), Hash(c.1), Hash(c.2), Keep(&c.3)],
118            __C_(c) => [Hash(c.0), Hash(c.1), Keep(&c.2), Hash(c.3)],
119            __CC(c) => [Hash(c.0), Hash(c.1), Keep(&c.2), Keep(&c.3)],
120            _C__(c) => [Hash(c.0), Keep(&c.1), Hash(c.2), Hash(c.3)],
121            _C_C(c) => [Hash(c.0), Keep(&c.1), Hash(c.2), Keep(&c.3)],
122            _CC_(c) => [Hash(c.0), Keep(&c.1), Keep(&c.2), Hash(c.3)],
123            _CCC(c) => [Hash(c.0), Keep(&c.1), Keep(&c.2), Keep(&c.3)],
124            C___(c) => [Keep(&c.0), Hash(c.1), Hash(c.2), Hash(c.3)],
125            C__C(c) => [Keep(&c.0), Hash(c.1), Hash(c.2), Keep(&c.3)],
126            C_C_(c) => [Keep(&c.0), Hash(c.1), Keep(&c.2), Hash(c.3)],
127            C_CC(c) => [Keep(&c.0), Hash(c.1), Keep(&c.2), Keep(&c.3)],
128            CC__(c) => [Keep(&c.0), Keep(&c.1), Hash(c.2), Hash(c.3)],
129            CC_C(c) => [Keep(&c.0), Keep(&c.1), Hash(c.2), Keep(&c.3)],
130            CCC_(c) => [Keep(&c.0), Keep(&c.1), Keep(&c.2), Hash(c.3)],
131            CCCC(c) => [Keep(&c.0), Keep(&c.1), Keep(&c.2), Keep(&c.3)],
132        }
133    }
134
135    /// Get an array of references to the children or hashes stored in this [`Children`].
136    pub fn children_mut(&mut self) -> [InsertMut<'_, Child>; 4] {
137        use Children::*;
138        use InsertMut::*;
139
140        match self {
141            ___C(c) => {
142                let c = Arc::make_mut(c);
143                [
144                    Hash(&mut c.0),
145                    Hash(&mut c.1),
146                    Hash(&mut c.2),
147                    Keep(&mut c.3),
148                ]
149            }
150            __C_(c) => {
151                let c = Arc::make_mut(c);
152                [
153                    Hash(&mut c.0),
154                    Hash(&mut c.1),
155                    Keep(&mut c.2),
156                    Hash(&mut c.3),
157                ]
158            }
159            __CC(c) => {
160                let c = Arc::make_mut(c);
161                [
162                    Hash(&mut c.0),
163                    Hash(&mut c.1),
164                    Keep(&mut c.2),
165                    Keep(&mut c.3),
166                ]
167            }
168            _C__(c) => {
169                let c = Arc::make_mut(c);
170                [
171                    Hash(&mut c.0),
172                    Keep(&mut c.1),
173                    Hash(&mut c.2),
174                    Hash(&mut c.3),
175                ]
176            }
177            _C_C(c) => {
178                let c = Arc::make_mut(c);
179                [
180                    Hash(&mut c.0),
181                    Keep(&mut c.1),
182                    Hash(&mut c.2),
183                    Keep(&mut c.3),
184                ]
185            }
186            _CC_(c) => {
187                let c = Arc::make_mut(c);
188                [
189                    Hash(&mut c.0),
190                    Keep(&mut c.1),
191                    Keep(&mut c.2),
192                    Hash(&mut c.3),
193                ]
194            }
195            _CCC(c) => {
196                let c = Arc::make_mut(c);
197                [
198                    Hash(&mut c.0),
199                    Keep(&mut c.1),
200                    Keep(&mut c.2),
201                    Keep(&mut c.3),
202                ]
203            }
204            C___(c) => {
205                let c = Arc::make_mut(c);
206                [
207                    Keep(&mut c.0),
208                    Hash(&mut c.1),
209                    Hash(&mut c.2),
210                    Hash(&mut c.3),
211                ]
212            }
213            C__C(c) => {
214                let c = Arc::make_mut(c);
215                [
216                    Keep(&mut c.0),
217                    Hash(&mut c.1),
218                    Hash(&mut c.2),
219                    Keep(&mut c.3),
220                ]
221            }
222            C_C_(c) => {
223                let c = Arc::make_mut(c);
224                [
225                    Keep(&mut c.0),
226                    Hash(&mut c.1),
227                    Keep(&mut c.2),
228                    Hash(&mut c.3),
229                ]
230            }
231            C_CC(c) => {
232                let c = Arc::make_mut(c);
233                [
234                    Keep(&mut c.0),
235                    Hash(&mut c.1),
236                    Keep(&mut c.2),
237                    Keep(&mut c.3),
238                ]
239            }
240            CC__(c) => {
241                let c = Arc::make_mut(c);
242                [
243                    Keep(&mut c.0),
244                    Keep(&mut c.1),
245                    Hash(&mut c.2),
246                    Hash(&mut c.3),
247                ]
248            }
249            CC_C(c) => {
250                let c = Arc::make_mut(c);
251                [
252                    Keep(&mut c.0),
253                    Keep(&mut c.1),
254                    Hash(&mut c.2),
255                    Keep(&mut c.3),
256                ]
257            }
258            CCC_(c) => {
259                let c = Arc::make_mut(c);
260                [
261                    Keep(&mut c.0),
262                    Keep(&mut c.1),
263                    Keep(&mut c.2),
264                    Hash(&mut c.3),
265                ]
266            }
267            CCCC(c) => {
268                let c = Arc::make_mut(c);
269                [
270                    Keep(&mut c.0),
271                    Keep(&mut c.1),
272                    Keep(&mut c.2),
273                    Keep(&mut c.3),
274                ]
275            }
276        }
277    }
278}
279
280impl<Child: Clone> From<Children<Child>> for [Insert<Child>; 4] {
281    /// Get an array of references to the children or hashes stored in this [`Children`].
282    fn from(children: Children<Child>) -> [Insert<Child>; 4] {
283        use Children::*;
284        use Insert::*;
285
286        match children {
287            ___C(c) => [Hash(c.0), Hash(c.1), Hash(c.2), Keep(c.3.clone())],
288            __C_(c) => [Hash(c.0), Hash(c.1), Keep(c.2.clone()), Hash(c.3)],
289            __CC(c) => [Hash(c.0), Hash(c.1), Keep(c.2.clone()), Keep(c.3.clone())],
290            _C__(c) => [Hash(c.0), Keep(c.1.clone()), Hash(c.2), Hash(c.3)],
291            _C_C(c) => [Hash(c.0), Keep(c.1.clone()), Hash(c.2), Keep(c.3.clone())],
292            _CC_(c) => [Hash(c.0), Keep(c.1.clone()), Keep(c.2.clone()), Hash(c.3)],
293            _CCC(c) => [
294                Hash(c.0),
295                Keep(c.1.clone()),
296                Keep(c.2.clone()),
297                Keep(c.3.clone()),
298            ],
299            C___(c) => [Keep(c.0.clone()), Hash(c.1), Hash(c.2), Hash(c.3)],
300            C__C(c) => [Keep(c.0.clone()), Hash(c.1), Hash(c.2), Keep(c.3.clone())],
301            C_C_(c) => [Keep(c.0.clone()), Hash(c.1), Keep(c.2.clone()), Hash(c.3)],
302            C_CC(c) => [
303                Keep(c.0.clone()),
304                Hash(c.1),
305                Keep(c.2.clone()),
306                Keep(c.3.clone()),
307            ],
308            CC__(c) => [Keep(c.0.clone()), Keep(c.1.clone()), Hash(c.2), Hash(c.3)],
309            CC_C(c) => [
310                Keep(c.0.clone()),
311                Keep(c.1.clone()),
312                Hash(c.2),
313                Keep(c.3.clone()),
314            ],
315            CCC_(c) => [
316                Keep(c.0.clone()),
317                Keep(c.1.clone()),
318                Keep(c.2.clone()),
319                Hash(c.3),
320            ],
321            CCCC(c) => [
322                Keep(c.0.clone()),
323                Keep(c.1.clone()),
324                Keep(c.2.clone()),
325                Keep(c.3.clone()),
326            ],
327        }
328    }
329}
penumbra_sdk_tct/internal/complete/node/children.rs

penumbra_sdk_tct/internal/complete/node/
children.rs
