Skip to main content

clm_rust_core/layer0/term/
render.rs

1//! Render a term as text (INV-626).
2//!
3//! Rendering gives every binder a name. `name_binders` keeps a binder's hint unless the body refers to
4//! another variable of that name, and then adds primes until the name is free. The rendered text
5//! therefore parses back to an equal term.
6
7use std::collections::BTreeSet;
8
9use super::{free_names, Collection, Hint, Lit, Term};
10use crate::layer0::vocabulary::{
11    GUARD_BACKSLASH, GUARD_COLON, GUARD_DOT, GUARD_DQUOTE, GUARD_LIT_FALSE, GUARD_LIT_NULL, GUARD_LIT_TRUE,
12    GUARD_LPAREN, GUARD_RPAREN, GUARD_SQUOTE, GUARD_UNDERSCORE, TERM_DEFAULT_HINT, TERM_KIND_VERDICT,
13    TERM_SYNTAX_LAMBDA, TERM_SYNTAX_LIST_CLOSE, TERM_SYNTAX_LIST_OPEN, TERM_SYNTAX_MAP_CLOSE,
14    TERM_SYNTAX_MAP_OPEN, TERM_SYNTAX_SEPARATOR, TERM_SYNTAX_SPACE,
15};
16
17/// How far outside `term` each of its dangling bound indices points: 0 is the nearest enclosing binder.
18fn outer_references(term: &Term, depth: usize, found: &mut BTreeSet<usize>) {
19    if let Term::BoundVar(index) = term {
20        if *index >= depth {
21            found.insert(index - depth);
22        }
23        return;
24    }
25    let inner = depth + usize::from(matches!(term, Term::Abs(..)));
26    for child in term.children() {
27        outer_references(child, inner, found);
28    }
29}
30
31/// `term` with every hint replaced by a name that no variable in the binder's body already uses.
32pub fn name_binders(term: &Term) -> Term {
33    name_within(term, &mut Vec::new())
34}
35
36fn name_within(term: &Term, scope: &mut Vec<String>) -> Term {
37    let Term::Abs(body, hint) = term else {
38        return term.map_children(|child| name_within(child, scope));
39    };
40    let mut taken = free_names(body);
41    let mut distances = BTreeSet::new();
42    outer_references(body, 0, &mut distances);
43    taken.extend(
44        distances.into_iter().filter(|distance| (1..=scope.len()).contains(distance)).map(|distance| scope[scope.len() - distance].clone()),
45    );
46    let mut name = if hint.0.is_empty() { TERM_DEFAULT_HINT.to_string() } else { hint.0.clone() };
47    while taken.contains(&name) {
48        name.push_str(GUARD_SQUOTE);
49    }
50    scope.push(name.clone());
51    let body = name_within(body, scope);
52    scope.pop();
53    Term::Abs(Box::new(body), Hint(name))
54}
55
56fn quoted(text: &str) -> String {
57    let escaped = text
58        .replace(GUARD_BACKSLASH, &[GUARD_BACKSLASH, GUARD_BACKSLASH].concat())
59        .replace(GUARD_DQUOTE, &[GUARD_BACKSLASH, GUARD_DQUOTE].concat());
60    [GUARD_DQUOTE, &escaped, GUARD_DQUOTE].concat()
61}
62
63fn call(name: &str, parts: &[String]) -> String {
64    [name, GUARD_LPAREN, &parts.join(TERM_SYNTAX_SEPARATOR), GUARD_RPAREN].concat()
65}
66
67pub fn render_literal(lit: &Lit) -> String {
68    match lit {
69        Lit::Null => GUARD_LIT_NULL.to_string(),
70        Lit::Boolean(value) => (if *value { GUARD_LIT_TRUE } else { GUARD_LIT_FALSE }).to_string(),
71        Lit::Integer(value) => value.to_string(),
72        Lit::Decimal(text) => text.clone(),
73        Lit::String(text) => quoted(text),
74        Lit::Verdict(verdict) => call(
75            TERM_KIND_VERDICT,
76            &[verdict.outcome.clone(), quoted(&verdict.reason), quoted(&verdict.invariant_code)],
77        ),
78        Lit::Collection(Collection::Map(entries)) if !entries.is_empty() => {
79            let entries: Vec<String> = entries
80                .iter()
81                .map(|(key, item)| [quoted(key).as_str(), GUARD_COLON, TERM_SYNTAX_SPACE, &render_literal(item)].concat())
82                .collect();
83            [TERM_SYNTAX_MAP_OPEN, &entries.join(TERM_SYNTAX_SEPARATOR), TERM_SYNTAX_MAP_CLOSE].concat()
84        }
85        Lit::Collection(collection) => {
86            let items: Vec<String> = match collection {
87                Collection::List(items) => items.iter().map(render_literal).collect(),
88                Collection::Map(_) => Vec::new(),
89            };
90            [TERM_SYNTAX_LIST_OPEN, &items.join(TERM_SYNTAX_SEPARATOR), TERM_SYNTAX_LIST_CLOSE].concat()
91        }
92    }
93}
94
95fn render_within(term: &Term, scope: &mut Vec<String>, out: &mut String) {
96    match term {
97        Term::BoundVar(index) if *index < scope.len() => out.push_str(&scope[scope.len() - 1 - index]),
98        Term::BoundVar(index) => {
99            out.push_str(GUARD_UNDERSCORE);
100            out.push_str(&(index - scope.len()).to_string());
101        }
102        Term::FreeVar(name) => out.push_str(name),
103        Term::Abs(body, hint) => {
104            out.push_str(GUARD_LPAREN);
105            out.push_str(TERM_SYNTAX_LAMBDA);
106            out.push_str(&hint.0);
107            out.push_str(GUARD_DOT);
108            scope.push(hint.0.clone());
109            render_within(body, scope, out);
110            scope.pop();
111            out.push_str(GUARD_RPAREN);
112        }
113        Term::App(func, arg) => {
114            out.push_str(GUARD_LPAREN);
115            render_within(func, scope, out);
116            out.push_str(TERM_SYNTAX_SPACE);
117            render_within(arg, scope, out);
118            out.push_str(GUARD_RPAREN);
119        }
120        Term::Lit(lit) => out.push_str(&render_literal(lit)),
121        Term::Prim(name, args) => {
122            let parts: Vec<String> = args
123                .iter()
124                .map(|arg| {
125                    let mut part = String::new();
126                    render_within(arg, scope, &mut part);
127                    part
128                })
129                .collect();
130            out.push_str(&call(name, &parts));
131        }
132    }
133}
134
135/// `term` as text, in the form `(λx.(x y))`.
136pub fn render(term: &Term) -> String {
137    let mut out = String::new();
138    render_within(&name_binders(term), &mut Vec::new(), &mut out);
139    out
140}