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