Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

2 files changed, 262 insertions, 75 deletions

diff --git a/compiler/rustc_index/src/bit_set.rs b/compiler/rustc_index/src/bit_set.rs
index cbf169afb..271ab8306 100644
--- a/compiler/rustc_index/src/bit_set.rs
+++ b/compiler/rustc_index/src/bit_set.rs
@@ -1,5 +1,6 @@
 use crate::vec::{Idx, IndexVec};
 use arrayvec::ArrayVec;
+use smallvec::{smallvec, SmallVec};
 use std::fmt;
 use std::iter;
 use std::marker::PhantomData;
@@ -111,7 +112,7 @@ macro_rules! bit_relations_inherent_impls {
 #[derive(Eq, PartialEq, Hash, Decodable, Encodable)]
 pub struct BitSet<T> {
     domain_size: usize,
-    words: Vec<Word>,
+    words: SmallVec<[Word; 2]>,
     marker: PhantomData<T>,
 }
 
@@ -127,14 +128,15 @@ impl<T: Idx> BitSet<T> {
     #[inline]
     pub fn new_empty(domain_size: usize) -> BitSet<T> {
         let num_words = num_words(domain_size);
-        BitSet { domain_size, words: vec![0; num_words], marker: PhantomData }
+        BitSet { domain_size, words: smallvec![0; num_words], marker: PhantomData }
     }
 
     /// Creates a new, filled bitset with a given `domain_size`.
     #[inline]
     pub fn new_filled(domain_size: usize) -> BitSet<T> {
         let num_words = num_words(domain_size);
-        let mut result = BitSet { domain_size, words: vec![!0; num_words], marker: PhantomData };
+        let mut result =
+            BitSet { domain_size, words: smallvec![!0; num_words], marker: PhantomData };
         result.clear_excess_bits();
         result
     }
@@ -1571,7 +1573,7 @@ impl<T: Idx> From<BitSet<T>> for GrowableBitSet<T> {
 pub struct BitMatrix<R: Idx, C: Idx> {
     num_rows: usize,
     num_columns: usize,
-    words: Vec<Word>,
+    words: SmallVec<[Word; 2]>,
     marker: PhantomData<(R, C)>,
 }
 
@@ -1584,7 +1586,7 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
         BitMatrix {
             num_rows,
             num_columns,
-            words: vec![0; num_rows * words_per_row],
+            words: smallvec![0; num_rows * words_per_row],
             marker: PhantomData,
         }
     }
@@ -1848,7 +1850,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 
     /// Iterates through all the columns set to true in a given row of
     /// the matrix.
-    pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
+    pub fn iter(&self, row: R) -> impl Iterator<Item = C> + '_ {
         self.row(row).into_iter().flat_map(|r| r.iter())
     }
 
diff --git a/compiler/rustc_index/src/vec.rs b/compiler/rustc_index/src/vec.rs
index 68cdc6d77..ae2f52c51 100644
--- a/compiler/rustc_index/src/vec.rs
+++ b/compiler/rustc_index/src/vec.rs
@@ -1,11 +1,12 @@
 #[cfg(feature = "rustc_serialize")]
 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::{Index, IndexMut, RangeBounds};
+use std::ops::{Deref, DerefMut, Index, IndexMut, RangeBounds};
 use std::slice;
 use std::vec;
 
@@ -23,6 +24,7 @@ pub trait Idx: Copy + 'static + Eq + PartialEq + Debug + Hash {
     }
 
     #[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)
     }
@@ -51,16 +53,41 @@ impl Idx for u32 {
     }
 }
 
+/// An owned contiguous collection of `T`s, indexed by `I` rather than by `usize`.
+///
+/// While it's possible to use `u32` or `usize` directly for `I`,
+/// you almost certainly want to use a [`newtype_index!`]-generated type instead.
+///
+/// [`newtype_index!`]: ../macro.newtype_index.html
 #[derive(Clone, PartialEq, Eq, Hash)]
+#[repr(transparent)]
 pub struct IndexVec<I: Idx, T> {
     pub raw: Vec<T>,
     _marker: PhantomData<fn(&I)>,
 }
 
+/// 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<I, T>` 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<I: Idx, T> {
+    _marker: PhantomData<fn(&I)>,
+    pub raw: [T],
+}
+
 // 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 {}
 
