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.

4 files changed, 38 insertions, 40 deletions

diff --git a/src/librustc_mir/dataflow/impls/borrowed_locals.rs b/src/librustc_mir/dataflow/impls/borrowed_locals.rs
index c8c41c13b0f..266e8e2d949 100644
--- a/src/librustc_mir/dataflow/impls/borrowed_locals.rs
+++ b/src/librustc_mir/dataflow/impls/borrowed_locals.rs
@@ -43,7 +43,7 @@ impl<'a, 'tcx> BitDenotation for HaveBeenBorrowedLocals<'a, 'tcx> {
         self.mir.local_decls.len()
     }
 
-    fn start_block_effect(&self, _sets: &mut IdxSet<Local>) {
+    fn start_block_effect(&self, _sets: &mut BitSet<Local>) {
         // Nothing is borrowed on function entry
     }
 
@@ -58,7 +58,7 @@ impl<'a, 'tcx> BitDenotation for HaveBeenBorrowedLocals<'a, 'tcx> {
 
         // StorageDead invalidates all borrows and raw pointers to a local
         match stmt.kind {
-            StatementKind::StorageDead(l) => sets.kill(&l),
+            StatementKind::StorageDead(l) => sets.kill(l),
             _ => (),
         }
     }
@@ -72,7 +72,7 @@ impl<'a, 'tcx> BitDenotation for HaveBeenBorrowedLocals<'a, 'tcx> {
     }
 
     fn propagate_call_return(&self,
-                             _in_out: &mut IdxSet<Local>,
+                             _in_out: &mut BitSet<Local>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              _dest_place: &mir::Place) {
@@ -118,7 +118,7 @@ impl<'tcx, 'b, 'c> Visitor<'tcx> for BorrowedLocalsVisitor<'b, 'c> {
                     location: Location) {
         if let Rvalue::Ref(_, _, ref place) = *rvalue {
             if let Some(local) = find_local(place) {
-                self.sets.gen(&local);
+                self.sets.gen(local);
             }
         }
 
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 66f020faa87..541f4c7026c 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -20,9 +20,8 @@ use rustc::ty::TyCtxt;
 use rustc::ty::{RegionKind, RegionVid};
 use rustc::ty::RegionKind::ReScope;
 
-use rustc_data_structures::bitvec::{BitwiseOperator, Word};
+use rustc_data_structures::bit_set::{BitSet, BitwiseOperator, Word};
 use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::indexed_set::IdxSet;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::sync::Lrc;
 
@@ -227,7 +226,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
         self.borrow_set.borrows.len() * 2
     }
 
-    fn start_block_effect(&self, _entry_set: &mut IdxSet<BorrowIndex>) {
+    fn start_block_effect(&self, _entry_set: &mut BitSet<BorrowIndex>) {
         // no borrows of code region_scopes have been taken prior to
         // function execution, so this method has no effect on
         // `_sets`.
@@ -286,7 +285,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
                         debug!("Borrows::statement_effect_on_borrows \
                                 location: {:?} stmt: {:?} has empty region, killing {:?}",
                                location, stmt.kind, index);
-                        sets.kill(&index);
+                        sets.kill(*index);
                         return
                     } else {
                         debug!("Borrows::statement_effect_on_borrows location: {:?} stmt: {:?}",
@@ -296,7 +295,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
                     assert!(self.borrow_set.region_map.get(region).unwrap_or_else(|| {
                         panic!("could not find BorrowIndexs for region {:?}", region);
                     }).contains(&index));
-                    sets.gen(&index);
+                    sets.gen(*index);
 
                     // Issue #46746: Two-phase borrows handles
                     // stmts of form `Tmp = &mut Borrow` ...
@@ -308,7 +307,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
                             // e.g. `box (&mut _)`. Current
                             // conservative solution: force
                             // immediate activation here.
-                            sets.gen(&index);
+                            sets.gen(*index);
                         }
                     }
                 }
@@ -378,7 +377,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
                             if *scope != root_scope &&
                                 self.scope_tree.is_subscope_of(*scope, root_scope)
                             {
-                                sets.kill(&borrow_index);
+                                sets.kill(borrow_index);
                             }
                         }
                     }
