about summary refs log tree commit diff
path: root/compiler/rustc_index/src/bit_set.rs
AgeCommit message (Collapse)AuthorLines
2025-09-21Rollup merge of #144091 - thaliaarchi:stabilize-new-zeroed, r=Mark-SimulacrumStuart Cook-2/+2
Stabilize `new_zeroed_alloc` The corresponding `new_uninit` and `new_uninit_slice` functions were stabilized in rust-lang/rust#129401, but the zeroed counterparts were left for later out of a [desire](https://github.com/rust-lang/rust/issues/63291#issuecomment-2161039756) to stabilize only the minimal set. These functions are straightforward mirrors of the uninit functions and well-established. Since no blockers or design questions have surfaced in the past year, I think it's time to stabilize them. Tracking issue: rust-lang/rust#129396
2025-08-24Update documentation.Camille Gillot-9/+3
2025-08-23Remove chunk size from each chunk.Camille GILLOT-108/+133
2025-07-19Stabilize `new_zeroed_alloc`Thalia Archibald-2/+2
2025-07-05use `div_ceil` instead of manual logicFolkert de Vries-2/+2
2025-06-04index: add method for checking range on DenseBitSetNia Espera-0/+26
2025-03-15Use {Decodable,Encodable}_NoContext in type_irMichael Goulet-4/+4
2025-03-07compiler: Use size_of from the prelude instead of importedThalia Archibald-2/+4
Use `std::mem::{size_of, size_of_val, align_of, align_of_val}` from the prelude instead of importing or qualifying them. These functions were added to all preludes in Rust 1.80.
2025-02-22Greatly simplify lifetime captures in edition 2024Michael Goulet-1/+1
2025-02-22Fix binding mode problemsMichael Goulet-16/+4
2025-01-14Add `DenseBitSet::union_not`Zalathar-0/+30
This is similar to the existing `union`, except that bits in the RHS are negated before being incorporated into the LHS. Currently only `DenseBitSet` is supported. Supporting other bitset types is possible, but non-trivial, and currently isn't needed.
2025-01-11document the use-cases of `DenseBitSet` a bit moreRémy Rakic-1/+7
2025-01-11rename `BitSet` to `DenseBitSet`Rémy Rakic-45/+49
This should make it clearer that this bitset is dense, with the advantages and disadvantages that it entails.
2024-12-29improve `bit_set` assertionRémy Rakic-1/+6
it missed the index and bounds info
2024-12-17add `MixedBitSet::clear`Rémy Rakic-0/+8
2024-12-09Use `BitSet` in `SparseBitMatrix`.Nicholas Nethercote-10/+10
A `ChunkedBitSet` has to be at least 2048 bits for it to outperform a `BitSet`, because that's the chunk size. The largest `SparseBitMatrix` encountered when compiling the compiler and the entire rustc-perf benchmark suite is less than 600 bits. This change is a tiny perf win, but the motivation is more about avoiding uses of `ChunkedBitSet` outside of `MixedBitSet`. The test change is necessary to avoid hitting the `<BitSet<T> as BitRelations<ChunkedBitSet<T>>>::subtract` method that has `unimplemented!` in its body and isn't otherwise used.
2024-12-05Introduce `MixedBitSet`.Nicholas Nethercote-0/+155
It just uses `BitSet` for small/medium sizes (<= 2048 bits) and `ChunkedBitSet` for larger sizes. This is good because `ChunkedBitSet` is slow and memory-hungry at smaller sizes.
2024-12-05Move some `BitSet` code blocks to a better place.Nicholas Nethercote-105/+105
These blocks are currently interleaved with `ChunkedBitSet` blocks. It makes things hard to find and has annoyed me for a while.
2024-11-29Remove `HybridBitSet`.Nicholas Nethercote-514/+0
It's no longer used.
2024-11-29Stop using `HybridBitSet` in `SparseBitMatrix`.Nicholas Nethercote-13/+18
Use `ChunkedBitSet` instead.
2024-11-29Speed up `ChunkedBitIter`Nicholas Nethercote-55/+40
The current implementation is slow because it does an operation for every bit in the set, even zero bits. So if you have a large bitset with many zero bits (which is common) it's very slow. This commit improves the iterator to skip over `Zeros` chunks in a single step, and uses the fast `BitIter` for `Mixed` chunks. It also removes the existing `fold` implementation, which was only there because the old iterator was slow.
2024-11-29Tiny `ChunkedBitSet` improvements.Nicholas Nethercote-19/+16
- Fix a typo in a comment. - Remove unnecessary `Chunk::` qualifiers. - Rename `ChunkedBitIter::bitset` as `ChunkedBitIter::bit_set`, because `bit_set` is the form used everywhere else. - Avoid some unnecessary local variables.
2024-11-29Clarify `ChunkSize` invariants.Nicholas Nethercote-4/+8
`ChunkedBitSet::is_empty` currently does an unnecessary check. This commit removes that check and adds clarifying comments and an assertion that demonstrate why it's unnecessary.
2024-11-20reduce false positives of tail-expr-drop-order from consumed valuesDing Xiang Fei-4/+136
take 2 open up coroutines tweak the wordings the lint works up until 2021 We were missing one case, for ADTs, which was causing `Result` to yield incorrect results. only include field spans with significant types deduplicate and eliminate field spans switch to emit spans to impl Drops Co-authored-by: Niko Matsakis <nikomat@amazon.com> collect drops instead of taking liveness diff apply some suggestions and add explantory notes small fix on the cache let the query recurse through coroutine new suggestion format with extracted variable name fine-tune the drop span and messages bugfix on runtime borrows tweak message wording filter out ecosystem types earlier apply suggestions clippy check lint level at session level further restrict applicability of the lint translate bid into nop for stable mir detect cycle in type structure
2024-09-22Reformat using the new identifier sorting from rustfmtMichael Goulet-2/+2
2024-07-29Reformat `use` declarations.Nicholas Nethercote-8/+3
The previous commit updated `rustfmt.toml` appropriately. This commit is the outcome of running `x fmt --all` with the new formatting options.
2024-04-18Simplify `static_assert_size`s.Nicholas Nethercote-1/+1
We want to run them on all 64-bit platforms.
2024-04-03Check `x86_64` size assertions on `aarch64`, tooZalathar-1/+1
This makes it easier for contributors on aarch64 workstations (e.g. Macs) to notice when these assertions have been violated.
2024-01-22Remove uses of HybridBitSet.Camille GILLOT-2/+2
2024-01-06Auto merge of #119499 - cjgillot:dtm-opt, r=nnethercotebors-11/+5
Two small bitset optimisations
2024-01-02Reuse `bitwise` in BitMatrix.Camille GILLOT-11/+5
2023-12-31Avoid specialization for the Span Encodable and Decodable implsbjorn3-4/+4
2023-12-23Mention the relevant tracking issue next to my `bit_set` hackNadrieril-0/+2
2023-12-15Make `rustc_index::bit_set` available on stableNadrieril-11/+37
2023-11-13Remove `impl FiniteBitSetTy for {u64,u128}`.Nicholas Nethercote-48/+0
Only the impl for `u32` is used. These can be reinstated easily if needed in the future.
2023-11-13Remove `BitSet::to_hybrid`.Nicholas Nethercote-6/+0
2023-11-13Remove `BitSet::words`.Nicholas Nethercote-9/+4
2023-10-06Preserve DebugInfo in DeadStoreElimination.Camille GILLOT-1/+7
2023-07-12Re-format let-else per rustfmt updateMark Rousskov-3/+1
2023-05-24Use `Option::is_some_and` and `Result::is_ok_and` in the compilerMaybe Waffle-2/+2
2023-04-24Split `{Idx, IndexVec, IndexSlice}` into their own modulesMaybe Waffle-3/+5
2023-04-09Fix some clippy::complexityNilstrieb-1/+1
2023-03-21Use `SmallVec` in bitsetsNilstrieb-5/+7
This doesn't increase their size and means that we don't have to heap allocate for small sets.
2023-03-03Match unmatched backticks in compiler/ that are part of rustdocest31-1/+1
2023-01-05Fix `uninlined_format_args` for some compiler cratesnils-1/+1
Convert all the crates that have had their diagnostic migration completed (except save_analysis because that will be deleted soon and apfloat because of the licensing problem).
2022-12-12minor code cleanupsMatthias Krüger-1/+1
2022-07-08Fix cloning from a BitSet with a different domain sizeTomasz Miąsko-6/+2
The previous implementation incorrectly assumed that the number of words in a bit set is equal to the domain size. The new implementation delegates to `Vec::clone_from` which is specialized for `Copy` elements.
2022-07-04Use a bitset instead of a hash map in HIR ID validatorJakub Beránek-0/+10
2022-06-21Auto merge of #95576 - DrMeepster:box_erasure, r=oli-obkbors-0/+12
Remove dereferencing of Box from codegen Through #94043, #94414, #94873, and #95328, I've been fixing issues caused by Box being treated like a pointer when it is not a pointer. However, these PRs just introduced special cases for Box. This PR removes those special cases and instead transforms a deref of Box into a deref of the pointer it contains. Hopefully, this is the end of the Box<T, A> ICEs.
2022-06-15add From impls for BitSet and GrowableBitSetDrMeepster-0/+12