mir: use `FiniteBitSet<u32>` in polymorphization

[rust.git] / src / librustc_index / bit_set.rs

diff --git a/src/librustc_index/bit_set.rs b/src/librustc_index/bit_set.rs
index a9a1564366d53bd636d91868ff421fea531ec2b9..e4b7c24a24989b3e9adffb533740013db24f773d 100644 (file)
--- a/src/librustc_index/bit_set.rs
+++ b/src/librustc_index/bit_set.rs
@@ -1,9 +1,10 @@
 use crate::vec::{Idx, IndexVec};
-use smallvec::SmallVec;
+use arrayvec::ArrayVec;
 use std::fmt;
 use std::iter;
 use std::marker::PhantomData;
 use std::mem;
+use std::ops::{BitAnd, BitAndAssign, BitOrAssign, Not, Range, Shl};
 use std::slice;
 
 #[cfg(test)]
@@ -355,20 +356,19 @@ fn bitwise<Op>(out_vec: &mut [Word], in_vec: &[Word], op: Op) -> bool
 const SPARSE_MAX: usize = 8;
 
 /// A fixed-size bitset type with a sparse representation and a maximum of
-/// `SPARSE_MAX` elements. The elements are stored as a sorted `SmallVec` with
-/// no duplicates; although `SmallVec` can spill its elements to the heap, that
-/// never happens within this type because of the `SPARSE_MAX` limit.
+/// `SPARSE_MAX` elements. The elements are stored as a sorted `ArrayVec` with
+/// no duplicates.
 ///
 /// This type is used by `HybridBitSet`; do not use directly.
 #[derive(Clone, Debug)]
 pub struct SparseBitSet<T: Idx> {
     domain_size: usize,
-    elems: SmallVec<[T; SPARSE_MAX]>,
+    elems: ArrayVec<[T; SPARSE_MAX]>,
 }
 
 impl<T: Idx> SparseBitSet<T> {
     fn new_empty(domain_size: usize) -> Self {
-        SparseBitSet { domain_size, elems: SmallVec::new() }
+        SparseBitSet { domain_size, elems: ArrayVec::new() }
     }
 
     fn len(&self) -> usize {
@@ -1002,3 +1002,161 @@ fn word_index_and_mask<T: Idx>(elem: T) -> (usize, Word) {
     let mask = 1 << (elem % WORD_BITS);
     (word_index, mask)
 }
+
+/// Integral type used to represent the bit set.
+pub trait FiniteBitSetTy:
+    BitAnd<Output = Self>
+    + BitAndAssign
+    + BitOrAssign
+    + Clone
+    + Copy
+    + Shl
+    + Not<Output = Self>
+    + PartialEq
+    + Sized
+{
+    /// Size of the domain representable by this type, e.g. 64 for `u64`.
+    const DOMAIN_SIZE: u32;
+
+    /// Value which represents the `FiniteBitSet` having every bit set.
+    const FILLED: Self;
+    /// Value which represents the `FiniteBitSet` having no bits set.
+    const EMPTY: Self;
+
+    /// Value for one as the integral type.
+    const ONE: Self;
+    /// Value for zero as the integral type.
+    const ZERO: Self;
+
+    /// Perform a checked left shift on the integral type.
+    fn checked_shl(self, rhs: u32) -> Option<Self>;
+    /// Perform a checked right shift on the integral type.
+    fn checked_shr(self, rhs: u32) -> Option<Self>;
+}
+
+impl FiniteBitSetTy for u32 {
+    const DOMAIN_SIZE: u32 = 32;
+
+    const FILLED: Self = Self::MAX;
+    const EMPTY: Self = Self::MIN;
+
+    const ONE: Self = 1u32;
+    const ZERO: Self = 0u32;
+
+    fn checked_shl(self, rhs: u32) -> Option<Self> {
+        self.checked_shl(rhs)
+    }
+
+    fn checked_shr(self, rhs: u32) -> Option<Self> {
+        self.checked_shr(rhs)
+    }
+}
+
+impl std::fmt::Debug for FiniteBitSet<u32> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:032b}", self.0)
+    }
+}
+
+impl FiniteBitSetTy for u64 {
+    const DOMAIN_SIZE: u32 = 64;
+
+    const FILLED: Self = Self::MAX;
+    const EMPTY: Self = Self::MIN;
+
+    const ONE: Self = 1u64;
+    const ZERO: Self = 0u64;
+
+    fn checked_shl(self, rhs: u32) -> Option<Self> {
+        self.checked_shl(rhs)
+    }
+
+    fn checked_shr(self, rhs: u32) -> Option<Self> {
+        self.checked_shr(rhs)
+    }
+}
+
+impl std::fmt::Debug for FiniteBitSet<u64> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:064b}", self.0)
+    }
+}
+
+impl FiniteBitSetTy for u128 {
+    const DOMAIN_SIZE: u32 = 128;
+
+    const FILLED: Self = Self::MAX;
+    const EMPTY: Self = Self::MIN;
+
+    const ONE: Self = 1u128;
+    const ZERO: Self = 0u128;
+
+    fn checked_shl(self, rhs: u32) -> Option<Self> {
+        self.checked_shl(rhs)
+    }
+
+    fn checked_shr(self, rhs: u32) -> Option<Self> {
+        self.checked_shr(rhs)
+    }
+}
+
+impl std::fmt::Debug for FiniteBitSet<u128> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{:0128b}", self.0)
+    }
+}
+
+/// A fixed-sized bitset type represented by an integer type. Indices outwith than the range
+/// representable by `T` are considered set.
+#[derive(Copy, Clone, Eq, PartialEq, RustcDecodable, RustcEncodable)]
+pub struct FiniteBitSet<T: FiniteBitSetTy>(pub T);
+
+impl<T: FiniteBitSetTy> FiniteBitSet<T> {
+    /// Creates a new, empty bitset.
+    pub fn new_empty() -> Self {
+        Self(T::EMPTY)
+    }
+
+    /// Sets the `index`th bit.
+    pub fn set(&mut self, index: u32) {
+        self.0 |= T::ONE.checked_shl(index).unwrap_or(T::ZERO);
+    }
+
+    /// Unsets the `index`th bit.
+    pub fn clear(&mut self, index: u32) {
+        self.0 &= !T::ONE.checked_shl(index).unwrap_or(T::ZERO);
+    }
+
+    /// Sets the `i`th to `j`th bits.
+    pub fn set_range(&mut self, range: Range<u32>) {
+        let bits = T::FILLED
+            .checked_shl(range.end - range.start)
+            .unwrap_or(T::ZERO)
+            .not()
+            .checked_shl(range.start)
+            .unwrap_or(T::ZERO);
+        self.0 |= bits;
+    }
+
+    /// Is the set empty?
+    pub fn is_empty(&self) -> bool {
+        self.0 == T::EMPTY
+    }
+
+    /// Returns the domain size of the bitset.
+    pub fn within_domain(&self, index: u32) -> bool {
+        index < T::DOMAIN_SIZE
+    }
+
+    /// Returns if the `index`th bit is set.
+    pub fn contains(&self, index: u32) -> Option<bool> {
+        self.within_domain(index)
+            .then(|| ((self.0.checked_shr(index).unwrap_or(T::ONE)) & T::ONE) == T::ONE)
+    }
+}
+
+impl<T: FiniteBitSetTy> Default for FiniteBitSet<T> {
+    fn default() -> Self {
+        Self::new_empty()
+    }
+}