strop_core/
id.rs

1//! Stable identities and typed coordinates (0014 wave 2).
2//!
3//! Two families:
4//! - **IDs**: generational arena keys (`DocumentId`, `ViewId`, …). A
5//!   closed document's id fails lookup instead of silently resolving to
6//!   whatever moved into its old vector slot.
7//! - **Coordinates**: newtypes so byte offsets, line indexes, and the
8//!   three column kinds (bytes / UTF-16 / display) can't mix silently.
9
10/// A generational-arena key: the index names the slot, the generation
11/// names the occupant. Stale keys fail lookup.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
13pub struct Id<K> {
14    index: u32,
15    generation: u32,
16    _kind: std::marker::PhantomData<K>,
17}
18
19impl<K> Id<K> {
20    pub fn index(self) -> usize {
21        self.index as usize
22    }
23
24    pub fn generation(self) -> u32 {
25        self.generation
26    }
27}
28
29/// Marker kinds for the arena's identities.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
31pub struct DocumentKind;
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub struct ViewKind;
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub struct PaneKind;
36
37pub type DocumentId = Id<DocumentKind>;
38pub type ViewId = Id<ViewKind>;
39pub type PaneId = Id<PaneKind>;
40
41/// A minimal generational arena (house rule: 40 boring lines beat a
42/// dependency). Slots are reused; each reuse bumps the generation.
43pub struct Arena<K, T> {
44    slots: Vec<Slot<T>>,
45    free: Vec<u32>,
46    _kind: std::marker::PhantomData<K>,
47}
48
49#[derive(Debug)]
50struct Slot<T> {
51    generation: u32,
52    value: Option<T>,
53}
54
55impl<K, T> Default for Arena<K, T> {
56    fn default() -> Self {
57        Self {
58            slots: Vec::new(),
59            free: Vec::new(),
60            _kind: std::marker::PhantomData,
61        }
62    }
63}
64
65impl<K, T> Arena<K, T> {
66    pub fn insert(&mut self, value: T) -> Id<K> {
67        if let Some(index) = self.free.pop() {
68            let slot = &mut self.slots[index as usize];
69            slot.generation += 1;
70            slot.value = Some(value);
71            return Id {
72                index,
73                generation: slot.generation,
74                _kind: std::marker::PhantomData,
75            };
76        }
77        let index = self.slots.len() as u32;
78        self.slots.push(Slot {
79            generation: 0,
80            value: Some(value),
81        });
82        Id {
83            index,
84            generation: 0,
85            _kind: std::marker::PhantomData,
86        }
87    }
88
89    /// None for a stale id — never the wrong document.
90    pub fn get(&self, id: Id<K>) -> Option<&T> {
91        self.slots
92            .get(id.index as usize)
93            .filter(|s| s.generation == id.generation)
94            .and_then(|s| s.value.as_ref())
95    }
96
97    pub fn get_mut(&mut self, id: Id<K>) -> Option<&mut T> {
98        self.slots
99            .get_mut(id.index as usize)
100            .filter(|s| s.generation == id.generation)
101            .and_then(|s| s.value.as_mut())
102    }
103
104    /// Remove and return the value; stale ids get None.
105    pub fn remove(&mut self, id: Id<K>) -> Option<T> {
106        let slot = self.slots.get_mut(id.index as usize)?;
107        if slot.generation != id.generation {
108            return None;
109        }
110        let value = slot.value.take()?;
111        self.free.push(id.index);
112        Some(value)
113    }
114
115    pub fn iter(&self) -> impl Iterator<Item = (Id<K>, &T)> {
116        self.slots.iter().enumerate().filter_map(|(i, s)| {
117            s.value.as_ref().map(|v| {
118                (
119                    Id {
120                        index: i as u32,
121                        generation: s.generation,
122                        _kind: std::marker::PhantomData,
123                    },
124                    v,
125                )
126            })
127        })
128    }
129
130    pub fn len(&self) -> usize {
131        self.slots.iter().filter(|s| s.value.is_some()).count()
132    }
133
134    /// Drop every live value (slot reuse still bumps generations).
135    pub fn clear(&mut self) {
136        let live: Vec<u32> = self
137            .slots
138            .iter()
139            .enumerate()
140            .filter(|(_, s)| s.value.is_some())
141            .map(|(i, _)| i as u32)
142            .collect();
143        for s in &mut self.slots {
144            s.value = None;
145        }
146        self.free.extend(live);
147    }
148    pub fn is_empty(&self) -> bool {
149        self.len() == 0
150    }
151}
152
153/// A coordinate newtype: the inner value is bytes (ByteOffset), lines
154/// (LineIndex), or columns in a named unit (ByteColumn/Utf16Column/
155/// DisplayColumn). Copy, ordered, hashable; arithmetic is explicit.
156macro_rules! coordinate {
157    ($name:ident, $unit:literal) => {
158        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
159        #[repr(transparent)]
160        pub struct $name(pub usize);
161
162        impl $name {
163            #[inline]
164            pub fn new(v: usize) -> Self {
165                Self(v)
166            }
167            /// Raw units (bytes / lines / columns per the type) — escape
168            /// hatch for arithmetic; naming the unit is the point.
169            #[inline]
170            pub fn get(self) -> usize {
171                self.0
172            }
173            #[inline]
174            pub fn saturating_sub(self, n: usize) -> Self {
175                Self(self.0.saturating_sub(n))
176            }
177        }
178
179        impl std::ops::AddAssign<usize> for $name {
180            #[inline]
181            fn add_assign(&mut self, n: usize) {
182                self.0 += n;
183            }
184        }
185        impl std::ops::SubAssign<usize> for $name {
186            #[inline]
187            fn sub_assign(&mut self, n: usize) {
188                self.0 -= n;
189            }
190        }
191        /// Raw-unit comparison: `offset > 0` reads naturally; the type
192        /// system still stops offset-vs-line mixes (the bug class).
193        impl PartialEq<usize> for $name {
194            #[inline]
195            fn eq(&self, other: &usize) -> bool {
196                self.0 == *other
197            }
198        }
199        impl PartialOrd<usize> for $name {
200            #[inline]
201            fn partial_cmp(&self, other: &usize) -> Option<std::cmp::Ordering> {
202                self.0.partial_cmp(other)
203            }
204        }
205        impl std::ops::Add<usize> for $name {
206            type Output = $name;
207            #[inline]
208            fn add(self, n: usize) -> $name {
209                $name(self.0 + n)
210            }
211        }
212        impl std::ops::Sub<usize> for $name {
213            type Output = $name;
214            #[inline]
215            fn sub(self, n: usize) -> $name {
216                $name(self.0 - n)
217            }
218        }
219        impl std::ops::Sub<$name> for $name {
220            type Output = usize; // a length
221            #[inline]
222            fn sub(self, other: $name) -> usize {
223                self.0 - other.0
224            }
225        }
226        impl std::fmt::Display for $name {
227            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
228                write!(f, "{} {}", self.0, $unit)
229            }
230        }
231        impl From<$name> for usize {
232            #[inline]
233            fn from(v: $name) -> usize {
234                v.0
235            }
236        }
237        impl From<usize> for $name {
238            #[inline]
239            fn from(v: usize) -> $name {
240                $name(v)
241            }
242        }
243    };
244}
245
246coordinate!(ByteOffset, "B");
247coordinate!(LineIndex, "L");
248coordinate!(ByteColumn, "col:B");
249coordinate!(Utf16Column, "col:u16");
250coordinate!(DisplayColumn, "col:dsp");
251
252// NOTE: full newtype wrappers (ByteOffset(usize), Utf16Column(u32), …)
253// are the target; the pragmatic cutover is to name the domains first
254// (this module + the conversion functions) and tighten the Buffer API
255// per call-site cluster as waves 2–4 touch them. A big-bang usize→newtype
256// rewrite of every arithmetic site would be unreviewable.
257
258#[cfg(test)]
259mod tests {
260    use super::*;
261
262    #[test]
263    fn stale_ids_fail_lookup() {
264        let mut a: Arena<DocumentKind, String> = Arena::default();
265        let one = a.insert("one".into());
266        let two = a.insert("two".into());
267        assert_eq!(a.get(one).map(String::as_str), Some("one"));
268        a.remove(one);
269        assert_eq!(a.get(one), None, "removed");
270        let three = a.insert("three".into()); // reuses the slot
271        assert_eq!(a.get(one), None, "stale generation must not resolve");
272        assert_eq!(a.get(three).map(String::as_str), Some("three"));
273        assert_eq!(a.get(two).map(String::as_str), Some("two"));
274        assert_eq!(a.len(), 2);
275    }
276}
strop_core/id.rs

strop_core/
id.rs
