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