| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Closes #60271.
|
|
|
|
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
|
|
Document time of back operations of a Linked List
Popping and pushing from the end of a linked list is constant time. This
documentation is already there for popping and pushing from the front.
@bors: r+ 38fe8d2 rollup
|
|
Fix BTreeMap UB
BTreeMap currently causes UB by created a shared reference to a too-small allocation. This PR fixes that by introducing a `NodeHeader` type and using that until we really need access to the key/value arrays. Avoiding run-time checks in `into_key_slice` was somewhat tricky, see the comments embedded in the code.
I also adjusted `as_leaf_mut` to return a raw pointer, because creating a mutable reference asserts that there are no aliases to the pointee, but that's not always correct: We use `as_leaf_mut` twice to create two mutable slices for keys and values; the second call overlaps with the first slice and hence is not a unique pointer.
Fixes https://github.com/rust-lang/rust/issues/54957
Cc @nikomatsakis @Gankro
|
|
|
|
|
|
VecDeque: fix for stacked borrows
`VecDeque` violates a version of stacked borrows where creating a shared reference is not enough to make a location *mutably accessible* from raw pointers (and I think that is the version we want). There are two problems:
* Creating a `NonNull<T>` from `&mut T` goes through `&T` (inferred for a `_`), then `*const T`, then `NonNull<T>`. That means in this stricter version of Stacked Borrows, we cannot actually write to such a `NonNull` because it was created from a shared reference! This PR fixes that by going from `&mut T` to `*mut T` to `*const T`.
* `VecDeque::drain` creates the `Drain` struct by *first* creating a `NonNull` from `self` (which is an `&mut VecDeque`), and *then* calling `self.buffer_as_mut_slice()`. The latter reborrows `self`, asserting that `self` is currently the unique pointer to access this `VecDeque`, and hence invalidating the `NonNull` that was created earlier. This PR fixes that by instead using `self.buffer_as_slice()`, which only performs read accesses and creates only shared references, meaning the raw pointer (`NonNull`) remains valid.
It is possible that other methods on `VecDeque` do something similar, miri's test coverage of `VecDeque` is sparse to say the least.
Cc @nikomatsakis @Gankro
|
|
Co-Authored-By: RalfJung <post@ralfj.de>
|
|
Popping and pushing from the end of a linked list is constant time. This
documentation is already there for popping and pushing from the front.
@bors: r+ 38fe8d2 rollup
|
|
|
|
|
|
|
