simplicity/node/
construct.rs

1// SPDX-License-Identifier: CC0-1.0
2
3use crate::dag::{InternalSharing, PostOrderIterItem};
4use crate::jet::{Jet, JetEnvironment};
5use crate::types::{self, Arrow};
6use crate::{encode, BitIter, BitWriter, Cmr, FailEntropy, FinalizeError, RedeemNode, Value, Word};
7
8use std::io;
9use std::marker::PhantomData;
10use std::sync::Arc;
11
12use super::{
13    Commit, CommitData, CommitNode, Converter, Inner, Marker, NoDisconnect, NoWitness, Node,
14    Redeem, RedeemData,
15};
16use super::{CoreConstructible, DisconnectConstructible, WitnessConstructible};
17
18/// ID used to share [`ConstructNode`]s.
19///
20/// This is impossible to construct, which is a promise that it is impossible
21/// to share [`ConstructNode`]s.
22#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
23pub enum ConstructId {}
24
25#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
26pub struct Construct<'brand> {
27    /// Makes the type non-constructible.
28    never: std::convert::Infallible,
29    /// Required by Rust.
30    phantom: std::marker::PhantomData<&'brand ()>,
31}
32
33impl<'brand> Marker for Construct<'brand> {
34    type CachedData = ConstructData<'brand>;
35    type Witness = Option<Value>;
36    type Disconnect = Option<Arc<ConstructNode<'brand>>>;
37    type SharingId = ConstructId;
38
39    fn compute_sharing_id(_: Cmr, _: &ConstructData<'brand>) -> Option<ConstructId> {
40        None
41    }
42}
43
44pub type ConstructNode<'brand> = Node<Construct<'brand>>;
45
46impl<'brand> ConstructNode<'brand> {
47    /// Accessor for the node's arrow
48    pub fn arrow(&self) -> &Arrow<'brand> {
49        self.data.arrow()
50    }
51
52    /// Sets the source and target type of the node to unit
53    pub fn set_arrow_to_program(&self) -> Result<(), types::Error> {
54        let ctx = self.data.inference_context();
55        let unit_ty = types::Type::unit(ctx);
56        ctx.unify(
57            &self.arrow().source,
58            &unit_ty,
59            "setting root source to unit",
60        )?;
61        ctx.unify(
62            &self.arrow().target,
63            &unit_ty,
64            "setting root target to unit",
65        )?;
66        Ok(())
67    }
68
69    /// Convert a [`ConstructNode`] to a [`CommitNode`] by finalizing all of the types.
70    ///
71    /// Also sets the source and target type of this node to unit. This is almost
72    /// certainly what you want, since the resulting `CommitNode` cannot be further
73    /// composed, and needs to be 1->1 to go on-chain. But if you don't, call
74    /// [`Self::finalize_types_non_program`] instead.
75    pub fn finalize_types(&self) -> Result<Arc<CommitNode>, types::Error> {
76        self.set_arrow_to_program()?;
77        self.finalize_types_non_program()
78    }
79
80    /// Convert a [`ConstructNode`] to a [`CommitNode`] by finalizing all of the types.
81    ///
82    /// Does *not* sets the source and target type of this node to unit.
83    pub fn finalize_types_non_program(&self) -> Result<Arc<CommitNode>, types::Error> {
84        struct FinalizeTypes;
85
86        impl<'brand> Converter<Construct<'brand>, Commit> for FinalizeTypes {
87            type Error = types::Error;
88
89            fn convert_witness(
90                &mut self,
91                _: &PostOrderIterItem<&ConstructNode>,
92                _: &Option<Value>,
93            ) -> Result<NoWitness, Self::Error> {
94                Ok(NoWitness)
95            }
96
97            fn convert_disconnect(
98                &mut self,
99                _: &PostOrderIterItem<&ConstructNode>,
100                _: Option<&Arc<CommitNode>>,
101                _: &Option<Arc<ConstructNode>>,
102            ) -> Result<NoDisconnect, Self::Error> {
103                Ok(NoDisconnect)
104            }
105
106            fn convert_data(
107                &mut self,
108                data: &PostOrderIterItem<&ConstructNode>,
109                inner: Inner<&Arc<CommitNode>, &NoDisconnect, &NoWitness>,
110            ) -> Result<Arc<CommitData>, Self::Error> {
111                let converted_data = inner.map(|node| node.cached_data());
112                CommitData::new(&data.node.data.arrow, converted_data).map(Arc::new)
113            }
114        }
115
116        self.convert::<InternalSharing, _, _>(&mut FinalizeTypes)
117    }
118
119    /// Finalize the witness program as an unpruned redeem program.
120    ///
121    /// Witness nodes must be populated with sufficient data,
122    /// to ensure that the resulting redeem program successfully runs on the Bit Machine.
123    /// Furthermore, **all** disconnected branches must be populated,
124    /// even those that are not executed.
125    ///
126    /// The resulting redeem program is **not pruned**.
127    ///
128    /// ## See
129    ///
130    /// [`RedeemNode::prune`]
131    pub fn finalize_unpruned(&self) -> Result<Arc<RedeemNode>, FinalizeError> {
132        struct Finalizer(PhantomData<()>);
133
134        impl<'brand> Converter<Construct<'brand>, Redeem> for Finalizer {
135            type Error = FinalizeError;
136
137            fn convert_witness(
138                &mut self,
139                data: &PostOrderIterItem<&ConstructNode>,
140                wit: &Option<Value>,
141            ) -> Result<Value, Self::Error> {
142                if let Some(ref wit) = wit {
143                    Ok(wit.shallow_clone())
144                } else {
145                    // We insert a zero value into unpopulated witness nodes,
146                    // assuming that this node will later be pruned out of the program.
147                    //
148                    // Pruning requires running a program on the Bit Machine,
149                    // which in turn requires a program with fully populated witness nodes.
150                    // It would be horrible UX to force the caller to provide witness data
151                    // even for unexecuted branches, so we insert zero values here.
152                    //
153                    // If this node is executed after all, then the caller can fix the witness
154                    // data based on the returned execution error.
155                    //
156                    // Zero values may "accidentally" satisfy a program even if the caller
157                    // didn't provide any witness data. However, this is only the case for the
158                    // most trivial programs. The only place where we must be careful is our
159                    // unit tests, which tend to include these kinds of trivial programs.
160                    let ty = data
161                        .node
162                        .arrow()
163                        .target
164                        .finalize()
165                        .map_err(FinalizeError::Type)?;
166                    Ok(Value::zero(&ty))
167                }
168            }
169
170            fn convert_disconnect(
171                &mut self,
172                _: &PostOrderIterItem<&ConstructNode>,
173                maybe_converted: Option<&Arc<RedeemNode>>,
174                _: &Option<Arc<ConstructNode>>,
175            ) -> Result<Arc<RedeemNode>, Self::Error> {
176                if let Some(child) = maybe_converted {
177                    Ok(Arc::clone(child))
178                } else {
179                    Err(FinalizeError::DisconnectRedeemTime)
180                }
181            }
182
183            fn convert_data(
184                &mut self,
185                data: &PostOrderIterItem<&ConstructNode>,
186                inner: Inner<&Arc<RedeemNode>, &Arc<RedeemNode>, &Value>,
187            ) -> Result<Arc<RedeemData>, Self::Error> {
188                let converted_data = inner
189                    .map(|node| node.cached_data())
190                    .map_disconnect(|node| node.cached_data())
191                    .map_witness(Value::shallow_clone);
192                Ok(Arc::new(RedeemData::new(
193                    data.node.arrow().finalize().map_err(FinalizeError::Type)?,
194                    converted_data,
195                )))
196            }
197        }
198
199        self.convert::<InternalSharing, _, _>(&mut Finalizer(PhantomData))
200    }
201
202    /// Finalize the witness program as a pruned redeem program.
203    ///
204    /// Witness nodes must be populated with sufficient data,
205    /// to ensure that the resulting redeem program successfully runs on the Bit Machine.
206    /// Furthermore, **all** disconnected branches must be populated,
207    /// even those that are not executed.
208    ///
209    /// The resulting redeem program is **pruned** based on the given transaction environment.
210    ///
211    /// ## See
212    ///
213    /// [`RedeemNode::prune`]
214    pub fn finalize_pruned<JE: JetEnvironment>(
215        &self,
216        env: &JE,
217    ) -> Result<Arc<RedeemNode>, FinalizeError> {
218        let unpruned = self.finalize_unpruned()?;
219        unpruned.prune(env).map_err(FinalizeError::Execution)
220    }
221
222    /// Decode a Simplicity expression from bits, without witness data.
223    ///
224    /// # Usage
225    ///
226    /// Use this method only if the serialization **does not** include the witness data.
227    /// This means, the program simply has no witness during commitment,
228    /// or the witness is provided by other means.
229    ///
230    /// If the serialization contains the witness data, then use [`crate::RedeemNode::decode()`].
231    pub fn decode<I: Iterator<Item = u8>, J: Jet>(
232        context: &types::Context<'brand>,
233        mut bits: BitIter<I>,
234    ) -> Result<Arc<Self>, crate::decode::Error> {
235        let res = crate::decode::decode_expression::<I, J>(context, &mut bits)?;
236        bits.close()?;
237        Ok(res)
238    }
239
240    #[cfg(feature = "base64")]
241    #[allow(clippy::should_implement_trait)] // returns Arc<Self>, needs tyctx
242    pub fn from_str<J: Jet>(
243        context: &types::Context<'brand>,
244        s: &str,
245    ) -> Result<Arc<Self>, crate::ParseError> {
246        use crate::base64::engine::general_purpose;
247        use crate::base64::Engine as _;
248
249        let v = general_purpose::STANDARD
250            .decode(s)
251            .map_err(crate::ParseError::Base64)?;
252        let iter = crate::BitIter::new(v.into_iter());
253        Self::decode::<_, J>(context, iter)
254            .map_err(crate::DecodeError::Decode)
255            .map_err(crate::ParseError::Decode)
256    }
257
258    /// Encode a Simplicity expression to bits, with no witness data
259    #[deprecated(since = "0.5.0", note = "use Self::encode_without_witness instead")]
260    pub fn encode(&self, w: &mut BitWriter<&mut dyn io::Write>) -> io::Result<usize> {
261        let program_bits = encode::encode_program(self, w)?;
262        w.flush_all()?;
263        Ok(program_bits)
264    }
265}
266
267#[derive(Clone, Debug)]
268pub struct ConstructData<'brand> {
269    arrow: Arrow<'brand>,
270}
271
272impl<'brand> ConstructData<'brand> {
273    /// Constructs a new [`ConstructData`] from an (unfinalized) type arrow
274    pub fn new(arrow: Arrow<'brand>) -> Self {
275        ConstructData { arrow }
276    }
277
278    /// Accessor for the node's arrow
279    pub fn arrow(&self) -> &Arrow<'brand> {
280        &self.arrow
281    }
282}
283
284impl<'brand> CoreConstructible<'brand> for ConstructData<'brand> {
285    fn iden(inference_context: &types::Context<'brand>) -> Self {
286        ConstructData {
287            arrow: Arrow::iden(inference_context),
288        }
289    }
290
291    fn unit(inference_context: &types::Context<'brand>) -> Self {
292        ConstructData {
293            arrow: Arrow::unit(inference_context),
294        }
295    }
296
297    fn injl(child: &Self) -> Self {
298        ConstructData {
299            arrow: Arrow::injl(&child.arrow),
300        }
301    }
302
303    fn injr(child: &Self) -> Self {
304        ConstructData {
305            arrow: Arrow::injr(&child.arrow),
306        }
307    }
308
309    fn take(child: &Self) -> Self {
310        ConstructData {
311            arrow: Arrow::take(&child.arrow),
312        }
313    }
314
315    fn drop_(child: &Self) -> Self {
316        ConstructData {
317            arrow: Arrow::drop_(&child.arrow),
318        }
319    }
320
321    fn comp(left: &Self, right: &Self) -> Result<Self, types::Error> {
322        Ok(ConstructData {
323            arrow: Arrow::comp(&left.arrow, &right.arrow)?,
324        })
325    }
326
327    fn case(left: &Self, right: &Self) -> Result<Self, types::Error> {
328        Ok(ConstructData {
329            arrow: Arrow::case(&left.arrow, &right.arrow)?,
330        })
331    }
332
333    fn assertl(left: &Self, _: Cmr) -> Result<Self, types::Error> {
334        Ok(ConstructData {
335            arrow: Arrow::assertl(&left.arrow)?,
336        })
337    }
338
339    fn assertr(_: Cmr, right: &Self) -> Result<Self, types::Error> {
340        Ok(ConstructData {
341            arrow: Arrow::assertr(&right.arrow)?,
342        })
343    }
344
345    fn pair(left: &Self, right: &Self) -> Result<Self, types::Error> {
346        Ok(ConstructData {
347            arrow: Arrow::pair(&left.arrow, &right.arrow)?,
348        })
349    }
350
351    fn fail(inference_context: &types::Context<'brand>, _: FailEntropy) -> Self {
352        ConstructData {
353            arrow: Arrow::fail(inference_context),
354        }
355    }
356
357    fn const_word(inference_context: &types::Context<'brand>, word: Word) -> Self {
358        ConstructData {
359            arrow: Arrow::const_word(inference_context, &word),
360        }
361    }
362
363    fn jet(inference_context: &types::Context<'brand>, jet: &dyn Jet) -> Self {
364        ConstructData {
365            arrow: Arrow::jet(inference_context, jet),
366        }
367    }
368
369    fn arrow(&self) -> &Arrow<'brand> {
370        &self.arrow
371    }
372}
373
374impl<'brand> DisconnectConstructible<'brand, Option<Arc<ConstructNode<'brand>>>>
375    for ConstructData<'brand>
376{
377    fn disconnect(
378        left: &Self,
379        right: &Option<Arc<ConstructNode<'brand>>>,
380    ) -> Result<Self, types::Error> {
381        let right = right.as_ref();
382        Ok(ConstructData {
383            arrow: Arrow::disconnect(&left.arrow, &right.map(|n| n.arrow()))?,
384        })
385    }
386}
387
388impl<'brand> WitnessConstructible<'brand, Option<Value>> for ConstructData<'brand> {
389    fn witness(inference_context: &types::Context<'brand>, _witness: Option<Value>) -> Self {
390        ConstructData {
391            arrow: Arrow::witness(inference_context),
392        }
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399    use crate::types::Final;
400    use crate::Value;
401
402    #[test]
403    fn occurs_check_error() {
404        types::Context::with_context(|ctx| {
405            let iden = Arc::<ConstructNode>::iden(&ctx);
406            let node = Arc::<ConstructNode>::disconnect(&iden, &Some(Arc::clone(&iden))).unwrap();
407
408            assert!(matches!(
409                node.finalize_types_non_program(),
410                Err(types::Error::OccursCheck { .. }),
411            ));
412        });
413    }
414
415    #[test]
416    fn occurs_check_2() {
417        types::Context::with_context(|ctx| {
418            // A more complicated occurs-check test that caused a deadlock in the past.
419            let iden = Arc::<ConstructNode>::iden(&ctx);
420            let injr = Arc::<ConstructNode>::injr(&iden);
421            let pair = Arc::<ConstructNode>::pair(&injr, &iden).unwrap();
422            let drop = Arc::<ConstructNode>::drop_(&pair);
423
424            let case1 = Arc::<ConstructNode>::case(&drop, &drop).unwrap();
425            let case2 = Arc::<ConstructNode>::case(&case1, &case1).unwrap();
426
427            let comp1 = Arc::<ConstructNode>::comp(&case2, &case2).unwrap();
428            let comp2 = Arc::<ConstructNode>::comp(&comp1, &case1).unwrap();
429
430            assert!(matches!(
431                comp2.finalize_types_non_program(),
432                Err(types::Error::OccursCheck { .. }),
433            ));
434        });
435    }
436
437    #[test]
438    fn occurs_check_3() {
439        types::Context::with_context(|ctx| {
440            // A similar example that caused a slightly different deadlock in the past.
441            let wit = Arc::<ConstructNode>::witness(&ctx, None);
442            let drop = Arc::<ConstructNode>::drop_(&wit);
443
444            let comp1 = Arc::<ConstructNode>::comp(&drop, &drop).unwrap();
445            let comp2 = Arc::<ConstructNode>::comp(&comp1, &comp1).unwrap();
446            let comp3 = Arc::<ConstructNode>::comp(&comp2, &comp2).unwrap();
447            let comp4 = Arc::<ConstructNode>::comp(&comp3, &comp3).unwrap();
448            let comp5 = Arc::<ConstructNode>::comp(&comp4, &comp4).unwrap();
449
450            let case = Arc::<ConstructNode>::case(&comp5, &comp4).unwrap();
451            let drop2 = Arc::<ConstructNode>::drop_(&case);
452            let case2 = Arc::<ConstructNode>::case(&drop2, &case).unwrap();
453            let comp6 = Arc::<ConstructNode>::comp(&case2, &case2).unwrap();
454            let case3 = Arc::<ConstructNode>::case(&comp6, &comp6).unwrap();
455
456            let comp7 = Arc::<ConstructNode>::comp(&case3, &case3).unwrap();
457            let comp8 = Arc::<ConstructNode>::comp(&comp7, &comp7).unwrap();
458
459            assert!(matches!(
460                comp8.finalize_types_non_program(),
461                Err(types::Error::OccursCheck { .. }),
462            ));
463        });
464    }
465
466    #[test]
467    fn type_check_error() {
468        types::Context::with_context(|ctx| {
469            let unit = Arc::<ConstructNode>::unit(&ctx);
470            let case = Arc::<ConstructNode>::case(&unit, &unit).unwrap();
471
472            assert!(matches!(
473                Arc::<ConstructNode>::disconnect(&case, &Some(unit)),
474                Err(types::Error::Bind { .. }),
475            ));
476        });
477    }
478
479    #[test]
480    fn scribe() {
481        // Ok to use same type inference context for all the below tests,
482        // since everything has concrete types and anyway we only care
483        // about CMRs, for which type inference is irrelevant.
484        types::Context::with_context(|ctx| {
485            let unit = Arc::<ConstructNode>::unit(&ctx);
486            let bit0 = Arc::<ConstructNode>::const_word(&ctx, Word::u1(0));
487            let bit1 = Arc::<ConstructNode>::const_word(&ctx, Word::u1(1));
488
489            assert_eq!(
490                unit.cmr(),
491                Arc::<ConstructNode>::scribe(&ctx, &Value::unit()).cmr()
492            );
493            assert_eq!(
494                bit0.cmr(),
495                Arc::<ConstructNode>::scribe(&ctx, &Value::u1(0)).cmr()
496            );
497            assert_eq!(
498                bit1.cmr(),
499                Arc::<ConstructNode>::scribe(&ctx, &Value::u1(1)).cmr()
500            );
501            assert_eq!(
502                Arc::<ConstructNode>::const_word(&ctx, Word::u2(1)).cmr(),
503                Arc::<ConstructNode>::scribe(&ctx, &Value::u2(1)).cmr()
504            );
505            assert_eq!(
506                Arc::<ConstructNode>::injl(&bit0).cmr(),
507                Arc::<ConstructNode>::scribe(&ctx, &Value::left(Value::u1(0), Final::unit())).cmr()
508            );
509            assert_eq!(
510                Arc::<ConstructNode>::injr(&bit1).cmr(),
511                Arc::<ConstructNode>::scribe(&ctx, &Value::right(Final::unit(), Value::u1(1)))
512                    .cmr()
513            );
514            assert_eq!(
515                Arc::<ConstructNode>::pair(&unit, &unit).unwrap().cmr(),
516                Arc::<ConstructNode>::scribe(&ctx, &Value::product(Value::unit(), Value::unit()))
517                    .cmr()
518            );
519        });
520    }
521
522    #[test]
523    fn regression_286_1() {
524        // This is the smallest pure Simplicity program I was able to find that exhibits the bad
525        // behavior seen in https://github.com/BlockstreamResearch/rust-simplicity/issues/286
526        types::Context::with_context(|ctx| {
527            let cmr = Cmr::from_byte_array([0xde; 32]);
528
529            let u0 = Arc::<ConstructNode>::unit(&ctx);
530            let i1 = Arc::<ConstructNode>::injl(&u0);
531            let i2 = Arc::<ConstructNode>::injr(&i1);
532            let i3 = Arc::<ConstructNode>::injr(&i2);
533            let i4 = Arc::<ConstructNode>::injl(&i3);
534            let u5 = Arc::<ConstructNode>::unit(&ctx);
535            let i6 = Arc::<ConstructNode>::injl(&u5);
536            let i7 = Arc::<ConstructNode>::injr(&i6);
537            let p8 = Arc::<ConstructNode>::pair(&i4, &i7).unwrap();
538            let u9 = Arc::<ConstructNode>::unit(&ctx);
539            let a10 = Arc::<ConstructNode>::assertr(cmr, &u9).unwrap();
540            let u11 = Arc::<ConstructNode>::unit(&ctx);
541            let a12 = Arc::<ConstructNode>::assertr(cmr, &u11).unwrap();
542            let a13 = Arc::<ConstructNode>::assertl(&a12, cmr).unwrap();
543            let c14 = Arc::<ConstructNode>::case(&a10, &a13).unwrap();
544            let c15 = Arc::<ConstructNode>::comp(&p8, &c14).unwrap();
545
546            let finalized: Arc<CommitNode> = c15.finalize_types().unwrap();
547            let prog = finalized.to_vec_without_witness();
548            // In #286 we are encoding correctly...
549            assert_eq!(
550                hex::DisplayHex::as_hex(&prog[..]).to_string(),
551                "dc920a28812b6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f6f243090e00b10e00680",
552            );
553
554            let prog = BitIter::from(prog);
555            let decode = CommitNode::decode::<_, crate::jet::Core>(prog).unwrap();
556
557            // ...but then during decoding we read the program incorrectly and this assertion fails.
558            assert_eq!(finalized, decode);
559        });
560    }
561
562    #[test]
563    fn regression_286_2() {
564        // This one is smaller because it starts with a witness node which has a large type.
565        // This is a bit easier to grok but can't be serialized as a complete/valid program
566        // without providing the witness data, which limits its ability to share with the
567        // other libraries.
568        //
569        // It also exhibits the bug earlier than the other one -- it *should* just fail to
570        // typecheck and not be constructible. So we can't get an encoding of it.
571        types::Context::with_context(|ctx| {
572            let w0 = Arc::<ConstructNode>::witness(&ctx, None);
573            let i1 = Arc::<ConstructNode>::iden(&ctx);
574            let d2 = Arc::<ConstructNode>::drop_(&i1);
575            let i3 = Arc::<ConstructNode>::iden(&ctx);
576            let i4 = Arc::<ConstructNode>::iden(&ctx);
577            let t5 = Arc::<ConstructNode>::take(&i4);
578            let ca6 = Arc::<ConstructNode>::case(&i3, &t5).unwrap();
579            let ca7 = Arc::<ConstructNode>::case(&d2, &ca6).unwrap();
580            let c8 = Arc::<ConstructNode>::comp(&w0, &ca7).unwrap();
581            let u9 = Arc::<ConstructNode>::unit(&ctx);
582            let c10 = Arc::<ConstructNode>::comp(&c8, &u9).unwrap();
583
584            // In #286 we incorrectly succeed finalizing the types, and then encode a bad program.
585            let err = c10.finalize_types().unwrap_err();
586            assert!(matches!(err, types::Error::OccursCheck { .. }));
587        });
588    }
589}
simplicity/node/construct.rs

simplicity/node/
construct.rs
