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.
11#[derive(Debug, Clone, Serialize, Deserialize)]
12pub struct ArenaSeed<T> {
13    pub slots: Vec<(u32, Option<T>)>,
14    pub free: Vec<u32>,
15}
16
17#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
18pub enum ArenaSeedError {
19    #[error("too many arena slots")]
20    TooManySlots,
21    #[error("free slot outside arena")]
22    FreeOutOfBounds,
23    #[error("invalid or repeated free slot")]
24    InvalidFreeSlot,
25    #[error("missing free slot")]
26    MissingFreeSlot,
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 exactly the empty slots
43    /// and nothing else; a seed that disagrees is rejected, never coerced
44    /// into a plausible-but-wrong identity layout.
45    pub fn from_seed(seed: ArenaSeed<T>) -> Result<Self, ArenaSeedError> {
46        if seed.slots.len() > u32::MAX as usize {
47            return Err(ArenaSeedError::TooManySlots);
48        }
49        let mut free = vec![false; seed.slots.len()];
50        for &index in &seed.free {
51            let Some(seen) = free.get_mut(index as usize) else {
52                return Err(ArenaSeedError::FreeOutOfBounds);
53            };
54            if *seen || seed.slots[index as usize].1.is_some() {
55                return Err(ArenaSeedError::InvalidFreeSlot);
56            }
57            *seen = true;
58        }
59        if seed
60            .slots
61            .iter()
62            .enumerate()
63            .any(|(index, (_, value))| value.is_none() != free[index])
64        {
65            return Err(ArenaSeedError::MissingFreeSlot);
66        }
67        Ok(Self {
68            slots: seed
69                .slots
70                .into_iter()
71                .map(|(generation, value)| Slot { generation, value })
72                .collect(),
73            free: seed.free,
74            _kind: std::marker::PhantomData,
75        })
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::super::{Arena, DocumentKind};
82    use super::{ArenaSeed, ArenaSeedError};
83
84    #[test]
85    fn seed_round_trips_ids_free_slots_and_generations() {
86        let mut arena: Arena<DocumentKind, String> = Arena::default();
87        let a = arena.insert("a".into());
88        let b = arena.insert("b".into());
89        arena.remove(a);
90        let seed = arena.seed_with(|value| value.clone());
91        let mut rebuilt = Arena::from_seed(seed).unwrap();
92        assert_eq!(rebuilt.get(a), None, "freed id stays dead");
93        assert_eq!(rebuilt.get(b).map(String::as_str), Some("b"));
94        let c = rebuilt.insert("c".into());
95        assert_eq!(c.index(), a.index(), "free slot is reused");
96        assert_eq!(c.generation(), a.generation() + 1);
97    }
98
99    #[test]
100    fn corrupt_seeds_are_rejected_not_repaired() {
101        let mut arena: Arena<DocumentKind, ()> = Arena::default();
102        let a = arena.insert(());
103        let seed = arena.seed_with(|&()| ());
104        let ArenaSeed { slots, .. } = seed;
105        // A free entry naming an occupied slot.
106        let corrupt = ArenaSeed {
107            slots: slots.clone(),
108            free: vec![a.index() as u32],
109        };
110        assert!(matches!(
111            Arena::<DocumentKind, _>::from_seed(corrupt),
112            Err(ArenaSeedError::InvalidFreeSlot)
113        ));
114        // An occupied slot absent from the free list's complement.
115        let corrupt = ArenaSeed {
116            slots: vec![(0, None)],
117            free: Vec::new(),
118        };
119        assert!(matches!(
120            Arena::<DocumentKind, ()>::from_seed(corrupt),
121            Err(ArenaSeedError::MissingFreeSlot)
122        ));
123        let corrupt = ArenaSeed {
124            slots,
125            free: vec![9],
126        };
127        assert!(matches!(
128            Arena::<DocumentKind, _>::from_seed(corrupt),
129            Err(ArenaSeedError::FreeOutOfBounds)
130        ));
131    }
132}
strop_core/id/seed.rs

strop_core/id/
seed.rs
