parameterize `BitVector` and `BitMatrix` by their index types

4 files changed, 63 insertions, 46 deletions

diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index ee903e49642..dec10416bcb 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -17,16 +17,18 @@ const WORD_BITS: usize = 128;
 
 /// A very simple BitVector type.
 #[derive(Clone, Debug, PartialEq)]
-pub struct BitVector {
+pub struct BitVector<C: Idx> {
     data: Vec<Word>,
+    marker: PhantomData<C>,
 }
 
-impl BitVector {
+impl<C: Idx> BitVector<C> {
     #[inline]
-    pub fn new(num_bits: usize) -> BitVector {
+    pub fn new(num_bits: usize) -> BitVector<C> {
         let num_words = words(num_bits);
         BitVector {
             data: vec![0; num_words],
+            marker: PhantomData,
         }
     }
 
@@ -42,14 +44,14 @@ impl BitVector {
     }
 
     #[inline]
-    pub fn contains(&self, bit: usize) -> bool {
+    pub fn contains(&self, bit: C) -> bool {
         let (word, mask) = word_mask(bit);
         (self.data[word] & mask) != 0
     }
 
     /// Returns true if the bit has changed.
     #[inline]
-    pub fn insert(&mut self, bit: usize) -> bool {
+    pub fn insert(&mut self, bit: C) -> bool {
         let (word, mask) = word_mask(bit);
         let data = &mut self.data[word];
         let value = *data;
@@ -60,7 +62,7 @@ impl BitVector {
 
     /// Returns true if the bit has changed.
     #[inline]
-    pub fn remove(&mut self, bit: usize) -> bool {
+    pub fn remove(&mut self, bit: C) -> bool {
         let (word, mask) = word_mask(bit);
         let data = &mut self.data[word];
         let value = *data;
@@ -70,7 +72,7 @@ impl BitVector {
     }
 
     #[inline]
-    pub fn merge(&mut self, all: &BitVector) -> bool {
+    pub fn merge(&mut self, all: &BitVector<C>) -> bool {
         assert!(self.data.len() == all.data.len());
         let mut changed = false;
         for (i, j) in self.data.iter_mut().zip(&all.data) {
@@ -84,7 +86,7 @@ impl BitVector {
     }
 
     #[inline]
-    pub fn grow(&mut self, num_bits: usize) {
+    pub fn grow(&mut self, num_bits: C) {
         let num_words = words(num_bits);
         if self.data.len() < num_words {
             self.data.resize(num_words, 0)
@@ -93,24 +95,26 @@ impl BitVector {
 
     /// Iterates over indexes of set bits in a sorted order
     #[inline]
-    pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
+    pub fn iter<'a>(&'a self) -> BitVectorIter<'a, C> {
         BitVectorIter {
             iter: self.data.iter(),
             current: 0,
             idx: 0,
+            marker: PhantomData,
         }
     }
 }
 
-pub struct BitVectorIter<'a> {
+pub struct BitVectorIter<'a, C: Idx> {
     iter: ::std::slice::Iter<'a, Word>,
     current: Word,
     idx: usize,
+    marker: PhantomData<C>
 }
 
-impl<'a> Iterator for BitVectorIter<'a> {
-    type Item = usize;
-    fn next(&mut self) -> Option<usize> {
+impl<'a, C: Idx> Iterator for BitVectorIter<'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 {
@@ -128,7 +132,7 @@ impl<'a> Iterator for BitVectorIter<'a> {
         self.current >>= offset;
         self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
         self.idx += offset + 1;
-        return Some(self.idx - 1);
+        return Some(C::new(self.idx - 1));
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
@@ -137,8 +141,8 @@ impl<'a> Iterator for BitVectorIter<'a> {
     }
 }
 
-impl FromIterator<bool> for BitVector {
-    fn from_iter<I>(iter: I) -> BitVector
+impl<C: Idx> FromIterator<bool> for BitVector<C> {
+    fn from_iter<I>(iter: I) -> BitVector<C>
     where
         I: IntoIterator<Item = bool>,
     {
@@ -150,10 +154,10 @@ impl FromIterator<bool> for BitVector {
         let mut bv = BitVector::new(len);
         for (idx, val) in iter.enumerate() {
             if idx > len {
-                bv.grow(idx);
+                bv.grow(C::new(idx));
             }
             if val {
-                bv.insert(idx);
+                bv.insert(C::new(idx));
             }
         }
 
@@ -165,25 +169,28 @@ impl FromIterator<bool> for BitVector {
 /// one gigantic bitvector. In other words, it is as if you have
 /// `rows` bitvectors, each of length `columns`.
 #[derive(Clone, Debug)]
-pub struct BitMatrix {
+pub struct BitMatrix<R: Idx, C: Idx> {
     columns: usize,
     vector: Vec<Word>,
+    phantom: PhantomData<(R, C)>,
 }
 
-impl BitMatrix {
+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 {
+    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);
         BitMatrix {
             columns,
             vector: vec![0; rows * words_per_row],
+            phantom: PhantomData,
         }
     }
 
     /// The range of bits for a given row.
-    fn range(&self, row: usize) -> (usize, usize) {
+    fn range(&self, row: R) -> (usize, usize) {
+        let row = row.index();
         let words_per_row = words(self.columns);
         let start = row * words_per_row;
         (start, start + words_per_row)
@@ -193,7 +200,7 @@ impl BitMatrix {
     /// `column` to the bitset for `row`.
     ///
     /// Returns true if this changed the matrix, and false otherwise.
-    pub fn add(&mut self, row: usize, column: usize) -> bool {
+    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[..];
@@ -207,7 +214,7 @@ impl BitMatrix {
     /// 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: usize, column: usize) -> bool {
+    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
@@ -217,7 +224,7 @@ impl BitMatrix {
     /// 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: usize, b: usize) -> Vec<usize> {
+    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);
@@ -228,7 +235,7 @@ impl BitMatrix {
                     break;
                 }
                 if v & 0x1 != 0 {
-                    result.push(base * WORD_BITS + bit);
+                    result.push(C::new(base * WORD_BITS + bit));
                 }
                 v >>= 1;
             }
@@ -243,7 +250,7 @@ impl BitMatrix {
     /// 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: usize, write: usize) -> bool {
+    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[..];
@@ -259,12 +266,13 @@ impl BitMatrix {
 
     /// Iterates through all the columns set to true in a given row of
     /// the matrix.
-    pub fn iter<'a>(&'a self, row: usize) -> BitVectorIter<'a> {
+    pub fn iter<'a>(&'a self, row: R) -> BitVectorIter<'a, C> {
         let (start, end) = self.range(row);
         BitVectorIter {
             iter: self.vector[start..end].iter(),
             current: 0,
             idx: 0,
+            marker: PhantomData,
         }
     }
 }
@@ -278,8 +286,7 @@ where
     C: Idx,
 {
     columns: usize,
-    vector: IndexVec<R, BitVector>,
-    marker: PhantomData<C>,
+    vector: IndexVec<R, BitVector<C>>,
 }
 
 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
@@ -288,7 +295,6 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         Self {
             columns,
             vector: IndexVec::new(),
-            marker: PhantomData,
         }
     }
 
@@ -300,7 +306,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
         let columns = self.columns;
         self.vector
             .ensure_contains_elem(row, || BitVector::new(columns));
-        self.vector[row].insert(column.index())
+        self.vector[row].insert(column)
     }
 
     /// Do the bits from `row` contain `column`? Put another way, is
@@ -308,7 +314,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
     /// if the matrix represents (transitive) reachability, can
     /// `row` reach `column`?
     pub fn contains(&self, row: R, column: C) -> bool {
-        self.vector.get(row).map_or(false, |r| r.contains(column.index()))
+        self.vector.get(row).map_or(false, |r| r.contains(column))
     }
 
     /// Add the bits from row `read` to the bits from row `write`,
@@ -331,7 +337,7 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
     }
 
     /// Merge a row, `from`, into the `into` row.
-    pub fn merge_into(&mut self, into: R, from: &BitVector) -> bool {
+    pub fn merge_into(&mut self, into: R, from: &BitVector<C>) -> bool {
         let columns = self.columns;
         self.vector
             .ensure_contains_elem(into, || BitVector::new(columns));
@@ -346,22 +352,27 @@ impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
     /// Iterates through all the columns set to true in a given row of
     /// the matrix.
     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
-        self.vector.get(row).into_iter().flat_map(|r| r.iter().map(|n| C::new(n)))
+        self.vector.get(row).into_iter().flat_map(|r| r.iter())
     }
 
     /// Iterates through each row and the accompanying bit set.
-    pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a BitVector)> + 'a {
+    pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a BitVector<C>)> + 'a {
         self.vector.iter_enumerated()
     }
+
+    pub fn row(&self, row: R) -> Option<&BitVector<C>> {
+        self.vector.get(row)
+    }
 }
 
 #[inline]
-fn words(elements: usize) -> usize {
-    (elements + WORD_BITS - 1) / WORD_BITS
+fn words<C: Idx>(elements: C) -> usize {
+    (elements.index() + WORD_BITS - 1) / WORD_BITS
 }
 
 #[inline]
-fn word_mask(index: usize) -> (usize, Word) {
+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)
diff --git a/src/librustc_data_structures/graph/implementation/mod.rs b/src/librustc_data_structures/graph/implementation/mod.rs
index e2b393071ff..dbfc09116bb 100644
--- a/src/librustc_data_structures/graph/implementation/mod.rs
+++ b/src/librustc_data_structures/graph/implementation/mod.rs
@@ -348,7 +348,7 @@ where
 {
     graph: &'g Graph<N, E>,
     stack: Vec<NodeIndex>,
-    visited: BitVector,
+    visited: BitVector<usize>,
     direction: Direction,
 }
 
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 08c518d5ba6..c358f2f852e 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -25,7 +25,13 @@ use rustc_serialize as serialize;
 /// (purpose: avoid mixing indexes for different bitvector domains.)
 pub trait Idx: Copy + 'static + Ord + Debug + Hash {
     fn new(idx: usize) -> Self;
+
     fn index(self) -> usize;
+
+    fn increment_by(&mut self, amount: usize) {
+        let v = self.index() + amount;
+        *self = Self::new(v);
+    }
 }
 
 impl Idx for usize {
@@ -504,8 +510,8 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
-    pub fn swap(&mut self, a: usize, b: usize) {
-        self.raw.swap(a, b)
+    pub fn swap(&mut self, a: I, b: I) {
+        self.raw.swap(a.index(), b.index())
     }
 
     #[inline]
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 6d63bc4436f..a8124fb7c5b 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -39,7 +39,7 @@ pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
     // are added with new elements. Perhaps better would be to ask the
     // user for a batch of edges to minimize this effect, but I
     // already wrote the code this way. :P -nmatsakis
-    closure: Lock<Option<BitMatrix>>,
+    closure: Lock<Option<BitMatrix<usize, usize>>>,
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)]
@@ -354,7 +354,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
     }
 
     fn with_closure<OP, R>(&self, op: OP) -> R
-        where OP: FnOnce(&BitMatrix) -> R
+        where OP: FnOnce(&BitMatrix<usize, usize>) -> R
     {
         let mut closure_cell = self.closure.borrow_mut();
         let mut closure = closure_cell.take();
@@ -366,7 +366,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
         result
     }
 
-    fn compute_closure(&self) -> BitMatrix {
+    fn compute_closure(&self) -> BitMatrix<usize, usize> {
         let mut matrix = BitMatrix::new(self.elements.len(),
                                         self.elements.len());
         let mut changed = true;
@@ -396,7 +396,7 @@ impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
-fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
+fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
     let mut i = 0;
     while i < candidates.len() {
         let candidate_i = candidates[i];