diff options
Diffstat (limited to 'src/federation/store/memory.rs')
| -rw-r--r-- | src/federation/store/memory.rs | 114 |
1 files changed, 102 insertions, 12 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index bc0c672..7527a44 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -19,7 +19,7 @@ pub(crate) enum Refusal { NotAbove, /// Its history takes it, but the node doesn't, by what it took before. Own, - /// Its operator had the node drop it. + /// Its operator had the node drop it, or one writing what it writes (`Fold::writes`). Dropped, } @@ -68,6 +68,9 @@ pub(crate) struct Store<F: Fold> { waits_for: HashMap<Id, BTreeSet<Id>>, /// The events refused, and why. refused: HashMap<Id, Refusal>, + /// Of the events refused as dropped, those writing what other events may write alike, + /// and what each writes (`Fold::writes`): an event writing that is refused as dropped. + writes: HashMap<Id, Id>, /// What a move to a checkpoint forgot that came before its heads: held as accounted /// for, and nothing after the checkpoint builds on it. forgotten: HashSet<Id>, @@ -112,6 +115,7 @@ impl<F: Fold> Store<F> { waiting: HashMap::new(), waits_for: HashMap::new(), refused: HashMap::new(), + writes: HashMap::new(), forgotten: HashSet::new(), }) } @@ -443,6 +447,12 @@ impl<F: Fold> Store<F> { } fn judged(&mut self, id: Id, event: Event, taken: &mut Vec<Id>) -> Offered { + if let Some(writes) = F::writes(&event.bytes) + && self.writes.values().any(|dropped| *dropped == writes) + { + self.writes.insert(id, writes); + return self.refuse(id, Refusal::Dropped); + } if let Some(refused) = event .dependencies .iter() @@ -503,22 +513,31 @@ impl<F: Fold> Store<F> { self.refused.iter() } - /// Drops events taken after the checkpoint, with everything built on them, as their - /// operator has the node do: it refuses them from then on, until its operator allows - /// them again. What the checkpoint keeps, or holds by ID, it drops not: every event - /// after it builds on that. Returns what it dropped, in the order taken. + /// Drops events taken after the checkpoint, those writing what they write alike + /// (`Fold::writes`), and everything built on them, as their operator has the node do: + /// it refuses them from then on, and whatever writes what they write, until its + /// operator allows them again. What the checkpoint keeps, or holds by ID, it drops not: + /// every event after it builds on that. Returns what it dropped, in the order taken. pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result<Vec<Id>, Refused> { if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) { return Err(Refused::new(format!( "{id} isn't an event taken after the checkpoint" ))); } + let named: HashSet<Id> = ids + .iter() + .filter_map(|id| F::writes(&self.events[id].bytes)) + .collect(); let mut dropped: HashMap<Id, Refusal> = ids.iter().map(|id| (*id, Refusal::Dropped)).collect(); for id in &self.order { if dropped.contains_key(id) { continue; } + if F::writes(&self.events[id].bytes).is_some_and(|writes| named.contains(&writes)) { + dropped.insert(*id, Refusal::Dropped); + continue; + } if let Some(on) = self.events[id] .dependencies .iter() @@ -536,7 +555,11 @@ impl<F: Fold> Store<F> { .collect(); self.order.retain(|id| !dropped.contains_key(id)); for id in &order { - self.events.remove(id); + if let Some(event) = self.events.remove(id) + && let Some(writes) = F::writes(&event.bytes) + { + self.writes.insert(*id, writes); + } } self.refused.extend(dropped); let mut state = self.start.clone(); @@ -548,14 +571,27 @@ impl<F: Fold> Store<F> { } /// Takes back what the node refused of its own, or dropped, as its operator says - /// otherwise: `ids`, and what was refused for being built on them. They are taken when - /// offered again, where the store takes them then. + /// otherwise: `ids`, what was dropped for writing what a dropped one among them writes, + /// and what was refused for being built on them. They are taken when offered again, + /// where the store takes them then. pub(crate) fn allow(&mut self, ids: &[Id]) { let mut todo: Vec<Id> = ids .iter() .filter(|id| matches!(self.refused.get(id), Some(Refusal::Own | Refusal::Dropped))) .copied() .collect(); + let lifted: HashSet<Id> = todo + .iter() + .filter_map(|id| self.writes.get(id)) + .copied() + .collect(); + todo.extend( + self.writes + .iter() + .filter(|(_, writes)| lifted.contains(writes)) + .map(|(id, _)| *id), + ); + self.writes.retain(|_, writes| !lifted.contains(writes)); while let Some(id) = todo.pop() { self.refused.remove(&id); todo.extend( @@ -568,17 +604,31 @@ impl<F: Fold> Store<F> { } /// Itself, refusing `own` as its node refused them of its own and `dropped` as its - /// operator had it drop them: a store read anew, before anything is offered to it, - /// refuses what its node refused so before, whatever order the events come in + /// operator had it drop them, and whatever writes what one of `writes`, each a dropped + /// event and what it writes, does: a store read anew, before anything is offered to + /// it, refuses what its node refused so before, whatever order the events come in /// (`docs/store.md`, A node's own). - pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id]) -> Self { + pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id], writes: &[(Id, Id)]) -> Self { self.refused .extend(own.iter().map(|id| (*id, Refusal::Own))); self.refused .extend(dropped.iter().map(|id| (*id, Refusal::Dropped))); + self.writes.extend(writes.iter().copied()); self } + /// Of what its operator had it drop, the events writing what others may write alike, + /// each with what it writes, in the order of their IDs. + pub(crate) fn dropped_writes(&self) -> Vec<(Id, Id)> { + let mut writes: Vec<(Id, Id)> = self + .writes + .iter() + .map(|(id, writes)| (*id, *writes)) + .collect(); + writes.sort_unstable(); + writes + } + /// What its node refused of its own, and what its operator had it drop. pub(crate) fn own(&self) -> (Vec<Id>, Vec<Id>) { let of = |refusal: Refusal| { @@ -778,6 +828,46 @@ mod tests { assert!(store.drop_taken(&[root]).is_err()); } + /// An event its operator had the node drop writing what others write alike: they are + /// dropped with it, taken or offered later, and whatever writes it, before or after a + /// store is read anew, until its operator allows one. + #[test] + fn a_drop_refuses_whatever_writes_what_the_dropped_write() { + let mut store = store(); + let root = store.id(); + let mark = taken(store.offer(testfold::put(&[root], "mark", "1"))); + let one = testfold::era(&[root], 1, "one"); + let again = testfold::era(&[mark], 1, "one"); + let anew = testfold::era(&[root, mark], 1, "one"); + let one_id = taken(store.offer(one.clone())); + let again_id = taken(store.offer(again)); + assert_eq!(store.drop_taken(&[one_id]).unwrap(), vec![one_id, again_id]); + assert_eq!(store.state().era().0, 0); + assert_eq!( + store.offer(anew.clone()), + Offered::Refused(Refusal::Dropped) + ); + assert_eq!(store.dropped_writes().len(), 3); + // Read anew: one writing the same, never offered before, is refused as dropped. + let (own, drops) = store.own(); + let mut read = self::store().refusing(&own, &drops, &store.dropped_writes()); + taken(read.offer(testfold::put(&[root], "mark", "1"))); + let later = taken(read.offer(testfold::put(&[mark], "later", "1"))); + assert_eq!( + read.offer(testfold::era(&[later], 1, "one")), + Offered::Refused(Refusal::Dropped) + ); + assert!(matches!( + read.offer(testfold::era(&[root], 1, "two")), + Offered::Taken(_) + )); + // Allowed again: all of them. + store.allow(&[one_id]); + assert!(store.dropped_writes().is_empty()); + assert!(matches!(store.offer(one), Offered::Taken(_))); + assert!(matches!(store.offer(anew), Offered::Taken(_))); + } + #[test] fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() { let mut store = store(); @@ -794,7 +884,7 @@ mod tests { (&[Id::of(&other)][..], &[dropped][..]) ); // Read anew, the other era first: refused as before. - let mut anew = self::store().refusing(&own, &drops); + let mut anew = self::store().refusing(&own, &drops, &store.dropped_writes()); assert_eq!(anew.offer(other), Offered::Refused(Refusal::Own)); assert_eq!( anew.offer(testfold::put(&[root], "b", "1")), |
