workshop_rs/
arena.rs

1//! Arena/index-based storage.
2//!
3//! An [`Arena`] is an append-only vector of nodes addressed by typed
4//! [`Id<T>`](crate::ids::Id) handles. Nodes are never moved after insertion,
5//! so IDs stay stable for the arena's lifetime. Lookup is bounds-checked and
6//! returns `Option`, so a dangling or out-of-range ID surfaces as a
7//! recoverable invariant error instead of a panic.
8
9use crate::ids::Id;
10
11/// An append-only store of `T` nodes addressed by [`Id<T>`].
12#[derive(Debug, Clone, Default, PartialEq, Eq)]
13pub struct Arena<T> {
14    items: Vec<T>,
15}
16
17impl<T> Arena<T> {
18    /// An empty arena.
19    pub const fn new() -> Self {
20        Arena { items: Vec::new() }
21    }
22
23    /// Append a node and return its stable ID.
24    pub fn push(&mut self, value: T) -> Id<T> {
25        let id = Id::from_index(self.items.len());
26        self.items.push(value);
27        id
28    }
29
30    /// Borrow the node with the given ID, or `None` when the ID is out of
31    /// range (a dangling reference).
32    pub fn get(&self, id: Id<T>) -> Option<&T> {
33        self.items.get(id.index())
34    }
35
36    /// Mutably borrow the node with the given ID, or `None` when the ID is
37    /// out of range.
38    pub fn get_mut(&mut self, id: Id<T>) -> Option<&mut T> {
39        self.items.get_mut(id.index())
40    }
41
42    /// Iterate over all nodes in insertion order.
43    pub fn iter(&self) -> impl Iterator<Item = &T> {
44        self.items.iter()
45    }
46
47    /// The number of nodes.
48    pub fn len(&self) -> usize {
49        self.items.len()
50    }
51
52    /// Whether the arena is empty.
53    pub fn is_empty(&self) -> bool {
54        self.items.is_empty()
55    }
56
57    /// True when `id` is within this arena's range (it may still refer to a
58    /// node; see [`get`](Arena::get)).
59    pub fn contains(&self, id: Id<T>) -> bool {
60        id.index() < self.items.len()
61    }
62}
63
64#[cfg(test)]
65mod tests {
66    use super::Arena;
67
68    #[test]
69    fn push_assigns_sequential_stable_ids() {
70        let mut arena = Arena::new();
71        let a = arena.push(10);
72        let b = arena.push(20);
73        let c = arena.push(30);
74        assert_eq!(a.index(), 0);
75        assert_eq!(b.index(), 1);
76        assert_eq!(c.index(), 2);
77        assert_eq!(arena.get(a), Some(&10));
78        assert_eq!(arena.get(b), Some(&20));
79        assert_eq!(arena.get(c), Some(&30));
80    }
81
82    #[test]
83    fn out_of_range_ids_return_none_without_panicking() {
84        let mut arena = Arena::new();
85        let valid = arena.push("x");
86        let dangling = crate::ids::Id::from_index(valid.index() + 1);
87        let far_out = crate::ids::Id::from_index(usize::MAX);
88        assert_eq!(arena.get(valid), Some(&"x"));
89        assert_eq!(arena.get(dangling), None);
90        assert_eq!(arena.get(far_out), None);
91        assert!(!arena.contains(dangling));
92        assert!(arena.contains(valid));
93    }
94
95    #[test]
96    fn get_mut_allows_in_place_updates_without_moving() {
97        let mut arena = Arena::new();
98        let id = arena.push(vec![1, 2]);
99        arena.get_mut(id).unwrap().push(3);
100        assert_eq!(arena.get(id), Some(&vec![1, 2, 3]));
101        // The ID is still valid after mutation.
102        assert_eq!(arena.get(id).unwrap().len(), 3);
103    }
104
105    #[test]
106    fn iteration_is_insertion_ordered() {
107        let mut arena = Arena::new();
108        arena.push(1);
109        arena.push(2);
110        arena.push(3);
111        let collected: Vec<&i32> = arena.iter().collect();
112        assert_eq!(collected, vec![&1, &2, &3]);
113    }
114}
workshop_rs/arena.rs

workshop_rs/
arena.rs
