Skip to main content

coven_merge/
removal.rs

1use crate::{Audience, ClaimOrder, MergeError, Parent, RowId, Slot};
2use std::collections::{BTreeMap, BTreeSet, VecDeque};
3
4/// The foreign key's ON DELETE action (§9.1).
5#[derive(Clone, Debug, PartialEq, Eq)]
6pub enum OnDelete {
7    /// A stale reference takes the child out.
8    Cascade,
9    /// A stale reference takes the child out.
10    Restrict,
11    /// A stale reference takes the child out.
12    NoAction,
13    /// Read null after a parent deletion if SQLite accepts it.
14    SetNull {
15        /// Whether the substitution passes the row’s CHECK constraints.
16        permitted: bool,
17    },
18}
19
20/// One reference in the merged values, before null substitution.
21#[derive(Clone, Debug, PartialEq, Eq)]
22pub struct Reference {
23    /// The parent generation carried by the winning reference's write.
24    pub parent: Parent,
25    /// The schema's ON DELETE action and substitution constraints.
26    pub on_delete: OnDelete,
27}
28
29/// What a reference reads as in the app's table. Substitution changes neither
30/// its winning write nor its timestamp; lost values stay as written (§9.1).
31#[derive(Clone, Debug, PartialEq, Eq)]
32pub enum ReferenceValue {
33    /// The original parent; stale references take their children out.
34    Original {
35        /// The original parent and generation.
36        parent: Parent,
37        /// The parent's carried generation has been deleted since.
38        stale: bool,
39    },
40    /// A set-null reference whose parent's generation was deleted.
41    Null,
42}
43
44impl ReferenceValue {
45    fn dependency(&self) -> Option<(&RowId, bool)> {
46        match self {
47            Self::Original { parent, stale } => Some((&parent.row, *stale)),
48            Self::Null => None,
49        }
50    }
51}
52
53/// Resolve a winning reference against its parent's generation, before CHECK
54/// and unique evaluation. Substitution affects the app's row, while lost values
55/// retain the written reference (§9.1).
56pub fn resolve_reference(
57    child: &RowId,
58    reference: &Reference,
59    parent_generation: u64,
60) -> Result<ReferenceValue, MergeError> {
61    reference.parent.validate_written(child)?;
62    let stale = parent_generation != reference.parent.generation;
63    if stale && matches!(reference.on_delete, OnDelete::SetNull { permitted: true }) {
64        return Ok(ReferenceValue::Null);
65    }
66    Ok(ReferenceValue::Original { parent: reference.parent.clone(), stale })
67}
68
69/// The row facts removal reads from merged state, never from prior removals.
70#[derive(Clone, Debug, PartialEq, Eq)]
71pub enum RemovalRow {
72    /// An even generation, including zero for a row never inserted.
73    Absent {
74        /// The row's current even generation.
75        generation: u64,
76    },
77    /// An odd generation, whether or not a rule currently removes the row.
78    Present {
79        /// The row's current odd generation.
80        generation: u64,
81        /// The claim order of the write `_coven_rows` records for this
82        /// generation (§15.4): the same order unique claims use, never a clock.
83        started: ClaimOrder,
84        /// Foreign-key names and their merged references.
85        references: BTreeMap<crate::ForeignKey, Reference>,
86        /// The slot deleting this row's circle, if any.
87        deleted_circle: Option<Slot>,
88    },
89}
90
91impl RemovalRow {
92    /// The generation in merged state, independent of removal rules.
93    pub fn generation(&self) -> u64 {
94        match self {
95            Self::Absent { generation } | Self::Present { generation, .. } => *generation,
96        }
97    }
98    /// Whether the row exists before the removal rules run.
99    pub fn present(&self) -> bool {
100        matches!(self, Self::Present { .. })
101    }
102}
103
104/// One unique value and the latest claim order of its current input setters.
105#[derive(Clone, Debug, PartialEq, Eq)]
106pub struct UniqueClaim {
107    /// Canonical equality encoding of the whole value: text compares by bytes,
108    /// since unique index terms are BINARY (§9.2). Non-conflicting nulls make no claim.
109    pub value: Vec<u8>,
110    /// The latest winning setter of any of the constraint's columns (§9.2).
111    pub order: ClaimOrder,
112}
113
114/// CHECK and unique results on merged values after reference substitution.
115#[derive(Clone, Debug, PartialEq, Eq, Default)]
116pub struct Constraints {
117    /// Names of all CHECK constraints the merged values fail.
118    pub failed_checks: BTreeSet<String>,
119    /// One non-null claim per constraint, identified by terms and predicate.
120    pub unique: BTreeMap<crate::UniqueConstraint, UniqueClaim>,
121}
122
123/// Rows competing for one unique value or one key across audiences.
124#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
125pub enum Group {
126    /// One unique constraint's value after reference substitution.
127    Claim {
128        /// The synced table's name.
129        table: String,
130        /// The audience within which the value must be unique.
131        audience: Audience,
132        /// The unique constraint's name.
133        constraint: crate::UniqueConstraint,
134        /// The canonical equality encoding used by [`UniqueClaim`].
135        value: Vec<u8>,
136    },
137    /// One primary key competing across its store and circle audiences.
138    Key {
139        /// The synced table's name.
140        table: String,
141        /// The encoded primary key.
142        key: Vec<u8>,
143    },
144}
145
146/// Abstract database view for the removal rules. All answers are functions of
147/// the merged state and applied admin slots, independent of which rows are removed.
148/// An adapter can prepare this view in memory; the merge itself performs no I/O.
149pub trait RemovalView {
150    /// Query failure, including the merge invariant errors checked here.
151    type Error: From<MergeError>;
152    /// Facts for a row. Unknown keys are `Absent { generation: 0 }`.
153    fn row(&self, row: &RowId) -> Result<RemovalRow, Self::Error>;
154    /// Evaluate constraints on merged values with these resolved references.
155    /// Substitution permission is supplied with the reference; CHECK results
156    /// here describe the merged values that remain after that decision.
157    fn constraints(
158        &self,
159        row: &RowId,
160        references: &BTreeMap<crate::ForeignKey, ReferenceValue>,
161    ) -> Result<Constraints, Self::Error>;
162    /// Rows whose references point at this row: the rows its removal takes
163    /// out with it. Include removed rows and references before substitution.
164    /// A row's parents come from [`Self::row`]; competition belongs in
165    /// [`Self::groups`], not in these edges.
166    fn children(&self, row: &RowId) -> Result<BTreeSet<RowId>, Self::Error>;
167    /// The row's key group and its current unique claim groups, using values
168    /// after reference substitution. Include removed rows' claims. The union
169    /// of the before/after views in [`recompute`] covers groups a row left.
170    fn groups(&self, row: &RowId) -> Result<BTreeSet<Group>, Self::Error>;
171    /// Every row in a competition group, including absent and removed rows,
172    /// regardless of rank. Region discovery visits each group once per view.
173    fn members(&self, group: &Group) -> Result<BTreeSet<RowId>, Self::Error>;
174}
175
176/// A rule recorded for a removed row. Every rule that holds at the end is
177/// included; unique/other-audience rules retain the once-judged decision.
178#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
179pub enum Rule {
180    /// The named foreign key is stale or its parent is absent/removed.
181    ForeignKey(crate::ForeignKey),
182    /// The named CHECK fails on merged values.
183    Check(String),
184    /// The kept entry deleting the row's circle.
185    DeletedCircle(Slot),
186    /// The same key won in another audience.
187    OtherAudience,
188    /// The named unique constraint lost its value to an earlier claim.
189    Unique(crate::UniqueConstraint),
190}
191
192/// Removals and reference readings for a closed region. Replace prior removal
193/// records for ALL rows in `region`, including rows absent from `removed`, so
194/// rows whose reasons cleared come back. Their merged states never change.
195#[derive(Clone, Debug, PartialEq, Eq, Default)]
196pub struct RemovalResult {
197    /// Rows recomputed, including deleted/unknown rows at the region's boundary.
198    pub region: BTreeSet<RowId>,
199    /// Removed rows with every final rule, plus the once-judged losers' rules.
200    pub removed: BTreeMap<RowId, BTreeSet<Rule>>,
201    /// References as they read in the app's table.
202    /// The original cell setters and timestamps are retained in `RowState`.
203    pub references: BTreeMap<RowId, BTreeMap<crate::ForeignKey, ReferenceValue>>,
204}
205
206/// Full row enumeration for comparison with incremental removal in tests.
207#[cfg(any(test, feature = "test-utils"))]
208pub trait FullRemovalView: RemovalView {
209    /// Every known row, including rows absent by their own generation.
210    fn rows(&self) -> Result<Vec<RowId>, Self::Error>;
211}
212
213/// Recompute every row using §8.4's three steps. The view controls iteration
214/// order; no choice of monotone rule order changes the result (proofs/merge.md B8).
215#[cfg(any(test, feature = "test-utils"))]
216pub fn removals<V: FullRemovalView>(view: &V) -> Result<RemovalResult, V::Error> {
217    let rows = view.rows()?;
218    let mut seen = BTreeSet::new();
219    for row in &rows {
220        if !seen.insert(row.clone()) {
221            return Err(MergeError::DuplicateRow(row.clone()).into());
222        }
223    }
224    let region = inputs(view, &mut BTreeSet::new(), seen.clone())?;
225    let mut order = rows;
226    order.extend(region.keys().filter(|r| !seen.contains(*r)).cloned());
227    evaluate(view, region, &order)
228}
229
230/// Recompute only the rows whose removal a change to `touched` can change: the
231/// touched rows and, through any chain, their children and rivals, in the
232/// union of the before/after views. Including old edges releases former losers
233/// and children when a claim/reference changes. Their parents and rivals in
234/// the after view, closed the same way, are evaluated with them, so
235/// proofs/merge.md B9 (`Audience.lean`, `removal_local`) gives exactly the full
236/// recomputation's answer there. Every other row's inputs and dependencies are
237/// unchanged, so its removal stands; a parent's other children are never read.
238/// The caller must include admin changes' rows among `touched`. No global row
239/// enumeration is performed by this function. Each competition group is
240/// expanded at most once in each view, so rivals are visited by group
241/// membership rather than by every pair of competing rows.
242pub fn recompute<E: From<MergeError>>(
243    before: &impl RemovalView<Error = E>,
244    after: &impl RemovalView<Error = E>,
245    touched: impl IntoIterator<Item = RowId>,
246) -> Result<RemovalResult, E> {
247    let mut before_groups = BTreeSet::new();
248    let mut after_groups = BTreeSet::new();
249    let mut changed: BTreeSet<RowId> = touched.into_iter().collect();
250    let mut pending: Vec<_> = changed.iter().cloned().collect();
251    while let Some(row) = pending.pop() {
252        let mut dependents = BTreeSet::new();
253        for (view, groups) in [
254            (before as &dyn RemovalView<Error = E>, &mut before_groups),
255            (after as &dyn RemovalView<Error = E>, &mut after_groups),
256        ] {
257            dependents.extend(view.children(&row)?);
258            dependents.extend(rivals(view, groups, &row)?);
259        }
260        for dependent in dependents {
261            if changed.insert(dependent.clone()) {
262                pending.push(dependent);
263            }
264        }
265    }
266    let region = inputs(after, &mut after_groups, changed)?;
267    let order: Vec<_> = region.keys().cloned().collect();
268    evaluate(after, region, &order)
269}
270
271/// The members of the row's groups not yet expanded in this view.
272fn rivals<E: From<MergeError>>(
273    view: &dyn RemovalView<Error = E>,
274    expanded: &mut BTreeSet<Group>,
275    row: &RowId,
276) -> Result<BTreeSet<RowId>, E> {
277    let mut rivals = BTreeSet::new();
278    for group in view.groups(row)? {
279        if expanded.insert(group.clone()) {
280            rivals.extend(view.members(&group)?);
281        }
282    }
283    Ok(rivals)
284}
285
286/// The rows' facts, with every parent and rival they read, transitively.
287fn inputs<E: From<MergeError>>(
288    view: &dyn RemovalView<Error = E>,
289    expanded: &mut BTreeSet<Group>,
290    rows: BTreeSet<RowId>,
291) -> Result<BTreeMap<RowId, RemovalRow>, E> {
292    let mut region = BTreeMap::new();
293    let mut pending: Vec<_> = rows.into_iter().collect();
294    while let Some(row) = pending.pop() {
295        if region.contains_key(&row) {
296            continue;
297        }
298        let facts = view.row(&row)?;
299        if facts.present() != crate::generation_present(facts.generation()) {
300            return Err(MergeError::GenerationParity(facts.generation()).into());
301        }
302        if let RemovalRow::Present { references, .. } = &facts {
303            pending.extend(references.values().map(|r| r.parent.row.clone()));
304        }
305        pending.extend(rivals(view, expanded, &row)?);
306        region.insert(row, facts);
307    }
308    Ok(region)
309}
310
311struct Facts {
312    row: RemovalRow,
313    constraints: Constraints,
314    references: BTreeMap<crate::ForeignKey, ReferenceValue>,
315}
316
317fn evaluate<E: From<MergeError>>(
318    view: &dyn RemovalView<Error = E>,
319    raw: BTreeMap<RowId, RemovalRow>,
320    order: &[RowId],
321) -> Result<RemovalResult, E> {
322    let mut facts = BTreeMap::new();
323    for (row, data) in &raw {
324        let mut resolved = BTreeMap::new();
325        if let RemovalRow::Present { references, .. } = data {
326            for (name, reference) in references {
327                let parent_gen = raw[&reference.parent.row].generation();
328                resolved.insert(name.clone(), resolve_reference(row, reference, parent_gen)?);
329            }
330        }
331        let constraints =
332            if data.present() { view.constraints(row, &resolved)? } else { Constraints::default() };
333        facts.insert(row.clone(), Facts { row: data.clone(), constraints, references: resolved });
334    }
335    let mut out: BTreeSet<_> =
336        facts.iter().filter(|(_, f)| !f.row.present()).map(|(r, _)| r.clone()).collect();
337    // Resolved references are the dependencies that propagate removal.
338    // Populate each parent's children in the view's order and reuse this
339    // index for both monotone passes.
340    let mut children = BTreeMap::<&RowId, Vec<&RowId>>::new();
341    for row in order {
342        for reference in facts[row].references.values() {
343            if let Some((parent, _)) = reference.dependency() {
344                children.entry(parent).or_default().push(row);
345            }
346        }
347    }
348    close(&facts, &children, order, &mut out);
349    let judged = judge_groups(&facts, &out);
350    out.extend(judged.keys().cloned());
351    close(&facts, &children, order, &mut out);
352    let mut result =
353        RemovalResult { region: raw.into_keys().collect(), ..RemovalResult::default() };
354    for (row, fact) in facts {
355        if fact.row.present() {
356            if out.contains(&row) {
357                let mut rules = monotone_rules(&fact, &out);
358                if let Some(unique) = judged.get(&row) {
359                    rules.extend(unique.iter().cloned());
360                }
361                result.removed.insert(row.clone(), rules);
362            }
363            result.references.insert(row, fact.references);
364        }
365    }
366    Ok(result)
367}
368
369fn close(
370    facts: &BTreeMap<RowId, Facts>,
371    children: &BTreeMap<&RowId, Vec<&RowId>>,
372    order: &[RowId],
373    out: &mut BTreeSet<RowId>,
374) {
375    let mut pending = VecDeque::new();
376    for row in order {
377        if out.contains(row) || !monotone_rules(&facts[row], out).is_empty() {
378            out.insert(row.clone());
379            pending.push_back(row);
380        }
381    }
382    while let Some(parent) = pending.pop_front() {
383        if let Some(children) = children.get(parent) {
384            for child in children {
385                // Any resolved parent going out suffices; no need to rescan
386                // the child's other references. Collect all rules at the end.
387                if out.insert((*child).clone()) {
388                    pending.push_back(child);
389                }
390            }
391        }
392    }
393}
394
395fn monotone_rules(fact: &Facts, out: &BTreeSet<RowId>) -> BTreeSet<Rule> {
396    let mut rules = BTreeSet::new();
397    for (name, reference) in &fact.references {
398        if let Some((parent, stale)) = reference.dependency() {
399            if stale || out.contains(parent) {
400                rules.insert(Rule::ForeignKey(name.clone()));
401            }
402        }
403    }
404    rules.extend(fact.constraints.failed_checks.iter().cloned().map(Rule::Check));
405    if let RemovalRow::Present { deleted_circle: Some(entry), .. } = fact.row {
406        rules.insert(Rule::DeletedCircle(entry));
407    }
408    rules
409}
410
411fn judge_groups(
412    facts: &BTreeMap<RowId, Facts>,
413    out: &BTreeSet<RowId>,
414) -> BTreeMap<RowId, BTreeSet<Rule>> {
415    let mut claims = BTreeMap::<Group, Vec<(&RowId, ClaimOrder)>>::new();
416    let mut keys = BTreeMap::<(&str, &[u8]), Vec<(&RowId, ClaimOrder)>>::new();
417    for (row, fact) in facts {
418        if out.contains(row) {
419            continue;
420        }
421        for (name, claim) in &fact.constraints.unique {
422            claims
423                .entry(Group::Claim {
424                    table: row.table.clone(),
425                    audience: row.audience.clone(),
426                    constraint: name.clone(),
427                    value: claim.value.clone(),
428                })
429                .or_default()
430                .push((row, claim.order));
431        }
432        if let RemovalRow::Present { started, .. } = fact.row {
433            keys.entry((&row.table, &row.key)).or_default().push((row, started));
434        }
435    }
436    let mut judged = BTreeMap::<RowId, BTreeSet<Rule>>::new();
437    for (group, members) in claims {
438        let Group::Claim { constraint, .. } = group else { unreachable!() };
439        let &(winner, _) = members
440            .iter()
441            .min_by_key(|(row, order)| (*order, &row.key))
442            .expect("a competition group contains a row");
443        for (row, _) in members {
444            if row != winner {
445                judged.entry(row.clone()).or_default().insert(Rule::Unique(constraint.clone()));
446            }
447        }
448    }
449    for members in keys.values() {
450        let &(winner, _) = members
451            .iter()
452            .min_by_key(|(row, order)| (row.audience != Audience::Store, *order, &row.audience))
453            .expect("a key group contains a row");
454        for (row, _) in members {
455            if *row != winner {
456                judged.entry((*row).clone()).or_default().insert(Rule::OtherAudience);
457            }
458        }
459    }
460    judged
461}
462
463#[cfg(test)]
464#[path = "removal_tests.rs"]
465mod tests;