coven_merge/
removal.rs

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

coven_merge/
removal.rs
