| Age | Commit message (Collapse) | Author | Lines |
|---|
|
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.
|
|
This requires the following changes.
- It moves parts of bitslice.rs into bitvec.rs: `bitwise()`,
`BitwiseOperator`, `bits_to_string()`.
- It changes `IdxSet` to just be a wrapper around `BitArray`.
- It changes `BitArray` and `BitVec` to use `usize` words instead of
`u128` words. (`BitSlice` and `IdxSet` already use `usize`.) Local
profiling showed `usize` was better.
- It moves some operations from `IdxSet` into `BitArray`:
`new_filled()`, `clear()`, `set_up_to()`, `trim_to()` (renamed
`clear_above()`), `words()` and `words_mut()`, `encode()` and
`decode(). The `IdxSet` operations now just call the `BitArray`
operations.
- It replaces `BitArray`'s iterator implementation with `IdxSet`'s,
because the latter is more concise. It also removes the buggy
`size_hint` function from `BitArray`'s iterator, which counted the
number of *words* rather than the number of *bits*. `IdxSet`'s
iterator is now just a thin wrapper around `BitArray`'s iterator.
- It moves some unit tests from `indexed_set.rs` to `bitvec.rs`.
|
|
So that the `BitArray` code is all together and before the `BitVector`
code, instead of being awkwardly interleaved.
|
|
Currently when a row is instantiated in SparseBitMatrix, any missing
rows prior to it are also fully instantiated.
This patch changes things so that those prior rows are minimally
instantiated (with a `None`). This avoids a decent number of allocations
in NLL, speeding up several benchmarks by up to 0.5%.
The patch also removes two unused methods, `len()` and
`iter_enumerated()`.
|
|
The new names are clearer.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Using a `BTreeMap` to represent rows in the bit matrix is really slow.
This patch changes things so that each row is represented by a
`BitVector`. This is a less sparse representation, but a much faster
one.
As a result, `SparseBitSet` and `SparseChunk` can be removed.
Other minor changes in this patch.
- It renames `BitVector::insert()` as `merge()`, which matches the
terminology in the other classes in bitvec.rs.
- It removes `SparseBitMatrix::is_subset()`, which is unused.
- It reinstates `RegionValueElements::num_elements()`, which #52190 had
removed.
- It removes a low-value `debug!` call in `SparseBitMatrix::add()`.
|
|
Also modify `SparseBitMatrix` so that it does not require knowing the
dimensions in advance, but instead grows on demand.
|
|
|
|
|
|
This also implements ExactSizeIterator where applicable.
Addresses most of the Iterator traits mentioned in #23708.
|
|
|
|
|
|
Fixes #48170
|
|
|
|
Fixes #47602
|
|
Notably, the (hitherto unused) `less_than` method was not at all what it
purported to be. It in fact computes the opposite.
|
|
On "the parameter type `T` may not live long enough" error, point to the
parameter type suggesting lifetime bindings:
```
error[E0310]: the parameter type `T` may not live long enough
--> $DIR/lifetime-doesnt-live-long-enough.rs:28:5
|
27 | struct Foo<T> {
| - help: consider adding an explicit lifetime bound `T: 'static`...
28 | foo: &'static T
| ^^^^^^^^^^^^^^^
|
note: ...so that the reference type `&'static T` does not outlive the data it points at
--> $DIR/lifetime-doesnt-live-long-enough.rs:28:5
|
28 | foo: &'static T
| ^^^^^^^^^^^^^^^
```
|
|
Like #43008 (f668999), but _much more aggressive_.
|
|
|
|
This removes another special case of Switch by replacing it with the more general SwitchInt. While
this is more clunky currently, there’s no reason we can’t make it nice (and efficient) to use.
|
|
|
|
|
|
The new `Predecessors` type computes a set of interesting targets and
their HIR predecessors, and discards everything in between.
|
|
|
|
clarify comments and panic message
|
|
|
|
Also adds a FromIterator impl for BitVector to allow construction of a
BitVector from an iterator yeilding bools.
|
|
Adds Preorder, Postorder and Reverse Postorder traversal iterators.
Also makes trans/mir use Reverse Postorder traversal for blocks.
|
|
rust-lang-nursery/rustfmt#836
|
|
BitVector is much more space efficient.
|
|
Fixes #31002
|
|
|
|
probably not enough. This code is so simple, what could possibly go
wrong?
|
|
The common pattern `iter::repeat(elt).take(n).collect::<Vec<_>>()` is
exactly equivalent to `vec![elt; n]`, do this replacement in the whole
tree.
(Actually, vec![] is smart enough to only call clone n - 1 times, while
the former solution would call clone n times, and this fact is
virtually irrelevant in practice.)
|
|
|
|
older `each` method, but is otherwise identical.
|