+// Whether `IndexSlice` is `Send` depends only on the data,
+// not the phantom data.
+unsafe impl<I: Idx, T> Send for IndexSlice<I, T> where T: Send {}
+
 #[cfg(feature = "rustc_serialize")]
 impl<S: Encoder, I: Idx, T: Encodable<S>> Encodable<S> for IndexVec<I, T> {
     fn encode(&self, s: &mut S) {
@@ -81,6 +108,12 @@ impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexVec<I, T> {
     }
 }
 
+impl<I: Idx, T: fmt::Debug> fmt::Debug for IndexSlice<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 {
@@ -97,8 +130,19 @@ impl<I: Idx, T> IndexVec<I, T> {
         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
     }
 
+    /// Creates a new vector with a copy of `elem` for each index in `universe`.
+    ///
+    /// Thus `IndexVec::from_elem(elem, &universe)` is equivalent to
+    /// `IndexVec::<I, _>::from_elem_n(elem, universe.len())`. That can help
+    /// type inference as it ensures that the resulting vector uses the same
+    /// index type as `universe`, rather than something potentially surprising.
+    ///
+    /// For example, if you want to store data for each local in a MIR body,
+    /// using `let mut uses = IndexVec::from_elem(vec![], &body.local_decls);`
+    /// ensures that `uses` is an `IndexVec<Local, _>`, and thus can give
+    /// better error messages later if one accidentally mismatches indices.
     #[inline]
-    pub fn from_elem<S>(elem: T, universe: &IndexVec<I, S>) -> Self
+    pub fn from_elem<S>(elem: T, universe: &IndexSlice<I, S>) -> Self
     where
         T: Clone,
     {
@@ -123,6 +167,16 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
+    pub fn as_slice(&self) -> &IndexSlice<I, T> {
+        IndexSlice::from_raw(&self.raw)
+    }
+
+    #[inline]
+    pub fn as_mut_slice(&mut self) -> &mut IndexSlice<I, T> {
+        IndexSlice::from_raw_mut(&mut self.raw)
+    }
+
+    #[inline]
     pub fn push(&mut self, d: T) -> I {
         let idx = I::new(self.len());
         self.raw.push(d);
@@ -135,32 +189,145 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
-    pub fn len(&self) -> usize {
-        self.raw.len()
+    pub fn into_iter(self) -> vec::IntoIter<T> {
+        self.raw.into_iter()
     }
 
-    /// Gives the next index that will be assigned when `push` is
-    /// called.
     #[inline]
-    pub fn next_index(&self) -> I {
-        I::new(self.len())
+    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 is_empty(&self) -> bool {
-        self.raw.is_empty()
+    pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> impl Iterator<Item = T> + '_ {
+        self.raw.drain(range)
     }
 
     #[inline]
-    pub fn into_iter(self) -> vec::IntoIter<T> {
-        self.raw.into_iter()
+    pub fn drain_enumerated<R: RangeBounds<usize>>(
+        &mut self,
+        range: R,
+    ) -> impl Iterator<Item = (I, T)> + '_ {
+        let begin = match range.start_bound() {
+            std::ops::Bound::Included(i) => *i,
+            std::ops::Bound::Excluded(i) => i.checked_add(1).unwrap(),
+            std::ops::Bound::Unbounded => 0,
+        };
+        self.raw.drain(range).enumerate().map(move |(n, t)| (I::new(begin + n), t))
     }
 
     #[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))
+    pub fn shrink_to_fit(&mut self) {
+        self.raw.shrink_to_fit()
+    }
+
+    #[inline]
+    pub fn truncate(&mut self, a: usize) {
+        self.raw.truncate(a)
+    }
+
+    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);
+    }
+}
+
+impl<I: Idx, T> Deref for IndexVec<I, T> {
+    type Target = IndexSlice<I, T>;
+
+    #[inline]
+    fn deref(&self) -> &Self::Target {
+        self.as_slice()
+    }
+}
+
+impl<I: Idx, T> DerefMut for IndexVec<I, T> {
+    #[inline]
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        self.as_mut_slice()
+    }
+}
+
+impl<I: Idx, T> Borrow<IndexSlice<I, T>> for IndexVec<I, T> {
+    fn borrow(&self) -> &IndexSlice<I, T> {
+        self
+    }
+}
+
+impl<I: Idx, T> BorrowMut<IndexSlice<I, T>> for IndexVec<I, T> {
+    fn borrow_mut(&mut self) -> &mut IndexSlice<I, T> {
+        self
+    }
+}
+
+impl<I: Idx, T: Clone> ToOwned for IndexSlice<I, T> {
+    type Owned = IndexVec<I, T>;
+
+    fn to_owned(&self) -> IndexVec<I, T> {
+        IndexVec::from_raw(self.raw.to_owned())
+    }
+
+    fn clone_into(&self, target: &mut IndexVec<I, T>) {
+        self.raw.clone_into(&mut target.raw)
+    }
+}
+
+impl<I: Idx, T> IndexSlice<I, T> {
+    #[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]
@@ -195,47 +362,16 @@ impl<I: Idx, T> IndexVec<I, 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 {
-        let begin = match range.start_bound() {
-            std::ops::Bound::Included(i) => *i,
-            std::ops::Bound::Excluded(i) => i.checked_add(1).unwrap(),
-            std::ops::Bound::Unbounded => 0,
-        };
-        self.raw.drain(range).enumerate().map(move |(n, t)| (I::new(begin + n), t))
-    }
-
-    #[inline]
-    pub fn last(&self) -> Option<I> {
+    pub fn last_index(&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())
     }
@@ -274,27 +410,35 @@ impl<I: Idx, T> IndexVec<I, T> {
         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);
+impl<I: Idx, J: Idx> IndexSlice<I, J> {
+    /// 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<J, I> {
+        debug_assert_eq!(
+            self.iter().map(|x| x.index() as u128).sum::<u128>(),
+            (0..self.len() as u128).sum::<u128>(),
+            "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;
         }
-    }
 
-    #[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);
+        debug_assert_eq!(
+            inverse.iter().map(|x| x.index() as u128).sum::<u128>(),
+            (0..inverse.len() as u128).sum::<u128>(),
+            "The values aren't 0..N in result {self:?}",
+        );
+
+        inverse
     }
 }
 
@@ -326,7 +470,7 @@ impl<I: Idx, T: Clone> IndexVec<I, T> {
     }
 }
 
