diff options
Diffstat (limited to 'compiler/rustc_index/src/vec.rs')
-rw-r--r-- | compiler/rustc_index/src/vec.rs | 409 |
1 files changed, 409 insertions, 0 deletions
diff --git a/compiler/rustc_index/src/vec.rs b/compiler/rustc_index/src/vec.rs new file mode 100644 index 000000000..30ff36421 --- /dev/null +++ b/compiler/rustc_index/src/vec.rs @@ -0,0 +1,409 @@ +use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; + +use std::fmt; +use std::fmt::Debug; +use std::hash::Hash; +use std::iter::FromIterator; +use std::marker::PhantomData; +use std::ops::{Index, IndexMut, RangeBounds}; +use std::slice; +use std::vec; + +/// Represents some newtyped `usize` wrapper. +/// +/// Purpose: avoid mixing indexes for different bitvector domains. +pub trait Idx: Copy + 'static + Eq + PartialEq + Debug + Hash { + fn new(idx: usize) -> Self; + + fn index(self) -> usize; + + fn increment_by(&mut self, amount: usize) { + *self = self.plus(amount); + } + + fn plus(self, amount: usize) -> Self { + Self::new(self.index() + amount) + } +} + +impl Idx for usize { + #[inline] + fn new(idx: usize) -> Self { + idx + } + #[inline] + fn index(self) -> usize { + self + } +} + +impl Idx for u32 { + #[inline] + fn new(idx: usize) -> Self { + assert!(idx <= u32::MAX as usize); + idx as u32 + } + #[inline] + fn index(self) -> usize { + self as usize + } +} + +#[derive(Clone, PartialEq, Eq, Hash)] +pub struct IndexVec<I: Idx, T> { + pub raw: Vec<T>, + _marker: PhantomData<fn(&I)>, +} + +// Whether `IndexVec` is `Send` depends only on the data, +// not the phantom data. +unsafe impl<I: Idx, T> Send for IndexVec<I, T> where T: Send {} + +impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> { + fn encode(&self, s: &mut S) { + Encodable::encode(&self.raw, s); + } +} + +impl<D: Decoder, I: Idx, T: Decodable<D>> Decodable<D> for IndexVec<I, T> { + fn decode(d: &mut D) -> Self { + IndexVec { raw: Decodable::decode(d), _marker: PhantomData } + } +} + +impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.raw, fmt) + } +} + +impl<I: Idx, T> IndexVec<I, T> { + #[inline] + pub fn new() -> Self { + IndexVec { raw: Vec::new(), _marker: PhantomData } + } + + #[inline] + pub fn from_raw(raw: Vec<T>) -> Self { + IndexVec { raw, _marker: PhantomData } + } + + #[inline] + pub fn with_capacity(capacity: usize) -> Self { + IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData } + } + + #[inline] + pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self + where + T: Clone, + { + IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData } + } + + #[inline] + pub fn from_elem_n(elem: T, n: usize) -> Self + where + T: Clone, + { + IndexVec { raw: vec![elem; n], _marker: PhantomData } + } + + /// Create an `IndexVec` with `n` elements, where the value of each + /// element is the result of `func(i)`. (The underlying vector will + /// be allocated only once, with a capacity of at least `n`.) + #[inline] + pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self { + let indices = (0..n).map(I::new); + Self::from_raw(indices.map(func).collect()) + } + + #[inline] + pub fn push(&mut self, d: T) -> I { + let idx = I::new(self.len()); + self.raw.push(d); + idx + } + + #[inline] + pub fn pop(&mut self) -> Option<T> { + self.raw.pop() + } + + #[inline] + pub fn len(&self) -> usize { + self.raw.len() + } + + /// Gives the next index that will be assigned when `push` is + /// called. + #[inline] + pub fn next_index(&self) -> I { + I::new(self.len()) + } + + #[inline] + pub fn is_empty(&self) -> bool { + self.raw.is_empty() + } + + #[inline] + pub fn into_iter(self) -> vec::IntoIter<T> { + self.raw.into_iter() + } + + #[inline] + pub fn into_iter_enumerated( + self, + ) -> impl DoubleEndedIterator<Item = (I, T)> + ExactSizeIterator { + self.raw.into_iter().enumerate().map(|(n, t)| (I::new(n), t)) + } + + #[inline] + pub fn iter(&self) -> slice::Iter<'_, T> { + self.raw.iter() + } + + #[inline] + pub fn iter_enumerated( + &self, + ) -> impl DoubleEndedIterator<Item = (I, &T)> + ExactSizeIterator + '_ { + self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t)) + } + + #[inline] + pub fn indices(&self) -> impl DoubleEndedIterator<Item = I> + ExactSizeIterator + 'static { + (0..self.len()).map(|n| I::new(n)) + } + + #[inline] + pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { + self.raw.iter_mut() + } + + #[inline] + pub fn iter_enumerated_mut( + &mut self, + ) -> impl DoubleEndedIterator<Item = (I, &mut T)> + ExactSizeIterator + '_ { + self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t)) + } + + #[inline] + pub fn drain<'a, R: RangeBounds<usize>>( + &'a mut self, + range: R, + ) -> impl Iterator<Item = T> + 'a { + self.raw.drain(range) + } + + #[inline] + pub fn drain_enumerated<'a, R: RangeBounds<usize>>( + &'a mut self, + range: R, + ) -> impl Iterator<Item = (I, T)> + 'a { + self.raw.drain(range).enumerate().map(|(n, t)| (I::new(n), t)) + } + + #[inline] + pub fn last(&self) -> Option<I> { + self.len().checked_sub(1).map(I::new) + } + + #[inline] + pub fn shrink_to_fit(&mut self) { + self.raw.shrink_to_fit() + } + + #[inline] + pub fn swap(&mut self, a: I, b: I) { + self.raw.swap(a.index(), b.index()) + } + + #[inline] + pub fn truncate(&mut self, a: usize) { + self.raw.truncate(a) + } + + #[inline] + pub fn get(&self, index: I) -> Option<&T> { + self.raw.get(index.index()) + } + + #[inline] + pub fn get_mut(&mut self, index: I) -> Option<&mut T> { + self.raw.get_mut(index.index()) + } + + /// Returns mutable references to two distinct elements, `a` and `b`. + /// + /// Panics if `a == b`. + #[inline] + pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) { + let (ai, bi) = (a.index(), b.index()); + assert!(ai != bi); + + if ai < bi { + let (c1, c2) = self.raw.split_at_mut(bi); + (&mut c1[ai], &mut c2[0]) + } else { + let (c2, c1) = self.pick2_mut(b, a); + (c1, c2) + } + } + + /// Returns mutable references to three distinct elements. + /// + /// Panics if the elements are not distinct. + #[inline] + pub fn pick3_mut(&mut self, a: I, b: I, c: I) -> (&mut T, &mut T, &mut T) { + let (ai, bi, ci) = (a.index(), b.index(), c.index()); + assert!(ai != bi && bi != ci && ci != ai); + let len = self.raw.len(); + assert!(ai < len && bi < len && ci < len); + let ptr = self.raw.as_mut_ptr(); + unsafe { (&mut *ptr.add(ai), &mut *ptr.add(bi), &mut *ptr.add(ci)) } + } + + pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> { + IndexVec { raw: self.raw, _marker: PhantomData } + } + + /// Grows the index vector so that it contains an entry for + /// `elem`; if that is already true, then has no + /// effect. Otherwise, inserts new values as needed by invoking + /// `fill_value`. + #[inline] + pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { + let min_new_len = elem.index() + 1; + if self.len() < min_new_len { + self.raw.resize_with(min_new_len, fill_value); + } + } + + #[inline] + pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { + let min_new_len = elem.index() + 1; + self.raw.resize_with(min_new_len, fill_value); + } +} + +/// `IndexVec` is often used as a map, so it provides some map-like APIs. +impl<I: Idx, T> IndexVec<I, Option<T>> { + #[inline] + pub fn insert(&mut self, index: I, value: T) -> Option<T> { + self.ensure_contains_elem(index, || None); + self[index].replace(value) + } + + #[inline] + pub fn get_or_insert_with(&mut self, index: I, value: impl FnOnce() -> T) -> &mut T { + self.ensure_contains_elem(index, || None); + self[index].get_or_insert_with(value) + } + + #[inline] + pub fn remove(&mut self, index: I) -> Option<T> { + self.ensure_contains_elem(index, || None); + self[index].take() + } +} + +impl<I: Idx, T: Clone> IndexVec<I, T> { + #[inline] + pub fn resize(&mut self, new_len: usize, value: T) { + self.raw.resize(new_len, value) + } +} + +impl<I: Idx, T: Ord> IndexVec<I, T> { + #[inline] + pub fn binary_search(&self, value: &T) -> Result<I, I> { + match self.raw.binary_search(value) { + Ok(i) => Ok(Idx::new(i)), + Err(i) => Err(Idx::new(i)), + } + } +} + +impl<I: Idx, T> Index<I> for IndexVec<I, T> { + type Output = T; + + #[inline] + fn index(&self, index: I) -> &T { + &self.raw[index.index()] + } +} + +impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> { + #[inline] + fn index_mut(&mut self, index: I) -> &mut T { + &mut self.raw[index.index()] + } +} + +impl<I: Idx, T> Default for IndexVec<I, T> { + #[inline] + fn default() -> Self { + Self::new() + } +} + +impl<I: Idx, T> Extend<T> for IndexVec<I, T> { + #[inline] + fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) { + self.raw.extend(iter); + } + + #[inline] + fn extend_one(&mut self, item: T) { + self.raw.push(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.raw.reserve(additional); + } +} + +impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> { + #[inline] + fn from_iter<J>(iter: J) -> Self + where + J: IntoIterator<Item = T>, + { + IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } + } +} + +impl<I: Idx, T> IntoIterator for IndexVec<I, T> { + type Item = T; + type IntoIter = vec::IntoIter<T>; + + #[inline] + fn into_iter(self) -> vec::IntoIter<T> { + self.raw.into_iter() + } +} + +impl<'a, I: Idx, T> IntoIterator for &'a IndexVec<I, T> { + type Item = &'a T; + type IntoIter = slice::Iter<'a, T>; + + #[inline] + fn into_iter(self) -> slice::Iter<'a, T> { + self.raw.iter() + } +} + +impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> { + type Item = &'a mut T; + type IntoIter = slice::IterMut<'a, T>; + + #[inline] + fn into_iter(self) -> slice::IterMut<'a, T> { + self.raw.iter_mut() + } +} + +#[cfg(test)] +mod tests; |