recon_core/store.rs
1//! Durable state, read and written synchronously.
2//!
3//! A write does not return until it would survive a crash. So a protocol that writes and then
4//! sends cannot be seen to have made a promise it has no record of — there is no other point at
5//! which a driver could synchronise with a synchronous protocol.
6//!
7//! Reads are synchronous too, which is honest while the record is mirrored in memory. For a log
8//! larger than memory a read is a real disk read; that is a bound of this interface.
9
10use core::convert::Infallible;
11
12/// A position in the appended sequence.
13#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
14pub struct Position(pub u64);
15
16impl Position {
17 pub const START: Position = Position(0);
18}
19
20/// One value that is replaced, and a sequence that grows.
21///
22/// The split is the point: metadata is small and rewritten, entries accumulate. Rewriting
23/// something that accumulates costs `O(n²)` over a run, so it must be appended instead.
24///
25/// A protocol that keeps nothing durably declares both types uninhabited, and then `set` and
26/// `append` take an argument that cannot be constructed. Reads stay callable and return nothing.
27pub trait Store<Meta, Entry> {
28 fn get(&self) -> Option<&Meta>;
29 fn set(&mut self, meta: Meta);
30 fn append(&mut self, entry: Entry) -> Position;
31 fn read_from(&self, from: Position) -> Vec<&Entry>;
32 /// One past the last entry.
33 fn end(&self) -> Position;
34}
35
36/// What a child that keeps nothing durably is handed.
37///
38/// This is the default, and it is what [`Cx::with_child`](crate::Cx::with_child) and
39/// [`Cx::with_child_consuming`](crate::Cx::with_child_consuming) supply. A child that *does* keep
40/// something durably is composed through a [`Slot`] instead — see
41/// [`Cx::with_durable_child_consuming`](crate::Cx::with_durable_child_consuming).
42#[derive(Debug, Default)]
43pub struct NoStore;
44
45impl Store<Infallible, Infallible> for NoStore {
46 fn get(&self) -> Option<&Infallible> {
47 None
48 }
49
50 fn set(&mut self, meta: Infallible) {
51 match meta {}
52 }
53
54 fn append(&mut self, entry: Infallible) -> Position {
55 match entry {}
56 }
57
58 fn read_from(&self, _from: Position) -> Vec<&Infallible> {
59 Vec::new()
60 }
61
62 fn end(&self) -> Position {
63 Position::START
64 }
65}
66
67/// Where a child's durable record lives inside its parent's.
68///
69/// A parent and a child sharing one store would collide on the metadata: each `set` would
70/// overwrite the other's. A `Slot` says which part of the parent's record belongs to the child, so
71/// the child's `set` becomes a read-modify-write of the parent's — **one record, one write**, which
72/// is what keeps durable-before-visible meaning what it says. Two writes could be interrupted
73/// between them; one cannot.
74///
75/// Both halves are `fn` pointers rather than closures, for the same reason the composition mappers
76/// are: a slot must not capture. It names a fixed place in a type, and a slot that could close over
77/// state would be a different place on different calls.
78///
79/// `write` takes the parent's record as an `Option` because the child may write first: nothing is
80/// stored until something is, and the child's own `Init` is often the first event of the run. The
81/// implementation is then "start from the parent's default, put the child's part in it".
82///
83/// ```
84/// # use recon_core::Slot;
85/// #[derive(Clone, Default, PartialEq, Debug)]
86/// struct Parent { mine: u64, childs: Option<u32> }
87///
88/// const CHILD: Slot<Parent, u32> = Slot {
89/// read: |p| p.childs.as_ref(),
90/// write: |p, c| Parent { childs: Some(c), ..p.cloned().unwrap_or_default() },
91/// };
92///
93/// assert_eq!((CHILD.read)(&Parent { mine: 1, childs: Some(7) }), Some(&7));
94/// assert_eq!((CHILD.write)(None, 7), Parent { mine: 0, childs: Some(7) });
95/// ```
96///
97/// # The sequence half is [`SeqSlot`]
98///
99/// A `Slot` scopes the **metadata** only, so [`Cx::with_durable_child_consuming`] hands the child a
100/// store whose `Entry` is uninhabited: such a child cannot append, and the signature says so rather
101/// than a comment. That is still the right default, and most durable children want nothing else.
102///
103/// A child that *appends* is composed through [`SeqSlot`] as well, with
104/// [`Cx::with_durable_child`](crate::Cx::with_durable_child). This paragraph used to say the shape
105/// such a thing would take and that nothing needed it — "building it now would be the framework
106/// before its second consumer". The second consumer arrived: the fail-recovery total-order
107/// broadcast keeps a durable record of its own *and* composes
108/// `logged_uniform_reliable_broadcast`, which is the one protocol here that appends. What was
109/// built is what that paragraph described, unchanged.
110///
111/// [`Cx::with_durable_child_consuming`]: crate::Cx::with_durable_child_consuming
112pub struct Slot<Parent, Child> {
113 /// The child's record, as it sits inside the parent's.
114 pub read: fn(&Parent) -> Option<&Child>,
115 /// The parent's record with the child's part replaced.
116 pub write: fn(Option<&Parent>, Child) -> Parent,
117}
118
119impl<Parent, Child> Clone for Slot<Parent, Child> {
120 fn clone(&self) -> Self {
121 *self
122 }
123}
124
125impl<Parent, Child> Copy for Slot<Parent, Child> {}
126
127impl<Parent, Child> core::fmt::Debug for Slot<Parent, Child> {
128 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
129 f.write_str("Slot")
130 }
131}
132
133/// A [`Slot`] for an `Option` field of a `Clone + Default` parent record — the common case.
134///
135/// `slot!(Parent, field)` writes the two projections every such slot writes the same way: read the
136/// field, and write the parent with the field replaced, starting from the parent's default if there
137/// is no parent record yet.
138///
139/// ```
140/// # use recon_core::{Slot, slot};
141/// #[derive(Clone, Default, PartialEq, Debug)]
142/// struct Parent { mine: u64, childs: Option<u32> }
143///
144/// const CHILD: Slot<Parent, u32> = slot!(Parent, childs);
145/// assert_eq!((CHILD.write)(None, 7), Parent { mine: 0, childs: Some(7) });
146/// assert_eq!((CHILD.read)(&Parent { mine: 1, childs: Some(3) }), Some(&3));
147/// ```
148#[macro_export]
149macro_rules! slot {
150 ($parent:ty, $field:ident) => {
151 $crate::Slot::<$parent, _> {
152 read: |p| p.$field.as_ref(),
153 write: |p, c| {
154 let mut whole: $parent = p.cloned().unwrap_or_default();
155 whole.$field = Some(c);
156 whole
157 },
158 }
159 };
160}
161
162/// A child's view of one slot of its parent's store.
163///
164/// Reads project; writes read the parent's record, replace the child's part, and write the whole
165/// thing back. The parent's `Entry` type is carried only so this satisfies [`Store`] — nothing here
166/// ever touches the sequence.
167pub(crate) struct SlotStore<'p, Parent, Child, En> {
168 pub(crate) parent: &'p mut dyn Store<Parent, En>,
169 pub(crate) slot: Slot<Parent, Child>,
170}
171
172impl<Parent, Child, En> Store<Child, Infallible> for SlotStore<'_, Parent, Child, En> {
173 fn get(&self) -> Option<&Child> {
174 self.parent.get().and_then(self.slot.read)
175 }
176
177 fn set(&mut self, child: Child) {
178 // One write, not two: the parent's record comes back with the child's part replaced, and
179 // goes down as a whole. A protocol above this cannot be interrupted between two writes,
180 // because there is only one.
181 let whole = (self.slot.write)(self.parent.get(), child);
182 self.parent.set(whole);
183 }
184
185 fn append(&mut self, entry: Infallible) -> Position {
186 match entry {}
187 }
188
189 fn read_from(&self, _from: Position) -> Vec<&Infallible> {
190 Vec::new()
191 }
192
193 fn end(&self) -> Position {
194 Position::START
195 }
196}
197
198/// Where a child's appended entries live inside its parent's sequence.
199///
200/// [`Slot`]'s counterpart, and the same idea one type along: the parent's `Entry` is a sum, the
201/// child's entries are one of its variants, and both append into **one** sequence rather than two.
202/// One sequence is what keeps the ordering between a parent's entry and its child's real — two
203/// would have no order between them at all, and a recovery replaying them would be inventing one.
204///
205/// `wrap` puts a child's entry into the parent's vocabulary; `project` takes it back out and says
206/// `None` for an entry that is not the child's.
207///
208/// # The positions the child sees are the parent's
209///
210/// The store handed to such a child filters the parent's sequence to the child's variant, so what the child
211/// reads back is its own entries in order — but the [`Position`]s are the parent's, and therefore
212/// **sparse**: a child's third entry may sit at position seven. That is deliberate and is all a
213/// cursor needs, since positions are only ever compared and advanced, never counted. A child that
214/// treated a position as an index into its own entries would be wrong, and would have been wrong
215/// about a plain store too.
216///
217/// `fn` pointers rather than closures, for the reason [`Slot`] gives: a slot names a fixed place in
218/// a type, and one that could close over state would name a different place on different calls.
219pub struct SeqSlot<Entry, ChildEntry> {
220 /// A child's entry, in the parent's vocabulary.
221 pub wrap: fn(ChildEntry) -> Entry,
222 /// The child's entry inside a parent's, or `None` if this entry is not the child's.
223 pub project: fn(&Entry) -> Option<&ChildEntry>,
224}
225
226impl<Entry, ChildEntry> Clone for SeqSlot<Entry, ChildEntry> {
227 fn clone(&self) -> Self {
228 *self
229 }
230}
231
232impl<Entry, ChildEntry> Copy for SeqSlot<Entry, ChildEntry> {}
233
234impl<Entry, ChildEntry> core::fmt::Debug for SeqSlot<Entry, ChildEntry> {
235 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
236 f.write_str("SeqSlot")
237 }
238}
239
240/// Where one of a *family* of children keeps its record, inside its parent's.
241///
242/// [`Slot`] names a fixed place, which is right when a parent has one child of a kind. A parent
243/// holding a family — one instance per round, per epoch, per slot of a log — needs a place *per
244/// member*, and the member is not known when the slot is written.
245///
246/// The key is **data, not a capture**. `read` and `write` stay `fn` pointers and take the key as an
247/// argument, so a keyed slot still names one fixed function; what varies is what it is applied to.
248/// That is what [`Slot`]'s own note means by "a slot must not capture": a slot closing over state
249/// would be a *different* function on different calls, and this is the same function every time.
250///
251/// The parent is responsible for the keyspace being a keyspace. Two children handed the same key
252/// share a record, exactly as two `Slot`s naming one field would.
253pub struct KeyedSlot<Parent, Child, K> {
254 /// The child's record for `key`, as it sits inside the parent's.
255 pub read: for<'a> fn(&'a Parent, &K) -> Option<&'a Child>,
256 /// The parent's record with the child's part for `key` replaced.
257 pub write: fn(Option<&Parent>, &K, Child) -> Parent,
258}
259
260impl<Parent, Child, K> Clone for KeyedSlot<Parent, Child, K> {
261 fn clone(&self) -> Self {
262 *self
263 }
264}
265
266impl<Parent, Child, K> Copy for KeyedSlot<Parent, Child, K> {}
267
268impl<Parent, Child, K> core::fmt::Debug for KeyedSlot<Parent, Child, K> {
269 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
270 f.write_str("KeyedSlot")
271 }
272}
273
274/// What one member of a family of durable children is handed.
275pub(crate) struct KeyedSlotStore<'p, Parent, Child, K, En> {
276 pub(crate) parent: &'p mut dyn Store<Parent, En>,
277 pub(crate) slot: KeyedSlot<Parent, Child, K>,
278 pub(crate) key: K,
279}
280
281impl<Parent, Child, K, En> Store<Child, Infallible> for KeyedSlotStore<'_, Parent, Child, K, En> {
282 fn get(&self) -> Option<&Child> {
283 self.parent.get().and_then(|p| (self.slot.read)(p, &self.key))
284 }
285
286 fn set(&mut self, child: Child) {
287 // One write, as with a plain slot: the parent's whole record comes back with this member's
288 // part replaced.
289 let whole = (self.slot.write)(self.parent.get(), &self.key, child);
290 self.parent.set(whole);
291 }
292
293 fn append(&mut self, entry: Infallible) -> Position {
294 match entry {}
295 }
296
297 fn read_from(&self, _from: Position) -> Vec<&Infallible> {
298 Vec::new()
299 }
300
301 fn end(&self) -> Position {
302 Position::START
303 }
304}
305
306/// What a child that keeps metadata **and** appends is handed: both halves of its parent's record,
307/// scoped.
308pub(crate) struct FullSlotStore<'p, Parent, Child, En, CEn> {
309 pub(crate) parent: &'p mut dyn Store<Parent, En>,
310 pub(crate) slot: Slot<Parent, Child>,
311 pub(crate) entries: SeqSlot<En, CEn>,
312}
313
314impl<Parent, Child, En, CEn> Store<Child, CEn> for FullSlotStore<'_, Parent, Child, En, CEn> {
315 fn get(&self) -> Option<&Child> {
316 self.parent.get().and_then(self.slot.read)
317 }
318
319 fn set(&mut self, child: Child) {
320 let whole = (self.slot.write)(self.parent.get(), child);
321 self.parent.set(whole);
322 }
323
324 fn append(&mut self, entry: CEn) -> Position {
325 self.parent.append((self.entries.wrap)(entry))
326 }
327
328 fn read_from(&self, from: Position) -> Vec<&CEn> {
329 self.parent.read_from(from).into_iter().filter_map(self.entries.project).collect()
330 }
331
332 fn end(&self) -> Position {
333 self.parent.end()
334 }
335}
336
337/// A store held in memory: the simulator's, and a test's.
338#[derive(Debug, Clone)]
339pub struct MemStore<Meta, Entry> {
340 meta: Option<Meta>,
341 entries: Vec<Entry>,
342}
343
344impl<Meta, Entry> Default for MemStore<Meta, Entry> {
345 fn default() -> Self {
346 MemStore { meta: None, entries: Vec::new() }
347 }
348}
349
350impl<Meta, Entry> MemStore<Meta, Entry> {
351 /// Nothing written yet — what distinguishes a first start from a restart.
352 pub fn is_empty(&self) -> bool {
353 self.meta.is_none() && self.entries.is_empty()
354 }
355
356 pub fn len(&self) -> usize {
357 self.entries.len()
358 }
359}
360
361impl<Meta, Entry> Store<Meta, Entry> for MemStore<Meta, Entry> {
362 fn get(&self) -> Option<&Meta> {
363 self.meta.as_ref()
364 }
365
366 fn set(&mut self, meta: Meta) {
367 self.meta = Some(meta);
368 }
369
370 fn append(&mut self, entry: Entry) -> Position {
371 let at = Position(self.entries.len() as u64);
372 self.entries.push(entry);
373 at
374 }
375
376 fn read_from(&self, from: Position) -> Vec<&Entry> {
377 self.entries.iter().skip(from.0 as usize).collect()
378 }
379
380 fn end(&self) -> Position {
381 Position(self.entries.len() as u64)
382 }
383}