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

simplicity/human_encoding/
mod.rs
