rust/src/liballoc/collections/btree, branch 1.37.0

Revert "Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators."

2019-05-22T21:09:34+00:00

This reverts commit 3e86cf36b5114f201868bf459934fe346a76a2d4.

Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators.

2019-04-20T04:52:43+00:00

r?Manishearth

Use for_each to extend collections

2019-04-05T21:51:07+00:00

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.

improve worst-case performance of BTreeSet difference and intersection

2019-03-29T11:18:20+00:00

adjust MaybeUninit API to discussions

2019-03-26T08:21:32+00:00

uninitialized -> uninit into_initialized -> assume_init read_initialized -> read set -> write

Rollup merge of #58431 - RalfJung:btree, r=Mark-Simulacrum

2019-02-22T13:58:00+00:00

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...

Rollup merge of #58553 - scottmcm:more-ihle, r=Centril

2019-02-20T03:59:10+00:00

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 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

Use more impl header lifetime elision

2019-02-18T03:42:36+00:00

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 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.

split MaybeUninit into several features, expand docs a bit

2019-02-14T19:07:57+00:00

fix invalidating references in BTree iterators

2019-02-13T16:25:41+00:00