Skip to main content

rypipe_core/plan/
predicate.rs

1use super::{ExecutionPlan, FieldType};
2use rustc_hash::FxHashMap as HashMap;
3
4/// Comparison operator for column-to-column filters.
5#[derive(Clone, Copy, Debug, PartialEq, Eq)]
6pub enum CompareOp {
7    Gt,
8    Lt,
9    Ge,
10    Le,
11    Eq,
12    Ne,
13}
14
15/// Arithmetic operator for field expressions.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub enum ArithOp {
18    Add,
19    Sub,
20    Mul,
21    Div,
22}
23
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum TrimMode {
26    Both,
27    Start,
28    End,
29}
30
31impl std::str::FromStr for ArithOp {
32    type Err = ();
33    fn from_str(s: &str) -> Result<Self, Self::Err> {
34        match s {
35            "+" | "add" => Ok(ArithOp::Add),
36            "-" | "sub" => Ok(ArithOp::Sub),
37            "*" | "mul" => Ok(ArithOp::Mul),
38            "/" | "div" => Ok(ArithOp::Div),
39            _ => Err(()),
40        }
41    }
42}
43
44impl std::str::FromStr for CompareOp {
45    type Err = ();
46    fn from_str(s: &str) -> Result<Self, Self::Err> {
47        match s {
48            ">" | "gt" => Ok(CompareOp::Gt),
49            "<" | "lt" => Ok(CompareOp::Lt),
50            ">=" | "ge" => Ok(CompareOp::Ge),
51            "<=" | "le" => Ok(CompareOp::Le),
52            "==" | "eq" => Ok(CompareOp::Eq),
53            "!=" | "ne" => Ok(CompareOp::Ne),
54            _ => Err(()),
55        }
56    }
57}
58
59/// A filter predicate evaluated per-row during parsing.
60///
61// Leaf predicates (`Equal`, `NotEqual`, `Compare`, `CompareLiteral`) can be
62// composed into a tree with `And`, `Or`, and `Not`. Evaluation is recursive
63// with short-circuiting; a row is kept only if the whole tree passes.
64#[derive(Clone, Debug, PartialEq)]
65pub enum FilterPredicate {
66    /// Keep row if `field_value != value` (string comparison, per-row).
67    NotEqual { field: String, value: String },
68    /// Keep row if `field_value == value` (string comparison, per-row).
69    Equal { field: String, value: String },
70    /// Column-to-column comparison, evaluated natively per-row during
71    /// parsing with numeric promotion (Int64 vs Float64 widens).
72    Compare {
73        field_a: String,
74        op: CompareOp,
75        field_b: String,
76    },
77    /// Column-to-literal comparison with ordering. Uses typed comparison
78    /// with numeric promotion (e.g. Int64 field > Float64 literal).
79    CompareLiteral {
80        field: String,
81        op: CompareOp,
82        value: String,
83    },
84    /// Keep row if `field_value.starts_with(value)`.
85    StartsWith { field: String, value: String },
86    /// Keep row if `field_value.ends_with(value)`.
87    EndsWith { field: String, value: String },
88    /// Keep row if `field_value` is in the given set.
89    In { field: String, values: Vec<String> },
90    /// Keep row if `field_value` is not in the given set.
91    NotIn { field: String, values: Vec<String> },
92    /// Always keep or reject the row.
93    Always(bool),
94    /// Keep row if the field is falsy (None, empty string, or missing).
95    NotField { field: String },
96    /// Arithmetic compare: field <arith_op> <arith_value> <cmp_op> <cmp_value>
97    ArithmeticCompare {
98        field: String,
99        arith_op: ArithOp,
100        arith_value: f64,
101        cmp_op: CompareOp,
102        cmp_value: String,
103    },
104    /// Keep row if `field_value.strip()` satisfies the comparison.
105    Strip {
106        field: String,
107        op: CompareOp,
108        value: String,
109        mode: TrimMode,
110    },
111    /// Keep row if `field_value.to_lowercase()` satisfies the comparison.
112    Lower {
113        field: String,
114        op: CompareOp,
115        value: String,
116    },
117    /// Keep row if `field_value.to_uppercase()` satisfies the comparison.
118    Upper {
119        field: String,
120        op: CompareOp,
121        value: String,
122    },
123    /// Keep row if `field_value.replace(old, new)` satisfies the comparison.
124    Replace {
125        field: String,
126        old: String,
127        new: String,
128        op: CompareOp,
129        value: String,
130    },
131    /// Keep row if `field_value.len()` satisfies the comparison (numeric).
132    Length {
133        field: String,
134        op: CompareOp,
135        value: String,
136    },
137    /// Keep row if `field_value.contains(value)`.
138    Contains { field: String, value: String },
139    /// Keep row if the field is null or missing.
140    IsNull { field: String },
141    /// Keep row if the field is of the given type (e.g., Int64, Float64, String).
142    IsType {
143        field: String,
144        field_type: FieldType,
145    },
146    /// Keep row if `field_value` matches the regular expression.
147    Regex { field: String, re: RegexSpec },
148    /// Keep row if both sub-predicates pass. Short-circuits on the first
149    /// failure.
150    And(Box<FilterPredicate>, Box<FilterPredicate>),
151    /// Keep row if either sub-predicate passes. Short-circuits on the first
152    /// success.
153    Or(Box<FilterPredicate>, Box<FilterPredicate>),
154    /// Keep row if the sub-predicate fails.
155    Not(Box<FilterPredicate>),
156}
157
158/// A compiled regex plus its pattern. Equality and debug output use the
159/// pattern string; the compiled form is the execution representation.
160#[derive(Clone)]
161pub struct RegexSpec {
162    pub pattern: String,
163    pub compiled: regex::Regex,
164}
165
166impl RegexSpec {
167    /// Maximum compiled regex size in bytes (1 MiB). Patterns that compile
168    /// to larger automata are rejected to limit memory use and reduce ReDoS
169    /// risk.
170    const SIZE_LIMIT: usize = 1024 * 1024;
171
172    pub fn new(pattern: impl Into<String>) -> std::result::Result<Self, regex::Error> {
173        let pattern = pattern.into();
174        let compiled = regex::RegexBuilder::new(&pattern)
175            .size_limit(Self::SIZE_LIMIT)
176            .build()?;
177        Ok(Self { pattern, compiled })
178    }
179}
180
181impl std::fmt::Debug for RegexSpec {
182    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
183        f.debug_struct("RegexSpec")
184            .field("pattern", &self.pattern)
185            .finish()
186    }
187}
188
189impl PartialEq for RegexSpec {
190    fn eq(&self, other: &Self) -> bool {
191        self.pattern == other.pattern
192    }
193}
194
195impl FilterPredicate {
196    /// Combine two predicates with logical AND.
197    pub fn all(a: FilterPredicate, b: FilterPredicate) -> Self {
198        FilterPredicate::And(Box::new(a), Box::new(b))
199    }
200
201    /// Combine two predicates with logical OR.
202    pub fn any(a: FilterPredicate, b: FilterPredicate) -> Self {
203        FilterPredicate::Or(Box::new(a), Box::new(b))
204    }
205
206    /// Negate a predicate.
207    #[allow(clippy::should_implement_trait)]
208    pub fn not(inner: FilterPredicate) -> Self {
209        FilterPredicate::Not(Box::new(inner))
210    }
211}
212
213impl FilterPredicate {
214    /// Check whether a partial row passes the filter.
215    /// `columns`/`field_index` contain all builders; `row_index` is the current
216    /// row number. Returns true to keep the row.
217    ///
218    /// * `Equal`/`NotEqual` use string comparison on the stored value.
219    /// * `Compare` is evaluated natively per-row against typed values with
220    ///   numeric promotion (`Int64` vs `Float64` widens to f64); any other
221    ///   type mismatch or a null operand fails the row.
222    /// * `And`/`Or` short-circuit; `Not` negates. A missing field fails an
223    ///   inner leaf, which `Not` can flip back to a keep.
224    pub(crate) fn check(
225        &self,
226        columns: &[crate::columnar::ColumnBuilder],
227        field_index: &HashMap<String, usize>,
228        row_index: usize,
229        plan: &ExecutionPlan,
230    ) -> bool {
231        match self {
232            FilterPredicate::NotEqual { field, value } => {
233                let actual = get_value(columns, field_index, field, plan, row_index);
234                actual.as_deref() != Some(value.as_str())
235            }
236            FilterPredicate::Equal { field, value } => {
237                let actual = get_value(columns, field_index, field, plan, row_index);
238                actual.as_deref() == Some(value.as_str())
239            }
240            FilterPredicate::Compare {
241                field_a,
242                op,
243                field_b,
244            } => {
245                let va = get_column(columns, field_index, resolve(field_a, plan))
246                    .and_then(|b| b.get_typed_value(row_index));
247                let vb = get_column(columns, field_index, resolve(field_b, plan))
248                    .and_then(|b| b.get_typed_value(row_index));
249                match (va, vb) {
250                    (Some(a), Some(b)) => compare_typed(&a, *op, &b),
251                    _ => false,
252                }
253            }
254            FilterPredicate::CompareLiteral { field, op, value } => {
255                let va = get_column(columns, field_index, resolve(field, plan))
256                    .and_then(|b| b.get_typed_value(row_index));
257                if let Some(a) = va {
258                    if let Some(b) = typed_from_literal(&a, value) {
259                        return compare_typed(&a, *op, &b);
260                    }
261                }
262                false
263            }
264            FilterPredicate::StartsWith { field, value } => {
265                let actual = get_value(columns, field_index, field, plan, row_index);
266                match actual {
267                    Some(s) => s.starts_with(value.as_str()),
268                    None => false,
269                }
270            }
271            FilterPredicate::EndsWith { field, value } => {
272                let actual = get_value(columns, field_index, field, plan, row_index);
273                match actual {
274                    Some(s) => s.ends_with(value.as_str()),
275                    None => false,
276                }
277            }
278            FilterPredicate::In { field, values } => {
279                let actual = get_value(columns, field_index, field, plan, row_index);
280                match actual {
281                    Some(s) => values.contains(&s),
282                    None => false,
283                }
284            }
285            FilterPredicate::NotIn { field, values } => {
286                let actual = get_value(columns, field_index, field, plan, row_index);
287                match actual {
288                    Some(s) => !values.contains(&s),
289                    None => true,
290                }
291            }
292            FilterPredicate::Always(keep) => *keep,
293            FilterPredicate::NotField { field } => {
294                let actual = get_value(columns, field_index, field, plan, row_index);
295                match actual {
296                    Some(s) => s.is_empty(),
297                    None => true,
298                }
299            }
300            FilterPredicate::ArithmeticCompare {
301                field,
302                arith_op,
303                arith_value,
304                cmp_op,
305                cmp_value,
306            } => {
307                let actual = get_column(columns, field_index, resolve(field, plan))
308                    .and_then(|b| b.get_typed_value(row_index));
309                if let Some(a) = actual {
310                    let field_f64 = match &a {
311                        crate::columnar::TypedValue::Int64(v) => *v as f64,
312                        crate::columnar::TypedValue::Float64(v) => *v,
313                        crate::columnar::TypedValue::Decimal128(v, scale) => {
314                            *v as f64 / 10_f64.powi(*scale as i32)
315                        }
316                        crate::columnar::TypedValue::Str(s) => match s.parse::<f64>() {
317                            Ok(v) => v,
318                            Err(_) => return false,
319                        },
320                        _ => return false,
321                    };
322                    let result = match arith_op {
323                        ArithOp::Add => field_f64 + arith_value,
324                        ArithOp::Sub => field_f64 - arith_value,
325                        ArithOp::Mul => field_f64 * arith_value,
326                        ArithOp::Div => {
327                            if *arith_value == 0.0 {
328                                return false;
329                            }
330                            field_f64 / arith_value
331                        }
332                    };
333                    let cmp_f64 = match cmp_value.parse::<f64>() {
334                        Ok(v) => v,
335                        Err(_) => return false,
336                    };
337                    return apply_op(*cmp_op, result.partial_cmp(&cmp_f64));
338                }
339                false
340            }
341            FilterPredicate::Strip {
342                field,
343                op,
344                value,
345                mode,
346            } => {
347                let actual = get_value(columns, field_index, field, plan, row_index);
348                match actual {
349                    Some(s) => {
350                        let transformed = match mode {
351                            TrimMode::Both => s.trim(),
352                            TrimMode::Start => s.trim_start(),
353                            TrimMode::End => s.trim_end(),
354                        };
355                        apply_op(*op, transformed.partial_cmp(value.as_str()))
356                    }
357                    None => false,
358                }
359            }
360            FilterPredicate::Lower { field, op, value } => {
361                let actual = get_value(columns, field_index, field, plan, row_index);
362                match actual {
363                    Some(s) => {
364                        let transformed = s.to_lowercase();
365                        apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
366                    }
367                    None => false,
368                }
369            }
370            FilterPredicate::Upper { field, op, value } => {
371                let actual = get_value(columns, field_index, field, plan, row_index);
372                match actual {
373                    Some(s) => {
374                        let transformed = s.to_uppercase();
375                        apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
376                    }
377                    None => false,
378                }
379            }
380            FilterPredicate::Replace {
381                field,
382                old,
383                new,
384                op,
385                value,
386            } => {
387                let actual = get_value(columns, field_index, field, plan, row_index);
388                match actual {
389                    Some(s) => {
390                        let transformed = s.replace(old.as_str(), new.as_str());
391                        apply_op(*op, transformed.as_str().partial_cmp(value.as_str()))
392                    }
393                    None => false,
394                }
395            }
396            FilterPredicate::Length { field, op, value } => {
397                let actual = get_value(columns, field_index, field, plan, row_index);
398                match actual {
399                    Some(s) => {
400                        let len = s.chars().count() as f64;
401                        let cmp_val = match value.parse::<f64>() {
402                            Ok(v) => v,
403                            Err(_) => return false,
404                        };
405                        apply_op(*op, len.partial_cmp(&cmp_val))
406                    }
407                    None => false,
408                }
409            }
410            FilterPredicate::Contains { field, value } => {
411                let actual = get_value(columns, field_index, field, plan, row_index);
412                match actual {
413                    Some(s) => s.contains(value.as_str()),
414                    None => false,
415                }
416            }
417            FilterPredicate::IsNull { field } => {
418                let actual = get_value(columns, field_index, field, plan, row_index);
419                actual.is_none()
420            }
421            FilterPredicate::Regex { field, re } => {
422                let actual = get_value(columns, field_index, field, plan, row_index);
423                match actual {
424                    Some(s) => re.compiled.is_match(s.as_ref()),
425                    None => false,
426                }
427            }
428            FilterPredicate::IsType { field, field_type } => {
429                let resolved = resolve(field, plan);
430                let col = get_column(columns, field_index, resolved);
431                match col {
432                    None => false,
433                    Some(c) => c.is_type_at(row_index, field_type),
434                }
435            }
436            FilterPredicate::And(a, b) => {
437                // Evaluate the operand with the earlier field first for
438                // short-circuit benefit (C2: reorder by document position).
439                let (first, second) =
440                    if pred_ordinal(a, field_index, plan) <= pred_ordinal(b, field_index, plan) {
441                        (a.as_ref(), b.as_ref())
442                    } else {
443                        (b.as_ref(), a.as_ref())
444                    };
445                first.check(columns, field_index, row_index, plan)
446                    && second.check(columns, field_index, row_index, plan)
447            }
448            FilterPredicate::Or(a, b) => {
449                let (first, second) =
450                    if pred_ordinal(a, field_index, plan) <= pred_ordinal(b, field_index, plan) {
451                        (a.as_ref(), b.as_ref())
452                    } else {
453                        (b.as_ref(), a.as_ref())
454                    };
455                first.check(columns, field_index, row_index, plan)
456                    || second.check(columns, field_index, row_index, plan)
457            }
458            FilterPredicate::Not(inner) => !inner.check(columns, field_index, row_index, plan),
459        }
460    }
461}
462
463/// Resolve a filter field name to its output column name.
464fn resolve<'a>(field: &'a str, plan: &'a ExecutionPlan) -> &'a str {
465    plan.field_map.get(field).map_or(field, |s| s.as_str())
466}
467
468fn get_column<'a>(
469    columns: &'a [crate::columnar::ColumnBuilder],
470    field_index: &HashMap<String, usize>,
471    name: &str,
472) -> Option<&'a crate::columnar::ColumnBuilder> {
473    field_index.get(name).map(|&i| &columns[i])
474}
475
476/// Fetch a stored value formatted as a string for Equal/NotEqual checks.
477/// Tries zero-allocation `get_filter_view` first (String/Dict columns);
478/// falls back to `get_filter_value` for typed columns that need formatting.
479fn get_value(
480    columns: &[crate::columnar::ColumnBuilder],
481    field_index: &HashMap<String, usize>,
482    field: &str,
483    plan: &ExecutionPlan,
484    row_index: usize,
485) -> Option<String> {
486    let col = get_column(columns, field_index, resolve(field, plan))?;
487    // Fast path: borrowed &str for String/Dictionary columns (no allocation).
488    if let Some(s) = col.get_filter_view(row_index) {
489        return Some(s.to_owned());
490    }
491    // Slow path: typed columns need formatting (allocates).
492    col.get_filter_value(row_index)
493}
494
495/// Native-typed comparison with numeric promotion. Mixed Int64/Float64
496/// operands are widened to f64; equal integral types stay integral.
497/// Nulls never reach here (checked by the caller).
498fn compare_typed(
499    a: &crate::columnar::TypedValue<'_>,
500    op: CompareOp,
501    b: &crate::columnar::TypedValue<'_>,
502) -> bool {
503    use crate::columnar::TypedValue as T;
504    match (a, b) {
505        (T::Int64(x), T::Int64(y)) => apply_op(op, Some(x.cmp(y))),
506        (T::Float64(x), T::Float64(y)) => apply_op(op, x.partial_cmp(y)),
507        (T::Int64(x), T::Float64(y)) => apply_op(op, (*x as f64).partial_cmp(y)),
508        (T::Float64(x), T::Int64(y)) => apply_op(op, x.partial_cmp(&(*y as f64))),
509        (T::Decimal128(x, xs), T::Decimal128(y, ys)) => {
510            apply_op(op, Some(compare_decimal128(*x, *xs, *y, *ys)))
511        }
512        (T::Str(x), T::Str(y)) => apply_op(op, x.cmp(y).into()),
513        (T::Bool(x), T::Bool(y)) => apply_op(op, x.cmp(y).into()),
514        // Temporal types compare by their raw integer; mixed Date32/Timestamp
515        // or differing timestamp units are not comparable.
516        (T::Date32(x), T::Date32(y)) => apply_op(op, x.cmp(y).into()),
517        (T::Timestamp(x, xu), T::Timestamp(y, yu)) if xu == yu => apply_op(op, x.cmp(y).into()),
518        _ => false,
519    }
520}
521
522pub(crate) fn compare_decimal128(a: i128, a_scale: u8, b: i128, b_scale: u8) -> std::cmp::Ordering {
523    if a == 0 || b == 0 || a_scale == b_scale {
524        return a.cmp(&b);
525    }
526    let negative = a.is_negative();
527    match (negative, b.is_negative()) {
528        (true, false) => return std::cmp::Ordering::Less,
529        (false, true) => return std::cmp::Ordering::Greater,
530        _ => {}
531    }
532    let scale = a_scale.max(b_scale) as usize;
533    let a = a.unsigned_abs().to_string();
534    let b = b.unsigned_abs().to_string();
535    let a_len = a.len() + scale - a_scale as usize;
536    let b_len = b.len() + scale - b_scale as usize;
537    let order = a_len.cmp(&b_len).then_with(|| {
538        let width = a_len.max(b_len);
539        (0..width)
540            .map(|i| a.as_bytes().get(i).copied().unwrap_or(b'0'))
541            .cmp((0..width).map(|i| b.as_bytes().get(i).copied().unwrap_or(b'0')))
542    });
543    if negative {
544        order.reverse()
545    } else {
546        order
547    }
548}
549
550/// Apply an operator to an `Ordering`, treating `None` (NaN) as no-match.
551fn apply_op(op: CompareOp, ord: Option<std::cmp::Ordering>) -> bool {
552    use std::cmp::Ordering::*;
553    let Some(ord) = ord else { return false };
554    match op {
555        CompareOp::Gt => ord == Greater,
556        CompareOp::Lt => ord == Less,
557        CompareOp::Ge => ord != Less,
558        CompareOp::Le => ord != Greater,
559        CompareOp::Eq => ord == Equal,
560        CompareOp::Ne => ord != Equal,
561    }
562}
563
564/// Parse a string literal into a `TypedValue` matching the operand's type.
565/// Used by `CompareLiteral` to coerce the literal to the field's type.
566fn typed_from_literal<'a>(
567    sample: &crate::columnar::TypedValue<'a>,
568    literal: &'a str,
569) -> Option<crate::columnar::TypedValue<'a>> {
570    use crate::columnar::TypedValue as T;
571    match sample {
572        T::Str(_) => Some(T::Str(literal)),
573        T::Int64(_) => literal.parse::<i64>().ok().map(T::Int64),
574        T::Float64(_) => literal.parse::<f64>().ok().map(T::Float64),
575        T::Bool(_) => match literal {
576            "true" | "True" | "TRUE" => Some(T::Bool(true)),
577            "false" | "False" | "FALSE" => Some(T::Bool(false)),
578            _ => None,
579        },
580        T::Date32(_) => literal.parse::<i32>().ok().map(T::Date32),
581        T::Timestamp(_, unit) => literal
582            .parse::<i64>()
583            .ok()
584            .map(|value| T::Timestamp(value, *unit)),
585        T::Decimal128(_, scale) => crate::columnar::parse_decimal128(literal, *scale)
586            .map(|value| T::Decimal128(value, *scale)),
587    }
588}
589
590/// Return the minimum field ordinal for a predicate, used to order
591/// `And`/`Or` operands by document position (C2). Higher ordinal = later
592/// in the document. Returns `usize::MAX` for predicates without a
593/// resolvable field (should evaluate last).
594fn pred_ordinal(
595    pred: &FilterPredicate,
596    field_index: &HashMap<String, usize>,
597    plan: &ExecutionPlan,
598) -> usize {
599    match pred {
600        FilterPredicate::Equal { field, .. }
601        | FilterPredicate::NotEqual { field, .. }
602        | FilterPredicate::CompareLiteral { field, .. }
603        | FilterPredicate::StartsWith { field, .. }
604        | FilterPredicate::EndsWith { field, .. }
605        | FilterPredicate::In { field, .. }
606        | FilterPredicate::NotIn { field, .. }
607        | FilterPredicate::NotField { field, .. }
608        | FilterPredicate::ArithmeticCompare { field, .. }
609        | FilterPredicate::Strip { field, .. }
610        | FilterPredicate::Lower { field, .. }
611        | FilterPredicate::Upper { field, .. }
612        | FilterPredicate::Replace { field, .. }
613        | FilterPredicate::Length { field, .. }
614        | FilterPredicate::Contains { field, .. }
615        | FilterPredicate::IsNull { field, .. }
616        | FilterPredicate::IsType { field, .. }
617        | FilterPredicate::Regex { field, .. } => field_index
618            .get(resolve(field, plan))
619            .copied()
620            .unwrap_or(usize::MAX),
621        FilterPredicate::Always(_) => usize::MAX,
622        FilterPredicate::Compare {
623            field_a, field_b, ..
624        } => {
625            let a = field_index
626                .get(resolve(field_a, plan))
627                .copied()
628                .unwrap_or(usize::MAX);
629            let b = field_index
630                .get(resolve(field_b, plan))
631                .copied()
632                .unwrap_or(usize::MAX);
633            a.min(b)
634        }
635        FilterPredicate::And(a, b) | FilterPredicate::Or(a, b) => {
636            pred_ordinal(a, field_index, plan).min(pred_ordinal(b, field_index, plan))
637        }
638        FilterPredicate::Not(inner) => pred_ordinal(inner, field_index, plan),
639    }
640}