Auto merge of #53520 - nnethercote:merge-IdxSet-IdxSetBuf, r=nikomatsakis

Merge `IdxSet` and `IdxSetBuf`

Because it simplifies things.

@r? nikomatsakis

14 files changed, 120 insertions, 232 deletions

diff --git a/src/librustc/ty/query/mod.rs b/src/librustc/ty/query/mod.rs
index c1372293a1b..6f61583e49b 100644
--- a/src/librustc/ty/query/mod.rs
+++ b/src/librustc/ty/query/mod.rs
@@ -49,7 +49,7 @@ use util::nodemap::{DefIdSet, DefIdMap, ItemLocalSet};
 use util::common::{ErrorReported};
 use util::profiling::ProfileCategory::*;
 
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_target::spec::PanicStrategy;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
@@ -208,7 +208,7 @@ define_queries! { <'tcx>
         /// Maps DefId's that have an associated Mir to the result
         /// of the MIR qualify_consts pass. The actual meaning of
         /// the value isn't known except to the pass itself.
-        [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Lrc<IdxSetBuf<mir::Local>>),
+        [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Lrc<IdxSet<mir::Local>>),
 
         /// Fetch the MIR for a given def-id right after it's built - this includes
         /// unreachable code.
diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index a7672d1ffe8..f21c898a28a 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -9,38 +9,36 @@
 // except according to those terms.
 
 use array_vec::ArrayVec;
-use std::borrow::{Borrow, BorrowMut, ToOwned};
 use std::fmt;
 use std::iter;
 use std::marker::PhantomData;
 use std::mem;
-use std::ops::{Deref, DerefMut, Range};
 use std::slice;
 use bitslice::{BitSlice, Word};
 use bitslice::{bitwise, Union, Subtract, Intersect};
 use indexed_vec::Idx;
 use rustc_serialize;
 
-/// Represents a set (or packed family of sets), of some element type
-/// E, where each E is identified by some unique index type `T`.
+/// Represents a set of some element type E, where each E is identified by some
+/// unique index type `T`.
 ///
 /// In other words, `T` is the type used to index into the bitvector
 /// this type uses to represent the set of object it holds.
 ///
 /// The representation is dense, using one bit per possible element.
 #[derive(Eq, PartialEq)]
-pub struct IdxSetBuf<T: Idx> {
+pub struct IdxSet<T: Idx> {
     _pd: PhantomData<fn(&T)>,
     bits: Vec<Word>,
 }
 
-impl<T: Idx> Clone for IdxSetBuf<T> {
+impl<T: Idx> Clone for IdxSet<T> {
     fn clone(&self) -> Self {
-        IdxSetBuf { _pd: PhantomData, bits: self.bits.clone() }
+        IdxSet { _pd: PhantomData, bits: self.bits.clone() }
     }
 }
 
-impl<T: Idx> rustc_serialize::Encodable for IdxSetBuf<T> {
+impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
     fn encode<E: rustc_serialize::Encoder>(&self,
                                      encoder: &mut E)
                                      -> Result<(), E::Error> {
@@ -48,61 +46,19 @@ impl<T: Idx> rustc_serialize::Encodable for IdxSetBuf<T> {
     }
 }
 
-impl<T: Idx> rustc_serialize::Decodable for IdxSetBuf<T> {
-    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSetBuf<T>, D::Error> {
+impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
+    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
         let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
 
-        Ok(IdxSetBuf {
+        Ok(IdxSet {
             _pd: PhantomData,
             bits: words,
         })
     }
 }
 
-
-// pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass
-// around `&mut IdxSet<T>` or `&IdxSet<T>`.
-
-/// Represents a set (or packed family of sets), of some element type
-/// E, where each E is identified by some unique index type `T`.
-///
-/// In other words, `T` is the type used to index into the bitslice
-/// this type uses to represent the set of object it holds.
-#[repr(transparent)]
-pub struct IdxSet<T: Idx> {
-    _pd: PhantomData<fn(&T)>,
-    bits: [Word],
-}
-
-impl<T: Idx> Borrow<IdxSet<T>> for IdxSetBuf<T> {
-    fn borrow(&self) -> &IdxSet<T> {
-        &*self
-    }
-}
-
-impl<T: Idx> BorrowMut<IdxSet<T>> for IdxSetBuf<T> {
-    fn borrow_mut(&mut self) -> &mut IdxSet<T> {
-        &mut *self
-    }
-}
-
-impl<T: Idx> ToOwned for IdxSet<T> {
-    type Owned = IdxSetBuf<T>;
-    fn to_owned(&self) -> Self::Owned {
-        IdxSet::to_owned(self)
-    }
-}
-
 const BITS_PER_WORD: usize = mem::size_of::<Word>() * 8;
 
-impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
-        w.debug_list()
-         .entries(self.iter())
-         .finish()
-    }
-}
-
 impl<T: Idx> fmt::Debug for IdxSet<T> {
     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
         w.debug_list()
@@ -111,10 +67,10 @@ impl<T: Idx> fmt::Debug for IdxSet<T> {
     }
 }
 
-impl<T: Idx> IdxSetBuf<T> {
+impl<T: Idx> IdxSet<T> {
     fn new(init: Word, universe_size: usize) -> Self {
         let num_words = (universe_size + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
-        IdxSetBuf {
+        IdxSet {
             _pd: Default::default(),
             bits: vec![init; num_words],
         }
@@ -131,47 +87,15 @@ impl<T: Idx> IdxSetBuf<T> {
     pub fn new_empty(universe_size: usize) -> Self {
         Self::new(0, universe_size)
     }
-}
-
-impl<T: Idx> IdxSet<T> {
-    unsafe fn from_slice(s: &[Word]) -> &Self {
-        &*(s as *const [Word] as *const Self)
-    }
-
-    unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self {
-        &mut *(s as *mut [Word] as *mut Self)
-    }
-}
-
-impl<T: Idx> Deref for IdxSetBuf<T> {
-    type Target = IdxSet<T>;
-    fn deref(&self) -> &IdxSet<T> {
-        unsafe { IdxSet::from_slice(&self.bits) }
-    }
-}
-
-impl<T: Idx> DerefMut for IdxSetBuf<T> {
-    fn deref_mut(&mut self) -> &mut IdxSet<T> {
-        unsafe { IdxSet::from_slice_mut(&mut self.bits) }
-    }
-}
-
-impl<T: Idx> IdxSet<T> {
-    pub fn to_owned(&self) -> IdxSetBuf<T> {
-        IdxSetBuf {
-            _pd: Default::default(),
-            bits: self.bits.to_owned(),
-        }
-    }
 
     /// Duplicates as a hybrid set.
-    pub fn to_hybrid(&self) -> HybridIdxSetBuf<T> {
+    pub fn to_hybrid(&self) -> HybridIdxSet<T> {
         // This universe_size may be slightly larger than the one specified
         // upon creation, due to rounding up to a whole word. That's ok.
         let universe_size = self.bits.len() * BITS_PER_WORD;
 
         // Note: we currently don't bother trying to make a Sparse set.
-        HybridIdxSetBuf::Dense(self.to_owned(), universe_size)
+        HybridIdxSet::Dense(self.to_owned(), universe_size)
     }
 
     /// Removes all elements
@@ -219,16 +143,6 @@ impl<T: Idx> IdxSet<T> {
         self.bits.set_bit(elem.index())
     }
 
-    pub fn range(&self, elems: &Range<T>) -> &Self {
-        let elems = elems.start.index()..elems.end.index();
-        unsafe { Self::from_slice(&self.bits[elems]) }
-    }
-
-    pub fn range_mut(&mut self, elems: &Range<T>) -> &mut Self {
-        let elems = elems.start.index()..elems.end.index();
-        unsafe { Self::from_slice_mut(&mut self.bits[elems]) }
-    }
-
     /// Returns true iff set `self` contains `elem`.
     pub fn contains(&self, elem: &T) -> bool {
         self.bits.get_bit(elem.index())
@@ -254,8 +168,8 @@ impl<T: Idx> IdxSet<T> {
         bitwise(self.words_mut(), other.words(), &Union)
     }
 
-    /// Like `union()`, but takes a `SparseIdxSetBuf` argument.
-    fn union_sparse(&mut self, other: &SparseIdxSetBuf<T>) -> bool {
+    /// Like `union()`, but takes a `SparseIdxSet` argument.
+    fn union_sparse(&mut self, other: &SparseIdxSet<T>) -> bool {
         let mut changed = false;
         for elem in other.iter() {
             changed |= self.add(&elem);
@@ -263,11 +177,11 @@ impl<T: Idx> IdxSet<T> {
         changed
     }
 
-    /// Like `union()`, but takes a `HybridIdxSetBuf` argument.
-    pub fn union_hybrid(&mut self, other: &HybridIdxSetBuf<T>) -> bool {
+    /// Like `union()`, but takes a `HybridIdxSet` argument.
+    pub fn union_hybrid(&mut self, other: &HybridIdxSet<T>) -> bool {
         match other {
-            HybridIdxSetBuf::Sparse(sparse, _) => self.union_sparse(sparse),
-            HybridIdxSetBuf::Dense(dense, _) => self.union(dense),
+            HybridIdxSet::Sparse(sparse, _) => self.union_sparse(sparse),
+            HybridIdxSet::Dense(dense, _) => self.union(dense),
         }
     }
 
@@ -277,8 +191,8 @@ impl<T: Idx> IdxSet<T> {
         bitwise(self.words_mut(), other.words(), &Subtract)
     }
 
-    /// Like `subtract()`, but takes a `SparseIdxSetBuf` argument.
-    fn subtract_sparse(&mut self, other: &SparseIdxSetBuf<T>) -> bool {
+    /// Like `subtract()`, but takes a `SparseIdxSet` argument.
+    fn subtract_sparse(&mut self, other: &SparseIdxSet<T>) -> bool {
         let mut changed = false;
         for elem in other.iter() {
             changed |= self.remove(&elem);
@@ -286,11 +200,11 @@ impl<T: Idx> IdxSet<T> {
         changed
     }
 
-    /// Like `subtract()`, but takes a `HybridIdxSetBuf` argument.
-    pub fn subtract_hybrid(&mut self, other: &HybridIdxSetBuf<T>) -> bool {
+    /// Like `subtract()`, but takes a `HybridIdxSet` argument.
+    pub fn subtract_hybrid(&mut self, other: &HybridIdxSet<T>) -> bool {
         match other {
-            HybridIdxSetBuf::Sparse(sparse, _) => self.subtract_sparse(sparse),
-            HybridIdxSetBuf::Dense(dense, _) => self.subtract(dense),
+            HybridIdxSet::Sparse(sparse, _) => self.subtract_sparse(sparse),
+            HybridIdxSet::Dense(dense, _) => self.subtract(dense),
         }
     }
 
@@ -338,15 +252,15 @@ impl<'a, T: Idx> Iterator for Iter<'a, T> {
 const SPARSE_MAX: usize = 8;
 
 /// A sparse index set with a maximum of SPARSE_MAX elements. Used by
-/// HybridIdxSetBuf; do not use directly.
+/// HybridIdxSet; do not use directly.
 ///
 /// The elements are stored as an unsorted vector with no duplicates.
 #[derive(Clone, Debug)]
-pub struct SparseIdxSetBuf<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
+pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
 
-impl<T: Idx> SparseIdxSetBuf<T> {
+impl<T: Idx> SparseIdxSet<T> {
     fn new() -> Self {
-        SparseIdxSetBuf(ArrayVec::new())
+        SparseIdxSet(ArrayVec::new())
     }
 
     fn len(&self) -> usize {
@@ -379,8 +293,8 @@ impl<T: Idx> SparseIdxSetBuf<T> {
         }
     }
 
-    fn to_dense(&self, universe_size: usize) -> IdxSetBuf<T> {
-        let mut dense = IdxSetBuf::new_empty(universe_size);
+    fn to_dense(&self, universe_size: usize) -> IdxSet<T> {
+        let mut dense = IdxSet::new_empty(universe_size);
         for elem in self.0.iter() {
             dense.add(elem);
         }
@@ -406,72 +320,72 @@ impl<'a, T: Idx> Iterator for SparseIter<'a, T> {
     }
 }
 
-/// Like IdxSetBuf, but with a hybrid representation: sparse when there are few
+/// Like IdxSet, but with a hybrid representation: sparse when there are few
 /// elements in the set, but dense when there are many. It's especially
 /// efficient for sets that typically have a small number of elements, but a
 /// large `universe_size`, and are cleared frequently.
 #[derive(Clone, Debug)]
-pub enum HybridIdxSetBuf<T: Idx> {
-    Sparse(SparseIdxSetBuf<T>, usize),
-    Dense(IdxSetBuf<T>, usize),
+pub enum HybridIdxSet<T: Idx> {
+    Sparse(SparseIdxSet<T>, usize),
+    Dense(IdxSet<T>, usize),
 }
 
-impl<T: Idx> HybridIdxSetBuf<T> {
+impl<T: Idx> HybridIdxSet<T> {
     pub fn new_empty(universe_size: usize) -> Self {
-        HybridIdxSetBuf::Sparse(SparseIdxSetBuf::new(), universe_size)
+        HybridIdxSet::Sparse(SparseIdxSet::new(), universe_size)
     }
 
     fn universe_size(&mut self) -> usize {
         match *self {
-            HybridIdxSetBuf::Sparse(_, size) => size,
-            HybridIdxSetBuf::Dense(_, size) => size,
+            HybridIdxSet::Sparse(_, size) => size,
+            HybridIdxSet::Dense(_, size) => size,
         }
     }
 
     pub fn clear(&mut self) {
         let universe_size = self.universe_size();
-        *self = HybridIdxSetBuf::new_empty(universe_size);
+        *self = HybridIdxSet::new_empty(universe_size);
     }
 
     /// Returns true iff set `self` contains `elem`.
     pub fn contains(&self, elem: &T) -> bool {
         match self {
-            HybridIdxSetBuf::Sparse(sparse, _) => sparse.contains(elem),
-            HybridIdxSetBuf::Dense(dense, _) => dense.contains(elem),
+            HybridIdxSet::Sparse(sparse, _) => sparse.contains(elem),
+            HybridIdxSet::Dense(dense, _) => dense.contains(elem),
         }
     }
 
     /// Adds `elem` to the set `self`.
     pub fn add(&mut self, elem: &T) -> bool {
         match self {
-            HybridIdxSetBuf::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
+            HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
                 // The set is sparse and has space for `elem`.
                 sparse.add(elem)
             }
-            HybridIdxSetBuf::Sparse(sparse, _) if sparse.contains(elem) => {
+            HybridIdxSet::Sparse(sparse, _) if sparse.contains(elem) => {
                 // The set is sparse and does not have space for `elem`, but
                 // that doesn't matter because `elem` is already present.
                 false
             }
-            HybridIdxSetBuf::Sparse(_, _) => {
+            HybridIdxSet::Sparse(_, _) => {
                 // The set is sparse and full. Convert to a dense set.
                 //
                 // FIXME: This code is awful, but I can't work out how else to
                 //        appease the borrow checker.
-                let dummy = HybridIdxSetBuf::Sparse(SparseIdxSetBuf::new(), 0);
+                let dummy = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
                 match mem::replace(self, dummy) {
-                    HybridIdxSetBuf::Sparse(sparse, universe_size) => {
+                    HybridIdxSet::Sparse(sparse, universe_size) => {
                         let mut dense = sparse.to_dense(universe_size);
                         let changed = dense.add(elem);
                         assert!(changed);
-                        mem::replace(self, HybridIdxSetBuf::Dense(dense, universe_size));
+                        mem::replace(self, HybridIdxSet::Dense(dense, universe_size));
                         changed
                     }
                     _ => panic!("impossible"),
                 }
             }
 
-            HybridIdxSetBuf::Dense(dense, _) => dense.add(elem),
+            HybridIdxSet::Dense(dense, _) => dense.add(elem),
         }
     }
 
@@ -479,24 +393,24 @@ impl<T: Idx> HybridIdxSetBuf<T> {
     pub fn remove(&mut self, elem: &T) -> bool {
         // Note: we currently don't bother going from Dense back to Sparse.
         match self {
-            HybridIdxSetBuf::Sparse(sparse, _) => sparse.remove(elem),
-            HybridIdxSetBuf::Dense(dense, _) => dense.remove(elem),
+            HybridIdxSet::Sparse(sparse, _) => sparse.remove(elem),
+            HybridIdxSet::Dense(dense, _) => dense.remove(elem),
         }
     }
 
     /// Converts to a dense set, consuming itself in the process.
-    pub fn to_dense(self) -> IdxSetBuf<T> {
+    pub fn to_dense(self) -> IdxSet<T> {
         match self {
-            HybridIdxSetBuf::Sparse(sparse, universe_size) => sparse.to_dense(universe_size),
-            HybridIdxSetBuf::Dense(dense, _) => dense,
+            HybridIdxSet::Sparse(sparse, universe_size) => sparse.to_dense(universe_size),
+            HybridIdxSet::Dense(dense, _) => dense,
         }
     }
 
     /// Iteration order is unspecified.
     pub fn iter(&self) -> HybridIter<T> {
         match self {
-            HybridIdxSetBuf::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
-            HybridIdxSetBuf::Dense(dense, _) => HybridIter::Dense(dense.iter()),
+            HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
+            HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
         }
     }
 }
@@ -522,7 +436,7 @@ fn test_trim_to() {
     use std::cmp;
 
     for i in 0..256 {
-        let mut idx_buf: IdxSetBuf<usize> = IdxSetBuf::new_filled(128);
+        let mut idx_buf: IdxSet<usize> = IdxSet::new_filled(128);
         idx_buf.trim_to(i);
 
         let elems: Vec<usize> = idx_buf.iter().collect();
@@ -535,7 +449,7 @@ fn test_trim_to() {
 fn test_set_up_to() {
     for i in 0..128 {
         for mut idx_buf in
-            vec![IdxSetBuf::new_empty(128), IdxSetBuf::new_filled(128)]
+            vec![IdxSet::new_empty(128), IdxSet::new_filled(128)]
             .into_iter()
         {
             idx_buf.set_up_to(i);
@@ -550,7 +464,7 @@ fn test_set_up_to() {
 #[test]
 fn test_new_filled() {
     for i in 0..128 {
-        let idx_buf = IdxSetBuf::new_filled(i);
+        let idx_buf = IdxSet::new_filled(i);
         let elems: Vec<usize> = idx_buf.iter().collect();
         let expected: Vec<usize> = (0..i).collect();
         assert_eq!(elems, expected);
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 9f1c7dac119..1024e69cc2b 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -432,7 +432,7 @@ impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<
 }
 
 
-impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::indexed_set::IdxSetBuf<I>
+impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::indexed_set::IdxSet<I>
 {
     fn hash_stable<W: StableHasherResult>(&self,
                                           ctx: &mut CTX,
diff --git a/src/librustc_data_structures/work_queue.rs b/src/librustc_data_structures/work_queue.rs
index b8e8b249bb5..0c8ec753a18 100644
--- a/src/librustc_data_structures/work_queue.rs
+++ b/src/librustc_data_structures/work_queue.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use indexed_set::IdxSetBuf;
+use indexed_set::IdxSet;
 use indexed_vec::Idx;
 use std::collections::VecDeque;
 
@@ -20,7 +20,7 @@ use std::collections::VecDeque;
 /// and also use a bit set to track occupancy.
 pub struct WorkQueue<T: Idx> {
     deque: VecDeque<T>,
-    set: IdxSetBuf<T>,
+    set: IdxSet<T>,
 }
 
 impl<T: Idx> WorkQueue<T> {
@@ -29,7 +29,7 @@ impl<T: Idx> WorkQueue<T> {
     pub fn with_all(len: usize) -> Self {
         WorkQueue {
             deque: (0..len).map(T::new).collect(),
-            set: IdxSetBuf::new_filled(len),
+            set: IdxSet::new_filled(len),
         }
     }
 
@@ -38,7 +38,7 @@ impl<T: Idx> WorkQueue<T> {
     pub fn with_none(len: usize) -> Self {
         WorkQueue {
             deque: VecDeque::with_capacity(len),
-            set: IdxSetBuf::new_empty(len),
+            set: IdxSet::new_empty(len),
         }
     }
 
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 083f9565666..5aa05270a2a 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -42,7 +42,7 @@ use syntax::edition::Edition;
 use syntax::parse::source_file_to_stream;
 use syntax::symbol::Symbol;
 use syntax_pos::{Span, NO_EXPANSION, FileName};
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc::hir;
 
 macro_rules! provide {
@@ -141,7 +141,7 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         mir
     }
     mir_const_qualif => {
-        (cdata.mir_const_qualif(def_id.index), Lrc::new(IdxSetBuf::new_empty(0)))
+        (cdata.mir_const_qualif(def_id.index), Lrc::new(IdxSet::new_empty(0)))
     }
     fn_sig => { cdata.fn_sig(def_id.index, tcx) }
     inherent_impls => { Lrc::new(cdata.get_inherent_implementations_for_type(def_id.index)) }
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index b6f7347dd57..f96f6127349 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -27,7 +27,7 @@ use rustc::ty::{self, ParamEnv, TyCtxt, Ty};
 use rustc_errors::{Applicability, Diagnostic, DiagnosticBuilder, Level};
 use rustc_data_structures::graph::dominators::Dominators;
 use rustc_data_structures::fx::FxHashSet;
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::small_vec::SmallVec;
 
@@ -166,7 +166,7 @@ fn do_mir_borrowck<'a, 'gcx, 'tcx>(
         _ => Some(tcx.hir.body_owned_by(id)),
     };
 
-    let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
+    let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len());
     let mut flow_inits = FlowAtLocation::new(do_dataflow(
         tcx,
         mir,
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
index ebcc044093a..ff68b5987e8 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -27,7 +27,7 @@ use rustc::mir::{
 use rustc::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable};
 use rustc::util::common;
 use rustc_data_structures::graph::scc::Sccs;
-use rustc_data_structures::indexed_set::{IdxSet, IdxSetBuf};
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_errors::Diagnostic;
 
@@ -468,7 +468,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         // SCC. For each SCC, we visit its successors and compute
         // their values, then we union all those values to get our
         // own.
-        let visited = &mut IdxSetBuf::new_empty(self.constraint_sccs.num_sccs());
+        let visited = &mut IdxSet::new_empty(self.constraint_sccs.num_sccs());
         for scc_index in self.constraint_sccs.all_sccs() {
             self.propagate_constraint_sccs_if_new(scc_index, visited);
         }
diff --git a/src/librustc_mir/dataflow/at_location.rs b/src/librustc_mir/dataflow/at_location.rs
index d2a8a9dcf4b..0dfc5b5b4b7 100644
--- a/src/librustc_mir/dataflow/at_location.rs
+++ b/src/librustc_mir/dataflow/at_location.rs
@@ -12,7 +12,7 @@
 //! locations.
 
 use rustc::mir::{BasicBlock, Location};
-use rustc_data_structures::indexed_set::{HybridIdxSetBuf, IdxSetBuf, Iter};
+use rustc_data_structures::indexed_set::{HybridIdxSet, IdxSet, Iter};
 use rustc_data_structures::indexed_vec::Idx;
 
 use dataflow::{BitDenotation, BlockSets, DataflowResults};
@@ -67,9 +67,9 @@ where
     BD: BitDenotation,
 {
     base_results: DataflowResults<BD>,
-    curr_state: IdxSetBuf<BD::Idx>,
-    stmt_gen: HybridIdxSetBuf<BD::Idx>,
-    stmt_kill: HybridIdxSetBuf<BD::Idx>,
+    curr_state: IdxSet<BD::Idx>,
+    stmt_gen: HybridIdxSet<BD::Idx>,
+    stmt_kill: HybridIdxSet<BD::Idx>,
 }
 
 impl<BD> FlowAtLocation<BD>
@@ -96,9 +96,9 @@ where
 
     pub fn new(results: DataflowResults<BD>) -> Self {
         let bits_per_block = results.sets().bits_per_block();
-        let curr_state = IdxSetBuf::new_empty(bits_per_block);
-        let stmt_gen = HybridIdxSetBuf::new_empty(bits_per_block);
-        let stmt_kill = HybridIdxSetBuf::new_empty(bits_per_block);
+        let curr_state = IdxSet::new_empty(bits_per_block);
+        let stmt_gen = HybridIdxSet::new_empty(bits_per_block);
+        let stmt_kill = HybridIdxSet::new_empty(bits_per_block);
         FlowAtLocation {
             base_results: results,
             curr_state: curr_state,
diff --git a/src/librustc_mir/dataflow/mod.rs b/src/librustc_mir/dataflow/mod.rs
index 116cefea175..598e827b256 100644
--- a/src/librustc_mir/dataflow/mod.rs
+++ b/src/librustc_mir/dataflow/mod.rs
@@ -10,8 +10,8 @@
 
 use syntax::ast::{self, MetaItem};
 
-use rustc_data_structures::bitslice::{bitwise, BitwiseOperator, Word};
-use rustc_data_structures::indexed_set::{HybridIdxSetBuf, IdxSet, IdxSetBuf};
+use rustc_data_structures::bitslice::{bitwise, BitwiseOperator};
+use rustc_data_structures::indexed_set::{HybridIdxSet, IdxSet};
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::work_queue::WorkQueue;
 
@@ -23,7 +23,6 @@ use rustc::session::Session;
 use std::borrow::Borrow;
 use std::fmt;
 use std::io;
-use std::mem;
 use std::path::PathBuf;
 use std::usize;
 
@@ -183,7 +182,7 @@ struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation
 impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
 {
     fn propagate(&mut self) {
-        let mut temp = IdxSetBuf::new_empty(self.flow_state.sets.bits_per_block);
+        let mut temp = IdxSet::new_empty(self.flow_state.sets.bits_per_block);
         let mut propcx = PropagationContext {
             builder: self,
         };
@@ -287,18 +286,6 @@ impl<'a, 'tcx: 'a, BD> DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
     }
 }
 
-/// Maps each block to a set of bits
-#[derive(Clone, Debug)]
-pub(crate) struct Bits<E:Idx> {
-    bits: IdxSetBuf<E>,
-}
-
-impl<E:Idx> Bits<E> {
-    fn new(bits: IdxSetBuf<E>) -> Self {
-        Bits { bits: bits }
-    }
-}
-
 /// DataflowResultsConsumer abstracts over walking the MIR with some
 /// already constructed dataflow results.
 ///
@@ -366,7 +353,7 @@ pub fn state_for_location<'tcx, T: BitDenotation>(loc: Location,
                                                   analysis: &T,
                                                   result: &DataflowResults<T>,
                                                   mir: &Mir<'tcx>)
-    -> IdxSetBuf<T::Idx> {
+    -> IdxSet<T::Idx> {
     let mut on_entry = result.sets().on_entry_set_for(loc.block.index()).to_owned();
     let mut kill_set = on_entry.to_hybrid();
     let mut gen_set = kill_set.clone();
@@ -450,7 +437,7 @@ impl<O: BitDenotation> DataflowState<O> {
 
     pub(crate) fn interpret_hybrid_set<'c, P>(&self,
                                               o: &'c O,
-                                              set: &HybridIdxSetBuf<O::Idx>,
+                                              set: &HybridIdxSet<O::Idx>,
                                               render_idx: &P)
                                               -> Vec<DebugFormatted>
         where P: Fn(&O, O::Idx) -> DebugFormatted
@@ -464,22 +451,18 @@ pub struct AllSets<E: Idx> {
     /// Analysis bitwidth for each block.
     bits_per_block: usize,
 
-    /// Number of words associated with each block entry
-    /// equal to bits_per_block / (mem::size_of::<Word> * 8), rounded up.
-    words_per_block: usize,
-
     /// For each block, bits valid on entry to the block.
-    on_entry_sets: Bits<E>,
+    on_entry_sets: Vec<IdxSet<E>>,
 
     /// For each block, bits generated by executing the statements in
     /// the block. (For comparison, the Terminator for each block is
     /// handled in a flow-specific manner during propagation.)
-    gen_sets: Vec<HybridIdxSetBuf<E>>,
+    gen_sets: Vec<HybridIdxSet<E>>,
 
     /// For each block, bits killed by executing the statements in the
     /// block. (For comparison, the Terminator for each block is
     /// handled in a flow-specific manner during propagation.)
-    kill_sets: Vec<HybridIdxSetBuf<E>>,
+    kill_sets: Vec<HybridIdxSet<E>>,
 }
 
 /// Triple of sets associated with a given block.
@@ -503,11 +486,11 @@ pub struct BlockSets<'a, E: Idx> {
 
     /// Bits that are set to 1 by the time we exit the given block. Hybrid
     /// because it usually contains only 0 or 1 elements.
-    pub(crate) gen_set: &'a mut HybridIdxSetBuf<E>,
+    pub(crate) gen_set: &'a mut HybridIdxSet<E>,
 
     /// Bits that are set to 0 by the time we exit the given block. Hybrid
     /// because it usually contains only 0 or 1 elements.
-    pub(crate) kill_set: &'a mut HybridIdxSetBuf<E>,
+    pub(crate) kill_set: &'a mut HybridIdxSet<E>,
 }
 
 impl<'a, E:Idx> BlockSets<'a, E> {
@@ -559,24 +542,20 @@ impl<'a, E:Idx> BlockSets<'a, E> {
 impl<E:Idx> AllSets<E> {
     pub fn bits_per_block(&self) -> usize { self.bits_per_block }
     pub fn for_block(&mut self, block_idx: usize) -> BlockSets<E> {
-        let offset = self.words_per_block * block_idx;
-        let range = E::new(offset)..E::new(offset + self.words_per_block);
         BlockSets {
-            on_entry: self.on_entry_sets.bits.range_mut(&range),
+            on_entry: &mut self.on_entry_sets[block_idx],
             gen_set: &mut self.gen_sets[block_idx],
             kill_set: &mut self.kill_sets[block_idx],
         }
     }
 
     pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> {
-        let offset = self.words_per_block * block_idx;
-        let range = E::new(offset)..E::new(offset + self.words_per_block);
-        self.on_entry_sets.bits.range(&range)
+        &self.on_entry_sets[block_idx]
     }
-    pub fn gen_set_for(&self, block_idx: usize) -> &HybridIdxSetBuf<E> {
+    pub fn gen_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> {
         &self.gen_sets[block_idx]
     }
-    pub fn kill_set_for(&self, block_idx: usize) -> &HybridIdxSetBuf<E> {
+    pub fn kill_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> {
         &self.kill_sets[block_idx]
     }
 }
@@ -731,18 +710,15 @@ impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
                dead_unwinds: &'a IdxSet<mir::BasicBlock>,
                denotation: D) -> Self where D: InitialFlow {
         let bits_per_block = denotation.bits_per_block();
-        let bits_per_word = mem::size_of::<Word>() * 8;
-        let words_per_block = (bits_per_block + bits_per_word - 1) / bits_per_word;
-        let bits_per_block_rounded_up = words_per_block * bits_per_word; // a multiple of word size
         let num_blocks = mir.basic_blocks().len();
-        let num_overall = num_blocks * bits_per_block_rounded_up;
 
-        let on_entry = Bits::new(if D::bottom_value() {
-            IdxSetBuf::new_filled(num_overall)
+        let on_entry_sets = if D::bottom_value() {
+            vec![IdxSet::new_filled(bits_per_block); num_blocks]
         } else {
-            IdxSetBuf::new_empty(num_overall)
-        });
-        let empties = vec![HybridIdxSetBuf::new_empty(bits_per_block); num_blocks];
+            vec![IdxSet::new_empty(bits_per_block); num_blocks]
+        };
+        let gen_sets = vec![HybridIdxSet::new_empty(bits_per_block); num_blocks];
+        let kill_sets = gen_sets.clone();
 
         DataflowAnalysis {
             mir,
@@ -750,10 +726,9 @@ impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
             flow_state: DataflowState {
                 sets: AllSets {
                     bits_per_block,
-                    words_per_block,
-                    on_entry_sets: on_entry,
-                    gen_sets: empties.clone(),
-                    kill_sets: empties,
+                    on_entry_sets,
+                    gen_sets,
+                    kill_sets,
                 },
                 operator: denotation,
             }
@@ -873,5 +848,4 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
             dirty_queue.insert(bb);
         }
     }
-
 }
diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs
index 937d01a0c5e..bbf896e624f 100644
--- a/src/librustc_mir/transform/elaborate_drops.rs
+++ b/src/librustc_mir/transform/elaborate_drops.rs
@@ -18,7 +18,7 @@ use dataflow::{self, do_dataflow, DebugFormatted};
 use rustc::ty::{self, TyCtxt};
 use rustc::mir::*;
 use rustc::util::nodemap::FxHashMap;
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::Idx;
 use transform::{MirPass, MirSource};
 use util::patch::MirPatch;
@@ -93,12 +93,12 @@ fn find_dead_unwinds<'a, 'tcx>(
     mir: &Mir<'tcx>,
     id: ast::NodeId,
     env: &MoveDataParamEnv<'tcx, 'tcx>)
-    -> IdxSetBuf<BasicBlock>
+    -> IdxSet<BasicBlock>
 {
     debug!("find_dead_unwinds({:?})", mir.span);
     // We only need to do this pass once, because unwind edges can only
     // reach cleanup blocks, which can't have unwind edges themselves.
-    let mut dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
+    let mut dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len());
     let flow_inits =
         do_dataflow(tcx, mir, id, &[], &dead_unwinds,
                     MaybeInitializedPlaces::new(tcx, mir, &env),
@@ -112,7 +112,7 @@ fn find_dead_unwinds<'a, 'tcx>(
 
         let mut init_data = InitializationData {
             live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(),
-            dead: IdxSetBuf::new_empty(env.move_data.move_paths.len()),
+            dead: IdxSet::new_empty(env.move_data.move_paths.len()),
         };
         debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}",
                bb, bb_data, init_data.live);
@@ -147,8 +147,8 @@ fn find_dead_unwinds<'a, 'tcx>(
 }
 
 struct InitializationData {
-    live: IdxSetBuf<MovePathIndex>,
-    dead: IdxSetBuf<MovePathIndex>
+    live: IdxSet<MovePathIndex>,
+    dead: IdxSet<MovePathIndex>
 }
 
 impl InitializationData {
diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs
index 4a9b6b7f6e8..dc657f228c9 100644
--- a/src/librustc_mir/transform/generator.rs
+++ b/src/librustc_mir/transform/generator.rs
@@ -68,7 +68,7 @@ use rustc::ty::subst::Substs;
 use util::dump_mir;
 use util::liveness::{self, IdentityMap, LivenessMode};
 use rustc_data_structures::indexed_vec::Idx;
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use std::collections::HashMap;
 use std::borrow::Cow;
 use std::iter::once;
@@ -369,7 +369,7 @@ fn locals_live_across_suspend_points<'a, 'tcx,>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                movable: bool) ->
                                                (liveness::LiveVarSet<Local>,
                                                 HashMap<BasicBlock, liveness::LiveVarSet<Local>>) {
-    let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
+    let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len());
     let node_id = tcx.hir.as_local_node_id(source.def_id).unwrap();
 
     // Calculate when MIR locals have live storage. This gives us an upper bound of their
@@ -381,7 +381,7 @@ fn locals_live_across_suspend_points<'a, 'tcx,>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     // Find the MIR locals which do not use StorageLive/StorageDead statements.
     // The storage of these locals are always live.
-    let mut ignored = StorageIgnored(IdxSetBuf::new_filled(mir.local_decls.len()));
+    let mut ignored = StorageIgnored(IdxSet::new_filled(mir.local_decls.len()));
     ignored.visit_mir(mir);
 
     // Calculate the MIR locals which have been previously
diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index 740581b8299..7582792b10d 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -15,7 +15,7 @@
 //! diagnostics as to why a constant rvalue wasn't promoted.
 
 use rustc_data_structures::bitvec::BitArray;
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 use rustc_data_structures::fx::FxHashSet;
 use rustc::hir;
@@ -279,7 +279,7 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> {
     }
 
     /// Qualify a whole const, static initializer or const fn.
-    fn qualify_const(&mut self) -> (Qualif, Lrc<IdxSetBuf<Local>>) {
+    fn qualify_const(&mut self) -> (Qualif, Lrc<IdxSet<Local>>) {
         debug!("qualifying {} {:?}", self.mode, self.def_id);
 
         let mir = self.mir;
@@ -382,7 +382,7 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> {
 
 
         // Collect all the temps we need to promote.
-        let mut promoted_temps = IdxSetBuf::new_empty(self.temp_promotion_state.len());
+        let mut promoted_temps = IdxSet::new_empty(self.temp_promotion_state.len());
 
         for candidate in &self.promotion_candidates {
             match *candidate {
@@ -1104,7 +1104,7 @@ pub fn provide(providers: &mut Providers) {
 
 fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                               def_id: DefId)
-                              -> (u8, Lrc<IdxSetBuf<Local>>) {
+                              -> (u8, Lrc<IdxSet<Local>>) {
     // NB: This `borrow()` is guaranteed to be valid (i.e., the value
     // cannot yet be stolen), because `mir_validated()`, which steals
     // from `mir_const(), forces this query to execute before
@@ -1113,7 +1113,7 @@ fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     if mir.return_ty().references_error() {
         tcx.sess.delay_span_bug(mir.span, "mir_const_qualif: Mir had errors");
-        return (Qualif::NOT_CONST.bits(), Lrc::new(IdxSetBuf::new_empty(0)));
+        return (Qualif::NOT_CONST.bits(), Lrc::new(IdxSet::new_empty(0)));
     }
 
     let mut qualifier = Qualifier::new(tcx, def_id, mir, Mode::Const);
diff --git a/src/librustc_mir/transform/rustc_peek.rs b/src/librustc_mir/transform/rustc_peek.rs
index 2147cc2a41a..63675f056ab 100644
--- a/src/librustc_mir/transform/rustc_peek.rs
+++ b/src/librustc_mir/transform/rustc_peek.rs
@@ -14,7 +14,7 @@ use syntax_pos::Span;
 
 use rustc::ty::{self, TyCtxt};
 use rustc::mir::{self, Mir, Location};
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::Idx;
 use transform::{MirPass, MirSource};
 
@@ -47,7 +47,7 @@ impl MirPass for SanityCheck {
         let param_env = tcx.param_env(def_id);
         let move_data = MoveData::gather_moves(mir, tcx).unwrap();
         let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env };
-        let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
+        let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len());
         let flow_inits =
             do_dataflow(tcx, mir, id, &attributes, &dead_unwinds,
                         MaybeInitializedPlaces::new(tcx, mir, &mdpe),
diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs
index 6c5b38a806e..04fa516a655 100644
--- a/src/librustc_mir/util/liveness.rs
+++ b/src/librustc_mir/util/liveness.rs
@@ -38,7 +38,7 @@ use rustc::mir::visit::{PlaceContext, Visitor};
 use rustc::mir::Local;
 use rustc::mir::*;
 use rustc::ty::{item_path, TyCtxt};
-use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
 use rustc_data_structures::work_queue::WorkQueue;
 use std::fs;
@@ -47,7 +47,7 @@ use std::path::{Path, PathBuf};
 use transform::MirSource;
 use util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
 
-pub type LiveVarSet<V> = IdxSetBuf<V>;
+pub type LiveVarSet<V> = IdxSet<V>;
 
 /// This gives the result of the liveness analysis at the boundary of
 /// basic blocks. You can use `simulate_block` to obtain the