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

simplicity/human_encoding/
named_node.rs
