Skip to main content

sqlive/
read_set.rs

1//! What a live query's run read, and whether a commit's row changes could
2//! change what it returned.
3
4use crate::row_scope::{RowImage, RowScope};
5use crate::scope_lookup::{Judging, Lookups, NoAnswer};
6use crate::sql_value::SqlValue;
7use std::borrow::Cow;
8use std::collections::{BTreeSet, HashMap, HashSet};
9
10/// Past this many row changes to one table, a write records only that the
11/// table changed, not each row, so its memory stays bounded; every live
12/// query that reads the table then runs again.
13pub const ROWS_PER_TABLE: usize = 10_000;
14
15/// The table and column names a run read, as pairs.
16pub type ColumnSet = BTreeSet<(String, String)>;
17/// The tables a run read, with the rows and columns of each.
18pub type ReadSet = Vec<TableRead>;
19
20/// What a run read from one table.
21#[derive(Clone)]
22pub struct TableRead {
23    /// The table's name.
24    pub table: String,
25    /// The columns the run read.
26    pub columns: BTreeSet<String>,
27    /// The rows whose changes matter.
28    pub scope: RowScope,
29    /// Only inserted rows affect this read, not updates or deletions.
30    pub inserted_only: bool,
31}
32
33/// One change a commit made to a table's column or row.
34pub struct RowChange {
35    /// The table's name.
36    pub table: String,
37    /// The changed column, or empty for a change to a whole row.
38    pub column: String,
39    /// The row before and after, `None` on the side where it isn't there;
40    /// `None` altogether for a change no row names, as a virtual table's or
41    /// one only the update hook observed, which every scope covers.
42    pub rows: Option<(Option<RowImage>, Option<RowImage>)>,
43}
44
45impl TableRead {
46    /// Whether `change` could change what this read returned, running
47    /// `lookups` for a join's values.
48    fn affected(&self, change: &RowChange, lookups: &mut Lookups<'_>) -> Result<bool, NoAnswer> {
49        if self.table != change.table
50            || !(change.column.is_empty() || self.columns.contains(&change.column))
51            || (self.inserted_only && !inserted(change))
52        {
53            return Ok(false);
54        }
55        let Some((old, new)) = &change.rows else {
56            return Ok(true);
57        };
58        for row in [old, new].into_iter().flatten() {
59            if self.scope.matches(row, lookups)? {
60                return Ok(true);
61            }
62        }
63        Ok(false)
64    }
65}
66
67/// An insertion: a whole-row change with no row before it.
68fn inserted(change: &RowChange) -> bool {
69    change.column.is_empty() && change.rows.as_ref().is_some_and(|(old, _)| old.is_none())
70}
71
72/// Whether `changes` could change what `reads` returned. Past
73/// `ROWS_PER_TABLE` row changes to one table, a join's values in that table
74/// count as matched without a lookup, as a table changed whole would, so a
75/// write's lookups stay bounded. A question that runs past `LOOKUP_STEPS`
76/// and stops leaves sqlive unable to tell, so `reads` count as changed
77/// whatever the other questions answer (ยง4).
78pub fn affected(
79    reads: &ReadSet,
80    changes: &[RowChange],
81    answers: &mut Answers,
82    lookups: &mut Lookups<'_>,
83) -> rusqlite::Result<bool> {
84    affected_by(reads, changes, &past_row_limit(changes), answers, lookups)
85}
86
87/// The tables `changes` changes more than `ROWS_PER_TABLE` rows of.
88pub(crate) fn past_row_limit(changes: &[RowChange]) -> HashSet<&str> {
89    let mut counts: HashMap<&str, usize> = HashMap::new();
90    for change in changes.iter().filter(|change| change.rows.is_some()) {
91        *counts.entry(&change.table).or_default() += 1;
92    }
93    counts
94        .into_iter()
95        .filter(|(_, count)| *count > ROWS_PER_TABLE)
96        .map(|(table, _)| table)
97        .collect()
98}
99
100/// Whether some of `changes`, of a write that changes more than
101/// `ROWS_PER_TABLE` rows of each table `crowded` names, could change what
102/// `reads` returned, as `affected` judges them.
103pub(crate) fn affected_by<'a>(
104    reads: &ReadSet,
105    changes: impl IntoIterator<Item = &'a RowChange>,
106    crowded: &HashSet<&str>,
107    answers: &mut Answers,
108    lookups: &mut Lookups<'_>,
109) -> rusqlite::Result<bool> {
110    for change in changes {
111        let bounded = crowded.contains(change.table.as_str());
112        for read in reads {
113            let found = if bounded {
114                read.affected(change, &mut |_| Ok(true))
115            } else {
116                read.affected(change, &mut |judging| answers.answer(judging, lookups))
117            };
118            match found {
119                Ok(false) => {}
120                Ok(true) | Err(NoAnswer::Stopped) => return Ok(true),
121                Err(NoAnswer::Failed(error)) => return Err(error),
122            }
123        }
124    }
125    Ok(false)
126}
127
128/// The answers to the lookups `affected` has run, keyed by lookup and value
129/// or by condition and values. Rows that share a value, and a row's old and
130/// new images that agree on the columns a condition names, share one run of
131/// the lookup.
132#[derive(Default)]
133pub struct Answers {
134    partners: HashMap<(usize, ValueKey<'static>), bool>,
135    rows: HashMap<(String, Vec<ValueKey<'static>>), bool>,
136}
137
138impl Answers {
139    fn answer(
140        &mut self,
141        judging: Judging<'_>,
142        lookups: &mut Lookups<'_>,
143    ) -> Result<bool, NoAnswer> {
144        match judging {
145            Judging::Partner(lookup, value) => {
146                let key = (std::ptr::from_ref(lookup) as usize, ValueKey::of(value).owned());
147                if let Some(found) = self.partners.get(&key) {
148                    return Ok(*found);
149                }
150                let found = lookups(judging)?;
151                self.partners.insert(key, found);
152                Ok(found)
153            }
154            Judging::Row(sql, parameters) => {
155                let key = (
156                    sql.to_owned(),
157                    parameters.iter().map(|value| ValueKey::of(value).owned()).collect(),
158                );
159                if let Some(found) = self.rows.get(&key) {
160                    return Ok(*found);
161                }
162                let found = lookups(judging)?;
163                self.rows.insert(key, found);
164                Ok(found)
165            }
166        }
167    }
168}
169
170/// A value by its type and bytes, as a hash key: two values are the same
171/// value exactly when their keys are equal. An integer and a real that
172/// compare equal are different values, which a query can tell apart.
173#[derive(Hash, PartialEq, Eq)]
174pub(crate) enum ValueKey<'a> {
175    Null,
176    Integer(i64),
177    Real(u64),
178    Text(Cow<'a, [u8]>),
179    Blob(Cow<'a, [u8]>),
180}
181
182impl<'a> ValueKey<'a> {
183    /// The key of `value`, which borrows its bytes.
184    pub(crate) fn of(value: &'a SqlValue) -> Self {
185        match value {
186            SqlValue::Null => Self::Null,
187            SqlValue::Integer(value) => Self::Integer(*value),
188            SqlValue::Real(value) => Self::Real(value.to_bits()),
189            SqlValue::Text(value) => Self::Text(Cow::Borrowed(value)),
190            SqlValue::Blob(value) => Self::Blob(Cow::Borrowed(value)),
191        }
192    }
193
194    /// The key with bytes of its own, to keep.
195    pub(crate) fn owned(self) -> ValueKey<'static> {
196        match self {
197            Self::Null => ValueKey::Null,
198            Self::Integer(value) => ValueKey::Integer(value),
199            Self::Real(bits) => ValueKey::Real(bits),
200            Self::Text(bytes) => ValueKey::Text(Cow::Owned(bytes.into_owned())),
201            Self::Blob(bytes) => ValueKey::Blob(Cow::Owned(bytes.into_owned())),
202        }
203    }
204
205    /// Whether `left` and `right` are the same value.
206    pub(crate) fn same(left: &SqlValue, right: &SqlValue) -> bool {
207        ValueKey::of(left) == ValueKey::of(right)
208    }
209}