diff options
| author | tv <tv@krebsco.de> | 2026-11-16 16:44:38 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-16 18:01:51 +0100 |
| commit | 4d13b874821220a65b8f74f6d0dd48028ec4c0f8 (patch) | |
| tree | acfa5ae768f67a96ab5c1e342cb5b3e44cf7b407 | |
| parent | 7dbf7dec7556e24e95ec5576c1bd290874a5d7c0 (diff) | |
store: the test fold judges a cut by the checkpoint current at its history
A cut names heads above those the latest cut of its history names, and holding that cut,
or, where its history holds none after the checkpoint the state starts from, heads after
that checkpoint or its own; as federation.md has a version name heads after the
checkpoint current at its history, at which that one is current too. It judged them by
the checkpoint the store holds, which isn't the one current at the history of a cut
taken in the same offer as the cut before it, before the store moves. A cut is above its
heads as store.md says, each of its dependencies one of them or above them, so that
moving to them refuses none of what named them.
Of a checkpoint's heads, whose history a state starting from it doesn't hold, it takes
none as built on another, nor on what the checkpoint keeps: starting from a checkpoint
at two heads, one of them kept, it took the other as built on it, and refused the cut
naming them.
| -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 => {} } |
