Skip to main content

coven_database/
forget_records.rs

1//! The slot at which each kept change stopped being current, and forgetting
2//! the records no write still to be judged can name (§16.7).
3//!
4//! A change is current while it supplies its row's generation or sets one of
5//! its present cells. A change that stopped never becomes current again, so a
6//! genuine write names it only if it read less than the slot where it
7//! stopped; once every device that can still write has written past that
8//! slot, and this device's queued writes read past it, its record goes.
9
10use crate::sqlite::StoreSql;
11use crate::store_call::StoreCall;
12use crate::write_encoding::{counter, decoded, encoded};
13use crate::DbError;
14use coven_format::merge_fields;
15use coven_foundation::id_source::DeviceId;
16use coven_merge::{Audience, RowId, RowState, Slot, WriteId};
17use sqlive::rusqlite::params;
18use std::collections::{BTreeMap, BTreeSet};
19
20/// The other devices that can still write: every device besides this one
21/// not gone for good (§14.1), each with the slot whose entry added it, when
22/// known. Stored files (§17.10) and kept records (§16.7) wait for the same
23/// devices.
24#[derive(Clone, Debug, PartialEq, Eq)]
25pub struct Writers(BTreeMap<DeviceId, Option<u64>>);
26
27impl Writers {
28    /// The devices, each with the slot that added it, when known.
29    pub fn new(devices: BTreeMap<DeviceId, Option<u64>>) -> Self {
30        Self(devices)
31    }
32
33    /// The devices.
34    pub fn devices(&self) -> impl Iterator<Item = DeviceId> + '_ {
35        self.0.keys().copied()
36    }
37
38    /// The greatest slot every one of these devices has seen: each has landed
39    /// a write that read through it, or was added after it, so writes nothing
40    /// that read less. `reads` holds the `read_through` of each device's last
41    /// landed write, for those that landed one. With no other device, every
42    /// slot.
43    pub fn through(&self, reads: &BTreeMap<DeviceId, u64>) -> u64 {
44        self.0
45            .iter()
46            .map(|(device, added)| {
47                // A device added at slot `a` writes nothing that read less
48                // than `a`; one that landed nothing and whose adding slot
49                // isn't known has seen nothing.
50                let seen = added.map(|added| added.saturating_sub(1));
51                reads.get(device).copied().max(seen).unwrap_or(0)
52            })
53            .min()
54            .unwrap_or(u64::MAX)
55    }
56}
57
58/// The writes current in a row's merge state: the one that supplied its
59/// generation, and each one setting a present cell.
60fn current(state: &RowState<coven_format::value::Value>) -> BTreeSet<WriteId> {
61    state
62        .generations()
63        .get(&state.generation())
64        .copied()
65        .into_iter()
66        .chain(state.cells().values().map(|cell| cell.write))
67        .collect()
68}
69
70/// `write`, landing in `slot`, moved `before` to `after`: every other write
71/// current before and not after stopped being current at `slot`, and its
72/// kept record says so.
73pub(crate) fn stopped(
74    db: &StoreSql,
75    call: &StoreCall<'_>,
76    write: WriteId,
77    before: &RowState<coven_format::value::Value>,
78    after: &RowState<coven_format::value::Value>,
79    slot: Slot,
80) -> Result<(), DbError> {
81    let after = current(after);
82    for writer in current(before) {
83        if writer != write && !after.contains(&writer) {
84            stop(db, call, writer, before.row(), slot)?;
85        }
86    }
87    Ok(())
88}
89
90/// Record that `writer`'s change at `row`, named as the row is now, stopped
91/// being current at `slot`.
92fn stop(
93    db: &StoreSql,
94    call: &StoreCall<'_>,
95    writer: WriteId,
96    row: &RowId,
97    slot: Slot,
98) -> Result<(), DbError> {
99    let Some((_, table)) = crate::write_sources::kept_part(db, call, writer, row)? else {
100        // A migration write another raise replaced, or one a loaded
101        // snapshot covers without its part: no history holds its changes,
102        // so there is no record to mark (§9.5).
103        tracing::debug!(?writer, ?row, "a write stopped being current with no record held");
104        return Ok(());
105    };
106    stopped_at(db, writer, &row.audience, &table, &row.key, slot)
107}
108
109/// Whether `write` is current in a row it just changed, as `updates` leave
110/// the rows.
111pub(crate) fn applied<'a>(
112    write: WriteId,
113    mut updates: impl Iterator<Item = &'a RowState<coven_format::value::Value>>,
114) -> bool {
115    updates.any(|state| current(state).contains(&write))
116}
117
118/// `write`'s change at `table` and `key` in `audience`, as its write named
119/// them, stopped being current at `slot`, unless it had already stopped.
120pub(crate) fn stopped_at(
121    db: &StoreSql,
122    write: WriteId,
123    audience: &Audience,
124    table: &str,
125    key: &[u8],
126    slot: Slot,
127) -> Result<(), DbError> {
128    db.execute(
129        "UPDATE _coven_authored_changes SET stop=?5 WHERE write_id=?1 AND audience=?2 AND table_name=?3 AND key=?4 AND stop IS NULL",
130        params![
131            encoded(merge_fields::encode_write_id(&write))?,
132            audience,
133            table,
134            key,
135            slot.get().to_be_bytes().as_slice()
136        ],
137    )?;
138    Ok(())
139}
140
141/// `write` landed in `slot` and was consumed in `audiences` without being
142/// staged, as a write the cut-off refuses: none of its changes there ever
143/// became current, so each stops at its own slot.
144pub(crate) fn none_current(
145    db: &StoreSql,
146    write: WriteId,
147    audiences: &[Audience],
148    slot: Slot,
149) -> Result<(), DbError> {
150    let id = encoded(merge_fields::encode_write_id(&write))?;
151    for audience in audiences {
152        db.execute(
153            "UPDATE _coven_authored_changes SET stop=?3 WHERE write_id=?1 AND audience=?2 AND stop IS NULL",
154            params![id, audience, slot.get().to_be_bytes().as_slice()],
155        )?;
156    }
157    Ok(())
158}
159
160/// Forget every kept record no write still to be judged here can name: those
161/// that stopped being current at or below the slot every other device that
162/// can still write has seen, and this device's queued writes have read
163/// (§16.7). Then forget the applied-write entries no check reads any more
164/// (`forget_entries`). Run in the transaction that applies a slot, after its
165/// writes are judged; it deletes only what nothing can name, so no state is
166/// wrong before it runs.
167pub(crate) fn forget(
168    db: &StoreSql,
169    call: &StoreCall<'_>,
170    writers: &Writers,
171) -> Result<(), DbError> {
172    let mut reads = BTreeMap::new();
173    for device in writers.devices() {
174        if let Some(read) = crate::write_metadata::last_landed_read(db, device)? {
175            reads.insert(device, read);
176        }
177    }
178    let own = call
179        .local_device()
180        .ok_or(DbError::Invariant { what: "a writer connection observes this device" })?;
181    // No record stopped after the slot this device has applied, so looking
182    // past it would mark slots forgotten through before they come.
183    let seen = writers.through(&reads).min(crate::sequence::applied(db)?);
184    let through = match crate::write_metadata::queued_read(db, own)? {
185        Some(queued) => seen.min(queued),
186        None => seen,
187    };
188    let (from, newest) = forgotten_through(db)?;
189    if through <= from {
190        return crate::forget_entries::forget(db, through, newest);
191    }
192    let candidates = db.query(
193        "SELECT write_id,audience,table_name,key FROM _coven_authored_changes WHERE stop>?1 AND stop<=?2 ORDER BY write_id,audience",
194        params![from.to_be_bytes().as_slice(), through.to_be_bytes().as_slice()],
195        |r| {
196            Ok((
197                r.get::<_, Vec<u8>>(0)?,
198                crate::write_encoding::audience(r, 1)?,
199                r.get::<_, String>(2)?,
200                r.get::<_, Vec<u8>>(3)?,
201            ))
202        },
203    )?;
204    let mut parts = BTreeMap::<(Vec<u8>, Audience), Vec<(String, Vec<u8>)>>::new();
205    for (write, audience, table, key) in candidates {
206        parts.entry((write, audience)).or_default().push((table, key));
207    }
208    for ((write, audience), records) in parts {
209        forget_in_part(db, call, &write, &audience, records, through)?;
210    }
211    let newest = crate::forget_entries::passed(db, from, through, newest)?;
212    db.execute(
213        "INSERT INTO _coven_forgotten(singleton,through,newest) VALUES(1,?1,?2)
214         ON CONFLICT(singleton) DO UPDATE SET through=excluded.through,newest=excluded.newest",
215        params![through.to_be_bytes().as_slice(), newest],
216    )?;
217    crate::forget_entries::forget(db, through, newest)
218}
219
220/// Forget the `candidates` of one part that may go once every write still to
221/// be judged has read `through`. Another member's creation that this device
222/// lists proves that member's authorship in its snapshots (format D7.5), so
223/// it stays; a part received whole opens its leaves by their place among all
224/// its records, so its records go together, with its leaf hashes, or stay.
225fn forget_in_part(
226    db: &StoreSql,
227    call: &StoreCall<'_>,
228    write: &[u8],
229    audience: &Audience,
230    candidates: Vec<(String, Vec<u8>)>,
231    through: u64,
232) -> Result<(), DbError> {
233    let id = decoded(merge_fields::decode_write_id(write))?;
234    let header = crate::transaction_constants::authored_part(db, call, write, audience)?
235        .ok_or(DbError::DamagedDatabase)?;
236    let version = merge_fields::decode_write_header(&header)?.schema_version;
237    let evidence = crate::authorship::keeps_evidence(db, call, id)?;
238    let protected = |table: &str, key: &[u8]| -> Result<bool, DbError> {
239        if !evidence {
240            return Ok(false);
241        }
242        let Some(table) = crate::source_names::table(
243            db,
244            version,
245            table,
246            crate::transaction_constants::schema_version(db, call)?,
247        )?
248        else {
249            return Ok(false);
250        };
251        let row = RowId { table, key: key.to_vec(), audience: audience.clone() };
252        Ok(crate::ownership::creation(db, &row)?.is_some_and(|creation| creation.write == id))
253    };
254    let leaves = crate::authorship::holds_leaves(db, id, audience)?;
255    let records = if leaves {
256        let mut records = Vec::new();
257        for (table, key, stop) in db.query(
258            "SELECT table_name,key,stop FROM _coven_authored_changes WHERE write_id=?1 AND audience=?2",
259            params![write, audience],
260            |r| {
261                Ok((
262                    r.get::<_, String>(0)?,
263                    r.get::<_, Vec<u8>>(1)?,
264                    r.get::<_, Option<Vec<u8>>>(2)?.map(counter).transpose()?,
265                ))
266            },
267        )? {
268            if stop.is_none_or(|stop| stop > through) || protected(&table, &key)? {
269                return Ok(());
270            }
271            records.push((table, key));
272        }
273        records
274    } else {
275        let mut records = Vec::new();
276        for (table, key) in candidates {
277            if !protected(&table, &key)? {
278                records.push((table, key));
279            }
280        }
281        records
282    };
283    for (table, key) in records {
284        db.execute(
285            "DELETE FROM _coven_authored_changes WHERE write_id=?1 AND audience=?2 AND table_name=?3 AND key=?4",
286            params![write, audience, table, key],
287        )?;
288    }
289    let emptied = db.execute(
290        "DELETE FROM _coven_authored_parts WHERE write_id=?1 AND audience=?2
291         AND NOT EXISTS(SELECT 1 FROM _coven_authored_changes c WHERE c.write_id=?1 AND c.audience=?2)",
292        params![write, audience],
293    )?;
294    if emptied > 0 {
295        call.forget_authored_part(write, audience);
296        if leaves {
297            crate::authorship::forget_part(db, id, audience)?;
298        }
299    }
300    Ok(())
301}
302
303/// The slot through which this device has looked at every stopped record
304/// and every applied-write entry, zero before it looked at any, and the
305/// latest stamped entry at or below it.
306fn forgotten_through(db: &StoreSql) -> Result<(u64, Option<i64>), DbError> {
307    let forgotten = db
308        .query("SELECT through,newest FROM _coven_forgotten WHERE singleton=1", [], |r| {
309            Ok((counter(r.get(0)?)?, r.get::<_, Option<i64>>(1)?))
310        })?
311        .pop();
312    Ok(forgotten.unwrap_or((0, None)))
313}
314
315/// Records and entries at or below the slot looked at through may have
316/// become forgettable, or come back: a loaded snapshot brings the records and
317/// entries its writer still held, a dropped table's creations no longer
318/// protect their records, and merge rows a reload or a migration deletes no
319/// longer name their writes. The next slot looks at every one again.
320pub(crate) fn look_again(db: &StoreSql) -> Result<(), DbError> {
321    db.execute("DELETE FROM _coven_forgotten", [])?;
322    Ok(())
323}
324
325#[cfg(test)]
326#[path = "forget_records_tests.rs"]
327pub(crate) mod tests;