Auto merge of #58644 - Centril:rollup, r=Centril

Rollup of 17 pull requests

Successful merges:

 - #57656 (Deprecate the unstable Vec::resize_default)
 - #58059 (deprecate before_exec in favor of unsafe pre_exec)
 - #58064 (override `VecDeque::try_rfold`, also update iterator)
 - #58198 (Suggest removing parentheses surrounding lifetimes)
 - #58431 (fix overlapping references in BTree)
 - #58555 (Add a note about 2018e if someone uses `try {` in 2015e)
 - #58588 (remove a bit of dead code)
 - #58589 (cleanup macro after 2018 transition)
 - #58591 (Dedup a rustdoc diagnostic construction)
 - #58600 (fix small documentation typo)
 - #58601 (Search for target_triple.json only if builtin target not found)
 - #58606 (Docs: put Future trait into spotlight)
 - #58607 (Fixes #58586: Make E0505 erronous example fail for the 2018 edition)
 - #58615 (miri: explain why we use static alignment in ref-to-place conversion)
 - #58620 (introduce benchmarks of BTreeSet.intersection)
 - #58621 (Update miri links)
 - #58632 (Make std feature list sorted)

Failed merges:

r? @ghost

8 files changed, 252 insertions, 20 deletions

diff --git a/src/liballoc/benches/btree/mod.rs b/src/liballoc/benches/btree/mod.rs
index 4dc2dfd9153..095ca5dd2e2 100644
--- a/src/liballoc/benches/btree/mod.rs
+++ b/src/liballoc/benches/btree/mod.rs
@@ -1 +1,2 @@
 mod map;
+mod set;
diff --git a/src/liballoc/benches/btree/set.rs b/src/liballoc/benches/btree/set.rs
new file mode 100644
index 00000000000..08e1db5fbb7
--- /dev/null
+++ b/src/liballoc/benches/btree/set.rs
@@ -0,0 +1,88 @@
+use std::collections::BTreeSet;
+
+use rand::{thread_rng, Rng};
+use test::{black_box, Bencher};
+
+fn random(n1: u32, n2: u32) -> [BTreeSet<usize>; 2] {
+    let mut rng = thread_rng();
+    let mut set1 = BTreeSet::new();
+    let mut set2 = BTreeSet::new();
+    for _ in 0..n1 {
+        let i = rng.gen::<usize>();
+        set1.insert(i);
+    }
+    for _ in 0..n2 {
+        let i = rng.gen::<usize>();
+        set2.insert(i);
+    }
+    [set1, set2]
+}
+
+fn staggered(n1: u32, n2: u32) -> [BTreeSet<u32>; 2] {
+    let mut even = BTreeSet::new();
+    let mut odd = BTreeSet::new();
+    for i in 0..n1 {
+        even.insert(i * 2);
+    }
+    for i in 0..n2 {
+        odd.insert(i * 2 + 1);
+    }
+    [even, odd]
+}
+
+fn neg_vs_pos(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
+    let mut neg = BTreeSet::new();
+    let mut pos = BTreeSet::new();
+    for i in -(n1 as i32)..=-1 {
+        neg.insert(i);
+    }
+    for i in 1..=(n2 as i32) {
+        pos.insert(i);
+    }
+    [neg, pos]
+}
+
+fn pos_vs_neg(n1: u32, n2: u32) -> [BTreeSet<i32>; 2] {
+    let mut neg = BTreeSet::new();
+    let mut pos = BTreeSet::new();
+    for i in -(n1 as i32)..=-1 {
+        neg.insert(i);
+    }
+    for i in 1..=(n2 as i32) {
+        pos.insert(i);
+    }
+    [pos, neg]
+}
+
+macro_rules! set_intersection_bench {
+    ($name: ident, $sets: expr) => {
+        #[bench]
+        pub fn $name(b: &mut Bencher) {
+            // setup
+            let sets = $sets;
+
+            // measure
+            b.iter(|| {
+                let x = sets[0].intersection(&sets[1]).count();
+                black_box(x);
+            })
+        }
+    };
+}
+
+set_intersection_bench! {intersect_random_100,          random(100, 100)}
+set_intersection_bench! {intersect_random_10k,          random(10_000, 10_000)}
+set_intersection_bench! {intersect_random_10_vs_10k,    random(10, 10_000)}
+set_intersection_bench! {intersect_random_10k_vs_10,    random(10_000, 10)}
+set_intersection_bench! {intersect_staggered_100,       staggered(100, 100)}
+set_intersection_bench! {intersect_staggered_10k,       staggered(10_000, 10_000)}
+set_intersection_bench! {intersect_staggered_10_vs_10k, staggered(10, 10_000)}
+set_intersection_bench! {intersect_staggered_10k_vs_10, staggered(10_000, 10)}
+set_intersection_bench! {intersect_neg_vs_pos_100,      neg_vs_pos(100, 100)}
+set_intersection_bench! {intersect_neg_vs_pos_10k,      neg_vs_pos(10_000, 10_000)}
+set_intersection_bench! {intersect_neg_vs_pos_10_vs_10k,neg_vs_pos(10, 10_000)}
+set_intersection_bench! {intersect_neg_vs_pos_10k_vs_10,neg_vs_pos(10_000, 10)}
+set_intersection_bench! {intersect_pos_vs_neg_100,      pos_vs_neg(100, 100)}
+set_intersection_bench! {intersect_pos_vs_neg_10k,      pos_vs_neg(10_000, 10_000)}
+set_intersection_bench! {intersect_pos_vs_neg_10_vs_10k,pos_vs_neg(10, 10_000)}
+set_intersection_bench! {intersect_pos_vs_neg_10k_vs_10,pos_vs_neg(10_000, 10)}
diff --git a/src/liballoc/benches/vec_deque.rs b/src/liballoc/benches/vec_deque.rs
index f7aadbdbd82..7d2d3cfa612 100644
--- a/src/liballoc/benches/vec_deque.rs
+++ b/src/liballoc/benches/vec_deque.rs
@@ -45,3 +45,10 @@ fn bench_mut_iter_1000(b: &mut Bencher) {
         black_box(sum);
     })
 }
