src/tools/rust-analyzer/lib/la-arena/src/lib.rs

   1 //! Yet another index-based arena.
   2
   3 #![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
   4 #![warn(missing_docs)]
   5
   6 use std::{
   7     fmt,
   8     hash::{Hash, Hasher},
   9     marker::PhantomData,
  10     ops::{Index, IndexMut, Range, RangeInclusive},
  11 };
  12
  13 mod map;
  14 pub use map::{ArenaMap, Entry, OccupiedEntry, VacantEntry};
  15
  16 /// The raw index of a value in an arena.
  17 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  18 pub struct RawIdx(u32);
  19
  20 impl From<RawIdx> for u32 {
  21     fn from(raw: RawIdx) -> u32 {
  22         raw.0
  23     }
  24 }
  25
  26 impl From<u32> for RawIdx {
  27     fn from(idx: u32) -> RawIdx {
  28         RawIdx(idx)
  29     }
  30 }
  31
  32 impl fmt::Debug for RawIdx {
  33     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  34         self.0.fmt(f)
  35     }
  36 }
  37
  38 impl fmt::Display for RawIdx {
  39     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  40         self.0.fmt(f)
  41     }
  42 }
  43
  44 /// The index of a value allocated in an arena that holds `T`s.
  45 pub struct Idx<T> {
  46     raw: RawIdx,
  47     _ty: PhantomData<fn() -> T>,
  48 }
  49
  50 impl<T> Clone for Idx<T> {
  51     fn clone(&self) -> Self {
  52         *self
  53     }
  54 }
  55 impl<T> Copy for Idx<T> {}
  56
  57 impl<T> PartialEq for Idx<T> {
  58     fn eq(&self, other: &Idx<T>) -> bool {
  59         self.raw == other.raw
  60     }
  61 }
  62 impl<T> Eq for Idx<T> {}
  63
  64 impl<T> Hash for Idx<T> {
  65     fn hash<H: Hasher>(&self, state: &mut H) {
  66         self.raw.hash(state);
  67     }
  68 }
  69
  70 impl<T> fmt::Debug for Idx<T> {
  71     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  72         let mut type_name = std::any::type_name::<T>();
  73         if let Some(idx) = type_name.rfind(':') {
  74             type_name = &type_name[idx + 1..];
  75         }
  76         write!(f, "Idx::<{}>({})", type_name, self.raw)
  77     }
  78 }
  79
  80 impl<T> Idx<T> {
  81     /// Creates a new index from a [`RawIdx`].
  82     pub fn from_raw(raw: RawIdx) -> Self {
  83         Idx { raw, _ty: PhantomData }
  84     }
  85
  86     /// Converts this index into the underlying [`RawIdx`].
  87     pub fn into_raw(self) -> RawIdx {
  88         self.raw
  89     }
  90 }
  91
  92 /// A range of densely allocated arena values.
  93 pub struct IdxRange<T> {
  94     range: Range<u32>,
  95     _p: PhantomData<T>,
  96 }
  97
  98 impl<T> IdxRange<T> {
  99     /// Creates a new index range
 100     /// inclusive of the start value and exclusive of the end value.
 101     ///
 102     /// ```
 103     /// let mut arena = la_arena::Arena::new();
 104     /// let a = arena.alloc("a");
 105     /// let b = arena.alloc("b");
 106     /// let c = arena.alloc("c");
 107     /// let d = arena.alloc("d");
 108     ///
 109     /// let range = la_arena::IdxRange::new(b..d);
 110     /// assert_eq!(&arena[range], &["b", "c"]);
 111     /// ```
 112     pub fn new(range: Range<Idx<T>>) -> Self {
 113         Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData }
 114     }
 115
 116     /// Creates a new index range
 117     /// inclusive of the start value and end value.
 118     ///
 119     /// ```
 120     /// let mut arena = la_arena::Arena::new();
 121     /// let foo = arena.alloc("foo");
 122     /// let bar = arena.alloc("bar");
 123     /// let baz = arena.alloc("baz");
 124     ///
 125     /// let range = la_arena::IdxRange::new_inclusive(foo..=baz);
 126     /// assert_eq!(&arena[range], &["foo", "bar", "baz"]);
 127     ///
 128     /// let range = la_arena::IdxRange::new_inclusive(foo..=foo);
 129     /// assert_eq!(&arena[range], &["foo"]);
 130     /// ```
 131     pub fn new_inclusive(range: RangeInclusive<Idx<T>>) -> Self {
 132         Self {
 133             range: u32::from(range.start().into_raw())..u32::from(range.end().into_raw()) + 1,
 134             _p: PhantomData,
 135         }
 136     }
 137
 138     /// Returns whether the index range is empty.
 139     ///
 140     /// ```
 141     /// let mut arena = la_arena::Arena::new();
 142     /// let one = arena.alloc(1);
 143     /// let two = arena.alloc(2);
 144     ///
 145     /// assert!(la_arena::IdxRange::new(one..one).is_empty());
 146     /// ```
 147     pub fn is_empty(&self) -> bool {
 148         self.range.is_empty()
 149     }
 150 }
 151
 152 impl<T> Iterator for IdxRange<T> {
 153     type Item = Idx<T>;
 154     fn next(&mut self) -> Option<Self::Item> {
 155         self.range.next().map(|raw| Idx::from_raw(raw.into()))
 156     }
 157 }
 158
 159 impl<T> DoubleEndedIterator for IdxRange<T> {
 160     fn next_back(&mut self) -> Option<Self::Item> {
 161         self.range.next_back().map(|raw| Idx::from_raw(raw.into()))
 162     }
 163 }
 164
 165 impl<T> fmt::Debug for IdxRange<T> {
 166     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 167         f.debug_tuple(&format!("IdxRange::<{}>", std::any::type_name::<T>()))
 168             .field(&self.range)
 169             .finish()
 170     }
 171 }
 172
 173 impl<T> Clone for IdxRange<T> {
 174     fn clone(&self) -> Self {
 175         Self { range: self.range.clone(), _p: PhantomData }
 176     }
 177 }
 178
 179 impl<T> PartialEq for IdxRange<T> {
 180     fn eq(&self, other: &Self) -> bool {
 181         self.range == other.range
 182     }
 183 }
 184
 185 impl<T> Eq for IdxRange<T> {}
 186
 187 /// Yet another index-based arena.
 188 #[derive(Clone, PartialEq, Eq, Hash)]
 189 pub struct Arena<T> {
 190     data: Vec<T>,
 191 }
 192
 193 impl<T: fmt::Debug> fmt::Debug for Arena<T> {
 194     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 195         fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish()
 196     }
 197 }
 198
 199 impl<T> Arena<T> {
 200     /// Creates a new empty arena.
 201     ///
 202     /// ```
 203     /// let arena: la_arena::Arena<i32> = la_arena::Arena::new();
 204     /// assert!(arena.is_empty());
 205     /// ```
 206     pub const fn new() -> Arena<T> {
 207         Arena { data: Vec::new() }
 208     }
 209
 210     /// Create a new empty arena with specific capacity.
 211     ///
 212     /// ```
 213     /// let arena: la_arena::Arena<i32> = la_arena::Arena::with_capacity(42);
 214     /// assert!(arena.is_empty());
 215     /// ```
 216     pub fn with_capacity(capacity: usize) -> Arena<T> {
 217         Arena { data: Vec::with_capacity(capacity) }
 218     }
 219
 220     /// Empties the arena, removing all contained values.
 221     ///
 222     /// ```
 223     /// let mut arena = la_arena::Arena::new();
 224     ///
 225     /// arena.alloc(1);
 226     /// arena.alloc(2);
 227     /// arena.alloc(3);
 228     /// assert_eq!(arena.len(), 3);
 229     ///
 230     /// arena.clear();
 231     /// assert!(arena.is_empty());
 232     /// ```
 233     pub fn clear(&mut self) {
 234         self.data.clear();
 235     }
 236
 237     /// Returns the length of the arena.
 238     ///
 239     /// ```
 240     /// let mut arena = la_arena::Arena::new();
 241     /// assert_eq!(arena.len(), 0);
 242     ///
 243     /// arena.alloc("foo");
 244     /// assert_eq!(arena.len(), 1);
 245     ///
 246     /// arena.alloc("bar");
 247     /// assert_eq!(arena.len(), 2);
 248     ///
 249     /// arena.alloc("baz");
 250     /// assert_eq!(arena.len(), 3);
 251     /// ```
 252     pub fn len(&self) -> usize {
 253         self.data.len()
 254     }
 255
 256     /// Returns whether the arena contains no elements.
 257     ///
 258     /// ```
 259     /// let mut arena = la_arena::Arena::new();
 260     /// assert!(arena.is_empty());
 261     ///
 262     /// arena.alloc(0.5);
 263     /// assert!(!arena.is_empty());
 264     /// ```
 265     pub fn is_empty(&self) -> bool {
 266         self.data.is_empty()
 267     }
 268
 269     /// Allocates a new value on the arena, returning the value’s index.
 270     ///
 271     /// ```
 272     /// let mut arena = la_arena::Arena::new();
 273     /// let idx = arena.alloc(50);
 274     ///
 275     /// assert_eq!(arena[idx], 50);
 276     /// ```
 277     pub fn alloc(&mut self, value: T) -> Idx<T> {
 278         let idx = self.next_idx();
 279         self.data.push(value);
 280         idx
 281     }
 282
 283     /// Returns an iterator over the arena’s elements.
 284     ///
 285     /// ```
 286     /// let mut arena = la_arena::Arena::new();
 287     /// let idx1 = arena.alloc(20);
 288     /// let idx2 = arena.alloc(40);
 289     /// let idx3 = arena.alloc(60);
 290     ///
 291     /// let mut iterator = arena.iter();
 292     /// assert_eq!(iterator.next(), Some((idx1, &20)));
 293     /// assert_eq!(iterator.next(), Some((idx2, &40)));
 294     /// assert_eq!(iterator.next(), Some((idx3, &60)));
 295     /// ```
 296     pub fn iter(
 297         &self,
 298     ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
 299         self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
 300     }
 301
 302     /// Returns an iterator over the arena’s mutable elements.
 303     ///
 304     /// ```
 305     /// let mut arena = la_arena::Arena::new();
 306     /// let idx1 = arena.alloc(20);
 307     ///
 308     /// assert_eq!(arena[idx1], 20);
 309     ///
 310     /// let mut iterator = arena.iter_mut();
 311     /// *iterator.next().unwrap().1 = 10;
 312     /// drop(iterator);
 313     ///
 314     /// assert_eq!(arena[idx1], 10);
 315     /// ```
 316     pub fn iter_mut(
 317         &mut self,
 318     ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator {
 319         self.data
 320             .iter_mut()
 321             .enumerate()
 322             .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
 323     }
 324
 325     /// Reallocates the arena to make it take up as little space as possible.
 326     pub fn shrink_to_fit(&mut self) {
 327         self.data.shrink_to_fit();
 328     }
 329
 330     /// Returns the index of the next value allocated on the arena.
 331     ///
 332     /// This method should remain private to make creating invalid `Idx`s harder.
 333     fn next_idx(&self) -> Idx<T> {
 334         Idx::from_raw(RawIdx(self.data.len() as u32))
 335     }
 336 }
 337
 338 impl<T> Default for Arena<T> {
 339     fn default() -> Arena<T> {
 340         Arena { data: Vec::new() }
 341     }
 342 }
 343
 344 impl<T> Index<Idx<T>> for Arena<T> {
 345     type Output = T;
 346     fn index(&self, idx: Idx<T>) -> &T {
 347         let idx = idx.into_raw().0 as usize;
 348         &self.data[idx]
 349     }
 350 }
 351
 352 impl<T> IndexMut<Idx<T>> for Arena<T> {
 353     fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
 354         let idx = idx.into_raw().0 as usize;
 355         &mut self.data[idx]
 356     }
 357 }
 358
 359 impl<T> Index<IdxRange<T>> for Arena<T> {
 360     type Output = [T];
 361     fn index(&self, range: IdxRange<T>) -> &[T] {
 362         let start = range.range.start as usize;
 363         let end = range.range.end as usize;
 364         &self.data[start..end]
 365     }
 366 }
 367
 368 impl<T> FromIterator<T> for Arena<T> {
 369     fn from_iter<I>(iter: I) -> Self
 370     where
 371         I: IntoIterator<Item = T>,
 372     {
 373         Arena { data: Vec::from_iter(iter) }
 374     }
 375 }