simplicity/human_encoding/
named_node.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! Human-readable Nodes
4
5use crate::dag::{InternalSharing, MaxSharing, PostOrderIterItem};
6use crate::human_encoding::{Error, ErrorSet, Position, WitnessOrHole};
7use crate::jet::Jet;
8use crate::node::{
9    self, Commit, CommitData, CommitNode, Construct, ConstructData, Constructible as _, Converter,
10    CoreConstructible as _, Inner, NoDisconnect, NoWitness, Node,
11};
12use crate::types;
13use crate::types::arrow::{Arrow, FinalArrow};
14use crate::{encode, ConstructNode, Value};
15use crate::{BitWriter, Cmr, Ihr};
16
17use std::collections::HashMap;
18use std::io;
19use std::marker::PhantomData;
20use std::sync::Arc;
21
22pub type NamedCommitNode<J> = Node<Named<Commit<J>>>;
23
24#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug, Hash)]
25pub struct Named<N> {
26    /// Makes the type non-constructible.
27    never: std::convert::Infallible,
28    /// Required by Rust.
29    phantom: std::marker::PhantomData<N>,
30}
31
32impl<J: Jet> node::Marker for Named<Commit<J>> {
33    type CachedData = NamedCommitData<J>;
34    type Witness = <Commit<J> as node::Marker>::Witness;
35    type Disconnect = Arc<str>;
36    type SharingId = <Commit<J> as node::Marker>::SharingId;
37    type Jet = J;
38
39    fn compute_sharing_id(cmr: Cmr, cached_data: &Self::CachedData) -> Option<Self::SharingId> {
40        Commit::<J>::compute_sharing_id(cmr, &cached_data.internal)
41    }
42}
43
44#[derive(Clone, Debug, PartialEq, Eq, Hash)]
45pub struct NamedCommitData<J> {
46    /// Data related to the node itself
47    internal: Arc<CommitData<J>>,
48    /// Name assigned to the node.
49    name: Arc<str>,
50}
51
52impl<J: Jet> NamedCommitNode<J> {
53    pub fn from_node(root: &CommitNode<J>) -> Arc<Self> {
54        let mut namer = Namer::new_rooted(root.cmr());
55        root.convert::<MaxSharing<Commit<J>>, _, _>(&mut namer)
56            .unwrap()
57    }
58
59    /// Accessor for the node's name
60    pub fn name(&self) -> &Arc<str> {
61        &self.cached_data().name
62    }
63
64    /// Accessor for the node's name
65    pub fn ihr(&self) -> Option<Ihr> {
66        self.cached_data().internal.ihr()
67    }
68
69    /// Accessor for the node's type arrow
70    pub fn arrow(&self) -> &FinalArrow {
71        self.cached_data().internal.arrow()
72    }
73
74    /// Forget the names, yielding an ordinary [`CommitNode`].
75    pub fn to_commit_node(&self) -> Arc<CommitNode<J>> {
76        struct Forgetter<J>(PhantomData<J>);
77
78        impl<J: Jet> Converter<Named<Commit<J>>, Commit<J>> for Forgetter<J> {
79            type Error = ();
80            fn convert_witness(
81                &mut self,
82                _: &PostOrderIterItem<&NamedCommitNode<J>>,
83                _: &NoWitness,
84            ) -> Result<NoWitness, Self::Error> {
85                Ok(NoWitness)
86            }
87
88            fn convert_disconnect(
89                &mut self,
90                _: &PostOrderIterItem<&NamedCommitNode<J>>,
91                _: Option<&Arc<CommitNode<J>>>,
92                _: &Arc<str>,
93            ) -> Result<NoDisconnect, Self::Error> {
94                Ok(NoDisconnect)
95            }
96
97            fn convert_data(
98                &mut self,
99                data: &PostOrderIterItem<&NamedCommitNode<J>>,
100                _: node::Inner<&Arc<CommitNode<J>>, J, &NoDisconnect, &NoWitness>,
101            ) -> Result<Arc<CommitData<J>>, Self::Error> {
102                Ok(Arc::clone(&data.node.cached_data().internal))
103            }
104        }
105
106        self.convert::<InternalSharing, _, _>(&mut Forgetter(PhantomData))
107            .unwrap()
108    }
109
110    pub fn to_construct_node<'brand>(
111        &self,
112        inference_context: &types::Context<'brand>,
113        witness: &HashMap<Arc<str>, Value>,
114        disconnect: &HashMap<Arc<str>, Arc<NamedCommitNode<J>>>,
115    ) -> Arc<ConstructNode<'brand, J>> {
116        struct Populator<'a, 'brand, J: Jet> {
117            witness_map: &'a HashMap<Arc<str>, Value>,
118            disconnect_map: &'a HashMap<Arc<str>, Arc<NamedCommitNode<J>>>,
119            inference_context: &'a types::Context<'brand>,
120            phantom: PhantomData<J>,
121        }
122
123        impl<'brand, J: Jet> Converter<Named<Commit<J>>, Construct<'brand, J>>
124            for Populator<'_, 'brand, J>
125        {
126            type Error = ();
127
128            fn convert_witness(
129                &mut self,
130                data: &PostOrderIterItem<&Node<Named<Commit<J>>>>,
131                _: &NoWitness,
132            ) -> Result<Option<Value>, Self::Error> {
133                let name = &data.node.cached_data().name;
134                // We keep the witness nodes without data unpopulated.
135                // Some nodes are pruned later so they don't need to be populated.
136                // Which nodes are pruned is not known when this code is executed.
137                // If an unpruned node is unpopulated, then there will be an error
138                // during the finalization.
139                Ok(self.witness_map.get(name).cloned())
140            }
141
142            fn convert_disconnect(
143                &mut self,
144                data: &PostOrderIterItem<&Node<Named<Commit<J>>>>,
145                maybe_converted: Option<&Arc<Node<Construct<'brand, J>>>>,
146                _: &Arc<str>,
147            ) -> Result<Option<Arc<Node<Construct<'brand, J>>>>, Self::Error> {
148                if let Some(converted) = maybe_converted {
149                    Ok(Some(converted.clone()))
150                } else {
151                    let hole_name = match data.node.inner() {
152                        Inner::Disconnect(_, hole_name) => hole_name,
153                        _ => unreachable!(),
154                    };
155                    // We keep the missing disconnected branches empty.
156                    // Like witness nodes (see above), disconnect nodes may be pruned later.
157                    // The finalization will detect missing branches and throw an error.
158                    let maybe_commit = self.disconnect_map.get(hole_name);
159                    // FIXME: recursive call to convert
160                    // We cannot introduce a stack because we are implementing the Converter
161                    // trait and do not have access to the actual algorithm used for conversion
162                    // in order to save its state.
163                    //
164                    // OTOH, if a user writes a program with so many disconnected expressions
165                    // that there is a stack overflow, it's his own fault :)
166                    // This may fail in a fuzz test.
167                    let witness = maybe_commit
168                        .map(|commit| commit.convert::<InternalSharing, _, _>(self).unwrap());
169                    Ok(witness)
170                }
171            }
172
173            fn convert_data(
174                &mut self,
175                _: &PostOrderIterItem<&Node<Named<Commit<J>>>>,
176                inner: Inner<
177                    &Arc<Node<Construct<'brand, J>>>,
178                    J,
179                    &Option<Arc<ConstructNode<'brand, J>>>,
180                    &Option<Value>,
181                >,
182            ) -> Result<ConstructData<'brand, J>, Self::Error> {
183                let inner = inner
184                    .map(|node| node.cached_data())
185                    .map_witness(|maybe_value| maybe_value.clone());
186                Ok(ConstructData::from_inner(self.inference_context, inner)
187                    .expect("types are already finalized"))
188            }
189        }
190
191        self.convert::<InternalSharing, _, _>(&mut Populator {
192            witness_map: witness,
193            disconnect_map: disconnect,
194            inference_context,
195            phantom: PhantomData,
196        })
197        .unwrap()
198    }
199
200    /// Encode a Simplicity expression to bits without any witness data
201    #[deprecated(since = "0.5.0", note = "use Self::encode_without_witness instead")]
202    pub fn encode<W: io::Write>(&self, w: &mut BitWriter<W>) -> io::Result<usize> {
203        let program_bits = encode::encode_program(self, w)?;
204        w.flush_all()?;
205        Ok(program_bits)
206    }
207
208    /// Encode a Simplicity program to a vector of bytes, without any witness data.
209    #[deprecated(since = "0.5.0", note = "use Self::to_vec_without_witness instead")]
210    pub fn encode_to_vec(&self) -> Vec<u8> {
211        let mut prog = Vec::<u8>::new();
212        self.encode_without_witness(&mut prog)
213            .expect("write to vector never fails");
214        debug_assert!(!prog.is_empty());
215
216        prog
217    }
218}
219
220pub type NamedConstructNode<'brand, J> = Node<Named<Construct<'brand, J>>>;
221
222impl<'brand, J: Jet> node::Marker for Named<Construct<'brand, J>> {
223    type CachedData = NamedConstructData<'brand, J>;
224    type Witness = WitnessOrHole;
225    type Disconnect = Arc<NamedConstructNode<'brand, J>>;
226    type SharingId = <Construct<'brand, J> as node::Marker>::SharingId;
227    type Jet = J;
228
229    fn compute_sharing_id(cmr: Cmr, cached_data: &Self::CachedData) -> Option<Self::SharingId> {
230        Construct::<J>::compute_sharing_id(cmr, &cached_data.internal)
231    }
232}
233
234#[derive(Clone, Debug)]
235pub struct NamedConstructData<'brand, J> {
236    /// Data related to the node itself
237    internal: ConstructData<'brand, J>,
238    /// Name assigned to the node
239    name: Arc<str>,
240    /// Position of the node, if it comes from source code.
241    position: Position,
242    /// User-provided type bounds on the source (will be checked for consistency
243    /// but only after the type checking has completed.)
244    user_source_types: Arc<[types::Type<'brand>]>,
245    /// User-provided type bounds on the target (will be checked for consistency
246    /// but only after the type checking has completed.)
247    user_target_types: Arc<[types::Type<'brand>]>,
248}
249
250impl<'brand, J: Jet> NamedConstructNode<'brand, J> {
251    /// Construct a named construct node from parts.
252    pub fn new(
253        inference_context: &types::Context<'brand>,
254        name: Arc<str>,
255        position: Position,
256        user_source_types: Arc<[types::Type<'brand>]>,
257        user_target_types: Arc<[types::Type<'brand>]>,
258        inner: node::Inner<Arc<Self>, J, Arc<Self>, WitnessOrHole>,
259    ) -> Result<Self, types::Error> {
260        let construct_data = ConstructData::from_inner(
261            inference_context,
262            inner
263                .as_ref()
264                .map(|data| &data.cached_data().internal)
265                .map_disconnect(|_| &None)
266                .map_witness(|_| None),
267        )?;
268        let named_data = NamedConstructData {
269            internal: construct_data,
270            name,
271            position,
272            user_source_types,
273            user_target_types,
274        };
275        Ok(Node::from_parts(inner, named_data))
276    }
277
278    /// Creates a copy of a node with a different name.
279    pub fn renamed(&self, new_name: Arc<str>) -> Self {
280        let data = NamedConstructData {
281            internal: self.cached_data().internal.clone(),
282            user_source_types: Arc::clone(&self.cached_data().user_source_types),
283            user_target_types: Arc::clone(&self.cached_data().user_target_types),
284            name: new_name,
285            position: self.position(),
286        };
287        Self::from_parts(self.inner().clone(), data)
288    }
289
290    /// Accessor for the node's name
291    pub fn name(&self) -> &Arc<str> {
292        &self.cached_data().name
293    }
294
295    /// Accessor for the node's position
296    pub fn position(&self) -> Position {
297        self.cached_data().position
298    }
299
300    /// Accessor for the node's arrow
301    pub fn arrow(&self) -> &Arrow<'brand> {
302        self.cached_data().internal.arrow()
303    }
304
305    /// Accessor for the node's type inference context.
306    pub fn inference_context(&self) -> &types::Context<'brand> {
307        self.cached_data().internal.inference_context()
308    }
309
310    /// Finalizes the types of the underlying [`crate::ConstructNode`].
311    pub fn finalize_types_main(&self) -> Result<Arc<NamedCommitNode<J>>, ErrorSet> {
312        self.finalize_types_inner(true)
313    }
314
315    /// Finalizes the types of the underlying [`crate::ConstructNode`], without setting
316    /// the root node's arrow to 1->1.
317    pub fn finalize_types_non_main(&self) -> Result<Arc<NamedCommitNode<J>>, ErrorSet> {
318        self.finalize_types_inner(false)
319    }
320
321    pub fn finalize_types_inner(
322        &self,
323        for_main: bool,
324    ) -> Result<Arc<NamedCommitNode<J>>, ErrorSet> {
325        struct FinalizeTypes<J: Jet> {
326            for_main: bool,
327            errors: ErrorSet,
328            pending_hole_error: Option<(Position, Error)>,
329            phantom: PhantomData<J>,
330        }
331
332        impl<'brand, J: Jet> Converter<Named<Construct<'brand, J>>, Named<Commit<J>>> for FinalizeTypes<J> {
333            type Error = ErrorSet;
334
335            fn visit_node(&mut self, data: &PostOrderIterItem<&NamedConstructNode<J>>) {
336                // If we encounter a typed hole, this is an error *except* when the typed
337                // hole is the right child of a disconnect combinator. Conveniently, this
338                // case is very easy to detect: it will always appear as a hole immediately
339                // followed by a disconnect.
340                //
341                // Less conveniently, detecting this from within a post-order-iterator
342                // requires a small state machine here: when we encounter a hole, we create
343                // an error and put it in `self.pending_hole_error`. If we then encounter a
344                // disconnect, we drop the error. Otherwise we move it to `self.errors`.
345                let inner = data.node.inner();
346                if let node::Inner::Disconnect(..) = inner {
347                    self.pending_hole_error = None;
348                } else {
349                    if let Some((position, error)) = self.pending_hole_error.take() {
350                        self.errors.add(position, error);
351                    }
352                    if let node::Inner::Witness(WitnessOrHole::TypedHole(name)) = inner {
353                        let arrow_source = data.node.arrow().source.to_incomplete();
354                        let arrow_target = data.node.arrow().source.to_incomplete();
355
356                        self.pending_hole_error = Some((
357                            data.node.position(),
358                            Error::HoleAtCommitTime {
359                                name: Arc::clone(name),
360                                arrow_source,
361                                arrow_target,
362                            },
363                        ));
364                    }
365                }
366            }
367
368            fn convert_witness(
369                &mut self,
370                _: &PostOrderIterItem<&NamedConstructNode<J>>,
371                _: &WitnessOrHole,
372            ) -> Result<NoWitness, Self::Error> {
373                Ok(NoWitness)
374            }
375
376            fn convert_disconnect(
377                &mut self,
378                data: &PostOrderIterItem<&NamedConstructNode<J>>,
379                _: Option<&Arc<NamedCommitNode<J>>>,
380                disc: &Arc<NamedConstructNode<J>>,
381            ) -> Result<Arc<str>, Self::Error> {
382                match disc.inner() {
383                    node::Inner::Witness(WitnessOrHole::TypedHole(hole_name)) => {
384                        Ok(hole_name.clone())
385                    }
386                    _ => {
387                        self.errors
388                            .add(data.node.position(), Error::HoleFilledAtCommitTime);
389                        Ok(Arc::from(""))
390                    }
391                }
392            }
393
394            fn convert_data(
395                &mut self,
396                data: &PostOrderIterItem<&NamedConstructNode<J>>,
397                inner: node::Inner<&Arc<NamedCommitNode<J>>, J, &Arc<str>, &NoWitness>,
398            ) -> Result<NamedCommitData<J>, Self::Error> {
399                let converted_data = inner
400                    .as_ref()
401                    .map(|node| &node.cached_data().internal)
402                    .map_disconnect(|_| &NoDisconnect)
403                    .copy_witness();
404
405                let ctx = data.node.inference_context();
406
407                if !self.for_main {
408                    // For non-`main` fragments, treat the ascriptions as normative, and apply them
409                    // before finalizing the type.
410                    let arrow = data.node.arrow();
411                    for ty in data.node.cached_data().user_source_types.as_ref() {
412                        if let Err(e) =
413                            ctx.unify(&arrow.source, ty, "binding source type annotation")
414                        {
415                            self.errors.add(data.node.position(), e);
416                        }
417                    }
418                    for ty in data.node.cached_data().user_target_types.as_ref() {
419                        if let Err(e) =
420                            ctx.unify(&arrow.target, ty, "binding target type annotation")
421                        {
422                            self.errors.add(data.node.position(), e);
423                        }
424                    }
425                }
426
427                let commit_data = match CommitData::new(data.node.arrow(), converted_data) {
428                    Ok(commit_data) => Arc::new(commit_data),
429                    Err(e) => {
430                        self.errors.add(data.node.position(), e);
431                        return Err(self.errors.clone());
432                    }
433                };
434
435                if self.for_main {
436                    // For `main`, only apply type ascriptions *after* inference has completely
437                    // determined the type.
438                    let source_ty =
439                        types::Type::complete(ctx, Arc::clone(&commit_data.arrow().source));
440                    for ty in data.node.cached_data().user_source_types.as_ref() {
441                        if let Err(e) = ctx.unify(&source_ty, ty, "binding source type annotation")
442                        {
443                            self.errors.add(data.node.position(), e);
444                        }
445                    }
446                    let target_ty =
447                        types::Type::complete(ctx, Arc::clone(&commit_data.arrow().target));
448                    for ty in data.node.cached_data().user_target_types.as_ref() {
449                        if let Err(e) = ctx.unify(&target_ty, ty, "binding target type annotation")
450                        {
451                            self.errors.add(data.node.position(), e);
452                        }
453                    }
454                }
455
456                Ok(NamedCommitData {
457                    name: Arc::clone(&data.node.cached_data().name),
458                    internal: commit_data,
459                })
460            }
461        }
462
463        let mut finalizer = FinalizeTypes {
464            for_main,
465            errors: ErrorSet::default(),
466            pending_hole_error: None,
467            phantom: PhantomData,
468        };
469
470        if for_main {
471            let ctx = self.inference_context();
472            let unit_ty = types::Type::unit(ctx);
473            if self.cached_data().user_source_types.is_empty() {
474                if let Err(e) = ctx.unify(
475                    &self.arrow().source,
476                    &unit_ty,
477                    "setting root source to unit",
478                ) {
479                    finalizer.errors.add(self.position(), e);
480                }
481            }
482            if self.cached_data().user_target_types.is_empty() {
483                if let Err(e) = ctx.unify(
484                    &self.arrow().target,
485                    &unit_ty,
486                    "setting root target to unit",
487                ) {
488                    finalizer.errors.add(self.position(), e);
489                }
490            }
491        }
492
493        let root = self.convert::<InternalSharing, _, _>(&mut finalizer)?;
494        finalizer.errors.into_result(root)
495    }
496}
497
498#[derive(Clone, Debug)]
499pub struct Namer {
500    const_idx: usize,
501    wit_idx: usize,
502    other_idx: usize,
503    root_cmr: Option<Cmr>,
504}
505
506impl Namer {
507    /// Costruct a new `Namer`. Will assign the name `main` to the node with
508    /// the given CMR.
509    pub fn new_rooted(root_cmr: Cmr) -> Self {
510        Namer {
511            const_idx: 0,
512            wit_idx: 0,
513            other_idx: 0,
514            root_cmr: Some(root_cmr),
515        }
516    }
517
518    /// Costruct a new `Namer`.
519    pub fn new() -> Self {
520        Namer {
521            const_idx: 0,
522            wit_idx: 0,
523            other_idx: 0,
524            root_cmr: None,
525        }
526    }
527
528    /// Generate a fresh name for the given node.
529    pub fn assign_name<C, J, X>(&mut self, inner: node::Inner<C, J, X, &WitnessOrHole>) -> String {
530        let prefix = match inner {
531            node::Inner::Iden => "id",
532            node::Inner::Unit => "ut",
533            node::Inner::InjL(..) => "jl",
534            node::Inner::InjR(..) => "jr",
535            node::Inner::Drop(..) => "dp",
536            node::Inner::Take(..) => "tk",
537            node::Inner::Comp(..) => "cp",
538            node::Inner::Case(..) => "cs",
539            node::Inner::AssertL(..) => "asstl",
540            node::Inner::AssertR(..) => "asstr",
541            node::Inner::Pair(..) => "pr",
542            node::Inner::Disconnect(..) => "disc",
543            node::Inner::Witness(WitnessOrHole::Witness) => "wit",
544            node::Inner::Witness(WitnessOrHole::TypedHole(name)) => {
545                return name.to_string();
546            }
547            node::Inner::Fail(..) => "FAIL",
548            node::Inner::Jet(..) => "jt",
549            node::Inner::Word(..) => "const",
550        };
551        let index = match inner {
552            node::Inner::Word(..) => &mut self.const_idx,
553            node::Inner::Witness(..) => &mut self.wit_idx,
554            _ => &mut self.other_idx,
555        };
556        *index += 1;
557        format!("{}{}", prefix, index)
558    }
559}
560
561impl<J: Jet> Converter<Commit<J>, Named<Commit<J>>> for Namer {
562    type Error = ();
563    fn convert_witness(
564        &mut self,
565        _: &PostOrderIterItem<&CommitNode<J>>,
566        _: &NoWitness,
567    ) -> Result<NoWitness, Self::Error> {
568        Ok(NoWitness)
569    }
570
571    fn convert_disconnect(
572        &mut self,
573        _: &PostOrderIterItem<&CommitNode<J>>,
574        _: Option<&Arc<NamedCommitNode<J>>>,
575        _: &NoDisconnect,
576    ) -> Result<Arc<str>, Self::Error> {
577        let hole_idx = self.other_idx;
578        self.other_idx += 1;
579        Ok(Arc::from(format!("hole {hole_idx}")))
580    }
581
582    fn convert_data(
583        &mut self,
584        data: &PostOrderIterItem<&CommitNode<J>>,
585        inner: node::Inner<&Arc<NamedCommitNode<J>>, J, &Arc<str>, &NoWitness>,
586    ) -> Result<NamedCommitData<J>, Self::Error> {
587        // Special-case the root node, which is always called main.
588        // The CMR of the root node, conveniently, is guaranteed to be
589        // unique, so we can key on the CMR to figure out which node to do.
590        if Some(data.node.cmr()) == self.root_cmr {
591            return Ok(NamedCommitData {
592                internal: Arc::clone(data.node.cached_data()),
593                name: Arc::from("main"),
594            });
595        }
596
597        Ok(NamedCommitData {
598            internal: Arc::clone(data.node.cached_data()),
599            name: Arc::from(
600                self.assign_name(inner.map_witness(WitnessOrHole::from).as_ref())
601                    .as_str(),
602            ),
603        })
604    }
605}
simplicity/human_encoding/named_node.rs

simplicity/human_encoding/
named_node.rs
