aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store/memory.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/store/memory.rs')
-rw-r--r--src/federation/store/memory.rs114
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")),