diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ast.rs | 106 | ||||
| -rw-r--r-- | src/display.rs | 126 | ||||
| -rw-r--r-- | src/eval.rs | 920 | ||||
| -rw-r--r-- | src/lex.rs | 574 | ||||
| -rw-r--r-- | src/lib.rs | 59 | ||||
| -rw-r--r-- | src/main.rs | 155 | ||||
| -rw-r--r-- | src/parser.rs | 546 |
7 files changed, 2486 insertions, 0 deletions
diff --git a/src/ast.rs b/src/ast.rs new file mode 100644 index 0000000..54128d8 --- /dev/null +++ b/src/ast.rs @@ -0,0 +1,106 @@ +/// Position in the filter string (line and column, 1-indexed). +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct Position { + pub line: usize, + pub col: usize, +} + +impl std::fmt::Display for Position { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}:{}", self.line, self.col) + } +} + +/// Binary operators: AND / OR. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum BinaryOp { + And, + Or, +} + +/// Unary operators: negation. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum UnaryOp { + Minus, + Not, +} + +/// Comparison operators. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub enum CompareOp { + Equals, + NotEquals, + LessThan, + LessThanEquals, + GreaterThan, + GreaterThanEquals, + Has, + MatchesRegexp, + NotMatchesRegexp, +} + +impl CompareOp { + pub fn as_str(&self) -> &'static str { + match self { + CompareOp::Equals => "=", + CompareOp::NotEquals => "!=", + CompareOp::LessThan => "<", + CompareOp::LessThanEquals => "<=", + CompareOp::GreaterThan => ">", + CompareOp::GreaterThanEquals => ">=", + CompareOp::Has => ":", + CompareOp::MatchesRegexp => "=~", + CompareOp::NotMatchesRegexp => "!~", + } + } +} + +/// The AST of a parsed AIP-160 filter expression. +#[derive(Debug, Clone, PartialEq)] +pub enum Expr { + /// Binary expression: `left AND right` or `left OR right`. + Binary { + op: BinaryOp, + left: Box<Expr>, + right: Box<Expr>, + pos: Position, + }, + + /// Unary expression: `-expr` or `NOT expr`. + Unary { + op: UnaryOp, + expr: Box<Expr>, + pos: Position, + }, + + /// Comparison expression: `left op right`. + Comparison { + op: CompareOp, + left: Box<Expr>, + right: Box<Expr>, + pos: Position, + }, + + /// A simple name or literal value. + Name { + name: String, + pos: Position, + /// `true` if this was a quoted string literal. + is_string: bool, + /// `true` if inside a parenthesized (composite) expression. + is_composite: bool, + }, + + /// A member access expression: `holder.member`. + Member { + holder: Box<Expr>, + member: String, + pos: Position, + }, + + /// A function call expression: `fn(args...)`. + Function { + func: Box<Expr>, + args: Vec<Expr>, + }, +} diff --git a/src/display.rs b/src/display.rs new file mode 100644 index 0000000..f89f284 --- /dev/null +++ b/src/display.rs @@ -0,0 +1,126 @@ +use super::ast::{BinaryOp, Expr, UnaryOp}; +use std::fmt; + +impl fmt::Display for Expr { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.print(f, 0) + } +} + +impl Expr { + fn print(&self, f: &mut fmt::Formatter<'_>, indent: usize) -> fmt::Result { + match self { + Expr::Binary { op, left, right, .. } => { + let label = match op { + BinaryOp::And => "conjunction", + BinaryOp::Or => "disjunction", + }; + writeln!(f, "{:indent$}{}", "", label, indent = indent)?; + left.print(f, indent + 2)?; + right.print(f, indent + 2) + } + + Expr::Unary { op, expr, .. } => { + let label = match op { + UnaryOp::Minus => "minus", + UnaryOp::Not => "not", + }; + writeln!(f, "{:indent$}{}", "", label, indent = indent)?; + expr.print(f, indent + 2) + } + + Expr::Comparison { op, left, right, .. } => { + writeln!(f, "{:indent$}compare {}", "", op.as_str(), indent = indent)?; + left.print(f, indent + 2)?; + right.print(f, indent + 2) + } + + Expr::Name { name, is_string, .. } => { + if *is_string { + writeln!(f, "{:indent$}{:?}", "", name, indent = indent) + } else { + writeln!(f, "{:indent$}{}", "", name, indent = indent) + } + } + + Expr::Member { holder, member, .. } => { + // Walk the member chain to collect all name segments. + 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; + } + _ => break, + } + } + parts.reverse(); + write!(f, "{:indent$}", "", indent = indent)?; + for (i, part) in parts.iter().enumerate() { + if i > 0 { + write!(f, ".")?; + } + write!(f, "{}", part)?; + } + writeln!(f) + } + + Expr::Function { func, args } => { + // "call" runs directly into the function name (no newline between them). + // The function name is indented at indent+2, which produces the + // two-space gap: "call funcname\n". + write!(f, "{:indent$}call", "", indent = indent)?; + func.print(f, indent + 2)?; + for arg in args { + arg.print(f, indent + 2)?; + } + Ok(()) + } + } + } +} + +#[cfg(test)] +mod tests { + use crate::parse; + + #[test] + fn test_display_comparison() { + let expr = parse("x = 42").unwrap().unwrap(); + assert_eq!(format!("{expr}"), "compare =\n x\n 42\n"); + } + + #[test] + fn test_display_conjunction() { + let expr = parse("a : b c = 17").unwrap().unwrap(); + assert_eq!( + format!("{expr}"), + "conjunction\n compare :\n a\n b\n compare =\n c\n 17\n" + ); + } + + #[test] + fn test_display_member() { + let expr = parse("a.b > 17").unwrap().unwrap(); + assert_eq!(format!("{expr}"), "compare >\n a.b\n 17\n"); + } + + #[test] + fn test_display_function() { + let expr = parse("func(val)").unwrap().unwrap(); + assert_eq!(format!("{expr}"), "call func\n val\n"); + } + + #[test] + fn test_display_string_literal() { + // String literals are displayed with Rust's {:?} quoting. + let expr = parse(r#"x = "hello""#).unwrap().unwrap(); + assert_eq!(format!("{expr}"), "compare =\n x\n \"hello\"\n"); + } +} diff --git a/src/eval.rs b/src/eval.rs new file mode 100644 index 0000000..bf2afec --- /dev/null +++ b/src/eval.rs @@ -0,0 +1,920 @@ +use super::ast::{BinaryOp, CompareOp, Expr, UnaryOp}; +use regex::Regex; +use std::cmp::Ordering; + +/// A runtime value used during filter evaluation. +#[derive(Debug, Clone)] +pub enum Value<'a> { + /// Boolean value. + Bool(bool), + /// Signed integer (covers i8..i64). + Int(i64), + /// Unsigned integer (covers u8..u64). + Uint(u64), + /// Floating-point number. + Float(f64), + /// Borrowed string reference. + String(&'a str), + /// Owned string (for computed values). + StringOwned(std::string::String), + /// A list of values (for repeated fields / slices). + List(Vec<Value<'a>>), + /// A map of string keys to values. + Map(Vec<(&'a str, Value<'a>)>), + /// Absent value. + Null, +} + +impl<'a> Value<'a> { + /// Returns the string content if this is a string variant. + pub fn as_str(&self) -> Option<&str> { + match self { + Value::String(s) => Some(s), + Value::StringOwned(s) => Some(s.as_str()), + _ => None, + } + } + + /// Returns true if this value is the zero/default for its type. + pub fn is_zero(&self) -> bool { + match self { + Value::Bool(b) => !b, + Value::Int(i) => *i == 0, + Value::Uint(u) => *u == 0, + Value::Float(f) => *f == 0.0, + Value::String(s) => s.is_empty(), + Value::StringOwned(s) => s.is_empty(), + Value::List(v) => v.is_empty(), + Value::Map(m) => m.is_empty(), + Value::Null => true, + } + } + + /// Try to compare two values, returning an ordering if possible. + fn compare(&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)) => (*a as f64).partial_cmp(b), + (Value::Float(a), Value::Int(b)) => a.partial_cmp(&(*b as f64)), + (Value::Uint(a), Value::Float(b)) => (*a as f64).partial_cmp(b), + (Value::Float(a), Value::Uint(b)) => a.partial_cmp(&(*b as f64)), + (Value::Int(a), Value::Uint(b)) => { + if *a < 0 { + Some(Ordering::Less) + } else { + (*a as u64).partial_cmp(b) + } + } + (Value::Uint(a), Value::Int(b)) => { + if *b < 0 { + Some(Ordering::Greater) + } else { + a.partial_cmp(&(*b as u64)) + } + } + _ => None, + } + } +} + +/// Trait that types must implement to be filterable. +/// +/// # Example +/// +/// ```rust +/// use aip_filter::{Value, Filterable}; +/// +/// struct Issue { +/// state: String, +/// priority: i64, +/// } +/// +/// impl Filterable for Issue { +/// fn field(&self, name: &str) -> Option<Value<'_>> { +/// match name { +/// "state" => Some(Value::String(&self.state)), +/// "priority" => Some(Value::Int(self.priority)), +/// _ => None, +/// } +/// } +/// } +/// ``` +pub trait Filterable { + /// Look up a field by name, returning its value. + /// + /// The name matching should ideally support both snake_case and camelCase + /// forms, though this is up to the implementor. + /// + /// Return `None` if the field doesn't exist. + fn field(&self, name: &str) -> Option<Value<'_>>; + + /// Look up a nested field path like `["a", "b"]` for `a.b`. + /// + /// Default implementation walks through `field()` calls for structs. + /// Override this for custom nested access. + fn field_path(&self, path: &[&str]) -> Option<Value<'_>> { + if path.is_empty() { + return None; + } + if path.len() == 1 { + return self.field(path[0]); + } + // Default: can't traverse deeper without knowing the sub-type + None + } + + /// Return all field values for "global restriction" matching + /// (when a bare value appears without a field name). + /// + /// Default returns an empty vec (no global matching). + fn all_field_values(&self) -> Vec<Value<'_>> { + Vec::new() + } +} + +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, .. + } => { + // A bare name/value: global restriction matching. + // Check if any field contains or equals the value. + if let Some(field_val) = val.field(name) { + // If it's a boolean field referenced by name, return its value + if !*is_string + && let Value::Bool(b) = field_val { + return b; + } + return !field_val.is_zero(); + } + + // Try matching against all fields + let search = name.as_str(); + for field_val in val.all_field_values() { + if value_contains_str(&field_val, search) { + return true; + } + } + false + } + + 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(), + } + } else { + false + } + } + + Expr::Function { .. } => { + // Function evaluation is not yet supported + false + } + } + } +} + +/// 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, val) +} + +fn eval_comparison_with_value<T: Filterable>( + op: CompareOp, + left_val: &Value<'_>, + right: &Expr, + val: &T, +) -> bool { + // Handle the right side, it could be a composite expression (AND/OR) + match right { + Expr::Binary { + op: bin_op, + left: rleft, + right: rright, + .. + } => { + let l = eval_comparison_with_value(op, left_val, rleft, val); + let r = eval_comparison_with_value(op, left_val, rright, val); + match bin_op { + BinaryOp::And => l && r, + BinaryOp::Or => l || r, + } + } + Expr::Unary { + op: UnaryOp::Minus | UnaryOp::Not, + expr, + .. + } => !eval_comparison_with_value(op, left_val, expr, val), + + _ => { + let right_str = expr_to_literal_str(right); + let right_str = right_str.as_deref(); + + 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 { + // Wildcard handling + if rs == "*" { + return !left_val.is_zero(); + } + 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 + } + } + + // 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 + } + } + } + } + } +} + +/// Resolve an expression to its value given a filterable object. +fn resolve_expr_value<'a, T: Filterable>(expr: &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::StringOwned(name.clone())) + } else { + val.field(name) + } + } + 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, + } + } + path.reverse(); + + // Try field_path first + if let Some(v) = val.field_path(&path) { + return Some(v); + } + + // Fall back to walking field by field (for nested Filterable values) + // First field + let first_val = val.field(path[0])?; + + // 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, + }; + } + Some(current) +} + +/// Extract the literal string from an expression (name or member chain as dotted string). +fn expr_to_literal_str(expr: &Expr) -> Option<String> { + match expr { + Expr::Name { name, .. } => Some(name.clone()), + 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(parts.join(".")) + } + Expr::Function { .. } => None, + _ => None, + } +} + +/// 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(_) => match literal.to_lowercase().as_str() { + "true" | "1" => Value::Bool(true), + "false" | "0" => Value::Bool(false), + _ => Value::String(literal), + }, + Value::Int(_) => { + if let Ok(i) = literal.parse::<i64>() { + Value::Int(i) + } else if let Ok(f) = literal.parse::<f64>() { + Value::Int(f as i64) + } else { + Value::String(literal) + } + } + Value::Uint(_) => { + if let Ok(u) = literal.parse::<u64>() { + Value::Uint(u) + } else { + Value::String(literal) + } + } + Value::Float(_) => { + if let Ok(f) = literal.parse::<f64>() { + Value::Float(f) + } else { + Value::String(literal) + } + } + Value::String(_) | Value::StringOwned(_) => Value::String(literal), + _ => Value::String(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(i) => { + if let Ok(ri) = s.parse::<i64>() { + match op { + CompareOp::Equals | CompareOp::Has => *i == ri, + _ => false, + } + } else { + false + } + } + Value::Uint(u) => { + if let Ok(ru) = s.parse::<u64>() { + match op { + CompareOp::Equals | CompareOp::Has => *u == ru, + _ => false, + } + } else { + false + } + } + Value::Float(f) => { + if let Ok(rf) = s.parse::<f64>() { + match op { + CompareOp::Equals | CompareOp::Has => (*f - rf).abs() < f64::EPSILON, + _ => false, + } + } else { + false + } + } + Value::Bool(b) => { + let sb = matches!(s.to_lowercase().as_str(), "true" | "1"); + match op { + CompareOp::Equals | CompareOp::Has => *b == sb, + _ => false, + } + } + 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, + } +} + +/// String matching: case-insensitive equality for `=`, word-boundary match for `:`, wildcard support. +fn string_match(haystack: &str, needle: &str, op: CompareOp) -> bool { + match op { + CompareOp::Has => { + // Wildcard: * prefix + if let Some(suffix) = needle.strip_prefix('*') { + return haystack.len() >= suffix.len() + && haystack[haystack.len() - suffix.len()..].eq_ignore_ascii_case(suffix); + } + // Wildcard: * suffix + if let Some(prefix) = needle.strip_suffix('*') { + return haystack.len() >= prefix.len() + && haystack[..prefix.len()].eq_ignore_ascii_case(prefix); + } + + // Word boundary match + let hl = haystack.to_lowercase(); + let nl = needle.to_lowercase(); + if let Some(idx) = hl.find(&nl) { + let is_boundary = |b: u8| -> bool { + b < 0x80 && !b.is_ascii_alphanumeric() + }; + let start_ok = idx == 0 || is_boundary(haystack.as_bytes()[idx - 1]); + let end_ok = idx + nl.len() >= haystack.len() + || is_boundary(haystack.as_bytes()[idx + nl.len()]); + if start_ok && end_ok { + return true; + } + } + + // Also check individual words + let words = split_string(haystack); + if words.len() > 1 { + for word in &words { + if string_match(word, needle, CompareOp::Has) { + return true; + } + } + } + + false + } + CompareOp::Equals => { + // Wildcard: * prefix + if let Some(suffix) = needle.strip_prefix('*') { + return haystack.len() >= suffix.len() + && haystack[haystack.len() - suffix.len()..].eq_ignore_ascii_case(suffix); + } + // Wildcard: * suffix + if let Some(prefix) = needle.strip_suffix('*') { + return haystack.len() >= prefix.len() + && haystack[..prefix.len()].eq_ignore_ascii_case(prefix); + } + haystack.eq_ignore_ascii_case(needle) + } + CompareOp::NotEquals => !haystack.eq_ignore_ascii_case(needle), + _ => { + // For ordering comparisons on strings, use case-sensitive compare + let ord = haystack.cmp(needle); + match op { + CompareOp::LessThan => ord == Ordering::Less, + CompareOp::LessThanEquals => ord != Ordering::Greater, + CompareOp::GreaterThan => ord == Ordering::Greater, + CompareOp::GreaterThanEquals => ord != Ordering::Less, + _ => false, + } + } + } +} + +/// Check if a value contains a string (for global restriction matching). +fn value_contains_str(val: &Value<'_>, search: &str) -> bool { + match val { + Value::String(s) => s.to_lowercase().contains(&search.to_lowercase()), + Value::StringOwned(s) => s.to_lowercase().contains(&search.to_lowercase()), + Value::Int(i) => i.to_string() == search, + Value::Uint(u) => u.to_string() == search, + Value::Float(f) => f.to_string() == search, + Value::Bool(b) => { + let bs = if *b { "true" } else { "false" }; + bs == search.to_lowercase() + } + 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::Null => false, + } +} + +/// Compare two values using a comparison operator. +fn compare_values(op: CompareOp, left: &Value<'_>, right: &Value<'_>) -> 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 !ls.eq_ignore_ascii_case(rs); + } + 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 + } + } +} + +/// Split a string into words. +fn split_string(s: &str) -> Vec<&str> { + let mut result = Vec::new(); + let mut start = None; + + for (i, c) in s.char_indices() { + if c.is_whitespace() { + if let Some(s_idx) = start { + result.push(&s[s_idx..i]); + start = None; + } + } else if is_text_start_char(c) { + if start.is_none() { + start = Some(i); + } + } else { + if let Some(s_idx) = start { + result.push(&s[s_idx..i]); + start = None; + } + // Single char becomes its own word + let end = i + c.len_utf8(); + result.push(&s[i..end]); + } + } + + if let Some(s_idx) = start { + result.push(&s[s_idx..]); + } + + result +} + +fn is_text_start_char(r: char) -> bool { + matches!(r, + '#'..='\'' | '*' | '/' | ';' | '?' | '@' | 'A'..='Z' | '[' | ']' | '^'..='}' | '\\' + ) || ('\u{00a1}'..='\u{0effff}').contains(&r) +} + +#[cfg(test)] +mod tests { + use super::*; + use crate::parse; + + struct TestItem { + state: String, + priority: i64, + score: f64, + active: bool, + labels: Vec<String>, + name: String, + } + + impl Filterable for TestItem { + fn field(&self, name: &str) -> Option<Value<'_>> { + match name { + "state" => Some(Value::String(&self.state)), + "priority" => Some(Value::Int(self.priority)), + "score" => Some(Value::Float(self.score)), + "active" => Some(Value::Bool(self.active)), + "labels" => Some(Value::List( + self.labels.iter().map(|l| Value::String(l.as_str())).collect(), + )), + "name" => Some(Value::String(&self.name)), + _ => None, + } + } + + fn all_field_values(&self) -> Vec<Value<'_>> { + vec![ + Value::String(&self.state), + Value::Int(self.priority), + Value::Float(self.score), + Value::Bool(self.active), + Value::String(&self.name), + ] + } + } + + fn item() -> TestItem { + TestItem { + state: "open".into(), + priority: 5, + score: 9.5, + active: true, + labels: vec!["bug".into(), "urgent".into()], + name: "Fix crash on startup".into(), + } + } + + #[test] + fn test_equals() { + let expr = parse(r#"state = "open""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"state = "closed""#).unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_not_equals() { + let expr = parse(r#"state != "closed""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_numeric_comparison() { + let expr = parse("priority > 3").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse("priority < 3").unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + + let expr = parse("priority >= 5").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse("priority <= 5").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_float_comparison() { + let expr = parse("score > 9.0").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_and() { + let expr = parse(r#"state = "open" AND priority > 3"#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"state = "closed" AND priority > 3"#) + .unwrap() + .unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_or() { + let expr = parse(r#"state = "closed" OR priority > 3"#) + .unwrap() + .unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_negation() { + let expr = parse(r#"-state = "closed""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"NOT state = "open""#).unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_has_on_list() { + let expr = parse(r#"labels : "bug""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"labels : "feature""#).unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_has_on_string() { + let expr = parse(r#"name : "crash""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"name : "memory""#).unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_boolean_field() { + let expr = parse("active").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_regex_match() { + let expr = parse(r#"state =~ "^op""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"state !~ "^cl""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_wildcard() { + let expr = parse(r#"state = "op*""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse(r#"state = "*en""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_case_insensitive() { + let expr = parse(r#"state = "OPEN""#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_implicit_and() { + let expr = parse(r#"state = "open" priority > 3"#).unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_parenthesized() { + let expr = parse(r#"(state = "open" OR state = "closed") AND priority > 3"#) + .unwrap() + .unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_has_wildcard_star() { + let expr = parse("priority : *").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + } + + #[test] + fn test_global_restriction() { + let expr = parse("open").unwrap().unwrap(); + assert!(expr.evaluate(&item())); + + let expr = parse("nonexistent").unwrap().unwrap(); + assert!(!expr.evaluate(&item())); + } + + #[test] + fn test_nested_field() { + struct Outer { + inner: Inner, + } + struct Inner { + value: i64, + } + + impl Filterable for Outer { + fn field(&self, name: &str) -> Option<Value<'_>> { + match name { + "inner" => Some(Value::Map(vec![ + ("value", Value::Int(self.inner.value)), + ])), + _ => None, + } + } + + fn field_path(&self, path: &[&str]) -> Option<Value<'_>> { + match path { + ["inner", "value"] => Some(Value::Int(self.inner.value)), + _ => None, + } + } + } + + let outer = Outer { + inner: Inner { value: 42 }, + }; + + let expr = parse("inner.value > 10").unwrap().unwrap(); + assert!(expr.evaluate(&outer)); + } +} diff --git a/src/lex.rs b/src/lex.rs new file mode 100644 index 0000000..284fd75 --- /dev/null +++ b/src/lex.rs @@ -0,0 +1,574 @@ +use super::ast::Position; + +/// Token kinds produced by the lexer. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub(crate) enum TokenKind { + InvalidInput, + Eof, + Wsc, // whitespace or comment + Dot, // . + Has, // : + Or, // OR + And, // AND + Not, // NOT + Lparen, // ( + Rparen, // ) + Comma, // , + LessThan, // < + GreaterThan, // > + GreaterThanEquals, // >= + LessThanEquals, // <= + NotEquals, // != + MatchesRegexp, // =~ + NotMatchesRegexp, // !~ + Equals, // = + Minus, // - + Plus, // + + Tilde, // ~ + #[allow(dead_code)] + Backslash, // backslash + StringLit, // quoted string + Text, // unquoted text/name +} + +/// A lexical token. +#[derive(Debug, Clone, PartialEq, Eq)] +pub(crate) struct Token { + pub kind: TokenKind, + pub pos: Position, + pub val: String, // only set for StringLit and Text +} + +/// Lexer converts a filter string into tokens. +pub(crate) struct Lexer { + input: Vec<char>, + cursor: usize, + pushed: Option<Token>, + prev_dot: bool, + prev_text: bool, + next_pos: Position, +} + +impl Lexer { + pub fn new(input: &str) -> Self { + Lexer { + input: input.chars().collect(), + cursor: 0, + pushed: None, + prev_dot: false, + prev_text: false, + next_pos: Position { line: 1, col: 0 }, + } + } + + 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; + self.prev_dot = false; + self.prev_text = false; + + let Some(r) = self.peek() else { + return Token { kind: TokenKind::Eof, pos, val: String::new() }; + }; + + self.advance(); + + match r { + _ if is_white(r) => { + self.skip_white(); + Token { kind: TokenKind::Wsc, pos, val: String::new() } + } + '-' => { + if let Some(rn) = self.peek() { + if rn == '-' { + self.advance(); + self.skip_comment(); + self.skip_white(); + return Token { kind: TokenKind::Wsc, pos, val: String::new() }; + } + if is_digit(rn) { + return self.text(r, prev_dot); + } + if !prev_text && rn == '.' + && let Some(&next_after) = self.input.get(self.cursor + 1) + && is_digit(next_after) { + return self.text(r, prev_dot); + } + } + Token { kind: TokenKind::Minus, pos, val: String::new() } + } + '.' => { + if self.peek().is_none() { + self.prev_dot = true; + return Token { kind: TokenKind::Dot, pos, val: String::new() }; + } + if !prev_text + && let Some(rn) = self.peek() + && is_digit(rn) { + return self.text(r, prev_dot); + } + self.prev_dot = true; + Token { kind: TokenKind::Dot, pos, val: String::new() } + } + ':' => Token { kind: TokenKind::Has, pos, val: String::new() }, + 'O' => { + if self.remaining() > 0 && self.input[self.cursor] == 'R' + && (self.remaining() < 2 || is_white(self.input[self.cursor + 1])) + { + self.advance(); + return Token { kind: TokenKind::Or, pos, val: String::new() }; + } + self.text(r, prev_dot) + } + 'A' => { + if self.remaining() > 1 + && self.input[self.cursor] == 'N' + && self.input[self.cursor + 1] == 'D' + && (self.remaining() < 3 || is_white(self.input[self.cursor + 2])) + { + self.advance(); + self.advance(); + return Token { kind: TokenKind::And, pos, val: String::new() }; + } + self.text(r, prev_dot) + } + 'N' => { + if self.remaining() > 1 + && self.input[self.cursor] == 'O' + && self.input[self.cursor + 1] == 'T' + && (self.remaining() < 3 || is_white(self.input[self.cursor + 2])) + { + self.advance(); + self.advance(); + return Token { kind: TokenKind::Not, pos, val: String::new() }; + } + self.text(r, prev_dot) + } + '(' => Token { kind: TokenKind::Lparen, pos, val: String::new() }, + ')' => Token { kind: TokenKind::Rparen, pos, val: String::new() }, + ',' => Token { kind: TokenKind::Comma, pos, val: String::new() }, + '<' => { + if self.peek() == Some('=') { + self.advance(); + Token { kind: TokenKind::LessThanEquals, pos, val: String::new() } + } else { + Token { kind: TokenKind::LessThan, pos, val: String::new() } + } + } + '>' => { + if self.peek() == Some('=') { + self.advance(); + Token { kind: TokenKind::GreaterThanEquals, pos, val: String::new() } + } else { + Token { kind: TokenKind::GreaterThan, pos, val: String::new() } + } + } + '!' => { + if let Some(rn) = self.peek() { + if rn == '=' { + self.advance(); + return Token { kind: TokenKind::NotEquals, pos, val: String::new() }; + } + if rn == '~' { + self.advance(); + return Token { kind: TokenKind::NotMatchesRegexp, pos, val: String::new() }; + } + } + // bare ! is part of a name + self.text(r, prev_dot) + } + '=' => { + if self.peek() == Some('~') { + self.advance(); + Token { kind: TokenKind::MatchesRegexp, pos, val: String::new() } + } else { + Token { kind: TokenKind::Equals, pos, val: String::new() } + } + } + '+' => Token { kind: TokenKind::Plus, pos, val: String::new() }, + '~' => Token { kind: TokenKind::Tilde, pos, val: String::new() }, + '"' => self.collect_string(), + _ if is_text_start(r) || is_digit(r) => self.text(r, prev_dot), + _ => Token { kind: TokenKind::InvalidInput, pos, val: String::new() }, + } + } + + 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> { + self.input.get(self.cursor).copied() + } + + fn remaining(&self) -> usize { + self.input.len() - self.cursor + } + + fn advance(&mut self) -> Option<char> { + if self.cursor >= self.input.len() { + return None; + } + let r = self.input[self.cursor]; + self.cursor += 1; + if r == '\n' { + self.next_pos.line += 1; + self.next_pos.col = 0; + } else { + self.next_pos.col += 1; + } + Some(r) + } + + fn skip_white(&mut self) { + loop { + match self.peek() { + Some(r) if is_white(r) => { self.advance(); } + Some('-') => { + if self.input.get(self.cursor + 1) == Some(&'-') { + self.advance(); + self.advance(); + self.skip_comment(); + } else { + return; + } + } + _ => return, + } + } + } + + fn skip_comment(&mut self) { + while let Some(r) = self.peek() { + if r == '\t' || (' '..='~').contains(&r) || is_a1_or_higher(r) { + self.advance(); + } else { + return; + } + } + } + + fn text(&mut self, first: char, prev_dot: bool) -> Token { + let pos = self.next_pos; + + let mut sb = String::new(); + + if first != '\\' { + sb.push(first); + } else if !self.text_esc(&mut sb) { + return Token { kind: TokenKind::InvalidInput, pos, val: String::new() }; + } + + // Number prefix handling + if first == '-' || first == '.' || is_digit(first) { + let mut r = first; + while let Some(rn) = self.peek() { + if is_digit(rn) { + sb.push(rn); + self.advance(); + if r == '.' { + break; + } + } else if !prev_dot && r != '.' && rn == '.' { + sb.push(rn); + self.advance(); + break; + } else { + break; + } + if r == '-' { + r = rn; + } + } + } + + loop { + let Some(rn) = self.peek() else { break }; + if rn == '\\' { + self.advance(); + if !self.text_esc(&mut sb) { + return Token { kind: TokenKind::InvalidInput, pos, val: String::new() }; + } + } else if is_text_start(rn) || is_digit(rn) || rn == '+' || rn == '-' { + sb.push(rn); + self.advance(); + } else if rn == '!' { + // ! is part of a name unless followed by = or ~ + if let Some(&next) = self.input.get(self.cursor + 1) + && (next == '=' || next == '~') { + break; + } + sb.push(rn); + self.advance(); + } else { + break; + } + } + + self.prev_text = true; + Token { kind: TokenKind::Text, pos, val: sb } + } + + fn text_esc(&mut self, sb: &mut String) -> bool { + let Some(r) = self.peek() else { return false }; + self.handle_text_esc(r, sb) + } + + fn handle_text_esc(&mut self, r: char, sb: &mut String) -> bool { + match r { + ',' | ':' | '=' | '<' | '>' | '+' | '~' | '"' | '\\' | '.' | '*' => { + self.advance(); + sb.push(r); + true + } + 'u' => self.handle_hex(r, sb), + '0'..='7' => { + // Octal escapes + let d0 = r as u32 - '0' as u32; + if r <= '3' && self.remaining() >= 3 { + let n1 = self.input[self.cursor + 1]; + let n2 = self.input[self.cursor + 2]; + if is_octal_digit(n1) && is_octal_digit(n2) { + self.advance(); // skip r + self.advance(); // skip n1 + self.advance(); // skip n2 + let val = (d0 << 6) + + ((n1 as u32 - '0' as u32) << 3) + + (n2 as u32 - '0' as u32); + if let Some(c) = char::from_u32(val) { + sb.push(c); + } else { + sb.push(char::REPLACEMENT_CHARACTER); + } + return true; + } + } + if self.remaining() >= 2 { + let n1 = self.input[self.cursor + 1]; + if is_octal_digit(n1) { + self.advance(); // skip r + self.advance(); // skip n1 + let val = (d0 << 3) + (n1 as u32 - '0' as u32); + if let Some(c) = char::from_u32(val) { + sb.push(c); + } + return true; + } + } + self.advance(); // skip r + if let Some(c) = char::from_u32(d0) { + sb.push(c); + } + true + } + 'x' => self.handle_hex(r, sb), + _ => false, + } + } + + fn handle_hex(&mut self, starter: char, sb: &mut String) -> bool { + let len = if starter == 'u' { 4 } else { 2 }; + + if self.remaining() < len + 1 { + return false; + } + + // Check all hex digits (they start at cursor+1) + for i in 1..=len { + if !is_hex_digit(self.input[self.cursor + i]) { + return false; + } + } + + // Skip the starter ('u' or 'x') + self.advance(); + + let mut val: u32 = 0; + for _ in 0..len { + let r1 = self.input[self.cursor]; + self.advance(); + val <<= 4; + if ('a'..='f').contains(&r1) { + val += 10 + r1 as u32 - 'a' as u32; + } else if ('A'..='F').contains(&r1) { + val += 10 + r1 as u32 - 'A' as u32; + } else { + val += r1 as u32 - '0' as u32; + } + } + + if starter == 'u' { + if let Some(c) = char::from_u32(val) { + sb.push(c); + } else { + sb.push(char::REPLACEMENT_CHARACTER); + } + } else { + // \xHH: treat as the Unicode scalar value with that code point. + // All values 0x00..=0xFF are valid Unicode scalar values. + if let Some(c) = char::from_u32(val) { + sb.push(c); + } else { + sb.push(char::REPLACEMENT_CHARACTER); + } + } + true + } + + fn collect_string(&mut self) -> Token { + let start_pos = self.next_pos; + let mut sb = String::new(); + while let Some(r) = self.peek() { + self.advance(); + match r { + '"' => return Token { kind: TokenKind::StringLit, pos: start_pos, val: sb }, + '\\' => { + let Some(rn) = self.peek() else { + return Token { kind: TokenKind::InvalidInput, pos: start_pos, val: String::new() }; + }; + if !self.handle_text_esc(rn, &mut sb) { + // String-only single-char escape sequences not handled by handle_text_esc + match rn { + 'a' => { self.advance(); sb.push('\x07'); } + 'b' => { self.advance(); sb.push('\x08'); } + 'f' => { self.advance(); sb.push('\x0c'); } + 'n' => { self.advance(); sb.push('\n'); } + 'r' => { self.advance(); sb.push('\r'); } + 't' => { self.advance(); sb.push('\t'); } + 'v' => { self.advance(); sb.push('\x0b'); } + // Unrecognised escape: keep the backslash + _ => sb.push('\\'), + } + } + } + _ => sb.push(r), + } + } + // Unterminated string + Token { kind: TokenKind::InvalidInput, pos: start_pos, val: String::new() } + } +} + +fn is_white(r: char) -> bool { + matches!(r, ' ' | '\t' | '\x0c' | '\u{00a0}' | '\r' | '\n') +} + +fn is_digit(r: char) -> bool { + ('0'..='9').contains(&r) +} + +fn is_octal_digit(r: char) -> bool { + ('0'..='7').contains(&r) +} + +fn is_hex_digit(r: char) -> bool { + is_digit(r) || ('a'..='f').contains(&r) || ('A'..='F').contains(&r) +} + +fn is_text_start(r: char) -> bool { + matches!(r, + '#'..='\'' | '*' | '/' | ';' | '?' | '@' | 'A'..='Z' | '[' | ']' | '^'..='}' | '\\' + ) || is_a1_or_higher(r) +} + +fn is_a1_or_higher(r: char) -> bool { + ('\u{00a1}'..='\u{0effff}').contains(&r) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_basic_tokens() { + let mut lex = Lexer::new("x = 42"); + let t1 = lex.next_token(); + assert_eq!(t1.kind, TokenKind::Text); + assert_eq!(t1.val, "x"); + + let t2 = lex.next_token(); + assert_eq!(t2.kind, TokenKind::Wsc); + + let t3 = lex.next_token(); + assert_eq!(t3.kind, TokenKind::Equals); + + let t4 = lex.next_token(); + assert_eq!(t4.kind, TokenKind::Wsc); + + let t5 = lex.next_token(); + assert_eq!(t5.kind, TokenKind::Text); + assert_eq!(t5.val, "42"); + + let t6 = lex.next_token(); + assert_eq!(t6.kind, TokenKind::Eof); + } + + #[test] + fn test_keywords() { + let mut lex = Lexer::new("AND OR NOT"); + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::And); + lex.next_token(); // wsc + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::Or); + lex.next_token(); // wsc + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::Not); + } + + #[test] + fn test_string() { + let mut lex = Lexer::new(r#""hello world""#); + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::StringLit); + assert_eq!(t.val, "hello world"); + } + + #[test] + fn test_comparison_ops() { + let mut lex = Lexer::new("< <= > >= != =~ !~"); + assert_eq!(lex.next_token().kind, TokenKind::LessThan); + lex.next_token(); // wsc + assert_eq!(lex.next_token().kind, TokenKind::LessThanEquals); + lex.next_token(); + assert_eq!(lex.next_token().kind, TokenKind::GreaterThan); + lex.next_token(); + assert_eq!(lex.next_token().kind, TokenKind::GreaterThanEquals); + lex.next_token(); + assert_eq!(lex.next_token().kind, TokenKind::NotEquals); + lex.next_token(); + assert_eq!(lex.next_token().kind, TokenKind::MatchesRegexp); + lex.next_token(); + assert_eq!(lex.next_token().kind, TokenKind::NotMatchesRegexp); + } + + #[test] + fn test_comment() { + let mut lex = Lexer::new("x -- this is a comment\n= 42"); + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::Text); + assert_eq!(t.val, "x"); + let t = lex.next_token(); + assert_eq!(t.kind, TokenKind::Wsc); + let t = lex.next_token(); + 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/lib.rs b/src/lib.rs new file mode 100644 index 0000000..60e05d3 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,59 @@ +//! Parses and evaluates [AIP-160](https://google.aip.dev/160) filter expressions. +//! +//! ## Example +//! +//! ```rust +//! use aip_filter::{parse, Value, Filterable}; +//! +//! let expr = parse("state = \"open\" AND priority > 3").unwrap().unwrap(); +//! println!("{}", expr); +//! ``` +//! +//! ## Evaluating filters +//! +//! Implement [`Filterable`] for your type, then call [`Expr::evaluate`]: +//! +//! ```rust +//! use aip_filter::{parse, Value, Filterable}; +//! +//! struct Issue { +//! state: String, +//! priority: i64, +//! labels: Vec<String>, +//! } +//! +//! impl Filterable for Issue { +//! fn field(&self, name: &str) -> Option<Value<'_>> { +//! match name { +//! "state" => Some(Value::String(&self.state)), +//! "priority" => Some(Value::Int(self.priority)), +//! "labels" => Some(Value::List( +//! self.labels.iter().map(|l| Value::String(l)).collect() +//! )), +//! _ => None, +//! } +//! } +//! } +//! +//! let expr = parse("state = \"open\"").unwrap().unwrap(); +//! let issue = Issue { state: "open".into(), priority: 1, labels: vec![] }; +//! assert!(expr.evaluate(&issue)); +//! ``` + +pub mod ast; +pub mod display; +pub mod eval; +pub mod lex; +pub mod parser; + +pub use ast::{BinaryOp, CompareOp, Expr, Position, UnaryOp}; +pub use eval::{Filterable, Value}; + +/// Parse a filter expression string into an [`Expr`] AST. +/// +/// Returns `Ok(None)` for empty/whitespace-only input. +/// Returns `Ok(Some(expr))` on success. +/// Returns `Err(message)` on parse errors. +pub fn parse(input: &str) -> Result<Option<Expr>, String> { + parser::parse_filter(input) +} diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..5bd138a --- /dev/null +++ b/src/main.rs @@ -0,0 +1,155 @@ +use aip_filter::{parse, Expr, Filterable, Value}; +use serde_json::Value as Json; +use std::{ + fs::File, + io::{self, BufRead, BufReader, BufWriter, Write}, + path::Path, + 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(), + _ => vec![], + } + } +} + +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(), + )), + // Nested objects are accessible via field_path; skip at top level. + Json::Object(_) => None, + } +} + +fn filter_lines( + expr: &Expr, + mut reader: impl BufRead, + out: &mut impl Write, + source: &str, +) -> io::Result<()> { + let mut line_buffer = String::with_capacity(128); + let mut lineno = 0; + + while reader.read_line(&mut line_buffer)? > 0 { + lineno += 1; + + // Skip empty lines + if !line_buffer.trim().is_empty() { + match serde_json::from_str::<Json>(&line_buffer) { + Ok(json) => { + if expr.evaluate(&JsonRecord(&json)) { + // Write directly to stdout + out.write_all(line_buffer.as_bytes())?; + } + } + Err(e) => { + eprintln!("{}:{}: invalid JSON: {}", source, lineno, e); + } + } + } + + // Clear the buffer for the next line, + // which keeps the memory allocated but resets the length to 0. + line_buffer.clear(); + } + + Ok(()) +} + +fn usage(program: &str) -> ! { + eprintln!("usage: {program} [-p|--print] <expr> [file...]"); + process::exit(2); +} + +fn main() { + let mut args: Vec<String> = std::env::args().collect(); + let program = args.remove(0); + + if args.is_empty() || args[0] == "-h" || args[0] == "--help" { + usage(&program); + } + + // Check for print flag + let mut print_only = false; + if args[0] == "-p" || args[0] == "--print" { + print_only = true; + args.remove(0); + if args.is_empty() { usage(&program); } + } + + let raw_expr = args.remove(0); + let expr = match parse(&raw_expr) { + Ok(Some(e)) => e, + Ok(None) => { + // Empty expression matches everything; just cat the input. + let stdin = io::stdin(); + let mut out = BufWriter::new(io::stdout().lock()); + for line in stdin.lock().lines() { + writeln!(out, "{}", line.unwrap_or_default()).ok(); + } + return; + } + Err(e) => { + eprintln!("{program}: {e}"); + process::exit(1); + } + }; + + if print_only { + println!("{}", expr); + return; + } + + let mut out = BufWriter::new(io::stdout().lock()); + + if args.is_empty() { + // Read from stdin. + let stdin = io::stdin(); + if let Err(e) = filter_lines(&expr, stdin.lock(), &mut out, "<stdin>") { + eprintln!("{program}: {e}"); + process::exit(1); + } + } else { + for path in &args { + let source = path.as_str(); + let file = match File::open(Path::new(path)) { + Ok(f) => f, + Err(e) => { + eprintln!("{program}: {path}: {e}"); + process::exit(1); + } + }; + if let Err(e) = filter_lines(&expr, BufReader::new(file), &mut out, source) { + eprintln!("{program}: {path}: {e}"); + process::exit(1); + } + } + } +} diff --git a/src/parser.rs b/src/parser.rs new file mode 100644 index 0000000..7555a87 --- /dev/null +++ b/src/parser.rs @@ -0,0 +1,546 @@ +use super::ast::{BinaryOp, CompareOp, Expr, Position, UnaryOp}; +use super::lex::{Lexer, Token, TokenKind}; + +/// 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 tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + if tok.kind == TokenKind::Eof { + return Ok(None); + } + lex.push_token(tok); + + let expr = parse_expression(&mut lex)?; + + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + if tok.kind != TokenKind::Eof { + return Err(format!("{}: unexpected tokens after filter expression", tok.pos)); + } + + Ok(Some(expr)) +} + +/// expression = sequence, { "AND", sequence } ; +fn parse_expression(lex: &mut Lexer) -> Result<Expr, String> { + parse_junction(lex, TokenKind::And, parse_sequence) +} + +/// sequence = factor, { factor } ; +fn parse_sequence(lex: &mut Lexer) -> Result<Expr, String> { + let mut factor = parse_factor(lex)?; + + loop { + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + lex.push_token(tok.clone()); + + if tok.kind == TokenKind::Eof || tok.kind == TokenKind::Rparen { + return Ok(factor); + } + + let pos = tok.pos; + + if tok.kind == TokenKind::And { + return Ok(factor); + } + + let rfactor = parse_factor(lex)?; + + factor = Expr::Binary { + op: BinaryOp::And, + left: Box::new(factor), + right: Box::new(rfactor), + pos, + }; + } +} + +/// factor = term, { "OR", term } ; +fn parse_factor(lex: &mut Lexer) -> Result<Expr, String> { + parse_junction(lex, TokenKind::Or, parse_term) +} + +/// Parse an AND or OR sequence. +fn parse_junction( + lex: &mut Lexer, + kind: TokenKind, + parse_element: fn(&mut Lexer) -> Result<Expr, String>, +) -> Result<Expr, String> { + let mut sub = parse_element(lex)?; + + loop { + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + + if tok.kind != kind { + lex.push_token(tok); + return Ok(sub); + } + + let pos = tok.pos; + + tok = lex.next_token(); + if tok.kind != TokenKind::Wsc { + lex.push_token(tok); + let name = if kind == TokenKind::And { "AND" } else { "OR" }; + return Err(format!("{}: missing whitespace after {}", pos, name)); + } + + let rsub = parse_element(lex)?; + + let op = if kind == TokenKind::And { + BinaryOp::And + } else { + BinaryOp::Or + }; + sub = Expr::Binary { + op, + left: Box::new(sub), + right: Box::new(rsub), + pos, + }; + } +} + +/// term = [ "-" | "NOT" ], primitive ; +fn parse_term(lex: &mut Lexer) -> Result<Expr, String> { + let tok = lex.next_token(); + let is_neg = tok.kind == TokenKind::Minus || tok.kind == TokenKind::Not; + let neg_pos = tok.pos; + let neg_kind = tok.kind; + + if !is_neg { + lex.push_token(tok); + } + + if neg_kind == TokenKind::Not { + let stok = lex.next_token(); + if stok.kind != TokenKind::Wsc { + lex.push_token(stok); + return Err(format!("{}: missing whitespace after NOT", neg_pos)); + } + } + + let ntok = lex.next_token(); + lex.push_token(ntok.clone()); + let prim = if ntok.kind == TokenKind::Minus || ntok.kind == TokenKind::Not { + parse_term(lex)? + } else { + parse_primitive(lex)? + }; + + if is_neg { + let op = if neg_kind == TokenKind::Minus { + UnaryOp::Minus + } else { + UnaryOp::Not + }; + Ok(Expr::Unary { + op, + expr: Box::new(prim), + pos: neg_pos, + }) + } else { + Ok(prim) + } +} + +/// Parse a primitive (comparison, function call, parenthesized expr, or bare value). +fn parse_primitive(lex: &mut Lexer) -> Result<Expr, String> { + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + + if tok.kind == TokenKind::Lparen { + return parse_parenthesized_expression(lex); + } + + let left = parse_comparable(lex, tok)?; + + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + + let cmp_op = match tok.kind { + TokenKind::LessThanEquals => Some(CompareOp::LessThanEquals), + TokenKind::LessThan => Some(CompareOp::LessThan), + TokenKind::GreaterThanEquals => Some(CompareOp::GreaterThanEquals), + TokenKind::GreaterThan => Some(CompareOp::GreaterThan), + TokenKind::NotEquals => Some(CompareOp::NotEquals), + TokenKind::Equals => Some(CompareOp::Equals), + TokenKind::Has => Some(CompareOp::Has), + TokenKind::MatchesRegexp => Some(CompareOp::MatchesRegexp), + TokenKind::NotMatchesRegexp => Some(CompareOp::NotMatchesRegexp), + _ => None, + }; + + if let Some(op) = cmp_op { + let pos = tok.pos; + + let ntok = lex.next_token(); + if ntok.kind != TokenKind::Wsc { + lex.push_token(ntok); + } + + let right = parse_arg(lex)?; + + // Validate regex on the right-hand side + if op == CompareOp::MatchesRegexp || op == CompareOp::NotMatchesRegexp { + validate_regex(&right)?; + } + + Ok(Expr::Comparison { + op, + left: Box::new(left), + right: Box::new(right), + pos, + }) + } else { + lex.push_token(tok); + Ok(left) + } +} + +/// Validate that a regex RHS only contains quoted strings. +fn validate_regex(expr: &Expr) -> Result<(), String> { + match expr { + Expr::Binary { left, right, .. } => { + validate_regex(left)?; + validate_regex(right) + } + Expr::Unary { expr, .. } => validate_regex(expr), + Expr::Name { is_string, pos, name, .. } => { + if !is_string { + return Err(format!("{}: regular expression is not a quoted string", pos)); + } + // Validate the regex syntax + if let Err(e) = regex::Regex::new(name) { + return Err(format!("{}: invalid regular expression: {}", pos, e)); + } + Ok(()) + } + Expr::Comparison { pos, .. } | Expr::Member { pos, .. } => { + Err(format!("{}: regular expression is not a quoted string", pos)) + } + Expr::Function { func, .. } => { + // Use the function name position + let pos = func_pos(func); + Err(format!("{}: regular expression is not a quoted string", pos)) + } + } +} + +fn func_pos(expr: &Expr) -> Position { + match expr { + Expr::Name { pos, .. } | Expr::Member { pos, .. } => *pos, + _ => Position { line: 0, col: 0 }, + } +} + +/// Parse a parenthesized expression. We have already consumed the `(`. +fn parse_parenthesized_expression(lex: &mut Lexer) -> Result<Expr, String> { + let tok = lex.next_token(); + if tok.kind != TokenKind::Wsc { + lex.push_token(tok); + } + + let mut ret = parse_expression(lex)?; + + // Mark all name exprs as composite + mark_composite(&mut ret); + + let tok = lex.next_token(); + if tok.kind != TokenKind::Rparen { + lex.push_token(tok.clone()); + return Err(format!( + "{}: expected right parenthesis after expression", + tok.pos + )); + } + + Ok(ret) +} + +fn mark_composite(expr: &mut Expr) { + match expr { + Expr::Binary { left, right, .. } => { + mark_composite(left); + mark_composite(right); + } + Expr::Unary { expr, .. } => { + mark_composite(expr); + } + Expr::Comparison { left, right, .. } => { + mark_composite(left); + mark_composite(right); + } + Expr::Name { is_composite, .. } => { + *is_composite = true; + } + Expr::Member { holder, .. } => { + mark_composite(holder); + } + Expr::Function { .. } => {} + } +} + +/// Parse a comparable (name, member, function). +fn parse_comparable(lex: &mut Lexer, tok: Token) -> Result<Expr, String> { + let mut saw_white = false; + let mut ntok = lex.next_token(); + if ntok.kind == TokenKind::Wsc { + saw_white = true; + ntok = lex.next_token(); + } + lex.push_token(ntok.clone()); + + let tok = match tok.kind { + TokenKind::StringLit | TokenKind::Text => tok, + TokenKind::And | TokenKind::Or | TokenKind::Not => { + if ntok.kind != TokenKind::Dot { + return Err(format!("{}: misplaced AND/OR/NOT", tok.pos)); + } + keyword_to_text(tok) + } + _ => return Err(format!("{}: expected identifier or value", tok.pos)), + }; + + match ntok.kind { + TokenKind::Dot => { + lex.next_token(); // consume dot + let dot_pos = ntok.pos; + let e = parse_member(lex, &tok, dot_pos)?; + + // Check if member is used as a function call + let ftok = lex.next_token(); + if ftok.kind != TokenKind::Lparen || saw_white { + lex.push_token(ftok); + return Ok(e); + } + parse_function(lex, e) + } + TokenKind::Lparen => { + let fn_expr = Expr::Name { + name: tok.val.clone(), + pos: tok.pos, + is_string: false, + is_composite: false, + }; + + if saw_white || tok.val.is_empty() || tok.val.starts_with(|c: char| c.is_ascii_digit()) + { + return Ok(fn_expr); + } + + lex.next_token(); // consume lparen + parse_function(lex, fn_expr) + } + _ => Ok(Expr::Name { + name: tok.val, + pos: tok.pos, + is_string: tok.kind == TokenKind::StringLit, + is_composite: false, + }), + } +} + +/// Parse member access: `identifier { "." identifier }`. +fn parse_member(lex: &mut Lexer, tok: &Token, pos: Position) -> Result<Expr, String> { + let mut ret: Expr = Expr::Name { + name: tok.val.clone(), + pos: tok.pos, + is_string: false, + is_composite: false, + }; + + let mut dot_pos = pos; + + loop { + let ntok = lex.next_token(); + let ntok = match ntok.kind { + TokenKind::StringLit | TokenKind::Text => ntok, + TokenKind::And | TokenKind::Or | TokenKind::Not => keyword_to_text(ntok), + _ => return Err(format!("{}: expected identifier", ntok.pos)), + }; + + ret = Expr::Member { + holder: Box::new(ret), + member: ntok.val, + pos: dot_pos, + }; + + let next = lex.next_token(); + if next.kind != TokenKind::Dot { + lex.push_token(next); + return Ok(ret); + } + dot_pos = next.pos; + } +} + +/// Parse a function call. We've consumed the `(`. +fn parse_function(lex: &mut Lexer, func: Expr) -> Result<Expr, String> { + let tok = lex.next_token(); + if tok.kind == TokenKind::Rparen { + return Ok(Expr::Function { + func: Box::new(func), + args: vec![], + }); + } + lex.push_token(tok); + + let mut args = Vec::new(); + loop { + let arg = parse_arg(lex)?; + args.push(arg); + + let mut tok = lex.next_token(); + if tok.kind == TokenKind::Rparen { + return Ok(Expr::Function { + func: Box::new(func), + args, + }); + } + if tok.kind == TokenKind::Wsc { + tok = lex.next_token(); + } + if tok.kind != TokenKind::Comma { + return Err(format!( + "{}: expected comma after function argument", + tok.pos + )); + } + + tok = lex.next_token(); + if tok.kind != TokenKind::Wsc { + lex.push_token(tok); + } + } +} + +/// Parse an argument (comparable, value, or parenthesized expression). +fn parse_arg(lex: &mut Lexer) -> Result<Expr, String> { + let tok = lex.next_token(); + if tok.kind == TokenKind::Lparen { + return parse_parenthesized_expression(lex); + } + parse_comparable(lex, tok) +} + +/// Convert a keyword token (AND/OR/NOT) to a text token. +fn keyword_to_text(tok: Token) -> Token { + let val = match tok.kind { + TokenKind::And => "AND", + TokenKind::Or => "OR", + TokenKind::Not => "NOT", + _ => unreachable!(), + }; + Token { + kind: TokenKind::Text, + pos: tok.pos, + val: val.to_string(), + } +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_empty() { + assert!(parse_filter("").unwrap().is_none()); + assert!(parse_filter(" ").unwrap().is_none()); + } + + #[test] + fn test_basic_comparison() { + let expr = parse_filter("x = 42").unwrap().unwrap(); + match expr { + Expr::Comparison { op, left, right, .. } => { + assert_eq!(op, CompareOp::Equals); + match *left { + Expr::Name { ref name, .. } => assert_eq!(name, "x"), + _ => panic!("expected name"), + } + match *right { + Expr::Name { ref name, .. } => assert_eq!(name, "42"), + _ => panic!("expected name"), + } + } + _ => panic!("expected comparison"), + } + } + + #[test] + fn test_conjunction() { + let expr = parse_filter("a : b c = 17").unwrap().unwrap(); + match expr { + Expr::Binary { op: BinaryOp::And, .. } => {} + _ => panic!("expected conjunction"), + } + } + + #[test] + fn test_negation() { + let expr = parse_filter("-a < 1").unwrap().unwrap(); + match expr { + Expr::Unary { op: UnaryOp::Minus, .. } => {} + _ => panic!("expected unary minus"), + } + } + + #[test] + fn test_member() { + let expr = parse_filter("a.b > 17").unwrap().unwrap(); + match expr { + Expr::Comparison { left, .. } => match *left { + Expr::Member { ref member, .. } => assert_eq!(member, "b"), + _ => panic!("expected member"), + }, + _ => panic!("expected comparison"), + } + } + + #[test] + fn test_function() { + let expr = parse_filter("func(val)").unwrap().unwrap(); + match expr { + Expr::Function { func, args } => { + match *func { + Expr::Name { ref name, .. } => assert_eq!(name, "func"), + _ => panic!("expected name"), + } + assert_eq!(args.len(), 1); + } + _ => panic!("expected function"), + } + } + + #[test] + fn test_error_double_equals() { + let err = parse_filter("x == 42").unwrap_err(); + assert!(err.contains("expected identifier or value"), "got: {err}"); + } + + #[test] + fn test_error_misplaced_keyword() { + let err = parse_filter("a : AND b c = 17").unwrap_err(); + assert!(err.contains("misplaced AND/OR/NOT"), "got: {err}"); + } +} |
