Merging upstream version 1.67.1+dfsg1.

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

11 files changed, 964 insertions, 1300 deletions

diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs
index 8a7719347..1d9c4460e 100644
--- a/library/alloc/src/collections/btree/map.rs
+++ b/library/alloc/src/collections/btree/map.rs
@@ -46,8 +46,8 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT;
 /// is done is *very* inefficient for modern computer architectures. In particular, every element
 /// is stored in its own individually heap-allocated node. This means that every single insertion
 /// triggers a heap-allocation, and every single comparison should be a cache-miss. Since these
-/// are both notably expensive things to do in practice, we are forced to at very least reconsider
-/// the BST strategy.
+/// are both notably expensive things to do in practice, we are forced to, at the very least,
+/// reconsider the BST strategy.
 ///
 /// A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing
 /// this, we reduce the number of allocations by a factor of B, and improve cache efficiency in
diff --git a/library/alloc/src/collections/btree/node/tests.rs b/library/alloc/src/collections/btree/node/tests.rs
index aadb0dc9c..64bce0ff8 100644
--- a/library/alloc/src/collections/btree/node/tests.rs
+++ b/library/alloc/src/collections/btree/node/tests.rs
@@ -94,6 +94,7 @@ fn test_partial_eq() {
 
 #[test]
 #[cfg(target_arch = "x86_64")]
+#[cfg_attr(miri, ignore)] // We'd like to run Miri with layout randomization
 fn test_sizes() {
     assert_eq!(core::mem::size_of::<LeafNode<(), ()>>(), 16);
     assert_eq!(core::mem::size_of::<LeafNode<i64, i64>>(), 16 + CAPACITY * 2 * 8);
diff --git a/library/alloc/src/collections/mod.rs b/library/alloc/src/collections/mod.rs
index 161a37573..3e0b0f735 100644
--- a/library/alloc/src/collections/mod.rs
+++ b/library/alloc/src/collections/mod.rs
@@ -139,7 +139,7 @@ impl Display for TryReserveError {
                 " because the computed capacity exceeded the collection's maximum"
             }
             TryReserveErrorKind::AllocError { .. } => {
-                " because the memory allocator returned a error"
+                " because the memory allocator returned an error"
             }
         };
         fmt.write_str(reason)
diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs
index 41baa7102..89feb361d 100644
--- a/library/alloc/src/collections/vec_deque/drain.rs
+++ b/library/alloc/src/collections/vec_deque/drain.rs
@@ -1,12 +1,12 @@
-use core::fmt;
 use core::iter::FusedIterator;
 use core::marker::PhantomData;
-use core::mem::{self, MaybeUninit};
-use core::ptr::{self, NonNull};
+use core::mem::{self, SizedTypeProperties};
+use core::ptr::NonNull;
+use core::{fmt, ptr};
 
 use crate::alloc::{Allocator, Global};
 
-use super::{count, wrap_index, VecDeque};
+use super::VecDeque;
 
 /// A draining iterator over the elements of a `VecDeque`.
 ///
@@ -20,26 +20,70 @@ pub struct Drain<
     T: 'a,
     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
 > {
-    after_tail: usize,
-    after_head: usize,
-    ring: NonNull<[T]>,
-    tail: usize,
-    head: usize,
+    // We can't just use a &mut VecDeque<T, A>, as that would make Drain invariant over T
+    // and we want it to be covariant instead
     deque: NonNull<VecDeque<T, A>>,
-    _phantom: PhantomData<&'a T>,
+    // drain_start is stored in deque.len
+    drain_len: usize,
+    // index into the logical array, not the physical one (always lies in [0..deque.len))
+    idx: usize,
+    // number of elements after the drain range
+    tail_len: usize,
+    remaining: usize,
+    // Needed to make Drain covariant over T
+    _marker: PhantomData<&'a T>,
 }
 
 impl<'a, T, A: Allocator> Drain<'a, T, A> {
     pub(super) unsafe fn new(
-        after_tail: usize,
-        after_head: usize,
-        ring: &'a [MaybeUninit<T>],
-        tail: usize,
-        head: usize,
-        deque: NonNull<VecDeque<T, A>>,
+        deque: &'a mut VecDeque<T, A>,
+        drain_start: usize,
+        drain_len: usize,
     ) -> Self {
-        let ring = unsafe { NonNull::new_unchecked(ring as *const [MaybeUninit<T>] as *mut _) };
-        Drain { after_tail, after_head, ring, tail, head, deque, _phantom: PhantomData }
+        let orig_len = mem::replace(&mut deque.len, drain_start);
+        let tail_len = orig_len - drain_start - drain_len;
+        Drain {
+            deque: NonNull::from(deque),
+            drain_len,
+            idx: drain_start,
+            tail_len,
+            remaining: drain_len,
+            _marker: PhantomData,
+        }
+    }
+
+    // Only returns pointers to the slices, as that's
+    // all we need to drop them. May only be called if `self.remaining != 0`.
+    unsafe fn as_slices(&self) -> (*mut [T], *mut [T]) {
+        unsafe {
+            let deque = self.deque.as_ref();
+            // FIXME: This is doing almost exactly the same thing as the else branch in `VecDeque::slice_ranges`.
+            // Unfortunately, we can't just call `slice_ranges` here, as the deque's `len` is currently
+            // just `drain_start`, so the range check would (almost) always panic. Between temporarily
+            // adjusting the deques `len` to call `slice_ranges`, and just copy pasting the `slice_ranges`
+            // implementation, this seemed like the less hacky solution, though it might be good to
+            // find a better one in the future.
+
+            // because `self.remaining != 0`, we know that `self.idx < deque.original_len`, so it's a valid
+            // logical index.
+            let wrapped_start = deque.to_physical_idx(self.idx);
+
+            let head_len = deque.capacity() - wrapped_start;
+
+            let (a_range, b_range) = if head_len >= self.remaining {
+                (wrapped_start..wrapped_start + self.remaining, 0..0)
+            } else {
+                let tail_len = self.remaining - head_len;
+                (wrapped_start..deque.capacity(), 0..tail_len)
+            };
+
+            // SAFETY: the range `self.idx..self.idx+self.remaining` lies strictly inside
+            // the range `0..deque.original_len`. because of this, and because of the fact
+            // that we acquire `a_range` and `b_range` exactly like `slice_ranges` would,
+            // it's guaranteed that `a_range` and `b_range` represent valid ranges into
+            // the deques buffer.
+            (deque.buffer_range(a_range), deque.buffer_range(b_range))
+        }
     }
 }
 
@@ -47,11 +91,10 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> {
 impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         f.debug_tuple("Drain")
-            .field(&self.after_tail)
-            .field(&self.after_head)
-            .field(&self.ring)
-            .field(&self.tail)
-            .field(&self.head)
+            .field(&self.drain_len)
+            .field(&self.idx)
+            .field(&self.tail_len)
+            .field(&self.remaining)
             .finish()
     }
 }
@@ -68,57 +111,81 @@ impl<T, A: Allocator> Drop for Drain<'_, T, A> {
 
         impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
             fn drop(&mut self) {
-                self.0.for_each(drop);
+                if self.0.remaining != 0 {
+                    unsafe {
+                        // SAFETY: We just checked that `self.remaining != 0`.
+                        let (front, back) = self.0.as_slices();
+                        ptr::drop_in_place(front);
+                        ptr::drop_in_place(back);
+                    }
+                }
 
                 let source_deque = unsafe { self.0.deque.as_mut() };
 
-                // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
-                //
-                //        T   t   h   H
-                // [. . . o o x x o o . . .]
-                //
-                let orig_tail = source_deque.tail;
-                let drain_tail = source_deque.head;
-                let drain_head = self.0.after_tail;
-                let orig_head = self.0.after_head;
+                let drain_start = source_deque.len();
+                let drain_len = self.0.drain_len;
+                let drain_end = drain_start + drain_len;
+
+                let orig_len = self.0.tail_len + drain_end;
 
-                let tail_len = count(orig_tail, drain_tail, source_deque.cap());
-                let head_len = count(drain_head, orig_head, source_deque.cap());
+                if T::IS_ZST {
+                    // no need to copy around any memory if T is a ZST
+                    source_deque.len = orig_len - drain_len;
+                    return;
+                }
 
-                // Restore the original head value
-                source_deque.head = orig_head;
+                let head_len = drain_start;
+                let tail_len = self.0.tail_len;
 
-                match (tail_len, head_len) {
+                match (head_len, tail_len) {
                     (0, 0) => {
                         source_deque.head = 0;
-                        source_deque.tail = 0;
+                        source_deque.len = 0;
                     }
                     (0, _) => {
-                        source_deque.tail = drain_head;
+                        source_deque.head = source_deque.to_physical_idx(drain_len);
+                        source_deque.len = orig_len - drain_len;
                     }
                     (_, 0) => {
-                        source_deque.head = drain_tail;
+                        source_deque.len = orig_len - drain_len;
                     }
                     _ => unsafe {
-                        if tail_len <= head_len {
-                            source_deque.tail = source_deque.wrap_sub(drain_head, tail_len);
-                            source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
+                        if head_len <= tail_len {
+                            source_deque.wrap_copy(
+                                source_deque.head,
+                                source_deque.to_physical_idx(drain_len),
+                                head_len,
+                            );
+                            source_deque.head = source_deque.to_physical_idx(drain_len);
+                            source_deque.len = orig_len - drain_len;
                         } else {
-                            source_deque.head = source_deque.wrap_add(drain_tail, head_len);
-                            source_deque.wrap_copy(drain_tail, drain_head, head_len);
+                            source_deque.wrap_copy(
+                                source_deque.to_physical_idx(head_len + drain_len),
+                                source_deque.to_physical_idx(head_len),
+                                tail_len,
+                            );
+                            source_deque.len = orig_len - drain_len;
                         }
                     },
                 }
             }
         }
 
-        while let Some(item) = self.next() {
-            let guard = DropGuard(self);
-            drop(item);
-            mem::forget(guard);
+        let guard = DropGuard(self);
+        if guard.0.remaining != 0 {
+            unsafe {
+                // SAFETY: We just checked that `self.remaining != 0`.
+                let (front, back) = guard.0.as_slices();
+                // since idx is a logical index, we don't need to worry about wrapping.
+                guard.0.idx += front.len();
+                guard.0.remaining -= front.len();
+                ptr::drop_in_place(front);
+                guard.0.remaining = 0;
+                ptr::drop_in_place(back);
+            }
         }
 
-        DropGuard(self);
+        // Dropping `guard` handles moving the remaining elements into place.
     }
 }
 
@@ -128,20 +195,18 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
 
     #[inline]
     fn next(&mut self) -> Option<T> {
-        if self.tail == self.head {
+        if self.remaining == 0 {
             return None;
         }
-        let tail = self.tail;
-        self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
-        // Safety:
-        // - `self.tail` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(tail))) }
+        let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx) };
+        self.idx += 1;
+        self.remaining -= 1;
+        Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let len = count(self.tail, self.head, self.ring.len());
+        let len = self.remaining;
         (len, Some(len))
     }
 }
@@ -150,14 +215,12 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
 impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
     #[inline]
     fn next_back(&mut self) -> Option<T> {
-        if self.tail == self.head {
+        if self.remaining == 0 {
             return None;
         }
-        self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
-        // Safety:
-        // - `self.head` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(self.head))) }
+        self.remaining -= 1;
+        let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx + self.remaining) };
+        Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
     }
 }
 
diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs
index e696d7ed6..d9f393714 100644
--- a/library/alloc/src/collections/vec_deque/iter.rs
+++ b/library/alloc/src/collections/vec_deque/iter.rs
@@ -1,9 +1,6 @@
-use core::fmt;
 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
-use core::mem::MaybeUninit;
 use core::ops::Try;
-
-use super::{count, wrap_index, RingSlices};
+use core::{fmt, mem, slice};
 
 /// An iterator over the elements of a `VecDeque`.
 ///
@@ -13,30 +10,20 @@ use super::{count, wrap_index, RingSlices};
 /// [`iter`]: super::VecDeque::iter
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, T: 'a> {
-    ring: &'a [MaybeUninit<T>],
-    tail: usize,
-    head: usize,
+    i1: slice::Iter<'a, T>,
+    i2: slice::Iter<'a, T>,
 }
 
 impl<'a, T> Iter<'a, T> {
-    pub(super) fn new(ring: &'a [MaybeUninit<T>], tail: usize, head: usize) -> Self {
-        Iter { ring, tail, head }
+    pub(super) fn new(i1: slice::Iter<'a, T>, i2: slice::Iter<'a, T>) -> Self {
+        Self { i1, i2 }
     }
 }
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            f.debug_tuple("Iter")
-                .field(&MaybeUninit::slice_assume_init_ref(front))
-                .field(&MaybeUninit::slice_assume_init_ref(back))
-                .finish()
-        }
+        f.debug_tuple("Iter").field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish()
     }
 }
 
@@ -44,7 +31,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for Iter<'_, T> {
     fn clone(&self) -> Self {
-        Iter { ring: self.ring, tail: self.tail, head: self.head }
+        Iter { i1: self.i1.clone(), i2: self.i2.clone() }
     }
 }
 
@@ -54,72 +41,50 @@ impl<'a, T> Iterator for Iter<'a, T> {
 
     #[inline]
     fn next(&mut self) -> Option<&'a T> {
-        if self.tail == self.head {
-            return None;
+        match self.i1.next() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the first one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i1 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i1.next()
+            }
         }
-        let tail = self.tail;
-        self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
-        // Safety:
-        // - `self.tail` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) }
+    }
+
+    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i1.advance_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i1.advance_by(n - m).map_err(|o| o + m)
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let len = count(self.tail, self.head, self.ring.len());
+        let len = self.len();
         (len, Some(len))
     }
 
-    fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            accum = MaybeUninit::slice_assume_init_ref(front).iter().fold(accum, &mut f);
-            MaybeUninit::slice_assume_init_ref(back).iter().fold(accum, &mut f)
-        }
+        let accum = self.i1.fold(accum, &mut f);
+        self.i2.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<Output = B>,
     {
-        let (mut iter, final_res);
-        if self.tail <= self.head {
-            // Safety: single slice self.ring[self.tail..self.head] is initialized.
-            iter = unsafe { MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]) }
-                .iter();
-            final_res = iter.try_fold(init, &mut f);
-        } else {
-            // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
-            let (front, back) = self.ring.split_at(self.tail);
-
-            let mut back_iter = unsafe { MaybeUninit::slice_assume_init_ref(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 = unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
-            final_res = iter.try_fold(res?, &mut f);
-        }
-        self.tail = self.head - iter.len();
-        final_res
-    }
-
-    fn nth(&mut self, n: usize) -> Option<Self::Item> {
-        if n >= count(self.tail, self.head, self.ring.len()) {
-            self.tail = self.head;
-            None
-        } else {
-            self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
-            self.next()
-        }
+        let acc = self.i1.try_fold(init, &mut f)?;
+        self.i2.try_fold(acc, &mut f)
     }
 
     #[inline]
@@ -132,8 +97,12 @@ impl<'a, T> Iterator for Iter<'a, T> {
         // Safety: The TrustedRandomAccess contract requires that callers only pass an index
         // that is in bounds.
         unsafe {
-            let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
-            self.ring.get_unchecked(idx).assume_init_ref()
+            let i1_len = self.i1.len();
+            if idx < i1_len {
+                self.i1.__iterator_get_unchecked(idx)
+            } else {
+                self.i2.__iterator_get_unchecked(idx - i1_len)
+            }
         }
     }
 }
