simplicity/human_encoding/
mod.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! The Simplicity Human-Readable Encoding
4//!
5//! This module provides the ability to decode and encode [`NamedCommitNode`]s
6//! in a human-readable format.
7//!
8
9mod error;
10mod named_node;
11mod parse;
12
13use crate::dag::{DagLike, MaxSharing};
14use crate::jet::Jet;
15use crate::node::{self, CommitNode, NoWitness};
16use crate::{Cmr, ConstructNode, Ihr, Value};
17
18use std::collections::HashMap;
19use std::str;
20use std::sync::Arc;
21
22pub use self::error::{Error, ErrorSet};
23pub use self::named_node::NamedCommitNode;
24
25/// Line/column pair
26///
27/// There is a similar type provided by the `santiago` library but it does not implement
28/// `Copy`, among many other traits, which makes it unergonomic to use. Santiago positions
29/// can be converted using `.into()`.
30#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Default, Hash)]
31pub struct Position {
32    line: usize,
33    column: usize,
34}
35
36impl<'a> From<&'a santiago::lexer::Position> for Position {
37    fn from(position: &'a santiago::lexer::Position) -> Position {
38        Position {
39            line: position.line,
40            column: position.column,
41        }
42    }
43}
44
45impl From<santiago::lexer::Position> for Position {
46    fn from(position: santiago::lexer::Position) -> Position {
47        Position {
48            line: position.line,
49            column: position.column,
50        }
51    }
52}
53
54/// For named construct nodes, we abuse the `witness` combinator to support typed holes.
55///
56/// We do this because `witness` nodes have free source and target arrows, and
57/// allow us to store arbitrary data in them using the generic witness type of
58/// the node. Holes are characterized entirely by their source and target type,
59/// just like witnesses, and are labelled by their name.
60#[derive(Debug, PartialEq, Eq, Clone, Hash)]
61pub enum WitnessOrHole {
62    /// This witness is an actual witness combinator (with no witness data attached,
63    /// that comes later)
64    Witness,
65    /// This is a typed hole, with the given name.
66    TypedHole(Arc<str>),
67}
68
69impl WitnessOrHole {
70    pub fn shallow_clone(&self) -> Self {
71        match self {
72            WitnessOrHole::Witness => WitnessOrHole::Witness,
73            WitnessOrHole::TypedHole(name) => WitnessOrHole::TypedHole(Arc::clone(name)),
74        }
75    }
76}
77
78impl From<&'_ NoWitness> for WitnessOrHole {
79    fn from(_: &NoWitness) -> Self {
80        WitnessOrHole::Witness
81    }
82}
83
84#[derive(Clone, Debug, PartialEq, Eq)]
85pub struct Forest<J: Jet> {
86    roots: HashMap<Arc<str>, Arc<NamedCommitNode<J>>>,
87}
88
89impl<J: Jet> Forest<J> {
90    /// Parses a forest from a string
91    pub fn parse(s: &str) -> Result<Self, ErrorSet> {
92        parse::parse(s).map(|roots| Forest { roots })
93    }
94
95    /// Parses a program from a bytestring
96    pub fn from_program(root: Arc<CommitNode<J>>) -> Self {
97        let root = NamedCommitNode::from_node(&root);
98        let mut roots = HashMap::new();
99        roots.insert("main".into(), root);
100        Forest { roots }
101    }
102
103    /// Accessor for the map of roots of this forest
104    pub fn roots(&self) -> &HashMap<Arc<str>, Arc<NamedCommitNode<J>>> {
105        &self.roots
106    }
107
108    /// Serialize the program in human-readable form
109    pub fn string_serialize(&self) -> String {
110        struct Print {
111            cmr: Cmr,
112            ihr: Option<Ihr>,
113            expr_str: String,  // The X = Y part
114            arrow_str: String, // The :: A -> B part
115        }
116        fn print_lines(lines: &[Print], skip_before_end: bool) -> String {
117            let mut ret = String::new();
118            let expr_width = lines.iter().map(|line| line.expr_str.len()).max().unwrap();
119            let arrow_width = lines.iter().map(|line| line.arrow_str.len()).max().unwrap();
120            let last_line = lines.len();
121            for (n, line) in lines.iter().enumerate() {
122                ret += "\n";
123                if skip_before_end && n == last_line - 1 {
124                    ret += "\n";
125                }
126                ret += &format!("-- CMR: {}\n", line.cmr);
127                if let Some(ihr) = line.ihr {
128                    ret += &format!("-- IHR: {}\n", ihr);
129                } else {
130                    ret += "-- IHR: [undetermined]\n";
131                }
132                ret += &format!(
133                    "{0:1$} {2:3$}\n",
134                    line.expr_str, expr_width, line.arrow_str, arrow_width,
135                );
136            }
137            ret
138        }
139
140        let mut witness_lines = vec![];
141        let mut const_lines = vec![];
142        let mut program_lines = vec![];
143        // Pass 1: compute string data for every node
144        for root in self.roots.values() {
145            for data in root.as_ref().post_order_iter::<MaxSharing<_>>() {
146                let node = data.node;
147                let name = node.name();
148                let mut expr_str = match node.inner() {
149                    node::Inner::AssertR(cmr, _) => format!("{} := assertr #{}", name, cmr),
150                    node::Inner::Fail(entropy) => format!("{} := fail {}", name, entropy),
151                    node::Inner::Jet(ref j) => format!("{} := jet_{}", name, j),
152                    node::Inner::Word(ref word) => {
153                        format!("{} := const {}", name, word)
154                    }
155                    inner => format!("{} := {}", name, inner),
156                };
157                if let Some(child) = node.left_child() {
158                    expr_str.push(' ');
159                    expr_str.push_str(child.name());
160                }
161                if let Some(child) = node.right_child() {
162                    expr_str.push(' ');
163                    expr_str.push_str(child.name());
164                } else if let node::Inner::AssertL(_, cmr) = node.inner() {
165                    expr_str.push_str(" #");
166                    expr_str.push_str(&cmr.to_string());
167                } else if let node::Inner::Disconnect(_, hole_name) = node.inner() {
168                    expr_str.push_str(&format!(" ?{}", hole_name));
169                }
170
171                let arrow = node.arrow();
172                let arrow_str = format!(": {} -> {}", arrow.source, arrow.target).replace('×', "*"); // for human-readable encoding stick with ASCII
173
174                let print = Print {
175                    cmr: node.cmr(),
176                    ihr: node.ihr(),
177                    expr_str,
178                    arrow_str,
179                };
180                if let node::Inner::Witness(..) = node.inner() {
181                    witness_lines.push(print);
182                } else if let node::Inner::Word(..) = node.inner() {
183                    const_lines.push(print);
184                } else {
185                    program_lines.push(print);
186                }
187            }
188        }
189
190        // Pass 2: actually print everything
191        let mut ret = String::new();
192        if !witness_lines.is_empty() {
193            ret += "--------------\n-- Witnesses\n--------------\n";
194            ret += &print_lines(&witness_lines, false);
195            ret += "\n";
196        }
197        if !const_lines.is_empty() {
198            // FIXME detect scribes
199            ret += "--------------\n-- Constants\n--------------\n";
200            ret += &print_lines(&const_lines, false);
201            ret += "\n";
202        }
203        if !program_lines.is_empty() {
204            ret += "--------------\n-- Program code\n--------------\n";
205            ret += &print_lines(&program_lines, true /* add a blank line before main */);
206        }
207        ret
208    }
209
210    /// Convert the forest into a witness node.
211    ///
212    /// Succeeds if the forest contains a "main" root and returns `None` otherwise.
213    pub fn to_witness_node(
214        &self,
215        witness: &HashMap<Arc<str>, Value>,
216    ) -> Option<Arc<ConstructNode<J>>> {
217        let main = self.roots.get("main")?;
218        Some(main.to_construct_node(witness, self.roots()))
219    }
220}
221
222#[cfg(test)]
223mod tests {
224    use crate::human_encoding::Forest;
225    use crate::jet::{Core, Jet};
226    use crate::{BitMachine, Value};
227    use std::collections::HashMap;
228    use std::sync::Arc;
229
230    fn assert_finalize_ok<J: Jet>(
231        s: &str,
232        witness: &HashMap<Arc<str>, Value>,
233        env: &J::Environment,
234    ) {
235        let program = Forest::<J>::parse(s)
236            .expect("Failed to parse human encoding")
237            .to_witness_node(witness)
238            .expect("Forest is missing expected root")
239            .finalize_pruned(env)
240            .expect("Failed to finalize");
241        let mut mac = BitMachine::for_program(&program).expect("program has reasonable bounds");
242        mac.exec(&program, env).expect("Failed to run program");
243    }
244
245    fn assert_finalize_err<J: Jet>(
246        s: &str,
247        witness: &HashMap<Arc<str>, Value>,
248        env: &J::Environment,
249        err_msg: &'static str,
250    ) {
251        let program = match Forest::<J>::parse(s)
252            .expect("Failed to parse human encoding")
253            .to_witness_node(witness)
254            .expect("Forest is missing expected root")
255            .finalize_pruned(env)
256        {
257            Ok(program) => program,
258            Err(error) => {
259                assert_eq!(&error.to_string(), err_msg);
260                return;
261            }
262        };
263        let mut mac = BitMachine::for_program(&program).expect("program has reasonable bounds");
264        match mac.exec(&program, env) {
265            Ok(_) => panic!("Execution is expected to fail"),
266            Err(error) => assert_eq!(&error.to_string(), err_msg),
267        }
268    }
269
270    #[test]
271    fn executed_witness_with_value() {
272        let s = "
273            a := witness
274            b := witness
275            main := comp
276                comp
277                    pair a b
278                    jet_lt_8
279                jet_verify
280        ";
281
282        let a_less_than_b = HashMap::from([
283            (Arc::from("a"), Value::u8(0x00)),
284            (Arc::from("b"), Value::u8(0x01)),
285        ]);
286        assert_finalize_ok::<Core>(s, &a_less_than_b, &());
287
288        let b_greater_equal_a = HashMap::from([
289            (Arc::from("a"), Value::u8(0x01)),
290            (Arc::from("b"), Value::u8(0x01)),
291        ]);
292        assert_finalize_err::<Core>(s, &b_greater_equal_a, &(), "Jet failed during execution");
293    }
294
295    #[test]
296    fn executed_witness_without_value() {
297        let witness = HashMap::from([(Arc::from("wit1"), Value::u32(1337))]);
298        assert_finalize_err::<Core>(
299            "
300                wit1 := witness : 1 -> 2^32
301                wit2 := witness : 1 -> 2^32
302
303                wits_are_equal := comp (pair wit1 wit2) jet_eq_32 : 1 -> 2
304                main := comp wits_are_equal jet_verify            : 1 -> 1
305            ",
306            &witness,
307            &(),
308            "Jet failed during execution",
309        );
310    }
311
312    #[test]
313    fn pruned_witness_without_value() {
314        let s = "
315            wit1 := witness : 1 -> 2
316            wit2 := witness : 1 -> 2^64
317            input := pair wit1 unit : 1 -> 2 * 1
318            process := case (drop injr unit) (drop comp wit2 jet_all_64) : 2 * 1 -> 2
319            main := comp input comp process jet_verify : 1 -> 1
320        ";
321        let wit2_is_pruned = HashMap::from([(Arc::from("wit1"), Value::u1(0))]);
322        assert_finalize_ok::<Core>(s, &wit2_is_pruned, &());
323
324        let wit2_is_missing = HashMap::from([(Arc::from("wit1"), Value::u1(1))]);
325        assert_finalize_err::<Core>(s, &wit2_is_missing, &(), "Jet failed during execution");
326
327        let wit2_is_present = HashMap::from([
328            (Arc::from("wit1"), Value::u1(1)),
329            (Arc::from("wit2"), Value::u64(u64::MAX)),
330        ]);
331        assert_finalize_ok::<Core>(s, &wit2_is_present, &());
332    }
333
334    #[test]
335    fn executed_hole_with_value() {
336        let empty = HashMap::new();
337        assert_finalize_ok::<Core>(
338            "
339                id1 := iden : 2^256 * 1 -> 2^256 * 1
340                main := comp (disconnect id1 ?hole) unit
341                hole := unit
342            ",
343            &empty,
344            &(),
345        );
346    }
347
348    #[test]
349    fn executed_hole_without_value() {
350        let empty = HashMap::new();
351        assert_finalize_err::<Core>(
352            "
353                wit1 := witness
354                main := comp wit1 comp disconnect iden ?dis2 unit
355            ",
356            &empty,
357            &(),
358            "disconnect node had one child (redeem time); must have two",
359        );
360    }
361
362    #[test]
363    fn witness_name_override() {
364        let s = "
365            wit1 := witness : 1 -> 2
366            wit2 := wit1 : 1 -> 2
367            main := comp wit2 jet_verify : 1 -> 1
368        ";
369        let wit1_populated = HashMap::from([(Arc::from("wit1"), Value::u1(1))]);
370        assert_finalize_err::<Core>(s, &wit1_populated, &(), "Jet failed during execution");
371
372        let wit2_populated = HashMap::from([(Arc::from("wit2"), Value::u1(1))]);
373        assert_finalize_ok::<Core>(s, &wit2_populated, &());
374    }
375}
simplicity/human_encoding/mod.rs

simplicity/human_encoding/
mod.rs
