Skip to main content

clm_rust_core/layer0/term/
parse.rs

1//! Parse the lambda surface syntax into a locally nameless term (INV-626).
2//!
3//! ```text
4//! term ::= atom+                      -- application, left associative
5//! atom ::= name | '"' text '"' | ("λ" | "\\") name "." term | "(" term ")"
6//! ```
7//!
8//! A name bound by an enclosing abstraction becomes its de Bruijn index and any other name stays a
9//! free variable, so two sources that differ only in bound names parse to equal terms. A quoted string
10//! is a free variable whose name keeps its quotes. A position counts characters, not bytes, so it
11//! matches the Python and TypeScript cores on `λ` and other non-ASCII input.
12
13use super::Term;
14use regex::Regex;
15use std::sync::LazyLock;
16use crate::layer0::limits::{SPEC_ASCII_CR, SPEC_ASCII_LF, SPEC_ASCII_SPACE, SPEC_ASCII_TAB};
17use crate::layer0::vocabulary::{
18    GUARD_BACKSLASH, GUARD_DOT, GUARD_DQUOTE, GUARD_LPAREN, GUARD_RPAREN, GUARD_SQUOTE, GUARD_UNDERSCORE,
19    TERM_PARSE_EXPECTED_AT_END, TERM_PARSE_EXPECTED_FOUND, TERM_PARSE_EXPECTED_PARAMETER,
20    TERM_PARSE_EXPECTED_TERM, TERM_PARSE_EXPECTED_VARIABLE, TERM_PARSE_UNEXPECTED,
21    TERM_PARSE_UNTERMINATED_STRING, TERM_PLACEHOLDER_EXPECTED, TERM_PLACEHOLDER_FOUND,
22    TERM_PLACEHOLDER_POSITION, TERM_SYNTAX_LAMBDA, TERM_SYNTAX_NAME_PART, TERM_SYNTAX_NAME_START,
23};
24
25#[derive(Clone, Debug, PartialEq, Eq, Hash)]
26pub struct ParseFailure {
27    pub message: String,
28    pub position: usize,
29}
30
31pub fn parse(source: &str) -> Result<Term, ParseFailure> {
32    let mut parser = Parser { source: source.trim_matches(is_whitespace).chars().collect(), position: 0, scope: Vec::new() };
33    let term = parser.term()?;
34    parser.skip_whitespace();
35    match parser.peek() {
36        Some(found) => Err(failure(TERM_PARSE_UNEXPECTED, parser.position, "", &found.to_string())),
37        None => Ok(term),
38    }
39}
40
41fn failure(template: &str, position: usize, expected: &str, found: &str) -> ParseFailure {
42    let message = template
43        .replace(TERM_PLACEHOLDER_POSITION, &position.to_string())
44        .replace(TERM_PLACEHOLDER_EXPECTED, expected)
45        .replace(TERM_PLACEHOLDER_FOUND, found);
46    ParseFailure { message, position }
47}
48
49/// The grammar's whitespace, between tokens and around the source alike, in all three runtimes.
50fn is_whitespace(char: char) -> bool {
51    [SPEC_ASCII_SPACE, SPEC_ASCII_TAB, SPEC_ASCII_LF, SPEC_ASCII_CR].contains(&i64::from(u32::from(char)))
52}
53
54/// Python's `str.isalpha` and `str.isalnum` on one code point, by Unicode general category.
55static NAME_START: LazyLock<Regex> = LazyLock::new(|| Regex::new(TERM_SYNTAX_NAME_START).expect(TERM_SYNTAX_NAME_START));
56static NAME_PART: LazyLock<Regex> = LazyLock::new(|| Regex::new(TERM_SYNTAX_NAME_PART).expect(TERM_SYNTAX_NAME_PART));
57
58fn is_letter(char: char) -> bool {
59    NAME_START.is_match(&String::from(char))
60}
61
62fn is(char: char, text: &str) -> bool {
63    text.chars().eq(std::iter::once(char))
64}
65
66fn is_binder(char: char) -> bool {
67    is(char, TERM_SYNTAX_LAMBDA) || is(char, GUARD_BACKSLASH)
68}
69
70fn in_name(char: char) -> bool {
71    NAME_PART.is_match(&String::from(char)) || is(char, GUARD_SQUOTE) || is(char, GUARD_UNDERSCORE)
72}
73
74fn starts_atom(char: char) -> bool {
75    is_binder(char) || is(char, GUARD_LPAREN) || is(char, GUARD_DQUOTE) || is(char, GUARD_UNDERSCORE) || is_letter(char)
76}
77
78struct Parser {
79    source: Vec<char>,
80    position: usize,
81    scope: Vec<String>,
82}
83
84impl Parser {
85    fn peek(&self) -> Option<char> {
86        self.source.get(self.position).copied()
87    }
88
89    fn skip_whitespace(&mut self) {
90        while self.peek().is_some_and(is_whitespace) {
91            self.position += 1;
92        }
93    }
94
95    fn expect(&mut self, expected: &str) -> Result<(), ParseFailure> {
96        self.skip_whitespace();
97        match self.peek() {
98            None => Err(failure(TERM_PARSE_EXPECTED_AT_END, self.position, expected, "")),
99            Some(found) if !is(found, expected) => {
100                Err(failure(TERM_PARSE_EXPECTED_FOUND, self.position, expected, &found.to_string()))
101            }
102            Some(_) => {
103                self.position += 1;
104                Ok(())
105            }
106        }
107    }
108
109    fn take_name(&mut self) -> String {
110        let start = self.position;
111        while self.peek().is_some_and(in_name) {
112            self.position += 1;
113        }
114        self.source[start..self.position].iter().collect()
115    }
116
117    fn term(&mut self) -> Result<Term, ParseFailure> {
118        let mut term: Option<Term> = None;
119        loop {
120            self.skip_whitespace();
121            let Some(char) = self.peek().filter(|char| starts_atom(*char)) else { break };
122            let atom = self.atom(char)?;
123            term = Some(match term {
124                Some(func) => Term::app(func, atom),
125                None => atom,
126            });
127        }
128        term.ok_or_else(|| failure(TERM_PARSE_EXPECTED_TERM, self.position, "", ""))
129    }
130
131    fn atom(&mut self, char: char) -> Result<Term, ParseFailure> {
132        if is_binder(char) {
133            return self.abstraction();
134        }
135        if is(char, GUARD_LPAREN) {
136            self.expect(GUARD_LPAREN)?;
137            let term = self.term()?;
138            self.expect(GUARD_RPAREN)?;
139            return Ok(term);
140        }
141        if is(char, GUARD_DQUOTE) {
142            return self.string();
143        }
144        if !is_letter(char) {
145            return Err(failure(TERM_PARSE_EXPECTED_VARIABLE, self.position, "", ""));
146        }
147        let name = self.take_name();
148        Ok(self.variable(name))
149    }
150
151    fn variable(&self, name: String) -> Term {
152        match self.scope.iter().rev().position(|bound| *bound == name) {
153            Some(index) => Term::BoundVar(index),
154            None => Term::FreeVar(name),
155        }
156    }
157
158    fn string(&mut self) -> Result<Term, ParseFailure> {
159        let start = self.position;
160        self.position += 1;
161        while self.peek().is_some_and(|char| !is(char, GUARD_DQUOTE)) {
162            self.position += 1;
163        }
164        if self.peek().is_none() {
165            return Err(failure(TERM_PARSE_UNTERMINATED_STRING, start, "", ""));
166        }
167        self.position += 1;
168        Ok(Term::FreeVar(self.source[start..self.position].iter().collect()))
169    }
170
171    fn abstraction(&mut self) -> Result<Term, ParseFailure> {
172        self.position += 1;
173        self.skip_whitespace();
174        let hint = self.take_name();
175        if hint.is_empty() {
176            return Err(failure(TERM_PARSE_EXPECTED_PARAMETER, self.position, "", ""));
177        }
178        self.expect(GUARD_DOT)?;
179        self.scope.push(hint.clone());
180        let body = self.term();
181        self.scope.pop();
182        Ok(Term::abs(body?, hint))
183    }
184}