Skip to main content

zero_client/ivm/
predicate.rs

1//! Row predicates for conditions without subqueries (`createPredicate` in
2//! `packages/zql/src/builder/filter.ts`), and `transformFilters`.
3
4use super::{PipelineError, Row, identical};
5use crate::ast::{Condition, SimpleOperator, ValuePosition, json_value_at};
6use crate::compare;
7use crate::json::{Value, number};
8use crate::like::LikePattern;
9use crate::query::simplify_condition;
10use std::cell::Cell;
11use std::cmp::Ordering;
12use std::rc::Rc;
13
14/// Whether a row passes a filter.
15pub type RowPredicate = Rc<dyn Fn(&Row) -> bool>;
16
17type ValuePredicate = Rc<dyn Fn(&Value) -> bool>;
18
19/// `createPredicate(condition)` for a condition without subqueries.
20pub fn create_predicate(condition: &Condition) -> Result<RowPredicate, PipelineError> {
21    match condition {
22        Condition::And(conditions) => {
23            let predicates = conditions
24                .iter()
25                .map(create_predicate)
26                .collect::<Result<Vec<_>, _>>()?;
27            Ok(Rc::new(move |row| predicates.iter().all(|p| p(row))))
28        }
29        Condition::Or(conditions) => {
30            let predicates = conditions
31                .iter()
32                .map(create_predicate)
33                .collect::<Result<Vec<_>, _>>()?;
34            Ok(Rc::new(move |row| predicates.iter().any(|p| p(row))))
35        }
36        Condition::CorrelatedSubquery { .. } => Err(PipelineError::new(
37            "createPredicate: unexpected correlated subquery",
38        )),
39        Condition::Simple { op, left, right } => simple_predicate(*op, left, right),
40    }
41}
42
43fn unresolved_static() -> PipelineError {
44    PipelineError::new("static values should be resolved before creating predicates")
45}
46
47fn simple_predicate(
48    op: SimpleOperator,
49    left: &ValuePosition,
50    right: &ValuePosition,
51) -> Result<RowPredicate, PipelineError> {
52    let rhs = match right {
53        ValuePosition::Literal(v) => v.clone(),
54        ValuePosition::Static { .. } => return Err(unresolved_static()),
55        _ => {
56            return Err(PipelineError::new(
57                "createPredicate: right side must be a literal",
58            ));
59        }
60    };
61    if let ValuePosition::Static { .. } = left {
62        return Err(unresolved_static());
63    }
64    if matches!(op, SimpleOperator::Is | SimpleOperator::IsNot) {
65        let is_not = op == SimpleOperator::IsNot;
66        let rhs = Some(rhs);
67        return Ok(match left {
68            ValuePosition::Literal(l) => {
69                let result = identical(Some(l), rhs.as_ref()) != is_not;
70                Rc::new(move |_| result)
71            }
72            ValuePosition::Json { column, path } => {
73                let (column, path, hint) = (column.clone(), path.clone(), Cell::new(0));
74                Rc::new(move |row| {
75                    let v = json_value_at(&path, row.get_hinted(&column, &hint));
76                    identical(Some(v), rhs.as_ref()) != is_not
77                })
78            }
79            ValuePosition::Column(name) => {
80                let (name, hint) = (name.clone(), Cell::new(0));
81                Rc::new(move |row| identical(row.get_hinted(&name, &hint), rhs.as_ref()) != is_not)
82            }
83            ValuePosition::Static { .. } => unreachable!("checked above"),
84        });
85    }
86    if rhs.is_null() {
87        return Ok(Rc::new(|_| false));
88    }
89    let imp = predicate_impl(&rhs, op)?;
90    Ok(match left {
91        ValuePosition::Literal(l) => {
92            let result = !l.is_null() && imp(l);
93            Rc::new(move |_| result)
94        }
95        ValuePosition::Json { column, path } => {
96            // A JSON leaf is dynamically typed, so the comparison is
97            // type-strict: a leaf of another type than the literal's is a
98            // non-match, or a match for a negated operator, and never an
99            // error. LIKE compares text.
100            use SimpleOperator::*;
101            let required = match op {
102                Like | NotLike | Ilike | NotIlike => Some("string"),
103                _ => match rhs.as_array().and_then(|a| a.first()).unwrap_or(&rhs) {
104                    Value::String(_) => Some("string"),
105                    Value::Number(_) => Some("number"),
106                    Value::Bool(_) => Some("boolean"),
107                    _ => None,
108                },
109            };
110            let negated = matches!(op, Ne | NotLike | NotIlike | NotIn);
111            let (column, path, hint) = (column.clone(), path.clone(), Cell::new(0));
112            Rc::new(move |row| {
113                let lhs = json_value_at(&path, row.get_hinted(&column, &hint));
114                if lhs.is_null() {
115                    return false;
116                }
117                match required {
118                    Some(t) if lhs.type_name() == t => imp(lhs),
119                    _ => negated,
120                }
121            })
122        }
123        ValuePosition::Column(name) => {
124            let (name, hint) = (name.clone(), Cell::new(0));
125            Rc::new(move |row| match row.get_hinted(&name, &hint) {
126                None | Some(Value::Null) => false,
127                Some(lhs) => imp(lhs),
128            })
129        }
130        ValuePosition::Static { .. } => unreachable!("checked above"),
131    })
132}
133
134fn is_nan(v: &Value) -> bool {
135    matches!(v, Value::Number(n) if n.is_nan())
136}
137
138/// `createPredicateImpl`: `lhs` and `rhs` are not null.
139fn predicate_impl(rhs: &Value, op: SimpleOperator) -> Result<ValuePredicate, PipelineError> {
140    use SimpleOperator::*;
141    let r = rhs.clone();
142    let cmp = move |l: &Value| compare::compare(l, &r);
143    Ok(match op {
144        Eq => {
145            let r = rhs.clone();
146            Rc::new(move |l| identical(Some(l), Some(&r)))
147        }
148        Ne => {
149            let r = rhs.clone();
150            Rc::new(move |l| !identical(Some(l), Some(&r)))
151        }
152        // compareValues orders strings by UTF-8, matching ORDER BY and SQLite.
153        Lt => Rc::new(move |l| cmp(l) == Ordering::Less),
154        Gt => Rc::new(move |l| cmp(l) == Ordering::Greater),
155        // `compare` orders NaN as equal to every number; JS's `a - b` is NaN,
156        // and NaN <= 0 and NaN >= 0 are false.
157        Le => {
158            let nan = is_nan(rhs);
159            Rc::new(move |l| !nan && !is_nan(l) && cmp(l) != Ordering::Greater)
160        }
161        Ge => {
162            let nan = is_nan(rhs);
163            Rc::new(move |l| !nan && !is_nan(l) && cmp(l) != Ordering::Less)
164        }
165        Like | Ilike | NotLike | NotIlike => {
166            let p = like_predicate(rhs, matches!(op, Ilike | NotIlike))?;
167            if matches!(op, NotLike | NotIlike) {
168                Rc::new(move |l| !p(l))
169            } else {
170                p
171            }
172        }
173        In | NotIn => {
174            let Value::Array(values) = rhs else {
175                return Err(PipelineError::new(format!(
176                    "Expected rhs to be an array for {} operator",
177                    op.as_str()
178                )));
179            };
180            let values = values.clone();
181            let is_in = op == In;
182            Rc::new(move |l| same_value_zero_contains(&values, l) == is_in)
183        }
184        Is | IsNot => unreachable!("handled by create_predicate"),
185    })
186}
187
188/// `new Set(values).has(lhs)`: SameValueZero, arrays and objects by
189/// reference (so never).
190fn same_value_zero_contains(values: &[Value], lhs: &Value) -> bool {
191    match lhs {
192        Value::Array(_) | Value::Object(_) => false,
193        Value::Number(n) if n.is_nan() => values.iter().any(is_nan),
194        _ => values.iter().any(|v| identical(Some(v), Some(lhs))),
195    }
196}
197
198/// `getLikePredicate(pattern, flags)`. JS converts the pattern with
199/// `String()` and throws on a non-string left side; Rust treats that as no
200/// match.
201fn like_predicate(
202    pattern: &Value,
203    case_insensitive: bool,
204) -> Result<ValuePredicate, PipelineError> {
205    let like = LikePattern::new(&js_string(pattern), case_insensitive)
206        .map_err(|e| PipelineError::new(e.to_string()))?;
207    Ok(Rc::new(move |l| match l {
208        Value::String(s) => like.matches(s),
209        _ => false,
210    }))
211}
212
213/// JS `String(value)` for JSON values.
214pub fn js_string(v: &Value) -> String {
215    match v {
216        Value::Null => "null".to_owned(),
217        Value::Bool(b) => b.to_string(),
218        Value::Number(n) => number::format(*n),
219        Value::String(s) => s.clone(),
220        Value::Array(a) => a
221            .iter()
222            .map(|e| {
223                if e.is_null() {
224                    String::new()
225                } else {
226                    js_string(e)
227                }
228            })
229            .collect::<Vec<_>>()
230            .join(","),
231        Value::Object(_) => "[object Object]".to_owned(),
232    }
233}
234
235/// `transformFilters`: a condition without subqueries that matches a
236/// superset of the rows `filters` matches, and whether anything was
237/// removed.
238pub fn transform_filters(filters: Option<&Condition>) -> (Option<Condition>, bool) {
239    let Some(filters) = filters else {
240        return (None, false);
241    };
242    let (is_or, conditions) = match filters {
243        Condition::Simple { .. } => return (Some(filters.clone()), false),
244        Condition::CorrelatedSubquery { .. } => return (None, true),
245        Condition::And(c) => (false, c),
246        Condition::Or(c) => (true, c),
247    };
248    let mut transformed = Vec::new();
249    let mut removed = false;
250    for c in conditions {
251        let (f, r) = transform_filters(Some(c));
252        // If any branch of an OR ends up empty, the whole OR goes.
253        if f.is_none() && is_or {
254            return (None, true);
255        }
256        removed |= r;
257        transformed.extend(f);
258    }
259    let c = if is_or {
260        Condition::Or(transformed)
261    } else {
262        Condition::And(transformed)
263    };
264    (Some(simplify_condition(c)), removed)
265}