Merging upstream version 1.68.2+dfsg1.

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

4 files changed, 190 insertions, 75 deletions

diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs
index 55f6138cd..e54880e86 100644
--- a/library/alloc/src/collections/vec_deque/into_iter.rs
+++ b/library/alloc/src/collections/vec_deque/into_iter.rs
@@ -25,6 +25,10 @@ impl<T, A: Allocator> IntoIter<T, A> {
     pub(super) fn new(inner: VecDeque<T, A>) -> Self {
         IntoIter { inner }
     }
+
+    pub(super) fn into_vecdeque(self) -> VecDeque<T, A> {
+        self.inner
+    }
 }
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 4866c53e7..8317ac431 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -55,6 +55,10 @@ use self::spec_extend::SpecExtend;
 
 mod spec_extend;
 
+use self::spec_from_iter::SpecFromIter;
+
+mod spec_from_iter;
+
 #[cfg(test)]
 mod tests;
 
@@ -531,12 +535,13 @@ impl<T> VecDeque<T> {
     ///
     /// let deque: VecDeque<u32> = VecDeque::new();
     /// ```
-    // FIXME: This should probably be const
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
+    #[rustc_const_stable(feature = "const_vec_deque_new", since = "1.68.0")]
     #[must_use]
-    pub fn new() -> VecDeque<T> {
-        VecDeque::new_in(Global)
+    pub const fn new() -> VecDeque<T> {
+        // FIXME: This should just be `VecDeque::new_in(Global)` once that hits stable.
+        VecDeque { head: 0, len: 0, buf: RawVec::NEW }
     }
 
     /// Creates an empty deque with space for at least `capacity` elements.
@@ -586,6 +591,38 @@ impl<T, A: Allocator> VecDeque<T, A> {
         VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) }
     }
 
+    /// Creates a `VecDeque` from a raw allocation, when the initialized
+    /// part of that allocation forms a *contiguous* subslice thereof.
+    ///
+    /// For use by `vec::IntoIter::into_vecdeque`
+    ///
+    /// # Safety
+    ///
+    /// All the usual requirements on the allocated memory like in
+    /// `Vec::from_raw_parts_in`, but takes a *range* of elements that are
+    /// initialized rather than only supporting `0..len`.  Requires that
+    /// `initialized.start` ≤ `initialized.end` ≤ `capacity`.
+    #[inline]
+    pub(crate) unsafe fn from_contiguous_raw_parts_in(
+        ptr: *mut T,
+        initialized: Range<usize>,
+        capacity: usize,
+        alloc: A,
+    ) -> Self {
+        debug_assert!(initialized.start <= initialized.end);
+        debug_assert!(initialized.end <= capacity);
+
+        // SAFETY: Our safety precondition guarantees the range length won't wrap,
+        // and that the allocation is valid for use in `RawVec`.
+        unsafe {
+            VecDeque {
+                head: initialized.start,
+                len: initialized.end.unchecked_sub(initialized.start),
+                buf: RawVec::from_raw_parts_in(ptr, capacity, alloc),
+            }
+        }
+    }
+
     /// Provides a reference to the element at the given index.
     ///
     /// Element at index 0 is the front of the queue.
@@ -599,6 +636,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// buf.push_back(3);
     /// buf.push_back(4);
     /// buf.push_back(5);
+    /// buf.push_back(6);
     /// assert_eq!(buf.get(1), Some(&4));
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -624,10 +662,11 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// buf.push_back(3);
     /// buf.push_back(4);
     /// buf.push_back(5);
+    /// buf.push_back(6);
+    /// assert_eq!(buf[1], 4);
     /// if let Some(elem) = buf.get_mut(1) {
     ///     *elem = 7;
     /// }
-    ///
     /// assert_eq!(buf[1], 7);
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
@@ -905,65 +944,72 @@ impl<T, A: Allocator> VecDeque<T, A> {
             return;
         }
 
