aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/federation/store/testfold.rs106
1 files changed, 83 insertions, 23 deletions
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs
index 68397e7..7e3b703 100644
--- a/src/federation/store/testfold.rs
+++ b/src/federation/store/testfold.rs
@@ -7,7 +7,10 @@
//! * `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).
-//! * `cut`: cut `n`, naming heads to move the store to, as `era`; it must be above them.
+//! * `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
+//! them.
//! * `junk`: refused wherever it is.
use std::collections::{BTreeMap, BTreeSet};
@@ -124,14 +127,19 @@ pub(crate) struct State {
era: u64,
tags: BTreeMap<u64, String>,
cut: u64,
+ /// The heads each cut names, by its number; and each cut, with its number.
cuts: BTreeMap<u64, Vec<Id>>,
+ cut_events: BTreeMap<Id, u64>,
}
impl State {
/// Whether `b` is in the history of `a`.
pub(crate) fn built_on(&self, a: &Id, b: &Id) -> bool {
+ // What the checkpoint keeps is in the history of every event after it. Of the
+ // checkpoint's heads, the state holds no history: as it tells, none builds on what
+ // the checkpoint keeps, nor on another head.
if self.before.contains(b) {
- return !self.before.contains(a);
+ return self.graph.contains_key(a) && !self.before.contains(a);
}
let mut seen = BTreeSet::new();
let mut todo: Vec<Id> = self.graph.get(a).cloned().unwrap_or_default();
@@ -174,29 +182,80 @@ impl State {
(self.era, self.tags.get(&self.era))
}
- /// Whether `heads` may be a checkpoint's here, and the state is above them.
- fn above(&self, heads: &[Id]) -> bool {
- // The heads of the checkpoint the state starts from count as after the checkpoint
- // current at them, so that a node starting from it judges the cut naming it as
- // every node does.
- let after = |id: &Id| {
- (self.graph.contains_key(id) && !self.before.contains(id)) || self.at.contains(id)
- };
- if heads.is_empty() || !heads.iter().all(after) {
- return false;
+ pub(crate) fn cut(&self) -> u64 {
+ self.cut
+ }
+
+ /// The events here above `heads` (`docs/store.md`, Events): each with them all in its
+ /// history, and each of its dependencies one of them or above them.
+ fn above(&self, heads: &BTreeSet<Id>) -> BTreeSet<Id> {
+ let mut above = BTreeSet::new();
+ loop {
+ let more: Vec<Id> = self
+ .graph
+ .iter()
+ .filter(|(id, deps)| {
+ !above.contains(*id)
+ && !heads.contains(*id)
+ && !deps.is_empty()
+ && deps
+ .iter()
+ .all(|dep| heads.contains(dep) || above.contains(dep))
+ && (deps.iter().any(|dep| above.contains(dep))
+ || heads.iter().all(|head| deps.contains(head)))
+ })
+ .map(|(id, _)| *id)
+ .collect();
+ if more.is_empty() {
+ return above;
+ }
+ above.extend(more);
}
- if heads.windows(2).any(|pair| pair[0] >= pair[1]) {
+ }
+
+ /// Whether an event built on `deps`, whose history reads as this state, may name
+ /// `heads` for a checkpoint: as `cut` says, and the event above them.
+ fn may_cut(&self, deps: &[Id], heads: &[Id]) -> bool {
+ if heads.is_empty() || heads.windows(2).any(|pair| pair[0] >= pair[1]) {
return false;
}
- let beside = |a: &Id, b: &Id| a != b && self.built_on(a, b);
- if heads.iter().any(|a| heads.iter().any(|b| beside(a, b))) {
+ if heads
+ .iter()
+ .any(|a| heads.iter().any(|b| a != b && self.built_on(a, b)))
+ {
return false;
}
- self.graph.keys().filter(|id| after(id)).all(|id| {
- heads.contains(id)
- || heads.iter().any(|head| self.built_on(head, id))
- || heads.iter().all(|head| self.built_on(id, head))
- })
+ let after = match self.cuts.get(&self.cut) {
+ // The latest cut of the history is one of the state's events.
+ Some(current) => {
+ let above = self.above(&current.iter().copied().collect());
+ heads.iter().all(|head| above.contains(head))
+ && self.cut_events.iter().any(|(cut, n)| {
+ *n == self.cut
+ && heads
+ .iter()
+ .any(|head| head == cut || self.built_on(head, cut))
+ })
+ }
+ // The latest cut is in the history of the checkpoint the state starts from: the
+ // heads are after that checkpoint, or its own, which count as after the latest
+ // cut and holding it, so that a node starting from it judges the cut naming it
+ // as every node does.
+ None => {
+ heads.iter().eq(self.at.iter())
+ || heads
+ .iter()
+ .all(|head| self.graph.contains_key(head) && !self.before.contains(head))
+ }
+ };
+ let named: BTreeSet<Id> = heads.iter().copied().collect();
+ let above = self.above(&named);
+ after
+ && deps
+ .iter()
+ .all(|dep| named.contains(dep) || above.contains(dep))
+ && (deps.iter().any(|dep| above.contains(dep))
+ || named.iter().all(|head| deps.contains(head)))
}
}
@@ -230,7 +289,7 @@ impl Fold for TestFold {
}
fn judge(at: &State, _id: &Id, event: &[u8]) -> Result<(), Refused> {
- let (_, kind) = decode(event).ok_or_else(|| Refused::new("no event"))?;
+ let (deps, kind) = decode(event).ok_or_else(|| Refused::new("no event"))?;
match kind {
Kind::Put { key, .. } if at.locks.contains(&key) => {
Err(Refused::new(format!("{key} is locked")))
@@ -242,8 +301,8 @@ impl Fold for TestFold {
let heads = ids(&heads).ok_or_else(|| Refused::new("heads not IDs"))?;
if n != at.cut + 1 {
Err(Refused::new(format!("cut {n} after {}", at.cut)))
- } else if !at.above(&heads) {
- Err(Refused::new("not above its heads"))
+ } else if !at.may_cut(&deps, &heads) {
+ Err(Refused::new("heads it may not name"))
} else {
Ok(())
}
@@ -272,6 +331,7 @@ impl Fold for TestFold {
Kind::Cut { n, heads } => {
state.cut = state.cut.max(n);
state.cuts.insert(n, ids(&heads).unwrap_or_default());
+ state.cut_events.insert(*id, n);
}
Kind::Junk => {}
}