Add VecDeque::extend from vec::IntoIter and slice::Iter specializations

4 files changed, 85 insertions, 20 deletions

diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index ab14a43fb93..5f1a6848ae6 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -54,6 +54,10 @@ use self::ring_slices::RingSlices;
 
 mod ring_slices;
 
+use self::spec_extend::SpecExtend;
+
+mod spec_extend;
+
 #[cfg(test)]
 mod tests;
 
@@ -2970,24 +2974,7 @@ impl<'a, T, A: Allocator> IntoIterator for &'a mut VecDeque<T, A> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
     fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
-        // This function should be the moral equivalent of:
-        //
-        //      for item in iter.into_iter() {
-        //          self.push_back(item);
-        //      }
-        let mut iter = iter.into_iter();
-        while let Some(element) = iter.next() {
-            if self.len() == self.capacity() {
-                let (lower, _) = iter.size_hint();
-                self.reserve(lower.saturating_add(1));
-            }
-
-            let head = self.head;
-            self.head = self.wrap_add(self.head, 1);
-            unsafe {
-                self.buffer_write(head, element);
-            }
-        }
+        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
     }
 
     #[inline]
@@ -3004,7 +2991,7 @@ impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
 #[stable(feature = "extend_ref", since = "1.2.0")]
 impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
-        self.extend(iter.into_iter().cloned());
+        self.spec_extend(iter.into_iter());
     }
 
     #[inline]
diff --git a/library/alloc/src/collections/vec_deque/spec_extend.rs b/library/alloc/src/collections/vec_deque/spec_extend.rs
new file mode 100644
index 00000000000..172f2e9068f
--- /dev/null
+++ b/library/alloc/src/collections/vec_deque/spec_extend.rs
@@ -0,0 +1,73 @@
+use crate::alloc::Allocator;
+use crate::vec;
+use core::slice;
+
+use super::VecDeque;
+
+// Specialization trait used for VecDeque::extend
+pub(super) trait SpecExtend<T, I> {
+    fn spec_extend(&mut self, iter: I);
+}
+
+impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
+where
+    I: Iterator<Item = T>,
+{
+    default fn spec_extend(&mut self, mut iter: I) {
+        // This function should be the moral equivalent of:
+        //
+        //      for item in iter {
+        //          self.push_back(item);
+        //      }
+        while let Some(element) = iter.next() {
+            if self.len() == self.capacity() {
+                let (lower, _) = iter.size_hint();
+                self.reserve(lower.saturating_add(1));
+            }
+
+            let head = self.head;
+            self.head = self.wrap_add(self.head, 1);
+            unsafe {
+                self.buffer_write(head, element);
+            }
+        }
+    }
+}
+
+impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> {
+    fn spec_extend(&mut self, mut iterator: vec::IntoIter<T>) {
+        let slice = iterator.as_slice();
+        self.reserve(slice.len());
+
+        unsafe {
+            self.copy_slice(self.head, slice);
+            self.head = self.wrap_add(self.head, slice.len());
+        }
+        iterator.forget_remaining_elements();
+    }
+}
+
+impl<'a, T: 'a, I, A: Allocator> SpecExtend<&'a T, I> for VecDeque<T, A>
+where
+    I: Iterator<Item = &'a T>,
+    T: Copy,
+{
+    default fn spec_extend(&mut self, iterator: I) {
+        self.spec_extend(iterator.copied())
+    }
+}
+
+impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for VecDeque<T, A>
+where
+    T: Copy,
+{
+    fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
+        let slice = iterator.as_slice();
+        self.reserve(slice.len());
+
+        unsafe {
+            self.copy_slice(self.head, slice);
+            self.head = self.wrap_add(self.head, slice.len());
+        }
+    }
+}
diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs
index 03c532bb697..8134eea570a 100644
--- a/library/alloc/src/vec/into_iter.rs
+++ b/library/alloc/src/vec/into_iter.rs
@@ -121,6 +121,11 @@ impl<T, A: Allocator> IntoIter<T, A> {
             ptr::drop_in_place(remaining);
         }
     }
+
+    /// Forgets to Drop the remaining elements while still allowing the backing allocation to be freed.
+    pub(crate) fn forget_remaining_elements(&mut self) {
+        self.ptr = self.end;
+    }
 }
 
 #[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")]
diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs
index c3b4534096d..506ee0ecfa2 100644
--- a/library/alloc/src/vec/spec_extend.rs
+++ b/library/alloc/src/vec/spec_extend.rs
@@ -62,7 +62,7 @@ impl<T, A: Allocator> SpecExtend<T, IntoIter<T>> for Vec<T, A> {
         unsafe {
             self.append_elements(iterator.as_slice() as _);
         }
-        iterator.ptr = iterator.end;
+        iterator.forget_remaining_elements();
     }
 }