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;
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`.
384    fn key_of(&self, table: &str) -> Option<String>;
385    /// The FTS5 shadow table of `table`, when the model declares `fts(…)`.
386    fn fts_of(&self, table: &str) -> Option<String>;
387    fn fts_key_of(&self, _table: &str) -> &str {
388        "rowid"
389    }
390    /// The R*Tree shadow of `table`, when `lat`/`lon` are its declared `spatial(…)` pair.
391    fn geo_of(&self, table: &str, lat: &str, lon: &str) -> Option<String>;
392    /// Whether the connection has `day_fold` registered (exact Unicode case folding in SQL).
393    fn unicode_fold(&self) -> bool;
394}
395
396/// Why a fetch would not compile. `NeedsFold` routes to the fallback evaluator; everything
397/// else is a wiring error the query surfaces.
398#[derive(Clone, Debug, PartialEq)]
399pub(crate) enum CompileErr {
400    /// A case-insensitive text predicate on a driver without `day_fold`.
401    NeedsFold,
402    /// A `ContainsCi`/`StartsWithCi` inside a relation predicate on a driver without
403    /// `day_fold`: the fallback evaluator cannot traverse relations, so this combination
404    /// needs the function.
405    FoldInsideRelation,
406    /// `owner.field` is not a wired relation of this container.
407    Unwired(&'static str, &'static str),
408    /// A `matches(…)`/`rank()` fetch on a model with no `fts(…)` declaration.
409    NoFts,
410}
411
412impl CompileErr {
413    pub(crate) fn message(&self) -> String {
414        match self {
415            CompileErr::NeedsFold | CompileErr::FoldInsideRelation => {
416                "case-insensitive predicate needs the driver's day_fold function".into()
417            }
418            CompileErr::Unwired(owner, field) => {
419                format!("`{owner}.{field}` is not a wired relation of this container")
420            }
421            CompileErr::NoFts => "matches()/rank() needs a #[model(fts(…))] declaration".into(),
422        }
423    }
424}
425
426/// A compiled statement and its bound parameters.
427#[derive(Clone, Debug)]
428pub(crate) struct SqlQuery {
429    pub sql: String,
430    pub params: Vec<Value>,
431}
432
433/// Compile a whole fetch over `table` into the id `SELECT` that answers it: `WHERE` from the
434/// predicate, `ORDER BY` from the sorts (with the key as the deterministic tie-break), `LIMIT`
435/// from the window. `Err(NeedsFold)` sends the caller to the fallback path.
436pub(crate) fn compile_fetch(
437    table: &str,
438    fetch: &Fetch,
439    idx: &dyn SqlIndex,
440) -> Result<SqlQuery, CompileErr> {
441    let key = idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?;
442    let mut params = Vec::new();
443    let mut aliases = 0usize;
444    let by_rank = fetch.sort.iter().any(|s| s.by_rank);
445
446    // A rank sort orders by the FTS index's own bm25: the match query moves into a join so
447    // `rank` is in scope, and the predicate's own `Matches` compiles to `1` (the join already
448    // constrains to matching rows).
449    let (from, rank_pred);
450    if by_rank {
451        let fts = idx.fts_of(table).ok_or(CompileErr::NoFts)?;
452        // The hidden `MATCH` column carries the index's bare name, schema-qualified or not.
453        let fts_bare = fts.rsplit('.').next().unwrap_or(&fts).to_string();
454        let Some(q) = find_match_query(&fetch.pred) else {
455            return Err(CompileErr::NoFts);
456        };
457        params.push(Value::Text(q));
458        let fts_key = idx.fts_key_of(table);
459        from = format!(
460            "{table} JOIN {fts} AS day_rank ON day_rank.{fts_key} = {table}.{key} AND day_rank.{fts_bare} MATCH ?"
461        );
462        rank_pred = true;
463    } else {
464        from = table.to_string();
465        rank_pred = false;
466    }
467
468    let ctx = SqlCtx {
469        idx,
470        skip_matches: rank_pred,
471    };
472    let where_clause = pred_sql(
473        &fetch.pred,
474        table,
475        table,
476        &key,
477        &ctx,
478        &mut params,
479        &mut aliases,
480    )?;
481
482    let mut sql = format!("SELECT {table}.{key} FROM {from}");
483    if where_clause != "1" {
484        sql.push_str(&format!(" WHERE {where_clause}"));
485    }
486    let mut orders: Vec<String> = Vec::new();
487    for s in &fetch.sort {
488        if s.by_rank {
489            orders.push("day_rank.rank".into());
490        } else {
491            orders.push(format!(
492                "{table}.{} {}",
493                s.column,
494                if s.ascending { "ASC" } else { "DESC" }
495            ));
496        }
497    }
498    // The key tie-break makes the order total and deterministic, so the same fetch always
499    // answers in the same order and a diff against the previous answer is meaningful.
500    orders.push(format!("{table}.{key} ASC"));
501    sql.push_str(&format!(" ORDER BY {}", orders.join(", ")));
502    if let Some(n) = fetch.limit {
503        sql.push_str(&format!(" LIMIT {n}"));
504    }
505    Ok(SqlQuery { sql, params })
506}
507
508/// Compile the `COUNT` form of a fetch: the same `WHERE`, no `ORDER BY`, no id vector; the
509/// badge-shaped query. A `limit` caps the answer after the fact (`min(count, limit)` is what
510/// a limited set's length would be), which the caller applies.
511pub(crate) fn compile_count(
512    table: &str,
513    fetch: &Fetch,
514    idx: &dyn SqlIndex,
515) -> Result<SqlQuery, CompileErr> {
516    let key = idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?;
517    let mut params = Vec::new();
518    let mut aliases = 0usize;
519    let ctx = SqlCtx {
520        idx,
521        skip_matches: false,
522    };
523    let where_clause = pred_sql(
524        &fetch.pred,
525        table,
526        table,
527        &key,
528        &ctx,
529        &mut params,
530        &mut aliases,
531    )?;
532    let mut sql = format!("SELECT COUNT(*) FROM {table}");
533    if where_clause != "1" {
534        sql.push_str(&format!(" WHERE {where_clause}"));
535    }
536    Ok(SqlQuery { sql, params })
537}
538
539/// Compile the fallback form for a driver without `day_fold`: select the key and every column
540/// the predicate/sort reads, SQL-filter by the top-level `AND` conjuncts that compile exactly,
541/// keep the `ORDER BY` (so the fallback preserves the query's order), and leave the `LIMIT`
542/// to the caller, which applies it after the in-memory re-check.
543pub(crate) fn compile_fallback(
544    table: &str,
545    fetch: &Fetch,
546    idx: &dyn SqlIndex,
547) -> Result<(SqlQuery, Vec<&'static str>), CompileErr> {
548    if fetch.pred.contains_related() && fetch.pred.contains_fold() {
549        // The evaluator cannot traverse relations, and the SQL cannot fold, so no path is
550        // exact; refuse rather than under- or over-answer.
551        return Err(CompileErr::FoldInsideRelation);
552    }
553    let key = idx.key_of(table).ok_or(CompileErr::Unwired("", ""))?;
554    let mut params = Vec::new();
555    let mut aliases = 0usize;
556    let ctx = SqlCtx {
557        idx,
558        skip_matches: false,
559    };
560
561    // The exact conjuncts filter in SQL (a candidate superset, since dropping a conjunct can
562    // only widen); the full predicate re-checks in memory over the selected columns.
563    let mut conjuncts = Vec::new();
564    split_and(&fetch.pred, &mut conjuncts);
565    let mut clauses = Vec::new();
566    for c in conjuncts {
567        if !c.contains_fold() {
568            clauses.push(pred_sql(
569                c,
570                table,
571                table,
572                &key,
573                &ctx,
574                &mut params,
575                &mut aliases,
576            )?);
577        }
578    }
579
580    let mut deps = Vec::new();
581    fetch.pred.columns(&mut deps);
582    for s in &fetch.sort {
583        if !s.by_rank && !deps.contains(&s.column) {
584            deps.push(s.column);
585        }
586    }
587    let cols = if deps.is_empty() {
588        format!("{table}.{key}")
589    } else {
590        format!(
591            "{table}.{key}, {}",
592            deps.iter()
593                .map(|c| format!("{table}.{c}"))
594                .collect::<Vec<_>>()
595                .join(", ")
596        )
597    };
598    let mut sql = format!("SELECT {cols} FROM {table}");
599    let clauses: Vec<String> = clauses.into_iter().filter(|c| c != "1").collect();
600    if !clauses.is_empty() {
601        sql.push_str(&format!(" WHERE {}", clauses.join(" AND ")));
602    }
603    let mut orders: Vec<String> = fetch
604        .sort
605        .iter()
606        .filter(|s| !s.by_rank)
607        .map(|s| {
608            format!(
609                "{table}.{} {}",
610                s.column,
611                if s.ascending { "ASC" } else { "DESC" }
612            )
613        })
614        .collect();
615    orders.push(format!("{table}.{key} ASC"));
616    sql.push_str(&format!(" ORDER BY {}", orders.join(", ")));
617    Ok((SqlQuery { sql, params }, deps))
618}
619
620/// Split a predicate into its top-level `AND` conjuncts.
621fn split_and<'p>(pred: &'p Pred, out: &mut Vec<&'p Pred>) {
622    match pred {
623        Pred::And(a, b) => {
624            split_and(a, out);
625            split_and(b, out);
626        }
627        p => out.push(p),
628    }
629}
630
631struct SqlCtx<'a> {
632    idx: &'a dyn SqlIndex,
633    /// A rank fetch already constrained to matching rows through its join; the `Matches`
634    /// predicate inside compiles to `1` instead of a second subquery.
635    skip_matches: bool,
636}
637
638/// The `WHERE` form of one predicate, columns qualified by `alias` (the current table or an
639/// `EXISTS` alias), appending bound parameters to `params`. `table` is the alias's underlying
640/// table name, which FTS and R*Tree shadow lookups resolve against, since an `EXISTS` alias
641/// like `day_r0` names no shadow.
642fn pred_sql(
643    pred: &Pred,
644    table: &str,
645    alias: &str,
646    key: &str,
647    ctx: &SqlCtx<'_>,
648    params: &mut Vec<Value>,
649    aliases: &mut usize,
650) -> Result<String, CompileErr> {
651    Ok(match pred {
652        Pred::Always => "1".into(),
653        Pred::Eq(c, Value::Null) => format!("{alias}.{c} IS NULL"),
654        Pred::Ne(c, Value::Null) => format!("{alias}.{c} IS NOT NULL"),
655        Pred::Eq(c, v) => {
656            params.push(v.clone());
657            format!("{alias}.{c} = ?")
658        }
659        Pred::Ne(c, v) => {
660            params.push(v.clone());
661            format!("{alias}.{c} <> ?")
662        }
663        Pred::Lt(c, v) => {
664            params.push(v.clone());
665            format!("{alias}.{c} < ?")
666        }
667        Pred::Le(c, v) => {
668            params.push(v.clone());
669            format!("{alias}.{c} <= ?")
670        }
671        Pred::Gt(c, v) => {
672            params.push(v.clone());
673            format!("{alias}.{c} > ?")
674        }
675        Pred::Ge(c, v) => {
676            params.push(v.clone());
677            format!("{alias}.{c} >= ?")
678        }
679        Pred::Contains(c, s) => {
680            params.push(Value::Text(s.clone()));
681            format!("instr({alias}.{c}, ?) > 0")
682        }
683        Pred::ContainsCi(c, s) => {
684            if !ctx.idx.unicode_fold() {
685                return Err(CompileErr::NeedsFold);
686            }
687            params.push(Value::Text(s.to_lowercase()));
688            format!("instr(day_fold({alias}.{c}), ?) > 0")
689        }
690        Pred::StartsWith(c, prefix) => {
691            // Not `LIKE`: SQLite's `LIKE` is case-insensitive for ASCII by default, which
692            // would quietly answer a different question. `substr` counts characters on
693            // `TEXT`, which agrees with Rust's `starts_with` on any valid UTF-8.
694            params.push(Value::Int(prefix.chars().count() as i64));
695            params.push(Value::Text(prefix.clone()));
696            format!("substr({alias}.{c}, 1, ?) = ?")
697        }
698        Pred::StartsWithCi(c, prefix) => {
699            if !ctx.idx.unicode_fold() {
700                return Err(CompileErr::NeedsFold);
701            }
702            let folded = prefix.to_lowercase();
703            params.push(Value::Int(folded.chars().count() as i64));
704            params.push(Value::Text(folded));
705            format!("substr(day_fold({alias}.{c}), 1, ?) = ?")
706        }
707        Pred::In(c, set) | Pred::NotIn(c, set) => {
708            // The empty set compiles to its three-valued constant: `IN ()` matches nothing;
709            // `NOT IN ()` matches every row whose column is present; a NULL column is
710            // unknown, not vacuously a non-member, which is the same rule the evaluator
711            // applies (SQLite's literal `NOT IN ()` extension answers true for NULL, and
712            // would let the two paths disagree).
713            if set.is_empty() {
714                return Ok(if matches!(pred, Pred::In(..)) {
715                    "0".into()
716                } else {
717                    format!("{alias}.{c} IS NOT NULL")
718                });
719            }
720            let negate = if matches!(pred, Pred::NotIn(..)) {
721                "NOT "
722            } else {
723                ""
724            };
725            let marks = vec!["?"; set.len()].join(", ");
726            params.extend(set.iter().cloned());
727            format!("{alias}.{c} {negate}IN ({marks})")
728        }
729        Pred::IdIn(ids) => {
730            if ids.is_empty() {
731                return Ok("0".into());
732            }
733            for id in ids {
734                params.push(crate::key_param(*id));
735            }
736            let marks = vec!["?"; ids.len()].join(", ");
737            format!("{alias}.{key} IN ({marks})")
738        }
739        Pred::Between(c, lo, hi) => {
740            params.push(lo.clone());
741            params.push(hi.clone());
742            format!("{alias}.{c} BETWEEN ? AND ?")
743        }
744        Pred::And(a, b) => format!(
745            "({} AND {})",
746            pred_sql(a, table, alias, key, ctx, params, aliases)?,
747            pred_sql(b, table, alias, key, ctx, params, aliases)?
748        ),
749        Pred::Or(a, b) => format!(
750            "({} OR {})",
751            pred_sql(a, table, alias, key, ctx, params, aliases)?,
752            pred_sql(b, table, alias, key, ctx, params, aliases)?
753        ),
754        Pred::Not(a) => format!(
755            "NOT ({})",
756            pred_sql(a, table, alias, key, ctx, params, aliases)?
757        ),
758        Pred::Raw(sql, args) => {
759            params.extend(args.iter().cloned());
760            format!("({sql})")
761        }
762        Pred::Matches { query, .. } => {
763            if ctx.skip_matches {
764                // The rank join already constrains to matching rows.
765                "1".into()
766            } else {
767                let fts = ctx.idx.fts_of(table).ok_or(CompileErr::NoFts)?;
768                params.push(Value::Text(query.clone()));
769                // The `MATCH` operand is the index's bare name even when the table is
770                // schema-qualified (an attached database): `catalog.t_fts MATCH` is a
771                // syntax error, `t_fts MATCH` inside `FROM catalog.t_fts` is not.
772                let fts_bare = fts.rsplit('.').next().unwrap_or(&fts);
773                let fts_key = ctx.idx.fts_key_of(table);
774                format!("{alias}.{key} IN (SELECT {fts_key} FROM {fts} WHERE {fts_bare} MATCH ?)")
775            }
776        }
777        Pred::Within {
778            lat,
779            lon,
780            min_lat,
781            max_lat,
782            min_lon,
783            max_lon,
784        } => {
785            let exact = {
786                params.push(Value::Real(*min_lat));
787                params.push(Value::Real(*max_lat));
788                params.push(Value::Real(*min_lon));
789                params.push(Value::Real(*max_lon));
790                format!("({alias}.{lat} BETWEEN ? AND ? AND {alias}.{lon} BETWEEN ? AND ?)")
791            };
792            // The R*Tree shadow narrows first when this is the declared pair: its 32-bit
793            // entries are outward-rounded (a candidate superset, never a miss), and the exact
794            // check above settles the edges.
795            match ctx.idx.geo_of(table, lat, lon) {
796                Some(geo) => {
797                    params.push(Value::Real(*min_lat));
798                    params.push(Value::Real(*max_lat));
799                    params.push(Value::Real(*min_lon));
800                    params.push(Value::Real(*max_lon));
801                    format!(
802                        "({alias}.{key} IN (SELECT {key} FROM {geo} WHERE \
803                         max_lat >= ? AND min_lat <= ? AND max_lon >= ? AND min_lon <= ?) \
804                         AND {exact})"
805                    )
806                }
807                None => exact,
808            }
809        }
810        Pred::Related {
811            owner,
812            field,
813            target,
814            quant,
815            inner,
816        } => {
817            let rel = ctx
818                .idx
819                .relation(owner, field)
820                .ok_or(CompileErr::Unwired(owner, field))?;
821            let r = format!("day_r{}", *aliases);
822            *aliases += 1;
823            let (from, tie, inner_alias, inner_key) = match &rel {
824                RelSql::Children {
825                    target_key,
826                    fk_col,
827                    owner_key,
828                } => (
829                    format!("{target} AS {r}"),
830                    format!("{r}.{fk_col} = {alias}.{owner_key}"),
831                    r.clone(),
832                    target_key.clone(),
833                ),
834                RelSql::Referent { target_key, fk_col } => (
835                    format!("{target} AS {r}"),
836                    format!("{r}.{target_key} = {alias}.{fk_col}"),
837                    r.clone(),
838                    target_key.clone(),
839                ),
840                RelSql::Linked {
841                    local_col,
842                    remote_col,
843                    target_key,
844                } => (
845                    format!("{target} AS {r}"),
846                    format!("{r}.{remote_col} = {alias}.{local_col}"),
847                    r.clone(),
848                    target_key.clone(),
849                ),
850                RelSql::Join {
851                    join_table,
852                    owner_col,
853                    target_col,
854                    owner_key,
855                    target_key,
856                } => {
857                    let j = format!("day_j{}", *aliases);
858                    *aliases += 1;
859                    (
860                        format!(
861                            "{join_table} AS {j} JOIN {target} AS {r} ON {r}.{target_key} = {j}.{target_col}"
862                        ),
863                        format!("{j}.{owner_col} = {alias}.{owner_key}"),
864                        r.clone(),
865                        target_key.clone(),
866                    )
867                }
868            };
869            match quant {
870                Quant::Empty => format!("NOT EXISTS (SELECT 1 FROM {from} WHERE {tie})"),
871                Quant::CountGe(n) => {
872                    params.push(Value::Int(*n as i64));
873                    format!("(SELECT COUNT(*) FROM {from} WHERE {tie}) >= ?")
874                }
875                Quant::Any | Quant::None | Quant::All => {
876                    let inner_sql = pred_sql(
877                        inner,
878                        target,
879                        &inner_alias,
880                        &inner_key,
881                        ctx,
882                        params,
883                        aliases,
884                    )?;
885                    match quant {
886                        Quant::Any => {
887                            format!("EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}))")
888                        }
889                        Quant::None => format!(
890                            "NOT EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}))"
891                        ),
892                        // Every related row definitely matches: `IS TRUE` keeps a related
893                        // row whose inner is unknown failing the quantifier, the reading
894                        // `All` documents.
895                        Quant::All => format!(
896                            "NOT EXISTS (SELECT 1 FROM {from} WHERE {tie} AND ({inner_sql}) IS NOT TRUE)"
897                        ),
898                        _ => unreachable!(),
899                    }
900                }
901            }
902        }
903    })
904}
905
906// ---------------------------------------------------------------------------
907// Values
908// ---------------------------------------------------------------------------
909
910/// A column's value when it is present and not NULL, otherwise unknown. A column the row
911/// does not carry at all (a transient field's label) reads as unknown too, rather than as a
912/// silent non-match.
913fn defined(v: Option<Value>) -> Option<Value> {
914    match v {
915        Some(Value::Null) | None => None,
916        Some(v) => Some(v),
917    }
918}
919
920/// The text of a column, or unknown. A text predicate can only be built on a `Col<String>`,
921/// so a non-text value here is a schema mismatch rather than an answer; unknown keeps it out
922/// of the result instead of guessing at a coercion the two paths might disagree about.
923fn text(v: Option<Value>) -> Option<String> {
924    match defined(v) {
925        Some(Value::Text(t)) => Some(t),
926        _ => None,
927    }
928}
929
930/// Membership in a sorted set, with the same equality `eq` uses: find the run that compares
931/// equal under [`compare_values`], then confirm exactly. A mixed `Int`/`Real` set therefore
932/// cannot make `is_in` and `eq` disagree with one another.
933fn in_set(set: &[Value], v: &Value) -> bool {
934    let start = set.partition_point(|x| compare_values(x, v) == Ordering::Less);
935    set[start..]
936        .iter()
937        .take_while(|x| compare_values(x, v) == Ordering::Equal)
938        .any(|x| x == v)
939}
940
941/// SQLite's cross-class ordering (NULL < numbers < text < blob), with one difference:
942/// `Real` compares by `total_cmp`, so a NaN that reaches the fallback evaluator
943/// still orders deterministically instead of poisoning it.
944pub fn compare_values(a: &Value, b: &Value) -> Ordering {
945    fn class(v: &Value) -> u8 {
946        match v {
947            Value::Null => 0,
948            Value::Int(_) | Value::Real(_) => 1,
949            Value::Text(_) => 2,
950            Value::Blob(_) => 3,
951        }
952    }
953    match (a, b) {
954        (Value::Int(x), Value::Int(y)) => x.cmp(y),
955        (Value::Real(x), Value::Real(y)) => x.total_cmp(y),
956        (Value::Int(x), Value::Real(y)) => (*x as f64).total_cmp(y),
957        (Value::Real(x), Value::Int(y)) => x.total_cmp(&(*y as f64)),
958        (Value::Text(x), Value::Text(y)) => x.cmp(y),
959        (Value::Blob(x), Value::Blob(y)) => x.cmp(y),
960        _ => class(a).cmp(&class(b)),
961    }
962}
963
964// ---------------------------------------------------------------------------
965// Typed builders
966// ---------------------------------------------------------------------------
967
968/// A typed column reference, what `Trip::name()` returns (the derive emits one inherent fn
969/// per persisted field). It knows the column's name and its stored encoding, so a predicate
970/// built from it compares in the column's stored language whatever codec the field uses.
971pub struct Col<V: 'static> {
972    pub column: &'static str,
973    /// The struct field this column stores. The change log speaks field names and the SQL
974    /// speaks column names; they differ under `#[model(column = "…")]`, and a relation is
975    /// wired by field, so a predicate that crosses one needs both.
976    pub field: &'static str,
977    /// The table this column belongs to, which disambiguates a relation when two models
978    /// happen to name a field alike.
979    pub owner: &'static str,
980    encode: fn(&V) -> Value,
981}
982
983impl<V> Clone for Col<V> {
984    fn clone(&self) -> Self {
985        *self
986    }
987}
988impl<V> Copy for Col<V> {}
989
990/// A relation, as a predicate builder: what `Trip::lodging()` returns. The instance
991/// accessor of the same name (`trip.lodging()`) reads and writes the relation; this one asks
992/// questions about it in a query. They cannot collide: one takes `self`, this one does not.
993pub struct RelationCol<P: 'static, T: 'static> {
994    field: &'static str,
995    owner: &'static str,
996    target: &'static str,
997    _p: std::marker::PhantomData<fn() -> (P, T)>,
998}
999
1000impl<P, T> Clone for RelationCol<P, T> {
1001    fn clone(&self) -> Self {
1002        *self
1003    }
1004}
1005impl<P, T> Copy for RelationCol<P, T> {}
1006
1007impl<P, T> RelationCol<P, T> {
1008    pub const fn new(field: &'static str, owner: &'static str, target: &'static str) -> Self {
1009        RelationCol {
1010            field,
1011            owner,
1012            target,
1013            _p: std::marker::PhantomData,
1014        }
1015    }
1016
1017    fn build(self, quant: Quant, inner: Pred) -> Pred {
1018        Pred::Related {
1019            owner: self.owner,
1020            field: self.field,
1021            target: self.target,
1022            quant,
1023            inner: Box::new(inner),
1024        }
1025    }
1026
1027    /// Some related row matches. False when there are none.
1028    pub fn any(self, inner: Pred) -> Pred {
1029        self.build(Quant::Any, inner)
1030    }
1031
1032    /// No related row matches. True when there are none.
1033    pub fn none(self, inner: Pred) -> Pred {
1034        self.build(Quant::None, inner)
1035    }
1036
1037    /// Every related row matches; vacuously true when there are none, as in SQL. Reach for
1038    /// [`RelationCol::none`] when that is not what you meant.
1039    pub fn all(self, inner: Pred) -> Pred {
1040        self.build(Quant::All, inner)
1041    }
1042
1043    /// No related rows at all: one `NOT EXISTS` over the indexed foreign key.
1044    pub fn is_empty(self) -> Pred {
1045        self.build(Quant::Empty, Pred::Always)
1046    }
1047
1048    /// At least `n` related rows.
1049    pub fn count_ge(self, n: usize) -> Pred {
1050        self.build(Quant::CountGe(n), Pred::Always)
1051    }
1052}
1053
1054/// The encoder a plain (codec-less) field's [`Col`] carries.
1055pub fn encode_column<T: crate::ColumnValue>(v: &T) -> Value {
1056    v.to_sqlite_value()
1057}
1058
1059impl<V> Col<V> {
1060    pub const fn new(
1061        column: &'static str,
1062        field: &'static str,
1063        owner: &'static str,
1064        encode: fn(&V) -> Value,
1065    ) -> Col<V> {
1066        Col {
1067            column,
1068            field,
1069            owner,
1070            encode,
1071        }
1072    }
1073    fn enc(&self, v: &V) -> Value {
1074        (self.encode)(v)
1075    }
1076    pub fn eq(self, v: impl std::borrow::Borrow<V>) -> Pred {
1077        Pred::Eq(self.column, self.enc(v.borrow()))
1078    }
1079    pub fn ne(self, v: impl std::borrow::Borrow<V>) -> Pred {
1080        Pred::Ne(self.column, self.enc(v.borrow()))
1081    }
1082    pub fn lt(self, v: impl std::borrow::Borrow<V>) -> Pred {
1083        Pred::Lt(self.column, self.enc(v.borrow()))
1084    }
1085    pub fn le(self, v: impl std::borrow::Borrow<V>) -> Pred {
1086        Pred::Le(self.column, self.enc(v.borrow()))
1087    }
1088    pub fn gt(self, v: impl std::borrow::Borrow<V>) -> Pred {
1089        Pred::Gt(self.column, self.enc(v.borrow()))
1090    }
1091    pub fn ge(self, v: impl std::borrow::Borrow<V>) -> Pred {
1092        Pred::Ge(self.column, self.enc(v.borrow()))
1093    }
1094    /// `column ∈ values`, each encoded through this column's own codec exactly as `eq` does.
1095    /// An empty set matches nothing, in both evaluation paths.
1096    pub fn is_in(self, values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>) -> Pred {
1097        Pred::In(self.column, self.encode_set(values))
1098    }
1099
1100    /// The complement of [`Col::is_in`], with SQL's NULL rule: a NULL column is unknown, so
1101    /// it is not selected; `not_in` is therefore not the same as `!is_in` over nullable
1102    /// columns, exactly as in SQL.
1103    pub fn not_in(self, values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>) -> Pred {
1104        Pred::NotIn(self.column, self.encode_set(values))
1105    }
1106
1107    /// Sorted and deduped once, here, so evaluation can binary-search it.
1108    fn encode_set(
1109        self,
1110        values: impl IntoIterator<Item = impl std::borrow::Borrow<V>>,
1111    ) -> Vec<Value> {
1112        let mut set: Vec<Value> = values.into_iter().map(|v| self.enc(v.borrow())).collect();
1113        set.sort_by(compare_values);
1114        set.dedup();
1115        set
1116    }
1117
1118    /// `column IS NULL`.
1119    pub fn is_null(self) -> Pred {
1120        Pred::Eq(self.column, Value::Null)
1121    }
1122
1123    /// `column IS NOT NULL`.
1124    pub fn is_not_null(self) -> Pred {
1125        Pred::Ne(self.column, Value::Null)
1126    }
1127
1128    pub fn between(self, lo: impl std::borrow::Borrow<V>, hi: impl std::borrow::Borrow<V>) -> Pred {
1129        Pred::Between(self.column, self.enc(lo.borrow()), self.enc(hi.borrow()))
1130    }
1131    pub fn asc(self) -> Sort {
1132        Sort::asc(self.column)
1133    }
1134    pub fn desc(self) -> Sort {
1135        Sort::desc(self.column)
1136    }
1137}
1138
1139/// What `Trip::fts()` returns when the model declares `#[model(fts(…))]`.
1140#[derive(Clone, Copy)]
1141pub struct FtsRef {
1142    pub columns: &'static [&'static str],
1143}
1144
1145impl FtsRef {
1146    /// Literal search-box input: AND the whitespace-separated terms, quoting FTS syntax.
1147    /// Empty input is unconstrained. Use `matches` for an advanced FTS query expression.
1148    pub fn search(self, text: &str) -> Pred {
1149        let terms = text
1150            .split_whitespace()
1151            .map(|term| format!("\"{}\"", term.replace('"', "\"\"")))
1152            .collect::<Vec<_>>();
1153        if terms.is_empty() {
1154            Pred::Always
1155        } else {
1156            self.matches(terms.join(" AND "))
1157        }
1158    }
1159
1160    /// FTS5 `MATCH`: one subquery over the shadow table; the query re-runs when an indexed
1161    /// column changes and ignores every other column, so the zero-cost tier survives search.
1162    pub fn matches(self, query: impl Into<String>) -> Pred {
1163        Pred::Matches {
1164            columns: self.columns,
1165            query: query.into(),
1166        }
1167    }
1168}
1169
1170/// What `Trip::geo()` returns when the model declares `#[model(spatial(…))]`.
1171#[derive(Clone, Copy)]
1172pub struct GeoRef {
1173    pub lat: &'static str,
1174    pub lon: &'static str,
1175}
1176
1177/// A bounding box for [`GeoRef::within`].
1178#[derive(Clone, Copy, Debug, PartialEq)]
1179pub struct GeoRect {
1180    pub min_lat: f64,
1181    pub max_lat: f64,
1182    pub min_lon: f64,
1183    pub max_lon: f64,
1184}
1185
1186impl GeoRef {
1187    /// Range comparisons over the two columns, narrowed through the R*Tree shadow when the
1188    /// pair is the model's declared one.
1189    pub fn within(self, r: GeoRect) -> Pred {
1190        Pred::Within {
1191            lat: self.lat,
1192            lon: self.lon,
1193            min_lat: r.min_lat,
1194            max_lat: r.max_lat,
1195            min_lon: r.min_lon,
1196            max_lon: r.max_lon,
1197        }
1198    }
1199}
1200
1201/// Order by FTS relevance (bm25, best first); pair with a `matches` predicate.
1202pub fn rank() -> Sort {
1203    Sort {
1204        column: "",
1205        ascending: true,
1206        by_rank: true,
1207    }
1208}
1209
1210impl Col<String> {
1211    /// Case-sensitive substring.
1212    pub fn contains(self, needle: impl Into<String>) -> Pred {
1213        Pred::Contains(self.column, needle.into())
1214    }
1215    /// Case-sensitive prefix match.
1216    pub fn starts_with(self, prefix: impl Into<String>) -> Pred {
1217        Pred::StartsWith(self.column, prefix.into())
1218    }
1219
1220    /// Case-insensitive prefix match.
1221    pub fn starts_with_ci(self, prefix: impl Into<String>) -> Pred {
1222        Pred::StartsWithCi(self.column, prefix.into())
1223    }
1224
1225    /// Case-insensitive substring, what a search field wants.
1226    pub fn contains_ci(self, needle: impl Into<String>) -> Pred {
1227        Pred::ContainsCi(self.column, needle.into())
1228    }
1229}
1230
1231#[derive(Clone, Debug, PartialEq)]
1232pub struct Sort {
1233    pub column: &'static str,
1234    pub ascending: bool,
1235    /// Order by FTS relevance (bm25) instead of a column: `column` is empty, and it compiles
1236    /// to a join against the FTS shadow so the engine orders by its own rank.
1237    pub by_rank: bool,
1238}
1239
1240impl Sort {
1241    pub fn asc(column: &'static str) -> Sort {
1242        Sort {
1243            column,
1244            ascending: true,
1245            by_rank: false,
1246        }
1247    }
1248    pub fn desc(column: &'static str) -> Sort {
1249        Sort {
1250            column,
1251            ascending: false,
1252            by_rank: false,
1253        }
1254    }
1255}
1256
1257/// A declared fetch: predicate, sort, window.
1258#[derive(Clone, Debug, PartialEq)]
1259pub struct Fetch {
1260    pub pred: Pred,
1261    pub sort: Vec<Sort>,
1262    pub limit: Option<usize>,
1263}
1264
1265impl Default for Fetch {
1266    fn default() -> Fetch {
1267        Fetch {
1268            pred: Pred::Always,
1269            sort: Vec::new(),
1270            limit: None,
1271        }
1272    }
1273}
1274
1275impl Fetch {
1276    pub fn new() -> Fetch {
1277        Fetch::default()
1278    }
1279    pub fn filter(mut self, p: Pred) -> Fetch {
1280        self.pred = match self.pred {
1281            Pred::Always => p,
1282            prior => prior & p,
1283        };
1284        self
1285    }
1286    pub fn sort(mut self, s: Sort) -> Fetch {
1287        self.sort.push(s);
1288        self
1289    }
1290    pub fn limit(mut self, n: usize) -> Fetch {
1291        self.limit = Some(n);
1292        self
1293    }
1294
1295    /// The columns a change must touch for this query's result to be able to move. Everything
1296    /// else is a row-level change the query ignores entirely.
1297    pub fn dependencies(&self) -> Deps {
1298        let mut local = Vec::new();
1299        self.pred.columns(&mut local);
1300        for s in &self.sort {
1301            if !s.by_rank && !local.contains(&s.column) {
1302                local.push(s.column);
1303            }
1304        }
1305        let mut related = Vec::new();
1306        self.pred.related_deps(&mut related);
1307        Deps { local, related }
1308    }
1309}
1310
1311/// What a change did to the result set.
1312#[derive(Clone, Copy, PartialEq, Eq, Debug)]
1313pub enum Delta {
1314    Insert(usize, u64),
1315    Remove(usize, u64),
1316    Move(usize, usize, u64),
1317}
1318
1319/// What a fetch reads, and therefore what can move a row through it.
1320///
1321/// Split by table because a query's own columns are one question, and the columns it reads
1322/// across a relation are another: a change to a related row the predicate never mentions
1323/// must stay as free as a change to a local column it never mentions.
1324#[derive(Clone, Debug, Default, PartialEq)]
1325pub struct Deps {
1326    /// Columns of the query's own table: its predicate's and its sort's.
1327    pub local: Vec<&'static str>,
1328    /// One entry per relation the predicate crosses, at any depth.
1329    pub related: Vec<RelatedDep>,
1330}
1331
1332/// One relation's contribution to a fetch's dependencies.
1333#[derive(Clone, Debug, PartialEq)]
1334pub struct RelatedDep {
1335    /// The table declaring the relation.
1336    pub owner: &'static str,
1337    /// The `Many` field, or the `One` column, the predicate crossed.
1338    pub field: &'static str,
1339    pub target_table: &'static str,
1340    /// Columns of the target table the inner predicate reads. Empty when the predicate asks
1341    /// only about membership (`is_empty`, `count_ge`), which no column write can change.
1342    pub columns: Vec<&'static str>,
1343}
1344
1345impl Deps {
1346    /// Whether a change to this column of the query's own table can move a row.
1347    pub fn touches_local(&self, column: &str) -> bool {
1348        self.local.contains(&column)
1349    }
1350
1351    /// Whether a change to this column of `table`, reached across a relation, can move a row.
1352    pub fn touches_related(&self, table: &str, column: &str) -> bool {
1353        self.related
1354            .iter()
1355            .any(|r| r.target_table == table && r.columns.contains(&column))
1356    }
1357
1358    /// The tables this fetch reads across a relation: what a query subscribes to beyond its
1359    /// own store.
1360    pub fn related_tables(&self) -> Vec<&'static str> {
1361        let mut out: Vec<&'static str> = Vec::new();
1362        for r in &self.related {
1363            if !out.contains(&r.target_table) {
1364                out.push(r.target_table);
1365            }
1366        }
1367        out
1368    }
1369}
1370
1371/// What adopting a fresh answer did to a result set.
1372#[derive(Clone, PartialEq, Debug)]
1373pub enum SetChange {
1374    /// Identical; nothing downstream needs waking.
1375    Same,
1376    /// Changed by exactly these deltas, enough to animate a list rather than reload it.
1377    /// Removals come first in descending index order, then insertions in ascending order
1378    /// (each index valid at its point of application); a pure reposition is one `Move`.
1379    Deltas(Vec<Delta>),
1380    /// Too different to narrate row by row; the consumer reloads.
1381    Reload,
1382}
1383
1384/// A query's result set: the ids the SQL last answered, and the diff machinery that turns the
1385/// next answer into list deltas.
1386pub struct ResultSet {
1387    ids: Vec<u64>,
1388    fetch: Fetch,
1389    deps: Deps,
1390}
1391
1392impl ResultSet {
1393    pub fn new(fetch: Fetch) -> ResultSet {
1394        ResultSet {
1395            ids: Vec::new(),
1396            deps: fetch.dependencies(),
1397            fetch,
1398        }
1399    }
1400
1401    pub fn ids(&self) -> &[u64] {
1402        &self.ids
1403    }
1404
1405    pub fn fetch(&self) -> &Fetch {
1406        &self.fetch
1407    }
1408
1409    /// What this set reads: its own columns, and anything it reaches across a relation.
1410    pub fn deps(&self) -> &Deps {
1411        &self.deps
1412    }
1413
1414    /// Replace the whole set without narrating (the seed fetch).
1415    pub fn reset(&mut self, ids: Vec<u64>) {
1416        self.ids = ids;
1417    }
1418
1419    /// Adopt a requery's answer, narrating the difference. Removals and insertions (in any
1420    /// combination) come back as exact deltas, plus at most one reposition among the retained
1421    /// rows; anything more tangled reloads. Every delta list is verified by simulation before
1422    /// it is returned, so a consumer applying the deltas in order always lands on the new set.
1423    pub fn adopt(&mut self, new: Vec<u64>) -> SetChange {
1424        if self.ids == new {
1425            return SetChange::Same;
1426        }
1427        let old = std::mem::replace(&mut self.ids, new);
1428        let new = &self.ids;
1429
1430        let new_set: std::collections::HashSet<u64> = new.iter().copied().collect();
1431        let old_set: std::collections::HashSet<u64> = old.iter().copied().collect();
1432        let retained_old: Vec<u64> = old
1433            .iter()
1434            .copied()
1435            .filter(|k| new_set.contains(k))
1436            .collect();
1437        let retained_new: Vec<u64> = new
1438            .iter()
1439            .copied()
1440            .filter(|k| old_set.contains(k))
1441            .collect();
1442
1443        let mut deltas: Vec<Delta> = Vec::new();
1444        // Removals from the end first, so each index is valid at its point of application.
1445        for (i, k) in old.iter().enumerate().rev() {
1446            if !new_set.contains(k) {
1447                deltas.push(Delta::Remove(i, *k));
1448            }
1449        }
1450        let mut scratch = retained_old.clone();
1451
1452        if retained_old != retained_new {
1453            // The retained rows reordered. One reposition (the shape a sort-column edit
1454            // produces) narrates as a Move; more than one reloads. With one row out of
1455            // place, it is the first mismatched key of one side or the other.
1456            let mismatch = retained_old
1457                .iter()
1458                .copied()
1459                .zip(retained_new.iter().copied())
1460                .find(|(a, b)| a != b);
1461            let mut moved = false;
1462            if let Some((a, b)) = mismatch {
1463                for k in [a, b] {
1464                    let from = scratch.iter().position(|x| *x == k);
1465                    let to = retained_new.iter().position(|x| *x == k);
1466                    if let (Some(from), Some(to)) = (from, to) {
1467                        let mut trial = scratch.clone();
1468                        let key = trial.remove(from);
1469                        trial.insert(to, key);
1470                        if trial == retained_new {
1471                            deltas.push(Delta::Move(from, to, k));
1472                            scratch = trial;
1473                            moved = true;
1474                            break;
1475                        }
1476                    }
1477                }
1478            }
1479            if !moved {
1480                return SetChange::Reload;
1481            }
1482        }
1483
1484        // Insertions in ascending final position, each valid as applied.
1485        for (i, k) in new.iter().enumerate() {
1486            if !old_set.contains(k) {
1487                deltas.push(Delta::Insert(i, *k));
1488                if i <= scratch.len() {
1489                    scratch.insert(i, *k);
1490                } else {
1491                    return SetChange::Reload;
1492                }
1493            }
1494        }
1495
1496        // The proof: applying the narration lands exactly on the new set.
1497        if scratch == *new {
1498            SetChange::Deltas(deltas)
1499        } else {
1500            SetChange::Reload
1501        }
1502    }
1503}
1504
1505pub(crate) fn find_match_query(pred: &Pred) -> Option<String> {
1506    match pred {
1507        Pred::Matches { query, .. } => Some(query.clone()),
1508        Pred::And(a, b) | Pred::Or(a, b) => find_match_query(a).or_else(|| find_match_query(b)),
1509        Pred::Not(a) => find_match_query(a),
1510        _ => None,
1511    }
1512}