rindle/predicate.rs
1//! Spec `07` §4 — the compiled `where` **leaf predicate**: a [`ColId`]-addressed,
2//! string-free gate evaluated per row on the hot path.
3//!
4//! The boolean *structure* of a `where` (AND / OR / NOT) is **not** here — it is
5//! realized in the **Filter sub-graph** (one [`Filter`](crate::graph) link per
6//! leaf for AND, `FanOut`/`FanIn` for OR; specs `06`/`07`). A
7//! [`CompiledPredicate`] is therefore exactly one **leaf** condition: `col <cmp>
8//! value`, `col IN set`, `col LIKE pattern`, or `col IS [NOT] literal`. The builder
9//! (`08`) lowers each AST simple-condition — resolving the column *name* to a
10//! [`ColId`] against the `Schema` — into one of these.
11//!
12//! This is the **shared** predicate layer: the `Filter` operator (`07` §3) and any
13//! membership gate consume it, so the comparator choices (the three-way split in
14//! [`crate::value`]: [`compare_values`](crate::value::compare_values) for ordering, [`values_identical`] for
15//! `=`/`!=`/`IN`, never [`values_equal`](crate::value::values_equal) — `07` §8.1)
16//! are made **once, here**, not reinvented per operator. It replaces the spike's
17//! 2-variant `FilterPred` (`graph.rs`), which used the wrong (`values_equal`)
18//! comparator for `=`.
19
20use crate::value::{values_identical, ColId, OwnedRow, OwnedValue, Value};
21use std::cmp::Ordering;
22
23/// A scalar comparison operator (`07` §4.1). Ordering ops (`Lt`/`Le`/`Gt`/`Ge`)
24/// evaluate via [`compare_values`](crate::value::compare_values); `Eq`/`Ne` via [`values_identical`] (the
25/// predicate identity comparator, null≡null).
26#[derive(Clone, Copy, PartialEq, Eq, Debug)]
27pub enum CmpOp {
28 Eq,
29 Ne,
30 Lt,
31 Le,
32 Gt,
33 Ge,
34}
35
36/// One compiled leaf condition (`07` §4.1). Built once by the builder, evaluated
37/// per row with no name lookup. AND/OR/NOT live in the Filter sub-graph, so this
38/// is deliberately *flat* — no recursive `And`/`Or` variant.
39pub enum CompiledPredicate {
40 /// `col <op> value`. A NULL cell drops the row (SQL `UNKNOWN`) for every op.
41 /// Non-null `Eq`/`Ne` use [`values_identical`]; the ordering ops use
42 /// [`compare_values`](crate::value::compare_values).
43 Cmp {
44 col: ColId,
45 op: CmpOp,
46 value: OwnedValue,
47 },
48 /// `col IN (set)` (or `NOT IN` when `negated`). A NULL cell drops the row (even
49 /// for `NOT IN`). Membership via [`values_identical`] ([`ValueSet::contains`]).
50 In {
51 col: ColId,
52 set: ValueSet,
53 negated: bool,
54 },
55 /// `col LIKE pattern` / `col ILIKE pattern` (or the negated forms). Non-text
56 /// cells (incl. `null`) never match (so `NOT LIKE` on a null is still `false`
57 /// — SQL's three-valued `UNKNOWN`, collapsed to "drop").
58 Like {
59 col: ColId,
60 matcher: LikeMatcher,
61 negated: bool,
62 },
63 /// `col IS literal` (or `IS NOT` when `negated`). Identity equality, including
64 /// null (`null IS null` is true).
65 Is {
66 col: ColId,
67 value: OwnedValue,
68 negated: bool,
69 },
70 /// Fast path for `col IS NULL` (or `IS NOT NULL` when `negated`).
71 IsNull { col: ColId, negated: bool },
72 /// A constant, independent of the row — the builder folds a literal-only
73 /// condition (`5 = 5`) or any non-`IS` `col <op> NULL` (always false) to this
74 /// (`08`; `filter.ts:69,76,82,85`).
75 Const(bool),
76}
77
78impl CompiledPredicate {
79 /// Evaluate against one owned row. Index-addressed; no allocation. Cells are
80 /// borrowed via `as_ref()` and fed to the appropriate comparator.
81 ///
82 /// **Null handling (the SQL three-valued rule).** Except for [`IsNull`] — which
83 /// inspects null-ness directly — a NULL cell makes the comparison `UNKNOWN`, so
84 /// the row is dropped (`false`) for **every** operator, including the negated
85 /// ones (`!=` / `NOT IN` / `NOT LIKE`). This mirrors the JS `createPredicate`
86 /// LHS null guard (`filter.ts:88-94`). The builder never produces a `Cmp`/`In`/
87 /// `Like` over a NULL literal (those fold to `Const(false)`), so only the *cell*
88 /// can be null here.
89 ///
90 /// [`IsNull`]: CompiledPredicate::IsNull
91 pub fn eval(&self, row: &OwnedRow) -> bool {
92 match self {
93 CompiledPredicate::Const(b) => *b,
94 CompiledPredicate::Is {
95 col,
96 value,
97 negated,
98 } => values_identical(row.col(*col), value.as_ref()) ^ negated,
99 CompiledPredicate::IsNull { col, negated } => row.col(*col).is_null() ^ negated,
100 CompiledPredicate::Cmp { col, op, value } => {
101 let cell = row.col(*col);
102 if cell.is_null() {
103 return false;
104 }
105 let v = value.as_ref();
106 match op {
107 CmpOp::Eq => values_identical(cell, v),
108 CmpOp::Ne => !values_identical(cell, v),
109 // Ordering ops: a null RHS has no order vs the (non-null) cell
110 // (SQL `UNKNOWN`); guard it out rather than letting
111 // `compare_values`'s null-is-least order leak in. In practice the
112 // builder folds a null RHS to `Const(false)`, so this is belt-
113 // and-suspenders (`07` §3.1: ordering predicates are non-null).
114 CmpOp::Lt | CmpOp::Le | CmpOp::Gt | CmpOp::Ge => {
115 if v.is_null() {
116 return false;
117 }
118 let ord = compare_predicate_values(cell, v);
119 matches!(
120 (op, ord),
121 (CmpOp::Lt, Ordering::Less)
122 | (CmpOp::Le, Ordering::Less | Ordering::Equal)
123 | (CmpOp::Gt, Ordering::Greater)
124 | (CmpOp::Ge, Ordering::Greater | Ordering::Equal)
125 )
126 }
127 }
128 }
129 CompiledPredicate::In { col, set, negated } => {
130 let cell = row.col(*col);
131 if cell.is_null() {
132 return false;
133 }
134 set.contains(cell) ^ negated
135 }
136 CompiledPredicate::Like {
137 col,
138 matcher,
139 negated,
140 } => {
141 let cell = row.col(*col);
142 if cell.is_null() {
143 return false;
144 }
145 let hit = match cell {
146 Value::Str(b) | Value::Json(b) => matcher.matches(b),
147 _ => false, // non-text never matches
148 };
149 hit ^ negated
150 }
151 }
152 }
153}
154
155/// Ordering comparator for the predicate path (`<`/`<=`/`>`/`>=`). Like
156/// [`compare_values`](crate::value::compare_values) but **never panics on a cross-type pair** — a `where` filter
157/// must not crash the pipeline on a literal/column type mismatch (`07` §8.1; the
158/// `values.rs` doc-contract). Numeric `Int`/`Float` compare EXACTLY (design 226
159/// §5.1, `compare_int_f64` — all 64 bits significant, no f64 widening); a genuinely
160/// incomparable pair (e.g. string vs number) orders by a stable
161/// type rank, so a range op is total and an equality over mismatched types is false.
162/// (WS02.4 — this replaces the former `_ => compare_values` panic fallthrough.)
163///
164/// `pub(crate)` so the push-guard reverse index (`push_index::GuardKey`)
165/// can key a `BTreeMap` with the SAME total order the `=`/`IN` predicate identity
166/// (`values_identical`) uses — coarser-than-identical is safe (a false-positive
167/// candidate re-checks the exact predicate), finer would drop a delta.
168pub(crate) fn compare_predicate_values(a: Value<'_>, b: Value<'_>) -> Ordering {
169 use Value::*;
170 match (a, b) {
171 // `Absent` < everything (mirrors `compare_values`); never met on a predicate
172 // column in practice (presence-required), but kept total here.
173 (Absent, Absent) => Ordering::Equal,
174 (Absent, _) => Ordering::Less,
175 (_, Absent) => Ordering::Greater,
176 (Null, Null) => Ordering::Equal,
177 (Null, _) => Ordering::Less,
178 (_, Null) => Ordering::Greater,
179 (Int(x), Float(y)) => crate::value::compare_int_f64(x, y),
180 (Float(x), Int(y)) => crate::value::compare_int_f64(y, x).reverse(),
181 (Bool(x), Bool(y)) => x.cmp(&y),
182 (Int(x), Int(y)) => x.cmp(&y),
183 (Float(x), Float(y)) => x.total_cmp(&y),
184 (Str(x), Str(y)) => x.cmp(y),
185 (Json(x), Json(y)) => x.cmp(y),
186 _ => predicate_type_rank(a).cmp(&predicate_type_rank(b)),
187 }
188}
189
190/// Stable type ordering for incomparable cross-type predicate operands (numerics
191/// share a rank so `Int`/`Float` never reach here as a mismatch).
192fn predicate_type_rank(v: Value<'_>) -> u8 {
193 match v {
194 Value::Absent => 0,
195 Value::Null => 1,
196 Value::Bool(_) => 2,
197 Value::Int(_) | Value::Float(_) => 3,
198 Value::Str(_) => 4,
199 Value::Json(_) => 5,
200 }
201}
202
203// ---------------------------------------------------------------------------
204// ValueSet — the `IN (...)` membership set
205// ---------------------------------------------------------------------------
206
207/// The right-hand side of an `IN`. A small owned set; membership is
208/// [`values_identical`] (null≡null, the predicate comparator). Backed by a `Vec`
209/// with a linear scan — `IN` lists are typically short, and a hashed/sorted form
210/// is a measured optimization deferred until profiling shows it matters (`07`
211/// OQ on `ValueSet` representation).
212pub struct ValueSet {
213 values: Vec<OwnedValue>,
214}
215
216impl ValueSet {
217 pub fn new(values: Vec<OwnedValue>) -> ValueSet {
218 ValueSet { values }
219 }
220
221 /// True if `needle` is identical to some member (`values_identical`).
222 pub fn contains(&self, needle: Value<'_>) -> bool {
223 self.values
224 .iter()
225 .any(|v| values_identical(v.as_ref(), needle))
226 }
227
228 pub fn len(&self) -> usize {
229 self.values.len()
230 }
231
232 pub fn is_empty(&self) -> bool {
233 self.values.is_empty()
234 }
235}
236
237// ---------------------------------------------------------------------------
238// LikeMatcher — compiled SQL `LIKE` pattern
239// ---------------------------------------------------------------------------
240
241/// One token of a compiled `LIKE` pattern.
242#[derive(Clone, PartialEq, Eq, Debug)]
243enum LikeTok {
244 /// A run of literal bytes that must match exactly.
245 Lit(Box<[u8]>),
246 /// `_` — exactly one byte.
247 One,
248 /// `%` — any run of bytes (including empty).
249 Any,
250}
251
252/// A compiled SQL `LIKE` pattern (`07` §4 / `filter.ts`). `%` matches any byte
253/// run, `_` matches exactly one byte. Compiled once (the builder lowers the
254/// literal pattern) and matched per row with a classic backtracking glob walk.
255///
256/// **Collation / escape policy (WS05.1):**
257/// - **`\` escape** is honoured, matching the SQL the builder emits (`ESCAPE '\'`):
258/// `\%`/`\_`/`\\` are the literal `%`/`_`/`\`. So memory and SQLite agree for
259/// patterns that escape a wildcard.
260/// - **Case-sensitive `LIKE`** is byte-level; the SQLite leaf sets `PRAGMA
261/// case_sensitive_like = ON` so its bare `LIKE` agrees (both case-sensitive).
262/// - **`ILIKE`** folds ASCII-only (`eq_ignore_ascii_case`), which matches the
263/// bundled SQLite's `lower()` (no ICU) — so memory and SQLite agree on ASCII.
264/// **Non-ASCII case folding is a documented limitation** (both leave non-ASCII
265/// bytes unfolded); revisit only if a corpus needs Unicode `ILIKE`.
266/// - `_` is **byte-level**, not UTF-8-character-level (a deferred edge for non-ASCII
267/// single-char matches; the byte glob structure is correct and tested).
268pub struct LikeMatcher {
269 toks: Box<[LikeTok]>,
270 case_insensitive: bool,
271}
272
273impl LikeMatcher {
274 /// Compile a `LIKE` pattern. Adjacent literal bytes coalesce into one `Lit`
275 /// run; runs of `%` collapse to a single `Any`.
276 pub fn compile(pattern: &[u8]) -> LikeMatcher {
277 LikeMatcher::compile_with_case(pattern, false)
278 }
279
280 /// Compile a case-insensitive `LIKE` pattern (`ILIKE`).
281 pub fn compile_case_insensitive(pattern: &[u8]) -> LikeMatcher {
282 LikeMatcher::compile_with_case(pattern, true)
283 }
284
285 fn compile_with_case(pattern: &[u8], case_insensitive: bool) -> LikeMatcher {
286 let mut toks: Vec<LikeTok> = Vec::new();
287 let mut lit: Vec<u8> = Vec::new();
288 let flush = |lit: &mut Vec<u8>, toks: &mut Vec<LikeTok>| {
289 if !lit.is_empty() {
290 toks.push(LikeTok::Lit(std::mem::take(lit).into_boxed_slice()));
291 }
292 };
293 // Honour the `\` escape, matching the SQL the builder emits (`ESCAPE '\'`,
294 // `query_builder.rs`) and Postgres/SQLite semantics (WS05.1): `\%`/`\_`/`\\`
295 // are the literal `%`/`_`/`\`. An escaped wildcard goes into the `Lit` run, so
296 // it never becomes `Any`/`One` and never collapses with an adjacent real `%`.
297 let mut i = 0;
298 while i < pattern.len() {
299 let b = pattern[i];
300 match b {
301 b'\\' => match pattern.get(i + 1) {
302 Some(&n @ (b'%' | b'_' | b'\\')) => {
303 lit.push(n);
304 i += 2;
305 }
306 // `\x` for any other `x`: SQLite leaves this undefined; be lenient
307 // and keep both bytes literal.
308 Some(&n) => {
309 lit.push(b'\\');
310 lit.push(n);
311 i += 2;
312 }
313 // A trailing `\` is a literal backslash.
314 None => {
315 lit.push(b'\\');
316 i += 1;
317 }
318 },
319 b'%' => {
320 flush(&mut lit, &mut toks);
321 // Collapse `%%`→`%`.
322 if toks.last() != Some(&LikeTok::Any) {
323 toks.push(LikeTok::Any);
324 }
325 i += 1;
326 }
327 b'_' => {
328 flush(&mut lit, &mut toks);
329 toks.push(LikeTok::One);
330 i += 1;
331 }
332 other => {
333 lit.push(other);
334 i += 1;
335 }
336 }
337 }
338 flush(&mut lit, &mut toks);
339 LikeMatcher {
340 toks: toks.into_boxed_slice(),
341 case_insensitive,
342 }
343 }
344
345 fn lit_matches(&self, text: &[u8], start: usize, run: &[u8]) -> bool {
346 let end = start.saturating_add(run.len());
347 if end > text.len() {
348 return false;
349 }
350 if self.case_insensitive {
351 text[start..end].eq_ignore_ascii_case(run)
352 } else {
353 text[start..].starts_with(run)
354 }
355 }
356
357 /// Match `text` against the compiled pattern. Backtracking glob: `Any` records
358 /// a restart point so a later mismatch can re-anchor `%` one byte further.
359 pub fn matches(&self, text: &[u8]) -> bool {
360 let toks = &self.toks;
361 let (mut ti, mut si) = (0usize, 0usize); // token / string indices
362 let mut star: Option<(usize, usize)> = None; // (token idx after %, string idx)
363
364 loop {
365 match toks.get(ti) {
366 Some(LikeTok::Lit(run)) => {
367 if self.lit_matches(text, si, run) {
368 si += run.len();
369 ti += 1;
370 } else if let Some((st, ss)) = star {
371 ti = st;
372 si = ss + 1;
373 star = Some((st, ss + 1));
374 if si > text.len() {
375 return false;
376 }
377 } else {
378 return false;
379 }
380 }
381 Some(LikeTok::One) => {
382 if si < text.len() {
383 si += 1;
384 ti += 1;
385 } else if let Some((st, ss)) = star {
386 ti = st;
387 si = ss + 1;
388 star = Some((st, ss + 1));
389 if si > text.len() {
390 return false;
391 }
392 } else {
393 return false;
394 }
395 }
396 Some(LikeTok::Any) => {
397 ti += 1;
398 star = Some((ti, si));
399 }
400 None => {
401 // Pattern exhausted: match iff string is too.
402 if si == text.len() {
403 return true;
404 } else if let Some((st, ss)) = star {
405 ti = st;
406 si = ss + 1;
407 star = Some((st, ss + 1));
408 if si > text.len() {
409 return false;
410 }
411 } else {
412 return false;
413 }
414 }
415 }
416 }
417 }
418}
419
420#[cfg(test)]
421mod tests {
422 use super::*;
423 use crate::value::owned_row;
424
425 fn row(vals: Vec<OwnedValue>) -> OwnedRow {
426 owned_row(vals)
427 }
428
429 /// Design 226 §5.1: the predicate comparator's mixed Int/Float arms are exact —
430 /// the third comparator moves in lockstep with `compare_values`/`values_identical`
431 /// (a `GuardKey` BTreeMap keys on this order, so all three must agree).
432 #[test]
433 fn predicate_mixed_numeric_arms_are_exact() {
434 use crate::value::Value;
435 use std::cmp::Ordering;
436 const TWO_53: i64 = 1 << 53;
437 // Above 2^53: distinct Ints stay distinct against the same Float.
438 assert_eq!(
439 compare_predicate_values(Value::Int(TWO_53), Value::Float(TWO_53 as f64)),
440 Ordering::Equal
441 );
442 assert_eq!(
443 compare_predicate_values(Value::Int(TWO_53 + 1), Value::Float(TWO_53 as f64)),
444 Ordering::Greater
445 );
446 assert_eq!(
447 compare_predicate_values(Value::Float(TWO_53 as f64), Value::Int(TWO_53 + 1)),
448 Ordering::Less
449 );
450 // Below 2^53 the order is the old widened order (signed zero included).
451 assert_eq!(
452 compare_predicate_values(Value::Int(0), Value::Float(-0.0)),
453 Ordering::Greater
454 );
455 assert_eq!(
456 compare_predicate_values(Value::Int(3), Value::Float(3.5)),
457 Ordering::Less
458 );
459 }
460
461 #[test]
462 fn cmp_eq_compares_non_null_and_drops_null_cells() {
463 // Filter `=`: non-null cells compare by identity; a NULL cell is SQL
464 // UNKNOWN → dropped (NOT "null = null" — that is `IS NULL`'s job).
465 let p = CompiledPredicate::Cmp {
466 col: 0,
467 op: CmpOp::Eq,
468 value: OwnedValue::Int(7),
469 };
470 assert!(p.eval(&row(vec![OwnedValue::Int(7)])));
471 assert!(!p.eval(&row(vec![OwnedValue::Int(8)])));
472 assert!(!p.eval(&row(vec![OwnedValue::Null])));
473 }
474
475 #[test]
476 fn negated_ops_drop_null_cells() {
477 // The fix: `!=` / `NOT IN` / `NOT LIKE` on a NULL cell must DROP (false),
478 // not pass — SQL three-valued UNKNOWN, matching JS `createPredicate`.
479 let ne = CompiledPredicate::Cmp {
480 col: 0,
481 op: CmpOp::Ne,
482 value: OwnedValue::Int(7),
483 };
484 assert!(ne.eval(&row(vec![OwnedValue::Int(8)]))); // 8 != 7 → true
485 assert!(!ne.eval(&row(vec![OwnedValue::Null]))); // null != 7 → UNKNOWN → drop
486
487 let not_in = CompiledPredicate::In {
488 col: 0,
489 set: ValueSet::new(vec![OwnedValue::Int(1)]),
490 negated: true,
491 };
492 assert!(not_in.eval(&row(vec![OwnedValue::Int(2)])));
493 assert!(!not_in.eval(&row(vec![OwnedValue::Null])));
494
495 let not_like = CompiledPredicate::Like {
496 col: 0,
497 matcher: LikeMatcher::compile(b"x%"),
498 negated: true,
499 };
500 assert!(not_like.eval(&row(vec![OwnedValue::str("yz")]))); // not like "x%" → true
501 assert!(!not_like.eval(&row(vec![OwnedValue::Null]))); // null → drop
502 }
503
504 #[test]
505 fn const_is_row_independent() {
506 assert!(CompiledPredicate::Const(true).eval(&row(vec![OwnedValue::Null])));
507 assert!(!CompiledPredicate::Const(false).eval(&row(vec![OwnedValue::Int(1)])));
508 }
509
510 #[test]
511 fn cmp_ordering_guards_nulls() {
512 let p = CompiledPredicate::Cmp {
513 col: 0,
514 op: CmpOp::Gt,
515 value: OwnedValue::Int(5),
516 };
517 assert!(p.eval(&row(vec![OwnedValue::Int(6)])));
518 assert!(!p.eval(&row(vec![OwnedValue::Int(5)])));
519 assert!(!p.eval(&row(vec![OwnedValue::Int(4)])));
520 // null vs a real value has no order in a predicate → false, NOT "null < 5".
521 assert!(!p.eval(&row(vec![OwnedValue::Null])));
522 }
523
524 #[test]
525 fn in_and_not_in() {
526 let set = ValueSet::new(vec![OwnedValue::Int(1), OwnedValue::Int(3)]);
527 let p = CompiledPredicate::In {
528 col: 0,
529 set,
530 negated: false,
531 };
532 assert!(p.eval(&row(vec![OwnedValue::Int(1)])));
533 assert!(!p.eval(&row(vec![OwnedValue::Int(2)])));
534
535 let set = ValueSet::new(vec![OwnedValue::Int(1), OwnedValue::Int(3)]);
536 let np = CompiledPredicate::In {
537 col: 0,
538 set,
539 negated: true,
540 };
541 assert!(!np.eval(&row(vec![OwnedValue::Int(1)])));
542 assert!(np.eval(&row(vec![OwnedValue::Int(2)])));
543 }
544
545 #[test]
546 fn is_null() {
547 let p = CompiledPredicate::IsNull {
548 col: 0,
549 negated: false,
550 };
551 assert!(p.eval(&row(vec![OwnedValue::Null])));
552 assert!(!p.eval(&row(vec![OwnedValue::Int(0)])));
553 let np = CompiledPredicate::IsNull {
554 col: 0,
555 negated: true,
556 };
557 assert!(!np.eval(&row(vec![OwnedValue::Null])));
558 assert!(np.eval(&row(vec![OwnedValue::Int(0)])));
559 }
560
561 fn like(pat: &str, text: &str) -> bool {
562 LikeMatcher::compile(pat.as_bytes()).matches(text.as_bytes())
563 }
564
565 #[test]
566 fn like_glob_structure() {
567 assert!(like("abc", "abc"));
568 assert!(!like("abc", "abd"));
569 assert!(like("a%", "abcdef"));
570 assert!(like("%f", "abcdef"));
571 assert!(like("a%f", "abcdef"));
572 assert!(like("a%f", "af"));
573 assert!(!like("a%f", "afx"));
574 assert!(like("%", ""));
575 assert!(like("%%", "anything"));
576 assert!(like("a_c", "abc"));
577 assert!(!like("a_c", "ac"));
578 assert!(!like("a_c", "abbc"));
579 assert!(like("%a%b%", "xxaxxbxx"));
580 assert!(!like("%a%b%", "xxbxxaxx"));
581 // backtracking: the first `%` must give bytes back to satisfy the literal.
582 assert!(like("%abc", "zzabc"));
583 assert!(!like("%abc", "zzab"));
584 }
585
586 #[test]
587 fn like_predicate_non_text_never_matches() {
588 let p = CompiledPredicate::Like {
589 col: 0,
590 matcher: LikeMatcher::compile(b"%"),
591 negated: false,
592 };
593 // `%` matches any *text*, but a null/number cell is not text → false.
594 assert!(!p.eval(&row(vec![OwnedValue::Null])));
595 assert!(!p.eval(&row(vec![OwnedValue::Int(0)])));
596 assert!(p.eval(&row(vec![OwnedValue::str("hi")])));
597 }
598}