From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 18 May 2024 04:49:50 +0200 Subject: Merging upstream version 1.71.1+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_index/src/vec.rs | 424 +++++++--------------------------------- 1 file changed, 68 insertions(+), 356 deletions(-) (limited to 'compiler/rustc_index/src/vec.rs') diff --git a/compiler/rustc_index/src/vec.rs b/compiler/rustc_index/src/vec.rs index ae2f52c51..99e72e49f 100644 --- a/compiler/rustc_index/src/vec.rs +++ b/compiler/rustc_index/src/vec.rs @@ -3,55 +3,13 @@ use rustc_serialize::{Decodable, Decoder, Encodable, Encoder}; use std::borrow::{Borrow, BorrowMut}; use std::fmt; -use std::fmt::Debug; use std::hash::Hash; use std::marker::PhantomData; -use std::ops::{Deref, DerefMut, Index, IndexMut, RangeBounds}; +use std::ops::{Deref, DerefMut, 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; - - #[inline] - fn increment_by(&mut self, amount: usize) { - *self = self.plus(amount); - } - - #[inline] - #[must_use = "Use `increment_by` if you wanted to update the index in-place"] - 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 - } -} +use crate::{Idx, IndexSlice}; /// An owned contiguous collection of `T`s, indexed by `I` rather than by `usize`. /// @@ -66,68 +24,20 @@ pub struct IndexVec { _marker: PhantomData, } -/// A view into contiguous `T`s, indexed by `I` rather than by `usize`. -/// -/// One common pattern you'll see is code that uses [`IndexVec::from_elem`] -/// to create the storage needed for a particular "universe" (aka the set of all -/// the possible keys that need an associated value) then passes that working -/// area as `&mut IndexSlice` to clarify that nothing will be added nor -/// removed during processing (and, as a bonus, to chase fewer pointers). -#[derive(PartialEq, Eq, Hash)] -#[repr(transparent)] -pub struct IndexSlice { - _marker: PhantomData, - pub raw: [T], -} - -// Whether `IndexVec` is `Send` depends only on the data, -// not the phantom data. -unsafe impl Send for IndexVec where T: Send {} - -// Whether `IndexSlice` is `Send` depends only on the data, -// not the phantom data. -unsafe impl Send for IndexSlice where T: Send {} - -#[cfg(feature = "rustc_serialize")] -impl> Encodable for IndexVec { - fn encode(&self, s: &mut S) { - Encodable::encode(&self.raw, s); - } -} - -#[cfg(feature = "rustc_serialize")] -impl> Decodable for IndexVec { - fn decode(d: &mut D) -> Self { - IndexVec { raw: Decodable::decode(d), _marker: PhantomData } - } -} - -impl fmt::Debug for IndexVec { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt::Debug::fmt(&self.raw, fmt) - } -} - -impl fmt::Debug for IndexSlice { - fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { - fmt::Debug::fmt(&self.raw, fmt) - } -} - impl IndexVec { #[inline] - pub fn new() -> Self { - IndexVec { raw: Vec::new(), _marker: PhantomData } + pub const fn new() -> Self { + IndexVec::from_raw(Vec::new()) } #[inline] - pub fn from_raw(raw: Vec) -> Self { + pub const fn from_raw(raw: Vec) -> Self { IndexVec { raw, _marker: PhantomData } } #[inline] pub fn with_capacity(capacity: usize) -> Self { - IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData } + IndexVec::from_raw(Vec::with_capacity(capacity)) } /// Creates a new vector with a copy of `elem` for each index in `universe`. @@ -146,7 +56,7 @@ impl IndexVec { where T: Clone, { - IndexVec { raw: vec![elem; universe.len()], _marker: PhantomData } + IndexVec::from_raw(vec![elem; universe.len()]) } #[inline] @@ -154,7 +64,7 @@ impl IndexVec { where T: Clone, { - IndexVec { raw: vec![elem; n], _marker: PhantomData } + IndexVec::from_raw(vec![elem; n]) } /// Create an `IndexVec` with `n` elements, where the value of each @@ -162,8 +72,7 @@ impl IndexVec { /// 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()) + IndexVec::from_raw((0..n).map(I::new).map(func).collect()) } #[inline] @@ -178,7 +87,7 @@ impl IndexVec { #[inline] pub fn push(&mut self, d: T) -> I { - let idx = I::new(self.len()); + let idx = self.next_index(); self.raw.push(d); idx } @@ -229,216 +138,37 @@ impl IndexVec { } pub fn convert_index_type(self) -> IndexVec { - IndexVec { raw: self.raw, _marker: PhantomData } + IndexVec::from_raw(self.raw) } /// 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`. + /// + /// Returns a reference to the `elem` entry. #[inline] - pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) { + pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) -> &mut 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); - } -} - -impl Deref for IndexVec { - type Target = IndexSlice; - - #[inline] - fn deref(&self) -> &Self::Target { - self.as_slice() - } -} - -impl DerefMut for IndexVec { - #[inline] - fn deref_mut(&mut self) -> &mut Self::Target { - self.as_mut_slice() - } -} - -impl Borrow> for IndexVec { - fn borrow(&self) -> &IndexSlice { - self - } -} - -impl BorrowMut> for IndexVec { - fn borrow_mut(&mut self) -> &mut IndexSlice { - self - } -} - -impl ToOwned for IndexSlice { - type Owned = IndexVec; - - fn to_owned(&self) -> IndexVec { - IndexVec::from_raw(self.raw.to_owned()) - } - - fn clone_into(&self, target: &mut IndexVec) { - self.raw.clone_into(&mut target.raw) - } -} - -impl IndexSlice { - #[inline] - pub fn empty() -> &'static Self { - Default::default() - } - - #[inline] - pub fn from_raw(raw: &[T]) -> &Self { - let ptr: *const [T] = raw; - // SAFETY: `IndexSlice` is `repr(transparent)` over a normal slice - unsafe { &*(ptr as *const Self) } - } - - #[inline] - pub fn from_raw_mut(raw: &mut [T]) -> &mut Self { - let ptr: *mut [T] = raw; - // SAFETY: `IndexSlice` is `repr(transparent)` over a normal slice - unsafe { &mut *(ptr as *mut Self) } - } - - #[inline] - pub fn len(&self) -> usize { - self.raw.len() - } - - /// Gives the next index that will be assigned when `push` is called. - /// - /// Manual bounds checks can be done using `idx < slice.next_index()` - /// (as opposed to `idx.index() < slice.len()`). - #[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 iter(&self) -> slice::Iter<'_, T> { - self.raw.iter() - } - #[inline] - pub fn iter_enumerated( - &self, - ) -> impl DoubleEndedIterator + ExactSizeIterator + '_ { - self.raw.iter().enumerate().map(|(n, t)| (I::new(n), t)) - } - - #[inline] - pub fn indices( - &self, - ) -> impl DoubleEndedIterator + ExactSizeIterator + Clone + 'static { - (0..self.len()).map(|n| I::new(n)) - } - - #[inline] - pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> { - self.raw.iter_mut() + &mut self[elem] } #[inline] - pub fn iter_enumerated_mut( - &mut self, - ) -> impl DoubleEndedIterator + ExactSizeIterator + '_ { - self.raw.iter_mut().enumerate().map(|(n, t)| (I::new(n), t)) - } - - #[inline] - pub fn last_index(&self) -> Option { - self.len().checked_sub(1).map(I::new) - } - - #[inline] - pub fn swap(&mut self, a: I, b: I) { - self.raw.swap(a.index(), b.index()) - } - - #[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) - } + pub fn resize(&mut self, new_len: usize, value: T) + where + T: Clone, + { + self.raw.resize(new_len, value) } - /// 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)) } - } -} - -impl IndexSlice { - /// Invert a bijective mapping, i.e. `invert(map)[y] = x` if `map[x] = y`, - /// assuming the values in `self` are a permutation of `0..self.len()`. - /// - /// This is used to go between `memory_index` (source field order to memory order) - /// and `inverse_memory_index` (memory order to source field order). - /// See also `FieldsShape::Arbitrary::memory_index` for more details. - // FIXME(eddyb) build a better abstraction for permutations, if possible. - pub fn invert_bijective_mapping(&self) -> IndexVec { - debug_assert_eq!( - self.iter().map(|x| x.index() as u128).sum::(), - (0..self.len() as u128).sum::(), - "The values aren't 0..N in input {self:?}", - ); - - let mut inverse = IndexVec::from_elem_n(Idx::new(0), self.len()); - for (i1, &i2) in self.iter_enumerated() { - inverse[i2] = i1; - } - - debug_assert_eq!( - inverse.iter().map(|x| x.index() as u128).sum::(), - (0..inverse.len() as u128).sum::(), - "The values aren't 0..N in result {self:?}", - ); - - inverse + 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); } } @@ -446,74 +176,51 @@ impl IndexSlice { impl IndexVec> { #[inline] pub fn insert(&mut self, index: I, value: T) -> Option { - self.ensure_contains_elem(index, || None); - self[index].replace(value) + self.ensure_contains_elem(index, || None).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) + self.ensure_contains_elem(index, || None).get_or_insert_with(value) } #[inline] pub fn remove(&mut self, index: I) -> Option { - self.ensure_contains_elem(index, || None); - self[index].take() - } -} - -impl IndexVec { - #[inline] - pub fn resize(&mut self, new_len: usize, value: T) { - self.raw.resize(new_len, value) + self.get_mut(index)?.take() } } -impl IndexSlice { - #[inline] - pub fn binary_search(&self, value: &T) -> Result { - match self.raw.binary_search(value) { - Ok(i) => Ok(Idx::new(i)), - Err(i) => Err(Idx::new(i)), - } +impl fmt::Debug for IndexVec { + fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.raw, fmt) } } -impl Index for IndexSlice { - type Output = T; - - #[inline] - fn index(&self, index: I) -> &T { - &self.raw[index.index()] - } -} +impl Deref for IndexVec { + type Target = IndexSlice; -impl IndexMut for IndexSlice { #[inline] - fn index_mut(&mut self, index: I) -> &mut T { - &mut self.raw[index.index()] + fn deref(&self) -> &Self::Target { + self.as_slice() } } -impl Default for IndexVec { +impl DerefMut for IndexVec { #[inline] - fn default() -> Self { - Self::new() + fn deref_mut(&mut self) -> &mut Self::Target { + self.as_mut_slice() } } -impl Default for &IndexSlice { - #[inline] - fn default() -> Self { - IndexSlice::from_raw(Default::default()) +impl Borrow> for IndexVec { + fn borrow(&self) -> &IndexSlice { + self } } -impl Default for &mut IndexSlice { - #[inline] - fn default() -> Self { - IndexSlice::from_raw_mut(Default::default()) +impl BorrowMut> for IndexVec { + fn borrow_mut(&mut self) -> &mut IndexSlice { + self } } @@ -542,14 +249,7 @@ impl FromIterator for IndexVec { where J: IntoIterator, { - IndexVec { raw: FromIterator::from_iter(iter), _marker: PhantomData } - } -} - -impl From<[T; N]> for IndexVec { - #[inline] - fn from(array: [T; N]) -> Self { - IndexVec::from_raw(array.into()) + IndexVec::from_raw(Vec::from_iter(iter)) } } @@ -569,7 +269,7 @@ impl<'a, I: Idx, T> IntoIterator for &'a IndexVec { #[inline] fn into_iter(self) -> slice::Iter<'a, T> { - self.raw.iter() + self.iter() } } @@ -579,29 +279,41 @@ impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec { #[inline] fn into_iter(self) -> slice::IterMut<'a, T> { - self.raw.iter_mut() + self.iter_mut() } } -impl<'a, I: Idx, T> IntoIterator for &'a IndexSlice { - type Item = &'a T; - type IntoIter = slice::Iter<'a, T>; +impl Default for IndexVec { + #[inline] + fn default() -> Self { + IndexVec::new() + } +} +impl From<[T; N]> for IndexVec { #[inline] - fn into_iter(self) -> slice::Iter<'a, T> { - self.raw.iter() + fn from(array: [T; N]) -> Self { + IndexVec::from_raw(array.into()) } } -impl<'a, I: Idx, T> IntoIterator for &'a mut IndexSlice { - type Item = &'a mut T; - type IntoIter = slice::IterMut<'a, T>; +#[cfg(feature = "rustc_serialize")] +impl> Encodable for IndexVec { + fn encode(&self, s: &mut S) { + Encodable::encode(&self.raw, s); + } +} - #[inline] - fn into_iter(self) -> slice::IterMut<'a, T> { - self.raw.iter_mut() +#[cfg(feature = "rustc_serialize")] +impl> Decodable for IndexVec { + fn decode(d: &mut D) -> Self { + IndexVec::from_raw(Vec::::decode(d)) } } +// Whether `IndexVec` is `Send` depends only on the data, +// not the phantom data. +unsafe impl Send for IndexVec where T: Send {} + #[cfg(test)] mod tests; -- cgit v1.2.3