+
+#[bench]
+fn bench_try_fold(b: &mut Bencher) {
+    let ring: VecDeque<_> = (0..1000).collect();
+
+    b.iter(|| black_box(ring.iter().try_fold(0, |a, b| Some(a + b))))
+}
diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs
index 250927138b3..ce29978856f 100644
--- a/src/liballoc/collections/btree/map.rs
+++ b/src/liballoc/collections/btree/map.rs
@@ -1634,9 +1634,11 @@ impl<'a, K, V> RangeMut<'a, K, V> {
 
         let mut cur_handle = match handle.right_kv() {
             Ok(kv) => {
-                let (k, v) = ptr::read(&kv).into_kv_mut();
-                self.front = kv.right_edge();
-                return (k, v);
+                self.front = ptr::read(&kv).right_edge();
+                // Doing the descend invalidates the references returned by `into_kv_mut`,
+                // so we have to do this last.
+                let (k, v) = kv.into_kv_mut();
+                return (k, v); // coerce k from `&mut K` to `&K`
             }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
@@ -1647,9 +1649,11 @@ impl<'a, K, V> RangeMut<'a, K, V> {
         loop {
             match cur_handle.right_kv() {
                 Ok(kv) => {
-                    let (k, v) = ptr::read(&kv).into_kv_mut();
-                    self.front = first_leaf_edge(kv.right_edge().descend());
-                    return (k, v);
+                    self.front = first_leaf_edge(ptr::read(&kv).right_edge().descend());
+                    // Doing the descend invalidates the references returned by `into_kv_mut`,
+                    // so we have to do this last.
+                    let (k, v) = kv.into_kv_mut();
+                    return (k, v); // coerce k from `&mut K` to `&K`
                 }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
@@ -1680,9 +1684,11 @@ impl<'a, K, V> RangeMut<'a, K, V> {
 
         let mut cur_handle = match handle.left_kv() {
             Ok(kv) => {
-                let (k, v) = ptr::read(&kv).into_kv_mut();
-                self.back = kv.left_edge();
-                return (k, v);
+                self.back = ptr::read(&kv).left_edge();
+                // Doing the descend invalidates the references returned by `into_kv_mut`,
+                // so we have to do this last.
+                let (k, v) = kv.into_kv_mut();
+                return (k, v); // coerce k from `&mut K` to `&K`
             }
             Err(last_edge) => {
                 let next_level = last_edge.into_node().ascend().ok();
@@ -1693,9 +1699,11 @@ impl<'a, K, V> RangeMut<'a, K, V> {
         loop {
             match cur_handle.left_kv() {
                 Ok(kv) => {
-                    let (k, v) = ptr::read(&kv).into_kv_mut();
-                    self.back = last_leaf_edge(kv.left_edge().descend());
-                    return (k, v);
+                    self.back = last_leaf_edge(ptr::read(&kv).left_edge().descend());
+                    // Doing the descend invalidates the references returned by `into_kv_mut`,
+                    // so we have to do this last.
+                    let (k, v) = kv.into_kv_mut();
+                    return (k, v); // coerce k from `&mut K` to `&K`
                 }
                 Err(last_edge) => {
                     let next_level = last_edge.into_node().ascend().ok();
diff --git a/src/liballoc/collections/btree/node.rs b/src/liballoc/collections/btree/node.rs
index fc1c1878924..66d619b1298 100644
--- a/src/liballoc/collections/btree/node.rs
+++ b/src/liballoc/collections/btree/node.rs
@@ -645,6 +645,8 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
     }
 
     fn into_key_slice_mut(mut self) -> &'a mut [K] {
+        // Same as for `into_key_slice` above, we try to avoid a run-time check
+        // (the alignment comparison will usually be performed at compile-time).
         if mem::align_of::<K>() > mem::align_of::<LeafNode<(), ()>>() && self.is_shared_root() {
             &mut []
         } else {
@@ -667,9 +669,26 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> {
         }
     }
 
-    fn into_slices_mut(self) -> (&'a mut [K], &'a mut [V]) {
-        let k = unsafe { ptr::read(&self) };
-        (k.into_key_slice_mut(), self.into_val_slice_mut())
+    fn into_slices_mut(mut self) -> (&'a mut [K], &'a mut [V]) {
+        debug_assert!(!self.is_shared_root());
+        // We cannot use the getters here, because calling the second one
+        // invalidates the reference returned by the first.
+        // More precisely, it is the call to `len` that is the culprit,
+        // because that creates a shared reference to the header, which *can*
+        // overlap with the keys (and even the values, for ZST keys).
+        unsafe {
+            let len = self.len();
+            let leaf = self.as_leaf_mut();
+            let keys = slice::from_raw_parts_mut(
+                MaybeUninit::first_ptr_mut(&mut (*leaf).keys),
+                len
+            );
+            let vals = slice::from_raw_parts_mut(
+                MaybeUninit::first_ptr_mut(&mut (*leaf).vals),
+                len
+            );
+            (keys, vals)
+        }
     }
 }
 
diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs
index f778c4cbfde..4e90f783ec6 100644
--- a/src/liballoc/collections/vec_deque.rs
+++ b/src/liballoc/collections/vec_deque.rs
@@ -2170,12 +2170,29 @@ impl<'a, T> Iterator for Iter<'a, T> {
         back.iter().fold(accum, &mut f)
     }
 
-    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
-        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
+    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Ok = B>,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        let accum = front.iter().try_fold(init, &mut f)?;
-        back.iter().try_fold(accum, &mut f)
+        let (mut iter, final_res);
+        if self.tail <= self.head {
+            // single slice self.ring[self.tail..self.head]
+            iter = self.ring[self.tail..self.head].iter();
+            final_res = iter.try_fold(init, &mut f);
+        } else {
+            // two slices: self.ring[self.tail..], self.ring[..self.head]
+            let (front, back) = self.ring.split_at(self.tail);
+            let mut back_iter = back.iter();
+            let res = back_iter.try_fold(init, &mut f);
+            let len = self.ring.len();
+            self.tail = (self.ring.len() - back_iter.len()) & (len - 1);
+            iter = front[..self.head].iter();
+            final_res = iter.try_fold(res?, &mut f);
+        }
+        self.tail = self.head - iter.len();
+        final_res
     }
 }
 
@@ -2197,6 +2214,30 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
         accum = back.iter().rfold(accum, &mut f);
         front.iter().rfold(accum, &mut f)
     }
+
+    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Ok = B>,
+    {
+        let (mut iter, final_res);
+        if self.tail <= self.head {
+            // single slice self.ring[self.tail..self.head]
+            iter = self.ring[self.tail..self.head].iter();
+            final_res = iter.try_rfold(init, &mut f);
+        } else {
+            // two slices: self.ring[self.tail..], self.ring[..self.head]
+            let (front, back) = self.ring.split_at(self.tail);
+            let mut front_iter = front[..self.head].iter();
+            let res = front_iter.try_rfold(init, &mut f);
+            self.head = front_iter.len();
+            iter = back.iter();
+            final_res = iter.try_rfold(res?, &mut f);
+        }
+        self.head = self.tail + iter.len();
+        final_res
+    }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
diff --git a/src/liballoc/tests/vec_deque.rs b/src/liballoc/tests/vec_deque.rs
index e0cb0e7a9e7..16ddc1444fc 100644
--- a/src/liballoc/tests/vec_deque.rs
+++ b/src/liballoc/tests/vec_deque.rs
@@ -1465,6 +1465,15 @@ fn test_try_fold_unit() {
     assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
 }
 
+
+#[test]
+fn test_try_fold_unit_none() {
+    let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
+    let mut iter = v.into_iter();
+    assert!(iter.try_fold((), |_, _| None).is_none());
+    assert_eq!(iter.len(), 9);
+}
+
 #[test]
 fn test_try_fold_rotated() {
     let mut v: VecDeque<_> = (0..12).collect();
@@ -1477,3 +1486,58 @@ fn test_try_fold_rotated() {
         assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
     }
 }
+
+#[test]
+fn test_try_fold_moves_iter() {
+    let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
+    let mut iter = v.into_iter();
+    assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
+    assert_eq!(iter.next(), Some(&60));
+}
+
+#[test]
+fn test_try_fold_exhaust_wrap() {
+    let mut v = VecDeque::with_capacity(7);
+    v.push_back(1);
+    v.push_back(1);
+    v.push_back(1);
+    v.pop_front();
+    v.pop_front();
+    let mut iter = v.iter();
+    let _ = iter.try_fold(0, |_, _| Some(1));
+    assert!(iter.is_empty());
+}
+
+#[test]
+fn test_try_fold_wraparound() {
+    let mut v = VecDeque::with_capacity(8);
+    v.push_back(7);
+    v.push_back(8);
+    v.push_back(9);
+    v.push_front(2);
+    v.push_front(1);
+    let mut iter = v.iter();
+    let _ = iter.find(|&&x| x == 2);
+    assert_eq!(Some(&7), iter.next());
+}
+
+#[test]
+fn test_try_rfold_rotated() {
+    let mut v: VecDeque<_> = (0..12).collect();
+    for n in 0..10 {
+        if n & 1 == 0 {
+            v.rotate_left(n);
+        } else {
+            v.rotate_right(n);
+        }
+        assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
+    }
+}
+
+#[test]
+fn test_try_rfold_moves_iter() {
+    let v : VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
+    let mut iter = v.into_iter();
+    assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
+    assert_eq!(iter.next_back(), Some(&70));
+}
diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index a351d482fed..dddfa3f158e 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -1365,6 +1365,7 @@ impl<T: Default> Vec<T> {
     /// # Examples
     ///
     /// ```
+    /// # #![allow(deprecated)]
     /// #![feature(vec_resize_default)]
     ///
     /// let mut vec = vec![1, 2, 3];
@@ -1381,6 +1382,9 @@ impl<T: Default> Vec<T> {
     /// [`Default`]: ../../std/default/trait.Default.html
     /// [`Clone`]: ../../std/clone/trait.Clone.html
     #[unstable(feature = "vec_resize_default", issue = "41758")]
+    #[rustc_deprecated(reason = "This is moving towards being removed in favor \
+        of `.resize_with(Default::default)`.  If you disagree, please comment \
+        in the tracking issue.", since = "1.33.0")]
     pub fn resize_default(&mut self, new_len: usize) {
         let len = self.len();