@@ -142,63 +111,56 @@ impl<'a, T> Iterator for Iter<'a, T> {
 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
     #[inline]
     fn next_back(&mut self) -> Option<&'a T> {
-        if self.tail == self.head {
-            return None;
+        match self.i2.next_back() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the second one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i2 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i2.next_back()
+            }
         }
-        self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
-        // Safety:
-        // - `self.head` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(self.ring.get_unchecked(self.head).assume_init_ref()) }
     }
 
-    fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i2.advance_back_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i2.advance_back_by(n - m).map_err(|o| m + o)
+    }
+
+    fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            accum = MaybeUninit::slice_assume_init_ref(back).iter().rfold(accum, &mut f);
-            MaybeUninit::slice_assume_init_ref(front).iter().rfold(accum, &mut f)
-        }
+        let accum = self.i2.rfold(accum, &mut f);
+        self.i1.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<Output = B>,
     {
-        let (mut iter, final_res);
-        if self.tail <= self.head {
-            // Safety: single slice self.ring[self.tail..self.head] is initialized.
-            iter = unsafe {
-                MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]).iter()
-            };
-            final_res = iter.try_rfold(init, &mut f);
-        } else {
-            // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
-            let (front, back) = self.ring.split_at(self.tail);
-
-            let mut front_iter =
-                unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
-            let res = front_iter.try_rfold(init, &mut f);
-            self.head = front_iter.len();
-            iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() };
-            final_res = iter.try_rfold(res?, &mut f);
-        }
-        self.head = self.tail + iter.len();
-        final_res
+        let acc = self.i2.try_rfold(init, &mut f)?;
+        self.i1.try_rfold(acc, &mut f)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for Iter<'_, T> {
+    fn len(&self) -> usize {
+        self.i1.len() + self.i2.len()
+    }
+
     fn is_empty(&self) -> bool {
-        self.head == self.tail
+        self.i1.is_empty() && self.i2.is_empty()
     }
 }
 
diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs
index b78c0d5e1..2c59d95cd 100644
--- a/library/alloc/src/collections/vec_deque/iter_mut.rs
+++ b/library/alloc/src/collections/vec_deque/iter_mut.rs
@@ -1,8 +1,6 @@
-use core::fmt;
 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
-use core::marker::PhantomData;
-
-use super::{count, wrap_index, RingSlices};
+use core::ops::Try;
+use core::{fmt, mem, slice};
 
 /// A mutable iterator over the elements of a `VecDeque`.
 ///
@@ -12,39 +10,20 @@ use super::{count, wrap_index, RingSlices};
 /// [`iter_mut`]: super::VecDeque::iter_mut
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, T: 'a> {
-    // Internal safety invariant: the entire slice is dereferenceable.
-    ring: *mut [T],
-    tail: usize,
-    head: usize,
-    phantom: PhantomData<&'a mut [T]>,
+    i1: slice::IterMut<'a, T>,
+    i2: slice::IterMut<'a, T>,
 }
 
 impl<'a, T> IterMut<'a, T> {
-    pub(super) unsafe fn new(
-        ring: *mut [T],
-        tail: usize,
-        head: usize,
-        phantom: PhantomData<&'a mut [T]>,
-    ) -> Self {
-        IterMut { ring, tail, head, phantom }
+    pub(super) fn new(i1: slice::IterMut<'a, T>, i2: slice::IterMut<'a, T>) -> Self {
+        Self { i1, i2 }
     }
 }
 
-// SAFETY: we do nothing thread-local and there is no interior mutability,
-// so the usual structural `Send`/`Sync` apply.
-#[stable(feature = "rust1", since = "1.0.0")]
-unsafe impl<T: Send> Send for IterMut<'_, T> {}
-#[stable(feature = "rust1", since = "1.0.0")]
-unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
-
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // SAFETY: these are the elements we have not handed out yet, so aliasing is fine.
-        // The `IterMut` invariant also ensures everything is dereferenceable.
-        let (front, back) = unsafe { (&*front, &*back) };
-        f.debug_tuple("IterMut").field(&front).field(&back).finish()
+        f.debug_tuple("IterMut").field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish()
     }
 }
 
@@ -54,44 +33,50 @@ impl<'a, T> Iterator for IterMut<'a, T> {
 
     #[inline]
     fn next(&mut self) -> Option<&'a mut T> {
-        if self.tail == self.head {
-            return None;
+        match self.i1.next() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the first one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i1 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i1.next()
+            }
         }
-        let tail = self.tail;
-        self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
+    }
 
-        unsafe {
-            let elem = self.ring.get_unchecked_mut(tail);
-            Some(&mut *elem)
-        }
+    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i1.advance_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i1.advance_by(n - m).map_err(|o| o + m)
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let len = count(self.tail, self.head, self.ring.len());
+        let len = self.len();
         (len, Some(len))
     }
 
-    fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // SAFETY: these are the elements we have not handed out yet, so aliasing is fine.
-        // The `IterMut` invariant also ensures everything is dereferenceable.
-        let (front, back) = unsafe { (&mut *front, &mut *back) };
-        accum = front.iter_mut().fold(accum, &mut f);
-        back.iter_mut().fold(accum, &mut f)
+        let accum = self.i1.fold(accum, &mut f);
+        self.i2.fold(accum, &mut f)
     }
 
-    fn nth(&mut self, n: usize) -> Option<Self::Item> {
-        if n >= count(self.tail, self.head, self.ring.len()) {
-            self.tail = self.head;
-            None
-        } else {
-            self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
-            self.next()
-        }
+    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Output = B>,
+    {
+        let acc = self.i1.try_fold(init, &mut f)?;
+        self.i2.try_fold(acc, &mut f)
     }
 
     #[inline]
@@ -104,8 +89,12 @@ impl<'a, T> Iterator for IterMut<'a, T> {
         // Safety: The TrustedRandomAccess contract requires that callers only pass an index
         // that is in bounds.
         unsafe {
-            let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
-            &mut *self.ring.get_unchecked_mut(idx)
+            let i1_len = self.i1.len();
+            if idx < i1_len {
+                self.i1.__iterator_get_unchecked(idx)
+            } else {
+                self.i2.__iterator_get_unchecked(idx - i1_len)
+            }
         }
     }
 }
@@ -114,34 +103,56 @@ impl<'a, T> Iterator for IterMut<'a, T> {
 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
     #[inline]
     fn next_back(&mut self) -> Option<&'a mut T> {
-        if self.tail == self.head {
-            return None;
+        match self.i2.next_back() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the first one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i2 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i2.next_back()
+            }
         }
-        self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
+    }
 
-        unsafe {
-            let elem = self.ring.get_unchecked_mut(self.head);
-            Some(&mut *elem)
-        }
+    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i2.advance_back_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i2.advance_back_by(n - m).map_err(|o| m + o)
     }
 
-    fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // SAFETY: these are the elements we have not handed out yet, so aliasing is fine.
-        // The `IterMut` invariant also ensures everything is dereferenceable.
-        let (front, back) = unsafe { (&mut *front, &mut *back) };
-        accum = back.iter_mut().rfold(accum, &mut f);
-        front.iter_mut().rfold(accum, &mut f)
+        let accum = self.i2.rfold(accum, &mut f);
+        self.i1.rfold(accum, &mut f)
+    }
+
+    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
+    where
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Output = B>,
+    {
+        let acc = self.i2.try_rfold(init, &mut f)?;
+        self.i1.try_rfold(acc, &mut f)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for IterMut<'_, T> {
+    fn len(&self) -> usize {
+        self.i1.len() + self.i2.len()
+    }
+
     fn is_empty(&self) -> bool {
-        self.head == self.tail
+        self.i1.is_empty() && self.i2.is_empty()
     }
 }
 
diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs
index 2a57dad89..4866c53e7 100644
--- a/library/alloc/src/collections/vec_deque/mod.rs
+++ b/library/alloc/src/collections/vec_deque/mod.rs
@@ -10,11 +10,10 @@
 use core::cmp::{self, Ordering};
 use core::fmt;
 use core::hash::{Hash, Hasher};
-use core::iter::{repeat_with, FromIterator};
-use core::marker::PhantomData;
-use core::mem::{ManuallyDrop, MaybeUninit, SizedTypeProperties};
+use core::iter::{repeat_n, repeat_with, ByRefSized, FromIterator};
+use core::mem::{ManuallyDrop, SizedTypeProperties};
 use core::ops::{Index, IndexMut, Range, RangeBounds};
-use core::ptr::{self, NonNull};
+use core::ptr;
 use core::slice;
 
 // This is used in a bunch of intra-doc links.
@@ -52,14 +51,6 @@ pub use self::iter::Iter;
 
 mod iter;
 
-use self::pair_slices::PairSlices;
-
-mod pair_slices;
-
-use self::ring_slices::RingSlices;
-
-mod ring_slices;
-
 use self::spec_extend::SpecExtend;
 
 mod spec_extend;
@@ -67,11 +58,6 @@ mod spec_extend;
 #[cfg(test)]
 mod tests;
 
-const INITIAL_CAPACITY: usize = 7; // 2^3 - 1
-const MINIMUM_CAPACITY: usize = 1; // 2 - 1
-
-const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // Largest possible power of two
-
 /// A double-ended queue implemented with a growable ring buffer.
 ///
 /// The "default" usage of this type as a queue is to use [`push_back`] to add to
@@ -105,13 +91,13 @@ pub struct VecDeque<
     T,
     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
 > {
-    // tail and head are pointers into the buffer. Tail always points
-    // to the first element that could be read, Head always points
-    // to where data should be written.
-    // If tail == head the buffer is empty. The length of the ringbuffer
-    // is defined as the distance between the two.
-    tail: usize,
+    // `self[0]`, if it exists, is `buf[head]`.
+    // `head < buf.capacity()`, unless `buf.capacity() == 0` when `head == 0`.
     head: usize,
+    // the number of initialized elements, starting from the one at `head` and potentially wrapping around.
+    // if `len == 0`, the exact value of `head` is unimportant.
+    // if `T` is zero-Sized, then `self.len <= usize::MAX`, otherwise `self.len <= isize::MAX as usize`.
+    len: usize,
     buf: RawVec<T, A>,
 }
 
@@ -124,18 +110,8 @@ impl<T: Clone, A: Allocator + Clone> Clone for VecDeque<T, A> {
     }
 
     fn clone_from(&mut self, other: &Self) {
-        self.truncate(other.len());
-
-        let mut iter = PairSlices::from(self, other);
-        while let Some((dst, src)) = iter.next() {
-            dst.clone_from_slice(&src);
-        }
-
-        if iter.has_remainder() {
-            for remainder in iter.remainder() {
-                self.extend(remainder.iter().cloned());
-            }
-        }
+        self.clear();
+        self.extend(other.iter().cloned());
     }
 }
 
@@ -180,41 +156,6 @@ impl<T, A: Allocator> VecDeque<T, A> {
         self.buf.ptr()
     }
 
-    /// Marginally more convenient
-    #[inline]
-    fn cap(&self) -> usize {
-        if T::IS_ZST {
-            // For zero sized types, we are always at maximum capacity
-            MAXIMUM_ZST_CAPACITY
-        } else {
-            self.buf.capacity()
-        }
-    }
-
-    /// Turn ptr into a slice, since the elements of the backing buffer may be uninitialized,
-    /// we will return a slice of [`MaybeUninit<T>`].
-    ///
-    /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and
-    /// incorrect usage of this method.
-    ///
-    /// [zeroed]: mem::MaybeUninit::zeroed
-    #[inline]
-    unsafe fn buffer_as_slice(&self) -> &[MaybeUninit<T>] {
-        unsafe { slice::from_raw_parts(self.ptr() as *mut MaybeUninit<T>, self.cap()) }
-    }
-
-    /// Turn ptr into a mut slice, since the elements of the backing buffer may be uninitialized,
-    /// we will return a slice of [`MaybeUninit<T>`].
-    ///
-    /// See [`MaybeUninit::zeroed`][zeroed] for examples of correct and
-    /// incorrect usage of this method.
-    ///
-    /// [zeroed]: mem::MaybeUninit::zeroed
-    #[inline]
-    unsafe fn buffer_as_mut_slice(&mut self) -> &mut [MaybeUninit<T>] {
-        unsafe { slice::from_raw_parts_mut(self.ptr() as *mut MaybeUninit<T>, self.cap()) }
-    }
-
     /// Moves an element out of the buffer
     #[inline]
     unsafe fn buffer_read(&mut self, off: usize) -> T {
@@ -229,51 +170,58 @@ impl<T, A: Allocator> VecDeque<T, A> {
         }
     }
 
-    /// Returns `true` if the buffer is at full capacity.
+    /// Returns a slice pointer into the buffer.
+    /// `range` must lie inside `0..self.capacity()`.
     #[inline]
