clm_rust_core/layer0/term/
parse.rs1use 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
49fn 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
54static 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}