Merge indexed_set.rs into bitvec.rs, and rename it bit_set.rs.

Currently we have two files implementing bitsets (and 2D bit matrices).
This commit combines them into one, taking the best features from each.

This involves renaming a lot of things. The high level changes are as
follows.
- bitvec.rs              --> bit_set.rs
- indexed_set.rs         --> (removed)
- BitArray + IdxSet      --> BitSet (merged, see below)
- BitVector              --> GrowableBitSet
- {,Sparse,Hybrid}IdxSet --> {,Sparse,Hybrid}BitSet
- BitMatrix              --> BitMatrix
- SparseBitMatrix        --> SparseBitMatrix

The changes within the bitset types themselves are as follows.

```
OLD             OLD             NEW
BitArray<C>     IdxSet<T>       BitSet<T>
--------        ------          ------
grow            -               grow
new             -               (remove)
new_empty       new_empty       new_empty
new_filled      new_filled      new_filled
-               to_hybrid       to_hybrid
clear           clear           clear
set_up_to       set_up_to       set_up_to
clear_above     -               clear_above
count           -               count
contains(T)     contains(&T)    contains(T)
contains_all    -               superset
is_empty        -               is_empty
insert(T)       add(&T)         insert(T)
insert_all      -               insert_all()
remove(T)       remove(&T)      remove(T)
words           words           words
words_mut       words_mut       words_mut
-               overwrite       overwrite
merge           union           union
-               subtract        subtract
-               intersect       intersect
iter            iter            iter
```

In general, when choosing names I went with:
- names that are more obvious (e.g. `BitSet` over `IdxSet`).
- names that are more like the Rust libraries (e.g. `T` over `C`,
  `insert` over `add`);
- names that are more set-like (e.g. `union` over `merge`, `superset`
  over `contains_all`, `domain_size` over `num_bits`).

Also, using `T` for index arguments seems more sensible than `&T` --
even though the latter is standard in Rust collection types -- because
indices are always copyable. It also results in fewer `&` and `*`
sigils in practice.

8 files changed, 1063 insertions, 1157 deletions

