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