Commit graph

970 commits

Author SHA1 Message Date
Dan54
9383138801 add BinaryHeap::from_raw_vec 2026-02-11 21:18:07 +00:00
Max Heller
bae7a199f1
Address review comments and fix tests 2026-01-30 09:55:53 -05:00
Max Heller
9928723bff
Implement BinaryHeap::pop_if() 2026-01-29 10:20:34 -05:00
Stuart Cook
70e5959e48
Rollup merge of #151785 - zachs18:stabilize-push_mut, r=jhpratt
Stabilize feature(push_mut)

Stabilizes `feature(push_mut)`, consisting of `Vec::push_mut`, `Vec::insert_mut`, `VecDeque::push_front_mut`, `VecDeque::push_back_mut`, `VecDeque::insert_mut`, `LinkedList::push_front_mut`, and `LinkedList::push_back_mut`.

Tracking issue: https://github.com/rust-lang/rust/issues/135974

FCP completed: https://github.com/rust-lang/rust/issues/135974#issuecomment-3763973089

Release notes: https://github.com/rust-lang/rust/issues/151252
2026-01-29 19:03:32 +11:00
Zachary S
890e50de69 Stabilize feature(push_mut) 2026-01-28 10:02:49 -06:00
Jeremy Smart
b0d96492d0
fix undefined behavior in VecDeque::splice 2026-01-27 19:30:37 -05:00
Lukas Bergdoll
58be5d6620 Move assert_matches to planned stable path 2026-01-21 23:17:24 +01:00
bors
844f13103a Auto merge of #151228 - cyrgani:less-feature, r=jhpratt
remove multiple unhelpful `reason = "..."` values from `#[unstable(...)]` invocations

The vast majority of `#[unstable()]` attributes already has no explicit reason specified. This PR removes the `reason = "..."` value for the following unhelpful or meaningless reasons: 
* "recently added"
* "new API"
* "recently redesigned"
* "unstable"

An example of how the message looks with and without a reason:

```rust
fn main() {
    Vec::<()>::into_parts;
    Vec::<()>::const_make_global;
}
```

```
error[E0658]: use of unstable library feature `box_vec_non_null`: new API
 --> src/main.rs:2:5
  |
2 |     Vec::<()>::into_parts;
  |     ^^^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #130364 <https://github.com/rust-lang/rust/issues/130364> for more information
  = help: add `#![feature(box_vec_non_null)]` to the crate attributes to enable
  = note: this compiler was built on 2026-01-15; consider upgrading it if it is out of date

error[E0658]: use of unstable library feature `const_heap`
 --> src/main.rs:3:5
  |
3 |     Vec::<()>::const_make_global;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: see issue #79597 <https://github.com/rust-lang/rust/issues/79597> for more information
  = help: add `#![feature(const_heap)]` to the crate attributes to enable
  = note: this compiler was built on 2026-01-15; consider upgrading it if it is out of date
```

Most of the remaining reasons after this are something similar to "this is an implementation detail for XYZ" or "this is not public". If this PR is approved, I'll look into those next. 

The PR also removes the `fd_read` feature gate. It only consists of one attribute applied to an implementation inside a module that is already private and unstable and should not be needed.
2026-01-17 06:27:42 +00:00
cyrgani
69da4016aa remove reason = "new API" from #[unstable(...)] 2026-01-16 13:34:34 +00:00
Jonathan Brouwer
91429523f1
Rollup merge of #149408 - aatifsyed/binary-heap-no-ord, r=tgross35,dtolnay
refactor: remove Ord bound from BinaryHeap::new etc

This adds consistency with e.g `BTreeMap::new`, and makes it easier to e.g `#[derive(Default)]`[^1]

[^1]: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=f848e472a176fae155f17455bdfe0aee
2026-01-14 11:05:36 +01:00
bors
74fd7516da Auto merge of #147893 - fee1-dead-contrib:constheapheapheap, r=oli-obk
`Vec::push` in consts MVP

Example:

```rust
const X: &'static [u32] = {
    let mut v = Vec::with_capacity(6);
    let mut x = 1;
    while x < 42 {
        v.push(x);
        x *= 2;
    }
    assert!(v.len() == 6);
    v.const_make_global()
};

assert_eq!([1, 2, 4, 8, 16, 32], X);
```

Oh this is fun...

* We split out the implementation of `Global` such that it calls `intrinsics::const_allocate` and `intrinsics::const_deallocate` during compile time. This is achieved using `const_eval_select`
* This allows us to `impl const Allocator for Global`
* We then constify everything necessary for `Vec::with_capacity` and `Vec::push`.
* Added `Vec::const_make_global` to leak and intern the final value via `intrinsics::const_make_global`. If we see any pointer in the final value of a `const` that did not call `const_make_global`, we error as implemented in rust-lang/rust#143595.

r? `@rust-lang/wg-const-eval`

To-do for me:
* [x] Assess the rustdoc impact of additional bounds in the method
* [x] ~~Increase test coverage~~ I think this is enough for an unstable feature.
2026-01-06 11:39:17 +00:00
Matthias Krüger
9dd3b2358e
Rollup merge of #150597 - antonilol:extend-from-vec-any-allocator, r=jhpratt
make specialization of `Vec::extend` and `VecDeque::extend_front` work for vec::IntoIter with any `Allocator`, not just `Global`

