1 use std::{
2     fmt,
3     hash::{Hash, Hasher},
4     marker::PhantomData,
5     ops::{Index, Range},
6 };
7 
8 /// The index of a value allocated in an arena that holds `T`s.
9 ///
10 /// The Clone, Copy and other traits are defined manually because
11 /// deriving them adds some additional constraints on the `T` generic type
12 /// that we actually don't need since it is phantom.
13 ///
14 /// <https://github.com/rust-lang/rust/issues/26925>
15 pub struct Id<T> {
16     raw: u32,
17     _ty: PhantomData<fn() -> T>,
18 }
19 
20 impl<T> Clone for Id<T> {
clone(&self) -> Self21     fn clone(&self) -> Self {
22         *self
23     }
24 }
25 
26 impl<T> Copy for Id<T> {}
27 
28 impl<T> PartialEq for Id<T> {
eq(&self, other: &Id<T>) -> bool29     fn eq(&self, other: &Id<T>) -> bool {
30         self.raw == other.raw
31     }
32 }
33 
34 impl<T> Eq for Id<T> {}
35 
36 impl<T> Hash for Id<T> {
hash<H: Hasher>(&self, state: &mut H)37     fn hash<H: Hasher>(&self, state: &mut H) {
38         self.raw.hash(state)
39     }
40 }
41 
42 impl<T> fmt::Debug for Id<T> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result43     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44         let mut type_name = std::any::type_name::<T>();
45         if let Some(id) = type_name.rfind(':') {
46             type_name = &type_name[id + 1..]
47         }
48         write!(f, "Id::<{}>({})", type_name, self.raw)
49     }
50 }
51 
52 impl<T> Id<T> {
into_raw(self) -> usize53     pub fn into_raw(self) -> usize {
54         self.raw as usize
55     }
from(n: u32) -> Self56     fn from(n: u32) -> Self {
57         Self {
58             raw: n as u32,
59             _ty: PhantomData,
60         }
61     }
range_to_iter(range: Range<Self>) -> impl Iterator<Item = Self>62     pub fn range_to_iter(range: Range<Self>) -> impl Iterator<Item = Self> {
63         let start = range.start.raw;
64         let end = range.end.raw;
65         (start..end).map(Self::from)
66     }
67 }
68 
69 /// Yet another index-based arena.
70 ///
71 /// An arena is a kind of simple grow-only allocator, backed by a `Vec`
72 /// where all items have the same lifetime, making it easier
73 /// to have references between those items.
74 /// They are all dropped at once when the arena is dropped.
75 #[derive(Clone, PartialEq, Eq)]
76 pub struct Arena<T> {
77     data: Vec<T>,
78 }
79 
80 impl<T: fmt::Debug> fmt::Debug for Arena<T> {
fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result81     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
82         fmt.debug_struct("Arena")
83             .field("len", &self.data.len())
84             .field("data", &self.data)
85             .finish()
86     }
87 }
88 
89 impl<T> Arena<T> {
new() -> Arena<T>90     pub fn new() -> Arena<T> {
91         Arena { data: Vec::new() }
92     }
93 
alloc(&mut self, value: T) -> Id<T>94     pub fn alloc(&mut self, value: T) -> Id<T> {
95         let raw = self.data.len();
96         self.data.push(value);
97         Id::from(raw as u32)
98     }
99 
alloc_iter<I: Iterator<Item = T>>(&mut self, values: I) -> Range<Id<T>>100     pub fn alloc_iter<I: Iterator<Item = T>>(&mut self, values: I) -> Range<Id<T>> {
101         let start = Id::from(self.data.len() as u32);
102         values.for_each(|v| {
103             self.alloc(v);
104         });
105         let end = Id::from(self.data.len() as u32);
106         Range { start, end }
107     }
108 }
109 
110 impl<T> Index<Id<T>> for Arena<T> {
111     type Output = T;
index(&self, id: Id<T>) -> &T112     fn index(&self, id: Id<T>) -> &T {
113         &self.data[id.raw as usize]
114     }
115 }
116 
117 impl<T> Index<Range<Id<T>>> for Arena<T> {
118     type Output = [T];
index(&self, id: Range<Id<T>>) -> &[T]119     fn index(&self, id: Range<Id<T>>) -> &[T] {
120         &self.data[(id.start.raw as usize)..(id.end.raw as usize)]
121     }
122 }
123