-impl<I: Idx, T: Ord> IndexVec<I, T> {
+impl<I: Idx, T: Ord> IndexSlice<I, T> {
     #[inline]
     pub fn binary_search(&self, value: &T) -> Result<I, I> {
         match self.raw.binary_search(value) {
@@ -336,7 +480,7 @@ impl<I: Idx, T: Ord> IndexVec<I, T> {
     }
 }
 
-impl<I: Idx, T> Index<I> for IndexVec<I, T> {
+impl<I: Idx, T> Index<I> for IndexSlice<I, T> {
     type Output = T;
 
     #[inline]
@@ -345,7 +489,7 @@ impl<I: Idx, T> Index<I> for IndexVec<I, T> {
     }
 }
 
-impl<I: Idx, T> IndexMut<I> for IndexVec<I, T> {
+impl<I: Idx, T> IndexMut<I> for IndexSlice<I, T> {
     #[inline]
     fn index_mut(&mut self, index: I) -> &mut T {
         &mut self.raw[index.index()]
@@ -359,6 +503,20 @@ impl<I: Idx, T> Default for IndexVec<I, T> {
     }
 }
 
+impl<I: Idx, T> Default for &IndexSlice<I, T> {
+    #[inline]
+    fn default() -> Self {
+        IndexSlice::from_raw(Default::default())
+    }
+}
+
+impl<I: Idx, T> Default for &mut IndexSlice<I, T> {
+    #[inline]
+    fn default() -> Self {
+        IndexSlice::from_raw_mut(Default::default())
+    }
+}
+
 impl<I: Idx, T> Extend<T> for IndexVec<I, T> {
     #[inline]
     fn extend<J: IntoIterator<Item = T>>(&mut self, iter: J) {
@@ -388,6 +546,13 @@ impl<I: Idx, T> FromIterator<T> for IndexVec<I, T> {
     }
 }
 
+impl<I: Idx, T, const N: usize> From<[T; N]> for IndexVec<I, T> {
+    #[inline]
+    fn from(array: [T; N]) -> Self {
+        IndexVec::from_raw(array.into())
+    }
+}
+
 impl<I: Idx, T> IntoIterator for IndexVec<I, T> {
     type Item = T;
     type IntoIter = vec::IntoIter<T>;
@@ -418,5 +583,25 @@ impl<'a, I: Idx, T> IntoIterator for &'a mut IndexVec<I, T> {
     }
 }
 
+impl<'a, I: Idx, T> IntoIterator for &'a IndexSlice<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 IndexSlice<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;