diff options
| author | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 13:54:48 +0200 |
|---|---|---|
| committer | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 13:54:48 +0200 |
| commit | 93fd7757dc4900da697b9d5e884e1a343e2facda (patch) | |
| tree | 91faf28e84d65269a0328e2e7f5934e253886af5 /src | |
| parent | 4710b5224f24992dabb2a2dd9230cac586f20ffd (diff) | |
| download | ele-93fd7757dc4900da697b9d5e884e1a343e2facda.tar.gz ele-93fd7757dc4900da697b9d5e884e1a343e2facda.zip | |
Bound filter parsing and reject excessive expression depth
Diffstat (limited to 'src')
| -rw-r--r-- | src/ast.rs | 30 | ||||
| -rw-r--r-- | src/lex.rs | 25 | ||||
| -rw-r--r-- | src/parser.rs | 110 |
3 files changed, 129 insertions, 36 deletions
@@ -104,3 +104,33 @@ pub enum Expr { args: Vec<Expr>, }, } + +impl Expr { + pub(crate) fn check_limits(&self) -> Result<(), String> { + let mut pending = vec![(self, 1)]; + let mut count = 0; + while let Some((expr, depth)) = pending.pop() { + count += 1; + if depth > 128 || count > 512 { + return Err("filter exceeds expression limit (128 levels, 512 nodes)".into()); + } + match expr { + Expr::Binary { left, right, .. } | Expr::Comparison { left, right, .. } => { + pending.push((left, depth + 1)); + pending.push((right, depth + 1)); + } + Expr::Unary { expr, .. } => pending.push((expr, depth + 1)), + Expr::Member { holder, .. } => pending.push((holder, depth + 1)), + Expr::Function { func, args } => { + if args.len() > 512 { + return Err("filter exceeds expression limit (512 nodes)".into()); + } + pending.push((func, depth + 1)); + pending.extend(args.iter().map(|arg| (arg, depth + 1))); + } + Expr::Name { .. } => {} + } + } + Ok(()) + } +} @@ -43,7 +43,6 @@ pub(crate) struct Token { pub(crate) struct Lexer { input: Vec<char>, cursor: usize, - pushed: Option<Token>, prev_dot: bool, prev_text: bool, next_pos: Position, @@ -54,7 +53,6 @@ impl Lexer { Lexer { input: input.chars().collect(), cursor: 0, - pushed: None, prev_dot: false, prev_text: false, next_pos: Position { line: 1, col: 0 }, @@ -62,10 +60,6 @@ impl Lexer { } pub fn next_token(&mut self) -> Token { - if let Some(tok) = self.pushed.take() { - return tok; - } - let pos = self.next_pos; let prev_dot = self.prev_dot; let prev_text = self.prev_text; @@ -198,11 +192,6 @@ impl Lexer { } } - pub fn push_token(&mut self, tok: Token) { - assert!(self.pushed.is_none(), "double push_token"); - self.pushed = Some(tok); - } - // Helpers. fn peek(&self) -> Option<char> { @@ -290,8 +279,7 @@ impl Lexer { } } - loop { - let Some(rn) = self.peek() else { break }; + while let Some(rn) = self.peek() { if rn == '\\' { self.advance(); if !self.text_esc(&mut sb) { @@ -462,7 +450,7 @@ fn is_white(r: char) -> bool { } fn is_digit(r: char) -> bool { - ('0'..='9').contains(&r) + r.is_ascii_digit() } fn is_octal_digit(r: char) -> bool { @@ -562,13 +550,4 @@ mod tests { assert_eq!(t.kind, TokenKind::Equals); } - #[test] - fn test_push_token() { - let mut lex = Lexer::new("a b"); - let t = lex.next_token(); - assert_eq!(t.val, "a"); - lex.push_token(t.clone()); - let t2 = lex.next_token(); - assert_eq!(t2.val, "a"); - } } diff --git a/src/parser.rs b/src/parser.rs index 7555a87..e0b95fa 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -1,12 +1,74 @@ use super::ast::{BinaryOp, CompareOp, Expr, Position, UnaryOp}; use super::lex::{Lexer, Token, TokenKind}; +pub const MAX_FILTER_BYTES: usize = 64 * 1024; +pub const MAX_FILTER_TOKENS: usize = 512; +const MAX_PARSE_DEPTH: usize = 64; + +struct Parser { + tokens: std::vec::IntoIter<Token>, + pushed: Option<Token>, + eof: Token, + depth: usize, +} + +impl Parser { + fn new(filter: &str) -> Result<Self, String> { + if filter.len() > MAX_FILTER_BYTES { + return Err(format!("filter exceeds {MAX_FILTER_BYTES} bytes")); + } + let mut lexer = Lexer::new(filter); + let mut tokens = Vec::new(); + let mut count = 0; + loop { + let token = lexer.next_token(); + if token.kind == TokenKind::Eof { + return Ok(Self { + tokens: tokens.into_iter(), + pushed: None, + eof: token, + depth: 0, + }); + } + if token.kind != TokenKind::Wsc { + count += 1; + if count > MAX_FILTER_TOKENS { + return Err(format!("{}: filter exceeds {MAX_FILTER_TOKENS} tokens", token.pos)); + } + } + tokens.push(token); + } + } + + fn next_token(&mut self) -> Token { + self.pushed + .take() + .or_else(|| self.tokens.next()) + .unwrap_or_else(|| self.eof.clone()) + } + + fn push_token(&mut self, token: Token) { + assert!(self.pushed.is_none(), "double push_token"); + self.pushed = Some(token); + } + + fn nested<T>(&mut self, parse: impl FnOnce(&mut Self) -> Result<T, String>) -> Result<T, String> { + if self.depth >= MAX_PARSE_DEPTH { + return Err(format!("filter exceeds parser nesting limit of {MAX_PARSE_DEPTH}")); + } + self.depth += 1; + let result = parse(self); + self.depth -= 1; + result + } +} + /// Parse a filter expression string into an [`Expr`]. /// /// Returns `Ok(None)` for empty input, `Ok(Some(expr))` on success, /// `Err(msg)` on parse error. pub fn parse_filter(filter: &str) -> Result<Option<Expr>, String> { - let mut lex = Lexer::new(filter); + let mut lex = Parser::new(filter)?; let mut tok = lex.next_token(); if tok.kind == TokenKind::Wsc { @@ -27,16 +89,17 @@ pub fn parse_filter(filter: &str) -> Result<Option<Expr>, String> { return Err(format!("{}: unexpected tokens after filter expression", tok.pos)); } + expr.check_limits()?; Ok(Some(expr)) } /// expression = sequence, { "AND", sequence } ; -fn parse_expression(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_expression(lex: &mut Parser) -> Result<Expr, String> { parse_junction(lex, TokenKind::And, parse_sequence) } /// sequence = factor, { factor } ; -fn parse_sequence(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_sequence(lex: &mut Parser) -> Result<Expr, String> { let mut factor = parse_factor(lex)?; loop { @@ -68,15 +131,15 @@ fn parse_sequence(lex: &mut Lexer) -> Result<Expr, String> { } /// factor = term, { "OR", term } ; -fn parse_factor(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_factor(lex: &mut Parser) -> Result<Expr, String> { parse_junction(lex, TokenKind::Or, parse_term) } /// Parse an AND or OR sequence. fn parse_junction( - lex: &mut Lexer, + lex: &mut Parser, kind: TokenKind, - parse_element: fn(&mut Lexer) -> Result<Expr, String>, + parse_element: fn(&mut Parser) -> Result<Expr, String>, ) -> Result<Expr, String> { let mut sub = parse_element(lex)?; @@ -117,7 +180,11 @@ fn parse_junction( } /// term = [ "-" | "NOT" ], primitive ; -fn parse_term(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_term(lex: &mut Parser) -> Result<Expr, String> { + lex.nested(parse_term_inner) +} + +fn parse_term_inner(lex: &mut Parser) -> Result<Expr, String> { let tok = lex.next_token(); let is_neg = tok.kind == TokenKind::Minus || tok.kind == TokenKind::Not; let neg_pos = tok.pos; @@ -160,7 +227,7 @@ fn parse_term(lex: &mut Lexer) -> Result<Expr, String> { } /// Parse a primitive (comparison, function call, parenthesized expr, or bare value). -fn parse_primitive(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_primitive(lex: &mut Parser) -> Result<Expr, String> { let mut tok = lex.next_token(); if tok.kind == TokenKind::Wsc { tok = lex.next_token(); @@ -254,7 +321,11 @@ fn func_pos(expr: &Expr) -> Position { } /// Parse a parenthesized expression. We have already consumed the `(`. -fn parse_parenthesized_expression(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_parenthesized_expression(lex: &mut Parser) -> Result<Expr, String> { + lex.nested(parse_parenthesized_inner) +} + +fn parse_parenthesized_inner(lex: &mut Parser) -> Result<Expr, String> { let tok = lex.next_token(); if tok.kind != TokenKind::Wsc { lex.push_token(tok); @@ -301,7 +372,7 @@ fn mark_composite(expr: &mut Expr) { } /// Parse a comparable (name, member, function). -fn parse_comparable(lex: &mut Lexer, tok: Token) -> Result<Expr, String> { +fn parse_comparable(lex: &mut Parser, tok: Token) -> Result<Expr, String> { let mut saw_white = false; let mut ntok = lex.next_token(); if ntok.kind == TokenKind::Wsc { @@ -361,7 +432,7 @@ fn parse_comparable(lex: &mut Lexer, tok: Token) -> Result<Expr, String> { } /// Parse member access: `identifier { "." identifier }`. -fn parse_member(lex: &mut Lexer, tok: &Token, pos: Position) -> Result<Expr, String> { +fn parse_member(lex: &mut Parser, tok: &Token, pos: Position) -> Result<Expr, String> { let mut ret: Expr = Expr::Name { name: tok.val.clone(), pos: tok.pos, @@ -395,7 +466,11 @@ fn parse_member(lex: &mut Lexer, tok: &Token, pos: Position) -> Result<Expr, Str } /// Parse a function call. We've consumed the `(`. -fn parse_function(lex: &mut Lexer, func: Expr) -> Result<Expr, String> { +fn parse_function(lex: &mut Parser, func: Expr) -> Result<Expr, String> { + lex.nested(|lex| parse_function_inner(lex, func)) +} + +fn parse_function_inner(lex: &mut Parser, func: Expr) -> Result<Expr, String> { let tok = lex.next_token(); if tok.kind == TokenKind::Rparen { return Ok(Expr::Function { @@ -435,7 +510,7 @@ fn parse_function(lex: &mut Lexer, func: Expr) -> Result<Expr, String> { } /// Parse an argument (comparable, value, or parenthesized expression). -fn parse_arg(lex: &mut Lexer) -> Result<Expr, String> { +fn parse_arg(lex: &mut Parser) -> Result<Expr, String> { let tok = lex.next_token(); if tok.kind == TokenKind::Lparen { return parse_parenthesized_expression(lex); @@ -463,6 +538,15 @@ mod tests { use super::*; #[test] + fn test_push_token() { + let mut parser = Parser::new("a b").unwrap(); + let token = parser.next_token(); + assert_eq!(token.val, "a"); + parser.push_token(token); + assert_eq!(parser.next_token().val, "a"); + } + + #[test] fn test_empty() { assert!(parse_filter("").unwrap().is_none()); assert!(parse_filter(" ").unwrap().is_none()); |
