polyspec_crudui_validator/expr/
parser.rs

1//! CRUDUI expression parser: `Vec<Token>` → AST (expressions.md §3/§4, JS/PHP
2//! `Parser` parity).
3//!
4//! Recursive-descent grammar (EBNF, lowest precedence first):
5//!
6//! ```text
7//!   ternary    = or [ "?" ternary ":" ternary ]        (right-associative)
8//!   or         = and { "||" and }
9//!   and        = not { "&&" not }
10//!   not        = "!" not | comparison
11//!   comparison = primary [ cmp_op cmp_value | in_op value_list ]
12//!   primary    = "(" or ")" | path | literal
13//!   path       = [ "." | ".." ] identifier { "." (identifier | number | "*") }
14//! ```
15//!
16//! Priority and right-associativity come from the grammar productions, not a
17//! heuristic. No eval, no split (GRAMMAR §10).
18
19use super::ast::{LiteralValue, Node, PathSegment};
20use super::error::ParseError;
21use super::token::{Literal, Token, TokenType};
22
23/// The most nodes on a path from the root of an expression's syntax tree to a
24/// leaf. A deeper expression is a parse error in every runtime.
25pub const MAX_EXPRESSION_DEPTH: usize = 64;
26
27/// Recursive-descent parser over a lexer's token stream (must end in EOF).
28pub struct Parser {
29    tokens: Vec<Token>,
30    current: usize,
31    /// Nodes whose children are being parsed: each is an ancestor of what comes next.
32    open: usize,
33    /// Height of the node the last parse method returned.
34    height: usize,
35}
36
37impl Parser {
38    /// Build a parser over a token stream.
39    pub fn new(tokens: Vec<Token>) -> Self {
40        Parser {
41            tokens,
42            current: 0,
43            open: 0,
44            height: 0,
45        }
46    }
47
48    /// Parse the full token stream into one AST root. Errors on trailing tokens.
49    pub fn parse(&mut self) -> Result<Node, ParseError> {
50        let expression = self.parse_ternary_expression()?;
51
52        if !self.is_at_end() {
53            return Err(ParseError::new(format!(
54                "Unexpected token after expression: {}",
55                self.peek().value
56            )));
57        }
58
59        Ok(expression)
60    }
61
62    // ternary = or [ "?" ternary ":" ternary ]  (right-associative)
63    fn parse_ternary_expression(&mut self) -> Result<Node, ParseError> {
64        let condition = self.parse_or_expression()?;
65
66        if self.match_type(TokenType::Question) {
67            let condition_height = self.height;
68            self.enter()?;
69            let true_value = self.parse_ternary_expression()?;
70            let true_height = self.height;
71
72            if !self.match_type(TokenType::Colon) {
73                return Err(ParseError::new("Missing colon in ternary expression"));
74            }
75
76            let false_value = self.parse_ternary_expression()?;
77            self.open -= 1;
78
79            self.node(condition_height.max(true_height).max(self.height))?;
80            return Ok(Node::Ternary {
81                condition: Box::new(condition),
82                true_value: Box::new(true_value),
83                false_value: Box::new(false_value),
84            });
85        }
86
87        Ok(condition)
88    }
89
90    // or = and { "||" and }
91    fn parse_or_expression(&mut self) -> Result<Node, ParseError> {
92        let mut left = self.parse_and_expression()?;
93        let mut height = self.height;
94
95        while self.match_type(TokenType::Or) {
96            let right = self.parse_and_expression()?;
97            height = self.node(height.max(self.height))?;
98            left = Node::Binary {
99                operator: "||".to_string(),
100                left: Box::new(left),
101                right: Box::new(right),
102            };
103        }
104
105        Ok(left)
106    }
107
108    // and = not { "&&" not }
109    fn parse_and_expression(&mut self) -> Result<Node, ParseError> {
110        let mut left = self.parse_not_expression()?;
111        let mut height = self.height;
112
113        while self.match_type(TokenType::And) {
114            let right = self.parse_not_expression()?;
115            height = self.node(height.max(self.height))?;
116            left = Node::Binary {
117                operator: "&&".to_string(),
118                left: Box::new(left),
119                right: Box::new(right),
120            };
121        }
122
123        Ok(left)
124    }
125
126    // not = "!" not | comparison
127    fn parse_not_expression(&mut self) -> Result<Node, ParseError> {
128        if self.match_type(TokenType::Not) {
129            self.enter()?;
130            let operand = self.parse_not_expression()?;
131            self.open -= 1;
132            self.node(self.height)?;
133            return Ok(Node::Unary {
134                operator: "!".to_string(),
135                operand: Box::new(operand),
136            });
137        }
138
139        self.parse_comparison()
140    }
141
142    // comparison = primary [ cmp_op cmp_value | in_op value_list ]
143    fn parse_comparison(&mut self) -> Result<Node, ParseError> {
144        let left = self.parse_primary()?;
145        let left_height = self.height;
146
147        if self.match_any(&[TokenType::In, TokenType::NotIn]) {
148            let negated = self.previous().token_type == TokenType::NotIn;
149            let list = self.parse_value_list()?;
150            self.node(left_height)?;
151            return Ok(Node::In {
152                negated,
153                value: Box::new(left),
154                list,
155            });
156        }
157
158        if self.match_any(&[
159            TokenType::Eq,
160            TokenType::Ne,
161            TokenType::Gt,
162            TokenType::Ge,
163            TokenType::Lt,
164            TokenType::Le,
165        ]) {
166            let operator = self.previous().value.clone();
167            let right = self.parse_comparison_value()?;
168            self.node(left_height.max(self.height))?;
169            return Ok(Node::Binary {
170                operator,
171                left: Box::new(left),
172                right: Box::new(right),
173            });
174        }
175
176        Ok(left)
177    }
178
179    // value_list = "[" value { "," value } "]" | value { "," value }
180    fn parse_value_list(&mut self) -> Result<Vec<Node>, ParseError> {
181        let mut values = Vec::new();
182
183        let has_brackets = self.match_type(TokenType::LBracket);
184
185        values.push(self.parse_value_list_item()?);
186
187        while self.match_type(TokenType::Comma) {
188            values.push(self.parse_value_list_item()?);
189        }
190
191        if has_brackets && !self.match_type(TokenType::RBracket) {
192            return Err(ParseError::new("Missing closing bracket in value list"));
193        }
194
195        Ok(values)
196    }
197
198    fn parse_value_list_item(&mut self) -> Result<Node, ParseError> {
199        // Unquoted identifiers in an "in" list are string literals.
200        if self.match_type(TokenType::Identifier) {
201            return Ok(Node::Literal(LiteralValue::Str(
202                self.previous().value.clone(),
203            )));
204        }
205
206        if self.match_type(TokenType::Number) {
207            return Ok(Node::Literal(number_literal(&self.previous().literal)));
208        }
209
210        if self.match_type(TokenType::String) {
211            return Ok(Node::Literal(LiteralValue::Str(string_literal(
212                &self.previous().literal,
213            ))));
214        }
215
216        Err(ParseError::new(format!(
217            "Invalid value in list: {}",
218            self.peek().value
219        )))
220    }
221
222    /// Right-hand side of a comparison. An unquoted identifier with NO following
223    /// dot is a string literal (`.country == US` → 'US'); an identifier followed
224    /// by a dot is a path reference, so backtrack and parse it as a path.
225    fn parse_comparison_value(&mut self) -> Result<Node, ParseError> {
226        if self.check(TokenType::Identifier) {
227            let saved = self.current;
228            self.advance(); // consume identifier
229
230            if !self.check(TokenType::Dot) {
231                self.height = 1;
232                return Ok(Node::Literal(LiteralValue::Str(
233                    self.previous().value.clone(),
234                )));
235            }
236
237            // Followed by a dot → path reference; backtrack.
238            self.current = saved;
239        }
240
241        self.parse_primary()
242    }
243
244    // primary = "(" or ")" | path | literal
245    fn parse_primary(&mut self) -> Result<Node, ParseError> {
246        if self.match_type(TokenType::LParen) {
247            self.enter()?;
248            let expression = self.parse_or_expression()?;
249            self.open -= 1;
250            if !self.match_type(TokenType::RParen) {
251                return Err(ParseError::new("Missing closing parenthesis"));
252            }
253            self.node(self.height)?;
254            return Ok(Node::Group(Box::new(expression)));
255        }
256
257        // A path or a literal is a leaf.
258        self.height = 1;
259
260        if self.check(TokenType::Dot)
261            || self.check(TokenType::DotDot)
262            || self.check(TokenType::Identifier)
263        {
264            return self.parse_path();
265        }
266
267        if self.match_type(TokenType::String) {
268            return Ok(Node::Literal(LiteralValue::Str(string_literal(
269                &self.previous().literal,
270            ))));
271        }
272
273        if self.match_type(TokenType::Number) {
274            return Ok(Node::Literal(number_literal(&self.previous().literal)));
275        }
276
277        if self.match_type(TokenType::Boolean) {
278            let b = matches!(self.previous().literal, Literal::Bool(true));
279            return Ok(Node::Literal(LiteralValue::Bool(b)));
280        }
281
282        if self.match_type(TokenType::Null) {
283            return Ok(Node::Literal(LiteralValue::Null));
284        }
285
286        Err(ParseError::new(format!(
287            "Unexpected token in expression: {}",
288            self.peek().value
289        )))
290    }
291
292    // path = relative_path | absolute_path
293    fn parse_path(&mut self) -> Result<Node, ParseError> {
294        let mut relative = false;
295        let mut levels_up: i64 = 0;
296        let mut segments: Vec<PathSegment> = Vec::new();
297
298        if self.match_type(TokenType::DotDot) {
299            relative = true;
300            let dots = match self.previous().literal {
301                Literal::DotCount(n) => n,
302                _ => 0,
303            };
304            levels_up = dots - 1;
305        } else if self.match_type(TokenType::Dot) {
306            relative = true;
307            levels_up = 0;
308        }
309
310        if self.match_type(TokenType::Identifier) {
311            segments.push(PathSegment::Identifier(self.previous().value.clone()));
312        } else if relative {
313            return Err(ParseError::new("Missing field name after dot prefix"));
314        }
315
316        while self.match_type(TokenType::Dot) {
317            if self.match_type(TokenType::Asterisk) {
318                segments.push(PathSegment::Wildcard);
319            } else if self.match_type(TokenType::Number) {
320                let idx = match &self.previous().literal {
321                    Literal::Int(n) => *n,
322                    Literal::Float(f) => *f as i64,
323                    _ => 0,
324                };
325                segments.push(PathSegment::Index(idx));
326            } else if self.match_type(TokenType::Identifier) {
327                segments.push(PathSegment::Identifier(self.previous().value.clone()));
328            } else {
329                return Err(ParseError::new(format!(
330                    "Invalid path segment after dot: {}",
331                    self.peek().value
332                )));
333            }
334        }
335
336        Ok(Node::Path {
337            relative,
338            levels_up,
339            segments,
340        })
341    }
342
343    /// Open a node whose children follow; the tree is at least one level deeper
344    /// than the open nodes.
345    fn enter(&mut self) -> Result<(), ParseError> {
346        self.open += 1;
347        if self.open >= MAX_EXPRESSION_DEPTH {
348            return Err(too_deep());
349        }
350        Ok(())
351    }
352
353    /// Record a node whose tallest child has `child_height` as the last parsed
354    /// node and return its height.
355    fn node(&mut self, child_height: usize) -> Result<usize, ParseError> {
356        self.height = child_height + 1;
357        if self.height > MAX_EXPRESSION_DEPTH {
358            return Err(too_deep());
359        }
360        Ok(self.height)
361    }
362
363    fn match_type(&mut self, t: TokenType) -> bool {
364        if self.check(t) {
365            self.advance();
366            return true;
367        }
368        false
369    }
370
371    fn match_any(&mut self, types: &[TokenType]) -> bool {
372        for &t in types {
373            if self.check(t) {
374                self.advance();
375                return true;
376            }
377        }
378        false
379    }
380
381    fn check(&self, t: TokenType) -> bool {
382        if self.is_at_end() {
383            return false;
384        }
385        self.peek().token_type == t
386    }
387
388    fn advance(&mut self) -> &Token {
389        if !self.is_at_end() {
390            self.current += 1;
391        }
392        self.previous()
393    }
394
395    fn is_at_end(&self) -> bool {
396        self.peek().token_type == TokenType::Eof
397    }
398
399    fn peek(&self) -> &Token {
400        &self.tokens[self.current]
401    }
402
403    fn previous(&self) -> &Token {
404        &self.tokens[self.current - 1]
405    }
406}
407
408fn too_deep() -> ParseError {
409    ParseError::new(format!(
410        "Expression is nested more than {MAX_EXPRESSION_DEPTH} levels deep"
411    ))
412}
413
414fn number_literal(lit: &Literal) -> LiteralValue {
415    match lit {
416        Literal::Int(n) => LiteralValue::Int(*n),
417        Literal::Float(f) => LiteralValue::Float(*f),
418        _ => LiteralValue::Int(0),
419    }
420}
421
422fn string_literal(lit: &Literal) -> String {
423    match lit {
424        Literal::Str(s) => s.clone(),
425        _ => String::new(),
426    }
427}
polyspec_crudui_validator/expr/parser.rs

polyspec_crudui_validator/expr/
parser.rs
