strop_core/id/
seed.rs

1//! Deterministic arena seeds (R11 forensic replay): a serialized image of
2//! slots, generations and the free list, so a replayed editor addresses
3//! documents by the exact identities the live session used.
4use serde::{Deserialize, Serialize};
5
6use super::{Arena, Slot};
7
8/// Per-slot `(generation, value)` plus the free list. Empty slots keep
9/// their generation: reuse bumps it, and a replay that skipped them would
10/// hand out different ids for later inserts. An empty slot ABSENT from
11/// the free list is retired (0056 AR13): its generation wrapped out, so
12/// it never hands out an id again — retirement must survive the round-trip.
13#[derive(Debug, Clone, Serialize, Deserialize)]
14pub struct ArenaSeed<T> {
15    pub slots: Vec<(u32, Option<T>)>,
16    pub free: Vec<u32>,
17}
18
19#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
20pub enum ArenaSeedError {
21    #[error("too many arena slots")]
22    TooManySlots,
23    #[error("free slot outside arena")]
24    FreeOutOfBounds,
25    #[error("invalid or repeated free slot")]
26    InvalidFreeSlot,
27}
28
29impl<K, T> Arena<K, T> {
30    /// Capture the arena, mapping every live value through `f`.
31    pub fn seed_with<U>(&self, mut f: impl FnMut(&T) -> U) -> ArenaSeed<U> {
32        ArenaSeed {
33            slots: self
34                .slots
35                .iter()
36                .map(|slot| (slot.generation, slot.value.as_ref().map(&mut f)))
37                .collect(),
38            free: self.free.clone(),
39        }
40    }
41
42    /// Rebuild an arena. The free list must name only empty slots, each
43    /// at most once; a seed that disagrees is rejected, never coerced
44    /// into a plausible-but-wrong identity layout. Empty slots missing
45    /// from the free list are retired identities, not corruption.
46    pub fn from_seed(seed: ArenaSeed<T>) -> Result<Self, ArenaSeedError> {
47        if seed.slots.len() > u32::MAX as usize {
48            return Err(ArenaSeedError::TooManySlots);
49        }
50        let mut free = vec![false; seed.slots.len()];
51        for &index in &seed.free {
52            let Some(seen) = free.get_mut(index as usize) else {
53                return Err(ArenaSeedError::FreeOutOfBounds);
54            };
55            if *seen || seed.slots[index as usize].1.is_some() {
56                return Err(ArenaSeedError::InvalidFreeSlot);
57            }
58            *seen = true;
59        }
60        Ok(Self {
61            slots: seed
62                .slots
63                .into_iter()
64                .map(|(generation, value)| Slot { generation, value })
65                .collect(),
66            free: seed.free,
67            _kind: std::marker::PhantomData,
68        })
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use super::super::{Arena, DocumentKind};
75    use super::{ArenaSeed, ArenaSeedError};
76
77    #[test]
78    fn seed_round_trips_ids_free_slots_and_generations() {
79        let mut arena: Arena<DocumentKind, String> = Arena::default();
80        let a = arena.try_insert("a".into()).unwrap();
81        let b = arena.try_insert("b".into()).unwrap();
82        arena.remove(a);
83        let seed = arena.seed_with(|value| value.clone());
84        let mut rebuilt = Arena::from_seed(seed).unwrap();
85        assert_eq!(rebuilt.get(a), None, "freed id stays dead");
86        assert_eq!(rebuilt.get(b).map(String::as_str), Some("b"));
87        let c = rebuilt.try_insert("c".into()).unwrap();
88        assert_eq!(c.index(), a.index(), "free slot is reused");
89        assert_eq!(c.generation(), a.generation() + 1);
90    }
91
92    #[test]
93    fn corrupt_seeds_are_rejected_not_repaired() {
94        let mut arena: Arena<DocumentKind, ()> = Arena::default();
95        let a = arena.try_insert(()).unwrap();
96        let seed = arena.seed_with(|&()| ());
97        let ArenaSeed { slots, .. } = seed;
98        // A free entry naming an occupied slot.
99        let corrupt = ArenaSeed {
100            slots: slots.clone(),
101            free: vec![a.index() as u32],
102        };
103        assert!(matches!(
104            Arena::<DocumentKind, _>::from_seed(corrupt),
105            Err(ArenaSeedError::InvalidFreeSlot)
106        ));
107        // An empty slot absent from the free list is a retired identity,
108        // not corruption: it rebuilds and is never reused (0056 AR13).
109        let retired = ArenaSeed {
110            slots: vec![(u32::MAX, None)],
111            free: Vec::new(),
112        };
113        let mut rebuilt = Arena::<DocumentKind, ()>::from_seed(retired).unwrap();
114        let id = rebuilt.try_insert(()).unwrap();
115        assert_eq!(id.index(), 1, "retired slot stays dead");
116        let corrupt = ArenaSeed {
117            slots,
118            free: vec![9],
119        };
120        assert!(matches!(
121            Arena::<DocumentKind, _>::from_seed(corrupt),
122            Err(ArenaSeedError::FreeOutOfBounds)
123        ));
124    }
125}
strop_core/id/seed.rs

strop_core/id/
seed.rs
