diff options
Diffstat (limited to 'src/tools/rust-analyzer/lib/la-arena')
| -rw-r--r-- | src/tools/rust-analyzer/lib/la-arena/Cargo.toml | 10 | ||||
| -rw-r--r-- | src/tools/rust-analyzer/lib/la-arena/src/lib.rs | 366 | ||||
| -rw-r--r-- | src/tools/rust-analyzer/lib/la-arena/src/map.rs | 75 |
3 files changed, 451 insertions, 0 deletions
diff --git a/src/tools/rust-analyzer/lib/la-arena/Cargo.toml b/src/tools/rust-analyzer/lib/la-arena/Cargo.toml new file mode 100644 index 000000000..ec5ba8ba0 --- /dev/null +++ b/src/tools/rust-analyzer/lib/la-arena/Cargo.toml @@ -0,0 +1,10 @@ +[package] +name = "la-arena" +version = "0.3.0" +description = "Simple index-based arena without deletion." +license = "MIT OR Apache-2.0" +repository = "https://github.com/rust-lang/rust-analyzer/tree/master/lib/la-arena" +documentation = "https://docs.rs/la-arena" +categories = ["data-structures", "memory-management", "rust-patterns"] +edition = "2021" +rust-version = "1.56" diff --git a/src/tools/rust-analyzer/lib/la-arena/src/lib.rs b/src/tools/rust-analyzer/lib/la-arena/src/lib.rs new file mode 100644 index 000000000..dadee43b1 --- /dev/null +++ b/src/tools/rust-analyzer/lib/la-arena/src/lib.rs @@ -0,0 +1,366 @@ +//! Yet another index-based arena. + +#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)] +#![warn(missing_docs)] + +use std::{ + fmt, + hash::{Hash, Hasher}, + iter::FromIterator, + marker::PhantomData, + ops::{Index, IndexMut, Range, RangeInclusive}, +}; + +mod map; +pub use map::ArenaMap; + +/// The raw index of a value in an arena. +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct RawIdx(u32); + +impl From<RawIdx> for u32 { + fn from(raw: RawIdx) -> u32 { + raw.0 + } +} + +impl From<u32> for RawIdx { + fn from(idx: u32) -> RawIdx { + RawIdx(idx) + } +} + +impl fmt::Debug for RawIdx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(f) + } +} + +impl fmt::Display for RawIdx { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0.fmt(f) + } +} + +/// The index of a value allocated in an arena that holds `T`s. +pub struct Idx<T> { + raw: RawIdx, + _ty: PhantomData<fn() -> T>, +} + +impl<T> Clone for Idx<T> { + fn clone(&self) -> Self { + *self + } +} +impl<T> Copy for Idx<T> {} + +impl<T> PartialEq for Idx<T> { + fn eq(&self, other: &Idx<T>) -> bool { + self.raw == other.raw + } +} +impl<T> Eq for Idx<T> {} + +impl<T> Hash for Idx<T> { + fn hash<H: Hasher>(&self, state: &mut H) { + self.raw.hash(state); + } +} + +impl<T> fmt::Debug for Idx<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut type_name = std::any::type_name::<T>(); + if let Some(idx) = type_name.rfind(':') { + type_name = &type_name[idx + 1..]; + } + write!(f, "Idx::<{}>({})", type_name, self.raw) + } +} + +impl<T> Idx<T> { + /// Creates a new index from a [`RawIdx`]. + pub fn from_raw(raw: RawIdx) -> Self { + Idx { raw, _ty: PhantomData } + } + + /// Converts this index into the underlying [`RawIdx`]. + pub fn into_raw(self) -> RawIdx { + self.raw + } +} + +/// A range of densely allocated arena values. +pub struct IdxRange<T> { + range: Range<u32>, + _p: PhantomData<T>, +} + +impl<T> IdxRange<T> { + /// Creates a new index range + /// inclusive of the start value and exclusive of the end value. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let a = arena.alloc("a"); + /// let b = arena.alloc("b"); + /// let c = arena.alloc("c"); + /// let d = arena.alloc("d"); + /// + /// let range = la_arena::IdxRange::new(b..d); + /// assert_eq!(&arena[range], &["b", "c"]); + /// ``` + pub fn new(range: Range<Idx<T>>) -> Self { + Self { range: range.start.into_raw().into()..range.end.into_raw().into(), _p: PhantomData } + } + + /// Creates a new index range + /// inclusive of the start value and end value. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let foo = arena.alloc("foo"); + /// let bar = arena.alloc("bar"); + /// let baz = arena.alloc("baz"); + /// + /// let range = la_arena::IdxRange::new_inclusive(foo..=baz); + /// assert_eq!(&arena[range], &["foo", "bar", "baz"]); + /// + /// let range = la_arena::IdxRange::new_inclusive(foo..=foo); + /// assert_eq!(&arena[range], &["foo"]); + /// ``` + pub fn new_inclusive(range: RangeInclusive<Idx<T>>) -> Self { + Self { + range: u32::from(range.start().into_raw())..u32::from(range.end().into_raw()) + 1, + _p: PhantomData, + } + } + + /// Returns whether the index range is empty. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let one = arena.alloc(1); + /// let two = arena.alloc(2); + /// + /// assert!(la_arena::IdxRange::new(one..one).is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.range.is_empty() + } +} + +impl<T> Iterator for IdxRange<T> { + type Item = Idx<T>; + fn next(&mut self) -> Option<Self::Item> { + self.range.next().map(|raw| Idx::from_raw(raw.into())) + } +} + +impl<T> DoubleEndedIterator for IdxRange<T> { + fn next_back(&mut self) -> Option<Self::Item> { + self.range.next_back().map(|raw| Idx::from_raw(raw.into())) + } +} + +impl<T> fmt::Debug for IdxRange<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple(&format!("IdxRange::<{}>", std::any::type_name::<T>())) + .field(&self.range) + .finish() + } +} + +impl<T> Clone for IdxRange<T> { + fn clone(&self) -> Self { + Self { range: self.range.clone(), _p: PhantomData } + } +} + +impl<T> PartialEq for IdxRange<T> { + fn eq(&self, other: &Self) -> bool { + self.range == other.range + } +} + +impl<T> Eq for IdxRange<T> {} + +/// Yet another index-based arena. +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct Arena<T> { + data: Vec<T>, +} + +impl<T: fmt::Debug> fmt::Debug for Arena<T> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish() + } +} + +impl<T> Arena<T> { + /// Creates a new empty arena. + /// + /// ``` + /// let arena: la_arena::Arena<i32> = la_arena::Arena::new(); + /// assert!(arena.is_empty()); + /// ``` + pub const fn new() -> Arena<T> { + Arena { data: Vec::new() } + } + + /// Empties the arena, removing all contained values. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// + /// arena.alloc(1); + /// arena.alloc(2); + /// arena.alloc(3); + /// assert_eq!(arena.len(), 3); + /// + /// arena.clear(); + /// assert!(arena.is_empty()); + /// ``` + pub fn clear(&mut self) { + self.data.clear(); + } + + /// Returns the length of the arena. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// assert_eq!(arena.len(), 0); + /// + /// arena.alloc("foo"); + /// assert_eq!(arena.len(), 1); + /// + /// arena.alloc("bar"); + /// assert_eq!(arena.len(), 2); + /// + /// arena.alloc("baz"); + /// assert_eq!(arena.len(), 3); + /// ``` + pub fn len(&self) -> usize { + self.data.len() + } + + /// Returns whether the arena contains no elements. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// assert!(arena.is_empty()); + /// + /// arena.alloc(0.5); + /// assert!(!arena.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.data.is_empty() + } + + /// Allocates a new value on the arena, returning the value’s index. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let idx = arena.alloc(50); + /// + /// assert_eq!(arena[idx], 50); + /// ``` + pub fn alloc(&mut self, value: T) -> Idx<T> { + let idx = self.next_idx(); + self.data.push(value); + idx + } + + /// Returns an iterator over the arena’s elements. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let idx1 = arena.alloc(20); + /// let idx2 = arena.alloc(40); + /// let idx3 = arena.alloc(60); + /// + /// let mut iterator = arena.iter(); + /// assert_eq!(iterator.next(), Some((idx1, &20))); + /// assert_eq!(iterator.next(), Some((idx2, &40))); + /// assert_eq!(iterator.next(), Some((idx3, &60))); + /// ``` + pub fn iter( + &self, + ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator { + self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value)) + } + + /// Returns an iterator over the arena’s mutable elements. + /// + /// ``` + /// let mut arena = la_arena::Arena::new(); + /// let idx1 = arena.alloc(20); + /// + /// assert_eq!(arena[idx1], 20); + /// + /// let mut iterator = arena.iter_mut(); + /// *iterator.next().unwrap().1 = 10; + /// drop(iterator); + /// + /// assert_eq!(arena[idx1], 10); + /// ``` + pub fn iter_mut( + &mut self, + ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator { + self.data + .iter_mut() + .enumerate() + .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value)) + } + + /// Reallocates the arena to make it take up as little space as possible. + pub fn shrink_to_fit(&mut self) { + self.data.shrink_to_fit(); + } + + /// Returns the index of the next value allocated on the arena. + /// + /// This method should remain private to make creating invalid `Idx`s harder. + fn next_idx(&self) -> Idx<T> { + Idx::from_raw(RawIdx(self.data.len() as u32)) + } +} + +impl<T> Default for Arena<T> { + fn default() -> Arena<T> { + Arena { data: Vec::new() } + } +} + +impl<T> Index<Idx<T>> for Arena<T> { + type Output = T; + fn index(&self, idx: Idx<T>) -> &T { + let idx = idx.into_raw().0 as usize; + &self.data[idx] + } +} + +impl<T> IndexMut<Idx<T>> for Arena<T> { + fn index_mut(&mut self, idx: Idx<T>) -> &mut T { + let idx = idx.into_raw().0 as usize; + &mut self.data[idx] + } +} + +impl<T> Index<IdxRange<T>> for Arena<T> { + type Output = [T]; + fn index(&self, range: IdxRange<T>) -> &[T] { + let start = range.range.start as usize; + let end = range.range.end as usize; + &self.data[start..end] + } +} + +impl<T> FromIterator<T> for Arena<T> { + fn from_iter<I>(iter: I) -> Self + where + I: IntoIterator<Item = T>, + { + Arena { data: Vec::from_iter(iter) } + } +} diff --git a/src/tools/rust-analyzer/lib/la-arena/src/map.rs b/src/tools/rust-analyzer/lib/la-arena/src/map.rs new file mode 100644 index 000000000..d27f086d3 --- /dev/null +++ b/src/tools/rust-analyzer/lib/la-arena/src/map.rs @@ -0,0 +1,75 @@ +use std::marker::PhantomData; + +use crate::Idx; + +/// A map from arena indexes to some other type. +/// Space requirement is O(highest index). +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub struct ArenaMap<IDX, V> { + v: Vec<Option<V>>, + _ty: PhantomData<IDX>, +} + +impl<T, V> ArenaMap<Idx<T>, V> { + /// Inserts a value associated with a given arena index into the map. + pub fn insert(&mut self, idx: Idx<T>, t: V) { + let idx = Self::to_idx(idx); + + self.v.resize_with((idx + 1).max(self.v.len()), || None); + self.v[idx] = Some(t); + } + + /// Returns a reference to the value associated with the provided index + /// if it is present. + pub fn get(&self, idx: Idx<T>) -> Option<&V> { + self.v.get(Self::to_idx(idx)).and_then(|it| it.as_ref()) + } + + /// Returns a mutable reference to the value associated with the provided index + /// if it is present. + pub fn get_mut(&mut self, idx: Idx<T>) -> Option<&mut V> { + self.v.get_mut(Self::to_idx(idx)).and_then(|it| it.as_mut()) + } + + /// Returns an iterator over the values in the map. + pub fn values(&self) -> impl Iterator<Item = &V> { + self.v.iter().filter_map(|o| o.as_ref()) + } + + /// Returns an iterator over mutable references to the values in the map. + pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V> { + self.v.iter_mut().filter_map(|o| o.as_mut()) + } + + /// Returns an iterator over the arena indexes and values in the map. + pub fn iter(&self) -> impl Iterator<Item = (Idx<T>, &V)> { + self.v.iter().enumerate().filter_map(|(idx, o)| Some((Self::from_idx(idx), o.as_ref()?))) + } + + fn to_idx(idx: Idx<T>) -> usize { + u32::from(idx.into_raw()) as usize + } + + fn from_idx(idx: usize) -> Idx<T> { + Idx::from_raw((idx as u32).into()) + } +} + +impl<T, V> std::ops::Index<Idx<V>> for ArenaMap<Idx<V>, T> { + type Output = T; + fn index(&self, idx: Idx<V>) -> &T { + self.v[Self::to_idx(idx)].as_ref().unwrap() + } +} + +impl<T, V> std::ops::IndexMut<Idx<V>> for ArenaMap<Idx<V>, T> { + fn index_mut(&mut self, idx: Idx<V>) -> &mut T { + self.v[Self::to_idx(idx)].as_mut().unwrap() + } +} + +impl<T, V> Default for ArenaMap<Idx<V>, T> { + fn default() -> Self { + ArenaMap { v: Vec::new(), _ty: PhantomData } + } +} |