| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
Currently, `BitSet` doesn't actually know its own domain size; it just
knows how many words it contains. To improve things, this commit makes
the following changes.
- It changes `BitSet` and `SparseBitSet` to store their own domain size,
and do more precise bounds and same-size checks with it. It also
changes the signature of `BitSet::to_string()` (and puts it within
`impl ToString`) now that the domain size need not be passed in from
outside.
- It uses `derive(RustcDecodable, RustcEncodable)` for `BitSet`. This
required adding code to handle `PhantomData` in `libserialize`.
- As a result, it removes the domain size from `HybridBitSet`, making a
lot of that code nicer.
- Both set_up_to() and clear_above() were overly general, working with
arbitrary sizes when they are only needed for the domain size. The
commit removes the former, degeneralizes the latter, and removes the
(overly general) tests.
- Changes `GrowableBitSet::grow()` to `ensure()`, fixing a bug where a
(1-based) domain size was confused with a (0-based) element index.
- Changes `BitMatrix` to store its row count, and do more precise bounds
checks with it.
- Changes `ty_params` in `select.rs` from a `BitSet` to a
`GrowableBitSet` because it repeatedly failed the new, more precise
bounds checks. (Changing the type was simpler than computing an
accurate domain size.)
- Various other minor improvements.
|
|
This requires adding a few extra methods to `HybridBitSet`. (These are
tested in a new unit test.)
This commit reduces the `max-rss` for `nll-check` builds of `html5ever`
by 46%, `ucd` by 45%, `clap-rs` by 23%, `inflate` by 14%. And the
results for the `unic-ucd-name` crate are even more impressive: a 21%
reduction in instructions, a 60% reduction in wall-time, a 96%
reduction in `max-rss`, and a 97% reduction in faults!
Fixes #52028.
|
|
`SparseBitSet` is the only remaining user of `ArrayVec`. This commit
switches it to using `SmallVec`, and removes `array_vec.rs`.
Why the switch? Although `SparseBitSet` is size-limited and doesn't need
the ability to spill to the heap, `SmallVec` has many more features than
`ArrayVec`. In particular, it's now possible to keep `SparseBitSet`'s
elements in sorted order, which gives in-order iteration, which is a
requirement for the next commit.
|
|
|
|
- Rename `BitSet::data` and `BitMatrix::vector` as `words`, because that's
what they are.
- Remove `BitSet::words_mut()`, which is no longer necessary.
- Better distinguish multiple meanins of "word", i.e. "word index" vs
"word ref" vs "word" (i.e. the value itself).
|
|
`BitwiseOperator` is an unnecessarily low-level thing. This commit
replaces it with `BitSetOperator`, which works on `BitSet`s instead of
words. Within `bit_set.rs`, the commit eliminates `Intersect`, `Union`,
and `Subtract` by instead passing a function to `bitwise()`.
|
|
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.
|
|
Remove bitslice.rs
As the comment in `bitslice.rs` says:
> FIXME: merge with `bitvec`
|
|
Add forever unstable attribute to allow specifying arbitrary scalar ranges
r? @eddyb for the first commit and @nikomatsakis for the second one
|
|
Fix compiling some rustc crates to wasm
I was dabbling recently seeing what it would take to compile `rustfmt` to the
`wasm32-unknown-unknown` target and it turns out not much effort is needed!
Currently `rustfmt` depends on a few rustc crates published to crates.io, so
this commit touches up those crates to compile for wasm themselves. Notably:
* The `rustc_data_structures` crate's `flock` implementation is stubbed out to
unconditionally return errors on unsupported platforms.
* The `rustc_errors` crate is extended to not do any locking for all non-windows
platforms.
In both of these cases if we port the compiler to new platforms the
functionality isn't critical but will be discovered over time as it comes up, so
this hopefully doesn't make it too too hard to compile to new platforms!
|
|
Because they're just thin wrappers around `BitIter` and `slice::Iter`.
|
|
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.
|
|
Co-authored-by: nikomatsakis
|
|
|
|
|
|
|
|
|
|
This reverts (part of) commit cb9a336ae2cf6a75fdcc130853286349cb424c96.
|
|
|
|
|
|
Also, adjust the MAX to be `u32::MAX - 1`, leaving room for `u32::MAX`
to become a sentinel value in the future.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I was dabbling recently seeing what it would take to compile `rustfmt` to the
`wasm32-unknown-unknown` target and it turns out not much effort is needed!
Currently `rustfmt` depends on a few rustc crates published to crates.io, so
this commit touches up those crates to compile for wasm themselves. Notably:
* The `rustc_data_structures` crate's `flock` implementation is stubbed out to
unconditionally return errors on unsupported platforms.
* The `rustc_errors` crate is extended to not do any locking for all non-windows
platforms.
In both of these cases if we port the compiler to new platforms the
functionality isn't critical but will be discovered over time as it comes up, so
this hopefully doesn't make it too too hard to compile to new platforms!
|
|
Fix issue #52475: Make loop detector only consider reachable memory
As [suggested](https://github.com/rust-lang/rust/pull/51702#discussion_r197585664) by @oli-obk `alloc_id`s should be ignored by traversing all `Allocation`s in interpreter memory at a given moment in time, beginning by `ByRef` locals in the stack.
- [x] Generalize the implementation of `Hash` for `EvalSnapshot` to traverse `Allocation`s
- [x] Generalize the implementation of `PartialEq` for `EvalSnapshot` to traverse `Allocation`s
- [x] Commit regression tests
Fixes #52626
Fixes https://github.com/rust-lang/rust/issues/52849
|
|
|
|
|
|
Replace usages of 'bad_style' with 'nonstandard_style'.
`bad_style` is being deprecated in favor of `nonstandard_style`:
- https://github.com/rust-lang/rust/issues/41646
|
|
Use FxHash{Map,Set} instead of the default Hash{Map,Set} everywhere in rustc.
Most of the compiler uses the `Fx` hasher but some places ended up with the default one.
|
|
`bad_style` is being deprecated in favor of `nonstandard_style`:
- https://github.com/rust-lang/rust/issues/41646
|
|
It's basically just a less capable version of `SmallVec`.
|
|
|
|
NLL: experiment with inverting liveness
I got inspired to see what would happen here.
Fixes #52460
r? @pnkfelix
|
|
|
|
|
|
|
|
fix for late-bound regions
Fix for https://github.com/rust-lang/rust/issues/53419
r? @nikomatsakis
|
|
`HybridIdxSet` tweaks
A couple of tweaks to `HybridIdxSet`.
r? @nikomatsakis
|
|
Lazier sparse bit matrix
A small NLL win.
r? @nikomatsakis
|
|
|
|
They let `union()`, `union_sparse()` and `union_hybrid()` be merged.
Likewise for subtract()`, `subtract_sparse()` and `subtract_hybrid()`.
|
|
Because `domain` is a more obvious term than `universe` for this
concept.
|
|
|