-        if target_cap < self.capacity() {
-            // There are three cases of interest:
-            //   All elements are out of desired bounds
-            //   Elements are contiguous, and head is out of desired bounds
-            //   Elements are discontiguous, and tail is out of desired bounds
+        // There are three cases of interest:
+        //   All elements are out of desired bounds
+        //   Elements are contiguous, and tail is out of desired bounds
+        //   Elements are discontiguous
+        //
+        // At all other times, element positions are unaffected.
+
+        // `head` and `len` are at most `isize::MAX` and `target_cap < self.capacity()`, so nothing can
+        // overflow.
+        let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len));
+
+        if self.len == 0 {
+            self.head = 0;
+        } else if self.head >= target_cap && tail_outside {
+            // Head and tail are both out of bounds, so copy all of them to the front.
             //
-            // At all other times, element positions are unaffected.
+            //  H := head
+            //  L := last element
+            //                    H           L
+            //   [. . . . . . . . o o o o o o o . ]
+            //    H           L
+            //   [o o o o o o o . ]
+            unsafe {
+                // nonoverlapping because `self.head >= target_cap >= self.len`.
+                self.copy_nonoverlapping(self.head, 0, self.len);
+            }
+            self.head = 0;
+        } else if self.head < target_cap && tail_outside {
+            // Head is in bounds, tail is out of bounds.
+            // Copy the overflowing part to the beginning of the
+            // buffer. This won't overlap because `target_cap >= self.len`.
             //
-            // Indicates that elements at the head should be moved.
-
-            let tail_outside = (target_cap + 1..=self.capacity()).contains(&(self.head + self.len));
-            // Move elements from out of desired bounds (positions after target_cap)
-            if self.len == 0 {
-                self.head = 0;
-            } else if self.head >= target_cap && tail_outside {
-                //  H := head
-                //  L := last element
-                //                    H           L
-                //   [. . . . . . . . o o o o o o o . ]
-                //    H           L
-                //   [o o o o o o o . ]
-                unsafe {
-                    // nonoverlapping because self.head >= target_cap >= self.len
-                    self.copy_nonoverlapping(self.head, 0, self.len);
-                }
-                self.head = 0;
-            } else if self.head < target_cap && tail_outside {
-                //  H := head
-                //  L := last element
-                //          H           L
-                //   [. . . o o o o o o o . . . . . . ]
-                //      L   H
-                //   [o o . o o o o o ]
-                let len = self.head + self.len - target_cap;
-                unsafe {
-                    self.copy_nonoverlapping(target_cap, 0, len);
-                }
-            } else if self.head >= target_cap {
-                //  H := head
-                //  L := last element
-                //            L                   H
-                //   [o o o o o . . . . . . . . . o o ]
-                //            L   H
-                //   [o o o o o . o o ]
-                let len = self.capacity() - self.head;
-                let new_head = target_cap - len;
-                unsafe {
-                    // can't use copy_nonoverlapping here for the same reason
-                    // as in `handle_capacity_increase()`
-                    self.copy(self.head, new_head, len);
-                }
-                self.head = new_head;
+            //  H := head
+            //  L := last element
+            //          H           L
+            //   [. . . o o o o o o o . . . . . . ]
+            //      L   H
+            //   [o o . o o o o o ]
+            let len = self.head + self.len - target_cap;
+            unsafe {
+                self.copy_nonoverlapping(target_cap, 0, len);
             }
-
-            self.buf.shrink_to_fit(target_cap);
-
-            debug_assert!(self.head < self.capacity() || self.capacity() == 0);
-            debug_assert!(self.len <= self.capacity());
+        } else if !self.is_contiguous() {
+            // The head slice is at least partially out of bounds, tail is in bounds.
+            // Copy the head backwards so it lines up with the target capacity.
+            // This won't overlap because `target_cap >= self.len`.
+            //
+            //  H := head
+            //  L := last element
+            //            L                   H
+            //   [o o o o o . . . . . . . . . o o ]
+            //            L   H
+            //   [o o o o o . o o ]
+            let head_len = self.capacity() - self.head;
+            let new_head = target_cap - head_len;
+            unsafe {
+                // can't use `copy_nonoverlapping()` here because the new and old
+                // regions for the head might overlap.
+                self.copy(self.head, new_head, head_len);
+            }
+            self.head = new_head;
         }
+        self.buf.shrink_to_fit(target_cap);
+
+        debug_assert!(self.head < self.capacity() || self.capacity() == 0);
+        debug_assert!(self.len <= self.capacity());
     }
 
     /// Shortens the deque, keeping the first `len` elements and dropping