diff --git a/src/librustc_data_structures/bit_set.rs b/src/librustc_data_structures/bit_set.rs
new file mode 100644
index 00000000000..71cd4ba37ab
--- /dev/null
+++ b/src/librustc_data_structures/bit_set.rs
@@ -0,0 +1,1046 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use array_vec::ArrayVec;
+use indexed_vec::{Idx, IndexVec};
+use rustc_serialize;
+use std::fmt;
+use std::iter;
+use std::marker::PhantomData;
+use std::mem;
+use std::slice;
+
+pub type Word = u64;
+pub const WORD_BYTES: usize = mem::size_of::<Word>();
+pub const WORD_BITS: usize = WORD_BYTES * 8;
+
+/// A fixed-size bitset type with a dense representation. It does not support
+/// resizing after creation; use `GrowableBitSet` for that.
+///
+/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
+/// just be `usize`.
+#[derive(Clone, Eq, PartialEq)]
+pub struct BitSet<T: Idx> {
+    data: Vec<Word>,
+    marker: PhantomData<T>,
+}
+
+impl<T: Idx> BitSet<T> {
+    #[inline]
+    pub fn new_empty(domain_size: usize) -> BitSet<T> {
+        let num_words = num_words(domain_size);
+        BitSet {
+            data: vec![0; num_words],
+            marker: PhantomData,
+        }
+    }
+
+    #[inline]
+    pub fn new_filled(domain_size: usize) -> BitSet<T> {
+        let num_words = num_words(domain_size);
+        let mut result = BitSet {
+            data: vec![!0; num_words],
+            marker: PhantomData,
+        };
+        result.clear_above(domain_size);
+        result
+    }
+
+    #[inline]
+    pub fn clear(&mut self) {
+        for word in &mut self.data {
+            *word = 0;
+        }
+    }
+
+    /// Sets all elements up to and including `size`.
+    pub fn set_up_to(&mut self, bit: usize) {
+        for word in &mut self.data {
+            *word = !0;
+        }
+        self.clear_above(bit);
+    }
+
+    /// Clear all elements above `bit`.
+    fn clear_above(&mut self, bit: usize) {
+        let first_clear_block = bit / WORD_BITS;
+
+        if first_clear_block < self.data.len() {
+            // Within `first_clear_block`, the `bit % WORD_BITS` LSBs should
+            // remain.
+            let mask = (1 << (bit % WORD_BITS)) - 1;
+            self.data[first_clear_block] &= mask;
+
+            // All the blocks above `first_clear_block` are fully cleared.
+            for word in &mut self.data[first_clear_block + 1..] {
+                *word = 0;
+            }
+        }
+    }
+
+    /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
+    /// don't have the same length.
+    pub fn overwrite(&mut self, other: &BitSet<T>) {
+        self.words_mut().clone_from_slice(other.words());
+    }
+
+    /// Count the number of set bits in the set.
+    pub fn count(&self) -> usize {
+        self.data.iter().map(|e| e.count_ones() as usize).sum()
+    }
+
+    /// True if `self` contains the bit `bit`.
+    #[inline]
+    pub fn contains(&self, bit: T) -> bool {
+        let (word, mask) = word_mask(bit);
+        (self.data[word] & mask) != 0
+    }
+
+    /// True if `self` is a (non-strict) superset of `other`.
+    ///
+    /// The two vectors must have the same length.
+    #[inline]
+    pub fn superset(&self, other: &BitSet<T>) -> bool {
+        assert_eq!(self.data.len(), other.data.len());
+        self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
+    }
+
+    /// Is the set empty?
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.data.iter().all(|a| *a == 0)
+    }
+
+    /// Insert a bit. Returns true if the bit has changed.
+    #[inline]
+    pub fn insert(&mut self, bit: T) -> bool {
+        let (word, mask) = word_mask(bit);
+        let data = &mut self.data[word];
+        let value = *data;
+        let new_value = value | mask;
+        *data = new_value;
+        new_value != value
+    }
+
+    /// Sets all bits to true.
+    pub fn insert_all(&mut self) {
+        for word in &mut self.data {
+            *word = !0;
+        }
+    }
+
+    /// Returns true if the bit has changed.
+    #[inline]
+    pub fn remove(&mut self, bit: T) -> bool {
+        let (word, mask) = word_mask(bit);
+        let data = &mut self.data[word];
+        let value = *data;
+        let new_value = value & !mask;
+        *data = new_value;
+        new_value != value
+    }
+
+    /// Set `self = self | other` and return true if `self` changed
+    /// (i.e., if new bits were added).
+    pub fn union(&mut self, other: &impl UnionIntoBitSet<T>) -> bool {
+        other.union_into(self)
+    }
+
+    /// Set `self = self - other` and return true if `self` changed.
+    /// (i.e., if any bits were removed).
+    pub fn subtract(&mut self, other: &impl SubtractFromBitSet<T>) -> bool {
+        other.subtract_from(self)
+    }
+
+    /// Set `self = self & other` and return true if `self` changed.
+    /// (i.e., if any bits were removed).
+    pub fn intersect(&mut self, other: &BitSet<T>) -> bool {
+        bitwise(self.words_mut(), other.words(), &Intersect)
+    }
+
+    /// Get a slice of the underlying words.
+    pub fn words(&self) -> &[Word] {
+        &self.data
+    }
+
+    /// Get a mutable slice of the underlying words.
+    pub fn words_mut(&mut self) -> &mut [Word] {
+        &mut self.data
+    }
+
+    /// Iterates over the indices of set bits in a sorted order.
+    #[inline]
+    pub fn iter<'a>(&'a self) -> BitIter<'a, T> {
+        BitIter {
+            cur: None,
+            iter: self.data.iter().enumerate(),
+            marker: PhantomData,
+        }
+    }
+
+    /// Duplicates the set as a hybrid set.
+    pub fn to_hybrid(&self) -> HybridBitSet<T> {
+        // This domain_size may be slightly larger than the one specified
+        // upon creation, due to rounding up to a whole word. That's ok.
+        let domain_size = self.words().len() * WORD_BITS;
+
+        // Note: we currently don't bother trying to make a Sparse set.
+        HybridBitSet::Dense(self.to_owned(), domain_size)
+    }
+
+    pub fn to_string(&self, bits: usize) -> String {
+        let mut result = String::new();
+        let mut sep = '[';
+
+        // Note: this is a little endian printout of bytes.
+
+        // i tracks how many bits we have printed so far.
+        let mut i = 0;
+        for word in &self.data {
+            let mut v = *word;
+            for _ in 0..WORD_BYTES { // for each byte in `v`:
+                let remain = bits - i;
+                // If less than a byte remains, then mask just that many bits.
+                let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
+                assert!(mask <= 0xFF);
+                let byte = v & mask;
+
+                result.push_str(&format!("{}{:02x}", sep, byte));
+
+                if remain <= 8 { break; }
+                v >>= 8;
+                i += 8;
+                sep = '-';
+            }
+            sep = '|';
+        }
+        result.push(']');
+
+        result
+    }
+}
+
+/// This is implemented by all the bitsets so that BitSet::union() can be
+/// passed any type of bitset.
+pub trait UnionIntoBitSet<T: Idx> {
+    // Performs `other = other | self`.
+    fn union_into(&self, other: &mut BitSet<T>) -> bool;
+}
+
+/// This is implemented by all the bitsets so that BitSet::subtract() can be
+/// passed any type of bitset.
+pub trait SubtractFromBitSet<T: Idx> {
+    // Performs `other = other - self`.
+    fn subtract_from(&self, other: &mut BitSet<T>) -> bool;
+}
+
+impl<T: Idx> UnionIntoBitSet<T> for BitSet<T> {
+    fn union_into(&self, other: &mut BitSet<T>) -> bool {
+        bitwise(other.words_mut(), self.words(), &Union)
+    }
+}
+
+impl<T: Idx> SubtractFromBitSet<T> for BitSet<T> {
+    fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
+        bitwise(other.words_mut(), self.words(), &Subtract)
+    }
+}
+
+impl<T: Idx> fmt::Debug for BitSet<T> {
+    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
+        w.debug_list()
+         .entries(self.iter())
+         .finish()
+    }
+}
+
+impl<T: Idx> rustc_serialize::Encodable for BitSet<T> {
+    fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
+        self.data.encode(encoder)
+    }
+}
+
+impl<T: Idx> rustc_serialize::Decodable for BitSet<T> {
+    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<BitSet<T>, D::Error> {
+        let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
+        Ok(BitSet {
+            data: words,
+            marker: PhantomData,
+        })
+    }
+}
+
+pub struct BitIter<'a, T: Idx> {
+    cur: Option<(Word, usize)>,
+    iter: iter::Enumerate<slice::Iter<'a, Word>>,
+    marker: PhantomData<T>
+}
+
+impl<'a, T: Idx> Iterator for BitIter<'a, T> {
+    type Item = T;
+    fn next(&mut self) -> Option<T> {
+        loop {
+            if let Some((ref mut word, offset)) = self.cur {
+                let bit_pos = word.trailing_zeros() as usize;
+                if bit_pos != WORD_BITS {
+                    let bit = 1 << bit_pos;
+                    *word ^= bit;
+                    return Some(T::new(bit_pos + offset))
+                }
+            }
+
+            let (i, word) = self.iter.next()?;
+            self.cur = Some((*word, WORD_BITS * i));
+        }
+    }
+}
+
+pub trait BitwiseOperator {
+    /// Applies some bit-operation pointwise to each of the bits in the two inputs.
+    fn join(&self, pred1: Word, pred2: Word) -> Word;
+}
+
+#[inline]
+pub fn bitwise<Op: BitwiseOperator>(out_vec: &mut [Word], in_vec: &[Word], op: &Op) -> bool
+{
+    assert_eq!(out_vec.len(), in_vec.len());
+    let mut changed = false;
+    for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
+        let old_val = *out_elem;
+        let new_val = op.join(old_val, *in_elem);
+        *out_elem = new_val;
+        changed |= old_val != new_val;
+    }
+    changed
+}
+
+pub struct Intersect;
+impl BitwiseOperator for Intersect {
+    #[inline]
+    fn join(&self, a: Word, b: Word) -> Word { a & b }
+}
+
+pub struct Union;
+impl BitwiseOperator for Union {
+    #[inline]
+    fn join(&self, a: Word, b: Word) -> Word { a | b }
+}
+
+pub struct Subtract;
+impl BitwiseOperator for Subtract {
+    #[inline]
+    fn join(&self, a: Word, b: Word) -> Word { a & !b }
+}
+
+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 an unsorted vector with no
+/// duplicates.
+///
+/// This type is used by HybridBitSet; do not use directly.
+#[derive(Clone, Debug)]
+pub struct SparseBitSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
+
+impl<T: Idx> SparseBitSet<T> {
+    fn new_empty() -> Self {
+        SparseBitSet(ArrayVec::new())
+    }
+
+    fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    fn contains(&self, elem: T) -> bool {
+        self.0.contains(&elem)
+    }
+
+    fn insert(&mut self, elem: T) -> bool {
+        // Ensure there are no duplicates.
+        if self.0.contains(&elem) {
+            false
+        } else {
+            self.0.push(elem);
+            true
+        }
+    }
+
+    fn remove(&mut self, elem: T) -> bool {
+        if let Some(i) = self.0.iter().position(|&e| e == elem) {
+            // Swap the found element to the end, then pop it.
+            let len = self.0.len();
+            self.0.swap(i, len - 1);
+            self.0.pop();
+            true
+        } else {
+            false
+        }
+    }
+
+    fn to_dense(&self, domain_size: usize) -> BitSet<T> {
+        let mut dense = BitSet::new_empty(domain_size);
+        for elem in self.0.iter() {
+            dense.insert(*elem);
+        }
+        dense
+    }
+
+    fn iter(&self) -> slice::Iter<T> {
+        self.0.iter()
+    }
+}
+
+impl<T: Idx> UnionIntoBitSet<T> for SparseBitSet<T> {
+    fn union_into(&self, other: &mut BitSet<T>) -> bool {
+        let mut changed = false;
+        for elem in self.iter() {
+            changed |= other.insert(*elem);
+        }
+        changed
+    }
+}
+
+impl<T: Idx> SubtractFromBitSet<T> for SparseBitSet<T> {
+    fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
+        let mut changed = false;
+        for elem in self.iter() {
+            changed |= other.remove(*elem);
+        }
+        changed
+    }
+}
+
+/// A fixed-size bitset type with a hybrid representation: sparse when there
+/// are up to a SPARSE_MAX elements in the set, but dense when there are more
+/// than SPARSE_MAX.
+///
+/// This type is especially efficient for sets that typically have a small
+/// number of elements, but a large `domain_size`, and are cleared frequently.
+///
+/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
+/// just be `usize`.
+#[derive(Clone, Debug)]
+pub enum HybridBitSet<T: Idx> {
+    Sparse(SparseBitSet<T>, usize),
+    Dense(BitSet<T>, usize),
+}
+
+impl<T: Idx> HybridBitSet<T> {
+    pub fn new_empty(domain_size: usize) -> Self {
+        HybridBitSet::Sparse(SparseBitSet::new_empty(), domain_size)
+    }
+
+    pub fn clear(&mut self) {
+        let domain_size = match *self {
+            HybridBitSet::Sparse(_, size) => size,
+            HybridBitSet::Dense(_, size) => size,
+        };
+        *self = HybridBitSet::new_empty(domain_size);
+    }
+
+    pub fn contains(&self, elem: T) -> bool {
+        match self {
+            HybridBitSet::Sparse(sparse, _) => sparse.contains(elem),
+            HybridBitSet::Dense(dense, _) => dense.contains(elem),
+        }
+    }
+
+    pub fn insert(&mut self, elem: T) -> bool {
+        match self {
+            HybridBitSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
+                // The set is sparse and has space for `elem`.
+                sparse.insert(elem)
+            }
+            HybridBitSet::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
+            }
+            HybridBitSet::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 = HybridBitSet::Sparse(SparseBitSet::new_empty(), 0);
+                match mem::replace(self, dummy) {
+                    HybridBitSet::Sparse(sparse, domain_size) => {
+                        let mut dense = sparse.to_dense(domain_size);
+                        let changed = dense.insert(elem);
+                        assert!(changed);
+                        mem::replace(self, HybridBitSet::Dense(dense, domain_size));
+                        changed
+                    }
+                    _ => panic!("impossible"),
+                }
+            }
+
+            HybridBitSet::Dense(dense, _) => dense.insert(elem),
+        }
+    }
+
+    pub fn remove(&mut self, elem: T) -> bool {
+        // Note: we currently don't bother going from Dense back to Sparse.
+        match self {
+            HybridBitSet::Sparse(sparse, _) => sparse.remove(elem),
+            HybridBitSet::Dense(dense, _) => dense.remove(elem),
+        }
+    }
+
+    /// Converts to a dense set, consuming itself in the process.
+    pub fn to_dense(self) -> BitSet<T> {
+        match self {
+            HybridBitSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
+            HybridBitSet::Dense(dense, _) => dense,
+        }
+    }
+
+    /// Iteration order is unspecified.
+    pub fn iter(&self) -> HybridIter<T> {
+        match self {
+            HybridBitSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
+            HybridBitSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
+        }
+    }
+}
+
+impl<T: Idx> UnionIntoBitSet<T> for HybridBitSet<T> {
+    fn union_into(&self, other: &mut BitSet<T>) -> bool {
+        match self {
+            HybridBitSet::Sparse(sparse, _) => sparse.union_into(other),
+            HybridBitSet::Dense(dense, _) => dense.union_into(other),
+        }
+    }
+}
+
+impl<T: Idx> SubtractFromBitSet<T> for HybridBitSet<T> {
+    fn subtract_from(&self, other: &mut BitSet<T>) -> bool {
+        match self {
+            HybridBitSet::Sparse(sparse, _) => sparse.subtract_from(other),
+            HybridBitSet::Dense(dense, _) => dense.subtract_from(other),
+        }
+    }
+}
+
+pub enum HybridIter<'a, T: Idx> {
+    Sparse(slice::Iter<'a, T>),
+    Dense(BitIter<'a, T>),
+}
+
+impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        match self {
+            HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
+            HybridIter::Dense(dense) => dense.next(),
+        }
+    }
+}
+
+/// A resizable bitset type with a dense representation.
+///
+/// `T` is an index type, typically a newtyped `usize` wrapper, but it can also
+/// just be `usize`.
+#[derive(Clone, Debug, PartialEq)]
+pub struct GrowableBitSet<T: Idx> {
+    bit_set: BitSet<T>,
+}
+
+impl<T: Idx> GrowableBitSet<T> {
+    pub fn grow(&mut self, domain_size: T) {
+        let num_words = num_words(domain_size);
+        if self.bit_set.data.len() <= num_words {
+            self.bit_set.data.resize(num_words + 1, 0)
+        }
+    }
+
+    pub fn new_empty() -> GrowableBitSet<T> {
+        GrowableBitSet { bit_set: BitSet::new_empty(0) }
+    }
+
+    pub fn with_capacity(bits: usize) -> GrowableBitSet<T> {
+        GrowableBitSet { bit_set: BitSet::new_empty(bits) }
+    }
+
+    /// Returns true if the bit has changed.
+    #[inline]
+    pub fn insert(&mut self, bit: T) -> bool {
+        self.grow(bit);
+        self.bit_set.insert(bit)
+    }
+
+    #[inline]
+    pub fn contains(&self, bit: T) -> bool {
+        let (word, mask) = word_mask(bit);
+        if let Some(word) = self.bit_set.data.get(word) {
+            (word & mask) != 0
+        } else {
+            false
+        }
+    }
+}
+
+/// A fixed-size 2D bit matrix type with a dense representation.
+///
+/// `R` and `C` are index types used to identify rows and columns respectively;
+/// typically newtyped `usize` wrappers, but they can also just be `usize`.
+///
+#[derive(Clone, Debug)]
+pub struct BitMatrix<R: Idx, C: Idx> {
+    columns: usize,
+    vector: Vec<Word>,
+    marker: PhantomData<(R, C)>,
+}
+
+impl<R: Idx, C: Idx> BitMatrix<R, C> {
+    /// Create a new `rows x columns` matrix, initially empty.
+    pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
+        // For every element, we need one bit for every other
+        // element. Round up to an even number of words.
+        let words_per_row = num_words(columns);
+        BitMatrix {
+            columns,
+            vector: vec![0; rows * words_per_row],
+            marker: PhantomData,
+        }
+    }
+
+    /// The range of bits for a given row.
+    fn range(&self, row: R) -> (usize, usize) {
+        let row = row.index();
+        let words_per_row = num_words(self.columns);
+        let start = row * words_per_row;
+        (start, start + words_per_row)
+    }
+
+    /// Sets the cell at `(row, column)` to true. Put another way, insert
+    /// `column` to the bitset for `row`.
+    ///
+    /// Returns true if this changed the matrix, and false otherwise.
+    pub fn insert(&mut self, row: R, column: R) -> bool {
+        let (start, _) = self.range(row);
+        let (word, mask) = word_mask(column);
+        let vector = &mut self.vector[..];
+        let v1 = vector[start + word];
+        let v2 = v1 | mask;
+        vector[start + word] = v2;
+        v1 != v2
+    }
+
+    /// Do the bits from `row` contain `column`? Put another way, is
+    /// the matrix cell at `(row, column)` true?  Put yet another way,
+    /// if the matrix represents (transitive) reachability, can
+    /// `row` reach `column`?
+    pub fn contains(&self, row: R, column: R) -> bool {
+        let (start, _) = self.range(row);
+        let (word, mask) = word_mask(column);
+        (self.vector[start + word] & mask) != 0
+    }
+
+    /// Returns those indices that are true in rows `a` and `b`.  This
+    /// is an O(n) operation where `n` is the number of elements
+    /// (somewhat independent from the actual size of the
+    /// intersection, in particular).
+    pub fn intersect_rows(&self, a: R, b: R) -> Vec<C> {
+        let (a_start, a_end) = self.range(a);
+        let (b_start, b_end) = self.range(b);
+        let mut result = Vec::with_capacity(self.columns);
+        for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
+            let mut v = self.vector[i] & self.vector[j];
+            for bit in 0..WORD_BITS {
+                if v == 0 {
+                    break;
+                }
+                if v & 0x1 != 0 {
+                    result.push(C::new(base * WORD_BITS + bit));
+                }
+                v >>= 1;
+            }
+        }
+        result
+    }
+
+    /// Add the bits from row `read` to the bits from row `write`,
+    /// return true if anything changed.
+    ///
+    /// This is used when computing transitive reachability because if
+    /// you have an edge `write -> read`, because in that case
+    /// `write` can reach everything that `read` can (and
+    /// potentially more).
+    pub fn union_rows(&mut self, read: R, write: R) -> bool {
+        let (read_start, read_end) = self.range(read);
+        let (write_start, write_end) = self.range(write);
+        let vector = &mut self.vector[..];
+        let mut changed = false;
+        for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
+            let v1 = vector[write_index];
+            let v2 = v1 | vector[read_index];
+            vector[write_index] = v2;
+            changed |= v1 != v2;
+        }
+        changed
+    }
+
+    /// Iterates through all the columns set to true in a given row of
+    /// the matrix.
+    pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
+        let (start, end) = self.range(row);
+        BitIter {
+            cur: None,
+            iter: self.vector[start..end].iter().enumerate(),
+            marker: PhantomData,
+        }
+    }
+}
+
+/// A fixed-column-size, variable-row-size 2D bit matrix with a moderately
+/// sparse representation.
+///
+/// Initially, every row has no explicit representation. If any bit within a
+/// row is set, the entire row is instantiated as
+/// `Some(<full-column-width-BitSet>)`. Furthermore, any previously
+/// uninstantiated rows prior to it will be instantiated as `None`. Those prior
+/// rows may themselves become fully instantiated later on if any of their bits
+/// are set.
+///
+/// `R` and `C` are index types used to identify rows and columns respectively;
+/// typically newtyped `usize` wrappers, but they can also just be `usize`.
+#[derive(Clone, Debug)]
+pub struct SparseBitMatrix<R, C>
+where
+    R: Idx,
+    C: Idx,
+{
+    num_columns: usize,
+    rows: IndexVec<R, Option<BitSet<C>>>,
+}
+
+impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
+    /// Create a new empty sparse bit matrix with no rows or columns.
+    pub fn new(num_columns: usize) -> Self {
+        Self {
+            num_columns,
+            rows: IndexVec::new(),
+        }
+    }
+
+    fn ensure_row(&mut self, row: R) -> &mut BitSet<C> {
+        // Instantiate any missing rows up to and including row `row` with an
+        // empty BitSet.
+        self.rows.ensure_contains_elem(row, || None);
+
+        // Then replace row `row` with a full BitSet if necessary.
+        let num_columns = self.num_columns;
+        self.rows[row].get_or_insert_with(|| BitSet::new_empty(num_columns))
+    }
+
+    /// Sets the cell at `(row, column)` to true. Put another way, insert
+    /// `column` to the bitset for `row`.
+    ///
+    /// Returns true if this changed the matrix, and false otherwise.
+    pub fn insert(&mut self, row: R, column: C) -> bool {
+        self.ensure_row(row).insert(column)
+    }
+
+    /// Do the bits from `row` contain `column`? Put another way, is
+    /// the matrix cell at `(row, column)` true?  Put yet another way,
+    /// if the matrix represents (transitive) reachability, can
+    /// `row` reach `column`?
+    pub fn contains(&self, row: R, column: C) -> bool {
+        self.row(row).map_or(false, |r| r.contains(column))
+    }
+
+    /// Add the bits from row `read` to the bits from row `write`,
+    /// return true if anything changed.
+    ///
+    /// This is used when computing transitive reachability because if
+    /// you have an edge `write -> read`, because in that case
+    /// `write` can reach everything that `read` can (and
+    /// potentially more).
+    pub fn union_rows(&mut self, read: R, write: R) -> bool {
+        if read == write || self.row(read).is_none() {
+            return false;
+        }
+
+        self.ensure_row(write);
+        if let (Some(read_row), Some(write_row)) = self.rows.pick2_mut(read, write) {
+            write_row.union(read_row)
+        } else {
+            unreachable!()
+        }
+    }
+
+    /// Merge a row, `from`, into the `into` row.
+    pub fn union_into_row(&mut self, into: R, from: &BitSet<C>) -> bool {
+        self.ensure_row(into).union(from)
+    }
+
+    /// Insert all bits in the given row.
+    pub fn insert_all_into_row(&mut self, row: R) {
+        self.ensure_row(row).insert_all();
+    }
+
+    pub fn rows(&self) -> impl Iterator<Item = R> {
+        self.rows.indices()
+    }
+
+    /// 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 {
+        self.row(row).into_iter().flat_map(|r| r.iter())
+    }
+
+    pub fn row(&self, row: R) -> Option<&BitSet<C>> {
+        if let Some(Some(row)) = self.rows.get(row) {
+            Some(row)
+        } else {
+            None
+        }
+    }
+}
+
+#[inline]
+fn num_words<T: Idx>(elements: T) -> usize {
+    (elements.index() + WORD_BITS - 1) / WORD_BITS
+}
+
+#[inline]
+fn word_mask<T: Idx>(index: T) -> (usize, Word) {
+    let index = index.index();
+    let word = index / WORD_BITS;
+    let mask = 1 << (index % WORD_BITS);
+    (word, mask)
+}
+
+#[test]
+fn test_clear_above() {
+    use std::cmp;
+
+    for i in 0..256 {
+        let mut idx_buf: BitSet<usize> = BitSet::new_filled(128);
+        idx_buf.clear_above(i);
+
+        let elems: Vec<usize> = idx_buf.iter().collect();
+        let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
+        assert_eq!(elems, expected);
+    }
+}
+
+#[test]
+fn test_set_up_to() {
+    for i in 0..128 {
+        for mut idx_buf in
+            vec![BitSet::new_empty(128), BitSet::new_filled(128)].into_iter()
+        {
+            idx_buf.set_up_to(i);
+
+            let elems: Vec<usize> = idx_buf.iter().collect();
+            let expected: Vec<usize> = (0..i).collect();
+            assert_eq!(elems, expected);
+        }
+    }
+}
+
+#[test]
+fn test_new_filled() {
+    for i in 0..128 {
+        let idx_buf = BitSet::new_filled(i);
+        let elems: Vec<usize> = idx_buf.iter().collect();
+        let expected: Vec<usize> = (0..i).collect();
+        assert_eq!(elems, expected);
+    }
+}
+
+#[test]
+fn bitset_iter_works() {
+    let mut bitset: BitSet<usize> = BitSet::new_empty(100);
+    bitset.insert(1);
+    bitset.insert(10);
+    bitset.insert(19);
+    bitset.insert(62);
+    bitset.insert(63);
+    bitset.insert(64);
+    bitset.insert(65);
+    bitset.insert(66);
+    bitset.insert(99);
+    assert_eq!(
+        bitset.iter().collect::<Vec<_>>(),
+        [1, 10, 19, 62, 63, 64, 65, 66, 99]
+    );
+}
+
+#[test]
+fn bitset_iter_works_2() {
+    let mut bitset: BitSet<usize> = BitSet::new_empty(319);
+    bitset.insert(0);
+    bitset.insert(127);
+    bitset.insert(191);
+    bitset.insert(255);
+    bitset.insert(319);
+    assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
+}
+
+#[test]
+fn union_two_vecs() {
+    let mut set1: BitSet<usize> = BitSet::new_empty(65);
+    let mut set2: BitSet<usize> = BitSet::new_empty(65);
+    assert!(set1.insert(3));
+    assert!(!set1.insert(3));
+    assert!(set2.insert(5));
+    assert!(set2.insert(64));
+    assert!(set1.union(&set2));
+    assert!(!set1.union(&set2));
+    assert!(set1.contains(3));
+    assert!(!set1.contains(4));
+    assert!(set1.contains(5));
+    assert!(!set1.contains(63));
+    assert!(set1.contains(64));
+}
+
+#[test]
+fn grow() {
+    let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
+    for index in 0..65 {
+        assert!(set.insert(index));
+        assert!(!set.insert(index));
+    }
+    set.grow(128);
+
+    // Check if the bits set before growing are still set
+    for index in 0..65 {
+        assert!(set.contains(index));
+    }
+
+    // Check if the new bits are all un-set
+    for index in 65..128 {
+        assert!(!set.contains(index));
+    }
+
+    // Check that we can set all new bits without running out of bounds
+    for index in 65..128 {
+        assert!(set.insert(index));
+        assert!(!set.insert(index));
+    }
+}
+
+#[test]
+fn matrix_intersection() {
+    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
+
+    // (*) Elements reachable from both 2 and 65.
+
+    matrix.insert(2, 3);
+    matrix.insert(2, 6);
+    matrix.insert(2, 10); // (*)
+    matrix.insert(2, 64); // (*)
+    matrix.insert(2, 65);
+    matrix.insert(2, 130);
+    matrix.insert(2, 160); // (*)
+
+    matrix.insert(64, 133);
+
+    matrix.insert(65, 2);
+    matrix.insert(65, 8);
+    matrix.insert(65, 10); // (*)
+    matrix.insert(65, 64); // (*)
+    matrix.insert(65, 68);
+    matrix.insert(65, 133);
+    matrix.insert(65, 160); // (*)
+
+    let intersection = matrix.intersect_rows(2, 64);
+    assert!(intersection.is_empty());
+
+    let intersection = matrix.intersect_rows(2, 65);
+    assert_eq!(intersection, &[10, 64, 160]);
+}
+
+#[test]
+fn matrix_iter() {
+    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
+    matrix.insert(3, 22);
+    matrix.insert(3, 75);
+    matrix.insert(2, 99);
+    matrix.insert(4, 0);
+    matrix.union_rows(3, 5);
+
+    let expected = [99];
+    let mut iter = expected.iter();
+    for i in matrix.iter(2) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(3) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [0];
+    let mut iter = expected.iter();
+    for i in matrix.iter(4) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(5) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+}
+
+#[test]
+fn sparse_matrix_iter() {
+    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
+    matrix.insert(3, 22);
+    matrix.insert(3, 75);
+    matrix.insert(2, 99);
+    matrix.insert(4, 0);
+    matrix.union_rows(3, 5);
+
+    let expected = [99];
+    let mut iter = expected.iter();
+    for i in matrix.iter(2) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(3) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [0];
+    let mut iter = expected.iter();
+    for i in matrix.iter(4) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(5) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+}
diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
deleted file mode 100644
index 52cc347f8e7..00000000000
--- a/src/librustc_data_structures/bitvec.rs
+++ /dev/null
@@ -1,781 +0,0 @@
-// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-use indexed_vec::{Idx, IndexVec};
-use rustc_serialize;
-use std::iter;
-use std::marker::PhantomData;
-use std::slice;
-
-pub type Word = u64;
-pub const WORD_BYTES: usize = ::std::mem::size_of::<Word>();
-pub const WORD_BITS: usize = WORD_BYTES * 8;
-
-/// A very simple BitArray type.
-///
-/// It does not support resizing after creation; use `BitVector` for that.
-#[derive(Clone, Debug, Eq, PartialEq)]
-pub struct BitArray<C: Idx> {
-    data: Vec<Word>,
-    marker: PhantomData<C>,
-}
-
-impl<C: Idx> BitArray<C> {
-    // Do not make this method public, instead switch your use case to BitVector.
-    #[inline]
-    fn grow(&mut self, num_bits: C) {
-        let num_words = num_words(num_bits);
-        if self.data.len() <= num_words {
-            self.data.resize(num_words + 1, 0)
-        }
-    }
-
-    #[inline]
-    pub fn new(num_bits: usize) -> BitArray<C> {
-        BitArray::new_empty(num_bits)
-    }
-
-    #[inline]
-    pub fn new_empty(num_bits: usize) -> BitArray<C> {
-        let num_words = num_words(num_bits);
-        BitArray {
-            data: vec![0; num_words],
-            marker: PhantomData,
-        }
-    }
-
-    #[inline]
-    pub fn new_filled(num_bits: usize) -> BitArray<C> {
-        let num_words = num_words(num_bits);
-        let mut result = BitArray {
-            data: vec![!0; num_words],
-            marker: PhantomData,
-        };
-        result.clear_above(num_bits);
-        result
-    }
-
-    #[inline]
-    pub fn clear(&mut self) {
-        for p in &mut self.data {
-            *p = 0;
-        }
-    }
-
-    /// Sets all elements up to `num_bits`.
-    pub fn set_up_to(&mut self, num_bits: usize) {
-        for p in &mut self.data {
-            *p = !0;
-        }
-        self.clear_above(num_bits);
-    }
-
-    /// Clear all elements above `num_bits`.
-    fn clear_above(&mut self, num_bits: usize) {
-        let first_clear_block = num_bits / WORD_BITS;
-
-        if first_clear_block < self.data.len() {
-            // Within `first_clear_block`, the `num_bits % WORD_BITS` LSBs
-            // should remain.
-            let mask = (1 << (num_bits % WORD_BITS)) - 1;
-            self.data[first_clear_block] &= mask;
-
-            // All the blocks above `first_clear_block` are fully cleared.
-            for b in &mut self.data[first_clear_block + 1..] {
-                *b = 0;
-            }
-        }
-    }
-
-    pub fn count(&self) -> usize {
-        self.data.iter().map(|e| e.count_ones() as usize).sum()
-    }
-
-    /// True if `self` contains the bit `bit`.
-    #[inline]
-    pub fn contains(&self, bit: C) -> bool {
-        let (word, mask) = word_mask(bit);
-        (self.data[word] & mask) != 0
-    }
-
-    /// True if `self` contains all the bits in `other`.
-    ///
-    /// The two vectors must have the same length.
-    #[inline]
-    pub fn contains_all(&self, other: &BitArray<C>) -> bool {
-        assert_eq!(self.data.len(), other.data.len());
-        self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
-    }
-
-    #[inline]
-    pub fn is_empty(&self) -> bool {
-        self.data.iter().all(|a| *a == 0)
-    }
-
-    /// Returns true if the bit has changed.
-    #[inline]
-    pub fn insert(&mut self, bit: C) -> bool {
-        let (word, mask) = word_mask(bit);
-        let data = &mut self.data[word];
-        let value = *data;
-        let new_value = value | mask;
-        *data = new_value;
-        new_value != value
-    }
-
-    /// Sets all bits to true.
-    pub fn insert_all(&mut self) {
-        for data in &mut self.data {
-            *data = !0;
-        }
-    }
-
-    /// Returns true if the bit has changed.
-    #[inline]
-    pub fn remove(&mut self, bit: C) -> bool {
-        let (word, mask) = word_mask(bit);
-        let data = &mut self.data[word];
-        let value = *data;
-        let new_value = value & !mask;
-        *data = new_value;
-        new_value != value
-    }
-
-    #[inline]
-    pub fn merge(&mut self, all: &BitArray<C>) -> bool {
-        assert!(self.data.len() == all.data.len());
-        let mut changed = false;
-        for (i, j) in self.data.iter_mut().zip(&all.data) {
-            let value = *i;
-            *i = value | *j;
-            if value != *i {
-                changed = true;
-            }
-        }
-        changed
-    }
-
-    pub fn words(&self) -> &[Word] {
-        &self.data
-    }
-
-    pub fn words_mut(&mut self) -> &mut [Word] {
-        &mut self.data
-    }
-
-    /// Iterates over indexes of set bits in a sorted order
-    #[inline]
-    pub fn iter<'a>(&'a self) -> BitIter<'a, C> {
-        BitIter {
-            cur: None,
-            iter: self.data.iter().enumerate(),
-            marker: PhantomData,
-        }
-    }
-}
-
-impl<T: Idx> rustc_serialize::Encodable for BitArray<T> {
-    fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
-        self.data.encode(encoder)
-    }
-}
-
-impl<T: Idx> rustc_serialize::Decodable for BitArray<T> {
-    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<BitArray<T>, D::Error> {
-        let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
-        Ok(BitArray {
-            data: words,
-            marker: PhantomData,
-        })
-    }
-}
-
-pub struct BitIter<'a, C: Idx> {
-    cur: Option<(Word, usize)>,
-    iter: iter::Enumerate<slice::Iter<'a, Word>>,
-    marker: PhantomData<C>
-}
-
-impl<'a, C: Idx> Iterator for BitIter<'a, C> {
-    type Item = C;
-    fn next(&mut self) -> Option<C> {
-        loop {
-            if let Some((ref mut word, offset)) = self.cur {
-                let bit_pos = word.trailing_zeros() as usize;
-                if bit_pos != WORD_BITS {
-                    let bit = 1 << bit_pos;
-                    *word ^= bit;
-                    return Some(C::new(bit_pos + offset))
-                }
-            }
-
-            let (i, word) = self.iter.next()?;
-            self.cur = Some((*word, WORD_BITS * i));
-        }
-    }
-}
-
-pub trait BitwiseOperator {
-    /// Applies some bit-operation pointwise to each of the bits in the two inputs.
-    fn join(&self, pred1: Word, pred2: Word) -> Word;
-}
-
-#[inline]
-pub fn bitwise<Op: BitwiseOperator>(out_vec: &mut [Word], in_vec: &[Word], op: &Op) -> bool
-{
-    assert_eq!(out_vec.len(), in_vec.len());
-    let mut changed = false;
-    for (out_elem, in_elem) in out_vec.iter_mut().zip(in_vec.iter()) {
-        let old_val = *out_elem;
-        let new_val = op.join(old_val, *in_elem);
-        *out_elem = new_val;
-        changed |= old_val != new_val;
-    }
-    changed
-}
-
-pub struct Intersect;
-impl BitwiseOperator for Intersect {
-    #[inline]
-    fn join(&self, a: Word, b: Word) -> Word { a & b }
-}
-
-pub struct Union;
-impl BitwiseOperator for Union {
-    #[inline]
-    fn join(&self, a: Word, b: Word) -> Word { a | b }
-}
-
-pub struct Subtract;
-impl BitwiseOperator for Subtract {
-    #[inline]
-    fn join(&self, a: Word, b: Word) -> Word { a & !b }
-}
-
-pub fn bits_to_string(words: &[Word], bits: usize) -> String {
-    let mut result = String::new();
-    let mut sep = '[';
-
-    // Note: this is a little endian printout of bytes.
-
-    // i tracks how many bits we have printed so far.
-    let mut i = 0;
-    for &word in words.iter() {
-        let mut v = word;
-        for _ in 0..WORD_BYTES { // for each byte in `v`:
-            let remain = bits - i;
-            // If less than a byte remains, then mask just that many bits.
-            let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
-            assert!(mask <= 0xFF);
-            let byte = v & mask;
-
-            result.push_str(&format!("{}{:02x}", sep, byte));
-
-            if remain <= 8 { break; }
-            v >>= 8;
-            i += 8;
-            sep = '-';
-        }
-        sep = '|';
-    }
-    result.push(']');
-
-    result
-}
-
-/// A resizable BitVector type.
-#[derive(Clone, Debug, PartialEq)]
-pub struct BitVector<C: Idx> {
-    data: BitArray<C>,
-}
-
-impl<C: Idx> BitVector<C> {
-    pub fn grow(&mut self, num_bits: C) {
-        self.data.grow(num_bits)
-    }
-
-    pub fn new() -> BitVector<C> {
-        BitVector { data: BitArray::new(0) }
-    }
-
-    pub fn with_capacity(bits: usize) -> BitVector<C> {
-        BitVector { data: BitArray::new(bits) }
-    }
-
-    /// Returns true if the bit has changed.
-    #[inline]
-    pub fn insert(&mut self, bit: C) -> bool {
-        self.grow(bit);
-        self.data.insert(bit)
-    }
-
-    #[inline]
-    pub fn contains(&self, bit: C) -> bool {
-        let (word, mask) = word_mask(bit);
-        if let Some(word) = self.data.data.get(word) {
-            (word & mask) != 0
-        } else {
-            false
-        }
-    }
-}
-
-/// A "bit matrix" is basically a matrix of booleans represented as
-/// one gigantic bitvector. In other words, it is as if you have
-/// `rows` bitvectors, each of length `columns`.
-#[derive(Clone, Debug)]
-pub struct BitMatrix<R: Idx, C: Idx> {
-    columns: usize,
-    vector: Vec<Word>,
-    phantom: PhantomData<(R, C)>,
-}
-
-impl<R: Idx, C: Idx> BitMatrix<R, C> {
-    /// Create a new `rows x columns` matrix, initially empty.
-    pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
-        // For every element, we need one bit for every other
-        // element. Round up to an even number of words.
-        let words_per_row = num_words(columns);
-        BitMatrix {
-            columns,
-            vector: vec![0; rows * words_per_row],
-            phantom: PhantomData,
-        }
-    }
-
-    /// The range of bits for a given row.
-    fn range(&self, row: R) -> (usize, usize) {
-        let row = row.index();
-        let words_per_row = num_words(self.columns);
-        let start = row * words_per_row;
-        (start, start + words_per_row)
-    }
-
-    /// Sets the cell at `(row, column)` to true. Put another way, add
-    /// `column` to the bitset for `row`.
-    ///
-    /// Returns true if this changed the matrix, and false otherwise.
-    pub fn add(&mut self, row: R, column: R) -> bool {
-        let (start, _) = self.range(row);
-        let (word, mask) = word_mask(column);
-        let vector = &mut self.vector[..];
-        let v1 = vector[start + word];
-        let v2 = v1 | mask;
-        vector[start + word] = v2;
-        v1 != v2
-    }
-
-    /// Do the bits from `row` contain `column`? Put another way, is
-    /// the matrix cell at `(row, column)` true?  Put yet another way,
-    /// if the matrix represents (transitive) reachability, can
-    /// `row` reach `column`?
-    pub fn contains(&self, row: R, column: R) -> bool {
-        let (start, _) = self.range(row);
-        let (word, mask) = word_mask(column);
-        (self.vector[start + word] & mask) != 0
-    }
-
-    /// Returns those indices that are true in rows `a` and `b`.  This
-    /// is an O(n) operation where `n` is the number of elements
-    /// (somewhat independent from the actual size of the
-    /// intersection, in particular).
-    pub fn intersection(&self, a: R, b: R) -> Vec<C> {
-        let (a_start, a_end) = self.range(a);
-        let (b_start, b_end) = self.range(b);
-        let mut result = Vec::with_capacity(self.columns);
-        for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
-            let mut v = self.vector[i] & self.vector[j];
-            for bit in 0..WORD_BITS {
-                if v == 0 {
-                    break;
-                }
-                if v & 0x1 != 0 {
-                    result.push(C::new(base * WORD_BITS + bit));
-                }
-                v >>= 1;
-            }
-        }
-        result
-    }
-
-    /// Add the bits from row `read` to the bits from row `write`,
-    /// return true if anything changed.
-    ///
-    /// This is used when computing transitive reachability because if
-    /// you have an edge `write -> read`, because in that case
-    /// `write` can reach everything that `read` can (and
-    /// potentially more).
-    pub fn merge(&mut self, read: R, write: R) -> bool {
-        let (read_start, read_end) = self.range(read);
-        let (write_start, write_end) = self.range(write);
-        let vector = &mut self.vector[..];
-        let mut changed = false;
-        for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
-            let v1 = vector[write_index];
-            let v2 = v1 | vector[read_index];
-            vector[write_index] = v2;
-            changed |= v1 != v2;
-        }
-        changed
-    }
-
-    /// Iterates through all the columns set to true in a given row of
-    /// the matrix.
-    pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
-        let (start, end) = self.range(row);
-        BitIter {
-            cur: None,
-            iter: self.vector[start..end].iter().enumerate(),
-            marker: PhantomData,
-        }
-    }
-}
-
-/// A moderately sparse bit matrix, in which rows are instantiated lazily.
-///
-/// Initially, every row has no explicit representation. If any bit within a
-/// row is set, the entire row is instantiated as
-/// `Some(<full-column-width-BitArray>)`. Furthermore, any previously
-/// uninstantiated rows prior to it will be instantiated as `None`. Those prior
-/// rows may themselves become fully instantiated later on if any of their bits
-/// are set.
-#[derive(Clone, Debug)]
-pub struct SparseBitMatrix<R, C>
-where
-    R: Idx,
-    C: Idx,
-{
-    num_columns: usize,
-    rows: IndexVec<R, Option<BitArray<C>>>,
-}
-
-impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
-    /// Create a new empty sparse bit matrix with no rows or columns.
-    pub fn new(num_columns: usize) -> Self {
-        Self {
-            num_columns,
-            rows: IndexVec::new(),
-        }
-    }
-
-    fn ensure_row(&mut self, row: R) -> &mut BitArray<C> {
-        // Instantiate any missing rows up to and including row `row` with an
-        // empty BitArray.
-        self.rows.ensure_contains_elem(row, || None);
-
-        // Then replace row `row` with a full BitArray if necessary.
-        let num_columns = self.num_columns;
-        self.rows[row].get_or_insert_with(|| BitArray::new(num_columns))
-    }
-
-    /// Sets the cell at `(row, column)` to true. Put another way, insert
-    /// `column` to the bitset for `row`.
-    ///
-    /// Returns true if this changed the matrix, and false otherwise.
-    pub fn add(&mut self, row: R, column: C) -> bool {
-        self.ensure_row(row).insert(column)
-    }
-
-    /// Do the bits from `row` contain `column`? Put another way, is
-    /// the matrix cell at `(row, column)` true?  Put yet another way,
-    /// if the matrix represents (transitive) reachability, can
-    /// `row` reach `column`?
-    pub fn contains(&self, row: R, column: C) -> bool {
-        self.row(row).map_or(false, |r| r.contains(column))
-    }
-
-    /// Add the bits from row `read` to the bits from row `write`,
-    /// return true if anything changed.
-    ///
-    /// This is used when computing transitive reachability because if
-    /// you have an edge `write -> read`, because in that case
-    /// `write` can reach everything that `read` can (and
-    /// potentially more).
-    pub fn merge(&mut self, read: R, write: R) -> bool {
-        if read == write || self.row(read).is_none() {
-            return false;
-        }
-
-        self.ensure_row(write);
-        if let (Some(bitvec_read), Some(bitvec_write)) = self.rows.pick2_mut(read, write) {
-            bitvec_write.merge(bitvec_read)
-        } else {
-            unreachable!()
-        }
-    }
-
-    /// Merge a row, `from`, into the `into` row.
-    pub fn merge_into(&mut self, into: R, from: &BitArray<C>) -> bool {
-        self.ensure_row(into).merge(from)
-    }
-
-    /// Add all bits to the given row.
-    pub fn add_all(&mut self, row: R) {
-        self.ensure_row(row).insert_all();
-    }
-
-    pub fn rows(&self) -> impl Iterator<Item = R> {
-        self.rows.indices()
-    }
-
-    /// 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 {
-        self.row(row).into_iter().flat_map(|r| r.iter())
-    }
-
-    pub fn row(&self, row: R) -> Option<&BitArray<C>> {
-        if let Some(Some(row)) = self.rows.get(row) {
-            Some(row)
-        } else {
-            None
-        }
-    }
-}
-
-#[inline]
-fn num_words<C: Idx>(elements: C) -> usize {
-    (elements.index() + WORD_BITS - 1) / WORD_BITS
-}
-
-#[inline]
-fn word_mask<C: Idx>(index: C) -> (usize, Word) {
-    let index = index.index();
-    let word = index / WORD_BITS;
-    let mask = 1 << (index % WORD_BITS);
-    (word, mask)
-}
-
-#[test]
-fn test_clear_above() {
-    use std::cmp;
-
-    for i in 0..256 {
-        let mut idx_buf: BitArray<usize> = BitArray::new_filled(128);
-        idx_buf.clear_above(i);
-
-        let elems: Vec<usize> = idx_buf.iter().collect();
-        let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
-        assert_eq!(elems, expected);
-    }
-}
-
-#[test]
-fn test_set_up_to() {
-    for i in 0..128 {
-        for mut idx_buf in
-            vec![BitArray::new_empty(128), BitArray::new_filled(128)]
-            .into_iter()
-        {
-            idx_buf.set_up_to(i);
-
-            let elems: Vec<usize> = idx_buf.iter().collect();
-            let expected: Vec<usize> = (0..i).collect();
-            assert_eq!(elems, expected);
-        }
-    }
-}
-
-#[test]
-fn test_new_filled() {
-    for i in 0..128 {
-        let idx_buf = BitArray::new_filled(i);
-        let elems: Vec<usize> = idx_buf.iter().collect();
-        let expected: Vec<usize> = (0..i).collect();
-        assert_eq!(elems, expected);
-    }
-}
-
-#[test]
-fn bitvec_iter_works() {
-    let mut bitvec: BitArray<usize> = BitArray::new(100);
-    bitvec.insert(1);
-    bitvec.insert(10);
-    bitvec.insert(19);
-    bitvec.insert(62);
-    bitvec.insert(63);
-    bitvec.insert(64);
-    bitvec.insert(65);
-    bitvec.insert(66);
-    bitvec.insert(99);
-    assert_eq!(
-        bitvec.iter().collect::<Vec<_>>(),
-        [1, 10, 19, 62, 63, 64, 65, 66, 99]
-    );
-}
-
-#[test]
-fn bitvec_iter_works_2() {
-    let mut bitvec: BitArray<usize> = BitArray::new(319);
-    bitvec.insert(0);
-    bitvec.insert(127);
-    bitvec.insert(191);
-    bitvec.insert(255);
-    bitvec.insert(319);
-    assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
-}
-
-#[test]
-fn union_two_vecs() {
-    let mut vec1: BitArray<usize> = BitArray::new(65);
-    let mut vec2: BitArray<usize> = BitArray::new(65);
-    assert!(vec1.insert(3));
-    assert!(!vec1.insert(3));
-    assert!(vec2.insert(5));
-    assert!(vec2.insert(64));
-    assert!(vec1.merge(&vec2));
-    assert!(!vec1.merge(&vec2));
-    assert!(vec1.contains(3));
-    assert!(!vec1.contains(4));
-    assert!(vec1.contains(5));
-    assert!(!vec1.contains(63));
-    assert!(vec1.contains(64));
-}
-
-#[test]
-fn grow() {
-    let mut vec1: BitVector<usize> = BitVector::with_capacity(65);
-    for index in 0..65 {
-        assert!(vec1.insert(index));
-        assert!(!vec1.insert(index));
-    }
-    vec1.grow(128);
-
-    // Check if the bits set before growing are still set
-    for index in 0..65 {
-        assert!(vec1.contains(index));
-    }
-
-    // Check if the new bits are all un-set
-    for index in 65..128 {
-        assert!(!vec1.contains(index));
-    }
-
-    // Check that we can set all new bits without running out of bounds
-    for index in 65..128 {
-        assert!(vec1.insert(index));
-        assert!(!vec1.insert(index));
-    }
-}
-
-#[test]
-fn matrix_intersection() {
-    let mut vec1: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
-
-    // (*) Elements reachable from both 2 and 65.
-
-    vec1.add(2, 3);
-    vec1.add(2, 6);
-    vec1.add(2, 10); // (*)
-    vec1.add(2, 64); // (*)
-    vec1.add(2, 65);
-    vec1.add(2, 130);
-    vec1.add(2, 160); // (*)
-
-    vec1.add(64, 133);
-
-    vec1.add(65, 2);
-    vec1.add(65, 8);
-    vec1.add(65, 10); // (*)
-    vec1.add(65, 64); // (*)
-    vec1.add(65, 68);
-    vec1.add(65, 133);
-    vec1.add(65, 160); // (*)
-
-    let intersection = vec1.intersection(2, 64);
-    assert!(intersection.is_empty());
-
-    let intersection = vec1.intersection(2, 65);
-    assert_eq!(intersection, &[10, 64, 160]);
-}
-
-#[test]
-fn matrix_iter() {
-    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
-    matrix.add(3, 22);
-    matrix.add(3, 75);
-    matrix.add(2, 99);
-    matrix.add(4, 0);
-    matrix.merge(3, 5);
-
-    let expected = [99];
-    let mut iter = expected.iter();
-    for i in matrix.iter(2) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(3) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [0];
-    let mut iter = expected.iter();
-    for i in matrix.iter(4) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(5) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-}
-
-#[test]
-fn sparse_matrix_iter() {
-    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
-    matrix.add(3, 22);
-    matrix.add(3, 75);
-    matrix.add(2, 99);
-    matrix.add(4, 0);
-    matrix.merge(3, 5);
-
-    let expected = [99];
-    let mut iter = expected.iter();
-    for i in matrix.iter(2) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(3) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [0];
-    let mut iter = expected.iter();
-    for i in matrix.iter(4) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-
-    let expected = [22, 75];
-    let mut iter = expected.iter();
-    for i in matrix.iter(5) {
-        let j = *iter.next().unwrap();
-        assert_eq!(i, j);
-    }
-    assert!(iter.next().is_none());
-}
diff --git a/src/librustc_data_structures/graph/implementation/mod.rs b/src/librustc_data_structures/graph/implementation/mod.rs
index baac7565868..c31321fa374 100644
--- a/src/librustc_data_structures/graph/implementation/mod.rs
+++ b/src/librustc_data_structures/graph/implementation/mod.rs
@@ -30,7 +30,7 @@
 //! the field `next_edge`). Each of those fields is an array that should
 //! be indexed by the direction (see the type `Direction`).
 