These functions consume all the elements from the respective collection, but do not care about the `Allocator` they use. Without specifying one (like in `vec::IntoIter<T>`) the specialization is only chosen when `A=Global`.

(extra context: `VecDeque::extend_front` is unstable and tracked by rust-lang/rust#146975)
2026-01-04 16:16:10 +01:00
Antoni Spaanderman
9a170fedd7
make specialization of Vec::extend and VecDeque::extend_front work for vec::IntoIter with any Allocator, not just Global 2026-01-02 16:15:40 +01:00
Antoni Spaanderman
7e425b8985
Add specialization for deque1.prepend(deque2.drain(range))
This is used when moving elements between `VecDeque`s
This pattern is also used in examples of `VecDeque::prepend`. (see its docs)
2026-01-02 16:05:42 +01:00
Deadbeef
3982d3e706 Vec::push in consts MVP 2026-01-01 19:17:11 -05:00
bors
0e89999425 Auto merge of #147247 - Qelxiros:vecdeque_splice, r=Mark-Simulacrum
add VecDeque::splice

Tracking issue: rust-lang/rust#146975
2025-12-30 19:18:37 +00:00
Jonathan Brouwer
596e1e3f88
Rollup merge of #150344 - hkBst:cleanup-linked-list, r=jhpratt
Cleanup linked list

 - Replaces some checked_sub().unwrap_or(0) with saturating_sub().
 - Replaces NonNull::from(Box::leak(node)) with Box::into_non_null(node)
2025-12-30 10:42:28 +01:00
Marijn Schouten
eea3d794ff LinkedList: use Box::into_non_null_with_allocator 2025-12-29 19:08:34 +00:00
Jeremy Smart
0763954226
add VecDeque::splice 2025-12-29 13:25:56 -05:00
bors
9f54abeeba Auto merge of #150076 - heathdutton:fix-linked-list-cursor-pop-front-index, r=Mark-Simulacrum
Fix `LinkedList::CursorMut::pop_front` to correctly update index

When `pop_front` was called while the cursor pointed to the front element, `move_next` incremented the index but it was never decremented afterwards, causing the index to incorrectly report 1 instead of 0.

Always decrement the index after popping from front using `saturating_sub` to handle edge cases safely.

Fixes rust-lang/rust#147616
2025-12-28 15:10:14 +00:00
Marijn Schouten
9b2d03bd60 .checked_sub(1).unwrap_or(0) → .saturating_sub(1) 2025-12-24 11:37:54 +00:00
Boxy Uwu
90a33f69f4 replace version placeholder 2025-12-19 15:04:30 -08:00
Heath Dutton🕴️
901fe3f804 Fix LinkedList::CursorMut::pop_front to correctly update index
When `pop_front` was called while the cursor pointed to the front
element, `move_next` incremented the index but it was never decremented
afterwards, causing the index to incorrectly report 1 instead of 0.

Always decrement the index after popping from front using
`saturating_sub` to handle edge cases safely.
2025-12-17 15:42:47 -05:00
Esteban Küber
0488690d3e Use let...else instead of match foo { ... _ => return }; and if let ... else return in std 2025-12-09 23:35:14 +00:00
bors
646a3f8c15 Auto merge of #149125 - zachs18:btreemap-eq-perf, r=workingjubilee
In `BTreeMap::eq`, do not compare the elements if the sizes are different.

Reverts rust-lang/rust#147101 in library/alloc/src/btree/

rust-lang/rust#147101 replaced some instances of code like `a.len() == b.len() && a.iter().eq(&b)` with just `a.iter().eq(&b)`, but the optimization that PR introduced only applies for `TrustedLen` iterators, and `BTreeMap`'s itertors are not `TrustedLen`, so this theoretically regressed perf for comparing large `BTreeMap`/`BTreeSet`s with unequal lengths but equal prefixes, (and also made it so that comparing two different-length `BTreeMap`/`BTreeSet`s with elements whose `PartialEq` impls that can panic now can panic, though this is not a "promised" behaviour either way (cc rust-lang/rust#149122))

Given that `TrustedLen` is an unsafe trait, I opted to not implement it for `BTreeMap`'s iterators, and instead just revert the change. If someone else wants to audit `BTreeMap`'s iterators to make sure they always return the right number of items (even in the face of incorrect user `Ord` impls) and then implement `TrustedLen` for them so that the optimization works for them, then this can be closed in favor of that (or if the perf regression is deemed too theoretical, this can be closed outright).

Example of theoretical perf regression: https://play.rust-lang.org/?version=beta&mode=release&edition=2024&gist=a37e3d61e6bf02669b251315c9a44fe2 (very rough estimates, using `Instant::elapsed`).
In release mode on stable the comparison takes ~23.68µs.
In release mode on beta/nightly the comparison takes ~48.351057ms.
2025-12-02 17:04:58 +00:00
Stuart Cook
dbb92adfc1
Rollup merge of #145628 - tinnamchoi:fix-btree-append, r=Amanieu
[std][BTree] Fix behavior of `::append` to match documentation, `::insert`, and `::extend`

Resolves rust-lang/rust#145614
2025-12-02 13:56:29 +11:00
Aatif Syed
fcf24266b4 fix: BinaryHeap<T: Ord>::peek_mut 2025-11-28 01:19:07 +00:00
Aatif Syed
845da88381 refactor: remove Ord bound from BinaryHeap::new etc 2025-11-28 00:52:38 +00:00
Yotam Ofek
6d05636645 Add impl TrustedLen on BTree{Map,Set} iterators 2025-11-27 14:48:18 +02:00
chiri
3386da8f6f
Move safe computation out of unsafe block 2025-11-21 22:52:19 +03:00
Zachary S
4adcdbb58b In BTreeMap::eq, do not compare the elements if the sizes are different.
Reverts 68a7c25078 in library/
2025-11-19 22:49:44 -06:00
Ralf Jung
fc07052f8b add must_use to extract_if methods 2025-11-16 15:57:23 +01:00
joboet
5fb5861765
(almost) get rid of the unsound #[rustc_unsafe_specialization_marker] on Copy, introduce TrivialClone 2025-11-09 15:51:25 +01:00
Jacob Pratt
4ad5a39183
Rollup merge of #147808 - hkBst:btree-3, r=joboet
btree: cleanup difference, intersection, is_subset
2025-11-07 00:21:19 -05:00
Jacob Pratt
47eeb00a63
Rollup merge of #145992 - GrigorenkoPV:stabilize/vec_deque_pop_if, r=Amanieu
Stabilize `vec_deque_pop_if`

Tracking issue: rust-lang/rust#135889
Closes rust-lang/rust#135889
Also fixes a typo mentioned in https://github.com/rust-lang/rust/issues/135889#issuecomment-2991213248

FCP: https://github.com/rust-lang/rust/issues/135889#issuecomment-3238777731

`@rustbot` label -T-libs +T-libs-api +needs-fcp +S-waiting-on-fcp

r? t-libs-api
2025-11-07 00:21:17 -05:00
Marijn Schouten
acd0294845 btree: cleanup difference, intersection, is_subset 2025-11-04 15:37:54 +00:00
Antoni Spaanderman
5b96677adb
add specialization for extend_front and prepend with copied slice iterator 2025-11-03 12:35:30 +01:00
Antoni Spaanderman
e23c1551a7
implement VecDeque extend_front and prepend, add tests 2025-11-01 18:30:01 +01:00
Matthias Krüger
c42f8eb2ad
Rollup merge of #147780 - tisonkun:vec-deque-extract-if, r=joboet
Implement VecDeque::extract_if

This refers to https://github.com/rust-lang/rust/issues/147750.
2025-10-31 18:41:49 +01:00
Matthias Krüger
53c52a2ae4
Rollup merge of #147161 - antonilol:vec-deque-extend-from-within, r=joboet
implement VecDeque extend_from_within and prepend_from_within

Tracking issue: rust-lang/rust#146975
2025-10-31 18:41:48 +01:00
tison
06a2e72109
Implement VecDeque::extract_if
Signed-off-by: tison <wander4096@gmail.com>
2025-10-31 21:37:36 +08:00
Josh Stone
f25ca45fd1 Update CURRENT_RUSTC_VERSION post-bump
(cherry picked from commit 813072186c)
2025-10-28 13:22:00 -07:00
Pavel Grigorenko
2f4813fa0a Stabilize vec_deque_pop_if 2025-10-23 23:43:59 +03:00
Antoni Spaanderman
63bb238e5d
implement VecDeque extend_from_within and prepend_from_within, add tests 2025-10-23 13:52:55 +02:00
bors
4d94478977 Auto merge of #147826 - Muscraft:update-typos, r=Noratrieb
Update typos

I saw that `typos` was a few versions out of date and figured it would be a good idea to update it. Upgrading to `1.38.1` adds the [July](https://github.com/crate-ci/typos/issues/1331), [August](https://github.com/crate-ci/typos/issues/1345), and [September](https://github.com/crate-ci/typos/issues/1370) dictionary updates. As part of this change, I also sorted the configuration file.
2025-10-22 13:11:47 +00:00
Scott Schafer
12f6b9697f
chore: Update typos to 1.38.1 2025-10-20 12:20:15 -06:00
Marijn Schouten
7c95768dbd btree: some cleanup with less unsafe 2025-10-17 16:43:01 +00:00
Kivooeo
8fcb7e18c1 extended doc comment 2025-10-01 21:22:53 +00:00
Yotam Ofek
68a7c25078 Use Iterator::eq and (dogfood) eq_by in compiler and library 2025-09-29 08:08:05 +03:00
bors
c7f6aa2869 Auto merge of #147042 - Noratrieb:untrack-caller-vec, r=tgross35
Remove most `#[track_caller]` from allocating Vec methods

They cause significant binary size overhead while contributing little value.

closes rust-lang/rust#146963, see that issue for more details.
2025-09-28 03:23:45 +00:00