@@ -399,7 +398,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for Borrows<'a, 'gcx, 'tcx> {
     }
 
     fn propagate_call_return(&self,
-                             _in_out: &mut IdxSet<BorrowIndex>,
+                             _in_out: &mut BitSet<BorrowIndex>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              _dest_place: &mir::Place) {
diff --git a/src/librustc_mir/dataflow/impls/mod.rs b/src/librustc_mir/dataflow/impls/mod.rs
index c8f70479852..6088f85c3c8 100644
--- a/src/librustc_mir/dataflow/impls/mod.rs
+++ b/src/librustc_mir/dataflow/impls/mod.rs
@@ -14,8 +14,7 @@
 
 use rustc::ty::TyCtxt;
 use rustc::mir::{self, Mir, Location};
-use rustc_data_structures::bitvec::{BitwiseOperator, Word};
-use rustc_data_structures::indexed_set::{IdxSet};
+use rustc_data_structures::bit_set::{BitSet, BitwiseOperator, Word};
 use rustc_data_structures::indexed_vec::Idx;
 
 use super::MoveDataParamEnv;
@@ -266,8 +265,8 @@ impl<'a, 'gcx, 'tcx> MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
                    state: DropFlagState)
     {
         match state {
-            DropFlagState::Absent => sets.kill(&path),
-            DropFlagState::Present => sets.gen(&path),
+            DropFlagState::Absent => sets.kill(path),
+            DropFlagState::Present => sets.gen(path),
         }
     }
 }
@@ -277,8 +276,8 @@ impl<'a, 'gcx, 'tcx> MaybeUninitializedPlaces<'a, 'gcx, 'tcx> {
                    state: DropFlagState)
     {
         match state {
-            DropFlagState::Absent => sets.gen(&path),
-            DropFlagState::Present => sets.kill(&path),
+            DropFlagState::Absent => sets.gen(path),
+            DropFlagState::Present => sets.kill(path),
         }
     }
 }
@@ -288,8 +287,8 @@ impl<'a, 'gcx, 'tcx> DefinitelyInitializedPlaces<'a, 'gcx, 'tcx> {
                    state: DropFlagState)
     {
         match state {
-            DropFlagState::Absent => sets.kill(&path),
-            DropFlagState::Present => sets.gen(&path),
+            DropFlagState::Absent => sets.kill(path),
+            DropFlagState::Present => sets.gen(path),
         }
     }
 }
@@ -301,12 +300,12 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
         self.move_data().move_paths.len()
     }
 
-    fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
+    fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
         drop_flag_effects_for_function_entry(
             self.tcx, self.mir, self.mdpe,
             |path, s| {
                 assert!(s == DropFlagState::Present);
-                entry_set.add(&path);
+                entry_set.insert(path);
             });
     }
 
@@ -333,7 +332,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
     }
 
     fn propagate_call_return(&self,
-                             in_out: &mut IdxSet<MovePathIndex>,
+                             in_out: &mut BitSet<MovePathIndex>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              dest_place: &mir::Place) {
@@ -341,7 +340,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeInitializedPlaces<'a, 'gcx, 'tcx> {
         // the bits for that dest_place to 1 (initialized).
         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
                               self.move_data().rev_lookup.find(dest_place),
-                              |mpi| { in_out.add(&mpi); });
+                              |mpi| { in_out.insert(mpi); });
     }
 }
 
@@ -353,7 +352,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeUninitializedPlaces<'a, 'gcx, 'tcx>
     }
 
     // sets on_entry bits for Arg places
-    fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
+    fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
         // set all bits to 1 (uninit) before gathering counterevidence
         entry_set.set_up_to(self.bits_per_block());
 
@@ -361,7 +360,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeUninitializedPlaces<'a, 'gcx, 'tcx>
             self.tcx, self.mir, self.mdpe,
             |path, s| {
                 assert!(s == DropFlagState::Present);
-                entry_set.remove(&path);
+                entry_set.remove(path);
             });
     }
 
@@ -388,7 +387,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeUninitializedPlaces<'a, 'gcx, 'tcx>
     }
 
     fn propagate_call_return(&self,
-                             in_out: &mut IdxSet<MovePathIndex>,
+                             in_out: &mut BitSet<MovePathIndex>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              dest_place: &mir::Place) {
@@ -396,7 +395,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for MaybeUninitializedPlaces<'a, 'gcx, 'tcx>
         // the bits for that dest_place to 0 (initialized).
         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
                               self.move_data().rev_lookup.find(dest_place),
-                              |mpi| { in_out.remove(&mpi); });
+                              |mpi| { in_out.remove(mpi); });
     }
 }
 
