diff options
| author | Nicholas Nethercote <nnethercote@mozilla.com> | 2018-09-14 15:07:25 +1000 |
|---|---|---|
| committer | Nicholas Nethercote <nnethercote@mozilla.com> | 2018-09-18 07:08:09 +1000 |
| commit | 266e2d3d69f61692a4080ff345d05c49d9f3c855 (patch) | |
| tree | c9d316b9999b4ffdd18e4d5a1bf2512edaf20087 | |
| parent | 8a2dec6e583bc6425a91b277bdc6c602088845f1 (diff) | |
| download | rust-266e2d3d69f61692a4080ff345d05c49d9f3c855.tar.gz rust-266e2d3d69f61692a4080ff345d05c49d9f3c855.zip | |
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.
40 files changed, 1276 insertions, 1377 deletions
diff --git a/src/librustc/mir/traversal.rs b/src/librustc/mir/traversal.rs index c919793fe3e..db1bc3e7519 100644 --- a/src/librustc/mir/traversal.rs +++ b/src/librustc/mir/traversal.rs @@ -8,7 +8,7 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use super::*; @@ -32,7 +32,7 @@ use super::*; #[derive(Clone)] pub struct Preorder<'a, 'tcx: 'a> { mir: &'a Mir<'tcx>, - visited: BitArray<BasicBlock>, + visited: BitSet<BasicBlock>, worklist: Vec<BasicBlock>, } @@ -42,7 +42,7 @@ impl<'a, 'tcx> Preorder<'a, 'tcx> { Preorder { mir, - visited: BitArray::new(mir.basic_blocks().len()), + visited: BitSet::new_empty(mir.basic_blocks().len()), worklist, } } @@ -104,7 +104,7 @@ impl<'a, 'tcx> ExactSizeIterator for Preorder<'a, 'tcx> {} /// A Postorder traversal of this graph is `D B C A` or `D C B A` pub struct Postorder<'a, 'tcx: 'a> { mir: &'a Mir<'tcx>, - visited: BitArray<BasicBlock>, + visited: BitSet<BasicBlock>, visit_stack: Vec<(BasicBlock, Successors<'a>)> } @@ -112,7 +112,7 @@ impl<'a, 'tcx> Postorder<'a, 'tcx> { pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> { let mut po = Postorder { mir, - visited: BitArray::new(mir.basic_blocks().len()), + visited: BitSet::new_empty(mir.basic_blocks().len()), visit_stack: Vec::new() }; diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs index 232ef108537..85e7368bfdd 100644 --- a/src/librustc/traits/select.rs +++ b/src/librustc/traits/select.rs @@ -44,8 +44,8 @@ use ty::relate::TypeRelation; use middle::lang_items; use mir::interpret::{GlobalId}; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::sync::Lock; -use rustc_data_structures::bitvec::BitArray; use std::iter; use std::cmp; use std::fmt; @@ -3069,7 +3069,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> { } else { return Err(Unimplemented); }; - let mut ty_params = BitArray::new(substs_a.types().count()); + let mut ty_params = BitSet::new_empty(substs_a.types().count()); let mut found = false; for ty in field.walk() { if let ty::Param(p) = ty.sty { diff --git a/src/librustc/ty/query/mod.rs b/src/librustc/ty/query/mod.rs index f0ca168e9e4..79c7e517273 100644 --- a/src/librustc/ty/query/mod.rs +++ b/src/librustc/ty/query/mod.rs @@ -49,14 +49,14 @@ use util::nodemap::{DefIdSet, DefIdMap, ItemLocalSet}; use util::common::{ErrorReported}; use util::profiling::ProfileCategory::*; -use rustc_data_structures::indexed_set::IdxSet; -use rustc_target::spec::PanicStrategy; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::IndexVec; use rustc_data_structures::fx::{FxHashMap, FxHashSet}; use rustc_data_structures::stable_hasher::StableVec; +use rustc_data_structures::sync::Lrc; +use rustc_target::spec::PanicStrategy; use std::ops::Deref; -use rustc_data_structures::sync::Lrc; use std::sync::Arc; use syntax_pos::{Span, DUMMY_SP}; use syntax_pos::symbol::InternedString; @@ -208,7 +208,7 @@ define_queries! { <'tcx> /// Maps DefId's that have an associated Mir to the result /// of the MIR qualify_consts pass. The actual meaning of /// the value isn't known except to the pass itself. - [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Lrc<IdxSet<mir::Local>>), + [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Lrc<BitSet<mir::Local>>), /// Fetch the MIR for a given def-id right after it's built - this includes /// unreachable code. diff --git a/src/librustc_codegen_llvm/debuginfo/create_scope_map.rs b/src/librustc_codegen_llvm/debuginfo/create_scope_map.rs index a76f1d50fa7..0484837a48d 100644 --- a/src/librustc_codegen_llvm/debuginfo/create_scope_map.rs +++ b/src/librustc_codegen_llvm/debuginfo/create_scope_map.rs @@ -21,7 +21,7 @@ use libc::c_uint; use syntax_pos::Pos; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use syntax_pos::BytePos; @@ -64,7 +64,7 @@ pub fn create_mir_scopes( }; // Find all the scopes with variables defined in them. - let mut has_variables = BitArray::new(mir.source_scopes.len()); + let mut has_variables = BitSet::new_empty(mir.source_scopes.len()); for var in mir.vars_iter() { let decl = &mir.local_decls[var]; has_variables.insert(decl.visibility_scope); @@ -81,7 +81,7 @@ pub fn create_mir_scopes( fn make_mir_scope(cx: &CodegenCx<'ll, '_>, mir: &Mir, - has_variables: &BitArray<SourceScope>, + has_variables: &BitSet<SourceScope>, debug_context: &FunctionDebugContextData<'ll>, scope: SourceScope, scopes: &mut IndexVec<SourceScope, MirDebugScope<'ll>>) { diff --git a/src/librustc_codegen_llvm/mir/analyze.rs b/src/librustc_codegen_llvm/mir/analyze.rs index 0206744eb2b..c3e3785a724 100644 --- a/src/librustc_codegen_llvm/mir/analyze.rs +++ b/src/librustc_codegen_llvm/mir/analyze.rs @@ -11,7 +11,7 @@ //! An analysis to determine which locals require allocas and //! which do not. -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::graph::dominators::Dominators; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use rustc::mir::{self, Location, TerminatorKind}; @@ -22,7 +22,7 @@ use rustc::ty::layout::LayoutOf; use type_of::LayoutLlvmExt; use super::FunctionCx; -pub fn non_ssa_locals(fx: &FunctionCx<'a, 'll, 'tcx>) -> BitArray<mir::Local> { +pub fn non_ssa_locals(fx: &FunctionCx<'a, 'll, 'tcx>) -> BitSet<mir::Local> { let mir = fx.mir; let mut analyzer = LocalAnalyzer::new(fx); @@ -54,7 +54,7 @@ pub fn non_ssa_locals(fx: &FunctionCx<'a, 'll, 'tcx>) -> BitArray<mir::Local> { struct LocalAnalyzer<'mir, 'a: 'mir, 'll: 'a, 'tcx: 'll> { fx: &'mir FunctionCx<'a, 'll, 'tcx>, dominators: Dominators<mir::BasicBlock>, - non_ssa_locals: BitArray<mir::Local>, + non_ssa_locals: BitSet<mir::Local>, // The location of the first visited direct assignment to each // local, or an invalid location (out of bounds `block` index). first_assignment: IndexVec<mir::Local, Location> @@ -67,7 +67,7 @@ impl LocalAnalyzer<'mir, 'a, 'll, 'tcx> { let mut analyzer = LocalAnalyzer { fx, dominators: fx.mir.dominators(), - non_ssa_locals: BitArray::new(fx.mir.local_decls.len()), + non_ssa_locals: BitSet::new_empty(fx.mir.local_decls.len()), first_assignment: IndexVec::from_elem(invalid_location, &fx.mir.local_decls) }; diff --git a/src/librustc_codegen_llvm/mir/mod.rs b/src/librustc_codegen_llvm/mir/mod.rs index 258fe643c30..c61a326e7c8 100644 --- a/src/librustc_codegen_llvm/mir/mod.rs +++ b/src/librustc_codegen_llvm/mir/mod.rs @@ -31,7 +31,7 @@ use syntax::symbol::keywords; use std::iter; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::IndexVec; pub use self::constant::codegen_static_initializer; @@ -341,7 +341,7 @@ pub fn codegen_mir( debuginfo::start_emitting_source_locations(&fx.debug_context); let rpo = traversal::reverse_postorder(&mir); - let mut visited = BitArray::new(mir.basic_blocks().len()); + let mut visited = BitSet::new_empty(mir.basic_blocks().len()); // Codegen the body of each block using reverse postorder for (bb, _) in rpo { @@ -435,7 +435,7 @@ fn arg_local_refs( bx: &Builder<'a, 'll, 'tcx>, fx: &FunctionCx<'a, 'll, 'tcx>, scopes: &IndexVec<mir::SourceScope, debuginfo::MirDebugScope<'ll>>, - memory_locals: &BitArray<mir::Local>, + memory_locals: &BitSet<mir::Local>, ) -> Vec<LocalRef<'ll, 'tcx>> { let mir = fx.mir; let tcx = bx.tcx(); 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 diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs index 87a32b5a53e..d2285e8cbf1 100644 --- a/src/librustc_metadata/cstore_impl.rs +++ b/src/librustc_metadata/cstore_impl.rs @@ -42,7 +42,7 @@ use syntax::edition::Edition; use syntax::parse::source_file_to_stream; use syntax::symbol::Symbol; use syntax_pos::{Span, NO_EXPANSION, FileName}; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; use rustc::hir; macro_rules! provide { @@ -141,7 +141,7 @@ provide! { <'tcx> tcx, def_id, other, cdata, mir } mir_const_qualif => { - (cdata.mir_const_qualif(def_id.index), Lrc::new(IdxSet::new_empty(0))) + (cdata.mir_const_qualif(def_id.index), Lrc::new(BitSet::new_empty(0))) } fn_sig => { cdata.fn_sig(def_id.index, tcx) } inherent_impls => { Lrc::new(cdata.get_inherent_implementations_for_type(def_id.index)) } diff --git a/src/librustc_mir/borrow_check/borrow_set.rs b/src/librustc_mir/borrow_check/borrow_set.rs index 8ddcfa05432..bb70b4b76c2 100644 --- a/src/librustc_mir/borrow_check/borrow_set.rs +++ b/src/librustc_mir/borrow_check/borrow_set.rs @@ -17,7 +17,7 @@ use rustc::mir::{self, Location, Mir, Place, Local}; use rustc::ty::{Region, TyCtxt}; use rustc::util::nodemap::{FxHashMap, FxHashSet}; use rustc_data_structures::indexed_vec::IndexVec; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use std::fmt; use std::hash::Hash; use std::ops::Index; @@ -102,7 +102,7 @@ impl<'tcx> fmt::Display for BorrowData<'tcx> { crate enum LocalsStateAtExit { AllAreInvalidated, - SomeAreInvalidated { has_storage_dead_or_moved: BitArray<Local> } + SomeAreInvalidated { has_storage_dead_or_moved: BitSet<Local> } } impl LocalsStateAtExit { @@ -111,7 +111,7 @@ impl LocalsStateAtExit { mir: &Mir<'tcx>, move_data: &MoveData<'tcx> ) -> Self { - struct HasStorageDead(BitArray<Local>); + struct HasStorageDead(BitSet<Local>); impl<'tcx> Visitor<'tcx> for HasStorageDead { fn visit_local(&mut self, local: &Local, ctx: PlaceContext<'tcx>, _: Location) { @@ -124,7 +124,7 @@ impl LocalsStateAtExit { if locals_are_invalidated_at_exit { LocalsStateAtExit::AllAreInvalidated } else { - let mut has_storage_dead = HasStorageDead(BitArray::new(mir.local_decls.len())); + let mut has_storage_dead = HasStorageDead(BitSet::new_empty(mir.local_decls.len())); has_storage_dead.visit_mir(mir); let mut has_storage_dead_or_moved = has_storage_dead.0; for move_out in &move_data.moves { diff --git a/src/librustc_mir/borrow_check/flows.rs b/src/librustc_mir/borrow_check/flows.rs index a4900ab57f5..16bb1ef78dc 100644 --- a/src/librustc_mir/borrow_check/flows.rs +++ b/src/librustc_mir/borrow_check/flows.rs @@ -15,7 +15,7 @@ use rustc::mir::{BasicBlock, Location}; use rustc::ty::RegionVid; -use rustc_data_structures::bitvec::BitIter; +use rustc_data_structures::bit_set::BitIter; use borrow_check::location::LocationIndex; diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs index 3c694fe7b4e..521e7ade00e 100644 --- a/src/librustc_mir/borrow_check/mod.rs +++ b/src/librustc_mir/borrow_check/mod.rs @@ -26,9 +26,9 @@ use rustc::ty::query::Providers; use rustc::ty::{self, ParamEnv, TyCtxt, Ty}; use rustc_errors::{Applicability, Diagnostic, DiagnosticBuilder, Level}; -use rustc_data_structures::graph::dominators::Dominators; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::fx::FxHashSet; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::graph::dominators::Dominators; use rustc_data_structures::indexed_vec::Idx; use smallvec::SmallVec; @@ -167,7 +167,7 @@ fn do_mir_borrowck<'a, 'gcx, 'tcx>( _ => Some(tcx.hir.body_owned_by(id)), }; - let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len()); + let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); let mut flow_inits = FlowAtLocation::new(do_dataflow( tcx, mir, @@ -1595,7 +1595,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> { // Check if any of the initializiations of `local` have happened yet: let mpi = self.move_data.rev_lookup.find_local(local); let init_indices = &self.move_data.init_path_map[mpi]; - let first_init_index = init_indices.iter().find(|ii| flow_state.ever_inits.contains(ii)); + let first_init_index = init_indices.iter().find(|&ii| flow_state.ever_inits.contains(*ii)); if let Some(&init_index) = first_init_index { // And, if so, report an error. let init = &self.move_data.inits[init_index]; @@ -1653,7 +1653,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> { debug!("check_if_full_path_is_moved place: {:?}", place_span.0); match self.move_path_closest_to(place_span.0) { Ok(mpi) => { - if maybe_uninits.contains(&mpi) { + if maybe_uninits.contains(mpi) { self.report_use_of_moved_or_uninitialized( context, desired_action, @@ -1969,7 +1969,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> { // keyword, since the mutation may be a possible reassignment. let mpi = self.move_data.rev_lookup.find_local(*local); let ii = &self.move_data.init_path_map[mpi]; - for index in ii { + for &index in ii { if flow_state.ever_inits.contains(index) { self.used_mut.insert(*local); break; diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs index 214628600b3..d1713a520a7 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -26,8 +26,8 @@ use rustc::mir::{ }; use rustc::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable}; use rustc::util::common; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::graph::scc::Sccs; -use rustc_data_structures::indexed_set::IdxSet; use rustc_data_structures::indexed_vec::IndexVec; use rustc_errors::{DiagnosticBuilder, Diagnostic}; @@ -477,7 +477,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { // SCC. For each SCC, we visit its successors and compute // their values, then we union all those values to get our // own. - let visited = &mut IdxSet::new_empty(self.constraint_sccs.num_sccs()); + let visited = &mut BitSet::new_empty(self.constraint_sccs.num_sccs()); for scc_index in self.constraint_sccs.all_sccs() { self.propagate_constraint_sccs_if_new(scc_index, visited); } @@ -487,9 +487,9 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn propagate_constraint_sccs_if_new( &mut self, scc_a: ConstraintSccIndex, - visited: &mut IdxSet<ConstraintSccIndex>, + visited: &mut BitSet<ConstraintSccIndex>, ) { - if visited.add(&scc_a) { + if visited.insert(scc_a) { self.propagate_constraint_sccs_new(scc_a, visited); } } @@ -497,7 +497,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { fn propagate_constraint_sccs_new( &mut self, scc_a: ConstraintSccIndex, - visited: &mut IdxSet<ConstraintSccIndex>, + visited: &mut BitSet<ConstraintSccIndex>, ) { let constraint_sccs = self.constraint_sccs.clone(); diff --git a/src/librustc_mir/borrow_check/nll/region_infer/values.rs b/src/librustc_mir/borrow_check/nll/region_infer/values.rs index 3dafab2f5a9..618bf99c7c0 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs @@ -10,7 +10,7 @@ use rustc::mir::{BasicBlock, Location, Mir}; use rustc::ty::{self, RegionVid}; -use rustc_data_structures::bitvec::{BitArray, SparseBitMatrix}; +use rustc_data_structures::bit_set::{BitSet, SparseBitMatrix}; use rustc_data_structures::indexed_vec::Idx; use rustc_data_structures::indexed_vec::IndexVec; use std::fmt::Debug; @@ -179,19 +179,19 @@ impl<N: Idx> LivenessValues<N> { crate fn add_element(&mut self, row: N, location: Location) -> bool { debug!("LivenessValues::add(r={:?}, location={:?})", row, location); let index = self.elements.point_from_location(location); - self.points.add(row, index) + self.points.insert(row, index) } /// Adds all the elements in the given bit array into the given /// region. Returns true if any of them are newly added. - crate fn add_elements(&mut self, row: N, locations: &BitArray<PointIndex>) -> bool { + crate fn add_elements(&mut self, row: N, locations: &BitSet<PointIndex>) -> bool { debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations); - self.points.merge_into(row, locations) + self.points.union_into_row(row, locations) } /// Adds all the control-flow points to the values for `r`. crate fn add_all_points(&mut self, row: N) { - self.points.add_all(row); + self.points.insert_all_into_row(row); } /// True if the region `r` contains the given element. @@ -270,15 +270,15 @@ impl<N: Idx> RegionValues<N> { /// Adds all the control-flow points to the values for `r`. crate fn add_all_points(&mut self, r: N) { - self.points.add_all(r); + self.points.insert_all_into_row(r); } /// Add all elements in `r_from` to `r_to` (because e.g. `r_to: /// r_from`). crate fn add_region(&mut self, r_to: N, r_from: N) -> bool { - self.points.merge(r_from, r_to) - | self.free_regions.merge(r_from, r_to) - | self.placeholders.merge(r_from, r_to) + self.points.union_rows(r_from, r_to) + | self.free_regions.union_rows(r_from, r_to) + | self.placeholders.union_rows(r_from, r_to) } /// True if the region `r` contains the given element. @@ -291,7 +291,7 @@ impl<N: Idx> RegionValues<N> { /// the region `to` in `self`. crate fn merge_liveness<M: Idx>(&mut self, to: N, from: M, values: &LivenessValues<M>) { if let Some(set) = values.points.row(from) { - self.points.merge_into(to, set); + self.points.union_into_row(to, set); } } @@ -300,7 +300,7 @@ impl<N: Idx> RegionValues<N> { crate fn contains_points(&self, sup_region: N, sub_region: N) -> bool { if let Some(sub_row) = self.points.row(sub_region) { if let Some(sup_row) = self.points.row(sup_region) { - sup_row.contains_all(sub_row) + sup_row.superset(sub_row) } else { // sup row is empty, so sub row must be empty sub_row.is_empty() @@ -378,7 +378,7 @@ crate trait ToElementIndex: Debug + Copy { impl ToElementIndex for Location { fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { let index = values.elements.point_from_location(self); - values.points.add(row, index) + values.points.insert(row, index) } fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { @@ -389,7 +389,7 @@ impl ToElementIndex for Location { impl ToElementIndex for RegionVid { fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { - values.free_regions.add(row, self) + values.free_regions.insert(row, self) } fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { @@ -400,7 +400,7 @@ impl ToElementIndex for RegionVid { impl ToElementIndex for ty::UniverseIndex { fn add_to_row<N: Idx>(self, values: &mut RegionValues<N>, row: N) -> bool { let index = PlaceholderIndex::new(self.as_usize() - 1); - values.placeholders.add(row, index) + values.placeholders.insert(row, index) } fn contained_in_row<N: Idx>(self, values: &RegionValues<N>, row: N) -> bool { diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs index 79589ce9733..b6410f7de3d 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs @@ -22,7 +22,7 @@ use rustc::traits::query::dropck_outlives::DropckOutlivesResult; use rustc::traits::query::type_op::outlives::DropckOutlives; use rustc::traits::query::type_op::TypeOp; use rustc::ty::{Ty, TypeFoldable}; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::fx::FxHashMap; use std::rc::Rc; use util::liveness::LiveVariableMap; @@ -121,16 +121,16 @@ where cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>, /// Set of points that define the current local. - defs: BitArray<PointIndex>, + defs: BitSet<PointIndex>, /// Points where the current variable is "use live" -- meaning /// that there is a future "full use" that may use its value. - use_live_at: BitArray<PointIndex>, + use_live_at: BitSet<PointIndex>, /// Points where the current variable is "drop live" -- meaning /// that there is no future "full use" that may use its value, but /// there is a future drop. - drop_live_at: BitArray<PointIndex>, + drop_live_at: BitSet<PointIndex>, /// Locations where drops may occur. drop_locations: Vec<Location>, @@ -144,9 +144,9 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { let num_points = cx.elements.num_points(); LivenessResults { cx, - defs: BitArray::new(num_points), - use_live_at: BitArray::new(num_points), - drop_live_at: BitArray::new(num_points), + defs: BitSet::new_empty(num_points), + use_live_at: BitSet::new_empty(num_points), + drop_live_at: BitSet::new_empty(num_points), drop_locations: vec![], stack: vec![], } @@ -448,7 +448,7 @@ impl LivenessContext<'_, '_, '_, '_, 'tcx> { fn add_use_live_facts_for( &mut self, value: impl TypeFoldable<'tcx>, - live_at: &BitArray<PointIndex>, + live_at: &BitSet<PointIndex>, ) { debug!("add_use_live_facts_for(value={:?})", value); @@ -465,7 +465,7 @@ impl LivenessContext<'_, '_, '_, '_, 'tcx> { dropped_local: Local, dropped_ty: Ty<'tcx>, drop_locations: &[Location], - live_at: &BitArray<PointIndex>, + live_at: &BitSet<PointIndex>, ) { debug!( "add_drop_live_constraint(\ @@ -508,7 +508,7 @@ impl LivenessContext<'_, '_, '_, '_, 'tcx> { elements: &RegionValueElements, typeck: &mut TypeChecker<'_, '_, 'tcx>, value: impl TypeFoldable<'tcx>, - live_at: &BitArray<PointIndex>, + live_at: &BitSet<PointIndex>, ) { debug!("make_all_regions_live(value={:?})", value); debug!( diff --git a/src/librustc_mir/build/matches/mod.rs b/src/librustc_mir/build/matches/mod.rs index cef1fb77e5c..49c4ed874bb 100644 --- a/src/librustc_mir/build/matches/mod.rs +++ b/src/librustc_mir/build/matches/mod.rs @@ -21,7 +21,7 @@ use hair::*; use rustc::hir; use rustc::mir::*; use rustc::ty::{self, CanonicalTy, Ty}; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::fx::FxHashMap; use syntax::ast::{Name, NodeId}; use syntax_pos::Span; @@ -635,7 +635,7 @@ enum TestKind<'tcx> { // test the branches of enum Switch { adt_def: &'tcx ty::AdtDef, - variants: BitArray<usize>, + variants: BitSet<usize>, }, // test the branches of enum diff --git a/src/librustc_mir/build/matches/test.rs b/src/librustc_mir/build/matches/test.rs index 373c8e039f8..caef3ef80db 100644 --- a/src/librustc_mir/build/matches/test.rs +++ b/src/librustc_mir/build/matches/test.rs @@ -18,8 +18,8 @@ use build::Builder; use build::matches::{Candidate, MatchPair, Test, TestKind}; use hair::*; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::bitvec::BitArray; use rustc::ty::{self, Ty}; use rustc::ty::util::IntTypeExt; use rustc::mir::*; @@ -38,7 +38,7 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> { span: match_pair.pattern.span, kind: TestKind::Switch { adt_def: adt_def.clone(), - variants: BitArray::new(adt_def.variants.len()), + variants: BitSet::new_empty(adt_def.variants.len()), }, } } @@ -152,7 +152,7 @@ impl<'a, 'gcx, 'tcx> Builder<'a, 'gcx, 'tcx> { pub fn add_variants_to_switch<'pat>(&mut self, test_place: &Place<'tcx>, candidate: &Candidate<'pat, 'tcx>, - variants: &mut BitArray<usize>) + variants: &mut BitSet<usize>) -> bool { let match_pair = match candidate.match_pairs.iter().find(|mp| mp.place == *test_place) { diff --git a/src/librustc_mir/dataflow/at_location.rs b/src/librustc_mir/dataflow/at_location.rs index 39643af77a1..d815bfedc37 100644 --- a/src/librustc_mir/dataflow/at_location.rs +++ b/src/librustc_mir/dataflow/at_location.rs @@ -12,8 +12,7 @@ //! locations. use rustc::mir::{BasicBlock, Location}; -use rustc_data_structures::bitvec::BitIter; -use rustc_data_structures::indexed_set::{HybridIdxSet, IdxSet}; +use rustc_data_structures::bit_set::{BitIter, BitSet, HybridBitSet}; use dataflow::{BitDenotation, BlockSets, DataflowResults}; use dataflow::move_paths::{HasMoveData, MovePathIndex}; @@ -76,9 +75,9 @@ where BD: BitDenotation, { base_results: DataflowResults<BD>, - curr_state: IdxSet<BD::Idx>, - stmt_gen: HybridIdxSet<BD::Idx>, - stmt_kill: HybridIdxSet<BD::Idx>, + curr_state: BitSet<BD::Idx>, + stmt_gen: HybridBitSet<BD::Idx>, + stmt_kill: HybridBitSet<BD::Idx>, } impl<BD> FlowAtLocation<BD> @@ -105,9 +104,9 @@ where pub fn new(results: DataflowResults<BD>) -> Self { let bits_per_block = results.sets().bits_per_block(); - let curr_state = IdxSet::new_empty(bits_per_block); - let stmt_gen = HybridIdxSet::new_empty(bits_per_block); - let stmt_kill = HybridIdxSet::new_empty(bits_per_block); + let curr_state = BitSet::new_empty(bits_per_block); + let stmt_gen = HybridBitSet::new_empty(bits_per_block); + let stmt_kill = HybridBitSet::new_empty(bits_per_block); FlowAtLocation { base_results: results, curr_state: curr_state, @@ -121,7 +120,7 @@ where self.base_results.operator() } - pub fn contains(&self, x: &BD::Idx) -> bool { + pub fn contains(&self, x: BD::Idx) -> bool { self.curr_state.contains(x) } @@ -224,7 +223,7 @@ where // siblings); // - ~99% of the time the loop isn't reached, and this code is hot, so // we don't want to allocate `todo` unnecessarily. - if self.contains(&mpi) { + if self.contains(mpi) { return Some(mpi); } let move_data = self.operator().move_data(); @@ -236,7 +235,7 @@ where }; while let Some(mpi) = todo.pop() { - if self.contains(&mpi) { + if self.contains(mpi) { return Some(mpi); } let move_path = &move_data.move_paths[mpi]; diff --git a/src/librustc_mir/dataflow/graphviz.rs b/src/librustc_mir/dataflow/graphviz.rs index 9487147ea9d..45baab844ab 100644 --- a/src/librustc_mir/dataflow/graphviz.rs +++ b/src/librustc_mir/dataflow/graphviz.rs @@ -12,7 +12,6 @@ use syntax::ast::NodeId; use rustc::mir::{BasicBlock, Mir}; -use rustc_data_structures::bitvec::bits_to_string; use dot; use dot::IntoCow; @@ -223,7 +222,7 @@ where MWF: MirWithFlowState<'tcx>, // Entry let set = flow.sets.on_entry_set_for(i); - write!(w, "<td>{:?}</td>", dot::escape_html(&bits_to_string(set.words(), bits_per_block)))?; + write!(w, "<td>{:?}</td>", dot::escape_html(&set.to_string(bits_per_block)))?; // Terminator write!(w, "<td>")?; 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) { diff --git a/src/librustc_mir/dataflow/mod.rs b/src/librustc_mir/dataflow/mod.rs index 49d75d31fc7..42b3ac6c6d1 100644 --- a/src/librustc_mir/dataflow/mod.rs +++ b/src/librustc_mir/dataflow/mod.rs @@ -10,8 +10,7 @@ use syntax::ast::{self, MetaItem}; -use rustc_data_structures::bitvec::{bitwise, BitwiseOperator}; -use rustc_data_structures::indexed_set::{HybridIdxSet, IdxSet}; +use rustc_data_structures::bit_set::{bitwise, BitwiseOperator, BitSet, HybridBitSet}; use rustc_data_structures::indexed_vec::Idx; use rustc_data_structures::work_queue::WorkQueue; @@ -125,7 +124,7 @@ pub(crate) fn do_dataflow<'a, 'gcx, 'tcx, BD, P>(tcx: TyCtxt<'a, 'gcx, 'tcx>, mir: &'a Mir<'tcx>, node_id: ast::NodeId, attributes: &[ast::Attribute], - dead_unwinds: &IdxSet<BasicBlock>, + dead_unwinds: &BitSet<BasicBlock>, bd: BD, p: P) -> DataflowResults<BD> @@ -182,7 +181,7 @@ struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation { fn propagate(&mut self) { - let mut temp = IdxSet::new_empty(self.flow_state.sets.bits_per_block); + let mut temp = BitSet::new_empty(self.flow_state.sets.bits_per_block); let mut propcx = PropagationContext { builder: self, }; @@ -231,7 +230,7 @@ impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> where BD: BitDenotation { - fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) { + fn walk_cfg(&mut self, in_out: &mut BitSet<BD::Idx>) { let mut dirty_queue: WorkQueue<mir::BasicBlock> = WorkQueue::with_all(self.builder.mir.basic_blocks().len()); let mir = self.builder.mir; @@ -352,7 +351,7 @@ pub fn state_for_location<'tcx, T: BitDenotation>(loc: Location, analysis: &T, result: &DataflowResults<T>, mir: &Mir<'tcx>) - -> IdxSet<T::Idx> { + -> BitSet<T::Idx> { let mut on_entry = result.sets().on_entry_set_for(loc.block.index()).to_owned(); let mut kill_set = on_entry.to_hybrid(); let mut gen_set = kill_set.clone(); @@ -385,7 +384,7 @@ pub fn state_for_location<'tcx, T: BitDenotation>(loc: Location, pub struct DataflowAnalysis<'a, 'tcx: 'a, O> where O: BitDenotation { flow_state: DataflowState<O>, - dead_unwinds: &'a IdxSet<mir::BasicBlock>, + dead_unwinds: &'a BitSet<mir::BasicBlock>, mir: &'a Mir<'tcx>, } @@ -426,7 +425,7 @@ pub struct DataflowState<O: BitDenotation> impl<O: BitDenotation> DataflowState<O> { pub(crate) fn interpret_set<'c, P>(&self, o: &'c O, - set: &IdxSet<O::Idx>, + set: &BitSet<O::Idx>, render_idx: &P) -> Vec<DebugFormatted> where P: Fn(&O, O::Idx) -> DebugFormatted @@ -436,7 +435,7 @@ impl<O: BitDenotation> DataflowState<O> { pub(crate) fn interpret_hybrid_set<'c, P>(&self, o: &'c O, - set: &HybridIdxSet<O::Idx>, + set: &HybridBitSet<O::Idx>, render_idx: &P) -> Vec<DebugFormatted> where P: Fn(&O, O::Idx) -> DebugFormatted @@ -451,21 +450,21 @@ pub struct AllSets<E: Idx> { bits_per_block: usize, /// For each block, bits valid on entry to the block. - on_entry_sets: Vec<IdxSet<E>>, + on_entry_sets: Vec<BitSet<E>>, /// For each block, bits generated by executing the statements + /// terminator in the block -- with one caveat. In particular, for /// *call terminators*, the effect of storing the destination is /// not included, since that only takes effect on the **success** /// edge (and not the unwind edge). - gen_sets: Vec<HybridIdxSet<E>>, + gen_sets: Vec<HybridBitSet<E>>, /// For each block, bits killed by executing the statements + /// terminator in the block -- with one caveat. In particular, for /// *call terminators*, the effect of storing the destination is /// not included, since that only takes effect on the **success** /// edge (and not the unwind edge). - kill_sets: Vec<HybridIdxSet<E>>, + kill_sets: Vec<HybridBitSet<E>>, } /// Triple of sets associated with a given block. @@ -485,20 +484,20 @@ pub struct AllSets<E: Idx> { #[derive(Debug)] pub struct BlockSets<'a, E: Idx> { /// Dataflow state immediately before control flow enters the given block. - pub(crate) on_entry: &'a mut IdxSet<E>, + pub(crate) on_entry: &'a mut BitSet<E>, /// Bits that are set to 1 by the time we exit the given block. Hybrid /// because it usually contains only 0 or 1 elements. - pub(crate) gen_set: &'a mut HybridIdxSet<E>, + pub(crate) gen_set: &'a mut HybridBitSet<E>, /// Bits that are set to 0 by the time we exit the given block. Hybrid /// because it usually contains only 0 or 1 elements. - pub(crate) kill_set: &'a mut HybridIdxSet<E>, + pub(crate) kill_set: &'a mut HybridBitSet<E>, } impl<'a, E:Idx> BlockSets<'a, E> { - fn gen(&mut self, e: &E) { - self.gen_set.add(e); + fn gen(&mut self, e: E) { + self.gen_set.insert(e); self.kill_set.remove(e); } fn gen_all<I>(&mut self, i: I) @@ -506,13 +505,13 @@ impl<'a, E:Idx> BlockSets<'a, E> { I::Item: Borrow<E> { for j in i { - self.gen(j.borrow()); + self.gen(*j.borrow()); } } - fn kill(&mut self, e: &E) { + fn kill(&mut self, e: E) { self.gen_set.remove(e); - self.kill_set.add(e); + self.kill_set.insert(e); } fn kill_all<I>(&mut self, i: I) @@ -520,7 +519,7 @@ impl<'a, E:Idx> BlockSets<'a, E> { I::Item: Borrow<E> { for j in i { - self.kill(j.borrow()); + self.kill(*j.borrow()); } } @@ -540,13 +539,13 @@ impl<E:Idx> AllSets<E> { } } - pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> { + pub fn on_entry_set_for(&self, block_idx: usize) -> &BitSet<E> { &self.on_entry_sets[block_idx] } - pub fn gen_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> { + pub fn gen_set_for(&self, block_idx: usize) -> &HybridBitSet<E> { &self.gen_sets[block_idx] } - pub fn kill_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> { + pub fn kill_set_for(&self, block_idx: usize) -> &HybridBitSet<E> { &self.kill_sets[block_idx] } } @@ -609,7 +608,7 @@ pub trait BitDenotation: BitwiseOperator { /// these won't be accounted for correctly. /// /// (For example, establishing the call arguments.) - fn start_block_effect(&self, entry_set: &mut IdxSet<Self::Idx>); + fn start_block_effect(&self, entry_set: &mut BitSet<Self::Idx>); /// Similar to `statement_effect`, except it applies /// *just before* the statement rather than *just after* it. @@ -689,7 +688,7 @@ pub trait BitDenotation: BitwiseOperator { /// kill-sets associated with each edge coming out of the basic /// block. fn propagate_call_return(&self, - in_out: &mut IdxSet<Self::Idx>, + in_out: &mut BitSet<Self::Idx>, call_bb: mir::BasicBlock, dest_bb: mir::BasicBlock, dest_place: &mir::Place); @@ -698,17 +697,17 @@ pub trait BitDenotation: BitwiseOperator { impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation { pub fn new(mir: &'a Mir<'tcx>, - dead_unwinds: &'a IdxSet<mir::BasicBlock>, + dead_unwinds: &'a BitSet<mir::BasicBlock>, denotation: D) -> Self where D: InitialFlow { let bits_per_block = denotation.bits_per_block(); let num_blocks = mir.basic_blocks().len(); let on_entry_sets = if D::bottom_value() { - vec![IdxSet::new_filled(bits_per_block); num_blocks] + vec![BitSet::new_filled(bits_per_block); num_blocks] } else { - vec![IdxSet::new_empty(bits_per_block); num_blocks] + vec![BitSet::new_empty(bits_per_block); num_blocks] }; - let gen_sets = vec![HybridIdxSet::new_empty(bits_per_block); num_blocks]; + let gen_sets = vec![HybridBitSet::new_empty(bits_per_block); num_blocks]; let kill_sets = gen_sets.clone(); DataflowAnalysis { @@ -727,7 +726,7 @@ impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation } pub fn new_from_sets(mir: &'a Mir<'tcx>, - dead_unwinds: &'a IdxSet<mir::BasicBlock>, + dead_unwinds: &'a BitSet<mir::BasicBlock>, sets: AllSets<D::Idx>, denotation: D) -> Self { DataflowAnalysis { @@ -758,7 +757,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation /// unwind target). fn propagate_bits_into_graph_successors_of( &mut self, - in_out: &mut IdxSet<D::Idx>, + in_out: &mut BitSet<D::Idx>, (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData), dirty_list: &mut WorkQueue<mir::BasicBlock>) { @@ -787,7 +786,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation target, value: _, location: _, unwind: Some(unwind) } => { self.propagate_bits_into_entry_set_for(in_out, target, dirty_list); - if !self.dead_unwinds.contains(&bb) { + if !self.dead_unwinds.contains(bb) { self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list); } } @@ -798,7 +797,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation } mir::TerminatorKind::Call { cleanup, ref destination, func: _, args: _ } => { if let Some(unwind) = cleanup { - if !self.dead_unwinds.contains(&bb) { + if !self.dead_unwinds.contains(bb) { self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list); } } @@ -819,7 +818,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation mir::TerminatorKind::FalseUnwind { real_target, unwind } => { self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list); if let Some(unwind) = unwind { - if !self.dead_unwinds.contains(&bb) { + if !self.dead_unwinds.contains(bb) { self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list); } } @@ -828,7 +827,7 @@ impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation } fn propagate_bits_into_entry_set_for(&mut self, - in_out: &IdxSet<D::Idx>, + in_out: &BitSet<D::Idx>, bb: mir::BasicBlock, dirty_queue: &mut WorkQueue<mir::BasicBlock>) { let entry_set = self.flow_state.sets.for_block(bb.index()).on_entry; diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs index 52bbffa7519..d50ef2242fa 100644 --- a/src/librustc_mir/monomorphize/collector.rs +++ b/src/librustc_mir/monomorphize/collector.rs @@ -210,7 +210,7 @@ use rustc::util::common::time; use monomorphize::item::{MonoItemExt, DefPathBasedNames, InstantiationMode}; -use rustc_data_structures::bitvec::BitVector; +use rustc_data_structures::bit_set::GrowableBitSet; use rustc_data_structures::sync::{MTRef, MTLock, ParallelIterator, par_iter}; #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] @@ -231,7 +231,7 @@ pub struct InliningMap<'tcx> { // Contains one bit per mono item in the `targets` field. That bit // is true if that mono item needs to be inlined into every CGU. - inlines: BitVector<usize>, + inlines: GrowableBitSet<usize>, } impl<'tcx> InliningMap<'tcx> { @@ -240,7 +240,7 @@ impl<'tcx> InliningMap<'tcx> { InliningMap { index: FxHashMap(), targets: Vec::new(), - inlines: BitVector::with_capacity(1024), + inlines: GrowableBitSet::with_capacity(1024), } } diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs index bf538112e41..92b6af8b51f 100644 --- a/src/librustc_mir/transform/elaborate_drops.rs +++ b/src/librustc_mir/transform/elaborate_drops.rs @@ -18,15 +18,14 @@ use dataflow::{self, do_dataflow, DebugFormatted}; use rustc::ty::{self, TyCtxt}; use rustc::mir::*; use rustc::util::nodemap::FxHashMap; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; +use std::fmt; +use syntax::ast; +use syntax_pos::Span; use transform::{MirPass, MirSource}; use util::patch::MirPatch; use util::elaborate_drops::{DropFlagState, Unwind, elaborate_drop}; use util::elaborate_drops::{DropElaborator, DropStyle, DropFlagMode}; -use syntax::ast; -use syntax_pos::Span; - -use std::fmt; pub struct ElaborateDrops; @@ -92,12 +91,12 @@ fn find_dead_unwinds<'a, 'tcx>( mir: &Mir<'tcx>, id: ast::NodeId, env: &MoveDataParamEnv<'tcx, 'tcx>) - -> IdxSet<BasicBlock> + -> BitSet<BasicBlock> { debug!("find_dead_unwinds({:?})", mir.span); // We only need to do this pass once, because unwind edges can only // reach cleanup blocks, which can't have unwind edges themselves. - let mut dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len()); + let mut dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); let flow_inits = do_dataflow(tcx, mir, id, &[], &dead_unwinds, MaybeInitializedPlaces::new(tcx, mir, &env), @@ -111,7 +110,7 @@ fn find_dead_unwinds<'a, 'tcx>( let mut init_data = InitializationData { live: flow_inits.sets().on_entry_set_for(bb.index()).to_owned(), - dead: IdxSet::new_empty(env.move_data.move_paths.len()), + dead: BitSet::new_empty(env.move_data.move_paths.len()), }; debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}", bb, bb_data, init_data.live); @@ -138,7 +137,7 @@ fn find_dead_unwinds<'a, 'tcx>( debug!("find_dead_unwinds @ {:?}: maybe_live={}", bb, maybe_live); if !maybe_live { - dead_unwinds.add(&bb); + dead_unwinds.insert(bb); } } @@ -146,8 +145,8 @@ fn find_dead_unwinds<'a, 'tcx>( } struct InitializationData { - live: IdxSet<MovePathIndex>, - dead: IdxSet<MovePathIndex> + live: BitSet<MovePathIndex>, + dead: BitSet<MovePathIndex> } impl InitializationData { @@ -162,19 +161,19 @@ impl InitializationData { loc, path, df); match df { DropFlagState::Present => { - self.live.add(&path); - self.dead.remove(&path); + self.live.insert(path); + self.dead.remove(path); } DropFlagState::Absent => { - self.dead.add(&path); - self.live.remove(&path); + self.dead.insert(path); + self.live.remove(path); } } }); } fn state(&self, path: MovePathIndex) -> (bool, bool) { - (self.live.contains(&path), self.dead.contains(&path)) + (self.live.contains(path), self.dead.contains(path)) } } diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs index 01edfd2bfc9..96111519550 100644 --- a/src/librustc_mir/transform/generator.rs +++ b/src/librustc_mir/transform/generator.rs @@ -69,7 +69,7 @@ use util::dump_mir; use util::liveness::{self, IdentityMap}; use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::indexed_vec::Idx; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; use std::borrow::Cow; use std::iter::once; use std::mem; @@ -331,7 +331,7 @@ impl<'tcx> Visitor<'tcx> for StorageIgnored { _location: Location) { match statement.kind { StatementKind::StorageLive(l) | - StatementKind::StorageDead(l) => { self.0.remove(&l); } + StatementKind::StorageDead(l) => { self.0.remove(l); } _ => (), } } @@ -341,7 +341,7 @@ struct BorrowedLocals(liveness::LiveVarSet<Local>); fn mark_as_borrowed<'tcx>(place: &Place<'tcx>, locals: &mut BorrowedLocals) { match *place { - Place::Local(l) => { locals.0.add(&l); }, + Place::Local(l) => { locals.0.insert(l); }, Place::Promoted(_) | Place::Static(..) => (), Place::Projection(ref proj) => { @@ -376,7 +376,7 @@ fn locals_live_across_suspend_points( liveness::LiveVarSet<Local>, FxHashMap<BasicBlock, liveness::LiveVarSet<Local>>, ) { - let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len()); + let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); let node_id = tcx.hir.as_local_node_id(source.def_id).unwrap(); // Calculate when MIR locals have live storage. This gives us an upper bound of their @@ -388,7 +388,7 @@ fn locals_live_across_suspend_points( // Find the MIR locals which do not use StorageLive/StorageDead statements. // The storage of these locals are always live. - let mut ignored = StorageIgnored(IdxSet::new_filled(mir.local_decls.len())); + let mut ignored = StorageIgnored(BitSet::new_filled(mir.local_decls.len())); ignored.visit_mir(mir); // Calculate the MIR locals which have been previously @@ -472,7 +472,7 @@ fn locals_live_across_suspend_points( } // The generator argument is ignored - set.remove(&self_arg()); + set.remove(self_arg()); (set, storage_liveness_map) } @@ -502,7 +502,7 @@ fn compute_layout<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, for (local, decl) in mir.local_decls.iter_enumerated() { // Ignore locals which are internal or not live - if !live_locals.contains(&local) || decl.internal { + if !live_locals.contains(local) || decl.internal { continue; } @@ -823,7 +823,7 @@ fn create_cases<'a, 'tcx, F>(mir: &mut Mir<'tcx>, // Create StorageLive instructions for locals with live storage for i in 0..(mir.local_decls.len()) { let l = Local::new(i); - if point.storage_liveness.contains(&l) && !transform.remap.contains_key(&l) { + if point.storage_liveness.contains(l) && !transform.remap.contains_key(&l) { statements.push(Statement { source_info, kind: StatementKind::StorageLive(l), diff --git a/src/librustc_mir/transform/inline.rs b/src/librustc_mir/transform/inline.rs index 31e437ce228..8689fde3ee6 100644 --- a/src/librustc_mir/transform/inline.rs +++ b/src/librustc_mir/transform/inline.rs @@ -14,7 +14,7 @@ use rustc::hir; use rustc::hir::CodegenFnAttrFlags; use rustc::hir::def_id::DefId; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use rustc::mir::*; @@ -271,7 +271,7 @@ impl<'a, 'tcx> Inliner<'a, 'tcx> { // Traverse the MIR manually so we can account for the effects of // inlining on the CFG. let mut work_list = vec![START_BLOCK]; - let mut visited = BitArray::new(callee_mir.basic_blocks().len()); + let mut visited = BitSet::new_empty(callee_mir.basic_blocks().len()); while let Some(bb) = work_list.pop() { if !visited.insert(bb.index()) { continue; } let blk = &callee_mir.basic_blocks()[bb]; diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs index a2175dce33a..bc9cc7274d5 100644 --- a/src/librustc_mir/transform/qualify_consts.rs +++ b/src/librustc_mir/transform/qualify_consts.rs @@ -14,8 +14,7 @@ //! The Qualif flags below can be used to also provide better //! diagnostics as to why a constant rvalue wasn't promoted. -use rustc_data_structures::bitvec::BitArray; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::IndexVec; use rustc_data_structures::fx::FxHashSet; use rustc::hir; @@ -116,7 +115,7 @@ struct Qualifier<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { param_env: ty::ParamEnv<'tcx>, local_qualif: IndexVec<Local, Option<Qualif>>, qualif: Qualif, - const_fn_arg_vars: BitArray<Local>, + const_fn_arg_vars: BitSet<Local>, temp_promotion_state: IndexVec<Local, TempState>, promotion_candidates: Vec<Candidate> } @@ -151,7 +150,7 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> { param_env, local_qualif, qualif: Qualif::empty(), - const_fn_arg_vars: BitArray::new(mir.local_decls.len()), + const_fn_arg_vars: BitSet::new_empty(mir.local_decls.len()), temp_promotion_state: temps, promotion_candidates: vec![] } @@ -280,12 +279,12 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> { } /// Qualify a whole const, static initializer or const fn. - fn qualify_const(&mut self) -> (Qualif, Lrc<IdxSet<Local>>) { + fn qualify_const(&mut self) -> (Qualif, Lrc<BitSet<Local>>) { debug!("qualifying {} {:?}", self.mode, self.def_id); let mir = self.mir; - let mut seen_blocks = BitArray::new(mir.basic_blocks().len()); + let mut seen_blocks = BitSet::new_empty(mir.basic_blocks().len()); let mut bb = START_BLOCK; loop { seen_blocks.insert(bb.index()); @@ -383,14 +382,14 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> { // Collect all the temps we need to promote. - let mut promoted_temps = IdxSet::new_empty(self.temp_promotion_state.len()); + let mut promoted_temps = BitSet::new_empty(self.temp_promotion_state.len()); for candidate in &self.promotion_candidates { match *candidate { Candidate::Ref(Location { block: bb, statement_index: stmt_idx }) => { match self.mir[bb].statements[stmt_idx].kind { StatementKind::Assign(_, Rvalue::Ref(_, _, Place::Local(index))) => { - promoted_temps.add(&index); + promoted_temps.insert(index); } _ => {} } @@ -1121,7 +1120,7 @@ pub fn provide(providers: &mut Providers) { fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) - -> (u8, Lrc<IdxSet<Local>>) { + -> (u8, Lrc<BitSet<Local>>) { // NB: This `borrow()` is guaranteed to be valid (i.e., the value // cannot yet be stolen), because `mir_validated()`, which steals // from `mir_const(), forces this query to execute before @@ -1130,7 +1129,7 @@ fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, if mir.return_ty().references_error() { tcx.sess.delay_span_bug(mir.span, "mir_const_qualif: Mir had errors"); - return (Qualif::NOT_CONST.bits(), Lrc::new(IdxSet::new_empty(0))); + return (Qualif::NOT_CONST.bits(), Lrc::new(BitSet::new_empty(0))); } let mut qualifier = Qualifier::new(tcx, def_id, mir, Mode::Const); @@ -1220,7 +1219,7 @@ impl MirPass for QualifyAndPromoteConstants { block.statements.retain(|statement| { match statement.kind { StatementKind::StorageDead(index) => { - !promoted_temps.contains(&index) + !promoted_temps.contains(index) } _ => true } @@ -1228,7 +1227,7 @@ impl MirPass for QualifyAndPromoteConstants { let terminator = block.terminator_mut(); match terminator.kind { TerminatorKind::Drop { location: Place::Local(index), target, .. } => { - if promoted_temps.contains(&index) { + if promoted_temps.contains(index) { terminator.kind = TerminatorKind::Goto { target, }; diff --git a/src/librustc_mir/transform/remove_noop_landing_pads.rs b/src/librustc_mir/transform/remove_noop_landing_pads.rs index a2561d3d793..9cdd94a7be7 100644 --- a/src/librustc_mir/transform/remove_noop_landing_pads.rs +++ b/src/librustc_mir/transform/remove_noop_landing_pads.rs @@ -10,7 +10,7 @@ use rustc::ty::TyCtxt; use rustc::mir::*; -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use transform::{MirPass, MirSource}; use util::patch::MirPatch; @@ -45,7 +45,7 @@ impl RemoveNoopLandingPads { &self, bb: BasicBlock, mir: &Mir, - nop_landing_pads: &BitArray<BasicBlock>, + nop_landing_pads: &BitSet<BasicBlock>, ) -> bool { for stmt in &mir[bb].statements { match stmt.kind { @@ -111,7 +111,7 @@ impl RemoveNoopLandingPads { let mut jumps_folded = 0; let mut landing_pads_removed = 0; - let mut nop_landing_pads = BitArray::new(mir.basic_blocks().len()); + let mut nop_landing_pads = BitSet::new_empty(mir.basic_blocks().len()); // This is a post-order traversal, so that if A post-dominates B // then A will be visited before B. diff --git a/src/librustc_mir/transform/rustc_peek.rs b/src/librustc_mir/transform/rustc_peek.rs index f3e0f557363..3c898eedebc 100644 --- a/src/librustc_mir/transform/rustc_peek.rs +++ b/src/librustc_mir/transform/rustc_peek.rs @@ -14,7 +14,7 @@ use syntax_pos::Span; use rustc::ty::{self, TyCtxt}; use rustc::mir::{self, Mir, Location}; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; use transform::{MirPass, MirSource}; use dataflow::{do_dataflow, DebugFormatted}; @@ -46,7 +46,7 @@ impl MirPass for SanityCheck { let param_env = tcx.param_env(def_id); let move_data = MoveData::gather_moves(mir, tcx).unwrap(); let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env }; - let dead_unwinds = IdxSet::new_empty(mir.basic_blocks().len()); + let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); let flow_inits = do_dataflow(tcx, mir, id, &attributes, &dead_unwinds, MaybeInitializedPlaces::new(tcx, mir, &mdpe), @@ -175,7 +175,7 @@ fn each_block<'a, 'tcx, O>(tcx: TyCtxt<'a, 'tcx, 'tcx>, // Okay, our search is over. match move_data.rev_lookup.find(peeking_at_place) { LookupResult::Exact(peek_mpi) => { - let bit_state = sets.on_entry.contains(&peek_mpi); + let bit_state = sets.on_entry.contains(peek_mpi); debug!("rustc_peek({:?} = &{:?}) bit_state: {}", place, peeking_at_place, bit_state); if !bit_state { diff --git a/src/librustc_mir/transform/simplify.rs b/src/librustc_mir/transform/simplify.rs index 164790db4b5..a6e0932bf0a 100644 --- a/src/librustc_mir/transform/simplify.rs +++ b/src/librustc_mir/transform/simplify.rs @@ -37,7 +37,7 @@ //! naively generate still contains the `_a = ()` write in the unreachable block "after" the //! return. -use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use rustc::ty::TyCtxt; use rustc::mir::*; @@ -249,7 +249,7 @@ impl<'a, 'tcx: 'a> CfgSimplifier<'a, 'tcx> { } pub fn remove_dead_blocks(mir: &mut Mir) { - let mut seen = BitArray::new(mir.basic_blocks().len()); + let mut seen = BitSet::new_empty(mir.basic_blocks().len()); for (bb, _) in traversal::preorder(mir) { seen.insert(bb.index()); } @@ -285,7 +285,7 @@ impl MirPass for SimplifyLocals { tcx: TyCtxt<'a, 'tcx, 'tcx>, _: MirSource, mir: &mut Mir<'tcx>) { - let mut marker = DeclMarker { locals: BitArray::new(mir.local_decls.len()) }; + let mut marker = DeclMarker { locals: BitSet::new_empty(mir.local_decls.len()) }; marker.visit_mir(mir); // Return pointer and arguments are always live marker.locals.insert(RETURN_PLACE); @@ -310,7 +310,7 @@ impl MirPass for SimplifyLocals { /// Construct the mapping while swapping out unused stuff out from the `vec`. fn make_local_map<'tcx, V>( vec: &mut IndexVec<Local, V>, - mask: BitArray<Local>, + mask: BitSet<Local>, ) -> IndexVec<Local, Option<Local>> { let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*vec); let mut used = Local::new(0); @@ -326,7 +326,7 @@ fn make_local_map<'tcx, V>( } struct DeclMarker { - pub locals: BitArray<Local>, + pub locals: BitSet<Local>, } impl<'tcx> Visitor<'tcx> for DeclMarker { diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs index 3ae470e1d4b..420ca4efde3 100644 --- a/src/librustc_mir/util/liveness.rs +++ b/src/librustc_mir/util/liveness.rs @@ -37,7 +37,7 @@ use rustc::mir::visit::{PlaceContext, Visitor}; use rustc::mir::Local; use rustc::mir::*; use rustc::ty::{item_path, TyCtxt}; -use rustc_data_structures::indexed_set::IdxSet; +use rustc_data_structures::bit_set::BitSet; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use rustc_data_structures::work_queue::WorkQueue; use std::fs; @@ -46,7 +46,7 @@ use std::path::{Path, PathBuf}; use transform::MirSource; use util::pretty::{dump_enabled, write_basic_block, write_mir_intro}; -pub type LiveVarSet<V> = IdxSet<V>; +pub type LiveVarSet<V> = BitSet<V>; /// This gives the result of the liveness analysis at the boundary of /// basic blocks. @@ -243,8 +243,8 @@ impl<V: Idx> DefsUses<V> { // X = 5 // // Defs = {}, Uses = {X} // use(X) - self.uses.remove(&index); - self.defs.add(&index); + self.uses.remove(index); + self.defs.insert(index); } fn add_use(&mut self, index: V) { @@ -258,8 +258,8 @@ impl<V: Idx> DefsUses<V> { // X = 5 // // Defs = {}, Uses = {X} // use(X) - self.defs.remove(&index); - self.uses.add(&index); + self.defs.remove(index); + self.uses.insert(index); } } diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs index 2aaab6aaa16..68b46841718 100644 --- a/src/libsyntax/lib.rs +++ b/src/libsyntax/lib.rs @@ -46,7 +46,7 @@ extern crate smallvec; extern crate serialize as rustc_serialize; // used by deriving use rustc_data_structures::sync::Lock; -use rustc_data_structures::bitvec::BitVector; +use rustc_data_structures::bit_set::GrowableBitSet; pub use rustc_data_structures::small_vec::OneVector; pub use rustc_data_structures::thin_vec::ThinVec; use ast::AttrId; @@ -82,8 +82,8 @@ macro_rules! unwrap_or { } pub struct Globals { - used_attrs: Lock<BitVector<AttrId>>, - known_attrs: Lock<BitVector<AttrId>>, + used_attrs: Lock<GrowableBitSet<AttrId>>, + known_attrs: Lock<GrowableBitSet<AttrId>>, syntax_pos_globals: syntax_pos::Globals, } @@ -92,8 +92,8 @@ impl Globals { Globals { // We have no idea how many attributes their will be, so just // initiate the vectors with 0 bits. We'll grow them as necessary. - used_attrs: Lock::new(BitVector::new()), - known_attrs: Lock::new(BitVector::new()), + used_attrs: Lock::new(GrowableBitSet::new_empty()), + known_attrs: Lock::new(GrowableBitSet::new_empty()), syntax_pos_globals: syntax_pos::Globals::new(), } } |