aboutsummaryrefslogtreecommitdiffstats
path: root/src/federation/store
diff options
context:
space:
mode:
Diffstat (limited to 'src/federation/store')
-rw-r--r--src/federation/store/memory.rs189
-rw-r--r--src/federation/store/mod.rs10
-rw-r--r--src/federation/store/testfold.rs12
3 files changed, 192 insertions, 19 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index 7527a44..f721b47 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -34,6 +34,9 @@ pub(crate) enum Offered {
Waiting,
/// Refused, and why; what waited on it is refused with it.
Refused(Refusal),
+ /// Held back, neither taken nor refused: the store stopped at an event it can't judge
+ /// (`Fold::stops`), this one or one before.
+ Stopped,
}
/// A checkpoint built: its bytes, and the events it keeps, by ID.
@@ -74,6 +77,12 @@ pub(crate) struct Store<F: Fold> {
/// 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>,
+ /// The event the store stopped at, and why (`Fold::stops`); and what it holds back
+ /// since, that one first, in the order offered: it takes nothing and refuses nothing
+ /// until its operator has it drop that one.
+ stopped: Option<(Id, String)>,
+ held_back: Vec<(Id, Event)>,
+ holding_back: HashSet<Id>,
}
impl<F: Fold> Store<F> {
@@ -117,6 +126,9 @@ impl<F: Fold> Store<F> {
refused: HashMap::new(),
writes: HashMap::new(),
forgotten: HashSet::new(),
+ stopped: None,
+ held_back: Vec::new(),
+ holding_back: HashSet::new(),
})
}
@@ -202,6 +214,14 @@ impl<F: Fold> Store<F> {
self.waiting.contains_key(id)
}
+ /// The event the store stopped at, and why, where it stopped (`Fold::stops`); and how
+ /// many events it holds back, that one among them.
+ pub(crate) fn stopped(&self) -> Option<(&Id, &str, usize)> {
+ self.stopped
+ .as_ref()
+ .map(|(id, why)| (id, why.as_str(), self.held_back.len()))
+ }
+
/// What a new event builds on: the events nothing else held builds on, or the
/// checkpoint's heads where nothing came after it.
pub(crate) fn heads(&self) -> Vec<Id> {
@@ -240,6 +260,9 @@ impl<F: Fold> Store<F> {
if self.waiting.contains_key(&id) {
return Offered::Waiting;
}
+ if self.holding_back.contains(&id) {
+ return Offered::Stopped;
+ }
if bytes.len() > F::LARGEST {
return self.refuse(id, Refusal::None);
}
@@ -447,6 +470,9 @@ impl<F: Fold> Store<F> {
}
fn judged(&mut self, id: Id, event: Event, taken: &mut Vec<Id>) -> Offered {
+ if self.stopped.is_some() {
+ return self.hold_back(id, event);
+ }
if let Some(writes) = F::writes(&event.bytes)
&& self.writes.values().any(|dropped| *dropped == writes)
{
@@ -498,6 +524,10 @@ impl<F: Fold> Store<F> {
if let Err(why) = F::judge(&at, &id, &event.bytes) {
return self.refuse(id, Refusal::Judged(why));
}
+ if let Some(why) = F::stops(&at, &self.state, &id, &event.bytes) {
+ self.stopped = Some((id, why));
+ return self.hold_back(id, event);
+ }
if !F::keeps(&self.state, &id, &event.bytes) {
return self.refuse(id, Refusal::Own);
}
@@ -508,6 +538,14 @@ impl<F: Fold> Store<F> {
Offered::Taken(vec![id])
}
+ /// Holds an event back, the store stopped.
+ fn hold_back(&mut self, id: Id, event: Event) -> Offered {
+ if self.holding_back.insert(id) {
+ self.held_back.push((id, event));
+ }
+ Offered::Stopped
+ }
+
/// The events refused, and why: for reports.
pub(crate) fn refused(&self) -> impl Iterator<Item = (&Id, &Refusal)> {
self.refused.iter()
@@ -517,19 +555,31 @@ impl<F: Fold> Store<F> {
/// (`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.
+ /// every event after it builds on that. It drops the event it stopped at alike, or
+ /// refuses it for building on what it drops: then it takes again, and is offered what
+ /// it held back anew. Returns what it dropped, in the order taken, then the event it
+ /// stopped at, where it dropped that.
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)) {
+ let stopped = self.stopped.as_ref().map(|(id, _)| *id);
+ if let Some(id) = ids
+ .iter()
+ .find(|id| !self.events.contains_key(id) && Some(**id) != stopped)
+ {
return Err(Refused::new(format!(
- "{id} isn't an event taken after the checkpoint"
+ "{id} isn't an event taken after the checkpoint, nor the one the store stopped at"
)));
}
- let named: HashSet<Id> = ids
+ let taken: Vec<Id> = ids
+ .iter()
+ .filter(|id| self.events.contains_key(id))
+ .copied()
+ .collect();
+ let named: HashSet<Id> = taken
.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();
+ taken.iter().map(|id| (*id, Refusal::Dropped)).collect();
for id in &self.order {
if dropped.contains_key(id) {
continue;
@@ -547,26 +597,52 @@ impl<F: Fold> Store<F> {
dropped.insert(*id, Refusal::BuiltOn(on));
}
}
- let order: Vec<Id> = self
+ let mut order: Vec<Id> = self
.order
.iter()
.filter(|id| dropped.contains_key(id))
.copied()
.collect();
- self.order.retain(|id| !dropped.contains_key(id));
- for id in &order {
- if let Some(event) = self.events.remove(id)
- && let Some(writes) = F::writes(&event.bytes)
- {
- self.writes.insert(*id, writes);
+ if !order.is_empty() {
+ self.order.retain(|id| !dropped.contains_key(id));
+ for id in &order {
+ 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();
+ for id in &self.order {
+ F::add(&mut state, id, &self.events[id].bytes);
+ }
+ self.state = state;
}
- self.refused.extend(dropped);
- let mut state = self.start.clone();
- for id in &self.order {
- F::add(&mut state, id, &self.events[id].bytes);
+ if let Some(stopped) = stopped {
+ let dropping = ids.contains(&stopped);
+ let on_dropped = self.held_back[0]
+ .1
+ .dependencies
+ .iter()
+ .any(|dependency| self.refused.contains_key(dependency));
+ if dropping || on_dropped {
+ self.stopped = None;
+ self.holding_back.clear();
+ let mut held_back = std::mem::take(&mut self.held_back);
+ if dropping {
+ let (_, event) = held_back.remove(0);
+ if let Some(writes) = F::writes(&event.bytes) {
+ self.writes.insert(stopped, writes);
+ }
+ self.refuse(stopped, Refusal::Dropped);
+ order.push(stopped);
+ }
+ for (_, event) in held_back {
+ self.offer(event.bytes);
+ }
+ }
}
- self.state = state;
Ok(order)
}
@@ -868,6 +944,85 @@ mod tests {
assert!(matches!(store.offer(anew), Offered::Taken(_)));
}
+ /// An event the store can't judge, that its node would take: it stops there, holding
+ /// back what comes after, taken or refused by nobody, until its operator has it drop
+ /// that one; then it takes them, as before the stop. Beside what it took, the event
+ /// is refused of its own.
+ #[test]
+ fn a_store_stops_at_what_it_cant_judge_until_its_operator_drops_it() {
+ let mut store = store();
+ let root = store.id();
+ let mark = taken(store.offer(testfold::put(&[root], "mark", "1")));
+ let new = testfold::era(&[mark], 1, "new");
+ let at = Id::of(&new);
+ let on = testfold::put(&[at], "a", "1");
+ // Waiting for it before the stop: refused once it is dropped.
+ assert_eq!(store.offer(on.clone()), Offered::Waiting);
+ assert_eq!(store.offer(new.clone()), Offered::Stopped);
+ let (id, why, held) = store.stopped().expect("stopped");
+ assert_eq!((*id, why, held), (at, "era 1, tagged new", 1));
+ // Nothing taken, nothing refused, junk or not.
+ let later = testfold::put(&[mark], "b", "1");
+ let junk = testfold::junk(&[mark]);
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.offer(junk.clone()), Offered::Stopped);
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.offer(new.clone()), Offered::Stopped);
+ assert_eq!(store.taken(), &[mark]);
+ assert_eq!(store.refused().count(), 0);
+ assert_eq!(store.stopped().map(|(_, _, held)| held), Some(3));
+ assert!(store.drop_taken(&[Id::of(&later)]).is_err());
+ // Dropped: what it held back is taken, or refused, and what waited for it refused.
+ assert_eq!(store.drop_taken(&[at]), Ok(vec![at]));
+ assert!(store.stopped().is_none());
+ assert_eq!(store.taken(), &[mark, Id::of(&later)]);
+ assert!(matches!(
+ store.refusal(&Id::of(&junk)),
+ Some(Refusal::Judged(_))
+ ));
+ assert_eq!(store.refusal(&Id::of(&on)), Some(&Refusal::BuiltOn(at)));
+ assert_eq!(store.own(), (Vec::new(), vec![at]));
+ // Of what writes what it writes, whoever wrote it: dropped.
+ assert_eq!(
+ store.offer(testfold::era(&[root], 1, "new")),
+ Offered::Refused(Refusal::Dropped)
+ );
+ // Allowed again: it stops there once more.
+ store.allow(&[at]);
+ assert_eq!(store.offer(new), Offered::Stopped);
+ assert_eq!(store.offer(on), Offered::Stopped);
+ // Beside an era it took, it is refused of its own, and nothing stops.
+ let mut beside = self::store();
+ let one = taken(beside.offer(testfold::era(&[root], 1, "one")));
+ let new = testfold::era(&[root], 1, "new");
+ assert_eq!(beside.offer(new.clone()), Offered::Refused(Refusal::Own));
+ assert!(beside.stopped().is_none());
+ // Its operator drops the era it took and allows the other: it stops there.
+ beside.drop_taken(&[one]).unwrap();
+ beside.allow(&[Id::of(&new)]);
+ assert_eq!(beside.offer(new), Offered::Stopped);
+ }
+
+ /// The store stopped at an event built on one its operator has it drop: it refuses it
+ /// with the rest, and takes again.
+ #[test]
+ fn a_drop_under_the_event_a_store_stopped_at_takes_it_with_it() {
+ let mut store = store();
+ let root = store.id();
+ let mark = taken(store.offer(testfold::put(&[root], "mark", "1")));
+ let new = Id::of(&testfold::era(&[mark], 1, "new"));
+ assert_eq!(
+ store.offer(testfold::era(&[mark], 1, "new")),
+ Offered::Stopped
+ );
+ let later = testfold::put(&[root], "b", "1");
+ assert_eq!(store.offer(later.clone()), Offered::Stopped);
+ assert_eq!(store.drop_taken(&[mark]), Ok(vec![mark]));
+ assert!(store.stopped().is_none());
+ assert_eq!(store.refusal(&new), Some(&Refusal::BuiltOn(mark)));
+ assert_eq!(store.taken(), &[Id::of(&later)]);
+ }
+
#[test]
fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() {
let mut store = store();
diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs
index 4027fb9..c80f5b8 100644
--- a/src/federation/store/mod.rs
+++ b/src/federation/store/mod.rs
@@ -82,13 +82,21 @@ pub(crate) trait Fold {
/// What the event builds on; `None` where its bytes are none of this fold's events.
fn dependencies(event: &[u8]) -> Option<Vec<Id>>;
- /// Whether the event is taken where its history reads as `at`.
+ /// Whether the event is taken where its history reads as `at`, as far as the fold
+ /// reads it (`stops`).
fn judge(at: &Self::State, id: &Id, event: &[u8]) -> Result<(), Refused>;
/// Adds the event, whose dependencies are added already. Events neither of which
/// builds on the other may come in either order: the state is the same.
fn add(state: &mut Self::State, id: &Id, event: &[u8]);
+ /// Why a node whose store reads as `now` can't judge an event its history, read as
+ /// `at`, doesn't refuse, where it can't: one only a fold knowing more reads, that the
+ /// node would take. The store stops at it (`docs/store.md`, A node's own).
+ fn stops(_at: &Self::State, _now: &Self::State, _id: &Id, _event: &[u8]) -> Option<String> {
+ None
+ }
+
/// Whether a node whose store reads as `now` takes an event its history takes.
fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
true
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs
index 2478c0a..17e039b 100644
--- a/src/federation/store/testfold.rs
+++ b/src/federation/store/testfold.rs
@@ -7,7 +7,8 @@
//! * `lock`: a key locked for good.
//! * `era`: era `n`, taken only where `n` is one past the era at its history; of two of one
//! number, a node keeps the first it takes (as the federation's versions). Eras of one
-//! number and tag write the same: a drop of one refuses them all.
+//! number and tag write the same: a drop of one refuses them all. One tagged `new` is
+//! of a fold knowing more: a node that would take it stops at it.
//! * `cut`: cut `n`, naming heads to move the store to, as `era`: above the heads the latest
//! cut of its history names, and holding that cut (or after the checkpoint the state
//! starts from, where it holds none); none of them in another's history. It must be above
@@ -347,6 +348,15 @@ impl Fold for TestFold {
}
}
+ fn stops(at: &State, now: &State, _id: &Id, event: &[u8]) -> Option<String> {
+ match decode(event)? {
+ (_, Kind::Era { n, tag }) if tag == "new" && now.era == at.era => {
+ Some(format!("era {n}, tagged new"))
+ }
+ _ => None,
+ }
+ }
+
fn keeps(now: &State, _id: &Id, event: &[u8]) -> bool {
match decode(event) {
Some((_, Kind::Era { n, tag })) => {