diff options
| author | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 14:03:41 +0200 |
|---|---|---|
| committer | Onur Gündüz <ogunduz@gmail.com> | 2026-09-29 14:03:41 +0200 |
| commit | e3eb58307419a9f7314e061c393d579fd14b75ab (patch) | |
| tree | 8e232ec9ee70bd07ebe46bbc9fd86643cb411642 | |
| parent | 93fd7757dc4900da697b9d5e884e1a343e2facda (diff) | |
| download | ele-e3eb58307419a9f7314e061c393d579fd14b75ab.tar.gz ele-e3eb58307419a9f7314e061c393d579fd14b75ab.zip | |
Compile filters once and reject unsupported evaluation
| -rw-r--r-- | README.md | 13 | ||||
| -rw-r--r-- | src/compiled.rs | 271 | ||||
| -rw-r--r-- | src/eval.rs | 476 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/main.rs | 70 | ||||
| -rw-r--r-- | src/parser.rs | 2 | ||||
| -rw-r--r-- | tests/compiled_tests.rs | 147 |
7 files changed, 569 insertions, 412 deletions
@@ -28,7 +28,9 @@ usage: aip-filter [-p|--print] <expr> [file...] * An unquoted boolean field name evaluates that field. A dotted name resolves a field path first and otherwise becomes a global literal. Quote a search term to prevent field lookup, for example `'"active"'` or `'"example.com"'`. * String `=` and `!=` ignore ASCII case and support one leading or trailing `*`. The two operators are opposites. * String `:` matches words or phrases bounded by whitespace or ASCII punctuation, or a leading/trailing wildcard. Lists match any element; maps match keys. `field:*` tests for a non-default value, including a nonempty list or map. -* Functions are parsed but not evaluated. Regexes are validated when parsing and recompiled during evaluation. Filters are limited to 64 KiB, 512 non-whitespace tokens, 64 recursive parser calls, and an expression tree of at most 128 levels and 512 nodes. Excessive filters return errors instead of recursing without a bound. +* Functions can be parsed and printed, but evaluation rejects the entire filter if any function is present, including inside a negation or unused branch. +* The CLI compiles filters before reading records. Regexes, numeric literals, and field paths are reused across records. Filters can contain at most 32 regexes; each regex has a 1 MiB compiled-size limit and a 256 KiB DFA cache limit. +* Filters are limited to 64 KiB, 512 non-whitespace tokens, 64 recursive parser calls, and an expression tree of at most 128 levels and 512 nodes. Excessive filters return errors instead of recursing without a bound. ### Examples @@ -50,7 +52,9 @@ echo '{"user": {"settings": {"theme": "dark"}}}' | \ ## API -Implement `Filterable` for your type, then call `Expr::evaluate`: +Implement `Filterable` for your type, compile the expression once with `Expr::compile`, and reuse `CompiledFilter::evaluate`. Compilation returns errors for unsupported expressions before any records are read. `serde_json::Value` implements `Filterable` directly and borrows arrays and objects without copying them. + +`Expr::evaluate` is a convenience method for one record: it compiles on every call and returns false if compilation fails. Use `Expr::compile` when errors must be reported. Bare-literal matching also requires overriding `all_field_values` or `matches_global`; the default searches no values. Override `matches_global` to search borrowed data without building a list of values. `Value::matches_global` provides recursive matching for individual values. @@ -78,14 +82,15 @@ impl Filterable for Issue { fn main() { let expr = parse("state = \"open\"").unwrap().unwrap(); + let filter = expr.compile().unwrap(); let issue = Issue { state: "open".into(), priority: 1, labels: vec![] }; - if expr.evaluate(&issue) { + if filter.evaluate(&issue) { println!("got match"); } else { println!("no match"); } - assert!(expr.evaluate(&issue)); + assert!(filter.evaluate(&issue)); } ``` diff --git a/src/compiled.rs b/src/compiled.rs new file mode 100644 index 0000000..45c7dc3 --- /dev/null +++ b/src/compiled.rs @@ -0,0 +1,271 @@ +use crate::ast::{BinaryOp, CompareOp, Expr}; +use crate::eval::{Filterable, Literal, Value, eval_literal}; +use regex::{Regex, RegexBuilder}; +use std::borrow::Cow; + +/// A validated filter with reusable regexes, literals, and field paths. +/// +/// ``` +/// use aip_filter::parse; +/// use serde_json::json; +/// +/// let expr = parse(r#"state =~ "^op" AND priority < 6"#).unwrap().unwrap(); +/// let filter = expr.compile().unwrap(); +/// assert!(filter.evaluate(&json!({"state": "open", "priority": 5}))); +/// assert!(!filter.evaluate(&json!({"state": "closed", "priority": 5}))); +/// ``` +#[derive(Debug)] +pub struct CompiledFilter<'a> { + root: Node<'a>, +} + +#[derive(Debug)] +enum Node<'a> { + Binary(BinaryOp, Box<Node<'a>>, Box<Node<'a>>), + Not(Box<Node<'a>>), + Global { + text: Cow<'a, str>, + field: Option<Source<'a>>, + boolean_only: bool, + }, + Comparison(Source<'a>, Predicate<'a>), +} + +#[derive(Debug)] +enum Source<'a> { + Field(Vec<&'a str>), + String(&'a str), +} + +#[derive(Debug)] +enum Predicate<'a> { + Binary(BinaryOp, Box<Predicate<'a>>, Box<Predicate<'a>>), + Not(Box<Predicate<'a>>), + Literal(CompareOp, Literal<'a>), + Regex { regex: Regex, negated: bool }, +} + +impl Expr { + /// Validates the entire expression and prepares it for repeated evaluation. + /// Unsupported functions and invalid comparison operands return an error. + pub fn compile(&self) -> Result<CompiledFilter<'_>, String> { + self.check_limits()?; + Ok(CompiledFilter { + root: Node::compile(self, &mut 32)?, + }) + } +} + +impl CompiledFilter<'_> { + pub fn evaluate<T: Filterable>(&self, record: &T) -> bool { + self.root.evaluate(record) + } +} + +impl<'a> Node<'a> { + fn compile(expr: &'a Expr, regex_budget: &mut usize) -> Result<Self, String> { + Ok(match expr { + Expr::Binary { + op, left, right, .. + } => Self::Binary( + *op, + Box::new(Self::compile(left, regex_budget)?), + Box::new(Self::compile(right, regex_budget)?), + ), + Expr::Unary { expr, .. } => Self::Not(Box::new(Self::compile(expr, regex_budget)?)), + Expr::Comparison { + op, left, right, .. + } => Self::Comparison( + Source::compile(left)?, + Predicate::compile(*op, right, regex_budget)?, + ), + Expr::Name { + name, is_string, .. + } => Self::Global { + text: Cow::Borrowed(name), + field: (!is_string).then(|| Source::Field(vec![name])), + boolean_only: true, + }, + Expr::Member { .. } => Self::Global { + text: literal_text(expr)?, + field: Some(Source::compile(expr)?), + boolean_only: false, + }, + Expr::Function { .. } => { + return Err("function calls are not supported during evaluation".into()); + } + }) + } + + fn evaluate<T: Filterable>(&self, record: &T) -> bool { + match self { + Self::Binary(BinaryOp::And, left, right) => { + left.evaluate(record) && right.evaluate(record) + } + Self::Binary(BinaryOp::Or, left, right) => { + left.evaluate(record) || right.evaluate(record) + } + Self::Not(expr) => !expr.evaluate(record), + Self::Global { + text, + field, + boolean_only, + } => { + if let Some(value) = field.as_ref().and_then(|field| field.resolve(record)) { + if let Value::Bool(value) = value { + return value; + } + if !boolean_only { + return !value.is_zero(); + } + } + record.matches_global(text) + } + Self::Comparison(source, predicate) => source + .resolve(record) + .is_some_and(|value| predicate.evaluate(&value)), + } + } +} + +impl<'a> Source<'a> { + fn compile(expr: &'a Expr) -> Result<Self, String> { + match expr { + Expr::Name { + name, + is_string: true, + .. + } => Ok(Self::String(name)), + Expr::Name { name, .. } => Ok(Self::Field(vec![name])), + Expr::Member { .. } => Ok(Self::Field(field_path(expr)?)), + Expr::Function { .. } => { + Err("function calls are not supported during evaluation".into()) + } + _ => Err("left operand must be a field or string literal".into()), + } + } + + fn resolve<'s, T: Filterable>(&'s self, record: &'s T) -> Option<Value<'s>> { + let path = match self { + Self::String(text) => return Some(Value::String(text)), + Self::Field(path) => path, + }; + if path.len() == 1 { + return record.field(path[0]); + } + if let Some(value) = record.field_path(path) { + return Some(value); + } + let mut value = record.field(path[0])?; + for segment in &path[1..] { + value = match value { + Value::Map(entries) => { + entries + .into_iter() + .find(|(key, _)| key.eq_ignore_ascii_case(segment))? + .1 + } + Value::JsonObject(entries) => entries + .iter() + .find(|(key, _)| key.eq_ignore_ascii_case(segment)) + .map(|(_, value)| Value::from(value))?, + _ => return None, + }; + } + Some(value) + } +} + +impl<'a> Predicate<'a> { + fn compile(op: CompareOp, expr: &'a Expr, regex_budget: &mut usize) -> Result<Self, String> { + Ok(match expr { + Expr::Binary { + op: binary, + left, + right, + .. + } => Self::Binary( + *binary, + Box::new(Self::compile(op, left, regex_budget)?), + Box::new(Self::compile(op, right, regex_budget)?), + ), + Expr::Unary { expr, .. } => Self::Not(Box::new(Self::compile(op, expr, regex_budget)?)), + Expr::Function { .. } => { + return Err("function calls are not supported during evaluation".into()); + } + _ if matches!(op, CompareOp::MatchesRegexp | CompareOp::NotMatchesRegexp) => { + let Expr::Name { + name, + is_string: true, + .. + } = expr + else { + return Err("regular expression is not a quoted string".into()); + }; + *regex_budget = regex_budget + .checked_sub(1) + .ok_or("filter exceeds limit of 32 regular expressions")?; + Self::Regex { + regex: compile_regex(name) + .map_err(|error| format!("invalid regular expression: {error}"))?, + negated: op == CompareOp::NotMatchesRegexp, + } + } + _ => Self::Literal(op, Literal::new(literal_text(expr)?)), + }) + } + + fn evaluate(&self, value: &Value<'_>) -> bool { + match self { + Self::Binary(BinaryOp::And, left, right) => { + left.evaluate(value) && right.evaluate(value) + } + Self::Binary(BinaryOp::Or, left, right) => { + left.evaluate(value) || right.evaluate(value) + } + Self::Not(expr) => !expr.evaluate(value), + Self::Literal(op, literal) => eval_literal(*op, value, literal), + Self::Regex { regex, negated } => value + .as_str() + .is_some_and(|text| regex.is_match(text) != *negated), + } + } +} + +fn field_path(expr: &Expr) -> Result<Vec<&str>, String> { + let mut path = Vec::new(); + let mut current = expr; + loop { + match current { + Expr::Member { holder, member, .. } => { + path.push(member.as_str()); + current = holder; + } + Expr::Name { name, .. } => { + path.push(name.as_str()); + path.reverse(); + return Ok(path); + } + Expr::Function { .. } => { + return Err("function calls are not supported during evaluation".into()); + } + _ => return Err("invalid field path".into()), + } + } +} + +fn literal_text(expr: &Expr) -> Result<Cow<'_, str>, String> { + match expr { + Expr::Name { name, .. } => Ok(Cow::Borrowed(name)), + Expr::Member { .. } => Ok(Cow::Owned(field_path(expr)?.join("."))), + Expr::Function { .. } => Err("function calls are not supported during evaluation".into()), + _ => Err("right operand must be a literal or a combination of literals".into()), + } +} + +pub(crate) fn compile_regex(pattern: &str) -> Result<Regex, regex::Error> { + RegexBuilder::new(pattern) + .size_limit(1024 * 1024) + .dfa_size_limit(256 * 1024) + .build() +} diff --git a/src/eval.rs b/src/eval.rs index 24866b9..e338900 100644 --- a/src/eval.rs +++ b/src/eval.rs @@ -1,5 +1,5 @@ -use super::ast::{BinaryOp, CompareOp, Expr, UnaryOp}; -use regex::Regex; +use super::ast::{CompareOp, Expr}; +use serde_json::Value as Json; use std::{borrow::Cow, cmp::Ordering}; /// A runtime value used during filter evaluation. @@ -21,6 +21,10 @@ pub enum Value<'a> { List(Vec<Value<'a>>), /// A map of string keys to values. Map(Vec<(&'a str, Value<'a>)>), + /// Borrowed JSON array; its elements are converted only when inspected. + JsonArray(&'a [Json]), + /// Borrowed JSON object; its values are converted only when inspected. + JsonObject(&'a serde_json::Map<String, Json>), /// Absent value. Null, } @@ -51,27 +55,17 @@ impl<'a> Value<'a> { Value::StringOwned(s) => s.is_empty(), Value::List(v) => v.is_empty(), Value::Map(m) => m.is_empty(), + Value::JsonArray(items) => items.is_empty(), + Value::JsonObject(entries) => entries.is_empty(), Value::Null => true, } } - /// Try to compare two values, returning an ordering if possible. - fn compare(&self, other: &Value<'_>) -> Option<Ordering> { + fn compare_number(&self, other: &Value<'_>) -> Option<Ordering> { match (self, other) { - (Value::Bool(a), Value::Bool(b)) => Some(a.cmp(b)), (Value::Int(a), Value::Int(b)) => Some(a.cmp(b)), (Value::Uint(a), Value::Uint(b)) => Some(a.cmp(b)), (Value::Float(a), Value::Float(b)) => a.partial_cmp(b), - (Value::String(a), Value::String(b)) => Some(a.to_lowercase().cmp(&b.to_lowercase())), - (Value::StringOwned(a), Value::String(b)) => { - Some(a.to_lowercase().cmp(&b.to_lowercase())) - } - (Value::String(a), Value::StringOwned(b)) => { - Some(a.to_lowercase().cmp(&b.to_lowercase())) - } - (Value::StringOwned(a), Value::StringOwned(b)) => { - Some(a.to_lowercase().cmp(&b.to_lowercase())) - } // Cross-numeric comparisons (Value::Int(a), Value::Float(b)) => compare_integer_float(i128::from(*a), *b), (Value::Float(a), Value::Int(b)) => { @@ -179,341 +173,153 @@ pub trait Filterable { } } -impl Expr { - /// Evaluate this expression against a filterable value. - /// - /// Returns `true` if the value matches the filter. - pub fn evaluate<T: Filterable>(&self, val: &T) -> bool { - match self { - Expr::Binary { op, left, right, .. } => match op { - BinaryOp::And => left.evaluate(val) && right.evaluate(val), - BinaryOp::Or => left.evaluate(val) || right.evaluate(val), - }, - - Expr::Unary { op, expr, .. } => { - let result = expr.evaluate(val); - match op { - UnaryOp::Minus | UnaryOp::Not => !result, - } - } - - Expr::Comparison { - op, left, right, .. - } => eval_comparison(*op, left, right, val), - - Expr::Name { - name, is_string, .. - } => { - if !*is_string && let Some(Value::Bool(b)) = val.field(name) { - return b; - } - val.matches_global(name) - } - - Expr::Member { - holder, member, .. - } => { - // Member as a standalone expression; expect boolean - if let Some(val) = resolve_member_value(holder, member, val) { - match val { - Value::Bool(b) => b, - _ => !val.is_zero(), - } +impl<'a> From<&'a Json> for Value<'a> { + fn from(value: &'a Json) -> Self { + match value { + Json::Null => Self::Null, + Json::Bool(value) => Self::Bool(*value), + Json::String(value) => Self::String(value), + Json::Number(value) => { + if let Some(value) = value.as_i64() { + Self::Int(value) + } else if let Some(value) = value.as_u64() { + Self::Uint(value) } else { - expr_to_literal_str(self).is_some_and(|literal| val.matches_global(&literal)) + Self::Float(value.as_f64().unwrap()) } } - - Expr::Function { .. } => { - // Function evaluation is not yet supported - false - } + Json::Array(values) => Self::JsonArray(values), + Json::Object(values) => Self::JsonObject(values), } } } -/// Evaluate a comparison expression. -fn eval_comparison<T: Filterable>( - op: CompareOp, - left: &Expr, - right: &Expr, - val: &T, -) -> bool { - // Resolve the left side to a Value - let left_val = resolve_expr_value(left, val); - - let Some(left_val) = left_val else { - return false; - }; - - eval_comparison_with_value(op, &left_val, right) -} - -fn eval_comparison_with_value( - op: CompareOp, - left_val: &Value<'_>, - right: &Expr, -) -> bool { - // Handle the right side, it could be a composite expression (AND/OR) - match right { - Expr::Binary { - op: bin_op, - left: rleft, - right: rright, - .. - } => match bin_op { - BinaryOp::And => { - eval_comparison_with_value(op, left_val, rleft) - && eval_comparison_with_value(op, left_val, rright) - } - BinaryOp::Or => { - eval_comparison_with_value(op, left_val, rleft) - || eval_comparison_with_value(op, left_val, rright) - } - }, - Expr::Unary { - op: UnaryOp::Minus | UnaryOp::Not, - expr, - .. - } => !eval_comparison_with_value(op, left_val, expr), - - _ => { - let right_str = expr_to_literal_str(right); - let right_str = right_str.as_deref(); - if op == CompareOp::Has && right_str == Some("*") { - return !left_val.is_zero(); - } - - match (&left_val, op) { - // Has operator on lists - (Value::List(items), CompareOp::Has) => { - if let Some(rs) = right_str { - items.iter().any(|item| value_matches_str(item, rs, op)) - } else { - false - } - } - - // Has operator on maps; check if key exists - (Value::Map(entries), CompareOp::Has) => { - if let Some(rs) = right_str { - entries.iter().any(|(k, _)| k.eq_ignore_ascii_case(rs)) - } else { - false - } - } - - // Equals/NotEquals on lists; check if any element matches - (Value::List(items), CompareOp::Equals) => { - if let Some(rs) = right_str { - items.iter().any(|item| value_matches_str(item, rs, op)) - } else { - false - } - } - (Value::List(items), CompareOp::NotEquals) => { - if let Some(rs) = right_str { - !items.iter().any(|item| value_matches_str(item, rs, CompareOp::Equals)) - } else { - true - } - } - - // Has on strings; substring/word boundary match - (_, CompareOp::Has) => { - if let Some(rs) = right_str { - value_matches_str(left_val, rs, op) - } else { - false - } - } - - // Regex match - (_, CompareOp::MatchesRegexp | CompareOp::NotMatchesRegexp) => { - let Some(left_s) = left_val.as_str() else { - return false; - }; - let Some(rs) = right_str else { - return false; - }; - let Ok(re) = Regex::new(rs) else { - return false; - }; - let matched = re.is_match(left_s); - if op == CompareOp::NotMatchesRegexp { - !matched - } else { - matched - } - } +impl Filterable for Json { + fn field(&self, name: &str) -> Option<Value<'_>> { + self.get(name).map(Value::from) + } - // Standard comparison - _ => { - if let Some(rs) = right_str { - let right_val = parse_literal_for_value(left_val, rs); - compare_values(op, left_val, &right_val) - } else { - false - } - } - } + fn field_path(&self, path: &[&str]) -> Option<Value<'_>> { + let mut current = self; + for segment in path { + current = current.get(*segment)?; } + Some(Value::from(current)) } -} -/// Resolve an expression to its value given a filterable object. -fn resolve_expr_value<'a, T: Filterable>(expr: &'a Expr, val: &'a T) -> Option<Value<'a>> { - match expr { - Expr::Name { - name, is_string, .. - } => { - if *is_string { - // A quoted string on the left side of a comparison is just a string literal - Some(Value::String(name)) - } else { - val.field(name) - } + fn all_field_values(&self) -> Vec<Value<'_>> { + match self { + Json::Object(values) => values.values().map(Value::from).collect(), + _ => vec![Value::from(self)], } - Expr::Member { - holder, member, .. - } => resolve_member_value(holder, member, val), - _ => None, } -} -/// Resolve a member expression (e.g., `a.b.c`) to a value. -fn resolve_member_value<'a, T: Filterable>( - holder: &Expr, - member: &str, - val: &'a T, -) -> Option<Value<'a>> { - // Collect the path segments - let mut path = vec![member]; - let mut cur = holder; - loop { - match cur { - Expr::Member { - holder, - member, - .. - } => { - path.push(member.as_str()); - cur = holder; - } - Expr::Name { name, .. } => { - path.push(name.as_str()); - break; - } - _ => return None, - } + fn matches_global(&self, search: &str) -> bool { + Value::from(self).matches_global(search) } - path.reverse(); +} - // Try field_path first - if let Some(v) = val.field_path(&path) { - return Some(v); +impl Expr { + /// Evaluates once, returning false if compilation fails, including under negation. + /// Use `compile()` to report errors and reuse the filter across records. + pub fn evaluate<T: Filterable>(&self, value: &T) -> bool { + self.compile().is_ok_and(|filter| filter.evaluate(value)) } +} - // Fall back to walking field by field (for nested Filterable values) - // First field - let first_val = val.field(path[0])?; +#[derive(Debug)] +pub(crate) struct Literal<'a> { + text: Cow<'a, str>, + folded: Option<String>, + number: Option<Value<'static>>, + boolean: Option<bool>, +} - // Walk remaining path through map keys - let mut current = first_val; - for &segment in &path[1..] { - current = match current { - Value::Map(entries) => { - let found = entries - .into_iter() - .find(|(k, _)| k.eq_ignore_ascii_case(segment)); - match found { - Some((_, v)) => v, - None => return None, - } - } - _ => return None, +impl<'a> Literal<'a> { + pub(crate) fn new(text: Cow<'a, str>) -> Self { + let number = if let Ok(value) = text.parse::<i64>() { + Some(Value::Int(value)) + } else if let Ok(value) = text.parse::<u64>() { + Some(Value::Uint(value)) + } else { + text.parse::<f64>().ok().map(Value::Float) + }; + let boolean = if text.eq_ignore_ascii_case("true") || text == "1" { + Some(true) + } else if text.eq_ignore_ascii_case("false") || text == "0" { + Some(false) + } else { + None + }; + let folded = match lowercase(&text) { + Cow::Borrowed(_) => None, + Cow::Owned(text) => Some(text), }; + Self { text, folded, number, boolean } } - Some(current) -} -/// Extract the literal string from an expression (name or member chain as dotted string). -fn expr_to_literal_str(expr: &Expr) -> Option<Cow<'_, str>> { - match expr { - Expr::Name { name, .. } => Some(Cow::Borrowed(name)), - Expr::Member { holder, member, .. } => { - // a.b on the right side is just "a.b" as a string - let mut parts = vec![member.as_str()]; - let mut cur = holder.as_ref(); - loop { - match cur { - Expr::Member { holder, member, .. } => { - parts.push(member.as_str()); - cur = holder.as_ref(); - } - Expr::Name { name, .. } => { - parts.push(name.as_str()); - break; - } - _ => return None, - } - } - parts.reverse(); - Some(Cow::Owned(parts.join("."))) - } - Expr::Function { .. } => None, - _ => None, + fn folded(&self) -> &str { + self.folded.as_deref().unwrap_or(&self.text) } } -/// Parse a literal string to match the type of a reference value. -fn parse_literal_for_value<'a>(reference: &Value<'_>, literal: &'a str) -> Value<'a> { - match reference { - Value::Bool(_) => { - if literal.eq_ignore_ascii_case("true") || literal == "1" { - Value::Bool(true) - } else if literal.eq_ignore_ascii_case("false") || literal == "0" { - Value::Bool(false) - } else { - Value::String(literal) - } +pub(crate) fn eval_literal(op: CompareOp, value: &Value<'_>, literal: &Literal<'_>) -> bool { + if op == CompareOp::Has && literal.text == "*" { + return !value.is_zero(); + } + if matches!(op, CompareOp::Equals | CompareOp::NotEquals | CompareOp::Has) { + let element_op = if op == CompareOp::NotEquals { CompareOp::Equals } else { op }; + let found = match value { + Value::List(items) => Some(items.iter().any(|item| value_matches_literal(item, literal, element_op))), + Value::JsonArray(items) => Some(items.iter().any(|item| value_matches_literal(&Value::from(item), literal, element_op))), + _ => None, + }; + if let Some(found) = found { + return found != (op == CompareOp::NotEquals); } - Value::Int(_) | Value::Uint(_) | Value::Float(_) => { - if let Ok(i) = literal.parse::<i64>() { - Value::Int(i) - } else if let Ok(u) = literal.parse::<u64>() { - Value::Uint(u) - } else if let Ok(f) = literal.parse::<f64>() { - Value::Float(f) - } else { - Value::String(literal) - } + } + if op == CompareOp::Has { + match value { + Value::Map(entries) => return entries.iter().any(|(key, _)| key.eq_ignore_ascii_case(&literal.text)), + Value::JsonObject(entries) => return entries.keys().any(|key| key.eq_ignore_ascii_case(&literal.text)), + _ => {} } - Value::String(_) | Value::StringOwned(_) => Value::String(literal), - _ => Value::String(literal), } + compare_literal(op, value, literal) } -/// Check if a value matches a string using the given comparison op. -fn value_matches_str(val: &Value<'_>, s: &str, op: CompareOp) -> bool { - match val { - Value::String(vs) => string_match(vs, s, op), - Value::StringOwned(vs) => string_match(vs.as_str(), s, op), - Value::Int(_) | Value::Uint(_) | Value::Float(_) | Value::Bool(_) => { - compare_values(op, val, &parse_literal_for_value(val, s)) - } - Value::List(items) => items.iter().any(|item| value_matches_str(item, s, op)), - Value::Map(entries) => entries.iter().any(|(_, v)| value_matches_str(v, s, op)), - Value::Null => false, +fn value_matches_literal(value: &Value<'_>, literal: &Literal<'_>, op: CompareOp) -> bool { + match value { + Value::List(items) => items.iter().any(|item| value_matches_literal(item, literal, op)), + Value::Map(entries) => entries.iter().any(|(_, value)| value_matches_literal(value, literal, op)), + Value::JsonArray(items) => items.iter().any(|value| value_matches_literal(&Value::from(value), literal, op)), + Value::JsonObject(entries) => entries.values().any(|value| value_matches_literal(&Value::from(value), literal, op)), + _ => compare_literal(op, value, literal), + } +} + +fn compare_literal(op: CompareOp, value: &Value<'_>, literal: &Literal<'_>) -> bool { + if let Some(text) = value.as_str() { + return string_match(text, literal, op); } + let order = match value { + Value::Bool(value) => literal.boolean.map(|right| value.cmp(&right)), + Value::Int(_) | Value::Uint(_) | Value::Float(_) => literal + .number + .as_ref() + .and_then(|right| value.compare_number(right)), + _ => None, + }; + compare_order(op, order) } /// Equality and `:` support a leading or trailing wildcard. /// Word boundaries for `:` are whitespace or ASCII punctuation. -fn string_match(haystack: &str, needle: &str, op: CompareOp) -> bool { +fn string_match(haystack: &str, literal: &Literal<'_>, op: CompareOp) -> bool { if op == CompareOp::NotEquals { - return !string_match(haystack, needle, CompareOp::Equals); + return !string_match(haystack, literal, CompareOp::Equals); } + let needle = literal.text.as_ref(); if matches!(op, CompareOp::Equals | CompareOp::Has) { if let Some(suffix) = needle.strip_prefix('*') { return haystack.len() @@ -530,7 +336,7 @@ fn string_match(haystack: &str, needle: &str, op: CompareOp) -> bool { CompareOp::Equals => haystack.eq_ignore_ascii_case(needle), CompareOp::Has => { let haystack = lowercase(haystack); - let needle = lowercase(needle); + let needle = literal.folded(); if needle.is_empty() { return true; } @@ -538,7 +344,7 @@ fn string_match(haystack: &str, needle: &str, op: CompareOp) -> bool { c.is_whitespace() || (c.is_ascii() && !c.is_ascii_alphanumeric()) }; let mut offset = 0; - while let Some(index) = haystack[offset..].find(needle.as_ref()) { + while let Some(index) = haystack[offset..].find(needle) { let start = offset + index; let end = start + needle.len(); if haystack[..start].chars().next_back().is_none_or(boundary) @@ -550,7 +356,7 @@ fn string_match(haystack: &str, needle: &str, op: CompareOp) -> bool { } false } - _ => compare_values(op, &Value::String(haystack), &Value::String(needle)), + _ => compare_order(op, Some(lowercase(haystack).as_ref().cmp(literal.folded()))), } } @@ -580,39 +386,21 @@ fn value_contains_str(val: &Value<'_>, search: &str) -> bool { } Value::List(items) => items.iter().any(|item| value_contains_str(item, search)), Value::Map(entries) => entries.iter().any(|(_, v)| value_contains_str(v, search)), + Value::JsonArray(items) => items.iter().any(|value| Value::from(value).matches_global(search)), + Value::JsonObject(entries) => entries.values().any(|value| Value::from(value).matches_global(search)), Value::Null => false, } } -/// Compare two values using a comparison operator. -fn compare_values(op: CompareOp, left: &Value<'_>, right: &Value<'_>) -> bool { +fn compare_order(op: CompareOp, order: Option<Ordering>) -> bool { match op { - CompareOp::Equals | CompareOp::Has => { - if let (Some(ls), Some(rs)) = (left.as_str(), right.as_str()) { - return string_match(ls, rs, op); - } - left.compare(right) == Some(Ordering::Equal) - } - CompareOp::NotEquals => { - if let (Some(ls), Some(rs)) = (left.as_str(), right.as_str()) { - return string_match(ls, rs, CompareOp::NotEquals); - } - left.compare(right) != Some(Ordering::Equal) - } - CompareOp::LessThan => left.compare(right) == Some(Ordering::Less), - CompareOp::LessThanEquals => matches!( - left.compare(right), - Some(Ordering::Less) | Some(Ordering::Equal) - ), - CompareOp::GreaterThan => left.compare(right) == Some(Ordering::Greater), - CompareOp::GreaterThanEquals => matches!( - left.compare(right), - Some(Ordering::Greater) | Some(Ordering::Equal) - ), - CompareOp::MatchesRegexp | CompareOp::NotMatchesRegexp => { - // Handled at a higher level - false - } + CompareOp::Equals | CompareOp::Has => order == Some(Ordering::Equal), + CompareOp::NotEquals => order != Some(Ordering::Equal), + CompareOp::LessThan => order == Some(Ordering::Less), + CompareOp::LessThanEquals => matches!(order, Some(Ordering::Less | Ordering::Equal)), + CompareOp::GreaterThan => order == Some(Ordering::Greater), + CompareOp::GreaterThanEquals => matches!(order, Some(Ordering::Greater | Ordering::Equal)), + CompareOp::MatchesRegexp | CompareOp::NotMatchesRegexp => false, } } @@ -41,12 +41,14 @@ //! ``` pub mod ast; +mod compiled; pub mod display; pub mod eval; pub mod lex; pub mod parser; pub use ast::{BinaryOp, CompareOp, Expr, Position, UnaryOp}; +pub use compiled::CompiledFilter; pub use eval::{Filterable, Value}; /// Parse a filter expression string into an [`Expr`] AST. diff --git a/src/main.rs b/src/main.rs index e8b58b0..afeaf39 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,4 +1,4 @@ -use aip_filter::{parse, Expr, Filterable, Value}; +use aip_filter::{parse, CompiledFilter}; use serde_json::Value as Json; use std::{ fs::File, @@ -7,66 +7,8 @@ use std::{ process, }; -struct JsonRecord<'j>(&'j Json); - -impl<'j> Filterable for JsonRecord<'j> { - fn field(&self, name: &str) -> Option<Value<'_>> { - json_to_value(self.0.get(name)?) - } - - fn field_path(&self, path: &[&str]) -> Option<Value<'_>> { - let mut cur = self.0; - for &segment in path { - cur = cur.get(segment)?; - } - json_to_value(cur) - } - - fn all_field_values(&self) -> Vec<Value<'_>> { - match self.0 { - Json::Object(map) => map.values().filter_map(json_to_value).collect(), - _ => json_to_value(self.0).into_iter().collect(), - } - } - - fn matches_global(&self, search: &str) -> bool { - match self.0 { - Json::Object(map) => map - .values() - .any(|value| JsonRecord(value).matches_global(search)), - Json::Array(items) => items - .iter() - .any(|value| JsonRecord(value).matches_global(search)), - _ => json_to_value(self.0).is_some_and(|value| value.matches_global(search)), - } - } -} - -fn json_to_value(v: &Json) -> Option<Value<'_>> { - match v { - Json::String(s) => Some(Value::String(s.as_str())), - Json::Bool(b) => Some(Value::Bool(*b)), - Json::Null => Some(Value::Null), - Json::Number(n) => { - if let Some(i) = n.as_i64() { return Some(Value::Int(i)); } - if let Some(u) = n.as_u64() { return Some(Value::Uint(u)); } - n.as_f64().map(Value::Float) - } - Json::Array(arr) => Some(Value::List( - arr.iter().filter_map(json_to_value).collect(), - )), - Json::Object(map) => Some(Value::Map( - map.iter() - .filter_map(|(key, value)| { - json_to_value(value).map(|value| (key.as_str(), value)) - }) - .collect(), - )), - } -} - fn filter_lines( - expr: Option<&Expr>, + expr: Option<&CompiledFilter<'_>>, mut reader: impl BufRead, out: &mut impl Write, source: &str, @@ -86,7 +28,7 @@ fn filter_lines( if !line_buffer.trim().is_empty() { match serde_json::from_str::<Json>(&line_buffer) { Ok(json) => { - if expr.evaluate(&JsonRecord(&json)) { + if expr.evaluate(&json) { // Write directly to stdout out.write_all(line_buffer.as_bytes())?; } @@ -144,14 +86,16 @@ fn main() { } return Ok(true); } + let filter = expr.as_ref().map(|expr| expr.compile()).transpose() + .map_err(|error| io::Error::new(io::ErrorKind::InvalidInput, error))?; if args.is_empty() { - return filter_lines(expr.as_ref(), io::stdin().lock(), &mut out, "<stdin>"); + return filter_lines(filter.as_ref(), io::stdin().lock(), &mut out, "<stdin>"); } let mut valid = true; for path in &args { let file = File::open(Path::new(path)) .map_err(|e| io::Error::new(e.kind(), format!("{path}: {e}")))?; - valid &= filter_lines(expr.as_ref(), BufReader::new(file), &mut out, path) + valid &= filter_lines(filter.as_ref(), BufReader::new(file), &mut out, path) .map_err(|e| io::Error::new(e.kind(), format!("{path}: {e}")))?; } Ok(valid) diff --git a/src/parser.rs b/src/parser.rs index e0b95fa..d979334 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -297,7 +297,7 @@ fn validate_regex(expr: &Expr) -> Result<(), String> { return Err(format!("{}: regular expression is not a quoted string", pos)); } // Validate the regex syntax - if let Err(e) = regex::Regex::new(name) { + if let Err(e) = crate::compiled::compile_regex(name) { return Err(format!("{}: invalid regular expression: {}", pos, e)); } Ok(()) diff --git a/tests/compiled_tests.rs b/tests/compiled_tests.rs new file mode 100644 index 0000000..c591fbc --- /dev/null +++ b/tests/compiled_tests.rs @@ -0,0 +1,147 @@ +use aip_filter::{Expr, Filterable, Value, parse}; +use serde_json::json; +use std::process::{Command, Stdio}; + +#[test] +fn unsupported_functions_reject_the_entire_filter() { + let record = json!({"active": true, "value": "open"}); + for input in [ + "fn(x)", + "NOT fn(x)", + "active OR fn(x)", + "-fn(x)", + "fn(x) = open", + "value = fn(x)", + "value:(open OR fn(x))", + ] { + let expr = parse(input).unwrap().unwrap(); + assert!( + expr.compile() + .unwrap_err() + .contains("function calls are not supported") + ); + assert!(!expr.evaluate(&record), "{input}"); + let output = Command::new(env!("CARGO_BIN_EXE_aip-filter")) + .arg(input) + .stdin(Stdio::null()) + .output() + .unwrap(); + assert_eq!(output.status.code(), Some(1), "{input}"); + assert!(output.stdout.is_empty()); + assert!( + String::from_utf8_lossy(&output.stderr).contains("function calls are not supported") + ); + } + let output = Command::new(env!("CARGO_BIN_EXE_aip-filter")) + .args(["--print", "fn(x)"]) + .output() + .unwrap(); + assert!(output.status.success()); + assert!(String::from_utf8_lossy(&output.stdout).contains("call")); +} + +#[test] +fn compiled_filters_are_reusable_with_different_record_types() { + let expr = parse(r#"state =~ ("^op" OR "^cl") AND priority < 5.9"#) + .unwrap() + .unwrap(); + let filter = expr.compile().unwrap(); + for _ in 0..100 { + assert!(filter.evaluate(&json!({"state":"open", "priority":5}))); + assert!(filter.evaluate(&json!({"state":"closed", "priority":1}))); + assert!(!filter.evaluate(&json!({"state":"shut", "priority":1}))); + assert!(!filter.evaluate(&json!({"state":"open", "priority":6}))); + assert!(!filter.evaluate(&json!({"priority":1}))); + } + + struct Record; + impl Filterable for Record { + fn field(&self, name: &str) -> Option<Value<'_>> { + match name { + "state" => Some(Value::String("closed")), + "priority" => Some(Value::Int(5)), + _ => None, + } + } + } + assert!(filter.evaluate(&Record)); +} + +#[test] +fn borrowed_and_owned_collections_have_identical_semantics() { + struct Record<'a>(Value<'a>); + impl Filterable for Record<'_> { + fn field(&self, name: &str) -> Option<Value<'_>> { + (name == "value").then(|| self.0.clone()) + } + } + let array = json!(["open", 5, false, {"key": "nested"}]); + let owned = Value::List(vec![ + Value::StringOwned("open".into()), + Value::Int(5), + Value::Bool(false), + Value::Map(vec![("key", Value::String("nested"))]), + ]); + assert!(matches!(Value::from(&array), Value::JsonArray(_))); + for input in [ + "value:*", + "value:open", + "value:5.0", + "value:false", + "value:garbage", + "value:nested", + "value = open", + "value != open", + "value != absent", + ] { + let expr = parse(input).unwrap().unwrap(); + let filter = expr.compile().unwrap(); + assert_eq!( + filter.evaluate(&Record(Value::from(&array))), + filter.evaluate(&Record(owned.clone())), + "{input}" + ); + } + let object = json!({"key":"nested"}); + assert!(matches!(Value::from(&object), Value::JsonObject(_))); + for input in ["value:key", "value:nested", "value:*", "value.KEY=nested"] { + let expr = parse(input).unwrap().unwrap(); + let filter = expr.compile().unwrap(); + assert_eq!( + filter.evaluate(&Record(Value::from(&object))), + filter.evaluate(&Record(Value::Map(vec![("key", Value::String("nested"))]))), + "{input}" + ); + } +} + +#[test] +fn regex_resources_and_manual_trees_are_bounded() { + let input = std::iter::repeat_n(r#"value =~ "x""#, 33) + .collect::<Vec<_>>() + .join(" OR "); + let expr = parse(&input).unwrap().unwrap(); + assert!( + expr.compile() + .unwrap_err() + .contains("32 regular expressions") + ); + assert!(parse(r#"value =~ "a{1000000}""#).is_err()); + + let mut expr = parse("value").unwrap().unwrap(); + for _ in 0..150 { + expr = Expr::Unary { + op: aip_filter::UnaryOp::Not, + expr: Box::new(expr), + pos: aip_filter::Position { line: 1, col: 1 }, + }; + } + assert!(expr.compile().unwrap_err().contains("expression limit")); +} + +#[test] +fn invalid_comparison_operands_report_errors() { + let expr = parse("value:(other=1)").unwrap().unwrap(); + assert!(expr.compile().is_err()); + assert!(!expr.evaluate(&json!({"value":"other"}))); +} |
