| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Stabilize vecdeque_rotate
This PR stabilizes the vecdeque_rotate feature.
r? @scottmcm
Closes https://github.com/rust-lang/rust/issues/56686
|
|
Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators
Provided a `DoubleEndedIterator` has finite length, `Iterator::last` is equivalent to `DoubleEndedIterator::next_back`. But searching forwards through the iterator when it's unnecessary is obviously not good for performance. I ran into this on one of the collection iterators.
I tried adding appropriate overloads for a bunch of the iterator adapters like filter, map, etc, but I ran into a lot of type inference failures after doing so.
The other interesting case is what to do with `Repeat`. Do we consider it part of the contract that `Iterator::last` will loop forever on it? The docs do say that the iterator will be evaluated until it returns None. This is also relevant for the adapters, it's trivially easy to observe whether a `Map` adapter invoked its closure a zillion times or just once for the last element.
|
|
Document the order of {Vec,VecDeque,String}::retain
It's natural for `retain` to work in order from beginning to end, but
this wasn't actually documented to be the case. If we actually promise
this, then the caller can do useful things like track the index of each
element being tested, as [discussed in the forum][1]. This is now
documented for `Vec`, `VecDeque`, and `String`.
[1]: https://users.rust-lang.org/t/vec-retain-by-index/27697
`HashMap` and `HashSet` also have `retain`, and the `hashbrown`
implementation does happen to use a plain `iter()` order too, but it's
not certain that this should always be the case for these types.
r? @scottmcm
|
|
|
|
|
|
|
|
|
|
It's natural for `retain` to work in order from beginning to end, but
this wasn't actually documented to be the case. If we actually promise
this, then the caller can do useful things like track the index of each
element being tested, as [discussed in the forum][1]. This is now
documented for `Vec`, `VecDeque`, and `String`.
[1]: https://users.rust-lang.org/t/vec-retain-by-index/27697
`HashMap` and `HashSet` also have `retain`, and the `hashbrown`
implementation does happen to use a plain `iter()` order too, but it's
not certain that this should always be the case for these types.
|
|
... but leave the old names in there for backwards compatibility.
|
|
Closes #60271.
|
|
|
|
DoubleEndedIterators.
r?Manishearth
|
|
fix LinkedList invalidating mutable references
The test `test_insert_prev` failed in Miri due to what I consider a bug in `LinkedList`: in various places, `NonNull::as_mut` got called to modify the `prev`/`next` pointers of existing nodes. In particular, the unstable `insert_next` has to modify the `next` pointer of the node that was last handed out by the iterator; to this end it creates a mutable reference to the *entire node* that overlaps with the mutable reference to the node's content that was handed out by the iterator! Thus, the next use if said mutable reference is UB.
In code:
```rust
loop {
match it.next() { // mutable reference handed to us
None => break,
Some(elt) => {
it.insert_next(*elt + 1); // this invalidates `elt` because it creates an overlapping mutable reference
match it.peek_next() {
Some(x) => assert_eq!(*x, *elt + 2), // this use of `elt` now is a use of an invalid pointer
None => assert_eq!(8, *elt),
}
}
}
}
```
This PR fixes that by using `as_ptr` instead of `as_mut`. This avoids invalidating the mutable reference that was handed to the user. I did this in all methods called by iterators, just to be sure.
Cc @Gankro
|
|
|
|
|
|
|
|
This updates the `Extend` implementations to use `for_each` for many
collections: `BinaryHeap`, `BTreeMap`, `BTreeSet`, `LinkedList`, `Path`,
`TokenStream`, `VecDeque`, and `Wtf8Buf`.
Folding with `for_each` enables better performance than a `for`-loop for
some iterators, especially if they can just forward to internal
iterators, like `Chain` and `FlatMap` do.
|
|
|
|
uninitialized -> uninit
into_initialized -> assume_init
read_initialized -> read
set -> write
|
|
Relax some Ord bounds on BinaryHeap<T>
Notably, iterators don't require any trait bounds to be iterated.
|
|
fix overlapping references in BTree
This fixes two kinds of overlapping references in BTree (both found by running the BTree test suite in Miri).
In `into_slices_mut`, we did `k.into_key_slice_mut()` followed by `self.into_val_slice_mut()` (where `k` is a copy of `self`). Calling `into_val_slice_mut` calls `self.len()`, which creates a shared reference to `NodeHeader`, which unfortunately (due to padding) overlaps with the mutable reference returned by `into_key_slice_mut`. Hence the key slice got (partially) invalidated. The fix is to avoid creating an `&NodeHeader` after the first slice got created.
In the iterators, we used to first create the references that will be returned, and then perform the walk on the tree. Walking the tree creates references (such as `&mut InternalNode`) that overlap with all of the keys and values stored in a pointer; in particular, they overlap with the references the iterator will later return. This is fixed by reordering the operations of walking the tree and obtaining the inner references.
The test suite still passes (and it passes in Miri now!), but there is a lot of code here that I do not understand...
|
|
override `VecDeque::try_rfold`, also update iterator
This keeps the slice based iteration and updates the iterator state after each slice. It also uses a loop to reduce the amount of code.
This uses unsafe code, so some thorough review would be appreciated. Cc @RalfJung
|
|
Use more impl header lifetime elision
Inspired by seeing explicit lifetimes on these two:
- https://doc.rust-lang.org/nightly/std/slice/struct.Iter.html#impl-FusedIterator
- https://doc.rust-lang.org/nightly/std/primitive.u32.html#impl-Not
And a follow-up to https://github.com/rust-lang/rust/pull/54687, that started using IHLE in libcore.
Most of the changes in here fall into two big categories:
- Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop`, `Debug`, and `Clone`)
- Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`)
I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations [where the flipped one cannot elide the lifetime](https://internals.rust-lang.org/t/impl-type-parameter-aliases/9403/2?u=scottmcm).
I also removed two lifetimes that turned out to be completely unused; see https://github.com/rust-lang/rust/issues/41960#issuecomment-464557423
|
|
This keeps the slice based iteration and updates the iterator
state after each slice. It also uses a loop to reduce the amount
of code.
This uses unsafe code, so some thorough review would be
appreciated.
|
|
There are two big categories of changes in here
- Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop` & `Debug`)
- Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`)
I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations where the flipped one cannot elide the lifetime.
|
|
|
|
|
|
|
|
Notably, iterators don't require any trait bounds to be iterated.
|
|
|
|
|
|
Avoid some bounds checks in binary_heap::{PeekMut,Hole}
Fixes #58121.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Add example of using the indexing operator to HashMap docs
Fixes #52575
|
|
|
|
Stabilize Vec(Deque)::resize_with
Closes #41758
|
|
Add unstable VecDeque::rotate_{left|right}
Like the ones on slices, but more efficient because vecdeque is a circular buffer.
Issue that proposed this: https://github.com/rust-lang/rust/issues/56686
~~:bomb: Please someone look very carefully at the `unsafe` in this! The `wrap_copy` seems to be exactly what this method needs, and the `len` passed to it is never more than half the length of the deque, but I haven't managed to prove to myself that it's correct :bomb:~~ I think I proved that this code meets the requirement of the unsafe code it's calling; please double-check, of course.
|
|
Closes #41758
|
