Skip to main content

day_persistence/
queries.rs

1// Copyright © The Daybrite Project
2// SPDX-License-Identifier: MPL-2.0
3
4//! Typed queries and their SQL compiler (docs/persistence.md).
5//!
6//! A predicate here is data, not a string: the same value compiles to a `WHERE` clause the
7//! engine can drive from its indexes, and names its column dependencies so a live query knows
8//! which changes can move its result at all. The engine answers every fetch (filter, sort,
9//! window, relation traversal, full-text match, spatial candidates), which is what lets a
10//! container serve a million-row table without ever holding it in memory. The change log
11//! names the column a write touched, so a write to a column the query never mentions is
12//! discarded before any SQL runs; a write the query does depend on marks it stale, and one
13//! requery after the turn's flush re-derives the id set, diffed against the old one so a list
14//! can animate the difference instead of reloading.
15
16use std::cmp::Ordering;
17use std::fmt::Write as _;
18
19use crate::{Value, ident};
20
21/// A row, as a predicate can read it: column name → stored value. Implementations answer in
22/// the column's stored language (through the field's codec), which is the language predicates
23/// encode their arguments into, so comparisons never mix representations.
24pub trait RowView {
25    fn col(&self, column: &str) -> Option<Value>;
26}
27
28/// How many related rows have to satisfy the inner predicate.
29///
30/// `All` over an empty relation is true: the vacuous reading, and the one SQL gives for
31/// `NOT EXISTS (… AND NOT p)`. It is the choice that surprises people, which is why `None`
32/// sits beside it: "no unconfirmed lodging" and "every lodging confirmed" differ exactly for
33/// the rows with nothing related, and an app usually means the former.
34#[derive(Clone, Copy, Debug, PartialEq, Eq)]
35pub enum Quant {
36    Any,
37    All,
38    None,
39    /// No related rows at all: one `NOT EXISTS` over the foreign-key index.
40    Empty,
41    /// At least `n` related rows: a correlated `COUNT` over the same index.
42    CountGe(usize),
43}
44
45/// A predicate as a value. Compiles to SQL; the fallback evaluator ([`Pred::eval`]) exists
46/// for drivers that cannot fold case exactly, and for tests.
47#[derive(Clone, Debug, PartialEq)]
48pub enum Pred {
49    Always,
50    Eq(&'static str, Value),
51    Ne(&'static str, Value),
52    Lt(&'static str, Value),
53    Le(&'static str, Value),
54    Gt(&'static str, Value),
55    Ge(&'static str, Value),
56    /// Case-sensitive substring on a `TEXT` column (SQL: `instr(col, ?) > 0`).
57    Contains(&'static str, String),
58    /// Case-insensitive substring, what a search field wants. Folds with full Unicode
59    /// lowercasing on both paths: the driver registers `day_fold` (Rust's `to_lowercase` as a
60    /// SQL function), so the SQL form selects exactly the rows the in-memory form would.
61    ContainsCi(&'static str, String),
62    /// Case-sensitive prefix. Not `LIKE`, whose SQLite default is case-insensitive for
63    /// ASCII and would quietly answer the wrong question.
64    StartsWith(&'static str, String),
65    /// Case-insensitive prefix through `day_fold`, like [`Pred::ContainsCi`].
66    StartsWithCi(&'static str, String),
67    Between(&'static str, Value, Value),
68    /// `column ∈ set`. The set is sorted and deduped at construction, so the fallback
69    /// evaluator can binary-search it.
70    In(&'static str, Vec<Value>),
71    /// `column ∉ set`, with SQL's NULL rule: a NULL column is unknown, not a match.
72    NotIn(&'static str, Vec<Value>),
73    /// The row's key ∈ set. Compiles against the key column directly.
74    IdIn(Vec<u64>),
75    /// A question about a row's relatives: "some lodging of this trip is in Kyoto".
76    /// Compiles to a correlated `EXISTS` over the relation's foreign key (or join table);
77    /// `inner` evaluates against rows of `target`, not of the query's own table. Nesting is
78    /// unlimited; each level is another subquery the engine plans.
79    Related {
80        /// The table declaring the relation, which tells two like-named fields apart.
81        owner: &'static str,
82        /// The `Many` field, or the `One` column's field name, that was crossed.
83        field: &'static str,
84        target: &'static str,
85        quant: Quant,
86        inner: Box<Pred>,
87    },
88    And(Box<Pred>, Box<Pred>),
89    Or(Box<Pred>, Box<Pred>),
90    Not(Box<Pred>),
91    /// Raw SQL the layer cannot read. The query cannot know its dependencies, so every flush
92    /// that touches the table re-runs it. That is the cost of the escape hatch.
93    Raw(String, Vec<Value>),
94    /// Full-text match (`#[model(fts(…))]`): compiles to a subquery over the FTS5 shadow.
95    /// The dependency set is the indexed columns, so the zero-cost tier survives search.
96    Matches {
97        columns: &'static [&'static str],
98        query: String,
99    },
100    /// A bounding-box test over two `REAL` columns. When the columns are the model's declared
101    /// `spatial(…)` pair, the compiler narrows through the R*Tree shadow first and re-checks
102    /// exactly (the shadow stores 32-bit floats, outward-rounded, as a candidate superset).
103    Within {
104        lat: &'static str,
105        lon: &'static str,
106        min_lat: f64,
107        max_lat: f64,
108        min_lon: f64,
109        max_lon: f64,
110    },
111}
112
113impl Pred {
114    /// The columns whose change can move a result through this predicate: local columns
115    /// only; what a predicate reads across a relation is collected by [`Pred::related_deps`].
116    #[expect(
117        clippy::match_same_arms,
118        reason = "each empty arm carries the explanation of why that predicate reads no local column"
119    )]
120    pub fn columns(&self, out: &mut Vec<&'static str>) {
121        let push = |c: &'static str, out: &mut Vec<&'static str>| {
122            if !out.contains(&c) {
123                out.push(c);
124            }
125        };
126        match self {
127            Pred::Always | Pred::Raw(..) => {}
128            Pred::Eq(c, _)
129            | Pred::Ne(c, _)
130            | Pred::Lt(c, _)
131            | Pred::Le(c, _)
132            | Pred::Gt(c, _)
133            | Pred::Ge(c, _)
134            | Pred::Contains(c, _)
135            | Pred::ContainsCi(c, _)
136            | Pred::StartsWith(c, _)
137            | Pred::StartsWithCi(c, _)
138            | Pred::In(c, _)
139            | Pred::NotIn(c, _)
140            | Pred::Between(c, _, _) => push(c, out),
141            // A row's key never changes: it can only enter or leave an id set by being
142            // inserted or deleted, which is a structural op, not a column write.
143            Pred::IdIn(_) => {}
144            // The inner predicate reads the target's columns, which are a different table's
145            // dependency; `Fetch::dependencies` collects them into `Deps::related`, and a
146            // local column write can never move a row through them. The membership itself
147            // (a foreign key rewrite, a link) is routed by the relation's own machinery.
148            Pred::Related { .. } => {}
149            Pred::And(a, b) | Pred::Or(a, b) => {
150                a.columns(out);
151                b.columns(out);
152            }
153            Pred::Not(a) => a.columns(out),
154            Pred::Matches { columns, .. } => {
155                for c in *columns {
156                    push(c, out);
157                }
158            }
159            Pred::Within { lat, lon, .. } => {
160                push(lat, out);
161                push(lon, out);
162            }
163        }
164    }
165
166    /// Collect what this predicate reads across relations, at every depth: the tables whose
167    /// changes must mark a query stale. A nested crossing's `owner` is the enclosing target,
168    /// recorded at construction, so each entry stands on its own.
169    fn related_deps(&self, out: &mut Vec<RelatedDep>) {
170        match self {
171            Pred::Related {
172                owner,
173                field,
174                target,
175                inner,
176                ..
177            } => {
178                let mut columns = Vec::new();
179                inner.columns(&mut columns);
180                out.push(RelatedDep {
181                    owner,
182                    field,
183                    target_table: target,
184                    columns,
185                });
186                inner.related_deps(out);
187            }
188            Pred::And(a, b) | Pred::Or(a, b) => {
189                a.related_deps(out);
190                b.related_deps(out);
191            }
192            Pred::Not(a) => a.related_deps(out),
193            _ => {}
194        }
195    }
196
197    /// Whether any part is raw SQL (unreadable, so every flush of the table re-queries).
198    pub fn contains_raw(&self) -> bool {
199        match self {
200            Pred::Raw(..) => true,
201            Pred::And(a, b) | Pred::Or(a, b) => a.contains_raw() || b.contains_raw(),
202            Pred::Not(a) => a.contains_raw(),
203            _ => false,
204        }
205    }
206
207    /// Whether any part folds case (`ContainsCi`/`StartsWithCi`); those need the driver's
208    /// `day_fold` function for exact SQL, or the fallback path.
209    pub(crate) fn contains_fold(&self) -> bool {
210        match self {
211            Pred::ContainsCi(..) | Pred::StartsWithCi(..) => true,
212            Pred::And(a, b) | Pred::Or(a, b) => a.contains_fold() || b.contains_fold(),
213            Pred::Not(a) => a.contains_fold(),
214            Pred::Related { inner, .. } => inner.contains_fold(),
215            _ => false,
216        }
217    }
218
219    /// Whether any part crosses a relation.
220    pub(crate) fn contains_related(&self) -> bool {
221        match self {
222            Pred::Related { .. } => true,
223            Pred::And(a, b) | Pred::Or(a, b) => a.contains_related() || b.contains_related(),
224            Pred::Not(a) => a.contains_related(),
225            _ => false,
226        }
227    }
228
229    /// Whether this row matches, in the WHERE-clause reading: unknown is not a match. This is
230    /// the fallback evaluator; the SQL compiler is the primary path, and this answers for
231    /// drivers without `day_fold` (over the row's own columns; relation crossings are refused
232    /// upstream) and for unit tests. `Raw` and `Matches` answer true here: on the fallback
233    /// path they have already filtered in SQL.
234    pub fn eval(&self, key: u64, row: &dyn RowView) -> bool {
235        self.eval3(key, row) == Some(true)
236    }
237
238    /// [`Pred::eval`], three-valued: SQL's logic, which is the only way this path and the SQL
239    /// path can agree about NULL.
240    ///
241    /// A comparison against a NULL column is unknown (`None`), not false: SQL's `notes <> 'x'`
242    /// does not select rows whose `notes` is NULL, and neither does this. `Eq`/`Ne` against a
243    /// `Null` literal keep their `IS NULL` / `IS NOT NULL` meaning and are always definite.
244    #[expect(
245        clippy::match_same_arms,
246        reason = "each constant arm carries the explanation of why that predicate is not evaluated here"
247    )]
248    pub fn eval3(&self, key: u64, row: &dyn RowView) -> Option<bool> {
249        match self {
250            Pred::Always => Some(true),
251            // Already answered in SQL on every path that reaches an evaluator.
252            Pred::Raw(..) | Pred::Matches { .. } => Some(true),
253            // Refused before evaluation (the compiler either answers it in SQL or errors);
254            // a constant keeps the match total without inventing an answer.
255            Pred::Related { .. } => Some(true),
256
257            // `IS NULL` / `IS NOT NULL`: definite, even about NULL.
258            Pred::Eq(c, Value::Null) => Some(matches!(row.col(c), Some(Value::Null) | None)),
259            Pred::Ne(c, Value::Null) => Some(!matches!(row.col(c), Some(Value::Null) | None)),
260
261            Pred::Eq(c, v) => defined(row.col(c)).map(|a| a == *v),
262            Pred::Ne(c, v) => defined(row.col(c)).map(|a| a != *v),
263            Pred::Lt(c, v) => defined(row.col(c)).map(|a| compare_values(&a, v) == Ordering::Less),
264            Pred::Le(c, v) => {
265                defined(row.col(c)).map(|a| compare_values(&a, v) != Ordering::Greater)
266            }
267            Pred::Gt(c, v) => {
268                defined(row.col(c)).map(|a| compare_values(&a, v) == Ordering::Greater)
269            }
270            Pred::Ge(c, v) => defined(row.col(c)).map(|a| compare_values(&a, v) != Ordering::Less),
271            Pred::Between(c, lo, hi) => defined(row.col(c)).map(|a| {
272                compare_values(&a, lo) != Ordering::Less
273                    && compare_values(&a, hi) != Ordering::Greater
274            }),
275
276            Pred::Contains(c, needle) => text(row.col(c)).map(|t| t.contains(needle.as_str())),
277            Pred::ContainsCi(c, needle) => {
278                text(row.col(c)).map(|t| t.to_lowercase().contains(&needle.to_lowercase()))
279            }
280            Pred::StartsWith(c, prefix) => text(row.col(c)).map(|t| t.starts_with(prefix.as_str())),
281            Pred::StartsWithCi(c, prefix) => {
282                text(row.col(c)).map(|t| t.to_lowercase().starts_with(&prefix.to_lowercase()))
283            }
284
285            Pred::In(c, set) => defined(row.col(c)).map(|a| in_set(set, &a)),
286            Pred::NotIn(c, set) => defined(row.col(c)).map(|a| !in_set(set, &a)),
287            // The key is always present and never NULL, so membership is definite.
288            Pred::IdIn(ids) => Some(ids.binary_search(&key).is_ok()),
289
290            // Kleene logic, so unknown propagates exactly as SQL propagates it.
291            Pred::And(a, b) => match (a.eval3(key, row), b.eval3(key, row)) {
292                (Some(false), _) | (_, Some(false)) => Some(false),
293                (Some(true), Some(true)) => Some(true),
294                _ => None,
295            },
296            Pred::Or(a, b) => match (a.eval3(key, row), b.eval3(key, row)) {
297                (Some(true), _) | (_, Some(true)) => Some(true),
298                (Some(false), Some(false)) => Some(false),
299                _ => None,
300            },
301            Pred::Not(a) => a.eval3(key, row).map(|v| !v),
302
303            Pred::Within {
304                lat,
305                lon,
306                min_lat,
307                max_lat,
308                min_lon,
309                max_lon,
310            } => {
311                let in_range = |c: &str, lo: f64, hi: f64| match defined(row.col(c)) {
312                    Some(Value::Real(v)) => Some(v >= lo && v <= hi),
313                    Some(Value::Int(v)) => Some((v as f64) >= lo && (v as f64) <= hi),
314                    Some(_) => Some(false),
315                    None => None,
316                };
317                match (
318                    in_range(lat, *min_lat, *max_lat),
319                    in_range(lon, *min_lon, *max_lon),
320                ) {
321                    (Some(false), _) | (_, Some(false)) => Some(false),
322                    (Some(true), Some(true)) => Some(true),
323                    _ => None,
324                }
325            }
326        }
327    }
328}
329
330impl std::ops::BitAnd for Pred {
331    type Output = Pred;
332    fn bitand(self, rhs: Pred) -> Pred {
333        Pred::And(Box::new(self), Box::new(rhs))
334    }
335}
336
337impl std::ops::BitOr for Pred {
338    type Output = Pred;
339    fn bitor(self, rhs: Pred) -> Pred {
340        Pred::Or(Box::new(self), Box::new(rhs))
341    }
342}
343
344impl std::ops::Not for Pred {
345    type Output = Pred;
346    fn not(self) -> Pred {
347        Pred::Not(Box::new(self))
348    }
349}
350
351// ---------------------------------------------------------------------------
352// The SQL compiler
353// ---------------------------------------------------------------------------
354
355/// One relation crossing, as SQL needs it, resolved by the container from its wired
356/// relations when a fetch compiles.
357#[derive(Clone, Debug)]
358pub(crate) enum RelSql {
359    /// The owner is the parent (a `Many` field): its children are the target rows whose
360    /// foreign-key column names the owner's key.
361    Children {
362        target_key: String,
363        fk_col: String,
364        owner_key: String,
365    },
366    /// The owner is the child (a `One` column): the target is the one row its foreign key
367    /// names.
368    Referent { target_key: String, fk_col: String },
369    /// A many-to-many: membership lives in the join table, one column per side.
370    Join {
371        join_table: String,
372        owner_col: String,
373        target_col: String,
374        owner_key: String,
375        target_key: String,
376    },
377    /// A link by value (`#[model(link(…))]`): target rows whose `remote_col` equals the
378    /// owner's `local_col`; no key on either side is involved, which is what lets it cross
379    /// into an attached database.
380    Linked {
381        local_col: String,
382        remote_col: String,
383        target_key: String,
384    },
385}
386
387/// What the compiler asks the container: how names resolve to SQL. Implemented over the wired
388/// relations and attached tables.
389pub(crate) trait SqlIndex {
390    /// Resolve `owner.field` to its wired SQL shape; `None` fails the compile, loudly.
391    fn relation(&self, owner: &str, field: &str) -> Option<RelSql>;
392    /// The key column of `table`, as a plain name.
393    fn key_of(&self, table: &str) -> Option<String>;
394    /// `table` as a statement names it: quoted, schema-qualified when attached.
395    fn table_sql(&self, table: &str) -> String;
396    /// The FTS5 shadow table of `table`, when the model declares `fts(…)`.
397    fn fts_of(&self, table: &str) -> Option<FtsSql>;
398    fn fts_key_of(&self, _table: &str) -> &'static str {
399        "rowid"
400    }
401    /// The R*Tree shadow of `table`, quoted, when `lat`/`lon` are its declared `spatial(…)`
402    /// pair.
403    fn geo_of(&self, table: &str, lat: &str, lon: &str) -> Option<String>;
404    /// Whether the connection has `day_fold` registered (exact Unicode case folding in SQL).
405    fn unicode_fold(&self) -> bool;
406}
407
408/// An FTS5 shadow as SQL names it: the table in a `FROM` (`"catalog"."stations_fts"`), and
409/// the hidden column `MATCH` takes, which carries the index's own name and no schema
410/// (`"catalog"."stations_fts" MATCH` is a syntax error, `"stations_fts" MATCH` is not).
411#[derive(Clone, Debug)]
412pub(crate) struct FtsSql {
413    pub from: String,
414    pub match_col: String,
415}
416
417/// Why a fetch would not compile. `NeedsFold` routes to the fallback evaluator; everything
418/// else is a wiring error the query surfaces.
419#[derive(Clone, Debug, PartialEq)]
420pub(crate) enum CompileErr {
421    /// A case-insensitive text predicate on a driver without `day_fold`.
422    NeedsFold,
423    /// A `ContainsCi`/`StartsWithCi` inside a relation predicate on a driver without
424    /// `day_fold`: the fallback evaluator cannot traverse relations, so this combination
425    /// needs the function.
426    FoldInsideRelation,
427    /// `owner.field` is not a wired relation of this container.
428    Unwired(&'static str, &'static str),
429    /// A `matches(…)`/`rank()` fetch on a model with no `fts(…)` declaration.
430    NoFts,
431}
432
433impl CompileErr {
434    pub(crate) fn message(&self) -> String {
435        match self {
436            CompileErr::NeedsFold | CompileErr::FoldInsideRelation => {
437                "case-insensitive predicate needs the driver's day_fold function".into()
438            }
439            CompileErr::Unwired(owner, field) => {
440                format!("`{owner}.{field}` is not a wired relation of this container")
441            }
442            CompileErr::NoFts => "matches()/rank() needs a #[model(fts(…))] declaration".into(),
443        }
444    }
445}
446
447/// A compiled statement and its bound parameters.
448#[derive(Clone, Debug)]
449pub(crate) struct SqlQuery {
450    pub sql: String,
451    pub params: Vec<Value>,
452}
453
454/// Compile a whole fetch over `table` into the id `SELECT` that answers it: `WHERE` from the
455/// predicate, `ORDER BY` from the sorts (with the key as the deterministic tie-break), `LIMIT`
456/// from the window. `Err(NeedsFold)` sends the caller to the fallback path.
457pub(crate) fn compile_fetch(
458    table: &str,
459    fetch: &Fetch,
460    idx: &dyn SqlIndex,
461) -> Result<SqlQuery, CompileErr> {
462    let key = ident(&idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?);
463    let t = idx.table_sql(table);
464    let mut params = Vec::new();
465    let mut aliases = 0usize;
466    let by_rank = fetch.sort.iter().any(|s| s.by_rank);
467
468    // A rank sort orders by the FTS index's own bm25: the match query moves into a join so
469    // `rank` is in scope, and the predicate's own `Matches` compiles to `1` (the join already
470    // constrains to matching rows).
471    let (from, rank_pred);
472    if by_rank {
473        let fts = idx.fts_of(table).ok_or(CompileErr::NoFts)?;
474        let Some(q) = find_match_query(&fetch.pred) else {
475            return Err(CompileErr::NoFts);
476        };
477        params.push(Value::Text(q));
478        let fts_key = idx.fts_key_of(table);
479        from = format!(
480            "{t} JOIN {} AS day_rank ON day_rank.{fts_key} = {t}.{key} AND day_rank.{} MATCH ?",
481            fts.from, fts.match_col
482        );
483        rank_pred = true;
484    } else {
485        from = t.clone();
486        rank_pred = false;
487    }
488
489    let ctx = SqlCtx {
490        idx,
491        skip_matches: rank_pred,
492    };
493    let where_clause = pred_sql(
494        &fetch.pred,
495        table,
496        &t,
497        &key,
498        &ctx,
499        &mut params,
500        &mut aliases,
501    )?;
502
503    let mut sql = format!("SELECT {t}.{key} FROM {from}");
504    if where_clause != "1" {
505        let _ = write!(sql, " WHERE {where_clause}");
506    }
507    let mut orders: Vec<String> = Vec::new();
508    for s in &fetch.sort {
509        if s.by_rank {
510            orders.push("day_rank.rank".into());
511        } else {
512            orders.push(format!(
513                "{t}.{} {}",
514                ident(s.column),
515                if s.ascending { "ASC" } else { "DESC" }
516            ));
517        }
518    }
519    // The key tie-break makes the order total and deterministic, so the same fetch always
520    // answers in the same order and a diff against the previous answer is meaningful.
521    orders.push(format!("{t}.{key} ASC"));
522    let _ = write!(sql, " ORDER BY {}", orders.join(", "));
523    if let Some(n) = fetch.limit {
524        let _ = write!(sql, " LIMIT {n}");
525    }
526    Ok(SqlQuery { sql, params })
527}
528
529/// Compile the `COUNT` form of a fetch: the same `WHERE`, no `ORDER BY`, no id vector; the
530/// badge-shaped query. A `limit` caps the answer after the fact (`min(count, limit)` is what
531/// a limited set's length would be), which the caller applies.
532pub(crate) fn compile_count(
533    table: &str,
534    fetch: &Fetch,
535    idx: &dyn SqlIndex,
536) -> Result<SqlQuery, CompileErr> {
537    let key = ident(&idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?);
538    let t = idx.table_sql(table);
539    let mut params = Vec::new();
540    let mut aliases = 0usize;
541    let ctx = SqlCtx {
542        idx,
543        skip_matches: false,
544    };
545    let where_clause = pred_sql(
546        &fetch.pred,
547        table,
548        &t,
549        &key,
550        &ctx,
551        &mut params,
552        &mut aliases,
553    )?;
554    let mut sql = format!("SELECT COUNT(*) FROM {t}");
555    if where_clause != "1" {
556        let _ = write!(sql, " WHERE {where_clause}");
557    }
558    Ok(SqlQuery { sql, params })
559}
560
561/// Compile the fallback form for a driver without `day_fold`: select the key and every column
562/// the predicate/sort reads, SQL-filter by the top-level `AND` conjuncts that compile exactly,
563/// keep the `ORDER BY` (so the fallback preserves the query's order), and leave the `LIMIT`
564/// to the caller, which applies it after the in-memory re-check.
565pub(crate) fn compile_fallback(
566    table: &str,
567    fetch: &Fetch,
568    idx: &dyn SqlIndex,
569) -> Result<(SqlQuery, Vec<&'static str>), CompileErr> {
570    if fetch.pred.contains_related() && fetch.pred.contains_fold() {
571        // The evaluator cannot traverse relations, and the SQL cannot fold, so no path is
572        // exact; refuse rather than under- or over-answer.
573        return Err(CompileErr::FoldInsideRelation);
574    }
575    let key = ident(&idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?);
576    let t = idx.table_sql(table);
577    let mut params = Vec::new();
578    let mut aliases = 0usize;
579    let ctx = SqlCtx {
580        idx,
581        skip_matches: false,
582    };
583
584    // The exact conjuncts filter in SQL (a candidate superset, since dropping a conjunct can
585    // only widen); the full predicate re-checks in memory over the selected columns.
586    let mut conjuncts = Vec::new();
587    split_and(&fetch.pred, &mut conjuncts);
588    let mut clauses = Vec::new();
589    for c in conjuncts {
590        if !c.contains_fold() {
591            clauses.push(pred_sql(
592                c,
593                table,
594                &t,
595                &key,
596                &ctx,
597                &mut params,
598                &mut aliases,
599            )?);
600        }
601    }
602
603    let mut deps = Vec::new();
604    fetch.pred.columns(&mut deps);
605    for s in &fetch.sort {
606        if !s.by_rank && !deps.contains(&s.column) {
607            deps.push(s.column);
608        }
609    }
610    let cols = if deps.is_empty() {
611        format!("{t}.{key}")
612    } else {
613        format!(
614            "{t}.{key}, {}",
615            deps.iter()
616                .map(|c| format!("{t}.{}", ident(c)))
617                .collect::<Vec<_>>()
618                .join(", ")
619        )
620    };
621    let mut sql = format!("SELECT {cols} FROM {t}");
622    let clauses: Vec<String> = clauses.into_iter().filter(|c| c != "1").collect();
623    if !clauses.is_empty() {
624        let _ = write!(sql, " WHERE {}", clauses.join(" AND "));
625    }
626    let mut orders: Vec<String> = fetch
627        .sort
628        .iter()
629        .filter(|s| !s.by_rank)
630        .map(|s| {
631            format!(
632                "{t}.{} {}",
633                ident(s.column),
634                if s.ascending { "ASC" } else { "DESC" }
635            )
636        })
637        .collect();
638    orders.push(format!("{t}.{key} ASC"));
639    let _ = write!(sql, " ORDER BY {}", orders.join(", "));
640    Ok((SqlQuery { sql, params }, deps))
641}
642
643/// Split a predicate into its top-level `AND` conjuncts.
644fn split_and<'p>(pred: &'p Pred, out: &mut Vec<&'p Pred>) {
645    match pred {
646        Pred::And(a, b) => {
647            split_and(a, out);
648            split_and(b, out);
649        }
650        p => out.push(p),
651    }
652}
653
654struct SqlCtx<'a> {
655    idx: &'a dyn SqlIndex,
656    /// A rank fetch already constrained to matching rows through its join; the `Matches`
657    /// predicate inside compiles to `1` instead of a second subquery.
658    skip_matches: bool,
659}
660
661/// The `WHERE` form of one predicate, columns qualified by `alias` (the current table, quoted,
662/// or an `EXISTS` alias), appending bound parameters to `params`. `table` is the alias's
663/// underlying table's plain name, which FTS and R*Tree shadow lookups resolve against, since
664/// an `EXISTS` alias like `day_r0` names no shadow. `key` is its key column, already quoted.
665fn pred_sql(
666    pred: &Pred,
667    table: &str,
668    alias: &str,
669    key: &str,
670    ctx: &SqlCtx<'_>,
671    params: &mut Vec<Value>,
672    aliases: &mut usize,
673) -> Result<String, CompileErr> {
674    // A column through the alias, quoted: `"t"."order"`, `day_r0."group"`.
675    let col = |c: &str| format!("{alias}.{}", ident(c));
676    Ok(match pred {
677        Pred::Always => "1".into(),
678        Pred::Eq(c, Value::Null) => format!("{} IS NULL", col(c)),
679        Pred::Ne(c, Value::Null) => format!("{} IS NOT NULL", col(c)),
680        Pred::Eq(c, v) => {
681            params.push(v.clone());
682            format!("{} = ?", col(c))
683        }
684        Pred::Ne(c, v) => {
685            params.push(v.clone());
686            format!("{} <> ?", col(c))
687        }
688        Pred::Lt(c, v) => {
689            params.push(v.clone());
690            format!("{} < ?", col(c))
691        }
692        Pred::Le(c, v) => {
693            params.push(v.clone());
694            format!("{} <= ?", col(c))
695        }
696        Pred::Gt(c, v) => {
697            params.push(v.clone());
698            format!("{} > ?", col(c))
699        }
700        Pred::Ge(c, v) => {
701            params.push(v.clone());
702            format!("{} >= ?", col(c))
703        }
704        Pred::Contains(c, s) => {
705            params.push(Value::Text(s.clone()));
706            format!("instr({}, ?) > 0", col(c))
707        }
708        Pred::ContainsCi(c, s) => {
709            if !ctx.idx.unicode_fold() {
710                return Err(CompileErr::NeedsFold);
711            }
712            params.push(Value::Text(s.to_lowercase()));
713            format!("instr(day_fold({}), ?) > 0", col(c))
714        }
715        Pred::StartsWith(c, prefix) => {
716            // Not `LIKE`: SQLite's `LIKE` is case-insensitive for ASCII by default, which
717            // would quietly answer a different question. `substr` counts characters on
718            // `TEXT`, which agrees with Rust's `starts_with` on any valid UTF-8.
719            params.push(Value::Int(prefix.chars().count() as i64));
720            params.push(Value::Text(prefix.clone()));
721            format!("substr({}, 1, ?) = ?", col(c))
722        }
723        Pred::StartsWithCi(c, prefix) => {
724            if !ctx.idx.unicode_fold() {
725                return Err(CompileErr::NeedsFold);
726            }
727            let folded = prefix.to_lowercase();
728            params.push(Value::Int(folded.chars().count() as i64));
729            params.push(Value::Text(folded));
730            format!("substr(day_fold({}), 1, ?) = ?", col(c))
731        }
732        Pred::In(c, set) | Pred::NotIn(c, set) => {
733            // The empty set compiles to its three-valued constant: `IN ()` matches nothing;
734            // `NOT IN ()` matches every row whose column is present; a NULL column is
735            // unknown, not vacuously a non-member, which is the same rule the evaluator
736            // applies (SQLite's literal `NOT IN ()` extension answers true for NULL, and
737            // would let the two paths disagree).
738            if set.is_empty() {
739                return Ok(if matches!(pred, Pred::In(..)) {
740                    "0".into()
741                } else {
742                    format!("{} IS NOT NULL", col(c))
743                });
744            }
745            let negate = if matches!(pred, Pred::NotIn(..)) {
746                "NOT "
747            } else {
748                ""
749            };
750            let marks = vec!["?"; set.len()].join(", ");
751            params.extend(set.iter().cloned());
752            format!("{} {negate}IN ({marks})", col(c))
753        }
754        Pred::IdIn(ids) => {
755            if ids.is_empty() {
756                return Ok("0".into());
757            }
758            for id in ids {
759                params.push(crate::key_param(*id));
760            }
761            let marks = vec!["?"; ids.len()].join(", ");
762            format!("{alias}.{key} IN ({marks})")
763        }
764        Pred::Between(c, lo, hi) => {
765            params.push(lo.clone());
766            params.push(hi.clone());
767            format!("{} BETWEEN ? AND ?", col(c))
768        }
769        Pred::And(a, b) => format!(
770            "({} AND {})",
771            pred_sql(a, table, alias, key, ctx, params, aliases)?,
772            pred_sql(b, table, alias, key, ctx, params, aliases)?
773        ),
774        Pred::Or(a, b) => format!(
775            "({} OR {})",
776            pred_sql(a, table, alias, key, ctx, params, aliases)?,
777            pred_sql(b, table, alias, key, ctx, params, aliases)?
778        ),
779        Pred::Not(a) => format!(
780            "NOT ({})",
781            pred_sql(a, table, alias, key, ctx, params, aliases)?
782        ),
783        Pred::Raw(sql, args) => {
784            params.extend(args.iter().cloned());
785            format!("({sql})")
786        }
787        Pred::Matches { query, .. } => {
788            if ctx.skip_matches {
789                // The rank join already constrains to matching rows.
790                "1".into()
791            } else {
792                let fts = ctx.idx.fts_of(table).ok_or(CompileErr::NoFts)?;
793                params.push(Value::Text(query.clone()));
794                let fts_key = ctx.idx.fts_key_of(table);
795                format!(
796                    "{alias}.{key} IN (SELECT {fts_key} FROM {} WHERE {} MATCH ?)",
797                    fts.from, fts.match_col
798                )
799            }
800        }
801        Pred::Within {
802            lat,
803            lon,
804            min_lat,
805            max_lat,
806            min_lon,
807            max_lon,
808        } => {
809            let exact = {
810                params.push(Value::Real(*min_lat));
811                params.push(Value::Real(*max_lat));
812                params.push(Value::Real(*min_lon));
813                params.push(Value::Real(*max_lon));
814                format!(
815                    "({} BETWEEN ? AND ? AND {} BETWEEN ? AND ?)",
816                    col(lat),
817                    col(lon)
818                )
819            };
820            // The R*Tree shadow narrows first when this is the declared pair: its 32-bit
821            // entries are outward-rounded (a candidate superset, never a miss), and the exact
822            // check above settles the edges.
823            match ctx.idx.geo_of(table, lat, lon) {
824                Some(geo) => {
825                    params.push(Value::Real(*min_lat));
826                    params.push(Value::Real(*max_lat));
827                    params.push(Value::Real(*min_lon));
828                    params.push(Value::Real(*max_lon));
829                    format!(
830                        "({alias}.{key} IN (SELECT {key} FROM {geo} WHERE \
831                         max_lat >= ? AND min_lat <= ? AND max_lon >= ? AND min_lon <= ?) \
832                         AND {exact})"
833                    )
834                }
835                None => exact,
836            }
837        }
838        Pred::Related {
839            owner,
840            field,
841            target,
842            quant,
843            inner,
844        } => {
845            let rel = ctx
846                .idx
847                .relation(owner, field)
848                .ok_or(CompileErr::Unwired(owner, field))?;
849            let r = format!("day_r{}", *aliases);
850            *aliases += 1;
851            let target_sql = ctx.idx.table_sql(target);
852            let (from, tie, inner_alias, inner_key) = match &rel {
853                RelSql::Children {
854                    target_key,
855                    fk_col,
856                    owner_key,
857                } => (
858                    format!("{target_sql} AS {r}"),
859                    format!("{r}.{} = {}", ident(fk_col), col(owner_key)),
860                    r.clone(),
861                    ident(target_key),
862                ),
863                RelSql::Referent { target_key, fk_col } => (
864                    format!("{target_sql} AS {r}"),
865                    format!("{r}.{} = {}", ident(target_key), col(fk_col)),
866                    r.clone(),
867                    ident(target_key),
868                ),
869                RelSql::Linked {
870                    local_col,
871                    remote_col,
872                    target_key,
873                } => (
874                    format!("{target_sql} AS {r}"),
875                    format!("{r}.{} = {}", ident(remote_col), col(local_col)),
876                    r.clone(),
877                    ident(target_key),
878                ),
879                RelSql::Join {
880                    join_table,
881                    owner_col,
882                    target_col,
883                    owner_key,
884                    target_key,
885                } => {
886                    let j = format!("day_j{}", *aliases);
887                    *aliases += 1;
888                    (
889                        format!(
890                            "{} AS {j} JOIN {target_sql} AS {r} ON {r}.{} = {j}.{}",
891                            ctx.idx.table_sql(join_table),
892                            ident(target_key),
893                            ident(target_col)
894                        ),
895                        format!("{j}.{} = {}", ident(owner_col), col(owner_key)),
896                        r.clone(),
897                        ident(target_key),
898                    )
899                }
900            };
901            match quant {
902                Quant::Empty => format!("NOT EXISTS (SELECT 1 FROM {from} WHERE {tie})"),
903                Quant::CountGe(n) => {
904                    params.push(Value::Int(*n as i64));
905                    format!("(SELECT COUNT(*) FROM {from} WHERE {tie}) >= ?")
906                }
907                Quant::Any | Quant::None | Quant::All => {
908                    let inner_sql = pred_sql(
909                        inner,
910                        target,
911                        &inner_alias,
912                        &inner_key,
913                        ctx,
914                        params,
915                        aliases,
916                    )?;
917                    match quant {
918                        Quant::Any => {
919                            format!("EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}))")
920                        }
921                        Quant::None => format!(
922                            "NOT EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}))"
923                        ),
924                        // Every related row definitely matches: `IS TRUE` keeps a related
925                        // row whose inner is unknown failing the quantifier, the reading
926                        // `All` documents.
927                        Quant::All => format!(
928                            "NOT EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}) IS NOT TRUE)"
929                        ),
930                        _ => unreachable!(),
931                    }
932                }
933            }
934        }
935    })
936}
937
938// ---------------------------------------------------------------------------
939// Values
940// ---------------------------------------------------------------------------
941
942/// A column's value when it is present and not NULL, otherwise unknown. A column the row
943/// does not carry at all (a transient field's label) reads as unknown too, rather than as a
944/// silent non-match.
945fn defined(v: Option<Value>) -> Option<Value> {
946    match v {
947        Some(Value::Null) | None => None,
948        Some(v) => Some(v),
949    }
950}
951
952/// The text of a column, or unknown. A text predicate can only be built on a `Col<String>`,
953/// so a non-text value here is a schema mismatch rather than an answer; unknown keeps it out
954/// of the result instead of guessing at a coercion the two paths might disagree about.
955fn text(v: Option<Value>) -> Option<String> {
956    match defined(v) {
957        Some(Value::Text(t)) => Some(t),
958        _ => None,
959    }
960}
961
962/// Membership in a sorted set, with the same equality `eq` uses: find the run that compares
963/// equal under [`compare_values`], then confirm exactly. A mixed `Int`/`Real` set therefore
964/// cannot make `is_in` and `eq` disagree with one another.
965fn in_set(set: &[Value], v: &Value) -> bool {
966    let start = set.partition_point(|x| compare_values(x, v) == Ordering::Less);
967    set[start..]
968        .iter()
969        .take_while(|x| compare_values(x, v) == Ordering::Equal)
970        .any(|x| x == v)
971}
972
973/// SQLite's cross-class ordering (NULL < numbers < text < blob), with one difference:
974/// `Real` compares by `total_cmp`, so a NaN that reaches the fallback evaluator
975/// still orders deterministically instead of poisoning it.
976pub fn compare_values(a: &Value, b: &Value) -> Ordering {
977    fn class(v: &Value) -> u8 {
978        match v {
979            Value::Null => 0,
980            Value::Int(_) | Value::Real(_) => 1,
981            Value::Text(_) => 2,
982            Value::Blob(_) => 3,
983        }
984    }
985    match (a, b) {
986        (Value::Int(x), Value::Int(y)) => x.cmp(y),
987        (Value::Real(x), Value::Real(y)) => x.total_cmp(y),
988        (Value::Int(x), Value::Real(y)) => (*x as f64).total_cmp(y),
989        (Value::Real(x), Value::Int(y)) => x.total_cmp(&(*y as f64)),
990        (Value::Text(x), Value::Text(y)) => x.cmp(y),
991        (Value::Blob(x), Value::Blob(y)) => x.cmp(y),
992        _ => class(a).cmp(&class(b)),
993    }
994}
995
996// ---------------------------------------------------------------------------
997// Typed builders
998// ---------------------------------------------------------------------------
999
1000/// A typed column reference, what `Trip::name()` returns (the derive emits one inherent fn
1001/// per persisted field). It knows the column's name and its stored encoding, so a predicate
1002/// built from it compares in the column's stored language whatever codec the field uses.
1003pub struct Col<V: 'static> {
1004    pub column: &'static str,
1005    /// The struct field this column stores. The change log speaks field names and the SQL
1006    /// speaks column names; they differ under `#[model(column = "…")]`, and a relation is
1007    /// wired by field, so a predicate that crosses one needs both.
1008    pub field: &'static str,
1009    /// The table this column belongs to, which disambiguates a relation when two models
1010    /// happen to name a field alike.
1011    pub owner: &'static str,
1012    encode: fn(&V) -> Value,
1013}
1014
1015impl<V> Clone for Col<V> {
1016    fn clone(&self) -> Self {
1017        *self
1018    }
1019}
1020impl<V> Copy for Col<V> {}
1021
1022/// A relation, as a predicate builder: what `Trip::lodging()` returns. The instance
1023/// accessor of the same name (`trip.lodging()`) reads and writes the relation; this one asks
1024/// questions about it in a query. They cannot collide: one takes `self`, this one does not.
1025pub struct RelationCol<P: 'static, T: 'static> {
1026    field: &'static str,
1027    owner: &'static str,
1028    target: &'static str,
1029    _p: std::marker::PhantomData<fn() -> (P, T)>,
1030}
1031
1032impl<P, T> Clone for RelationCol<P, T> {
1033    fn clone(&self) -> Self {
1034        *self
1035    }
1036}
1037impl<P, T> Copy for RelationCol<P, T> {}
1038
1039impl<P, T> RelationCol<P, T> {
1040    pub const fn new(field: &'static str, owner: &'static str, target: &'static str) -> Self {
1041        RelationCol {
1042            field,
1043            owner,
1044            target,
1045            _p: std::marker::PhantomData,
1046        }
1047    }
1048
1049    fn build(self, quant: Quant, inner: Pred) -> Pred {
1050        Pred::Related {
1051            owner: self.owner,
1052            field: self.field,
1053            target: self.target,
1054            quant,
1055            inner: Box::new(inner),
1056        }
1057    }
1058
1059    /// Some related row matches. False when there are none.
1060    pub fn any(self, inner: Pred) -> Pred {
1061        self.build(Quant::Any, inner)
1062    }
1063
1064    /// No related row matches. True when there are none.
1065    pub fn none(self, inner: Pred) -> Pred {
1066        self.build(Quant::None, inner)
1067    }
1068
1069    /// Every related row matches; vacuously true when there are none, as in SQL. Reach for
1070    /// [`RelationCol::none`] when that is not what you meant.
1071    pub fn all(self, inner: Pred) -> Pred {
1072        self.build(Quant::All, inner)
1073    }
1074
1075    /// No related rows at all: one `NOT EXISTS` over the indexed foreign key.
1076    pub fn is_empty(self) -> Pred {
1077        self.build(Quant::Empty, Pred::Always)
1078    }
1079
1080    /// At least `n` related rows.
1081    pub fn count_ge(self, n: usize) -> Pred {
1082        self.build(Quant::CountGe(n), Pred::Always)
1083    }
1084}
1085
1086/// The encoder a plain (codec-less) field's [`Col`] carries.
1087pub fn encode_column<T: crate::ColumnValue>(v: &T) -> Value {
1088    v.to_sqlite_value()
1089}
1090
1091impl<V> Col<V> {
1092    pub const fn new(
1093        column: &'static str,
1094        field: &'static str,
1095        owner: &'static str,
1096        encode: fn(&V) -> Value,
1097    ) -> Col<V> {
1098        Col {
1099            column,
1100            field,
1101            owner,
1102            encode,
1103        }
1104    }
1105    fn enc(&self, v: &V) -> Value {
1106        (self.encode)(v)
1107    }
1108    pub fn eq(self, v: impl std::borrow::Borrow<V>) -> Pred {
1109        Pred::Eq(self.column, self.enc(v.borrow()))
1110    }
1111    pub fn ne(self, v: impl std::borrow::Borrow<V>) -> Pred {
1112        Pred::Ne(self.column, self.enc(v.borrow()))
1113    }
1114    pub fn lt(self, v: impl std::borrow::Borrow<V>) -> Pred {
1115        Pred::Lt(self.column, self.enc(v.borrow()))
1116    }
1117    pub fn le(self, v: impl std::borrow::Borrow<V>) -> Pred {
1118        Pred::Le(self.column, self.enc(v.borrow()))
1119    }
1120    pub fn gt(self, v: impl std::borrow::Borrow<V>) -> Pred {
1121        Pred::Gt(self.column, self.enc(v.borrow()))
1122    }
1123    pub fn ge(self, v: impl std::borrow::Borrow<V>) -> Pred {
1124        Pred::Ge(self.column, self.enc(v.borrow()))
1125    }
1126    /// `column ∈ values`, each encoded through this column's own codec exactly as `eq` does.
1127    /// An empty set matches nothing, in both evaluation paths.
1128    pub fn is_in(self, values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>) -> Pred {
1129        Pred::In(self.column, self.encode_set(values))
1130    }
1131
1132    /// The complement of [`Col::is_in`], with SQL's NULL rule: a NULL column is unknown, so
1133    /// it is not selected; `not_in` is therefore not the same as `!is_in` over nullable
1134    /// columns, exactly as in SQL.
1135    pub fn not_in(self, values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>) -> Pred {
1136        Pred::NotIn(self.column, self.encode_set(values))
1137    }
1138
1139    /// Sorted and deduped once, here, so evaluation can binary-search it.
1140    fn encode_set(
1141        self,
1142        values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>,
1143    ) -> Vec<Value> {
1144        let mut set: Vec<Value> = values.into_iter().map(|v| self.enc(v.borrow())).collect();
1145        set.sort_by(compare_values);
1146        set.dedup();
1147        set
1148    }
1149
1150    /// `column IS NULL`.
1151    pub fn is_null(self) -> Pred {
1152        Pred::Eq(self.column, Value::Null)
1153    }
1154
1155    /// `column IS NOT NULL`.
1156    pub fn is_not_null(self) -> Pred {
1157        Pred::Ne(self.column, Value::Null)
1158    }
1159
1160    pub fn between(self, lo: impl std::borrow::Borrow<V>, hi: impl std::borrow::Borrow<V>) -> Pred {
1161        Pred::Between(self.column, self.enc(lo.borrow()), self.enc(hi.borrow()))
1162    }
1163    pub fn asc(self) -> Sort {
1164        Sort::asc(self.column)
1165    }
1166    pub fn desc(self) -> Sort {
1167        Sort::desc(self.column)
1168    }
1169}
1170
1171/// What `Trip::fts()` returns when the model declares `#[model(fts(…))]`.
1172#[derive(Clone, Copy)]
1173pub struct FtsRef {
1174    pub columns: &'static [&'static str],
1175}
1176
1177impl FtsRef {
1178    /// Literal search-box input: AND the whitespace-separated terms, quoting FTS syntax.
1179    /// Empty input is unconstrained. Use `matches` for an advanced FTS query expression.
1180    pub fn search(self, text: &str) -> Pred {
1181        let terms = text
1182            .split_whitespace()
1183            .map(|term| format!("\"{}\"", term.replace('"', "\"\"")))
1184            .collect::<Vec<_>>();
1185        if terms.is_empty() {
1186            Pred::Always
1187        } else {
1188            self.matches(terms.join(" AND "))
1189        }
1190    }
1191
1192    /// FTS5 `MATCH`: one subquery over the shadow table; the query re-runs when an indexed
1193    /// column changes and ignores every other column, so the zero-cost tier survives search.
1194    pub fn matches(self, query: impl Into<String>) -> Pred {
1195        Pred::Matches {
1196            columns: self.columns,
1197            query: query.into(),
1198        }
1199    }
1200}
1201
1202/// What `Trip::geo()` returns when the model declares `#[model(spatial(…))]`.
1203#[derive(Clone, Copy)]
1204pub struct GeoRef {
1205    pub lat: &'static str,
1206    pub lon: &'static str,
1207}
1208
1209/// A bounding box for [`GeoRef::within`].
1210#[derive(Clone, Copy, Debug, PartialEq)]
1211pub struct GeoRect {
1212    pub min_lat: f64,
1213    pub max_lat: f64,
1214    pub min_lon: f64,
1215    pub max_lon: f64,
1216}
1217
1218impl GeoRef {
1219    /// Range comparisons over the two columns, narrowed through the R*Tree shadow when the
1220    /// pair is the model's declared one.
1221    pub fn within(self, r: GeoRect) -> Pred {
1222        Pred::Within {
1223            lat: self.lat,
1224            lon: self.lon,
1225            min_lat: r.min_lat,
1226            max_lat: r.max_lat,
1227            min_lon: r.min_lon,
1228            max_lon: r.max_lon,
1229        }
1230    }
1231}
1232
1233/// Order by FTS relevance (bm25, best first); pair with a `matches` predicate.
1234pub fn rank() -> Sort {
1235    Sort {
1236        column: "",
1237        ascending: true,
1238        by_rank: true,
1239    }
1240}
1241
1242impl Col<String> {
1243    /// Case-sensitive substring.
1244    pub fn contains(self, needle: impl Into<String>) -> Pred {
1245        Pred::Contains(self.column, needle.into())
1246    }
1247    /// Case-sensitive prefix match.
1248    pub fn starts_with(self, prefix: impl Into<String>) -> Pred {
1249        Pred::StartsWith(self.column, prefix.into())
1250    }
1251
1252    /// Case-insensitive prefix match.
1253    pub fn starts_with_ci(self, prefix: impl Into<String>) -> Pred {
1254        Pred::StartsWithCi(self.column, prefix.into())
1255    }
1256
1257    /// Case-insensitive substring, what a search field wants.
1258    pub fn contains_ci(self, needle: impl Into<String>) -> Pred {
1259        Pred::ContainsCi(self.column, needle.into())
1260    }
1261}
1262
1263#[derive(Clone, Debug, PartialEq)]
1264pub struct Sort {
1265    pub column: &'static str,
1266    pub ascending: bool,
1267    /// Order by FTS relevance (bm25) instead of a column: `column` is empty, and it compiles
1268    /// to a join against the FTS shadow so the engine orders by its own rank.
1269    pub by_rank: bool,
1270}
1271
1272impl Sort {
1273    pub fn asc(column: &'static str) -> Sort {
1274        Sort {
1275            column,
1276            ascending: true,
1277            by_rank: false,
1278        }
1279    }
1280    pub fn desc(column: &'static str) -> Sort {
1281        Sort {
1282            column,
1283            ascending: false,
1284            by_rank: false,
1285        }
1286    }
1287}
1288
1289/// A declared fetch: predicate, sort, window.
1290#[derive(Clone, Debug, PartialEq)]
1291pub struct Fetch {
1292    pub pred: Pred,
1293    pub sort: Vec<Sort>,
1294    pub limit: Option<usize>,
1295}
1296
1297impl Default for Fetch {
1298    fn default() -> Fetch {
1299        Fetch {
1300            pred: Pred::Always,
1301            sort: Vec::new(),
1302            limit: None,
1303        }
1304    }
1305}
1306
1307impl Fetch {
1308    pub fn new() -> Fetch {
1309        Fetch::default()
1310    }
1311    #[must_use]
1312    pub fn filter(mut self, p: Pred) -> Fetch {
1313        self.pred = match self.pred {
1314            Pred::Always => p,
1315            prior => prior & p,
1316        };
1317        self
1318    }
1319    #[must_use]
1320    pub fn sort(mut self, s: Sort) -> Fetch {
1321        self.sort.push(s);
1322        self
1323    }
1324    #[must_use]
1325    pub fn limit(mut self, n: usize) -> Fetch {
1326        self.limit = Some(n);
1327        self
1328    }
1329
1330    /// The columns a change must touch for this query's result to be able to move. Everything
1331    /// else is a row-level change the query ignores entirely.
1332    pub fn dependencies(&self) -> Deps {
1333        let mut local = Vec::new();
1334        self.pred.columns(&mut local);
1335        for s in &self.sort {
1336            if !s.by_rank && !local.contains(&s.column) {
1337                local.push(s.column);
1338            }
1339        }
1340        let mut related = Vec::new();
1341        self.pred.related_deps(&mut related);
1342        Deps { local, related }
1343    }
1344}
1345
1346/// What a change did to the result set.
1347#[derive(Clone, Copy, PartialEq, Eq, Debug)]
1348pub enum Delta {
1349    Insert(usize, u64),
1350    Remove(usize, u64),
1351    Move(usize, usize, u64),
1352}
1353
1354/// What a fetch reads, and therefore what can move a row through it.
1355///
1356/// Split by table because a query's own columns are one question, and the columns it reads
1357/// across a relation are another: a change to a related row the predicate never mentions
1358/// must stay as free as a change to a local column it never mentions.
1359#[derive(Clone, Debug, Default, PartialEq)]
1360pub struct Deps {
1361    /// Columns of the query's own table: its predicate's and its sort's.
1362    pub local: Vec<&'static str>,
1363    /// One entry per relation the predicate crosses, at any depth.
1364    pub related: Vec<RelatedDep>,
1365}
1366
1367/// One relation's contribution to a fetch's dependencies.
1368#[derive(Clone, Debug, PartialEq)]
1369pub struct RelatedDep {
1370    /// The table declaring the relation.
1371    pub owner: &'static str,
1372    /// The `Many` field, or the `One` column, the predicate crossed.
1373    pub field: &'static str,
1374    pub target_table: &'static str,
1375    /// Columns of the target table the inner predicate reads. Empty when the predicate asks
1376    /// only about membership (`is_empty`, `count_ge`), which no column write can change.
1377    pub columns: Vec<&'static str>,
1378}
1379
1380impl Deps {
1381    /// Whether a change to this column of the query's own table can move a row.
1382    pub fn touches_local(&self, column: &str) -> bool {
1383        self.local.contains(&column)
1384    }
1385
1386    /// Whether a change to this column of `table`, reached across a relation, can move a row.
1387    pub fn touches_related(&self, table: &str, column: &str) -> bool {
1388        self.related
1389            .iter()
1390            .any(|r| r.target_table == table && r.columns.contains(&column))
1391    }
1392
1393    /// The tables this fetch reads across a relation: what a query subscribes to beyond its
1394    /// own store.
1395    pub fn related_tables(&self) -> Vec<&'static str> {
1396        let mut out: Vec<&'static str> = Vec::new();
1397        for r in &self.related {
1398            if !out.contains(&r.target_table) {
1399                out.push(r.target_table);
1400            }
1401        }
1402        out
1403    }
1404}
1405
1406/// What adopting a fresh answer did to a result set.
1407#[derive(Clone, PartialEq, Debug)]
1408pub enum SetChange {
1409    /// Identical; nothing downstream needs waking.
1410    Same,
1411    /// Changed by exactly these deltas, enough to animate a list rather than reload it.
1412    /// Removals come first in descending index order, then insertions in ascending order
1413    /// (each index valid at its point of application); a pure reposition is one `Move`.
1414    Deltas(Vec<Delta>),
1415    /// Too different to narrate row by row; the consumer reloads.
1416    Reload,
1417}
1418
1419/// A query's result set: the ids the SQL last answered, and the diff machinery that turns the
1420/// next answer into list deltas.
1421pub struct ResultSet {
1422    ids: Vec<u64>,
1423    fetch: Fetch,
1424    deps: Deps,
1425}
1426
1427impl ResultSet {
1428    pub fn new(fetch: Fetch) -> ResultSet {
1429        ResultSet {
1430            ids: Vec::new(),
1431            deps: fetch.dependencies(),
1432            fetch,
1433        }
1434    }
1435
1436    pub fn ids(&self) -> &[u64] {
1437        &self.ids
1438    }
1439
1440    pub fn fetch(&self) -> &Fetch {
1441        &self.fetch
1442    }
1443
1444    /// What this set reads: its own columns, and anything it reaches across a relation.
1445    pub fn deps(&self) -> &Deps {
1446        &self.deps
1447    }
1448
1449    /// Replace the whole set without narrating (the seed fetch).
1450    pub fn reset(&mut self, ids: Vec<u64>) {
1451        self.ids = ids;
1452    }
1453
1454    /// Adopt a requery's answer, narrating the difference. Removals and insertions (in any
1455    /// combination) come back as exact deltas, plus at most one reposition among the retained
1456    /// rows; anything more tangled reloads. Every delta list is verified by simulation before
1457    /// it is returned, so a consumer applying the deltas in order always lands on the new set.
1458    pub fn adopt(&mut self, new: Vec<u64>) -> SetChange {
1459        if self.ids == new {
1460            return SetChange::Same;
1461        }
1462        let old = std::mem::replace(&mut self.ids, new);
1463        let new = &self.ids;
1464
1465        let new_set: std::collections::HashSet<u64> = new.iter().copied().collect();
1466        let old_set: std::collections::HashSet<u64> = old.iter().copied().collect();
1467        let retained_old: Vec<u64> = old
1468            .iter()
1469            .copied()
1470            .filter(|k| new_set.contains(k))
1471            .collect();
1472        let retained_new: Vec<u64> = new
1473            .iter()
1474            .copied()
1475            .filter(|k| old_set.contains(k))
1476            .collect();
1477
1478        let mut deltas: Vec<Delta> = Vec::new();
1479        // Removals from the end first, so each index is valid at its point of application.
1480        for (i, k) in old.iter().enumerate().rev() {
1481            if !new_set.contains(k) {
1482                deltas.push(Delta::Remove(i, *k));
1483            }
1484        }
1485        let mut scratch = retained_old.clone();
1486
1487        if retained_old != retained_new {
1488            // The retained rows reordered. One reposition (the shape a sort-column edit
1489            // produces) narrates as a Move; more than one reloads. With one row out of
1490            // place, it is the first mismatched key of one side or the other.
1491            let mismatch = retained_old
1492                .iter()
1493                .copied()
1494                .zip(retained_new.iter().copied())
1495                .find(|(a, b)| a != b);
1496            let mut moved = false;
1497            if let Some((a, b)) = mismatch {
1498                for k in [a, b] {
1499                    let from = scratch.iter().position(|x| *x == k);
1500                    let to = retained_new.iter().position(|x| *x == k);
1501                    if let (Some(from), Some(to)) = (from, to) {
1502                        let mut trial = scratch.clone();
1503                        let key = trial.remove(from);
1504                        trial.insert(to, key);
1505                        if trial == retained_new {
1506                            deltas.push(Delta::Move(from, to, k));
1507                            scratch = trial;
1508                            moved = true;
1509                            break;
1510                        }
1511                    }
1512                }
1513            }
1514            if !moved {
1515                return SetChange::Reload;
1516            }
1517        }
1518
1519        // Insertions in ascending final position, each valid as applied.
1520        for (i, k) in new.iter().enumerate() {
1521            if !old_set.contains(k) {
1522                deltas.push(Delta::Insert(i, *k));
1523                if i <= scratch.len() {
1524                    scratch.insert(i, *k);
1525                } else {
1526                    return SetChange::Reload;
1527                }
1528            }
1529        }
1530
1531        // The proof: applying the narration lands exactly on the new set.
1532        if scratch == *new {
1533            SetChange::Deltas(deltas)
1534        } else {
1535            SetChange::Reload
1536        }
1537    }
1538}
1539
1540pub(crate) fn find_match_query(pred: &Pred) -> Option<String> {
1541    match pred {
1542        Pred::Matches { query, .. } => Some(query.clone()),
1543        Pred::And(a, b) | Pred::Or(a, b) => find_match_query(a).or_else(|| find_match_query(b)),
1544        Pred::Not(a) => find_match_query(a),
1545        _ => None,
1546    }
1547}