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/slice.rs | 256 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 256 insertions(+) create mode 100644 compiler/rustc_index/src/slice.rs (limited to 'compiler/rustc_index/src/slice.rs') diff --git a/compiler/rustc_index/src/slice.rs b/compiler/rustc_index/src/slice.rs new file mode 100644 index 000000000..0663c7247 --- /dev/null +++ b/compiler/rustc_index/src/slice.rs @@ -0,0 +1,256 @@ +use std::{ + fmt, + marker::PhantomData, + ops::{Index, IndexMut}, + slice, +}; + +use crate::{Idx, IndexVec}; + +/// 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], +} + +impl IndexSlice { + #[inline] + pub const fn empty() -> &'static Self { + Self::from_raw(&[]) + } + + #[inline] + pub const 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 const fn len(&self) -> usize { + self.raw.len() + } + + #[inline] + pub const fn is_empty(&self) -> bool { + self.raw.is_empty() + } + + /// 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 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() + } + + #[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) + } + } + + /// 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)) } + } + + #[inline] + pub fn binary_search(&self, value: &T) -> Result + where + T: Ord, + { + match self.raw.binary_search(value) { + Ok(i) => Ok(Idx::new(i)), + Err(i) => Err(Idx::new(i)), + } + } +} + +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 + } +} + +impl fmt::Debug for IndexSlice { + 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 IndexMut for IndexSlice { + #[inline] + fn index_mut(&mut self, index: I) -> &mut T { + &mut self.raw[index.index()] + } +} + +impl<'a, I: Idx, T> IntoIterator for &'a IndexSlice { + 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 IndexSlice { + type Item = &'a mut T; + type IntoIter = slice::IterMut<'a, T>; + + #[inline] + fn into_iter(self) -> slice::IterMut<'a, T> { + self.raw.iter_mut() + } +} + +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 Default for &IndexSlice { + #[inline] + fn default() -> Self { + IndexSlice::from_raw(Default::default()) + } +} + +impl Default for &mut IndexSlice { + #[inline] + fn default() -> Self { + IndexSlice::from_raw_mut(Default::default()) + } +} + +// Whether `IndexSlice` is `Send` depends only on the data, +// not the phantom data. +unsafe impl Send for IndexSlice where T: Send {} -- cgit v1.2.3