Merging upstream version 1.70.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 35 insertions, 56 deletions

diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs
index f1d0a305d..2c089bb31 100644
--- a/library/alloc/src/collections/binary_heap/mod.rs
+++ b/library/alloc/src/collections/binary_heap/mod.rs
@@ -144,7 +144,7 @@
 #![stable(feature = "rust1", since = "1.0.0")]
 
 use core::fmt;
-use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
+use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen};
 use core::mem::{self, swap, ManuallyDrop};
 use core::num::NonZeroUsize;
 use core::ops::{Deref, DerefMut};
@@ -154,8 +154,6 @@ use crate::collections::TryReserveError;
 use crate::slice;
 use crate::vec::{self, AsVecIntoIter, Vec};
 
-use super::SpecExtend;
-
 #[cfg(test)]
 mod tests;
 
@@ -265,7 +263,6 @@ mod tests;
 /// more detailed analysis.
 ///
 /// [`core::cmp::Reverse`]: core::cmp::Reverse
-/// [`Ord`]: core::cmp::Ord
 /// [`Cell`]: core::cell::Cell
 /// [`RefCell`]: core::cell::RefCell
 /// [push]: BinaryHeap::push
@@ -400,6 +397,17 @@ impl<T: fmt::Debug> fmt::Debug for BinaryHeap<T> {
     }
 }
 
+struct RebuildOnDrop<'a, T: Ord> {
+    heap: &'a mut BinaryHeap<T>,
+    rebuild_from: usize,
+}
+
+impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> {
+    fn drop(&mut self) {
+        self.heap.rebuild_tail(self.rebuild_from);
+    }
+}
+
 impl<T: Ord> BinaryHeap<T> {
     /// Creates an empty `BinaryHeap` as a max-heap.
     ///
@@ -837,7 +845,6 @@ impl<T: Ord> BinaryHeap<T> {
     /// Basic usage:
     ///
     /// ```
-    /// #![feature(binary_heap_retain)]
     /// use std::collections::BinaryHeap;
     ///
     /// let mut heap = BinaryHeap::from([-10, -5, 1, 2, 4, 13]);
@@ -846,35 +853,24 @@ impl<T: Ord> BinaryHeap<T> {
     ///
     /// assert_eq!(heap.into_sorted_vec(), [-10, 2, 4])
     /// ```
-    #[unstable(feature = "binary_heap_retain", issue = "71503")]
+    #[stable(feature = "binary_heap_retain", since = "1.70.0")]
     pub fn retain<F>(&mut self, mut f: F)
     where
         F: FnMut(&T) -> bool,
     {
-        struct RebuildOnDrop<'a, T: Ord> {
-            heap: &'a mut BinaryHeap<T>,
-            first_removed: usize,
-        }
-
-        let mut guard = RebuildOnDrop { first_removed: self.len(), heap: self };
-
+        // rebuild_start will be updated to the first touched element below, and the rebuild will
+        // only be done for the tail.
+        let mut guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
         let mut i = 0;
+
         guard.heap.data.retain(|e| {
             let keep = f(e);
-            if !keep && i < guard.first_removed {
-                guard.first_removed = i;
+            if !keep && i < guard.rebuild_from {
+                guard.rebuild_from = i;
             }
             i += 1;
             keep
         });
-
-        impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> {
-            fn drop(&mut self) {
-                // data[..first_removed] is untouched, so we only need to
-                // rebuild the tail:
-                self.heap.rebuild_tail(self.first_removed);
-            }
-        }
     }
 }
 
@@ -1421,7 +1417,6 @@ impl<T> FusedIterator for Iter<'_, T> {}
 /// (provided by the [`IntoIterator`] trait). See its documentation for more.
 ///
 /// [`into_iter`]: BinaryHeap::into_iter
-/// [`IntoIterator`]: core::iter::IntoIterator
 #[stable(feature = "rust1", since = "1.0.0")]
 #[derive(Clone)]
 pub struct IntoIter<T> {
@@ -1468,6 +1463,20 @@ impl<T> ExactSizeIterator for IntoIter<T> {
 #[stable(feature = "fused", since = "1.26.0")]
 impl<T> FusedIterator for IntoIter<T> {}
 
+#[stable(feature = "default_iters", since = "1.70.0")]
+impl<T> Default for IntoIter<T> {
+    /// Creates an empty `binary_heap::IntoIter`.
+    ///
+    /// ```
+    /// # use std::collections::binary_heap;
+    /// let iter: binary_heap::IntoIter<u8> = Default::default();
+    /// assert_eq!(iter.len(), 0);
+    /// ```
+    fn default() -> Self {
+        IntoIter { iter: Default::default() }
+    }
+}
+
 // In addition to the SAFETY invariants of the following three unsafe traits
 // also refer to the vec::in_place_collect module documentation to get an overview
 #[unstable(issue = "none", feature = "inplace_iteration")]
@@ -1715,7 +1724,8 @@ impl<'a, T> IntoIterator for &'a BinaryHeap<T> {
 impl<T: Ord> Extend<T> for BinaryHeap<T> {
     #[inline]
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        <Self as SpecExtend<I>>::spec_extend(self, iter);
+        let guard = RebuildOnDrop { rebuild_from: self.len(), heap: self };
+        guard.heap.data.extend(iter);
     }
 
     #[inline]
@@ -1729,37 +1739,6 @@ impl<T: Ord> Extend<T> for BinaryHeap<T> {
     }
 }
 
-impl<T: Ord, I: IntoIterator<Item = T>> SpecExtend<I> for BinaryHeap<T> {
-    default fn spec_extend(&mut self, iter: I) {
-        self.extend_desugared(iter.into_iter());
-    }
-}
-
-impl<T: Ord> SpecExtend<Vec<T>> for BinaryHeap<T> {
-    fn spec_extend(&mut self, ref mut other: Vec<T>) {
-        let start = self.data.len();
-        self.data.append(other);
-        self.rebuild_tail(start);
-    }
-}
-
-impl<T: Ord> SpecExtend<BinaryHeap<T>> for BinaryHeap<T> {
-    fn spec_extend(&mut self, ref mut other: BinaryHeap<T>) {
-        self.append(other);
-    }
-}
-
-impl<T: Ord> BinaryHeap<T> {
-    fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        let iterator = iter.into_iter();
-        let (lower, _) = iterator.size_hint();
-
-        self.reserve(lower);
-
-        iterator.for_each(move |elem| self.push(elem));
-    }
-}
-
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BinaryHeap<T> {
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {