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

strop_core/
id.rs
