aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ast.rs30
-rw-r--r--src/lex.rs25
-rw-r--r--src/parser.rs110
3 files changed, 129 insertions, 36 deletions
diff --git a/src/ast.rs b/src/ast.rs
index 54128d8..7612c35 100644
--- a/src/ast.rs
+++ b/src/ast.rs
@@ -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(())
+ }
+}
diff --git a/src/lex.rs b/src/lex.rs
index 284fd75..883e7c7 100644
--- a/src/lex.rs
+++ b/src/lex.rs
@@ -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());