| Age | Commit message (Collapse) | Author | Lines |
|---|
|
(cherry picked from commit 379b18bb0ab07e8f7ba04ca29ba52a1817cec1ce)
|
|
(cherry picked from commit 4a4f43e4e9b994c729a0506d921fe9734673a20a)
|
|
This adds both a test specific to #108453 as well as an exhaustive test
that goes through all possible combinations of head index, length and target capacity
for a deque with capacity 16.
(cherry picked from commit 9e22516877a2853c71456ef792fcbd9087fb905a)
|
|
|
|
|
|
|
|
|
|
|
|
Clarify examples for `VecDeque::get/get_mut`
Closes #106114
``@rustbot`` label +A-docs
|
|
Update `rand` in the stdlib tests, and remove the `getrandom` feature from it.
The main goal is actually removing `getrandom`, so that eventually we can allow running the stdlib test suite on tier3 targets which don't have `getrandom` support. Currently those targets can only run the subset of stdlib tests that exist in uitests, and (generally speaking), we prefer not to test libstd functionality in uitests, which came up recently in https://github.com/rust-lang/rust/pull/104095 and https://github.com/rust-lang/rust/pull/104185. Additionally, the fact that we can't update `rand`/`getrandom` means we're stuck with the old set of tier3 targets, so can't test new ones.
~~Anyway, I haven't checked that this actually does allow use on tier3 targets (I think it does not, as some work is needed in stdlib submodules) but it moves us slightly closer to this, and seems to allow at least finally updating our `rand` dep, which definitely improves the status quo.~~ Checked and works now.
For the most part, our tests and benchmarks are fine using hard-coded seeds. A couple tests seem to fail with this (stuff manipulating the environment expecting no collisions, for example), or become pointless (all inputs to a function become equivalent). In these cases I've done a (gross) dance (ab)using `RandomState` and `Location::caller()` for some extra "entropy".
Trying to share that code seems *way* more painful than it's worth given that the duplication is a 7-line function, even if the lines are quite gross. (Keeping in mind that sharing it would require adding `rand` as a non-dev dep to std, and exposing a type from it publicly, all of which sounds truly awful, even if done behind a perma-unstable feature).
See also some previous attempts:
- https://github.com/rust-lang/rust/pull/86963 (in particular https://github.com/rust-lang/rust/pull/86963#issuecomment-885438936 which explains why this is non-trivial)
- https://github.com/rust-lang/rust/pull/89131
- https://github.com/rust-lang/rust/pull/96626#issuecomment-1114562857 (I tried in that PR at the same time, but settled for just removing the usage of `thread_rng()` from the benchmarks, since that was the main goal).
- https://github.com/rust-lang/rust/pull/104185
- Probably more. It's very tempting of a thing to "just update".
r? `@Mark-Simulacrum`
|
|
Add O(1) `Vec -> VecDeque` conversion guarantee
(See #105072)
|
|
|
|
|
|
|
|
Test leaking of BinaryHeap Drain iterators
Add test cases about forgetting the `BinaryHeap::Drain` iterator, and slightly fortifies some other test cases.
Consists of separate commits that I don't think are relevant on their own (but I'll happily turn these into more PRs if desired).
|
|
Make `VecDeque::new` const
(See #105072)
|
|
* A few typos around generic types (`;` vs `,`)
* Use inline code formatting for code fragments
* One instance of wrong wording
|
|
|
|
|
|
|
|
Send `VecDeque::from_iter` via `Vec::from_iter`
Since it's O(1) to convert between them now, might as well reuse the logic.
Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
|
|
|
|
|
|
|
|
Since it's O(1) to convert between them now, might as well reuse the logic.
Mostly for the various specializations it does, but might also save some monomorphization work if, say, people collect slice iterators into both `Vec`s and `VecDeque`s.
|
|
Update VecDeque implementation to use head+len instead of head+tail
(See #99805)
This changes `alloc::collections::VecDeque`'s internal representation from using head and tail indices to using a head index and a length field. It has a few advantages over the current design:
* It allows the buffer to be of length 0, which means the `VecDeque::new` new longer has to allocate and could be changed to a `const fn`
* It allows the `VecDeque` to fill the buffer completely, unlike the old implementation, which always had to leave a free space
* It removes the restriction for the size to be a power of two, allowing it to properly `shrink_to_fit`, unlike the old `VecDeque`
* The above points also combine to allow the `Vec<T> -> VecDeque<T>` conversion to be very cheap and guaranteed O(1). I mention this in the `From<Vec<T>>` impl, but it's not a strong guarantee just yet, as that would likely need some form of API change proposal.
All the tests seem to pass for the new `VecDeque`, with some slight adjustments.
r? `@scottmcm`
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Today it always copies it for *every* appended element, but one of those clones is avoidable.
|
|
Bump bootstrap compiler to 1.66
This PR:
- Bumps version placeholders to release
- Bumps to latest beta
- cfg-steps code
r? `@pietroalbini`
|
|
run alloc benchmarks in Miri and fix UB
Miri since recently has a "fake monotonic clock" that works even with isolation. Its measurements are not very meaningful but it means we can run these benches and check them for UB.
And that's a good thing since there was UB here: fixes https://github.com/rust-lang/rust/issues/104096.
r? ``@thomcc``
|
|
disable btree size tests on Miri
Seems fine not to run these in Miri, they can't have UB anyway. And this lets us do layout randomization in Miri.
r? ``@thomcc``
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stabilize map_first_last
Stabilizes the following functions:
```Rust
impl<T> BTreeSet<T> {
pub fn first(&self) -> Option<&T> where T: Ord;
pub fn last(&self) -> Option<&T> where T: Ord;
pub fn pop_first(&mut self) -> Option<T> where T: Ord;
pub fn pop_last(&mut self) -> Option<T> where T: Ord;
}
impl<K, V> BTreeMap<K, V> {
pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord;
pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord;
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord;
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V>> where K: Ord;
pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord;
pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord;
}
```
Closes #62924
~~Blocked on the [FCP](https://github.com/rust-lang/rust/issues/62924#issuecomment-1179489929) finishing.~~ Edit: It finished!
|
|
|
|
|
|
|
|
|
|
Stabilize const `BTree{Map,Set}::new`
The FCP was completed in #71835.
Since `len` and `is_empty` are not const stable yet, this also creates a new feature for them since they previously used the same `const_btree_new` feature.
|
|
|