-use bitvec::BitArray;
+use bit_set::BitSet;
 use std::fmt::Debug;
 use std::usize;
 use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
@@ -266,7 +266,7 @@ impl<N: Debug, E: Debug> Graph<N, E> {
         direction: Direction,
         entry_node: NodeIndex,
     ) -> Vec<NodeIndex> {
-        let mut visited = BitArray::new(self.len_nodes());
+        let mut visited = BitSet::new_empty(self.len_nodes());
         let mut stack = vec![];
         let mut result = Vec::with_capacity(self.len_nodes());
         let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
@@ -348,7 +348,7 @@ where
 {
     graph: &'g Graph<N, E>,
     stack: Vec<NodeIndex>,
-    visited: BitArray<usize>,
+    visited: BitSet<usize>,
     direction: Direction,
 }
 
@@ -358,7 +358,7 @@ impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
         start_node: NodeIndex,
         direction: Direction,
     ) -> Self {
-        let mut visited = BitArray::new(graph.len_nodes());
+        let mut visited = BitSet::new_empty(graph.len_nodes());
         visited.insert(start_node.node_id());
         DepthFirstTraversal {
             graph,
diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
deleted file mode 100644
index 5ba8c150e1f..00000000000
--- a/src/librustc_data_structures/indexed_set.rs
+++ /dev/null
@@ -1,358 +0,0 @@
-// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-use array_vec::ArrayVec;
-use std::fmt;
-use std::mem;
-use std::slice;
-use bitvec::{bitwise, BitArray, BitIter, Intersect, Subtract, Union, Word, WORD_BITS};
-use indexed_vec::Idx;
-use rustc_serialize;
-
-/// This is implemented by all the index sets so that IdxSet::union() can be
-/// passed any type of index set.
-pub trait UnionIntoIdxSet<T: Idx> {
-    // Performs `other = other | self`.
-    fn union_into(&self, other: &mut IdxSet<T>) -> bool;
-}
-
-/// This is implemented by all the index sets so that IdxSet::subtract() can be
-/// passed any type of index set.
-pub trait SubtractFromIdxSet<T: Idx> {
-    // Performs `other = other - self`.
-    fn subtract_from(&self, other: &mut IdxSet<T>) -> bool;
-}
-
-/// 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(Clone, Eq, PartialEq)]
-pub struct IdxSet<T: Idx>(BitArray<T>);
-
-impl<T: Idx> rustc_serialize::Encodable for IdxSet<T> {
-    fn encode<E: rustc_serialize::Encoder>(&self, encoder: &mut E) -> Result<(), E::Error> {
-        self.0.encode(encoder)
-    }
-}
-
-impl<T: Idx> rustc_serialize::Decodable for IdxSet<T> {
-    fn decode<D: rustc_serialize::Decoder>(d: &mut D) -> Result<IdxSet<T>, D::Error> {
-        Ok(IdxSet(rustc_serialize::Decodable::decode(d)?))
-    }
-}
-
-impl<T: Idx> fmt::Debug for IdxSet<T> {
-    fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
-        w.debug_list()
-         .entries(self.iter())
-         .finish()
-    }
-}
-
-impl<T: Idx> IdxSet<T> {
-    /// Creates set holding no elements.
-    pub fn new_empty(domain_size: usize) -> Self {
-        IdxSet(BitArray::new_empty(domain_size))
-    }
-
-    /// Creates set holding every element whose index falls in range 0..domain_size.
-    pub fn new_filled(domain_size: usize) -> Self {
-        IdxSet(BitArray::new_filled(domain_size))
-    }
-
-    /// Duplicates as a hybrid set.
-    pub fn to_hybrid(&self) -> HybridIdxSet<T> {
-        // This domain_size may be slightly larger than the one specified
-        // upon creation, due to rounding up to a whole word. That's ok.
-        let domain_size = self.words().len() * WORD_BITS;
-
-        // Note: we currently don't bother trying to make a Sparse set.
-        HybridIdxSet::Dense(self.to_owned(), domain_size)
-    }
-
-    /// Removes all elements
-    pub fn clear(&mut self) {
-        self.0.clear();
-    }
-
-    /// Sets all elements up to `domain_size`
-    pub fn set_up_to(&mut self, domain_size: usize) {
-        self.0.set_up_to(domain_size);
-    }
-
-    /// Removes `elem` from the set `self`; returns true iff this changed `self`.
-    pub fn remove(&mut self, elem: &T) -> bool {
-        self.0.remove(*elem)
-    }
-
-    /// Adds `elem` to the set `self`; returns true iff this changed `self`.
-    pub fn add(&mut self, elem: &T) -> bool {
-        self.0.insert(*elem)
-    }
-
-    /// Returns true iff set `self` contains `elem`.
-    pub fn contains(&self, elem: &T) -> bool {
-        self.0.contains(*elem)
-    }
-
-    pub fn words(&self) -> &[Word] {
-        self.0.words()
-    }
-
-    pub fn words_mut(&mut self) -> &mut [Word] {
-        self.0.words_mut()
-    }
-
-    /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
-    /// don't have the same length.
-    pub fn overwrite(&mut self, other: &IdxSet<T>) {
-        self.words_mut().clone_from_slice(other.words());
-    }
-
-    /// Set `self = self | other` and return true if `self` changed
-    /// (i.e., if new bits were added).
-    pub fn union(&mut self, other: &impl UnionIntoIdxSet<T>) -> bool {
-        other.union_into(self)
-    }
-
-    /// Set `self = self - other` and return true if `self` changed.
-    /// (i.e., if any bits were removed).
-    pub fn subtract(&mut self, other: &impl SubtractFromIdxSet<T>) -> bool {
-        other.subtract_from(self)
-    }
-
-    /// Set `self = self & other` and return true if `self` changed.
-    /// (i.e., if any bits were removed).
-    pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
-        bitwise(self.words_mut(), other.words(), &Intersect)
-    }
-
-    pub fn iter(&self) -> BitIter<T> {
-        self.0.iter()
-    }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for IdxSet<T> {
-    fn union_into(&self, other: &mut IdxSet<T>) -> bool {
-        bitwise(other.words_mut(), self.words(), &Union)
-    }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
-    fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
-        bitwise(other.words_mut(), self.words(), &Subtract)
-    }
-}
-
-const SPARSE_MAX: usize = 8;
-
-/// A sparse index set with a maximum of SPARSE_MAX elements. Used by
-/// HybridIdxSet; do not use directly.
-///
-/// The elements are stored as an unsorted vector with no duplicates.
-#[derive(Clone, Debug)]
-pub struct SparseIdxSet<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
-
-impl<T: Idx> SparseIdxSet<T> {
-    fn new() -> Self {
-        SparseIdxSet(ArrayVec::new())
-    }
-
-    fn len(&self) -> usize {
-        self.0.len()
-    }
-
-    fn contains(&self, elem: &T) -> bool {
-        self.0.contains(elem)
-    }
-
-    fn add(&mut self, elem: &T) -> bool {
-        // Ensure there are no duplicates.
-        if self.0.contains(elem) {
-            false
-        } else {
-            self.0.push(*elem);
-            true
-        }
-    }
-
-    fn remove(&mut self, elem: &T) -> bool {
-        if let Some(i) = self.0.iter().position(|e| e == elem) {
-            // Swap the found element to the end, then pop it.
-            let len = self.0.len();
-            self.0.swap(i, len - 1);
-            self.0.pop();
-            true
-        } else {
-            false
-        }
-    }
-
-    fn to_dense(&self, domain_size: usize) -> IdxSet<T> {
-        let mut dense = IdxSet::new_empty(domain_size);
-        for elem in self.0.iter() {
-            dense.add(elem);
-        }
-        dense
-    }
-
-    fn iter(&self) -> slice::Iter<T> {
-        self.0.iter()
-    }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for SparseIdxSet<T> {
-    fn union_into(&self, other: &mut IdxSet<T>) -> bool {
-        let mut changed = false;
-        for elem in self.iter() {
-            changed |= other.add(&elem);
-        }
-        changed
-    }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for SparseIdxSet<T> {
-    fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
-        let mut changed = false;
-        for elem in self.iter() {
-            changed |= other.remove(&elem);
-        }
-        changed
-    }
-}
-
-/// 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 `domain_size`, and are cleared frequently.
-#[derive(Clone, Debug)]
-pub enum HybridIdxSet<T: Idx> {
-    Sparse(SparseIdxSet<T>, usize),
-    Dense(IdxSet<T>, usize),
-}
-
-impl<T: Idx> HybridIdxSet<T> {
-    pub fn new_empty(domain_size: usize) -> Self {
-        HybridIdxSet::Sparse(SparseIdxSet::new(), domain_size)
-    }
-
-    pub fn clear(&mut self) {
-        let domain_size = match *self {
-            HybridIdxSet::Sparse(_, size) => size,
-            HybridIdxSet::Dense(_, size) => size,
-        };
-        *self = HybridIdxSet::new_empty(domain_size);
-    }
-
-    /// Returns true iff set `self` contains `elem`.
-    pub fn contains(&self, elem: &T) -> bool {
-        match self {
-            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 {
-            HybridIdxSet::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
-                // The set is sparse and has space for `elem`.
-                sparse.add(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
-            }
-            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 = HybridIdxSet::Sparse(SparseIdxSet::new(), 0);
-                match mem::replace(self, dummy) {
-                    HybridIdxSet::Sparse(sparse, domain_size) => {
-                        let mut dense = sparse.to_dense(domain_size);
-                        let changed = dense.add(elem);
-                        assert!(changed);
-                        mem::replace(self, HybridIdxSet::Dense(dense, domain_size));
-                        changed
-                    }
-                    _ => panic!("impossible"),
-                }
-            }
-
-            HybridIdxSet::Dense(dense, _) => dense.add(elem),
-        }
-    }
-
-    /// Removes `elem` from the set `self`.
-    pub fn remove(&mut self, elem: &T) -> bool {
-        // Note: we currently don't bother going from Dense back to Sparse.
-        match self {
-            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) -> IdxSet<T> {
-        match self {
-            HybridIdxSet::Sparse(sparse, domain_size) => sparse.to_dense(domain_size),
-            HybridIdxSet::Dense(dense, _) => dense,
-        }
-    }
-
-    /// Iteration order is unspecified.
-    pub fn iter(&self) -> HybridIter<T> {
-        match self {
-            HybridIdxSet::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
-            HybridIdxSet::Dense(dense, _) => HybridIter::Dense(dense.iter()),
-        }
-    }
-}
-
-impl<T: Idx> UnionIntoIdxSet<T> for HybridIdxSet<T> {
-    fn union_into(&self, other: &mut IdxSet<T>) -> bool {
-        match self {
-            HybridIdxSet::Sparse(sparse, _) => sparse.union_into(other),
-            HybridIdxSet::Dense(dense, _) => dense.union_into(other),
-        }
-    }
-}
-
-impl<T: Idx> SubtractFromIdxSet<T> for HybridIdxSet<T> {
-    fn subtract_from(&self, other: &mut IdxSet<T>) -> bool {
-        match self {
-            HybridIdxSet::Sparse(sparse, _) => sparse.subtract_from(other),
-            HybridIdxSet::Dense(dense, _) => dense.subtract_from(other),
-        }
-    }
-}
-
-pub enum HybridIter<'a, T: Idx> {
-    Sparse(slice::Iter<'a, T>),
-    Dense(BitIter<'a, T>),
-}
-
-impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        match self {
-            HybridIter::Sparse(sparse) => sparse.next().map(|e| *e),
-            HybridIter::Dense(dense) => dense.next(),
-        }
-    }
-}
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 9435cb31842..1d7557953e9 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -62,12 +62,11 @@ pub use rustc_serialize::hex::ToHex;
 pub mod svh;
 pub mod array_vec;
 pub mod base_n;
-pub mod bitvec;
+pub mod bit_set;
 pub mod const_cstr;
 pub mod flock;
 pub mod fx;
 pub mod graph;
-pub mod indexed_set;
 pub mod indexed_vec;
 pub mod obligation_forest;
 pub mod owning_ref;
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 215c44dec69..c85d771a181 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -457,7 +457,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::IdxSet<I>
+impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::bit_set::BitSet<I>
 {
     fn hash_stable<W: StableHasherResult>(&self,
                                           ctx: &mut CTX,
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 2acc29acb0c..1512b30eead 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use bitvec::BitMatrix;
+use bit_set::BitMatrix;
 use fx::FxHashMap;
 use sync::Lock;
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
@@ -279,7 +279,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
             //
             // This same algorithm is used in `parents` below.
 
-            let mut candidates = closure.intersection(a.0, b.0); // (1)
+            let mut candidates = closure.intersect_rows(a.0, b.0); // (1)
             pare_down(&mut candidates, closure); // (2)
             candidates.reverse(); // (3a)
             pare_down(&mut candidates, closure); // (3b)
@@ -321,7 +321,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
         // with a slight tweak. In the case where `a R a`, we remove
         // that from the set of candidates.
         let ancestors = self.with_closure(|closure| {
-            let mut ancestors = closure.intersection(a.0, a.0);
+            let mut ancestors = closure.intersect_rows(a.0, a.0);
 
             // Remove anything that can reach `a`. If this is a
             // reflexive relation, this will include `a` itself.
@@ -366,10 +366,10 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
             changed = false;
             for edge in &self.edges {
                 // add an edge from S -> T
-                changed |= matrix.add(edge.source.0, edge.target.0);
+                changed |= matrix.insert(edge.source.0, edge.target.0);
 
                 // add all outgoing edges from T into S
-                changed |= matrix.merge(edge.target.0, edge.source.0);
+                changed |= matrix.union_rows(edge.target.0, edge.source.0);
             }
         }
         matrix
diff --git a/src/librustc_data_structures/work_queue.rs b/src/librustc_data_structures/work_queue.rs
index 0c8ec753a18..af9ed9306eb 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::IdxSet;
+use bit_set::BitSet;
 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: IdxSet<T>,
+    set: BitSet<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: IdxSet::new_filled(len),
+            set: BitSet::new_filled(len),
         }
     }
 
@@ -38,14 +38,14 @@ impl<T: Idx> WorkQueue<T> {
     pub fn with_none(len: usize) -> Self {
         WorkQueue {
             deque: VecDeque::with_capacity(len),
-            set: IdxSet::new_empty(len),
+            set: BitSet::new_empty(len),
         }
     }
 
     /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
     #[inline]
     pub fn insert(&mut self, element: T) -> bool {
-        if self.set.add(&element) {
+        if self.set.insert(element) {
             self.deque.push_back(element);
             true
         } else {
@@ -57,7 +57,7 @@ impl<T: Idx> WorkQueue<T> {
     #[inline]
     pub fn pop(&mut self) -> Option<T> {
         if let Some(element) = self.deque.pop_front() {
-            self.set.remove(&element);
+            self.set.remove(element);
             Some(element)
         } else {
             None