Skip to main content

sqlive/
row_scope.rs

1//! Which rows of a table a live query depends on, and the values of a changed
2//! row that decide whether it is one of them (ยง4). A join's values come from
3//! a lookup, and a condition on the row's own columns from a question to
4//! SQLite (`scope_lookup.rs`, `scope_row.rs`).
5
6use std::cmp::Ordering;
7use std::collections::{BTreeMap, BTreeSet};
8use std::sync::Arc;
9
10use crate::scope_lookup::{Judging, Lookup, Lookups, NoAnswer};
11use crate::scope_row::RowCondition;
12use crate::scope_window::{RowWindow, WindowQuestion};
13use crate::sql_value::SqlValue as Value;
14
15/// A predicate over a table's rows. A change reruns a query when its row
16/// passes in its old or its new image.
17#[derive(Clone, Debug)]
18pub enum RowScope {
19    /// Every row.
20    All,
21    /// Rows whose `column` compares with `value` as `ordering`, or equal too
22    /// when `inclusive`.
23    Compare {
24        /// The tested column, lowercase.
25        column: String,
26        /// The value the scope compares the column with.
27        value: Value,
28        /// The order the column's value has to `value`.
29        ordering: Ordering,
30        /// Whether a value equal to `value` also passes.
31        inclusive: bool,
32    },
33    /// Rows whose `column` is NULL, or is not NULL when `not`.
34    Null {
35        /// The tested column, lowercase.
36        column: String,
37        /// Whether rows whose column is not NULL pass instead.
38        not: bool,
39    },
40    /// Rows whose `column` equals one of `values`, sorted in SQLite's order
41    /// with NULLs and repeats left out: made by [`RowScope::equal`].
42    In {
43        /// The tested column, lowercase.
44        column: String,
45        /// The values that pass, in SQLite's order.
46        values: Vec<Value>,
47    },
48    /// Rows a condition on their columns holds for, which a write judges by
49    /// asking SQLite (`scope_row.rs`).
50    Row(Arc<RowCondition>),
51    /// Rows whose `column` equals a value some row of another source holds
52    /// in its own scope: a join, which a write judges by running `lookup`.
53    Joined {
54        /// The joined column, lowercase.
55        column: String,
56        /// The question that finds partner rows holding a value.
57        lookup: Arc<Lookup>,
58    },
59    /// Rows that fewer than a subquery's LIMIT rows of their window sort
60    /// before, which a write judges by asking SQLite (`scope_window.rs`).
61    Window(Arc<RowWindow>),
62    /// Rows both scopes pass.
63    And(Box<Self>, Box<Self>),
64    /// Rows either scope passes.
65    Or(Box<Self>, Box<Self>),
66}
67
68impl RowScope {
69    /// Whether `row` passes, running `lookups` for a join's values. A
70    /// column the image doesn't hold passes: the write that made it didn't
71    /// know this scope would test it. A question that stops ends the test
72    /// with no answer.
73    pub(crate) fn matches(
74        &self,
75        row: &RowImage,
76        lookups: &mut Lookups<'_>,
77    ) -> Result<bool, NoAnswer> {
78        Ok(match self {
79            Self::All => true,
80            Self::Compare { column, value, ordering, inclusive } => {
81                row.get(column).is_none_or(|actual| {
82                    compare(actual, value)
83                        .is_some_and(|found| found == *ordering || (*inclusive && found.is_eq()))
84                })
85            }
86            Self::Null { column, not } => {
87                row.get(column).is_none_or(|actual| matches!(actual, Value::Null) != *not)
88            }
89            Self::In { column, values } => row.get(column).is_none_or(|actual| {
90                !matches!(actual, Value::Null)
91                    && values
92                        .binary_search_by(|value| {
93                            compare(value, actual).expect("neither value is NULL")
94                        })
95                        .is_ok()
96            }),
97            Self::Joined { column, lookup } => match row.get(column) {
98                None => true,
99                // NULL equals nothing, so no join matches it, except one on
100                // `IS`.
101                Some(Value::Null) if !lookup.nulls() => false,
102                Some(value) => lookups(Judging::Partner(lookup, value))?,
103            },
104            // A value the question can't give its column's type, or one the
105            // write didn't record, passes.
106            Self::Row(condition) => match condition.question(row) {
107                None => true,
108                Some((sql, parameters)) => lookups(Judging::Row(&sql, &parameters))?,
109            },
110            Self::Window(window) => match window.question(row) {
111                WindowQuestion::Answered(passes) => passes,
112                WindowQuestion::Ask(sql, parameters) => lookups(Judging::Row(&sql, &parameters))?,
113            },
114            Self::And(left, right) => left.matches(row, lookups)? && right.matches(row, lookups)?,
115            Self::Or(left, right) => left.matches(row, lookups)? || right.matches(row, lookups)?,
116        })
117    }
118
119    /// Rows whose `column` equals one of `values`.
120    pub fn equal(column: String, mut values: Vec<Value>) -> Self {
121        values.retain(|value| !matches!(value, Value::Null));
122        values.sort_by(|left, right| compare(left, right).expect("NULLs were left out"));
123        values.dedup_by(|left, right| compare(left, right).is_some_and(Ordering::is_eq));
124        Self::In { column, values }
125    }
126
127    /// The values every row in this scope holds in `column`, when the scope
128    /// says: an equality or IN list on it, alone or among conditions it
129    /// joins with AND.
130    pub(crate) fn equal_values(&self, column: &str) -> Option<Vec<Value>> {
131        match self {
132            Self::In { column: tested, values } if tested == column => Some(values.clone()),
133            Self::Compare {
134                column: tested,
135                value,
136                ordering: Ordering::Equal,
137                inclusive: false,
138            } if tested == column => Some(vec![value.clone()]),
139            Self::And(left, right) => {
140                left.equal_values(column).or_else(|| right.equal_values(column))
141            }
142            Self::Or(left, right) => {
143                let mut values = left.equal_values(column)?;
144                values.extend(right.equal_values(column)?);
145                Some(values)
146            }
147            _ => None,
148        }
149    }
150
151    /// A column in which every row in this scope holds one of a few values,
152    /// with those values: the first column its equalities and IN lists test
153    /// for which `equal_values` gives them. A handle files the scope's read
154    /// under them, so a change to a row that holds none of them is never
155    /// judged against the read (`read_index.rs`).
156    pub(crate) fn key(&self) -> Option<(&str, Vec<Value>)> {
157        let mut columns = Vec::new();
158        self.equality_columns(&mut columns);
159        columns.into_iter().find_map(|column| Some((column, self.equal_values(column)?)))
160    }
161
162    /// The columns this scope's equalities and IN lists test, in order.
163    fn equality_columns<'a>(&'a self, into: &mut Vec<&'a str>) {
164        match self {
165            Self::In { column, .. }
166            | Self::Compare { column, ordering: Ordering::Equal, inclusive: false, .. } => {
167                into.push(column);
168            }
169            Self::And(left, right) | Self::Or(left, right) => {
170                left.equality_columns(into);
171                right.equality_columns(into);
172            }
173            Self::All
174            | Self::Compare { .. }
175            | Self::Null { .. }
176            | Self::Row(_)
177            | Self::Joined { .. }
178            | Self::Window(_) => {}
179        }
180    }
181
182    /// The columns this scope tests, lowercase.
183    pub fn columns(&self, into: &mut std::collections::BTreeSet<String>) {
184        match self {
185            Self::All => {}
186            Self::Compare { column, .. }
187            | Self::Null { column, .. }
188            | Self::In { column, .. }
189            | Self::Joined { column, .. } => {
190                into.insert(column.clone());
191            }
192            Self::Row(condition) => {
193                into.extend(condition.term.columns.iter().map(|(column, _)| column.clone()));
194            }
195            Self::Window(window) => into.extend(window.columns().cloned()),
196            Self::And(left, right) | Self::Or(left, right) => {
197                left.columns(into);
198                right.columns(into);
199            }
200        }
201    }
202
203    /// Both scopes: either alone when the other is every row.
204    pub fn and(self, other: Self) -> Self {
205        match (self, other) {
206            (Self::All, scope) | (scope, Self::All) => scope,
207            (left, right) => Self::And(Box::new(left), Box::new(right)),
208        }
209    }
210
211    /// Either scope: every row when either is.
212    pub(crate) fn or(self, other: Self) -> Self {
213        match (self, other) {
214            (Self::All, _) | (_, Self::All) => Self::All,
215            (left, right) => Self::Or(Box::new(left), Box::new(right)),
216        }
217    }
218}
219
220/// What one run of a statement depends on: the scope of each table it read
221/// as one of its sources, and the app's views and the CTEs it read as
222/// sources of their own, by the names SQLite reports reads through them by,
223/// whose tables' rows those scopes cover. A table read otherwise, as
224/// through a view read whole, depends on every row. Empty when the
225/// statement's shape keeps every table whole.
226pub struct Scopes {
227    pub(crate) tables: BTreeMap<String, RowScope>,
228    pub(crate) inlined: BTreeSet<String>,
229    /// The shadow tables of the contentful FTS5 tables the statement reads,
230    /// whose reads count for nothing (`Sources::fts5_shadows`).
231    pub(crate) fts5_shadows: BTreeSet<String>,
232    /// Columns the statement reads that SQLite's authorizer doesn't report:
233    /// those its USING and NATURAL joins compare and every column of a table
234    /// that a query whose rows SQLite picks reads, or every column when the
235    /// planner couldn't tell which (`unreported_columns.rs`).
236    pub(crate) unreported: std::sync::Arc<crate::unreported_columns::UnreportedColumns>,
237}
238
239impl Default for Scopes {
240    /// Every table whole, with no column beyond those SQLite reports.
241    fn default() -> Self {
242        Self {
243            tables: BTreeMap::new(),
244            inlined: BTreeSet::new(),
245            fts5_shadows: BTreeSet::new(),
246            unreported: std::sync::Arc::new(crate::unreported_columns::UnreportedColumns::Known(
247                crate::read_set::ColumnSet::new(),
248            )),
249        }
250    }
251}
252
253/// The values of some of a changed row's columns, as a write recorded them:
254/// its key's, and those a waiting live query reads or its scope tests.
255#[derive(Clone, Debug, PartialEq)]
256pub struct RowImage {
257    /// The columns, lowercase, shared by every image of one table in a write.
258    columns: Arc<[String]>,
259    /// Each column's value, or `None` where the write couldn't record it.
260    values: Vec<Option<Value>>,
261}
262
263impl RowImage {
264    /// The image of a row that holds `values` in `columns`.
265    pub fn new(columns: Arc<[String]>, values: Vec<Option<Value>>) -> Self {
266        assert_eq!(columns.len(), values.len(), "one value per column");
267        Self { columns, values }
268    }
269
270    /// The value of `column`, lowercase, if the write recorded it.
271    pub(crate) fn get(&self, column: &str) -> Option<&Value> {
272        self.columns
273            .iter()
274            .position(|name| name == column)
275            .and_then(|index| self.values[index].as_ref())
276    }
277}
278
279/// SQLite's order between two values of a column with BINARY collation and
280/// no conversion between them; `None` when either is NULL, which equals and
281/// orders against nothing.
282pub(crate) fn compare(left: &Value, right: &Value) -> Option<Ordering> {
283    fn rank(value: &Value) -> u8 {
284        match value {
285            Value::Null => 0,
286            Value::Integer(_) | Value::Real(_) => 1,
287            Value::Text(_) => 2,
288            Value::Blob(_) => 3,
289        }
290    }
291    match (left, right) {
292        (Value::Null, _) | (_, Value::Null) => None,
293        (Value::Text(left), Value::Text(right)) => Some(left.cmp(right)),
294        (Value::Blob(left), Value::Blob(right)) => Some(left.cmp(right)),
295        (Value::Integer(left), Value::Integer(right)) => Some(left.cmp(right)),
296        (Value::Real(left), Value::Real(right)) => Some(compare_reals(*left, *right)),
297        (Value::Integer(left), Value::Real(right)) => Some(compare_integer_real(*left, *right)),
298        (Value::Real(left), Value::Integer(right)) => {
299            Some(compare_integer_real(*right, *left).reverse())
300        }
301        _ => Some(rank(left).cmp(&rank(right))),
302    }
303}
304
305/// SQLite stores no NaN, and -0.0 equals 0.0.
306fn compare_reals(left: f64, right: f64) -> Ordering {
307    left.partial_cmp(&right).expect("SQLite stores no NaN")
308}
309
310/// Compares an integer with a real exactly as SQLite's `sqlite3IntFloatCompare`
311/// does, because converting the integer to `f64` would round it.
312fn compare_integer_real(integer: i64, real: f64) -> Ordering {
313    // 2^63 is the first real above every integer.
314    if real < -9_223_372_036_854_775_808.0 {
315        return Ordering::Greater;
316    }
317    if real >= 9_223_372_036_854_775_808.0 {
318        return Ordering::Less;
319    }
320    // The real's whole part is an integer in range; its fraction decides a tie.
321    let whole = real as i64;
322    integer.cmp(&whole).then_with(|| compare_reals(whole as f64, real))
323}
324
325#[cfg(test)]
326#[path = "row_scope_tests.rs"]
327mod tests;