clm-kernel 0.0.24

Cubical Logic Model (CLM) sovereign execution engine, CPN-VM, and Cordis spatiotemporal substrate
Documentation
//! Parse the lambda surface syntax into a locally nameless term (INV-626).
//!
//! ```text
//! term ::= atom+                      -- application, left associative
//! atom ::= name | '"' text '"' | ("λ" | "\\") name "." term | "(" term ")"
//! ```
//!
//! A name bound by an enclosing abstraction becomes its de Bruijn index and any other name stays a
//! free variable, so two sources that differ only in bound names parse to equal terms. A quoted string
//! is a free variable whose name keeps its quotes. A position counts characters, not bytes, so it
//! matches the Python and TypeScript cores on `λ` and other non-ASCII input.

use super::Term;
use regex::Regex;
use std::sync::LazyLock;
use crate::layer0::limits::{SPEC_ASCII_CR, SPEC_ASCII_LF, SPEC_ASCII_SPACE, SPEC_ASCII_TAB};
use crate::layer0::vocabulary::{
    GUARD_BACKSLASH, GUARD_DOT, GUARD_DQUOTE, GUARD_LPAREN, GUARD_RPAREN, GUARD_SQUOTE, GUARD_UNDERSCORE,
    TERM_PARSE_EXPECTED_AT_END, TERM_PARSE_EXPECTED_FOUND, TERM_PARSE_EXPECTED_PARAMETER,
    TERM_PARSE_EXPECTED_TERM, TERM_PARSE_EXPECTED_VARIABLE, TERM_PARSE_UNEXPECTED,
    TERM_PARSE_UNTERMINATED_STRING, TERM_PLACEHOLDER_EXPECTED, TERM_PLACEHOLDER_FOUND,
    TERM_PLACEHOLDER_POSITION, TERM_SYNTAX_LAMBDA, TERM_SYNTAX_NAME_PART, TERM_SYNTAX_NAME_START,
};

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct ParseFailure {
    pub message: String,
    pub position: usize,
}

pub fn parse(source: &str) -> Result<Term, ParseFailure> {
    let mut parser = Parser { source: source.trim_matches(is_whitespace).chars().collect(), position: 0, scope: Vec::new() };
    let term = parser.term()?;
    parser.skip_whitespace();
    match parser.peek() {
        Some(found) => Err(failure(TERM_PARSE_UNEXPECTED, parser.position, "", &found.to_string())),
        None => Ok(term),
    }
}

fn failure(template: &str, position: usize, expected: &str, found: &str) -> ParseFailure {
    let message = template
        .replace(TERM_PLACEHOLDER_POSITION, &position.to_string())
        .replace(TERM_PLACEHOLDER_EXPECTED, expected)
        .replace(TERM_PLACEHOLDER_FOUND, found);
    ParseFailure { message, position }
}

/// The grammar's whitespace, between tokens and around the source alike, in all three runtimes.
fn is_whitespace(char: char) -> bool {
    [SPEC_ASCII_SPACE, SPEC_ASCII_TAB, SPEC_ASCII_LF, SPEC_ASCII_CR].contains(&i64::from(u32::from(char)))
}

/// Python's `str.isalpha` and `str.isalnum` on one code point, by Unicode general category.
static NAME_START: LazyLock<Regex> = LazyLock::new(|| Regex::new(TERM_SYNTAX_NAME_START).expect(TERM_SYNTAX_NAME_START));
static NAME_PART: LazyLock<Regex> = LazyLock::new(|| Regex::new(TERM_SYNTAX_NAME_PART).expect(TERM_SYNTAX_NAME_PART));

fn is_letter(char: char) -> bool {
    NAME_START.is_match(&String::from(char))
}

fn is(char: char, text: &str) -> bool {
    text.chars().eq(std::iter::once(char))
}

fn is_binder(char: char) -> bool {
    is(char, TERM_SYNTAX_LAMBDA) || is(char, GUARD_BACKSLASH)
}

fn in_name(char: char) -> bool {
    NAME_PART.is_match(&String::from(char)) || is(char, GUARD_SQUOTE) || is(char, GUARD_UNDERSCORE)
}

fn starts_atom(char: char) -> bool {
    is_binder(char) || is(char, GUARD_LPAREN) || is(char, GUARD_DQUOTE) || is(char, GUARD_UNDERSCORE) || is_letter(char)
}

struct Parser {
    source: Vec<char>,
    position: usize,
    scope: Vec<String>,
}

impl Parser {
    fn peek(&self) -> Option<char> {
        self.source.get(self.position).copied()
    }

    fn skip_whitespace(&mut self) {
        while self.peek().is_some_and(is_whitespace) {
            self.position += 1;
        }
    }

    fn expect(&mut self, expected: &str) -> Result<(), ParseFailure> {
        self.skip_whitespace();
        match self.peek() {
            None => Err(failure(TERM_PARSE_EXPECTED_AT_END, self.position, expected, "")),
            Some(found) if !is(found, expected) => {
                Err(failure(TERM_PARSE_EXPECTED_FOUND, self.position, expected, &found.to_string()))
            }
            Some(_) => {
                self.position += 1;
                Ok(())
            }
        }
    }

    fn take_name(&mut self) -> String {
        let start = self.position;
        while self.peek().is_some_and(in_name) {
            self.position += 1;
        }
        self.source[start..self.position].iter().collect()
    }

    fn term(&mut self) -> Result<Term, ParseFailure> {
        let mut term: Option<Term> = None;
        loop {
            self.skip_whitespace();
            let Some(char) = self.peek().filter(|char| starts_atom(*char)) else { break };
            let atom = self.atom(char)?;
            term = Some(match term {
                Some(func) => Term::app(func, atom),
                None => atom,
            });
        }
        term.ok_or_else(|| failure(TERM_PARSE_EXPECTED_TERM, self.position, "", ""))
    }

    fn atom(&mut self, char: char) -> Result<Term, ParseFailure> {
        if is_binder(char) {
            return self.abstraction();
        }
        if is(char, GUARD_LPAREN) {
            self.expect(GUARD_LPAREN)?;
            let term = self.term()?;
            self.expect(GUARD_RPAREN)?;
            return Ok(term);
        }
        if is(char, GUARD_DQUOTE) {
            return self.string();
        }
        if !is_letter(char) {
            return Err(failure(TERM_PARSE_EXPECTED_VARIABLE, self.position, "", ""));
        }
        let name = self.take_name();
        Ok(self.variable(name))
    }

    fn variable(&self, name: String) -> Term {
        match self.scope.iter().rev().position(|bound| *bound == name) {
            Some(index) => Term::BoundVar(index),
            None => Term::FreeVar(name),
        }
    }

    fn string(&mut self) -> Result<Term, ParseFailure> {
        let start = self.position;
        self.position += 1;
        while self.peek().is_some_and(|char| !is(char, GUARD_DQUOTE)) {
            self.position += 1;
        }
        if self.peek().is_none() {
            return Err(failure(TERM_PARSE_UNTERMINATED_STRING, start, "", ""));
        }
        self.position += 1;
        Ok(Term::FreeVar(self.source[start..self.position].iter().collect()))
    }

    fn abstraction(&mut self) -> Result<Term, ParseFailure> {
        self.position += 1;
        self.skip_whitespace();
        let hint = self.take_name();
        if hint.is_empty() {
            return Err(failure(TERM_PARSE_EXPECTED_PARAMETER, self.position, "", ""));
        }
        self.expect(GUARD_DOT)?;
        self.scope.push(hint.clone());
        let body = self.term();
        self.scope.pop();
        Ok(Term::abs(body?, hint))
    }
}