Remove bitslice.rs.

This requires the following changes.

- It moves parts of bitslice.rs into bitvec.rs: `bitwise()`,
  `BitwiseOperator`, `bits_to_string()`.

- It changes `IdxSet` to just be a wrapper around `BitArray`.

- It changes `BitArray` and `BitVec` to use `usize` words instead of
  `u128` words. (`BitSlice` and `IdxSet` already use `usize`.) Local
  profiling showed `usize` was better.

- It moves some operations from `IdxSet` into `BitArray`:
  `new_filled()`, `clear()`, `set_up_to()`, `trim_to()` (renamed
  `clear_above()`), `words()` and `words_mut()`, `encode()` and
  `decode(). The `IdxSet` operations now just call the `BitArray`
  operations.

- It replaces `BitArray`'s iterator implementation with `IdxSet`'s,
  because the latter is more concise. It also removes the buggy
  `size_hint` function from `BitArray`'s iterator, which counted the
  number of *words* rather than the number of *bits*. `IdxSet`'s
  iterator is now just a thin wrapper around `BitArray`'s iterator.

- It moves some unit tests from `indexed_set.rs` to `bitvec.rs`.

4 files changed, 221 insertions, 317 deletions

diff --git a/src/librustc_data_structures/bitslice.rs b/src/librustc_data_structures/bitslice.rs
deleted file mode 100644
index a63033c4365..00000000000
--- a/src/librustc_data_structures/bitslice.rs
+++ /dev/null
@@ -1,146 +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.
-
-// FIXME: merge with `bitvec`
-
-use std::mem;
-
-pub type Word = usize;
-
-/// `BitSlice` provides helper methods for treating a `[Word]`
-/// as a bitvector.
-pub trait BitSlice {
-    fn clear_bit(&mut self, idx: usize) -> bool;
-    fn set_bit(&mut self, idx: usize) -> bool;
-    fn get_bit(&self, idx: usize) -> bool;
-}
-
-impl BitSlice for [Word] {
-    /// Clears bit at `idx` to 0; returns true iff this changed `self.`
-    #[inline]
-    fn clear_bit(&mut self, idx: usize) -> bool {
-        let words = self;
-        debug!("clear_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
-        let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
-        debug!("word={} bit_in_word={} bit_mask=0x{:x}", word, bit_in_word, bit_mask);
-        let oldv = words[word];
-        let newv = oldv & !bit_mask;
-        words[word] = newv;
-        oldv != newv
-    }
-
-    /// Sets bit at `idx` to 1; returns true iff this changed `self.`
-    #[inline]
-    fn set_bit(&mut self, idx: usize) -> bool {
-        let words = self;
-        debug!("set_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
-        let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
-        debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
-        let oldv = words[word];
-        let newv = oldv | bit_mask;
-        words[word] = newv;
-        oldv != newv
-    }
-
-    /// Extracts value of bit at `idx` in `self`.
-    #[inline]
-    fn get_bit(&self, idx: usize) -> bool {
-        let words = self;
-        let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
-        (words[word] & bit_mask) != 0
-    }
-}
-
-struct BitLookup {
-    /// An index of the word holding the bit in original `[Word]` of query.
-    word: usize,
-    /// Index of the particular bit within the word holding the bit.
-    bit_in_word: usize,
-    /// Word with single 1-bit set corresponding to where the bit is located.
-    bit_mask: Word,
-}
-
-#[inline]
-fn bit_lookup(bit: usize) -> BitLookup {
-    let word_bits = mem::size_of::<Word>() * 8;
-    let word = bit / word_bits;
-    let bit_in_word = bit % word_bits;
-    let bit_mask = 1 << bit_in_word;
-    BitLookup { word, bit_in_word, bit_mask }
-}
-
-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..mem::size_of::<Word>() { // 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
-}
-
-#[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_elt, in_elt) in out_vec.iter_mut().zip(in_vec) {
-        let old_val = *out_elt;
-        let new_val = op.join(old_val, *in_elt);
-        *out_elt = new_val;
-        changed |= old_val != new_val;
-    }
-    changed
-}
-
-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;
-}
-
-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 }
-}
diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index acf33697f58..52cc347f8e7 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -9,15 +9,19 @@
 // except according to those terms.
 
 use indexed_vec::{Idx, IndexVec};
+use rustc_serialize;
+use std::iter;
 use std::marker::PhantomData;
+use std::slice;
 
-type Word = u128;
-const WORD_BITS: usize = 128;
+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, PartialEq)]
+#[derive(Clone, Debug, Eq, PartialEq)]
 pub struct BitArray<C: Idx> {
     data: Vec<Word>,
     marker: PhantomData<C>,
@@ -27,7 +31,7 @@ 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 = words(num_bits);
+        let num_words = num_words(num_bits);
         if self.data.len() <= num_words {
             self.data.resize(num_words + 1, 0)
         }
@@ -35,7 +39,12 @@ impl<C: Idx> BitArray<C> {
 
     #[inline]
     pub fn new(num_bits: usize) -> BitArray<C> {
-        let num_words = words(num_bits);
+        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,
@@ -43,12 +52,48 @@ impl<C: Idx> BitArray<C> {
     }
 
     #[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()
     }
@@ -88,7 +133,7 @@ impl<C: Idx> BitArray<C> {
     /// Sets all bits to true.
     pub fn insert_all(&mut self) {
         for data in &mut self.data {
-            *data = u128::max_value();
+            *data = !0;
         }
     }
 
@@ -117,53 +162,132 @@ impl<C: Idx> BitArray<C> {
         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 {
-            iter: self.data.iter(),
-            current: 0,
-            idx: 0,
+            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> {
-    iter: ::std::slice::Iter<'a, Word>,
-    current: Word,
-    idx: usize,
+    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> {
-        while self.current == 0 {
-            self.current = if let Some(&i) = self.iter.next() {
-                if i == 0 {
-                    self.idx += WORD_BITS;
-                    continue;
-                } else {
-                    self.idx = words(self.idx) * WORD_BITS;
-                    i
+        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))
                 }
-            } else {
-                return None;
             }
-        }
-        let offset = self.current.trailing_zeros() as usize;
-        self.current >>= offset;
-        self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
-        self.idx += offset + 1;
 
-        Some(C::new(self.idx - 1))
+            let (i, word) = self.iter.next()?;
+            self.cur = Some((*word, WORD_BITS * i));
+        }
     }
+}
 
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        let (_, upper) = self.iter.size_hint();
-        (0, upper)
+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.
@@ -218,7 +342,7 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
     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 = words(columns);
+        let words_per_row = num_words(columns);
         BitMatrix {
             columns,
             vector: vec![0; rows * words_per_row],
@@ -229,7 +353,7 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
     /// The range of bits for a given row.
     fn range(&self, row: R) -> (usize, usize) {
         let row = row.index();
-        let words_per_row = words(self.columns);
+        let words_per_row = num_words(self.columns);
         let start = row * words_per_row;
         (start, start + words_per_row)
     }
@@ -307,9 +431,8 @@ impl<R: Idx, C: Idx> BitMatrix<R, C> {
     pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
         let (start, end) = self.range(row);
         BitIter {
-            iter: self.vector[start..end].iter(),
-            current: 0,
-            idx: 0,
+            cur: None,
+            iter: self.vector[start..end].iter().enumerate(),
             marker: PhantomData,
         }
     }
@@ -418,7 +541,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 }
 
 #[inline]
-fn words<C: Idx>(elements: C) -> usize {
+fn num_words<C: Idx>(elements: C) -> usize {
     (elements.index() + WORD_BITS - 1) / WORD_BITS
 }
 
@@ -431,6 +554,46 @@ fn word_mask<C: Idx>(index: C) -> (usize, Word) {
 }
 
 #[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);
diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index 65fdf10a86d..be519e7bbde 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -10,12 +10,9 @@
 
 use array_vec::ArrayVec;
 use std::fmt;
-use std::iter;
-use std::marker::PhantomData;
 use std::mem;
 use std::slice;
-use bitslice::{BitSlice, Word};
-use bitslice::{bitwise, Union, Subtract, Intersect};
+use bitvec::{bitwise, BitArray, BitIter, Intersect, Subtract, Union, Word, WORD_BITS};
 use indexed_vec::Idx;
 use rustc_serialize;
 
@@ -40,39 +37,21 @@ pub trait SubtractFromIdxSet<T: Idx> {
 /// 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 IdxSet<T: Idx> {
-    _pd: PhantomData<fn(&T)>,
-    bits: Vec<Word>,
-}
-
-impl<T: Idx> Clone for IdxSet<T> {
-    fn clone(&self) -> Self {
-        IdxSet { _pd: PhantomData, bits: self.bits.clone() }
-    }
-}
+#[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.bits.encode(encoder)
+    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> {
-        let words: Vec<Word> = rustc_serialize::Decodable::decode(d)?;
-
-        Ok(IdxSet {
-            _pd: PhantomData,
-            bits: words,
-        })
+        Ok(IdxSet(rustc_serialize::Decodable::decode(d)?))
     }
 }
 
-const BITS_PER_WORD: usize = mem::size_of::<Word>() * 8;
-
 impl<T: Idx> fmt::Debug for IdxSet<T> {
     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
         w.debug_list()
@@ -82,31 +61,21 @@ impl<T: Idx> fmt::Debug for IdxSet<T> {
 }
 
 impl<T: Idx> IdxSet<T> {
-    fn new(init: Word, domain_size: usize) -> Self {
-        let num_words = (domain_size + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
-        IdxSet {
-            _pd: Default::default(),
-            bits: vec![init; num_words],
-        }
+    /// 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 {
-        let mut result = Self::new(!0, domain_size);
-        result.trim_to(domain_size);
-        result
-    }
-
-    /// Creates set holding no elements.
-    pub fn new_empty(domain_size: usize) -> Self {
-        Self::new(0, domain_size)
+        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.bits.len() * BITS_PER_WORD;
+        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)
@@ -114,60 +83,35 @@ impl<T: Idx> IdxSet<T> {
 
     /// Removes all elements
     pub fn clear(&mut self) {
-        for b in &mut self.bits {
-            *b = 0;
-        }
+        self.0.clear();
     }
 
     /// Sets all elements up to `domain_size`
     pub fn set_up_to(&mut self, domain_size: usize) {
-        for b in &mut self.bits {
-            *b = !0;
-        }
-        self.trim_to(domain_size);
-    }
-
-    /// Clear all elements above `domain_size`.
-    fn trim_to(&mut self, domain_size: usize) {
-        // `trim_block` is the first block where some bits have
-        // to be cleared.
-        let trim_block = domain_size / BITS_PER_WORD;
-
-        // all the blocks above it have to be completely cleared.
-        if trim_block < self.bits.len() {
-            for b in &mut self.bits[trim_block+1..] {
-                *b = 0;
-            }
-
-            // at that block, the `domain_size % BITS_PER_WORD` LSBs
-            // should remain.
-            let remaining_bits = domain_size % BITS_PER_WORD;
-            let mask = (1<<remaining_bits)-1;
-            self.bits[trim_block] &= mask;
-        }
+        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.bits.clear_bit(elem.index())
+        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.bits.set_bit(elem.index())
+        self.0.insert(*elem)
     }
 
     /// Returns true iff set `self` contains `elem`.
     pub fn contains(&self, elem: &T) -> bool {
-        self.bits.get_bit(elem.index())
+        self.0.contains(*elem)
     }
 
     pub fn words(&self) -> &[Word] {
-        &self.bits
+        self.0.words()
     }
 
     pub fn words_mut(&mut self) -> &mut [Word] {
-        &mut self.bits
+        self.0.words_mut()
     }
 
     /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
@@ -196,9 +140,7 @@ impl<T: Idx> IdxSet<T> {
 
     pub fn iter(&self) -> Iter<T> {
         Iter {
-            cur: None,
-            iter: self.words().iter().enumerate(),
-            _pd: PhantomData,
+            iter: self.0.iter()
         }
     }
 }
@@ -216,28 +158,14 @@ impl<T: Idx> SubtractFromIdxSet<T> for IdxSet<T> {
 }
 
 pub struct Iter<'a, T: Idx> {
-    cur: Option<(Word, usize)>,
-    iter: iter::Enumerate<slice::Iter<'a, Word>>,
-    _pd: PhantomData<fn(&T)>,
+    iter: BitIter<'a, T>
 }
 
 impl<'a, T: Idx> Iterator for Iter<'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 != BITS_PER_WORD {
-                    let bit = 1 << bit_pos;
-                    *word ^= bit;
-                    return Some(T::new(bit_pos + offset))
-                }
-            }
-
-            let (i, word) = self.iter.next()?;
-            self.cur = Some((*word, BITS_PER_WORD * i));
-        }
+        self.iter.next()
     }
 }
 
@@ -456,43 +384,3 @@ impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
         }
     }
 }
-
-#[test]
-fn test_trim_to() {
-    use std::cmp;
-
-    for i in 0..256 {
-        let mut idx_buf: IdxSet<usize> = IdxSet::new_filled(128);
-        idx_buf.trim_to(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![IdxSet::new_empty(128), IdxSet::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 = 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/lib.rs b/src/librustc_data_structures/lib.rs
index 7915650fd89..1fdcab5f7a2 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -63,7 +63,6 @@ pub use rustc_serialize::hex::ToHex;
 pub mod svh;
 pub mod array_vec;
 pub mod base_n;
-pub mod bitslice;
 pub mod bitvec;
 pub mod const_cstr;
 pub mod flock;