diff options
| -rw-r--r-- | src/federation/store/testfold.rs | 106 |
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(¤t.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 => {} } |