-    fn is_full(&self) -> bool {
-        self.cap() - self.len() == 1
+    unsafe fn buffer_range(&self, range: Range<usize>) -> *mut [T] {
+        unsafe {
+            ptr::slice_from_raw_parts_mut(self.ptr().add(range.start), range.end - range.start)
+        }
     }
 
-    /// Returns the index in the underlying buffer for a given logical element
-    /// index.
+    /// Returns `true` if the buffer is at full capacity.
     #[inline]
-    fn wrap_index(&self, idx: usize) -> usize {
-        wrap_index(idx, self.cap())
+    fn is_full(&self) -> bool {
+        self.len == self.capacity()
     }
 
     /// Returns the index in the underlying buffer for a given logical element
     /// index + addend.
     #[inline]
     fn wrap_add(&self, idx: usize, addend: usize) -> usize {
-        wrap_index(idx.wrapping_add(addend), self.cap())
+        wrap_index(idx.wrapping_add(addend), self.capacity())
+    }
+
+    #[inline]
+    fn to_physical_idx(&self, idx: usize) -> usize {
+        self.wrap_add(self.head, idx)
     }
 
     /// Returns the index in the underlying buffer for a given logical element
     /// index - subtrahend.
     #[inline]
     fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
-        wrap_index(idx.wrapping_sub(subtrahend), self.cap())
+        wrap_index(idx.wrapping_sub(subtrahend).wrapping_add(self.capacity()), self.capacity())
     }
 
     /// Copies a contiguous block of memory len long from src to dst
     #[inline]
-    unsafe fn copy(&self, dst: usize, src: usize, len: usize) {
+    unsafe fn copy(&mut self, src: usize, dst: usize, len: usize) {
         debug_assert!(
-            dst + len <= self.cap(),
+            dst + len <= self.capacity(),
             "cpy dst={} src={} len={} cap={}",
             dst,
             src,
             len,
-            self.cap()
+            self.capacity()
         );
         debug_assert!(
-            src + len <= self.cap(),
+            src + len <= self.capacity(),
             "cpy dst={} src={} len={} cap={}",
             dst,
             src,
             len,
-            self.cap()
+            self.capacity()
         );
         unsafe {
             ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
@@ -282,22 +230,22 @@ impl<T, A: Allocator> VecDeque<T, A> {
 
     /// Copies a contiguous block of memory len long from src to dst
     #[inline]
-    unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) {
+    unsafe fn copy_nonoverlapping(&mut self, src: usize, dst: usize, len: usize) {
         debug_assert!(
-            dst + len <= self.cap(),
+            dst + len <= self.capacity(),
             "cno dst={} src={} len={} cap={}",
             dst,
             src,
             len,
-            self.cap()
+            self.capacity()
         );
         debug_assert!(
-            src + len <= self.cap(),
+            src + len <= self.capacity(),
             "cno dst={} src={} len={} cap={}",
             dst,
             src,
             len,
-            self.cap()
+            self.capacity()
         );
         unsafe {
             ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len);
@@ -305,30 +253,28 @@ impl<T, A: Allocator> VecDeque<T, A> {
     }
 
     /// Copies a potentially wrapping block of memory len long from src to dest.
-    /// (abs(dst - src) + len) must be no larger than cap() (There must be at
+    /// (abs(dst - src) + len) must be no larger than capacity() (There must be at
     /// most one continuous overlapping region between src and dest).
-    unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) {
-        #[allow(dead_code)]
-        fn diff(a: usize, b: usize) -> usize {
-            if a <= b { b - a } else { a - b }
-        }
+    unsafe fn wrap_copy(&mut self, src: usize, dst: usize, len: usize) {
         debug_assert!(
-            cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(),
+            cmp::min(src.abs_diff(dst), self.capacity() - src.abs_diff(dst)) + len
+                <= self.capacity(),
             "wrc dst={} src={} len={} cap={}",
             dst,
             src,
             len,
-            self.cap()
+            self.capacity()
         );
 
-        if src == dst || len == 0 {
+        // If T is a ZST, don't do any copying.
+        if T::IS_ZST || src == dst || len == 0 {
             return;
         }
 
         let dst_after_src = self.wrap_sub(dst, src) < len;
 
-        let src_pre_wrap_len = self.cap() - src;
-        let dst_pre_wrap_len = self.cap() - dst;
+        let src_pre_wrap_len = self.capacity() - src;
+        let dst_pre_wrap_len = self.capacity() - dst;
         let src_wraps = src_pre_wrap_len < len;
         let dst_wraps = dst_pre_wrap_len < len;
 
@@ -342,7 +288,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 //            D . . .
                 //
                 unsafe {
-                    self.copy(dst, src, len);
+                    self.copy(src, dst, len);
                 }
             }
             (false, false, true) => {
@@ -355,8 +301,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 //    . .           D .
                 //
                 unsafe {
-                    self.copy(dst, src, dst_pre_wrap_len);
-                    self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
+                    self.copy(src, dst, dst_pre_wrap_len);
+                    self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
                 }
             }
             (true, false, true) => {
@@ -369,8 +315,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 //    . .           D .
                 //
                 unsafe {
-                    self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
-                    self.copy(dst, src, dst_pre_wrap_len);
+                    self.copy(src + dst_pre_wrap_len, 0, len - dst_pre_wrap_len);
+                    self.copy(src, dst, dst_pre_wrap_len);
                 }
             }
             (false, true, false) => {
@@ -383,8 +329,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 //              D . . .
                 //
                 unsafe {
-                    self.copy(dst, src, src_pre_wrap_len);
-                    self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
+                    self.copy(src, dst, src_pre_wrap_len);
+                    self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
                 }
             }
             (true, true, false) => {
@@ -397,8 +343,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 //    D . . .
                 //
                 unsafe {
-                    self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
-                    self.copy(dst, src, src_pre_wrap_len);
+                    self.copy(0, dst + src_pre_wrap_len, len - src_pre_wrap_len);
+                    self.copy(src, dst, src_pre_wrap_len);
                 }
             }
             (false, true, true) => {
@@ -414,9 +360,9 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
                 let delta = dst_pre_wrap_len - src_pre_wrap_len;
                 unsafe {
-                    self.copy(dst, src, src_pre_wrap_len);
-                    self.copy(dst + src_pre_wrap_len, 0, delta);
-                    self.copy(0, delta, len - dst_pre_wrap_len);
+                    self.copy(src, dst, src_pre_wrap_len);
+                    self.copy(0, dst + src_pre_wrap_len, delta);
+                    self.copy(delta, 0, len - dst_pre_wrap_len);
                 }
             }
             (true, true, true) => {
@@ -432,9 +378,9 @@ impl<T, A: Allocator> VecDeque<T, A> {
                 debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
                 let delta = src_pre_wrap_len - dst_pre_wrap_len;
                 unsafe {
-                    self.copy(delta, 0, len - src_pre_wrap_len);
-                    self.copy(0, self.cap() - delta, delta);
-                    self.copy(dst, src, dst_pre_wrap_len);
+                    self.copy(0, delta, len - src_pre_wrap_len);
+                    self.copy(self.capacity() - delta, 0, delta);
+                    self.copy(src, dst, dst_pre_wrap_len);
                 }
             }
         }
@@ -444,8 +390,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// Assumes capacity is sufficient.
     #[inline]
     unsafe fn copy_slice(&mut self, dst: usize, src: &[T]) {
-        debug_assert!(src.len() <= self.cap());
-        let head_room = self.cap() - dst;
+        debug_assert!(src.len() <= self.capacity());
+        let head_room = self.capacity() - dst;
         if src.len() <= head_room {
             unsafe {
                 ptr::copy_nonoverlapping(src.as_ptr(), self.ptr().add(dst), src.len());
@@ -478,48 +424,100 @@ impl<T, A: Allocator> VecDeque<T, A> {
         });
     }
 
+    /// Writes all values from `iter` to `dst`, wrapping
+    /// at the end of the buffer and returns the number
+    /// of written values.
+    ///
+    /// # Safety
+    ///
+    /// Assumes that `iter` yields at most `len` items.
+    /// Assumes capacity is sufficient.
+    unsafe fn write_iter_wrapping(
+        &mut self,
+        dst: usize,
+        mut iter: impl Iterator<Item = T>,
+        len: usize,
+    ) -> usize {
+        struct Guard<'a, T, A: Allocator> {
+            deque: &'a mut VecDeque<T, A>,
+            written: usize,
+        }
+
+        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
+            fn drop(&mut self) {
+                self.deque.len += self.written;
+            }
+        }
+
+        let head_room = self.capacity() - dst;
+
+        let mut guard = Guard { deque: self, written: 0 };
+
+        if head_room >= len {
+            unsafe { guard.deque.write_iter(dst, iter, &mut guard.written) };
+        } else {
+            unsafe {
+                guard.deque.write_iter(
+                    dst,
+                    ByRefSized(&mut iter).take(head_room),
+                    &mut guard.written,
+                );
+                guard.deque.write_iter(0, iter, &mut guard.written)
+            };
+        }
+
+        guard.written
+    }
+
     /// Frobs the head and tail sections around to handle the fact that we
     /// just reallocated. Unsafe because it trusts old_capacity.
     #[inline]
     unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) {
-        let new_capacity = self.cap();
+        let new_capacity = self.capacity();
+        debug_assert!(new_capacity >= old_capacity);
 
         // Move the shortest contiguous section of the ring buffer
-        //    T             H
+        //
+        // H := head
+        // L := last element (`self.to_physical_idx(self.len - 1)`)
+        //
+        //    H           L
         //   [o o o o o o o . ]
-        //    T             H
+        //    H           L
         // A [o o o o o o o . . . . . . . . . ]
-        //        H T
-        //   [o o . o o o o o ]
-        //          T             H
+        //        L H
+        //   [o o o o o o o o ]
+        //          H           L
         // B [. . . o o o o o o o . . . . . . ]
-        //              H T
-        //   [o o o o o . o o ]
-        //              H                 T
+        //              L H
+        //   [o o o o o o o o ]
+        //            L                   H
         // C [o o o o o . . . . . . . . . o o ]
 
-        if self.tail <= self.head {
+        // can't use is_contiguous() because the capacity is already updated.
+        if self.head <= old_capacity - self.len {
             // A
             // Nop
-        } else if self.head < old_capacity - self.tail {
-            // B
-            unsafe {
-                self.copy_nonoverlapping(old_capacity, 0, self.head);
-            }
-            self.head += old_capacity;
-            debug_assert!(self.head > self.tail);
         } else {
-            // C
-            let new_tail = new_capacity - (old_capacity - self.tail);
-            unsafe {
-                self.copy_nonoverlapping(new_tail, self.tail, old_capacity - self.tail);
+            let head_len = old_capacity - self.head;
+            let tail_len = self.len - head_len;
+            if head_len > tail_len && new_capacity - old_capacity >= tail_len {
+                // B
+                unsafe {
+                    self.copy_nonoverlapping(0, old_capacity, tail_len);
+                }
+            } else {
+                // C
+                let new_head = new_capacity - head_len;
+                unsafe {
+                    // can't use copy_nonoverlapping here, because if e.g. head_len = 2
+                    // and new_capacity = old_capacity + 1, then the heads overlap.
+                    self.copy(self.head, new_head, head_len);
+                }
+                self.head = new_head;
             }
-            self.tail = new_tail;
-            debug_assert!(self.head < self.tail);
         }
-        debug_assert!(self.head < self.cap());
-        debug_assert!(self.tail < self.cap());
-        debug_assert!(self.cap().count_ones() == 1);
+        debug_assert!(self.head < self.capacity() || self.capacity() == 0);
     }
 }
 
@@ -533,6 +531,7 @@ impl<T> VecDeque<T> {
     ///
     /// let deque: VecDeque<u32> = VecDeque::new();
     /// ```
+    // FIXME: This should probably be const
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     #[must_use]
@@ -569,8 +568,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[inline]
     #[unstable(feature = "allocator_api", issue = "32838")]
-    pub fn new_in(alloc: A) -> VecDeque<T, A> {
-        VecDeque::with_capacity_in(INITIAL_CAPACITY, alloc)
+    pub const fn new_in(alloc: A) -> VecDeque<T, A> {
+        VecDeque { head: 0, len: 0, buf: RawVec::new_in(alloc) }
     }
 
     /// Creates an empty deque with space for at least `capacity` elements.
@@ -584,11 +583,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[unstable(feature = "allocator_api", issue = "32838")]
     pub fn with_capacity_in(capacity: usize, alloc: A) -> VecDeque<T, A> {
-        assert!(capacity < 1_usize << usize::BITS - 1, "capacity overflow");
-        // +1 since the ringbuffer always leaves one space empty
-        let cap = cmp::max(capacity + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
-
-        VecDeque { tail: 0, head: 0, buf: RawVec::with_capacity_in(cap, alloc) }
+        VecDeque { head: 0, len: 0, buf: RawVec::with_capacity_in(capacity, alloc) }
     }
 
     /// Provides a reference to the element at the given index.
@@ -608,8 +603,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn get(&self, index: usize) -> Option<&T> {
-        if index < self.len() {
-            let idx = self.wrap_add(self.tail, index);
+        if index < self.len {
+            let idx = self.to_physical_idx(index);
             unsafe { Some(&*self.ptr().add(idx)) }
         } else {
             None
@@ -637,8 +632,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
-        if index < self.len() {
-            let idx = self.wrap_add(self.tail, index);
+        if index < self.len {
+            let idx = self.to_physical_idx(index);
             unsafe { Some(&mut *self.ptr().add(idx)) }
         } else {
             None
@@ -672,8 +667,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     pub fn swap(&mut self, i: usize, j: usize) {
         assert!(i < self.len());
         assert!(j < self.len());
-        let ri = self.wrap_add(self.tail, i);
-        let rj = self.wrap_add(self.tail, j);
+        let ri = self.to_physical_idx(i);
+        let rj = self.to_physical_idx(j);
         unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
     }
 
@@ -691,7 +686,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn capacity(&self) -> usize {
-        self.cap() - 1
+        if T::IS_ZST { usize::MAX } else { self.buf.capacity() }
     }
 
     /// Reserves the minimum capacity for at least `additional` more elements to be inserted in the
@@ -718,7 +713,15 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// [`reserve`]: VecDeque::reserve
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve_exact(&mut self, additional: usize) {
-        self.reserve(additional);
+        let new_cap = self.len.checked_add(additional).expect("capacity overflow");
+        let old_cap = self.capacity();
+
+        if new_cap > old_cap {
+            self.buf.reserve_exact(self.len, additional);
+            unsafe {
+                self.handle_capacity_increase(old_cap);
+            }
+        }
     }
 
     /// Reserves capacity for at least `additional` more elements to be inserted in the given
@@ -739,15 +742,13 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve(&mut self, additional: usize) {
-        let old_cap = self.cap();
-        let used_cap = self.len() + 1;
-        let new_cap = used_cap
-            .checked_add(additional)
-            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
-            .expect("capacity overflow");
+        let new_cap = self.len.checked_add(additional).expect("capacity overflow");
+        let old_cap = self.capacity();
 
         if new_cap > old_cap {
-            self.buf.reserve_exact(used_cap, new_cap - used_cap);
+            // we don't need to reserve_exact(), as the size doesn't have
+            // to be a power of 2.
+            self.buf.reserve(self.len, additional);
             unsafe {
                 self.handle_capacity_increase(old_cap);
             }
@@ -793,7 +794,17 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
-        self.try_reserve(additional)
+        let new_cap =
+            self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
+        let old_cap = self.capacity();
+
+        if new_cap > old_cap {
+            self.buf.try_reserve_exact(self.len, additional)?;
+            unsafe {
+                self.handle_capacity_increase(old_cap);
+            }
+        }
+        Ok(())
     }
 
     /// Tries to reserve capacity for at least `additional` more elements to be inserted
@@ -831,15 +842,12 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
-        let old_cap = self.cap();
-        let used_cap = self.len() + 1;
-        let new_cap = used_cap
-            .checked_add(additional)
-            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
-            .ok_or(TryReserveErrorKind::CapacityOverflow)?;
+        let new_cap =
+            self.len.checked_add(additional).ok_or(TryReserveErrorKind::CapacityOverflow)?;
+        let old_cap = self.capacity();
 
         if new_cap > old_cap {
-            self.buf.try_reserve_exact(used_cap, new_cap - used_cap)?;
+            self.buf.try_reserve(self.len, additional)?;
             unsafe {
                 self.handle_capacity_increase(old_cap);
             }
@@ -890,13 +898,14 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "shrink_to", since = "1.56.0")]
     pub fn shrink_to(&mut self, min_capacity: usize) {
-        let min_capacity = cmp::min(min_capacity, self.capacity());
-        // We don't have to worry about an overflow as neither `self.len()` nor `self.capacity()`
-        // can ever be `usize::MAX`. +1 as the ringbuffer always leaves one space empty.
-        let target_cap = cmp::max(cmp::max(min_capacity, self.len()) + 1, MINIMUM_CAPACITY + 1)
-            .next_power_of_two();
+        let target_cap = min_capacity.max(self.len);
 
-        if target_cap < self.cap() {
+        // never shrink ZSTs
+        if T::IS_ZST || self.capacity() <= target_cap {
+            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
@@ -905,49 +914,55 @@ impl<T, A: Allocator> VecDeque<T, A> {
             // At all other times, element positions are unaffected.
             //
             // Indicates that elements at the head should be moved.
-            let head_outside = self.head == 0 || self.head >= target_cap;
+
+            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.tail >= target_cap && head_outside {
-                //                    T             H
+            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 . ]
-                //    T             H
+                //    H           L
                 //   [o o o o o o o . ]
                 unsafe {
-                    self.copy_nonoverlapping(0, self.tail, self.len());
+                    // nonoverlapping because self.head >= target_cap >= self.len
+                    self.copy_nonoverlapping(self.head, 0, self.len);
                 }
-                self.head = self.len();
-                self.tail = 0;
-            } else if self.tail != 0 && self.tail < target_cap && head_outside {
-                //          T             H
+                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 T
+                //      L   H
                 //   [o o . o o o o o ]
-                let len = self.wrap_sub(self.head, target_cap);
+                let len = self.head + self.len - target_cap;
                 unsafe {
-                    self.copy_nonoverlapping(0, target_cap, len);
+                    self.copy_nonoverlapping(target_cap, 0, len);
                 }
-                self.head = len;
-                debug_assert!(self.head < self.tail);
-            } else if self.tail >= target_cap {
-                //              H                 T
+            } else if self.head >= target_cap {
+                //  H := head
+                //  L := last element
+                //            L                   H
                 //   [o o o o o . . . . . . . . . o o ]
-                //              H T
+                //            L   H
                 //   [o o o o o . o o ]
-                debug_assert!(self.wrap_sub(self.head, 1) < target_cap);
-                let len = self.cap() - self.tail;
-                let new_tail = target_cap - len;
+                let len = self.capacity() - self.head;
+                let new_head = target_cap - len;
                 unsafe {
-                    self.copy_nonoverlapping(new_tail, self.tail, len);
+                    // can't use copy_nonoverlapping here for the same reason
+                    // as in `handle_capacity_increase()`
+                    self.copy(self.head, new_head, len);
                 }
-                self.tail = new_tail;
-                debug_assert!(self.head < self.tail);
+                self.head = new_head;
             }
 
             self.buf.shrink_to_fit(target_cap);
 
-            debug_assert!(self.head < self.cap());
-            debug_assert!(self.tail < self.cap());
-            debug_assert!(self.cap().count_ones() == 1);
+            debug_assert!(self.head < self.capacity() || self.capacity() == 0);
+            debug_assert!(self.len <= self.capacity());
         }
     }
 
@@ -992,20 +1007,20 @@ impl<T, A: Allocator> VecDeque<T, A> {
         // * The head of the VecDeque is moved before calling `drop_in_place`,
         //   so no value is dropped twice if `drop_in_place` panics
         unsafe {
-            if len > self.len() {
+            if len >= self.len {
                 return;
             }
-            let num_dropped = self.len() - len;
+
             let (front, back) = self.as_mut_slices();
             if len > front.len() {
                 let begin = len - front.len();
                 let drop_back = back.get_unchecked_mut(begin..) as *mut _;
-                self.head = self.wrap_sub(self.head, num_dropped);
+                self.len = len;
                 ptr::drop_in_place(drop_back);
             } else {
                 let drop_back = back as *mut _;
                 let drop_front = front.get_unchecked_mut(len..) as *mut _;
-                self.head = self.wrap_sub(self.head, num_dropped);
+                self.len = len;
 
                 // Make sure the second half is dropped even when a destructor
                 // in the first one panics.
@@ -1039,7 +1054,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter(&self) -> Iter<'_, T> {
-        Iter::new(unsafe { self.buffer_as_slice() }, self.tail, self.head)
+        let (a, b) = self.as_slices();
+        Iter::new(a.iter(), b.iter())
     }
 
     /// Returns a front-to-back iterator that returns mutable references.
@@ -1061,11 +1077,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
-        // SAFETY: The internal `IterMut` safety invariant is established because the
-        // `ring` we create is a dereferenceable slice for lifetime '_.
-        let ring = ptr::slice_from_raw_parts_mut(self.ptr(), self.cap());
-
-        unsafe { IterMut::new(ring, self.tail, self.head, PhantomData) }
+        let (a, b) = self.as_mut_slices();
+        IterMut::new(a.iter_mut(), b.iter_mut())
     }
 
     /// Returns a pair of slices which contain, in order, the contents of the
@@ -1097,14 +1110,10 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn as_slices(&self) -> (&[T], &[T]) {
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            let buf = self.buffer_as_slice();
-            let (front, back) = RingSlices::ring_slices(buf, self.head, self.tail);
-            (MaybeUninit::slice_assume_init_ref(front), MaybeUninit::slice_assume_init_ref(back))
-        }
+        let (a_range, b_range) = self.slice_ranges(..);
+        // SAFETY: `slice_ranges` always returns valid ranges into
+        // the physical buffer.
+        unsafe { (&*self.buffer_range(a_range), &*self.buffer_range(b_range)) }
     }
 
     /// Returns a pair of slices which contain, in order, the contents of the
@@ -1135,16 +1144,10 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            let head = self.head;
-            let tail = self.tail;
-            let buf = self.buffer_as_mut_slice();
-            let (front, back) = RingSlices::ring_slices(buf, head, tail);
-            (MaybeUninit::slice_assume_init_mut(front), MaybeUninit::slice_assume_init_mut(back))
-        }
+        let (a_range, b_range) = self.slice_ranges(..);
+        // SAFETY: `slice_ranges` always returns valid ranges into
+        // the physical buffer.
+        unsafe { (&mut *self.buffer_range(a_range), &mut *self.buffer_range(b_range)) }
     }
 
     /// Returns the number of elements in the deque.
@@ -1161,7 +1164,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn len(&self) -> usize {
-        count(self.tail, self.head, self.cap())
+        self.len
     }
 
     /// Returns `true` if the deque is empty.
@@ -1178,17 +1181,41 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn is_empty(&self) -> bool {
-        self.tail == self.head
+        self.len == 0
     }
 
-    fn range_tail_head<R>(&self, range: R) -> (usize, usize)
+    /// Given a range into the logical buffer of the deque, this function
+    /// return two ranges into the physical buffer that correspond to
+    /// the given range.
+    fn slice_ranges<R>(&self, range: R) -> (Range<usize>, Range<usize>)
     where
         R: RangeBounds<usize>,
     {
-        let Range { start, end } = slice::range(range, ..self.len());
-        let tail = self.wrap_add(self.tail, start);
-        let head = self.wrap_add(self.tail, end);
-        (tail, head)
+        let Range { start, end } = slice::range(range, ..self.len);
+        let len = end - start;
+
+        if len == 0 {
+            (0..0, 0..0)
+        } else {
+            // `slice::range` guarantees that `start <= end <= self.len`.
+            // because `len != 0`, we know that `start < end`, so `start < self.len`
+            // and the indexing is valid.
+            let wrapped_start = self.to_physical_idx(start);
+
+            // this subtraction can never overflow because `wrapped_start` is
+            // at most `self.capacity()` (and if `self.capacity != 0`, then `wrapped_start` is strictly less
+            // than `self.capacity`).
+            let head_len = self.capacity() - wrapped_start;
+
+            if head_len >= len {
+                // we know that `len + wrapped_start <= self.capacity <= usize::MAX`, so this addition can't overflow
+                (wrapped_start..wrapped_start + len, 0..0)
+            } else {
+                // can't overflow because of the if condition
+                let tail_len = len - head_len;
+                (wrapped_start..self.capacity(), 0..tail_len)
+            }
+        }
     }
 
     /// Creates an iterator that covers the specified range in the deque.
@@ -1217,9 +1244,14 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         R: RangeBounds<usize>,
     {
-        let (tail, head) = self.range_tail_head(range);
-        // The shared reference we have in &self is maintained in the '_ of Iter.
-        Iter::new(unsafe { self.buffer_as_slice() }, tail, head)
+        let (a_range, b_range) = self.slice_ranges(range);
+        // SAFETY: The ranges returned by `slice_ranges`
+        // are valid ranges into the physical buffer, so
+        // it's ok to pass them to `buffer_range` and
+        // dereference the result.
+        let a = unsafe { &*self.buffer_range(a_range) };
+        let b = unsafe { &*self.buffer_range(b_range) };
+        Iter::new(a.iter(), b.iter())
     }
 
     /// Creates an iterator that covers the specified mutable range in the deque.
@@ -1252,13 +1284,14 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         R: RangeBounds<usize>,
     {
-        let (tail, head) = self.range_tail_head(range);
-
-        // SAFETY: The internal `IterMut` safety invariant is established because the
-        // `ring` we create is a dereferenceable slice for lifetime '_.
-        let ring = ptr::slice_from_raw_parts_mut(self.ptr(), self.cap());
-
-        unsafe { IterMut::new(ring, tail, head, PhantomData) }
+        let (a_range, b_range) = self.slice_ranges(range);
+        // SAFETY: The ranges returned by `slice_ranges`
+        // are valid ranges into the physical buffer, so
+        // it's ok to pass them to `buffer_range` and
+        // dereference the result.
+        let a = unsafe { &mut *self.buffer_range(a_range) };
+        let b = unsafe { &mut *self.buffer_range(b_range) };
+        IterMut::new(a.iter_mut(), b.iter_mut())
     }
 
     /// Removes the specified range from the deque in bulk, returning all
@@ -1310,39 +1343,30 @@ impl<T, A: Allocator> VecDeque<T, A> {
         // When finished, the remaining data will be copied back to cover the hole,
         // and the head/tail values will be restored correctly.
         //
-        let (drain_tail, drain_head) = self.range_tail_head(range);
+        let Range { start, end } = slice::range(range, ..self.len);
+        let drain_start = start;
+        let drain_len = end - start;
 
         // The deque's elements are parted into three segments:
-        // * self.tail  -> drain_tail
-        // * drain_tail -> drain_head
-        // * drain_head -> self.head
+        // * 0  -> drain_start
+        // * drain_start -> drain_start+drain_len
+        // * drain_start+drain_len -> self.len
         //
-        // T = self.tail; H = self.head; t = drain_tail; h = drain_head
+        // H = self.head; T = self.head+self.len; t = drain_start+drain_len; h = drain_head
         //
-        // We store drain_tail as self.head, and drain_head and self.head as
-        // after_tail and after_head respectively on the Drain. This also
+        // We store drain_start as self.len, and drain_len and self.len as
+        // drain_len and orig_len respectively on the Drain. This also
         // truncates the effective array such that if the Drain is leaked, we
         // have forgotten about the potentially moved values after the start of
         // the drain.
         //
-        //        T   t   h   H
+        //        H   h   t   T
         // [. . . o o x x o o . . .]
         //
-        let head = self.head;
-
         // "forget" about the values after the start of the drain until after
         // the drain is complete and the Drain destructor is run.
-        self.head = drain_tail;
 
-        let deque = NonNull::from(&mut *self);
-        unsafe {
-            // Crucially, we only create shared references from `self` here and read from
-            // it.  We do not write to `self` nor reborrow to a mutable reference.
-            // Hence the raw pointer we created above, for `deque`, remains valid.
-            let ring = self.buffer_as_slice();
-
-            Drain::new(drain_head, head, ring, drain_tail, drain_head, deque)
-        }
+        unsafe { Drain::new(self, drain_start, drain_len) }
     }
 
     /// Clears the deque, removing all values.
@@ -1361,6 +1385,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     pub fn clear(&mut self) {
         self.truncate(0);
+        // Not strictly necessary, but leaves things in a more consistent/predictable state.
+        self.head = 0;
     }
 
     /// Returns `true` if the deque contains an element equal to the
@@ -1455,7 +1481,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back(&self) -> Option<&T> {
-        self.get(self.len().wrapping_sub(1))
+        self.get(self.len.wrapping_sub(1))
     }
 
     /// Provides a mutable reference to the back element, or `None` if the
@@ -1479,7 +1505,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn back_mut(&mut self) -> Option<&mut T> {
-        self.get_mut(self.len().wrapping_sub(1))
+        self.get_mut(self.len.wrapping_sub(1))
     }
 
     /// Removes the first element and returns it, or `None` if the deque is
@@ -1503,9 +1529,10 @@ impl<T, A: Allocator> VecDeque<T, A> {
         if self.is_empty() {
             None
         } else {
-            let tail = self.tail;
-            self.tail = self.wrap_add(self.tail, 1);
-            unsafe { Some(self.buffer_read(tail)) }
+            let old_head = self.head;
+            self.head = self.to_physical_idx(1);
+            self.len -= 1;
+            Some(unsafe { self.buffer_read(old_head) })
         }
     }
 
@@ -1528,9 +1555,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         if self.is_empty() {
             None
         } else {
-            self.head = self.wrap_sub(self.head, 1);
-            let head = self.head;
-            unsafe { Some(self.buffer_read(head)) }
+            self.len -= 1;
+            Some(unsafe { self.buffer_read(self.to_physical_idx(self.len)) })
         }
     }
 
@@ -1552,10 +1578,11 @@ impl<T, A: Allocator> VecDeque<T, A> {
             self.grow();
         }
 
-        self.tail = self.wrap_sub(self.tail, 1);
-        let tail = self.tail;
+        self.head = self.wrap_sub(self.head, 1);
+        self.len += 1;
+
         unsafe {
-            self.buffer_write(tail, value);
+            self.buffer_write(self.head, value);
         }
     }
 
@@ -1577,16 +1604,14 @@ impl<T, A: Allocator> VecDeque<T, A> {
             self.grow();
         }
 
-        let head = self.head;
-        self.head = self.wrap_add(self.head, 1);
-        unsafe { self.buffer_write(head, value) }
+        unsafe { self.buffer_write(self.to_physical_idx(self.len), value) }
+        self.len += 1;
     }
 
     #[inline]
     fn is_contiguous(&self) -> bool {
-        // FIXME: Should we consider `head == 0` to mean
-        // that `self` is contiguous?
-        self.tail <= self.head
+        // Do the calculation like this to avoid overflowing if len + head > usize::MAX
+        self.head <= self.capacity() - self.len
     }
 
     /// Removes an element from anywhere in the deque and returns it,
@@ -1615,8 +1640,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
-        let length = self.len();
-        if length > 0 && index < length && index != 0 {
+        let length = self.len;
+        if index < length && index != 0 {
             self.swap(index, 0);
         } else if index >= length {
             return None;
@@ -1650,7 +1675,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
-        let length = self.len();
+        let length = self.len;
         if length > 0 && index < length - 1 {
             self.swap(index, length - 1);
         } else if index >= length {
@@ -1689,198 +1714,26 @@ impl<T, A: Allocator> VecDeque<T, A> {
             self.grow();
         }
 
-        // Move the least number of elements in the ring buffer and insert
-        // the given object
-        //
-        // At most len/2 - 1 elements will be moved. O(min(n, n-i))
-        //
-        // There are three main cases:
-        //  Elements are contiguous
-        //      - special case when tail is 0
-        //  Elements are discontiguous and the insert is in the tail section
-        //  Elements are discontiguous and the insert is in the head section
-        //
-        // For each of those there are two more cases:
-        //  Insert is closer to tail
-        //  Insert is closer to head
-        //
-        // Key: H - self.head
-        //      T - self.tail
-        //      o - Valid element
-        //      I - Insertion element
-        //      A - The element that should be after the insertion point
-        //      M - Indicates element was moved
-
-        let idx = self.wrap_add(self.tail, index);
-
-        let distance_to_tail = index;
-        let distance_to_head = self.len() - index;
-
-        let contiguous = self.is_contiguous();
-
-        match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
-            (true, true, _) if index == 0 => {
-                // push_front
-                //
-                //       T
-                //       I             H
-                //      [A o o o o o o . . . . . . . . .]
-                //
-                //                       H         T
-                //      [A o o o o o o o . . . . . I]
-                //
-
-                self.tail = self.wrap_sub(self.tail, 1);
-            }
-            (true, true, _) => {
-                unsafe {
-                    // contiguous, insert closer to tail:
-                    //
-                    //             T   I         H
-                    //      [. . . o o A o o o o . . . . . .]
-                    //
-                    //           T               H
-                    //      [. . o o I A o o o o . . . . . .]
-                    //           M M
-                    //
-                    // contiguous, insert closer to tail and tail is 0:
-                    //
-                    //
-                    //       T   I         H
-                    //      [o o A o o o o . . . . . . . . .]
-                    //
-                    //                       H             T
-                    //      [o I A o o o o o . . . . . . . o]
-                    //       M                             M
-
-                    let new_tail = self.wrap_sub(self.tail, 1);
-
-                    self.copy(new_tail, self.tail, 1);
-                    // Already moved the tail, so we only copy `index - 1` elements.
-                    self.copy(self.tail, self.tail + 1, index - 1);
-
-                    self.tail = new_tail;
-                }
-            }
-            (true, false, _) => {
-                unsafe {
-                    //  contiguous, insert closer to head:
-                    //
-                    //             T       I     H
-                    //      [. . . o o o o A o o . . . . . .]
-                    //
-                    //             T               H
-                    //      [. . . o o o o I A o o . . . . .]
-                    //                       M M M
-
-                    self.copy(idx + 1, idx, self.head - idx);
-                    self.head = self.wrap_add(self.head, 1);
-                }
-            }
-            (false, true, true) => {
-                unsafe {
-                    // discontiguous, insert closer to tail, tail section:
-                    //
-                    //                   H         T   I
-                    //      [o o o o o o . . . . . o o A o o]
-                    //
-                    //                   H       T
-                    //      [o o o o o o . . . . o o I A o o]
-                    //                           M M
-
-                    self.copy(self.tail - 1, self.tail, index);
-                    self.tail -= 1;
-                }
-            }
-            (false, false, true) => {
-                unsafe {
-                    // discontiguous, insert closer to head, tail section:
-                    //
-                    //           H             T         I
-                    //      [o o . . . . . . . o o o o o A o]
-                    //
-                    //             H           T
-                    //      [o o o . . . . . . o o o o o I A]
-                    //       M M M                         M
-
-                    // copy elements up to new head
-                    self.copy(1, 0, self.head);
-
-                    // copy last element into empty spot at bottom of buffer
-                    self.copy(0, self.cap() - 1, 1);
-
-                    // move elements from idx to end forward not including ^ element
-                    self.copy(idx + 1, idx, self.cap() - 1 - idx);
-
-                    self.head += 1;
-                }
-            }
-            (false, true, false) if idx == 0 => {
-                unsafe {
-                    // discontiguous, insert is closer to tail, head section,
-                    // and is at index zero in the internal buffer:
-                    //
-                    //       I                   H     T
-                    //      [A o o o o o o o o o . . . o o o]
-                    //
-                    //                           H   T
-                    //      [A o o o o o o o o o . . o o o I]
-                    //                               M M M
-
-                    // copy elements up to new tail
-                    self.copy(self.tail - 1, self.tail, self.cap() - self.tail);
-
-                    // copy last element into empty spot at bottom of buffer
-                    self.copy(self.cap() - 1, 0, 1);
-
-                    self.tail -= 1;
-                }
-            }
-            (false, true, false) => {
-                unsafe {
-                    // discontiguous, insert closer to tail, head section:
-                    //
-                    //             I             H     T
-                    //      [o o o A o o o o o o . . . o o o]
-                    //
-                    //                           H   T
-                    //      [o o I A o o o o o o . . o o o o]
-                    //       M M                     M M M M
-
-                    // copy elements up to new tail
-                    self.copy(self.tail - 1, self.tail, self.cap() - self.tail);
-
-                    // copy last element into empty spot at bottom of buffer
-                    self.copy(self.cap() - 1, 0, 1);
-
-                    // move elements from idx-1 to end forward not including ^ element
-                    self.copy(0, 1, idx - 1);
-
-                    self.tail -= 1;
-                }
+        let k = self.len - index;
+        if k < index {
+            // `index + 1` can't overflow, because if index was usize::MAX, then either the
+            // assert would've failed, or the deque would've tried to grow past usize::MAX
+            // and panicked.
+            unsafe {
+                // see `remove()` for explanation why this wrap_copy() call is safe.
+                self.wrap_copy(self.to_physical_idx(index), self.to_physical_idx(index + 1), k);
+                self.buffer_write(self.to_physical_idx(index), value);
+                self.len += 1;
             }
-            (false, false, false) => {
-                unsafe {
-                    // discontiguous, insert closer to head, head section:
-                    //
-                    //               I     H           T
-                    //      [o o o o A o o . . . . . . o o o]
-                    //
-                    //                     H           T
-                    //      [o o o o I A o o . . . . . o o o]
-                    //                 M M M
-
-                    self.copy(idx + 1, idx, self.head - idx);
-                    self.head += 1;
-                }
+        } else {
+            let old_head = self.head;
+            self.head = self.wrap_sub(self.head, 1);
+            unsafe {
+                self.wrap_copy(old_head, self.head, index);
+                self.buffer_write(self.to_physical_idx(index), value);
+                self.len += 1;
             }
         }
-
-        // tail might've been changed so we need to recalculate
-        let new_idx = self.wrap_add(self.tail, index);
-        unsafe {
-            self.buffer_write(new_idx, value);
-        }
     }
 
     /// Removes and returns the element at `index` from the deque.
@@ -1906,156 +1759,26 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn remove(&mut self, index: usize) -> Option<T> {
-        if self.is_empty() || self.len() <= index {
+        if self.len <= index {
             return None;
         }
 
-        // There are three main cases:
-        //  Elements are contiguous
-        //  Elements are discontiguous and the removal is in the tail section
-        //  Elements are discontiguous and the removal is in the head section
-        //      - special case when elements are technically contiguous,
-        //        but self.head = 0
-        //
-        // For each of those there are two more cases:
-        //  Insert is closer to tail
-        //  Insert is closer to head
-        //
-        // Key: H - self.head
-        //      T - self.tail
-        //      o - Valid element
-        //      x - Element marked for removal
-        //      R - Indicates element that is being removed
-        //      M - Indicates element was moved
-
-        let idx = self.wrap_add(self.tail, index);
-
-        let elem = unsafe { Some(self.buffer_read(idx)) };
+        let wrapped_idx = self.to_physical_idx(index);
 
-        let distance_to_tail = index;
-        let distance_to_head = self.len() - index;
+        let elem = unsafe { Some(self.buffer_read(wrapped_idx)) };
 
-        let contiguous = self.is_contiguous();
-
-        match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
-            (true, true, _) => {
-                unsafe {
-                    // contiguous, remove closer to tail:
-                    //
-                    //             T   R         H
-                    //      [. . . o o x o o o o . . . . . .]
-                    //
-                    //               T           H
-                    //      [. . . . o o o o o o . . . . . .]
-                    //               M M
-
-                    self.copy(self.tail + 1, self.tail, index);
-                    self.tail += 1;
-                }
-            }
-            (true, false, _) => {
-                unsafe {
-                    // contiguous, remove closer to head:
-                    //
-                    //             T       R     H
-                    //      [. . . o o o o x o o . . . . . .]
-                    //
-                    //             T           H
-                    //      [. . . o o o o o o . . . . . . .]
-                    //                     M M
-
-                    self.copy(idx, idx + 1, self.head - idx - 1);
-                    self.head -= 1;
-                }
-            }
-            (false, true, true) => {
-                unsafe {
-                    // discontiguous, remove closer to tail, tail section:
-                    //
-                    //                   H         T   R
-                    //      [o o o o o o . . . . . o o x o o]
-                    //
-                    //                   H           T
-                    //      [o o o o o o . . . . . . o o o o]
-                    //                               M M
-
-                    self.copy(self.tail + 1, self.tail, index);
-                    self.tail = self.wrap_add(self.tail, 1);
-                }
-            }
-            (false, false, false) => {
-                unsafe {
-                    // discontiguous, remove closer to head, head section:
-                    //
-                    //               R     H           T
-                    //      [o o o o x o o . . . . . . o o o]
-                    //
-                    //                   H             T
-                    //      [o o o o o o . . . . . . . o o o]
-                    //               M M
-
-                    self.copy(idx, idx + 1, self.head - idx - 1);
-                    self.head -= 1;
-                }
-            }
-            (false, false, true) => {
-                unsafe {
-                    // discontiguous, remove closer to head, tail section:
-                    //
-                    //             H           T         R
-                    //      [o o o . . . . . . o o o o o x o]
-                    //
-                    //           H             T
-                    //      [o o . . . . . . . o o o o o o o]
-                    //       M M                         M M
-                    //
-                    // or quasi-discontiguous, remove next to head, tail section:
-                    //
-                    //       H                 T         R
-                    //      [. . . . . . . . . o o o o o x o]
-                    //
-                    //                         T           H
-                    //      [. . . . . . . . . o o o o o o .]
-                    //                                   M
-
-                    // draw in elements in the tail section
-                    self.copy(idx, idx + 1, self.cap() - idx - 1);
-
-                    // Prevents underflow.
-                    if self.head != 0 {
-                        // copy first element into empty spot
-                        self.copy(self.cap() - 1, 0, 1);
-
-                        // move elements in the head section backwards
-                        self.copy(0, 1, self.head - 1);
-                    }
-
-                    self.head = self.wrap_sub(self.head, 1);
-                }
-            }
-            (false, true, false) => {
-                unsafe {
-                    // discontiguous, remove closer to tail, head section:
-                    //
-                    //           R               H     T
-                    //      [o o x o o o o o o o . . . o o o]
-                    //
-                    //                           H       T
-                    //      [o o o o o o o o o o . . . . o o]
-                    //       M M M                       M M
-
-                    // draw in elements up to idx
-                    self.copy(1, 0, idx);
-
-                    // copy last element into empty spot
-                    self.copy(0, self.cap() - 1, 1);
-
-                    // move elements from tail to end forward, excluding the last one
-                    self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1);
-
-                    self.tail = self.wrap_add(self.tail, 1);
-                }
-            }
+        let k = self.len - index - 1;
+        // safety: due to the nature of the if-condition, whichever wrap_copy gets called,
+        // its length argument will be at most `self.len / 2`, so there can't be more than
+        // one overlapping area.
+        if k < index {
+            unsafe { self.wrap_copy(self.wrap_add(wrapped_idx, 1), wrapped_idx, k) };
+            self.len -= 1;
+        } else {
+            let old_head = self.head;
+            self.head = self.to_physical_idx(1);
+            unsafe { self.wrap_copy(old_head, self.head, index) };
+            self.len -= 1;
         }
 
         elem
@@ -2091,7 +1814,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         A: Clone,
     {
-        let len = self.len();
+        let len = self.len;
         assert!(at <= len, "`at` out of bounds");
 
         let other_len = len - at;
@@ -2128,8 +1851,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         }
 
         // Cleanup where the ends of the buffers are
-        self.head = self.wrap_sub(self.head, other_len);
-        other.head = other.wrap_index(other_len);
+        self.len = at;
+        other.len = other_len;
 
         other
     }
@@ -2154,17 +1877,26 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[inline]
     #[stable(feature = "append", since = "1.4.0")]
     pub fn append(&mut self, other: &mut Self) {
-        self.reserve(other.len());
+        if T::IS_ZST {
+            self.len += other.len;
+            other.len = 0;
+            other.head = 0;
+            return;
+        }
+
+        self.reserve(other.len);
         unsafe {
             let (left, right) = other.as_slices();
-            self.copy_slice(self.head, left);
-            self.copy_slice(self.wrap_add(self.head, left.len()), right);
+            self.copy_slice(self.to_physical_idx(self.len), left);
+            // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len()
+            self.copy_slice(self.to_physical_idx(self.len + left.len()), right);
         }
         // SAFETY: Update pointers after copying to avoid leaving doppelganger
         // in case of panics.
-        self.head = self.wrap_add(self.head, other.len());
-        // Silently drop values in `other`.
-        other.tail = other.head;
+        self.len += other.len;
+        // Now that we own its values, forget everything in `other`.
+        other.len = 0;
+        other.head = 0;
     }
 
     /// Retains only the elements specified by the predicate.
@@ -2232,7 +1964,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     where
         F: FnMut(&mut T) -> bool,
     {
-        let len = self.len();
+        let len = self.len;
         let mut idx = 0;
         let mut cur = 0;
 
@@ -2270,9 +2002,8 @@ impl<T, A: Allocator> VecDeque<T, A> {
         // Extend or possibly remove this assertion when valid use-cases for growing the
         // buffer without it being full emerge
         debug_assert!(self.is_full());
-        let old_cap = self.cap();
-        self.buf.reserve_exact(old_cap, old_cap);
-        assert!(self.cap() == old_cap * 2);
+        let old_cap = self.capacity();
+        self.buf.reserve_for_push(old_cap);
         unsafe {
             self.handle_capacity_increase(old_cap);
         }
@@ -2306,7 +2037,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "vec_resize_with", since = "1.33.0")]
     pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
-        let len = self.len();
+        let len = self.len;
 
         if new_len > len {
             self.extend(repeat_with(generator).take(new_len - len))
@@ -2372,110 +2103,129 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "deque_make_contiguous", since = "1.48.0")]
     pub fn make_contiguous(&mut self) -> &mut [T] {
+        if T::IS_ZST {
+            self.head = 0;
+        }
+
         if self.is_contiguous() {
-            let tail = self.tail;
-            let head = self.head;
-            // Safety:
-            // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-            // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-            return unsafe {
-                MaybeUninit::slice_assume_init_mut(
-                    RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0,
-                )
-            };
+            unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }
         }
 
-        let buf = self.buf.ptr();
-        let cap = self.cap();
-        let len = self.len();
+        let &mut Self { head, len, .. } = self;
+        let ptr = self.ptr();
+        let cap = self.capacity();
 
-        let free = self.tail - self.head;
-        let tail_len = cap - self.tail;
+        let free = cap - len;
+        let head_len = cap - head;
+        let tail = len - head_len;
+        let tail_len = tail;
 
-        if free >= tail_len {
-            // there is enough free space to copy the tail in one go,
-            // this means that we first shift the head backwards, and then
-            // copy the tail to the correct position.
+        if free >= head_len {
+            // there is enough free space to copy the head in one go,
+            // this means that we first shift the tail backwards, and then
+            // copy the head to the correct position.
             //
             // from: DEFGH....ABC
             // to:   ABCDEFGH....
             unsafe {
-                ptr::copy(buf, buf.add(tail_len), self.head);
+                self.copy(0, head_len, tail_len);
                 // ...DEFGH.ABC
-                ptr::copy_nonoverlapping(buf.add(self.tail), buf, tail_len);
+                self.copy_nonoverlapping(head, 0, head_len);
                 // ABCDEFGH....
-
-                self.tail = 0;
-                self.head = len;
             }
-        } else if free > self.head {
-            // FIXME: We currently do not consider ....ABCDEFGH
-            // to be contiguous because `head` would be `0` in this
-            // case. While we probably want to change this it
-            // isn't trivial as a few places expect `is_contiguous`
-            // to mean that we can just slice using `buf[tail..head]`.
 
-            // there is enough free space to copy the head in one go,
-            // this means that we first shift the tail forwards, and then
-            // copy the head to the correct position.
+            self.head = 0;
+        } else if free >= tail_len {
+            // there is enough free space to copy the tail in one go,
+            // this means that we first shift the head forwards, and then
+            // copy the tail to the correct position.
             //
             // from: FGH....ABCDE
             // to:   ...ABCDEFGH.
             unsafe {
-                ptr::copy(buf.add(self.tail), buf.add(self.head), tail_len);
+                self.copy(head, tail, head_len);
                 // FGHABCDE....
-                ptr::copy_nonoverlapping(buf, buf.add(self.head + tail_len), self.head);
+                self.copy_nonoverlapping(0, tail + head_len, tail_len);
                 // ...ABCDEFGH.
-
-                self.tail = self.head;
-                self.head = self.wrap_add(self.tail, len);
             }
+
+            self.head = tail;
         } else {
-            // free is smaller than both head and tail,
-            // this means we have to slowly "swap" the tail and the head.
+            // `free` is smaller than both `head_len` and `tail_len`.
+            // the general algorithm for this first moves the slices
+            // right next to each other and then uses `slice::rotate`
+            // to rotate them into place:
             //
-            // from: EFGHI...ABCD or HIJK.ABCDEFG
-            // to:   ABCDEFGHI... or ABCDEFGHIJK.
-            let mut left_edge: usize = 0;
-            let mut right_edge: usize = self.tail;
-            unsafe {
-                // The general problem looks like this
-                // GHIJKLM...ABCDEF - before any swaps
-                // ABCDEFM...GHIJKL - after 1 pass of swaps
-                // ABCDEFGHIJM...KL - swap until the left edge reaches the temp store
-                //                  - then restart the algorithm with a new (smaller) store
-                // Sometimes the temp store is reached when the right edge is at the end
-                // of the buffer - this means we've hit the right order with fewer swaps!
-                // E.g
-                // EF..ABCD
-                // ABCDEF.. - after four only swaps we've finished
-                while left_edge < len && right_edge != cap {
-                    let mut right_offset = 0;
-                    for i in left_edge..right_edge {
-                        right_offset = (i - left_edge) % (cap - right_edge);
-                        let src = right_edge + right_offset;
-                        ptr::swap(buf.add(i), buf.add(src));
+            // initially:   HIJK..ABCDEFG
+            // step 1:      ..HIJKABCDEFG
+            // step 2:      ..ABCDEFGHIJK
+            //
+            // or:
+            //
+            // initially:   FGHIJK..ABCDE
+            // step 1:      FGHIJKABCDE..
+            // step 2:      ABCDEFGHIJK..
+
+            // pick the shorter of the 2 slices to reduce the amount
+            // of memory that needs to be moved around.
+            if head_len > tail_len {
+                // tail is shorter, so:
+                //  1. copy tail forwards
+                //  2. rotate used part of the buffer
+                //  3. update head to point to the new beginning (which is just `free`)
+
+                unsafe {
+                    // if there is no free space in the buffer, then the slices are already
+                    // right next to each other and we don't need to move any memory.
+                    if free != 0 {
+                        // because we only move the tail forward as much as there's free space
+                        // behind it, we don't overwrite any elements of the head slice, and
+                        // the slices end up right next to each other.
+                        self.copy(0, free, tail_len);
                     }
-                    let n_ops = right_edge - left_edge;
-                    left_edge += n_ops;
-                    right_edge += right_offset + 1;
+
+                    // We just copied the tail right next to the head slice,
+                    // so all of the elements in the range are initialized
+                    let slice = &mut *self.buffer_range(free..self.capacity());
+
+                    // because the deque wasn't contiguous, we know that `tail_len < self.len == slice.len()`,
+                    // so this will never panic.
+                    slice.rotate_left(tail_len);
+
+                    // the used part of the buffer now is `free..self.capacity()`, so set
+                    // `head` to the beginning of that range.
+                    self.head = free;
                 }
+            } else {
+                // head is shorter so:
+                //  1. copy head backwards
+                //  2. rotate used part of the buffer
+                //  3. update head to point to the new beginning (which is the beginning of the buffer)
+
+                unsafe {
+                    // if there is no free space in the buffer, then the slices are already
+                    // right next to each other and we don't need to move any memory.
+                    if free != 0 {
+                        // copy the head slice to lie right behind the tail slice.
+                        self.copy(self.head, tail_len, head_len);
+                    }
 
-                self.tail = 0;
-                self.head = len;
+                    // because we copied the head slice so that both slices lie right
+                    // next to each other, all the elements in the range are initialized.
+                    let slice = &mut *self.buffer_range(0..self.len);
+
+                    // because the deque wasn't contiguous, we know that `head_len < self.len == slice.len()`
+                    // so this will never panic.
+                    slice.rotate_right(head_len);
+
+                    // the used part of the buffer now is `0..self.len`, so set
+                    // `head` to the beginning of that range.
+                    self.head = 0;
+                }
             }
         }
 
-        let tail = self.tail;
-        let head = self.head;
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            MaybeUninit::slice_assume_init_mut(
-                RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0,
-            )
-        }
+        unsafe { slice::from_raw_parts_mut(ptr.add(self.head), self.len) }
     }
 
     /// Rotates the double-ended queue `mid` places to the left.
@@ -2513,7 +2263,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
     pub fn rotate_left(&mut self, mid: usize) {
         assert!(mid <= self.len());
-        let k = self.len() - mid;
+        let k = self.len - mid;
         if mid <= k {
             unsafe { self.rotate_left_inner(mid) }
         } else {
@@ -2556,7 +2306,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
     #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
     pub fn rotate_right(&mut self, k: usize) {
         assert!(k <= self.len());
-        let mid = self.len() - k;
+        let mid = self.len - k;
         if k <= mid {
             unsafe { self.rotate_right_inner(k) }
         } else {
@@ -2567,26 +2317,24 @@ impl<T, A: Allocator> VecDeque<T, A> {
     // SAFETY: the following two methods require that the rotation amount
     // be less than half the length of the deque.
     //
-    // `wrap_copy` requires that `min(x, cap() - x) + copy_len <= cap()`,
-    // but than `min` is never more than half the capacity, regardless of x,
+    // `wrap_copy` requires that `min(x, capacity() - x) + copy_len <= capacity()`,
+    // but then `min` is never more than half the capacity, regardless of x,
     // so it's sound to call here because we're calling with something
     // less than half the length, which is never above half the capacity.
 
     unsafe fn rotate_left_inner(&mut self, mid: usize) {
         debug_assert!(mid * 2 <= self.len());
         unsafe {
-            self.wrap_copy(self.head, self.tail, mid);
+            self.wrap_copy(self.head, self.to_physical_idx(self.len), mid);
         }
-        self.head = self.wrap_add(self.head, mid);
-        self.tail = self.wrap_add(self.tail, mid);
+        self.head = self.to_physical_idx(mid);
     }
 
     unsafe fn rotate_right_inner(&mut self, k: usize) {
         debug_assert!(k * 2 <= self.len());
         self.head = self.wrap_sub(self.head, k);
-        self.tail = self.wrap_sub(self.tail, k);
         unsafe {
-            self.wrap_copy(self.tail, self.head, k);
+            self.wrap_copy(self.to_physical_idx(self.len), self.head, k);
         }
     }
 
@@ -2833,29 +2581,30 @@ impl<T: Clone, A: Allocator> VecDeque<T, A> {
     /// ```
     #[stable(feature = "deque_extras", since = "1.16.0")]
     pub fn resize(&mut self, new_len: usize, value: T) {
-        self.resize_with(new_len, || value.clone());
+        if new_len > self.len() {
+            let extra = new_len - self.len();
+            self.extend(repeat_n(value, extra))
+        } else {
+            self.truncate(new_len);
+        }
     }
 }
 
 /// Returns the index in the underlying buffer for a given logical element index.
 #[inline]
-fn wrap_index(index: usize, size: usize) -> usize {
-    // size is always a power of 2
-    debug_assert!(size.is_power_of_two());
-    index & (size - 1)
-}
-
-/// Calculate the number of elements left to be read in the buffer
-#[inline]
-fn count(tail: usize, head: usize, size: usize) -> usize {
-    // size is always a power of 2
-    (head.wrapping_sub(tail)) & (size - 1)
+fn wrap_index(logical_index: usize, capacity: usize) -> usize {
+    debug_assert!(
+        (logical_index == 0 && capacity == 0)
+            || logical_index < capacity
+            || (logical_index - capacity) < capacity
+    );
+    if logical_index >= capacity { logical_index - capacity } else { logical_index }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: PartialEq, A: Allocator> PartialEq for VecDeque<T, A> {
     fn eq(&self, other: &Self) -> bool {
-        if self.len() != other.len() {
+        if self.len != other.len() {
             return false;
         }
         let (sa, sb) = self.as_slices();
@@ -2919,7 +2668,7 @@ impl<T: Ord, A: Allocator> Ord for VecDeque<T, A> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Hash, A: Allocator> Hash for VecDeque<T, A> {
     fn hash<H: Hasher>(&self, state: &mut H) {
-        state.write_length_prefix(self.len());
+        state.write_length_prefix(self.len);
         // It's not possible to use Hash::hash_slice on slices
         // returned by as_slices method as their length can vary
         // in otherwise identical deques.
@@ -2950,12 +2699,18 @@ 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> {
-        let iterator = iter.into_iter();
-        let (lower, _) = iterator.size_hint();
-        let mut deq = VecDeque::with_capacity(lower);
-        deq.extend(iterator);
-        deq
+        // 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()
+        }
     }
 }
 
@@ -3028,7 +2783,7 @@ impl<'a, T: 'a + Copy, A: Allocator> Extend<&'a T> for VecDeque<T, A> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T: fmt::Debug, A: Allocator> fmt::Debug for VecDeque<T, A> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.debug_list().entries(self).finish()
+        f.debug_list().entries(self.iter()).finish()
     }
 }
 
@@ -3039,31 +2794,13 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> {
     /// [`Vec<T>`]: crate::vec::Vec
     /// [`VecDeque<T>`]: crate::collections::VecDeque
     ///
-    /// This avoids reallocating where possible, but the conditions for that are
-    /// strict, and subject to change, and so shouldn't be relied upon unless the
-    /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated.
-    fn from(mut other: Vec<T, A>) -> Self {
-        let len = other.len();
-        if T::IS_ZST {
-            // There's no actual allocation for ZSTs to worry about capacity,
-            // but `VecDeque` can't handle as much length as `Vec`.
-            assert!(len < MAXIMUM_ZST_CAPACITY, "capacity overflow");
-        } else {
-            // We need to resize if the capacity is not a power of two, too small or
-            // doesn't have at least one free space. We do this while it's still in
-            // the `Vec` so the items will drop on panic.
-            let min_cap = cmp::max(MINIMUM_CAPACITY, len) + 1;
-            let cap = cmp::max(min_cap, other.capacity()).next_power_of_two();
-            if other.capacity() != cap {
-                other.reserve_exact(cap - len);
-            }
-        }
-
-        unsafe {
-            let (other_buf, len, capacity, alloc) = other.into_raw_parts_with_alloc();
-            let buf = RawVec::from_raw_parts_in(other_buf, capacity, alloc);
-            VecDeque { tail: 0, head: len, buf }
-        }
+    /// In its current implementation, this is a very cheap
+    /// conversion. This isn't yet a guarantee though, and
+    /// shouldn't be relied on.
+    #[inline]
+    fn from(other: Vec<T, A>) -> Self {
+        let (ptr, len, cap, alloc) = other.into_raw_parts_with_alloc();
+        Self { head: 0, len, buf: unsafe { RawVec::from_raw_parts_in(ptr, cap, alloc) } }
     }
 }
 
@@ -3105,11 +2842,11 @@ impl<T, A: Allocator> From<VecDeque<T, A>> for Vec<T, A> {
             let other = ManuallyDrop::new(other);
             let buf = other.buf.ptr();
             let len = other.len();
-            let cap = other.cap();
+            let cap = other.capacity();
             let alloc = ptr::read(other.allocator());
 
-            if other.tail != 0 {
-                ptr::copy(buf.add(other.tail), buf, len);
+            if other.head != 0 {
+                ptr::copy(buf.add(other.head), buf, len);
             }
             Vec::from_raw_parts_in(buf, len, cap, alloc)
         }
@@ -3136,8 +2873,8 @@ impl<T, const N: usize> From<[T; N]> for VecDeque<T> {
                 ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N);
             }
         }
-        deq.tail = 0;
-        deq.head = N;
+        deq.head = 0;
+        deq.len = N;
         deq
     }
 }
diff --git a/library/alloc/src/collections/vec_deque/pair_slices.rs b/library/alloc/src/collections/vec_deque/pair_slices.rs
deleted file mode 100644
index 6735424a3..000000000
--- a/library/alloc/src/collections/vec_deque/pair_slices.rs
+++ /dev/null
@@ -1,67 +0,0 @@
-use core::cmp::{self};
-use core::mem::replace;
-
-use crate::alloc::Allocator;
-
-use super::VecDeque;
-
-/// PairSlices pairs up equal length slice parts of two deques
-///
-/// For example, given deques "A" and "B" with the following division into slices:
-///
-/// A: [0 1 2] [3 4 5]
-/// B: [a b] [c d e]
-///
-/// It produces the following sequence of matching slices:
-///
-/// ([0 1], [a b])
-/// (\[2\], \[c\])
-/// ([3 4], [d e])
-///
-/// and the uneven remainder of either A or B is skipped.
-pub struct PairSlices<'a, 'b, T> {
-    a0: &'a mut [T],
-    a1: &'a mut [T],
-    b0: &'b [T],
-    b1: &'b [T],
-}
-
-impl<'a, 'b, T> PairSlices<'a, 'b, T> {
-    pub fn from<A: Allocator>(to: &'a mut VecDeque<T, A>, from: &'b VecDeque<T, A>) -> Self {
-        let (a0, a1) = to.as_mut_slices();
-        let (b0, b1) = from.as_slices();
-        PairSlices { a0, a1, b0, b1 }
-    }
-
-    pub fn has_remainder(&self) -> bool {
-        !self.b0.is_empty()
-    }
-
-    pub fn remainder(self) -> impl Iterator<Item = &'b [T]> {
-        IntoIterator::into_iter([self.b0, self.b1])
-    }
-}
-
-impl<'a, 'b, T> Iterator for PairSlices<'a, 'b, T> {
-    type Item = (&'a mut [T], &'b [T]);
-    fn next(&mut self) -> Option<Self::Item> {
-        // Get next part length
-        let part = cmp::min(self.a0.len(), self.b0.len());
-        if part == 0 {
-            return None;
-        }
-        let (p0, p1) = replace(&mut self.a0, &mut []).split_at_mut(part);
-        let (q0, q1) = self.b0.split_at(part);
-
-        // Move a1 into a0, if it's empty (and b1, b0 the same way).
-        self.a0 = p1;
-        self.b0 = q1;
-        if self.a0.is_empty() {
-            self.a0 = replace(&mut self.a1, &mut []);
-        }
-        if self.b0.is_empty() {
-            self.b0 = replace(&mut self.b1, &[]);
-        }
-        Some((p0, q0))
-    }
-}
diff --git a/library/alloc/src/collections/vec_deque/ring_slices.rs b/library/alloc/src/collections/vec_deque/ring_slices.rs
deleted file mode 100644
index dd0fa7d60..000000000
--- a/library/alloc/src/collections/vec_deque/ring_slices.rs
+++ /dev/null
@@ -1,56 +0,0 @@
-use core::ptr::{self};
-
-/// Returns the two slices that cover the `VecDeque`'s valid range
-pub trait RingSlices: Sized {
-    fn slice(self, from: usize, to: usize) -> Self;
-    fn split_at(self, i: usize) -> (Self, Self);
-
-    fn ring_slices(buf: Self, head: usize, tail: usize) -> (Self, Self) {
-        let contiguous = tail <= head;
-        if contiguous {
-            let (empty, buf) = buf.split_at(0);
-            (buf.slice(tail, head), empty)
-        } else {
-            let (mid, right) = buf.split_at(tail);
-            let (left, _) = mid.split_at(head);
-            (right, left)
-        }
-    }
-}
-
-impl<T> RingSlices for &[T] {
-    fn slice(self, from: usize, to: usize) -> Self {
-        &self[from..to]
-    }
-    fn split_at(self, i: usize) -> (Self, Self) {
-        (*self).split_at(i)
-    }
-}
-
-impl<T> RingSlices for &mut [T] {
-    fn slice(self, from: usize, to: usize) -> Self {
-        &mut self[from..to]
-    }
-    fn split_at(self, i: usize) -> (Self, Self) {
-        (*self).split_at_mut(i)
-    }
-}
-
-impl<T> RingSlices for *mut [T] {
-    fn slice(self, from: usize, to: usize) -> Self {
-        assert!(from <= to && to < self.len());
-        // Not using `get_unchecked_mut` to keep this a safe operation.
-        let len = to - from;
-        ptr::slice_from_raw_parts_mut(self.as_mut_ptr().wrapping_add(from), len)
-    }
-
-    fn split_at(self, mid: usize) -> (Self, Self) {
-        let len = self.len();
-        let ptr = self.as_mut_ptr();
-        assert!(mid <= len);
-        (
-            ptr::slice_from_raw_parts_mut(ptr, mid),
-            ptr::slice_from_raw_parts_mut(ptr.wrapping_add(mid), len - mid),
-        )
-    }
-}
diff --git a/library/alloc/src/collections/vec_deque/spec_extend.rs b/library/alloc/src/collections/vec_deque/spec_extend.rs
index 97ff8b765..dccf40ccb 100644
--- a/library/alloc/src/collections/vec_deque/spec_extend.rs
+++ b/library/alloc/src/collections/vec_deque/spec_extend.rs
@@ -1,6 +1,6 @@
 use crate::alloc::Allocator;
 use crate::vec;
-use core::iter::{ByRefSized, TrustedLen};
+use core::iter::TrustedLen;
 use core::slice;
 
 use super::VecDeque;
@@ -17,19 +17,33 @@ where
     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));
-            }
+        // for item in iter {
+        //     self.push_back(item);
+        // }
+
+        // May only be called if `deque.len() < deque.capacity()`
+        unsafe fn push_unchecked<T, A: Allocator>(deque: &mut VecDeque<T, A>, element: T) {
+            // SAFETY: Because of the precondition, it's guaranteed that there is space
+            // in the logical array after the last element.
+            unsafe { deque.buffer_write(deque.to_physical_idx(deque.len), element) };
+            // This can't overflow because `deque.len() < deque.capacity() <= usize::MAX`.
+            deque.len += 1;
+        }
 
-            let head = self.head;
-            self.head = self.wrap_add(self.head, 1);
-            unsafe {
-                self.buffer_write(head, element);
+        while let Some(element) = iter.next() {
+            let (lower, _) = iter.size_hint();
+            self.reserve(lower.saturating_add(1));
+
+            // SAFETY: We just reserved space for at least one element.
+            unsafe { push_unchecked(self, element) };
+
+            // Inner loop to avoid repeatedly calling `reserve`.
+            while self.len < self.capacity() {
+                let Some(element) = iter.next() else {
+                    return;
+                };
+                // SAFETY: The loop condition guarantees that `self.len() < self.capacity()`.
+                unsafe { push_unchecked(self, element) };
             }
         }
     }
@@ -39,7 +53,7 @@ impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
 where
     I: TrustedLen<Item = T>,
 {
-    default fn spec_extend(&mut self, mut iter: I) {
+    default fn spec_extend(&mut self, iter: I) {
         // This is the case for a TrustedLen iterator.
         let (low, high) = iter.size_hint();
         if let Some(additional) = high {
@@ -51,35 +65,12 @@ where
             );
             self.reserve(additional);
 
-            struct WrapAddOnDrop<'a, T, A: Allocator> {
-                vec_deque: &'a mut VecDeque<T, A>,
-                written: usize,
-            }
-
-            impl<'a, T, A: Allocator> Drop for WrapAddOnDrop<'a, T, A> {
-                fn drop(&mut self) {
-                    self.vec_deque.head =
-                        self.vec_deque.wrap_add(self.vec_deque.head, self.written);
-                }
-            }
-
-            let mut wrapper = WrapAddOnDrop { vec_deque: self, written: 0 };
-
-            let head_room = wrapper.vec_deque.cap() - wrapper.vec_deque.head;
-            unsafe {
-                wrapper.vec_deque.write_iter(
-                    wrapper.vec_deque.head,
-                    ByRefSized(&mut iter).take(head_room),
-                    &mut wrapper.written,
-                );
-
-                if additional > head_room {
-                    wrapper.vec_deque.write_iter(0, iter, &mut wrapper.written);
-                }
-            }
+            let written = unsafe {
+                self.write_iter_wrapping(self.to_physical_idx(self.len), iter, additional)
+            };
 
             debug_assert_eq!(
-                additional, wrapper.written,
+                additional, written,
                 "The number of items written to VecDeque doesn't match the TrustedLen size hint"
             );
         } else {
@@ -99,8 +90,8 @@ impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> {
         self.reserve(slice.len());
 
         unsafe {
-            self.copy_slice(self.head, slice);
-            self.head = self.wrap_add(self.head, slice.len());
+            self.copy_slice(self.to_physical_idx(self.len), slice);
+            self.len += slice.len();
         }
         iterator.forget_remaining_elements();
     }
@@ -125,8 +116,8 @@ where
         self.reserve(slice.len());
 
         unsafe {
-            self.copy_slice(self.head, slice);
-            self.head = self.wrap_add(self.head, slice.len());
+            self.copy_slice(self.to_physical_idx(self.len), slice);
+            self.len += slice.len();
         }
     }
 }
diff --git a/library/alloc/src/collections/vec_deque/tests.rs b/library/alloc/src/collections/vec_deque/tests.rs
index 1f2daef21..220ad71be 100644
--- a/library/alloc/src/collections/vec_deque/tests.rs
+++ b/library/alloc/src/collections/vec_deque/tests.rs
@@ -3,7 +3,6 @@ use core::iter::TrustedLen;
 use super::*;
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_push_back_100(b: &mut test::Bencher) {
     let mut deq = VecDeque::with_capacity(101);
     b.iter(|| {
@@ -11,12 +10,11 @@ fn bench_push_back_100(b: &mut test::Bencher) {
             deq.push_back(i);
         }
         deq.head = 0;
-        deq.tail = 0;
+        deq.len = 0;
     })
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_push_front_100(b: &mut test::Bencher) {
     let mut deq = VecDeque::with_capacity(101);
     b.iter(|| {
@@ -24,18 +22,21 @@ fn bench_push_front_100(b: &mut test::Bencher) {
             deq.push_front(i);
         }
         deq.head = 0;
-        deq.tail = 0;
+        deq.len = 0;
     })
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_pop_back_100(b: &mut test::Bencher) {
-    let mut deq = VecDeque::<i32>::with_capacity(101);
+    let size = 100;
+    let mut deq = VecDeque::<i32>::with_capacity(size + 1);
+    // We'll mess with private state to pretend like `deq` is filled.
+    // Make sure the buffer is initialized so that we don't read uninit memory.
+    unsafe { deq.ptr().write_bytes(0u8, size + 1) };
 
     b.iter(|| {
-        deq.head = 100;
-        deq.tail = 0;
+        deq.head = 0;
+        deq.len = 100;
         while !deq.is_empty() {
             test::black_box(deq.pop_back());
         }
@@ -43,9 +44,9 @@ fn bench_pop_back_100(b: &mut test::Bencher) {
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_retain_whole_10000(b: &mut test::Bencher) {
-    let v = (1..100000).collect::<VecDeque<u32>>();
+    let size = if cfg!(miri) { 1000 } else { 100000 };
+    let v = (1..size).collect::<VecDeque<u32>>();
 
     b.iter(|| {
         let mut v = v.clone();
@@ -54,9 +55,9 @@ fn bench_retain_whole_10000(b: &mut test::Bencher) {
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_retain_odd_10000(b: &mut test::Bencher) {
-    let v = (1..100000).collect::<VecDeque<u32>>();
+    let size = if cfg!(miri) { 1000 } else { 100000 };
+    let v = (1..size).collect::<VecDeque<u32>>();
 
     b.iter(|| {
         let mut v = v.clone();
@@ -65,24 +66,27 @@ fn bench_retain_odd_10000(b: &mut test::Bencher) {
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_retain_half_10000(b: &mut test::Bencher) {
-    let v = (1..100000).collect::<VecDeque<u32>>();
+    let size = if cfg!(miri) { 1000 } else { 100000 };
+    let v = (1..size).collect::<VecDeque<u32>>();
 
     b.iter(|| {
         let mut v = v.clone();
-        v.retain(|x| *x > 50000)
+        v.retain(|x| *x > size / 2)
     })
 }
 
 #[bench]
-#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
 fn bench_pop_front_100(b: &mut test::Bencher) {
-    let mut deq = VecDeque::<i32>::with_capacity(101);
+    let size = 100;
+    let mut deq = VecDeque::<i32>::with_capacity(size + 1);
+    // We'll mess with private state to pretend like `deq` is filled.
+    // Make sure the buffer is initialized so that we don't read uninit memory.
+    unsafe { deq.ptr().write_bytes(0u8, size + 1) };
 
     b.iter(|| {
-        deq.head = 100;
-        deq.tail = 0;
+        deq.head = 0;
+        deq.len = 100;
         while !deq.is_empty() {
             test::black_box(deq.pop_front());
         }
@@ -101,9 +105,9 @@ fn test_swap_front_back_remove() {
         for len in 0..final_len {
             let expected: VecDeque<_> =
                 if back { (0..len).collect() } else { (0..len).rev().collect() };
-            for tail_pos in 0..usable_cap {
-                tester.tail = tail_pos;
-                tester.head = tail_pos;
+            for head_pos in 0..usable_cap {
+                tester.head = head_pos;
+                tester.len = 0;
                 if back {
                     for i in 0..len * 2 {
                         tester.push_front(i);
@@ -120,8 +124,8 @@ fn test_swap_front_back_remove() {
                         assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
                     }
                 }
-                assert!(tester.tail < tester.cap());
-                assert!(tester.head < tester.cap());
+                assert!(tester.head <= tester.capacity());
+                assert!(tester.len <= tester.capacity());
                 assert_eq!(tester, expected);
             }
         }
@@ -146,18 +150,18 @@ fn test_insert() {
     for len in minlen..cap {
         // 0, 1, 2, .., len - 1
         let expected = (0..).take(len).collect::<VecDeque<_>>();
-        for tail_pos in 0..cap {
+        for head_pos in 0..cap {
             for to_insert in 0..len {
-                tester.tail = tail_pos;
-                tester.head = tail_pos;
+                tester.head = head_pos;
+                tester.len = 0;
                 for i in 0..len {
                     if i != to_insert {
                         tester.push_back(i);
                     }
                 }
                 tester.insert(to_insert, to_insert);
-                assert!(tester.tail < tester.cap());
-                assert!(tester.head < tester.cap());
+                assert!(tester.head <= tester.capacity());
+                assert!(tester.len <= tester.capacity());
                 assert_eq!(tester, expected);
             }
         }
@@ -253,13 +257,14 @@ fn test_swap_panic() {
 #[test]
 fn test_reserve_exact() {
     let mut tester: VecDeque<i32> = VecDeque::with_capacity(1);
-    assert!(tester.capacity() == 1);
+    assert_eq!(tester.capacity(), 1);
     tester.reserve_exact(50);
-    assert!(tester.capacity() >= 51);
+    assert_eq!(tester.capacity(), 50);
     tester.reserve_exact(40);
-    assert!(tester.capacity() >= 51);
+    // reserving won't shrink the buffer
+    assert_eq!(tester.capacity(), 50);
     tester.reserve_exact(200);
-    assert!(tester.capacity() >= 200);
+    assert_eq!(tester.capacity(), 200);
 }
 
 #[test]
@@ -319,6 +324,7 @@ fn test_contains() {
 #[test]
 fn test_rotate_left_right() {
     let mut tester: VecDeque<_> = (1..=10).collect();
+    tester.reserve(1);
 
     assert_eq!(tester.len(), 10);
 
@@ -459,7 +465,7 @@ fn test_binary_search_key() {
 }
 
 #[test]
-fn make_contiguous_big_tail() {
+fn make_contiguous_big_head() {
     let mut tester = VecDeque::with_capacity(15);
 
     for i in 0..3 {
@@ -474,14 +480,14 @@ fn make_contiguous_big_tail() {
     assert_eq!(tester.capacity(), 15);
     assert_eq!((&[9, 8, 7, 6, 5, 4, 3] as &[_], &[0, 1, 2] as &[_]), tester.as_slices());
 
-    let expected_start = tester.head;
+    let expected_start = tester.as_slices().1.len();
     tester.make_contiguous();
-    assert_eq!(tester.tail, expected_start);
+    assert_eq!(tester.head, expected_start);
     assert_eq!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_], &[] as &[_]), tester.as_slices());
 }
 
 #[test]
-fn make_contiguous_big_head() {
+fn make_contiguous_big_tail() {
     let mut tester = VecDeque::with_capacity(15);
 
     for i in 0..8 {
@@ -495,44 +501,46 @@ fn make_contiguous_big_head() {
     // 01234567......98
     let expected_start = 0;
     tester.make_contiguous();
-    assert_eq!(tester.tail, expected_start);
+    assert_eq!(tester.head, expected_start);
     assert_eq!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_], &[] as &[_]), tester.as_slices());
 }
 
 #[test]
 fn make_contiguous_small_free() {
-    let mut tester = VecDeque::with_capacity(15);
+    let mut tester = VecDeque::with_capacity(16);
 
-    for i in 'A' as u8..'I' as u8 {
+    for i in b'A'..b'I' {
         tester.push_back(i as char);
     }
 
-    for i in 'I' as u8..'N' as u8 {
+    for i in b'I'..b'N' {
         tester.push_front(i as char);
     }
 
+    assert_eq!(tester, ['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']);
+
     // ABCDEFGH...MLKJI
     let expected_start = 0;
     tester.make_contiguous();
-    assert_eq!(tester.tail, expected_start);
+    assert_eq!(tester.head, expected_start);
     assert_eq!(
         (&['M', 'L', 'K', 'J', 'I', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'] as &[_], &[] as &[_]),
         tester.as_slices()
     );
 
     tester.clear();
-    for i in 'I' as u8..'N' as u8 {
+    for i in b'I'..b'N' {
         tester.push_back(i as char);
     }
 
-    for i in 'A' as u8..'I' as u8 {
+    for i in b'A'..b'I' {
         tester.push_front(i as char);
     }
 
     // IJKLM...HGFEDCBA
-    let expected_start = 0;
+    let expected_start = 3;
     tester.make_contiguous();
-    assert_eq!(tester.tail, expected_start);
+    assert_eq!(tester.head, expected_start);
     assert_eq!(
         (&['H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'I', 'J', 'K', 'L', 'M'] as &[_], &[] as &[_]),
         tester.as_slices()
@@ -541,16 +549,55 @@ fn make_contiguous_small_free() {
 
 #[test]
 fn make_contiguous_head_to_end() {
-    let mut dq = VecDeque::with_capacity(3);
-    dq.push_front('B');
-    dq.push_front('A');
-    dq.push_back('C');
-    dq.make_contiguous();
-    let expected_tail = 0;
-    let expected_head = 3;
-    assert_eq!(expected_tail, dq.tail);
-    assert_eq!(expected_head, dq.head);
-    assert_eq!((&['A', 'B', 'C'] as &[_], &[] as &[_]), dq.as_slices());
+    let mut tester = VecDeque::with_capacity(16);
+
+    for i in b'A'..b'L' {
+        tester.push_back(i as char);
+    }
+
+    for i in b'L'..b'Q' {
+        tester.push_front(i as char);
+    }
+
+    assert_eq!(
+        tester,
+        ['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
+    );
+
+    // ABCDEFGHIJKPONML
+    let expected_start = 0;
+    tester.make_contiguous();
+    assert_eq!(tester.head, expected_start);
+    assert_eq!(
+        (
+            &['P', 'O', 'N', 'M', 'L', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']
+                as &[_],
+            &[] as &[_]
+        ),
+        tester.as_slices()
+    );
+
+    tester.clear();
+    for i in b'L'..b'Q' {
+        tester.push_back(i as char);
+    }
+
+    for i in b'A'..b'L' {
+        tester.push_front(i as char);
+    }
+
+    // LMNOPKJIHGFEDCBA
+    let expected_start = 0;
+    tester.make_contiguous();
+    assert_eq!(tester.head, expected_start);
+    assert_eq!(
+        (
+            &['K', 'J', 'I', 'H', 'G', 'F', 'E', 'D', 'C', 'B', 'A', 'L', 'M', 'N', 'O', 'P']
+                as &[_],
+            &[] as &[_]
+        ),
+        tester.as_slices()
+    );
 }
 
 #[test]
@@ -584,10 +631,10 @@ fn test_remove() {
     for len in minlen..cap - 1 {
         // 0, 1, 2, .., len - 1
         let expected = (0..).take(len).collect::<VecDeque<_>>();
-        for tail_pos in 0..cap {
+        for head_pos in 0..cap {
             for to_remove in 0..=len {
-                tester.tail = tail_pos;
-                tester.head = tail_pos;
+                tester.head = head_pos;
+                tester.len = 0;
                 for i in 0..len {
                     if i == to_remove {
                         tester.push_back(1234);
@@ -598,8 +645,8 @@ fn test_remove() {
                     tester.push_back(1234);
                 }
                 tester.remove(to_remove);
-                assert!(tester.tail < tester.cap());
-                assert!(tester.head < tester.cap());
+                assert!(tester.head <= tester.capacity());
+                assert!(tester.len <= tester.capacity());
                 assert_eq!(tester, expected);
             }
         }
@@ -613,11 +660,11 @@ fn test_range() {
     let cap = tester.capacity();
     let minlen = if cfg!(miri) { cap - 1 } else { 0 }; // Miri is too slow
     for len in minlen..=cap {
-        for tail in 0..=cap {
+        for head in 0..=cap {
             for start in 0..=len {
                 for end in start..=len {
-                    tester.tail = tail;
-                    tester.head = tail;
+                    tester.head = head;
+                    tester.len = 0;
                     for i in 0..len {
                         tester.push_back(i);
                     }
@@ -638,17 +685,17 @@ fn test_range_mut() {
 
     let cap = tester.capacity();
     for len in 0..=cap {
-        for tail in 0..=cap {
+        for head in 0..=cap {
             for start in 0..=len {
                 for end in start..=len {
-                    tester.tail = tail;
-                    tester.head = tail;
+                    tester.head = head;
+                    tester.len = 0;
                     for i in 0..len {
                         tester.push_back(i);
                     }
 
                     let head_was = tester.head;
-                    let tail_was = tester.tail;
+                    let len_was = tester.len;
 
                     // Check that we iterate over the correct values
                     let range: VecDeque<_> = tester.range_mut(start..end).map(|v| *v).collect();
@@ -658,8 +705,8 @@ fn test_range_mut() {
                     // We shouldn't have changed the capacity or made the
                     // head or tail out of bounds
                     assert_eq!(tester.capacity(), cap);
-                    assert_eq!(tester.tail, tail_was);
                     assert_eq!(tester.head, head_was);
+                    assert_eq!(tester.len, len_was);
                 }
             }
         }
@@ -672,11 +719,11 @@ fn test_drain() {
 
     let cap = tester.capacity();
     for len in 0..=cap {
-        for tail in 0..=cap {
+        for head in 0..cap {
             for drain_start in 0..=len {
                 for drain_end in drain_start..=len {
-                    tester.tail = tail;
-                    tester.head = tail;
+                    tester.head = head;
+                    tester.len = 0;
                     for i in 0..len {
                         tester.push_back(i);
                     }
@@ -689,8 +736,8 @@ fn test_drain() {
                     // We shouldn't have changed the capacity or made the
                     // head or tail out of bounds
                     assert_eq!(tester.capacity(), cap);
-                    assert!(tester.tail < tester.cap());
-                    assert!(tester.head < tester.cap());
+                    assert!(tester.head <= tester.capacity());
+                    assert!(tester.len <= tester.capacity());
 
                     // We should see the correct values in the VecDeque
                     let expected: VecDeque<_> = (0..drain_start).chain(drain_end..len).collect();
@@ -717,17 +764,18 @@ fn test_shrink_to_fit() {
     for len in 0..=cap {
         // 0, 1, 2, .., len - 1
         let expected = (0..).take(len).collect::<VecDeque<_>>();
-        for tail_pos in 0..=max_cap {
-            tester.tail = tail_pos;
-            tester.head = tail_pos;
+        for head_pos in 0..=max_cap {
+            tester.reserve(head_pos);
+            tester.head = head_pos;
+            tester.len = 0;
             tester.reserve(63);
             for i in 0..len {
                 tester.push_back(i);
             }
             tester.shrink_to_fit();
             assert!(tester.capacity() <= cap);
-            assert!(tester.tail < tester.cap());
-            assert!(tester.head < tester.cap());
+            assert!(tester.head <= tester.capacity());
+            assert!(tester.len <= tester.capacity());
             assert_eq!(tester, expected);
         }
     }
@@ -754,17 +802,17 @@ fn test_split_off() {
             // at, at + 1, .., len - 1 (may be empty)
             let expected_other = (at..).take(len - at).collect::<VecDeque<_>>();
 
-            for tail_pos in 0..cap {
-                tester.tail = tail_pos;
-                tester.head = tail_pos;
+            for head_pos in 0..cap {
+                tester.head = head_pos;
+                tester.len = 0;
                 for i in 0..len {
                     tester.push_back(i);
                 }
                 let result = tester.split_off(at);
-                assert!(tester.tail < tester.cap());
-                assert!(tester.head < tester.cap());
-                assert!(result.tail < result.cap());
-                assert!(result.head < result.cap());
+                assert!(tester.head <= tester.capacity());
+                assert!(tester.len <= tester.capacity());
+                assert!(result.head <= result.capacity());
+                assert!(result.len <= result.capacity());
                 assert_eq!(tester, expected_self);
                 assert_eq!(result, expected_other);
             }
@@ -781,16 +829,10 @@ fn test_from_vec() {
             vec.extend(0..len);
 
             let vd = VecDeque::from(vec.clone());
-            assert!(vd.cap().is_power_of_two());
             assert_eq!(vd.len(), vec.len());
             assert!(vd.into_iter().eq(vec));
         }
     }
-
-    let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY - 1]);
-    let vd = VecDeque::from(vec.clone());
-    assert!(vd.cap().is_power_of_two());
-    assert_eq!(vd.len(), vec.len());
 }
 
 #[test]
@@ -842,10 +884,6 @@ fn test_extend_impl(trusted_len: bool) {
             }
 
             assert_eq!(self.test, self.expected);
-            let (a1, b1) = self.test.as_slices();
-            let (a2, b2) = self.expected.as_slices();
-            assert_eq!(a1, a2);
-            assert_eq!(b1, b2);
         }
 
         fn drain<R: RangeBounds<usize> + Clone>(&mut self, range: R) {
@@ -868,7 +906,7 @@ fn test_extend_impl(trusted_len: bool) {
     let mut tester = VecDequeTester::new(trusted_len);
 
     // Initial capacity
-    tester.test_extend(0..tester.remaining_capacity() - 1);
+    tester.test_extend(0..tester.remaining_capacity());
 
     // Grow
     tester.test_extend(1024..2048);
@@ -876,7 +914,7 @@ fn test_extend_impl(trusted_len: bool) {
     // Wrap around
     tester.drain(..128);
 
-    tester.test_extend(0..tester.remaining_capacity() - 1);
+    tester.test_extend(0..tester.remaining_capacity());
 
     // Continue
     tester.drain(256..);
@@ -889,16 +927,6 @@ fn test_extend_impl(trusted_len: bool) {
 }
 
 #[test]
-#[should_panic = "capacity overflow"]
-fn test_from_vec_zst_overflow() {
-    use crate::vec::Vec;
-    let vec = Vec::from([(); MAXIMUM_ZST_CAPACITY]);
-    let vd = VecDeque::from(vec.clone()); // no room for +1
-    assert!(vd.cap().is_power_of_two());
-    assert_eq!(vd.len(), vec.len());
-}
-
-#[test]
 fn test_from_array() {
     fn test<const N: usize>() {
         let mut array: [usize; N] = [0; N];
@@ -913,7 +941,6 @@ fn test_from_array() {
             assert_eq!(deq[i], i);
         }
 
-        assert!(deq.cap().is_power_of_two());
         assert_eq!(deq.len(), N);
     }
     test::<0>();
@@ -921,11 +948,6 @@ fn test_from_array() {
     test::<2>();
     test::<32>();
     test::<35>();
-
-    let array = [(); MAXIMUM_ZST_CAPACITY - 1];
-    let deq = VecDeque::from(array);
-    assert!(deq.cap().is_power_of_two());
-    assert_eq!(deq.len(), MAXIMUM_ZST_CAPACITY - 1);
 }
 
 #[test]