simplicity/node/
inner.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use super::{Disconnectable, FailEntropy};
4use crate::dag::Dag;
5use crate::Cmr;
6
7use crate::jet::Jet;
8use crate::value::Word;
9use std::fmt;
10use std::sync::Arc;
11
12/// Internal "Simplicity DAG" structure.
13///
14/// This structure is used to indicate the type of a node and provide
15/// pointers or references to its children, if any.
16#[derive(Clone, Eq, PartialOrd, Ord, Debug, Hash)]
17#[allow(clippy::derived_hash_with_manual_eq)] // see comment on manual `PartialEq` impl below
18pub enum Inner<C, X, W> {
19    /// Identity
20    Iden,
21    /// Unit constant
22    Unit,
23    /// Left injection of some child
24    InjL(C),
25    /// Right injection of some child
26    InjR(C),
27    /// Take of some child
28    Take(C),
29    /// Drop of some child
30    Drop(C),
31    /// Composition of a left and right child
32    Comp(C, C),
33    /// Case of a left and right child
34    Case(C, C),
35    /// Left assertion of a left and right child.
36    AssertL(C, Cmr),
37    /// Right assertion of a left and right child.
38    AssertR(Cmr, C),
39    /// Pair of a left and right child
40    Pair(C, C),
41    /// Disconnect of a left and right child
42    Disconnect(C, X),
43    /// Witness data (missing during commitment, inserted during redemption)
44    Witness(W),
45    /// Universal fail
46    Fail(FailEntropy),
47    /// Application jet
48    Jet(Box<dyn Jet>),
49    /// Constant word
50    Word(Word),
51}
52
53// Manually implemented because the 1.74 (MSRV) derive expands to a body that
54// moves out of the non-Copy `Box<dyn Jet>` field, later rustc versions are
55// fine.
56impl<C: PartialEq, X: PartialEq, W: PartialEq> PartialEq for Inner<C, X, W> {
57    fn eq(&self, other: &Self) -> bool {
58        use Inner::*;
59        match (self, other) {
60            (Iden, Iden) | (Unit, Unit) => true,
61            (InjL(a), InjL(b)) | (InjR(a), InjR(b)) | (Take(a), Take(b)) | (Drop(a), Drop(b)) => {
62                a == b
63            }
64            (Comp(a, b), Comp(c, d)) | (Case(a, b), Case(c, d)) | (Pair(a, b), Pair(c, d)) => {
65                a == c && b == d
66            }
67            (AssertL(a, b), AssertL(c, d)) => a == c && b == d,
68            (AssertR(a, b), AssertR(c, d)) => a == c && b == d,
69            (Disconnect(a, b), Disconnect(c, d)) => a == c && b == d,
70            (Witness(a), Witness(b)) => a == b,
71            (Fail(a), Fail(b)) => a == b,
72            (Jet(a), Jet(b)) => a == b,
73            (Word(a), Word(b)) => a == b,
74            _ => false,
75        }
76    }
77}
78
79impl<C, X, W> Inner<C, X, W> {
80    /// Convert a node's combinator data to a different type.
81    pub fn map<D, F: FnMut(C) -> D>(self, mut f: F) -> Inner<D, X, W> {
82        match self {
83            Inner::Iden => Inner::Iden,
84            Inner::Unit => Inner::Unit,
85            Inner::InjL(c) => Inner::InjL(f(c)),
86            Inner::InjR(c) => Inner::InjR(f(c)),
87            Inner::Take(c) => Inner::Take(f(c)),
88            Inner::Drop(c) => Inner::Drop(f(c)),
89            Inner::Comp(cl, cr) => Inner::Comp(f(cl), f(cr)),
90            Inner::Case(cl, cr) => Inner::Case(f(cl), f(cr)),
91            Inner::AssertL(c, cmr) => Inner::AssertL(f(c), cmr),
92            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, f(c)),
93            Inner::Pair(cl, cr) => Inner::Pair(f(cl), f(cr)),
94            Inner::Disconnect(cl, cr) => Inner::Disconnect(f(cl), cr),
95            Inner::Witness(w) => Inner::Witness(w),
96            Inner::Fail(entropy) => Inner::Fail(entropy),
97            Inner::Jet(j) => Inner::Jet(j),
98            Inner::Word(w) => Inner::Word(w),
99        }
100    }
101
102    /// Convert a node's combinator data to a different type.
103    pub fn map_result<D, E, F: FnMut(C) -> Result<D, E>>(
104        self,
105        mut f: F,
106    ) -> Result<Inner<D, X, W>, E> {
107        Ok(match self {
108            Inner::Iden => Inner::Iden,
109            Inner::Unit => Inner::Unit,
110            Inner::InjL(c) => Inner::InjL(f(c)?),
111            Inner::InjR(c) => Inner::InjR(f(c)?),
112            Inner::Take(c) => Inner::Take(f(c)?),
113            Inner::Drop(c) => Inner::Drop(f(c)?),
114            Inner::Comp(cl, cr) => Inner::Comp(f(cl)?, f(cr)?),
115            Inner::Case(cl, cr) => Inner::Case(f(cl)?, f(cr)?),
116            Inner::AssertL(c, cmr) => Inner::AssertL(f(c)?, cmr),
117            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, f(c)?),
118            Inner::Pair(cl, cr) => Inner::Pair(f(cl)?, f(cr)?),
119            Inner::Disconnect(cl, cr) => Inner::Disconnect(f(cl)?, cr),
120            Inner::Witness(w) => Inner::Witness(w),
121            Inner::Fail(entropy) => Inner::Fail(entropy),
122            Inner::Jet(j) => Inner::Jet(j),
123            Inner::Word(w) => Inner::Word(w),
124        })
125    }
126
127    /// Convert a node's combinator data to a different type, mapping each
128    /// child separately.
129    ///
130    /// Importantly, the child of an `AssertR` node is considered the left
131    /// child, because as a DAG node, this is the sole (left) child, even
132    /// though as a combinator, it is a right child.
133    pub fn map_left_right<D, FL, FR>(self, fl: FL, fr: FR) -> Inner<D, X, W>
134    where
135        FL: FnOnce(C) -> D,
136        FR: FnOnce(C) -> D,
137    {
138        match self {
139            Inner::Iden => Inner::Iden,
140            Inner::Unit => Inner::Unit,
141            Inner::InjL(c) => Inner::InjL(fl(c)),
142            Inner::InjR(c) => Inner::InjR(fl(c)),
143            Inner::Take(c) => Inner::Take(fl(c)),
144            Inner::Drop(c) => Inner::Drop(fl(c)),
145            Inner::Comp(cl, cr) => Inner::Comp(fl(cl), fr(cr)),
146            Inner::Case(cl, cr) => Inner::Case(fl(cl), fr(cr)),
147            Inner::AssertL(c, cmr) => Inner::AssertL(fl(c), cmr),
148            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, fl(c)),
149            Inner::Pair(cl, cr) => Inner::Pair(fl(cl), fr(cr)),
150            Inner::Disconnect(cl, cr) => Inner::Disconnect(fl(cl), cr),
151            Inner::Witness(w) => Inner::Witness(w),
152            Inner::Fail(entropy) => Inner::Fail(entropy),
153            Inner::Jet(j) => Inner::Jet(j),
154            Inner::Word(w) => Inner::Word(w),
155        }
156    }
157
158    /// Take references to all contained data.
159    pub fn as_ref(&self) -> Inner<&C, &X, &W> {
160        match self {
161            Inner::Iden => Inner::Iden,
162            Inner::Unit => Inner::Unit,
163            Inner::InjL(c) => Inner::InjL(c),
164            Inner::InjR(c) => Inner::InjR(c),
165            Inner::Take(c) => Inner::Take(c),
166            Inner::Drop(c) => Inner::Drop(c),
167            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
168            Inner::Case(cl, cr) => Inner::Case(cl, cr),
169            Inner::AssertL(c, cmr) => Inner::AssertL(c, *cmr),
170            Inner::AssertR(cmr, c) => Inner::AssertR(*cmr, c),
171            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
172            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, cr),
173            Inner::Witness(w) => Inner::Witness(w),
174            Inner::Fail(entropy) => Inner::Fail(*entropy),
175            Inner::Jet(j) => Inner::Jet(j.clone()),
176            Inner::Word(w) => Inner::Word(w.shallow_clone()),
177        }
178    }
179
180    /// Take references to only the disconnect node.
181    pub fn disconnect_as_ref(&self) -> Inner<C, &X, W>
182    where
183        C: Copy,
184        W: Copy,
185    {
186        match *self {
187            Inner::Iden => Inner::Iden,
188            Inner::Unit => Inner::Unit,
189            Inner::InjL(c) => Inner::InjL(c),
190            Inner::InjR(c) => Inner::InjR(c),
191            Inner::Take(c) => Inner::Take(c),
192            Inner::Drop(c) => Inner::Drop(c),
193            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
194            Inner::Case(cl, cr) => Inner::Case(cl, cr),
195            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
196            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
197            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
198            Inner::Disconnect(cl, ref cr) => Inner::Disconnect(cl, cr),
199            Inner::Witness(w) => Inner::Witness(w),
200            Inner::Fail(entropy) => Inner::Fail(entropy),
201            Inner::Jet(ref j) => Inner::Jet(j.dyn_clone()),
202            Inner::Word(ref w) => Inner::Word(w.shallow_clone()),
203        }
204    }
205
206    pub fn map_disconnect<Y, F: FnOnce(X) -> Y>(self, f: F) -> Inner<C, Y, W> {
207        match self {
208            Inner::Iden => Inner::Iden,
209            Inner::Unit => Inner::Unit,
210            Inner::InjL(c) => Inner::InjL(c),
211            Inner::InjR(c) => Inner::InjR(c),
212            Inner::Take(c) => Inner::Take(c),
213            Inner::Drop(c) => Inner::Drop(c),
214            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
215            Inner::Case(cl, cr) => Inner::Case(cl, cr),
216            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
217            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
218            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
219            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, f(cr)),
220            Inner::Witness(w) => Inner::Witness(w),
221            Inner::Fail(entropy) => Inner::Fail(entropy),
222            Inner::Jet(j) => Inner::Jet(j),
223            Inner::Word(w) => Inner::Word(w),
224        }
225    }
226
227    /// Convert a node's witness data to a different type.
228    pub fn map_disconnect_result<Y, E, F: FnOnce(X) -> Result<Y, E>>(
229        self,
230        f: F,
231    ) -> Result<Inner<C, Y, W>, E> {
232        Ok(match self {
233            Inner::Iden => Inner::Iden,
234            Inner::Unit => Inner::Unit,
235            Inner::InjL(c) => Inner::InjL(c),
236            Inner::InjR(c) => Inner::InjR(c),
237            Inner::Take(c) => Inner::Take(c),
238            Inner::Drop(c) => Inner::Drop(c),
239            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
240            Inner::Case(cl, cr) => Inner::Case(cl, cr),
241            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
242            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
243            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
244            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, f(cr)?),
245            Inner::Witness(w) => Inner::Witness(w),
246            Inner::Fail(entropy) => Inner::Fail(entropy),
247            Inner::Jet(j) => Inner::Jet(j),
248            Inner::Word(w) => Inner::Word(w),
249        })
250    }
251
252    /// Convert a node's witness data to a different type.
253    pub fn map_witness<V, F: FnOnce(W) -> V>(self, f: F) -> Inner<C, X, V> {
254        match self {
255            Inner::Iden => Inner::Iden,
256            Inner::Unit => Inner::Unit,
257            Inner::InjL(c) => Inner::InjL(c),
258            Inner::InjR(c) => Inner::InjR(c),
259            Inner::Take(c) => Inner::Take(c),
260            Inner::Drop(c) => Inner::Drop(c),
261            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
262            Inner::Case(cl, cr) => Inner::Case(cl, cr),
263            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
264            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
265            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
266            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, cr),
267            Inner::Witness(w) => Inner::Witness(f(w)),
268            Inner::Fail(entropy) => Inner::Fail(entropy),
269            Inner::Jet(j) => Inner::Jet(j),
270            Inner::Word(w) => Inner::Word(w),
271        }
272    }
273
274    /// Convert a node's witness data to a different type.
275    pub fn map_witness_result<V, E, F: FnOnce(W) -> Result<V, E>>(
276        self,
277        f: F,
278    ) -> Result<Inner<C, X, V>, E> {
279        Ok(match self {
280            Inner::Iden => Inner::Iden,
281            Inner::Unit => Inner::Unit,
282            Inner::InjL(c) => Inner::InjL(c),
283            Inner::InjR(c) => Inner::InjR(c),
284            Inner::Take(c) => Inner::Take(c),
285            Inner::Drop(c) => Inner::Drop(c),
286            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
287            Inner::Case(cl, cr) => Inner::Case(cl, cr),
288            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
289            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
290            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
291            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, cr),
292            Inner::Witness(w) => Inner::Witness(f(w)?),
293            Inner::Fail(entropy) => Inner::Fail(entropy),
294            Inner::Jet(j) => Inner::Jet(j),
295            Inner::Word(w) => Inner::Word(w),
296        })
297    }
298}
299
300impl<C, X: Disconnectable<C>, W> Inner<Arc<C>, X, W> {
301    /// Collapse the node information to a `Dag`
302    pub fn as_dag(&self) -> Dag<&C> {
303        match self {
304            Inner::Iden
305            | Inner::Unit
306            | Inner::Witness(_)
307            | Inner::Fail(_)
308            | Inner::Jet(_)
309            | Inner::Word(_) => Dag::Nullary,
310            Inner::InjL(c)
311            | Inner::InjR(c)
312            | Inner::Take(c)
313            | Inner::Drop(c)
314            | Inner::AssertL(c, _)
315            | Inner::AssertR(_, c) => Dag::Unary(c),
316            Inner::Comp(cl, cr) | Inner::Case(cl, cr) | Inner::Pair(cl, cr) => Dag::Binary(cl, cr),
317            Inner::Disconnect(cl, cr) => cr.disconnect_dag_ref(cl),
318        }
319    }
320}
321
322impl<C, X, W> Inner<Option<C>, X, W> {
323    /// Convert an `Inner<Option<C>, J, W>` to an `Option<Inner<C, J, W>>`.
324    pub fn transpose(self) -> Option<Inner<C, X, W>> {
325        Some(match self {
326            Inner::Iden => Inner::Iden,
327            Inner::Unit => Inner::Unit,
328            Inner::InjL(c) => Inner::InjL(c?),
329            Inner::InjR(c) => Inner::InjR(c?),
330            Inner::Take(c) => Inner::Take(c?),
331            Inner::Drop(c) => Inner::Drop(c?),
332            Inner::Comp(cl, cr) => Inner::Comp(cl?, cr?),
333            Inner::Case(cl, cr) => Inner::Case(cl?, cr?),
334            Inner::AssertL(c, cmr) => Inner::AssertL(c?, cmr),
335            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c?),
336            Inner::Pair(cl, cr) => Inner::Pair(cl?, cr?),
337            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl?, cr),
338            Inner::Witness(w) => Inner::Witness(w),
339            Inner::Fail(entropy) => Inner::Fail(entropy),
340            Inner::Jet(j) => Inner::Jet(j),
341            Inner::Word(w) => Inner::Word(w),
342        })
343    }
344}
345
346impl<C, X, W> Inner<C, Option<X>, W> {
347    /// Convert an `Inner<Option<C>, J, W>` to an `Option<Inner<C, J, W>>`.
348    pub fn transpose_disconnect(self) -> Option<Inner<C, X, W>> {
349        Some(match self {
350            Inner::Iden => Inner::Iden,
351            Inner::Unit => Inner::Unit,
352            Inner::InjL(c) => Inner::InjL(c),
353            Inner::InjR(c) => Inner::InjR(c),
354            Inner::Take(c) => Inner::Take(c),
355            Inner::Drop(c) => Inner::Drop(c),
356            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
357            Inner::Case(cl, cr) => Inner::Case(cl, cr),
358            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
359            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
360            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
361            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, cr?),
362            Inner::Witness(w) => Inner::Witness(w),
363            Inner::Fail(entropy) => Inner::Fail(entropy),
364            Inner::Jet(j) => Inner::Jet(j),
365            Inner::Word(w) => Inner::Word(w),
366        })
367    }
368}
369
370impl<C, X, W> Inner<C, X, Option<W>> {
371    /// Convert an `Inner<C, X, Option<W>>` to an `Option<Inner<C, X, W>>`.
372    pub fn transpose_witness(self) -> Option<Inner<C, X, W>> {
373        Some(match self {
374            Inner::Iden => Inner::Iden,
375            Inner::Unit => Inner::Unit,
376            Inner::InjL(c) => Inner::InjL(c),
377            Inner::InjR(c) => Inner::InjR(c),
378            Inner::Take(c) => Inner::Take(c),
379            Inner::Drop(c) => Inner::Drop(c),
380            Inner::Comp(cl, cr) => Inner::Comp(cl, cr),
381            Inner::Case(cl, cr) => Inner::Case(cl, cr),
382            Inner::AssertL(c, cmr) => Inner::AssertL(c, cmr),
383            Inner::AssertR(cmr, c) => Inner::AssertR(cmr, c),
384            Inner::Pair(cl, cr) => Inner::Pair(cl, cr),
385            Inner::Disconnect(cl, cr) => Inner::Disconnect(cl, cr),
386            Inner::Witness(w) => Inner::Witness(w?),
387            Inner::Fail(entropy) => Inner::Fail(entropy),
388            Inner::Jet(j) => Inner::Jet(j),
389            Inner::Word(w) => Inner::Word(w),
390        })
391    }
392}
393
394impl<C, X, W: Copy> Inner<C, X, &W> {
395    /// Copies witness data.
396    ///
397    /// Useful in conjunction with [`Inner::as_ref`] when you don't want to
398    /// take a reference to witness data.
399    pub fn copy_witness(self) -> Inner<C, X, W> {
400        self.map_witness(W::clone)
401    }
402}
403
404impl<C, X: Copy, W> Inner<C, &X, W> {
405    /// Copies disconnect data.
406    ///
407    /// Useful in conjunction with [`Inner::as_ref`] when you don't want to
408    /// take a reference to disconnect data.
409    pub fn copy_disconnect(self) -> Inner<C, X, W> {
410        self.map_disconnect(X::clone)
411    }
412}
413
414impl<C, X, W> fmt::Display for Inner<C, X, W> {
415    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
416        match self {
417            Inner::Iden => f.write_str("iden"),
418            Inner::Unit => f.write_str("unit"),
419            Inner::InjL(_) => f.write_str("injl"),
420            Inner::InjR(_) => f.write_str("injr"),
421            Inner::Take(_) => f.write_str("take"),
422            Inner::Drop(_) => f.write_str("drop"),
423            Inner::Comp(_, _) => f.write_str("comp"),
424            Inner::Case(_, _) => f.write_str("case"),
425            Inner::AssertL(_, _) => f.write_str("assertl"),
426            Inner::AssertR(_, _) => f.write_str("assertr"),
427            Inner::Pair(_, _) => f.write_str("pair"),
428            Inner::Disconnect(_, _) => f.write_str("disconnect"),
429            Inner::Witness(..) => f.write_str("witness"),
430            Inner::Fail(..) => f.write_str("fail"),
431            Inner::Jet(jet) => write!(f, "jet({})", jet),
432            Inner::Word(w) => write!(f, "word({})", w),
433        }
434    }
435}
simplicity/node/inner.rs

simplicity/node/
inner.rs
