1use crate::{Audience, ClaimOrder, MergeError, Parent, RowId, Slot};
2use std::collections::{BTreeMap, BTreeSet, VecDeque};
3
4#[derive(Clone, Debug, PartialEq, Eq)]
6pub enum OnDelete {
7 Cascade,
9 Restrict,
11 NoAction,
13 SetNull {
15 permitted: bool,
17 },
18}
19
20#[derive(Clone, Debug, PartialEq, Eq)]
22pub struct Reference {
23 pub parent: Parent,
25 pub on_delete: OnDelete,
27}
28
29#[derive(Clone, Debug, PartialEq, Eq)]
32pub enum ReferenceValue {
33 Original {
35 parent: Parent,
37 stale: bool,
39 },
40 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
53pub 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#[derive(Clone, Debug, PartialEq, Eq)]
71pub enum RemovalRow {
72 Absent {
74 generation: u64,
76 },
77 Present {
79 generation: u64,
81 started: ClaimOrder,
84 references: BTreeMap<crate::ForeignKey, Reference>,
86 deleted_circle: Option<Slot>,
88 },
89}
90
91impl RemovalRow {
92 pub fn generation(&self) -> u64 {
94 match self {
95 Self::Absent { generation } | Self::Present { generation, .. } => *generation,
96 }
97 }
98 pub fn present(&self) -> bool {
100 matches!(self, Self::Present { .. })
101 }
102}
103
104#[derive(Clone, Debug, PartialEq, Eq)]
106pub struct UniqueClaim {
107 pub value: Vec<u8>,
110 pub order: ClaimOrder,
112}
113
114#[derive(Clone, Debug, PartialEq, Eq, Default)]
116pub struct Constraints {
117 pub failed_checks: BTreeSet<String>,
119 pub unique: BTreeMap<crate::UniqueConstraint, UniqueClaim>,
121}
122
123#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
125pub enum Group {
126 Claim {
128 table: String,
130 audience: Audience,
132 constraint: crate::UniqueConstraint,
134 value: Vec<u8>,
136 },
137 Key {
139 table: String,
141 key: Vec<u8>,
143 },
144}
145
146pub trait RemovalView {
150 type Error: From<MergeError>;
152 fn row(&self, row: &RowId) -> Result<RemovalRow, Self::Error>;
154 fn constraints(
158 &self,
159 row: &RowId,
160 references: &BTreeMap<crate::ForeignKey, ReferenceValue>,
161 ) -> Result<Constraints, Self::Error>;
162 fn children(&self, row: &RowId) -> Result<BTreeSet<RowId>, Self::Error>;
167 fn groups(&self, row: &RowId) -> Result<BTreeSet<Group>, Self::Error>;
171 fn members(&self, group: &Group) -> Result<BTreeSet<RowId>, Self::Error>;
174}
175
176#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
179pub enum Rule {
180 ForeignKey(crate::ForeignKey),
182 Check(String),
184 DeletedCircle(Slot),
186 OtherAudience,
188 Unique(crate::UniqueConstraint),
190}
191
192#[derive(Clone, Debug, PartialEq, Eq, Default)]
196pub struct RemovalResult {
197 pub region: BTreeSet<RowId>,
199 pub removed: BTreeMap<RowId, BTreeSet<Rule>>,
201 pub references: BTreeMap<RowId, BTreeMap<crate::ForeignKey, ReferenceValue>>,
204}
205
206#[cfg(any(test, feature = "test-utils"))]
208pub trait FullRemovalView: RemovalView {
209 fn rows(&self) -> Result<Vec<RowId>, Self::Error>;
211}
212
213#[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
230pub 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
271fn 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
286fn 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 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 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;