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.rs236
1 files changed, 229 insertions, 7 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index 85fac7f..6d265f4 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -65,19 +65,42 @@ pub(crate) struct Store<F: Fold> {
waits_for: HashMap<Id, BTreeSet<Id>>,
/// The events refused, and why.
refused: HashMap<Id, Refusal>,
+ /// 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>,
}
impl<F: Fold> Store<F> {
- /// A store starting from its root, with the events the root keeps.
+ /// A store starting from its root, with the events the root keeps: its events build
+ /// on the root itself.
pub(crate) fn new(root: Vec<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> {
let id = Id::of(&root);
- let (_, keeps) = F::parts(&root).ok_or_else(|| Refused::new("no checkpoint"))?;
+ Self::starting(id, root, BTreeSet::from([id]), kept)
+ }
+
+ /// A store of ID `id` starting from a checkpoint its operator pins, with the events it
+ /// keeps: its events build on the heads it was built at.
+ pub(crate) fn pinned(id: Id, checkpoint: Vec<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> {
+ let (at, _) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?;
+ if at.is_empty() {
+ return Err(Refused::new("a checkpoint without heads is a root"));
+ }
+ Self::starting(id, checkpoint, at.into_iter().collect(), kept)
+ }
+
+ fn starting(
+ id: Id,
+ checkpoint: Vec<u8>,
+ heads: BTreeSet<Id>,
+ kept: Vec<Vec<u8>>,
+ ) -> Result<Self, Refused> {
+ let (_, keeps) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?;
let kept = matched(&keeps, kept)?;
- let start = F::start(&root, &kept.clone().into_iter().collect::<Vec<_>>())?;
+ let start = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>())?;
Ok(Self {
id,
- checkpoint: root,
- heads: BTreeSet::from([id]),
+ checkpoint,
+ heads,
kept,
state: start.clone(),
start,
@@ -86,6 +109,7 @@ impl<F: Fold> Store<F> {
waiting: HashMap::new(),
waits_for: HashMap::new(),
refused: HashMap::new(),
+ forgotten: HashSet::new(),
})
}
@@ -99,6 +123,11 @@ impl<F: Fold> Store<F> {
&self.checkpoint
}
+ /// The events the checkpoint keeps, as bytes, in the order of their IDs.
+ pub(crate) fn kept(&self) -> Vec<Vec<u8>> {
+ self.kept.values().cloned().collect()
+ }
+
/// What everything the store holds reads as.
pub(crate) fn state(&self) -> &F::State {
&self.state
@@ -152,7 +181,10 @@ impl<F: Fold> Store<F> {
/// takes it at its history.
pub(crate) fn offer(&mut self, bytes: Vec<u8>) -> Offered {
let id = Id::of(&bytes);
- if self.events.contains_key(&id) || self.kept.contains_key(&id) || self.heads.contains(&id)
+ if self.events.contains_key(&id)
+ || self.kept.contains_key(&id)
+ || self.heads.contains(&id)
+ || self.forgotten.contains(&id)
{
return Offered::Held;
}
@@ -209,12 +241,118 @@ impl<F: Fold> Store<F> {
}
first.get_or_insert(offered);
}
+ if !taken.is_empty() {
+ while self.moved() {}
+ }
match first.expect("one event considered") {
Offered::Taken(_) => Offered::Taken(taken),
other => other,
}
}
+ /// Moves to the checkpoint the fold names, where it names a later one: builds it at its
+ /// heads, forgets what came before them but what it keeps, and every event not above
+ /// them, refusing those from then on. Whether it moved.
+ fn moved(&mut self) -> bool {
+ let Some(named) = F::moves_to(&self.state) else {
+ return false;
+ };
+ let heads: BTreeSet<Id> = named.into_iter().collect();
+ if heads == self.heads
+ || heads.is_empty()
+ || !heads.iter().all(|head| self.events.contains_key(head))
+ {
+ return false;
+ }
+ let beside = heads.iter().any(|head| {
+ let history = self.history(&self.events[head].dependencies);
+ heads.iter().any(|other| history.contains(other))
+ });
+ if beside {
+ return false;
+ }
+ let ids: Vec<Id> = heads.iter().copied().collect();
+ let at = self.state_at(&ids);
+ let (checkpoint, keeps) = F::checkpoint(&at, &ids);
+ let Some(kept) = keeps
+ .iter()
+ .map(|id| self.get(id).map(<[u8]>::to_vec))
+ .collect::<Option<Vec<_>>>()
+ else {
+ return false;
+ };
+ let Ok(kept) = matched(&keeps, kept) else {
+ return false;
+ };
+ let Ok(start) = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>()) else {
+ return false;
+ };
+ let before = self.history(&ids);
+ let mut above: HashSet<Id> = HashSet::new();
+ for id in self.order.iter().filter(|id| !before.contains(id)) {
+ let dependencies = &self.events[id].dependencies;
+ let on = dependencies
+ .iter()
+ .all(|dependency| heads.contains(dependency) || above.contains(dependency));
+ let holds = dependencies
+ .iter()
+ .any(|dependency| above.contains(dependency))
+ || heads.iter().all(|head| dependencies.contains(head));
+ if on && holds {
+ above.insert(*id);
+ }
+ }
+ for id in &self.order {
+ if before.contains(id) {
+ if !kept.contains_key(id) && !heads.contains(id) {
+ self.forgotten.insert(*id);
+ }
+ } else if !above.contains(id) {
+ self.refused.insert(*id, Refusal::NotAbove);
+ }
+ }
+ let old = std::mem::replace(&mut self.heads, heads);
+ self.forgotten
+ .extend(old.into_iter().filter(|head| !self.heads.contains(head)));
+ self.forgotten.extend(
+ self.kept
+ .keys()
+ .filter(|id| !kept.contains_key(id))
+ .copied(),
+ );
+ self.checkpoint = checkpoint;
+ self.kept = kept;
+ self.order.retain(|id| above.contains(id));
+ self.events.retain(|id, _| above.contains(id));
+ let mut state = start.clone();
+ for id in &self.order {
+ F::add(&mut state, id, &self.events[id].bytes);
+ }
+ self.start = start;
+ self.state = state;
+ let stale: Vec<Id> = self
+ .waiting
+ .iter()
+ .filter(|(_, event)| {
+ event.dependencies.iter().any(|dependency| {
+ self.forgotten.contains(dependency) || self.refused.contains_key(dependency)
+ })
+ })
+ .map(|(id, _)| *id)
+ .collect();
+ for id in stale {
+ if let Some(event) = self.waiting.remove(&id) {
+ for dependency in &event.dependencies {
+ if let Some(waiting) = self.waits_for.get_mut(dependency) {
+ waiting.remove(&id);
+ }
+ }
+ }
+ self.refuse(id, Refusal::NotAbove);
+ }
+ true
+ }
+
/// The events that waited for `id` alone, now to be considered again.
fn woken(&mut self, id: &Id) -> Vec<(Id, Event)> {
let Some(waiters) = self.waits_for.remove(id) else {
@@ -243,7 +381,8 @@ impl<F: Fold> Store<F> {
return self.refuse(id, Refusal::BuiltOn(refused));
}
let before = |dependency: &Id| {
- self.kept.contains_key(dependency) && !self.heads.contains(dependency)
+ (self.kept.contains_key(dependency) || self.forgotten.contains(dependency))
+ && !self.heads.contains(dependency)
};
if event.dependencies.iter().any(before) {
return self.refuse(id, Refusal::NotAbove);
@@ -536,6 +675,89 @@ mod tests {
assert!(store.drop_taken(&[root]).is_err());
}
+ /// A store whose root holds puts and a lock, cut at the lock: the cut's ID, the lock's,
+ /// and the first put's, which the checkpoint forgets.
+ fn cut_at_a_lock() -> (Store<TestFold>, Id, Id, Id) {
+ let mut store = store();
+ let root = store.id();
+ let first = taken(store.offer(testfold::put(&[root], "a", "1")));
+ let second = taken(store.offer(testfold::put(&[first], "a", "2")));
+ let lock = taken(store.offer(testfold::lock(&[second], "b")));
+ let cut = taken(store.offer(testfold::cut(&[lock], 1, &[lock])));
+ (store, cut, lock, first)
+ }
+
+ #[test]
+ fn a_cut_moves_the_store_to_a_checkpoint() {
+ let (mut store, cut, lock, first) = cut_at_a_lock();
+ assert_eq!(
+ TestFold::parts(store.checkpoint()).map(|(at, _)| at),
+ Some(vec![lock])
+ );
+ assert_eq!(store.taken(), &[cut]);
+ assert_eq!(store.kept().len(), 1);
+ assert_eq!(store.state().counts()["a"], "2");
+ assert!(store.state().locks().contains("b"));
+ // After it: taken. On what it forgot, or the root: not above its heads.
+ assert!(matches!(
+ store.offer(testfold::put(&[cut], "a", "3")),
+ Offered::Taken(_)
+ ));
+ assert_eq!(store.state().counts()["a"], "3");
+ assert_eq!(
+ store.offer(testfold::put(&[first], "c", "1")),
+ Offered::Refused(Refusal::NotAbove)
+ );
+ let root = store.id();
+ assert_eq!(
+ store.offer(testfold::put(&[root], "c", "1")),
+ Offered::Refused(Refusal::NotAbove)
+ );
+ // A head brought again is held; so is what came before it.
+ assert_eq!(
+ store.offer(testfold::lock(
+ &[Id::of(&testfold::put(&[first], "a", "2"))],
+ "b"
+ )),
+ Offered::Held
+ );
+ assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held);
+ }
+
+ #[test]
+ fn what_was_taken_beside_the_heads_is_refused_by_the_move() {
+ let mut store = store();
+ let root = store.id();
+ let here = taken(store.offer(testfold::put(&[root], "a", "1")));
+ let beside = taken(store.offer(testfold::put(&[root], "b", "1")));
+ let on_beside = taken(store.offer(testfold::put(&[beside], "c", "1")));
+ let cut = taken(store.offer(testfold::cut(&[here], 1, &[here])));
+ assert_eq!(store.taken(), &[cut]);
+ assert_eq!(store.refusal(&beside), Some(&Refusal::NotAbove));
+ assert_eq!(store.refusal(&on_beside), Some(&Refusal::NotAbove));
+ assert!(!store.state().counts().contains_key("b"));
+ }
+
+ #[test]
+ fn a_node_starts_from_a_pinned_checkpoint() {
+ let (mut store, cut, _, _) = cut_at_a_lock();
+ let later = testfold::put(&[cut], "c", "1");
+ assert!(matches!(store.offer(later.clone()), Offered::Taken(_)));
+ let mut pinned: Store<TestFold> =
+ Store::pinned(store.id(), store.checkpoint().to_vec(), store.kept()).expect("pinned");
+ assert_eq!(pinned.offer(later.clone()), Offered::Waiting);
+ let cut_bytes = store.get(&cut).expect("held").to_vec();
+ assert_eq!(
+ pinned.offer(cut_bytes),
+ Offered::Taken(vec![cut, Id::of(&later)])
+ );
+ assert_eq!(pinned.state().counts(), store.state().counts());
+ assert_eq!(pinned.checkpoint(), store.checkpoint());
+ assert!(
+ Store::<TestFold>::pinned(store.id(), store.checkpoint().to_vec(), Vec::new()).is_err()
+ );
+ }
+
#[test]
fn an_event_waits_until_all_it_builds_on_is_held() {
let mut store = store();