@@ -1878,7 +1924,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[stable(feature = "append", since = "1.4.0")]
     pub fn append(&mut self, other: &mut Self) {
         if T::IS_ZST {
-            self.len += other.len;
+            self.len = self.len.checked_add(other.len).expect("capacity overflow");
             other.len = 0;
             other.head = 0;
             return;
@@ -2505,7 +2551,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// The deque is assumed to be partitioned according to the given predicate.
     /// This means that all elements for which the predicate returns true are at the start of the deque
     /// and all elements for which the predicate returns false are at the end.
-    /// For example, [7, 15, 3, 5, 4, 12, 6] is a partitioned under the predicate x % 2 != 0
+    /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
     /// (all odd numbers are at the start, all even at the end).
     ///
     /// If the deque is not partitioned, the returned result is unspecified and meaningless,
@@ -2699,18 +2745,8 @@ impl<T, A: Allocator> IndexMut<usize> for VecDeque<T, A> {
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> FromIterator<T> for VecDeque<T> {
-    #[inline]
     fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> VecDeque<T> {
-        // Since converting is O(1) now, might as well re-use that logic
-        // (including things like the `vec::IntoIter`→`Vec` specialization)
-        // especially as that could save us some monomorphiziation work
-        // if one uses the same iterators (like slice ones) with both.
-        return from_iter_via_vec(iter.into_iter());
-
-        #[inline]
-        fn from_iter_via_vec<U>(iter: impl Iterator<Item = U>) -> VecDeque<U> {
-            Vec::from_iter(iter).into()
-        }
+        SpecFromIter::spec_from_iter(iter.into_iter())
     }
 }
 
@@ -2794,9 +2830,9 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> {
     /// [`Vec<T>`]: crate::vec::Vec
     /// [`VecDeque<T>`]: crate::collections::VecDeque
     ///
-    /// In its current implementation, this is a very cheap
-    /// conversion. This isn't yet a guarantee though, and
-    /// shouldn't be relied on.
+    /// This conversion is guaranteed to run in *O*(1) time
+    /// and to not re-allocate the `Vec`'s buffer or allocate
+    /// any additional memory.
     #[inline]
     fn from(other: Vec<T, A>) -> Self {
         let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc();
diff --git a/library/alloc/src/collections/vec_deque/spec_from_iter.rs b/library/alloc/src/collections/vec_deque/spec_from_iter.rs
new file mode 100644
index 000000000..7650492eb
--- /dev/null
+++ b/library/alloc/src/collections/vec_deque/spec_from_iter.rs
@@ -0,0 +1,33 @@
+use super::{IntoIter, VecDeque};
+
+/// Specialization trait used for `VecDeque::from_iter`
+pub(super) trait SpecFromIter<T, I> {
+    fn spec_from_iter(iter: I) -> Self;
+}
+
+impl<T, I> SpecFromIter<T, I> for VecDeque<T>
+where
+    I: Iterator<Item = T>,
+{
+    default fn spec_from_iter(iterator: I) -> Self {
+        // Since converting is O(1) now, just re-use the `Vec` logic for
+        // anything where we can't do something extra-special for `VecDeque`,
+        // especially as that could save us some monomorphiziation work
+        // if one uses the same iterators (like slice ones) with both.
+        crate::vec::Vec::from_iter(iterator).into()
+    }
+}
+
+impl<T> SpecFromIter<T, crate::vec::IntoIter<T>> for VecDeque<T> {
+    #[inline]
+    fn spec_from_iter(iterator: crate::vec::IntoIter<T>) -> Self {
+        iterator.into_vecdeque()
+    }
+}
+
+impl<T> SpecFromIter<T, IntoIter<T>> for VecDeque<T> {
+    #[inline]
+    fn spec_from_iter(iterator: IntoIter<T>) -> Self {
+        iterator.into_vecdeque()
+    }
+}
diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs
index 220ad71be..205a8ff3c 100644
--- a/library/alloc/src/collections/vec_deque/tests.rs
+++ b/library/alloc/src/collections/vec_deque/tests.rs
@@ -749,6 +749,48 @@ fn test_drain() {
 }
 
 #[test]
+fn issue_108453() {
+    let mut deque = VecDeque::with_capacity(10);
+
+    deque.push_back(1u8);
+    deque.push_back(2);
+    deque.push_back(3);
+
+    deque.push_front(10);
+    deque.push_front(9);
+
+    deque.shrink_to(9);
+
+    assert_eq!(deque.into_iter().collect::<Vec<_>>(), vec![9, 10, 1, 2, 3]);
+}
+
+#[test]
+fn test_shrink_to() {
+    // test deques with capacity 16 with all possible head positions, lengths and target capacities.
+    let cap = 16;
+
+    for len in 0..cap {
+        for head in 0..cap {
+            let expected = (1..=len).collect::<VecDeque<_>>();
+
+            for target_cap in len..cap {
+                let mut deque = VecDeque::with_capacity(cap);
+                // currently, `with_capacity` always allocates the exact capacity if it's greater than 8.
+                assert_eq!(deque.capacity(), cap);
+
+                // we can let the head point anywhere in the buffer since the deque is empty.
+                deque.head = head;
+                deque.extend(1..=len);
+
+                deque.shrink_to(target_cap);
+
+                assert_eq!(deque, expected);
+            }
+        }
+    }
+}
+
+#[test]
 fn test_shrink_to_fit() {
     // This test checks that every single combination of head and tail position,
     // is tested. Capacity 15 should be large enough to cover every case.