clm-kernel 0.0.24

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Render a term as text (INV-626).
//!
//! Rendering gives every binder a name. `name_binders` keeps a binder's hint unless the body refers to
//! another variable of that name, and then adds primes until the name is free. The rendered text
//! therefore parses back to an equal term.

use std::collections::BTreeSet;

use super::{free_names, Collection, Hint, Lit, Term};
use crate::layer0::vocabulary::{
    GUARD_BACKSLASH, GUARD_COLON, GUARD_DOT, GUARD_DQUOTE, GUARD_LIT_FALSE, GUARD_LIT_NULL, GUARD_LIT_TRUE,
    GUARD_LPAREN, GUARD_RPAREN, GUARD_SQUOTE, GUARD_UNDERSCORE, TERM_DEFAULT_HINT, TERM_KIND_VERDICT,
    TERM_SYNTAX_LAMBDA, TERM_SYNTAX_LIST_CLOSE, TERM_SYNTAX_LIST_OPEN, TERM_SYNTAX_MAP_CLOSE,
    TERM_SYNTAX_MAP_OPEN, TERM_SYNTAX_SEPARATOR, TERM_SYNTAX_SPACE,
};

/// How far outside `term` each of its dangling bound indices points: 0 is the nearest enclosing binder.
fn outer_references(term: &Term, depth: usize, found: &mut BTreeSet<usize>) {
    if let Term::BoundVar(index) = term {
        if *index >= depth {
            found.insert(index - depth);
        }
        return;
    }
    let inner = depth + usize::from(matches!(term, Term::Abs(..)));
    for child in term.children() {
        outer_references(child, inner, found);
    }
}

/// `term` with every hint replaced by a name that no variable in the binder's body already uses.
pub fn name_binders(term: &Term) -> Term {
    name_within(term, &mut Vec::new())
}

fn name_within(term: &Term, scope: &mut Vec<String>) -> Term {
    let Term::Abs(body, hint) = term else {
        return term.map_children(|child| name_within(child, scope));
    };
    let mut taken = free_names(body);
    let mut distances = BTreeSet::new();
    outer_references(body, 0, &mut distances);
    taken.extend(
        distances.into_iter().filter(|distance| (1..=scope.len()).contains(distance)).map(|distance| scope[scope.len() - distance].clone()),
    );
    let mut name = if hint.0.is_empty() { TERM_DEFAULT_HINT.to_string() } else { hint.0.clone() };
    while taken.contains(&name) {
        name.push_str(GUARD_SQUOTE);
    }
    scope.push(name.clone());
    let body = name_within(body, scope);
    scope.pop();
    Term::Abs(Box::new(body), Hint(name))
}

fn quoted(text: &str) -> String {
    let escaped = text
        .replace(GUARD_BACKSLASH, &[GUARD_BACKSLASH, GUARD_BACKSLASH].concat())
        .replace(GUARD_DQUOTE, &[GUARD_BACKSLASH, GUARD_DQUOTE].concat());
    [GUARD_DQUOTE, &escaped, GUARD_DQUOTE].concat()
}

fn call(name: &str, parts: &[String]) -> String {
    [name, GUARD_LPAREN, &parts.join(TERM_SYNTAX_SEPARATOR), GUARD_RPAREN].concat()
}

pub fn render_literal(lit: &Lit) -> String {
    match lit {
        Lit::Null => GUARD_LIT_NULL.to_string(),
        Lit::Boolean(value) => (if *value { GUARD_LIT_TRUE } else { GUARD_LIT_FALSE }).to_string(),
        Lit::Integer(value) => value.to_string(),
        Lit::Decimal(text) => text.clone(),
        Lit::String(text) => quoted(text),
        Lit::Verdict(verdict) => call(
            TERM_KIND_VERDICT,
            &[verdict.outcome.clone(), quoted(&verdict.reason), quoted(&verdict.invariant_code)],
        ),
        Lit::Collection(Collection::Map(entries)) if !entries.is_empty() => {
            let entries: Vec<String> = entries
                .iter()
                .map(|(key, item)| [quoted(key).as_str(), GUARD_COLON, TERM_SYNTAX_SPACE, &render_literal(item)].concat())
                .collect();
            [TERM_SYNTAX_MAP_OPEN, &entries.join(TERM_SYNTAX_SEPARATOR), TERM_SYNTAX_MAP_CLOSE].concat()
        }
        Lit::Collection(collection) => {
            let items: Vec<String> = match collection {
                Collection::List(items) => items.iter().map(render_literal).collect(),
                Collection::Map(_) => Vec::new(),
            };
            [TERM_SYNTAX_LIST_OPEN, &items.join(TERM_SYNTAX_SEPARATOR), TERM_SYNTAX_LIST_CLOSE].concat()
        }
    }
}

fn render_within(term: &Term, scope: &mut Vec<String>, out: &mut String) {
    match term {
        Term::BoundVar(index) if *index < scope.len() => out.push_str(&scope[scope.len() - 1 - index]),
        Term::BoundVar(index) => {
            out.push_str(GUARD_UNDERSCORE);
            out.push_str(&(index - scope.len()).to_string());
        }
        Term::FreeVar(name) => out.push_str(name),
        Term::Abs(body, hint) => {
            out.push_str(GUARD_LPAREN);
            out.push_str(TERM_SYNTAX_LAMBDA);
            out.push_str(&hint.0);
            out.push_str(GUARD_DOT);
            scope.push(hint.0.clone());
            render_within(body, scope, out);
            scope.pop();
            out.push_str(GUARD_RPAREN);
        }
        Term::App(func, arg) => {
            out.push_str(GUARD_LPAREN);
            render_within(func, scope, out);
            out.push_str(TERM_SYNTAX_SPACE);
            render_within(arg, scope, out);
            out.push_str(GUARD_RPAREN);
        }
        Term::Lit(lit) => out.push_str(&render_literal(lit)),
        Term::Prim(name, args) => {
            let parts: Vec<String> = args
                .iter()
                .map(|arg| {
                    let mut part = String::new();
                    render_within(arg, scope, &mut part);
                    part
                })
                .collect();
            out.push_str(&call(name, &parts));
        }
    }
}

/// `term` as text, in the form `(λx.(x y))`.
pub fn render(term: &Term) -> String {
    let mut out = String::new();
    render_within(&name_binders(term), &mut Vec::new(), &mut out);
    out
}