@@ -408,14 +407,14 @@ impl<'a, 'gcx, 'tcx> BitDenotation for DefinitelyInitializedPlaces<'a, 'gcx, 'tc
     }
 
     // sets on_entry bits for Arg places
-    fn start_block_effect(&self, entry_set: &mut IdxSet<MovePathIndex>) {
+    fn start_block_effect(&self, entry_set: &mut BitSet<MovePathIndex>) {
         entry_set.clear();
 
         drop_flag_effects_for_function_entry(
             self.tcx, self.mir, self.mdpe,
             |path, s| {
                 assert!(s == DropFlagState::Present);
-                entry_set.add(&path);
+                entry_set.insert(path);
             });
     }
 
@@ -442,7 +441,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for DefinitelyInitializedPlaces<'a, 'gcx, 'tc
     }
 
     fn propagate_call_return(&self,
-                             in_out: &mut IdxSet<MovePathIndex>,
+                             in_out: &mut BitSet<MovePathIndex>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              dest_place: &mir::Place) {
@@ -450,7 +449,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for DefinitelyInitializedPlaces<'a, 'gcx, 'tc
         // the bits for that dest_place to 1 (initialized).
         on_lookup_result_bits(self.tcx, self.mir, self.move_data(),
                               self.move_data().rev_lookup.find(dest_place),
-                              |mpi| { in_out.add(&mpi); });
+                              |mpi| { in_out.insert(mpi); });
     }
 }
 
@@ -461,9 +460,9 @@ impl<'a, 'gcx, 'tcx> BitDenotation for EverInitializedPlaces<'a, 'gcx, 'tcx> {
         self.move_data().inits.len()
     }
 
-    fn start_block_effect(&self, entry_set: &mut IdxSet<InitIndex>) {
+    fn start_block_effect(&self, entry_set: &mut BitSet<InitIndex>) {
         for arg_init in 0..self.mir.arg_count {
-            entry_set.add(&InitIndex::new(arg_init));
+            entry_set.insert(InitIndex::new(arg_init));
         }
     }
 
@@ -531,7 +530,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for EverInitializedPlaces<'a, 'gcx, 'tcx> {
     }
 
     fn propagate_call_return(&self,
-                             in_out: &mut IdxSet<InitIndex>,
+                             in_out: &mut BitSet<InitIndex>,
                              call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              _dest_place: &mir::Place) {
@@ -545,7 +544,7 @@ impl<'a, 'gcx, 'tcx> BitDenotation for EverInitializedPlaces<'a, 'gcx, 'tcx> {
         };
         for init_index in &init_loc_map[call_loc] {
             assert!(init_index.index() < bits_per_block);
-            in_out.add(init_index);
+            in_out.insert(*init_index);
         }
     }
 }
diff --git a/src/librustc_mir/dataflow/impls/storage_liveness.rs b/src/librustc_mir/dataflow/impls/storage_liveness.rs
index 29548051a4d..e6229725fe8 100644
--- a/src/librustc_mir/dataflow/impls/storage_liveness.rs
+++ b/src/librustc_mir/dataflow/impls/storage_liveness.rs
@@ -36,7 +36,7 @@ impl<'a, 'tcx> BitDenotation for MaybeStorageLive<'a, 'tcx> {
         self.mir.local_decls.len()
     }
 
-    fn start_block_effect(&self, _sets: &mut IdxSet<Local>) {
+    fn start_block_effect(&self, _sets: &mut BitSet<Local>) {
         // Nothing is live on function entry
     }
 
@@ -46,8 +46,8 @@ impl<'a, 'tcx> BitDenotation for MaybeStorageLive<'a, 'tcx> {
         let stmt = &self.mir[loc.block].statements[loc.statement_index];
 
         match stmt.kind {
-            StatementKind::StorageLive(l) => sets.gen(&l),
-            StatementKind::StorageDead(l) => sets.kill(&l),
+            StatementKind::StorageLive(l) => sets.gen(l),
+            StatementKind::StorageDead(l) => sets.kill(l),
             _ => (),
         }
     }
@@ -59,7 +59,7 @@ impl<'a, 'tcx> BitDenotation for MaybeStorageLive<'a, 'tcx> {
     }
 
     fn propagate_call_return(&self,
-                             _in_out: &mut IdxSet<Local>,
+                             _in_out: &mut BitSet<Local>,
                              _call_bb: mir::BasicBlock,
                              _dest_bb: mir::BasicBlock,
                              _dest_place: &mir::Place) {