Update VecDeque implementation

12 files changed, 774 insertions, 1251 deletions

diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs
index 41baa7102cd..a4a96bad5e0 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,61 @@ 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
+    fn as_slices(&self) -> (*mut [T], *mut [T]) {
+        unsafe {
+            let deque = self.deque.as_ref();
+            let wrapped_start = deque.wrap_idx(self.idx);
+
+            if self.remaining <= deque.capacity() - wrapped_start {
+                // there's only one contigous slice
+                (
+                    ptr::slice_from_raw_parts_mut(deque.ptr().add(wrapped_start), self.remaining),
+                    &mut [] as *mut [T],
+                )
+            } else {
+                let head_len = deque.capacity() - wrapped_start;
+                // this will never overflow due to the if condition
+                let tail_len = self.remaining - head_len;
+                (
+                    ptr::slice_from_raw_parts_mut(deque.ptr().add(wrapped_start), head_len),
+                    ptr::slice_from_raw_parts_mut(deque.ptr(), tail_len),
+                )
+            }
+        }
     }
 }
 
@@ -47,11 +82,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 +102,77 @@ 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 {
+                    let (front, back) = self.0.as_slices();
+                    unsafe {
+                        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 tail_len = count(orig_tail, drain_tail, source_deque.cap());
-                let head_len = count(drain_head, orig_head, source_deque.cap());
+                let orig_len = self.0.tail_len + drain_end;
+
+                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.wrap_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.wrap_idx(drain_len),
+                                head_len,
+                            );
+                            source_deque.head = source_deque.wrap_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.wrap_idx(head_len + drain_len),
+                                source_deque.wrap_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);
+        let (front, back) = guard.0.as_slices();
+        unsafe {
+            // 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 +182,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().wrap_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 +202,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().wrap_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 e696d7ed636..d4e66db4903 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() }
     }
 }
 
@@ -52,37 +39,43 @@ impl<T> Clone for Iter<'_, T> {
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
 
+    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 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()) }
     }
 
     #[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, f)
     }
 
     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
@@ -91,35 +84,8 @@ impl<'a, T> Iterator for Iter<'a, T> {
         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, f)
     }
 
     #[inline]
@@ -132,8 +98,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,28 +112,36 @@ 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 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());
-        // 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, f)
     }
 
     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
@@ -172,33 +150,19 @@ impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
         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, 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 b78c0d5e1b3..7c955663bde 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,51 @@ 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, 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
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> R,
+        R: Try<Output = B>,
+    {
+        let acc = self.i1.try_fold(init, &mut f)?;
+        self.i2.try_fold(acc, f)
     }
 
     #[inline]
@@ -104,8 +90,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 +104,57 @@ 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, 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 acc = self.i2.try_rfold(init, &mut f)?;
+        self.i1.try_rfold(acc, 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 537fe22a4be..bb0e11d6c2d 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_n, 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,8 @@ 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,
     head: usize,
+    len: usize,
     buf: RawVec<T, A>,
 }
 
@@ -124,18 +105,16 @@ 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);
-        }
+        self.clear();
+        self.head = 0;
+        self.reserve(other.len);
 
-        if iter.has_remainder() {
-            for remainder in iter.remainder() {
-                self.extend(remainder.iter().cloned());
-            }
+        let (a, b) = other.as_slices();
+        unsafe {
+            self.write_iter(0, a.iter().cloned(), &mut 0);
+            self.write_iter(a.len(), b.iter().cloned(), &mut 0);
         }
+        self.len = other.len;
     }
 }
 
@@ -154,11 +133,13 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for VecDeque<T, A> {
             }
         }
 
-        let (front, back) = self.as_mut_slices();
-        unsafe {
-            let _back_dropper = Dropper(back);
-            // use drop for [T]
-            ptr::drop_in_place(front);
+        if mem::needs_drop::<T>() {
+            let (front, back) = self.as_mut_slices();
+            unsafe {
+                let _back_dropper = Dropper(back);
+                // use drop for [T]
+                ptr::drop_in_place(front);
+            }
         }
         // RawVec handles deallocation
     }
@@ -180,41 +161,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 {
@@ -232,48 +178,46 @@ impl<T, A: Allocator> VecDeque<T, A> {
     /// Returns `true` if the buffer is at full capacity.
     #[inline]
     fn is_full(&self) -> bool {
-        self.cap() - self.len() == 1
+        self.len == self.capacity()
     }
 
     /// Returns the index in the underlying buffer for a given logical element
-    /// index.
+    /// index + addend.
     #[inline]
-    fn wrap_index(&self, idx: usize) -> usize {
-        wrap_index(idx, self.cap())
+    fn wrap_add(&self, idx: usize, addend: usize) -> usize {
+        wrap_index(idx.wrapping_add(addend), 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())
+    fn wrap_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 +226,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 +249,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 +284,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 +297,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 +311,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 +325,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 +339,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 +356,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 +374,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 +386,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 +420,96 @@ 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           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 +523,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]
@@ -567,10 +558,11 @@ impl<T, A: Allocator> VecDeque<T, A> {
     ///
     /// let deque: VecDeque<u32> = VecDeque::new();
     /// ```
+    // FIXME: This should probably be const
     #[inline]
     #[unstable(feature = "allocator_api", issue = "32838")]
     pub fn new_in(alloc: A) -> VecDeque<T, A> {
-        VecDeque::with_capacity_in(INITIAL_CAPACITY, alloc)
+        VecDeque { head: 0, len: 0, buf: RawVec::new_in(alloc) }
     }
 
     /// Creates an empty deque with space for at least `capacity` elements.
@@ -584,11 +576,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 +596,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.wrap_idx(index);
             unsafe { Some(&*self.ptr().add(idx)) }
         } else {
             None
@@ -637,8 +625,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.wrap_idx(index);
             unsafe { Some(&mut *self.ptr().add(idx)) }
         } else {
             None
@@ -672,8 +660,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.wrap_idx(i);
+        let rj = self.wrap_idx(j);
         unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
     }
 
@@ -691,7 +679,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 +706,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 +735,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 +787,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 +835,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 +891,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 +907,49 @@ 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           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           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 {
+                //            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 +994,25 @@ 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;
+
+            if !mem::needs_drop::<T>() {
+                self.len = len;
+                return;
+            }
+
             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 +1046,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 +1069,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,13 +1102,17 @@ 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))
+        if self.is_contiguous() {
+            (unsafe { slice::from_raw_parts(self.ptr().add(self.head), self.len) }, &[])
+        } else {
+            let head_len = self.capacity() - self.head;
+            let tail_len = self.len - head_len;
+            unsafe {
+                (
+                    slice::from_raw_parts(self.ptr().add(self.head), head_len),
+                    slice::from_raw_parts(self.ptr(), tail_len),
+                )
+            }
         }
     }
 
@@ -1135,15 +1144,17 @@ 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))
+        if self.is_contiguous() {
+            (unsafe { slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }, &mut [])
+        } else {
+            let head_len = self.capacity() - self.head;
+            let tail_len = self.len - head_len;
+            unsafe {
+                (
+                    slice::from_raw_parts_mut(self.ptr().add(self.head), head_len),
+                    slice::from_raw_parts_mut(self.ptr(), tail_len),
+                )
+            }
         }
     }
 
@@ -1161,7 +1172,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 +1189,22 @@ 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)
+    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 a_len = self.len.min(self.capacity() - self.head);
+        if end <= a_len {
+            (start..end, 0..0)
+        } else if start >= a_len {
+            (0..0, start - a_len..end - a_len)
+        } else {
+            (start..a_len, 0..end - a_len)
+        }
     }
 
     /// Creates an iterator that covers the specified range in the deque.
@@ -1217,9 +1233,9 @@ 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, b) = self.as_slices();
+        let (a_range, b_range) = self.slice_ranges(range);
+        Iter::new(a[a_range].iter(), b[b_range].iter())
     }
 
     /// Creates an iterator that covers the specified mutable range in the deque.
@@ -1252,13 +1268,9 @@ 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);
+        let (a, b) = self.as_mut_slices();
+        IterMut::new(a[a_range].iter_mut(), b[b_range].iter_mut())
     }
 
     /// Removes the specified range from the deque in bulk, returning all
@@ -1310,39 +1322,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 +1364,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 +1460,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 +1484,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 +1508,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.wrap_idx(1);
+            self.len -= 1;
+            Some(unsafe { self.buffer_read(old_head) })
         }
     }
 
@@ -1528,9 +1534,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.wrap_idx(self.len)) })
         }
     }
 
@@ -1552,10 +1557,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 +1583,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.wrap_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 +1619,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 +1654,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 +1693,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.wrap_idx(index), self.wrap_idx(index + 1), k);
+                self.buffer_write(self.wrap_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.wrap_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 +1738,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 distance_to_tail = index;
-        let distance_to_head = self.len() - index;
+        let wrapped_idx = self.wrap_idx(index);
 
-        let contiguous = self.is_contiguous();
+        let elem = unsafe { Some(self.buffer_read(wrapped_idx)) };
 
-        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.wrap_idx(1);
+            unsafe { self.wrap_copy(old_head, self.head, index) };
+            self.len -= 1;
         }
 
         elem
@@ -2091,7 +1793,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 +1830,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 +1856,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.wrap_idx(self.len), left);
+            // no overflow, because self.capacity() >= old_cap + left.len() >= self.len + left.len()
+            self.copy_slice(self.wrap_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());
+        self.len += other.len;
         // Silently drop values in `other`.
-        other.tail = other.head;
+        other.len = 0;
+        other.head = 0;
     }
 
     /// Retains only the elements specified by the predicate.
@@ -2232,7 +1943,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 +1981,9 @@ 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();
+        // if the cap was 0, we need to reserve at least 1.
+        self.buf.reserve(old_cap, old_cap.max(1));
         unsafe {
             self.handle_capacity_increase(old_cap);
         }
@@ -2306,7 +2017,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,64 +2083,53 @@ 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.
@@ -2437,7 +2137,7 @@ impl<T, A: Allocator> VecDeque<T, A> {
             // from: EFGHI...ABCD or HIJK.ABCDEFG
             // to:   ABCDEFGHI... or ABCDEFGHIJK.
             let mut left_edge: usize = 0;
-            let mut right_edge: usize = self.tail;
+            let mut right_edge: usize = head;
             unsafe {
                 // The general problem looks like this
                 // GHIJKLM...ABCDEF - before any swaps
@@ -2454,28 +2154,18 @@ impl<T, A: Allocator> VecDeque<T, A> {
                     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));
+                        ptr::swap(ptr.add(i), ptr.add(src));
                     }
                     let n_ops = right_edge - left_edge;
                     left_edge += n_ops;
                     right_edge += right_offset + 1;
                 }
 
-                self.tail = 0;
-                self.head = len;
+                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 +2203,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 +2246,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 +2257,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.wrap_idx(self.len), mid);
         }
-        self.head = self.wrap_add(self.head, mid);
-        self.tail = self.wrap_add(self.tail, mid);
+        self.head = self.wrap_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.wrap_idx(self.len), self.head, k);
         }
     }
 
@@ -2845,22 +2533,13 @@ impl<T: Clone, A: Allocator> VecDeque<T, A> {
 /// 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)
+    if index >= size { index - size } else { 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();
@@ -2924,7 +2603,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.
@@ -3033,7 +2712,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()
     }
 }
 
@@ -3044,31 +2723,12 @@ 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.
+    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) } }
     }
 }
 
@@ -3110,11 +2770,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)
         }
@@ -3141,8 +2801,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 6735424a3ef..00000000000
--- 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 dd0fa7d6074..00000000000
--- 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 97ff8b76524..0f722ceb082 100644
--- a/library/alloc/src/collections/vec_deque/spec_extend.rs
+++ b/library/alloc/src/collections/vec_deque/spec_extend.rs
@@ -17,19 +17,31 @@ 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);
+        // }
+        loop {
+            let lower_bound = iter.size_hint().0;
+            if lower_bound != 0 {
+                self.reserve(lower_bound);
             }
 
-            let head = self.head;
-            self.head = self.wrap_add(self.head, 1);
+            match iter.next() {
+                Some(val) => self.push_back(val),
+                None => break,
+            }
+
+            let room = self.capacity() - self.len;
             unsafe {
-                self.buffer_write(head, element);
+                // Safety:
+                // The iter is at most `room` items long,
+                // and `room == self.capacity() - self.len`
+                //   => `self.len + room <= self.capacity()`
+                self.write_iter_wrapping(
+                    self.wrap_idx(self.len),
+                    ByRefSized(&mut iter).take(room),
+                    room,
+                );
             }
         }
     }
@@ -39,7 +51,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 +63,11 @@ 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.wrap_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 +87,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.wrap_idx(self.len), slice);
+            self.len += slice.len();
         }
         iterator.forget_remaining_elements();
     }
@@ -125,8 +113,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.wrap_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 6e0f83020f9..6995c5b47db 100644
--- a/library/alloc/src/collections/vec_deque/tests.rs
+++ b/library/alloc/src/collections/vec_deque/tests.rs
@@ -10,7 +10,7 @@ fn bench_push_back_100(b: &mut test::Bencher) {
             deq.push_back(i);
         }
         deq.head = 0;
-        deq.tail = 0;
+        deq.len = 0;
     })
 }
 
@@ -22,7 +22,7 @@ fn bench_push_front_100(b: &mut test::Bencher) {
             deq.push_front(i);
         }
         deq.head = 0;
-        deq.tail = 0;
+        deq.len = 0;
     })
 }
 
@@ -35,8 +35,8 @@ fn bench_pop_back_100(b: &mut test::Bencher) {
     unsafe { deq.ptr().write_bytes(0u8, size + 1) };
 
     b.iter(|| {
-        deq.head = size;
-        deq.tail = 0;
+        deq.head = 0;
+        deq.len = 100;
         while !deq.is_empty() {
             test::black_box(deq.pop_back());
         }
@@ -85,8 +85,8 @@ fn bench_pop_front_100(b: &mut test::Bencher) {
     unsafe { deq.ptr().write_bytes(0u8, size + 1) };
 
     b.iter(|| {
-        deq.head = size;
-        deq.tail = 0;
+        deq.head = 0;
+        deq.len = 100;
         while !deq.is_empty() {
             test::black_box(deq.pop_front());
         }
@@ -105,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);
@@ -124,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);
             }
         }
@@ -150,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);
             }
         }
@@ -259,9 +259,9 @@ fn test_reserve_exact() {
     let mut tester: VecDeque<i32> = VecDeque::with_capacity(1);
     assert!(tester.capacity() == 1);
     tester.reserve_exact(50);
-    assert!(tester.capacity() >= 51);
+    assert!(tester.capacity() >= 50);
     tester.reserve_exact(40);
-    assert!(tester.capacity() >= 51);
+    assert!(tester.capacity() >= 40);
     tester.reserve_exact(200);
     assert!(tester.capacity() >= 200);
 }
@@ -323,6 +323,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);
 
@@ -478,9 +479,9 @@ 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.wrap_idx(tester.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());
 }
 
@@ -499,7 +500,7 @@ 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());
 }
 
@@ -515,10 +516,12 @@ fn make_contiguous_small_free() {
         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()
@@ -536,7 +539,7 @@ fn make_contiguous_small_free() {
     // IJKLM...HGFEDCBA
     let expected_start = 0;
     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()
@@ -550,10 +553,10 @@ fn make_contiguous_head_to_end() {
     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);
+    let expected_head = 0;
+    let expected_len = 3;
     assert_eq!(expected_head, dq.head);
+    assert_eq!(expected_len, dq.len);
     assert_eq!((&['A', 'B', 'C'] as &[_], &[] as &[_]), dq.as_slices());
 }
 
@@ -588,10 +591,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);
@@ -602,8 +605,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);
             }
         }
@@ -617,11 +620,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);
                     }
@@ -642,17 +645,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();
@@ -662,8 +665,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);
                 }
             }
         }
@@ -676,11 +679,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);
                     }
@@ -693,8 +696,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();
@@ -721,17 +724,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);
         }
     }
@@ -758,17 +762,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);
             }
@@ -785,16 +789,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]
@@ -846,10 +844,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) {
@@ -872,7 +866,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);
@@ -880,7 +874,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..);
@@ -893,16 +887,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];
@@ -917,7 +901,6 @@ fn test_from_array() {
             assert_eq!(deq[i], i);
         }
 
-        assert!(deq.cap().is_power_of_two());
         assert_eq!(deq.len(), N);
     }
     test::<0>();
@@ -925,11 +908,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]
diff --git a/library/alloc/tests/vec_deque.rs b/library/alloc/tests/vec_deque.rs
index c1b9e7af9d8..d04de5a074b 100644
--- a/library/alloc/tests/vec_deque.rs
+++ b/library/alloc/tests/vec_deque.rs
@@ -465,7 +465,6 @@ fn test_drain() {
         for i in 6..9 {
             d.push_front(i);
         }
-
         assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
         assert!(d.is_empty());
     }
@@ -1142,7 +1141,7 @@ fn test_reserve_exact_2() {
     v.push_back(16);
 
     v.reserve_exact(16);
-    assert!(v.capacity() >= 48)
+    assert!(v.capacity() >= 33)
 }
 
 #[test]
@@ -1157,7 +1156,7 @@ fn test_try_reserve() {
     // * overflow may trigger when adding `len` to `cap` (in number of elements)
     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
 
-    const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
+    const MAX_CAP: usize = isize::MAX as usize;
     const MAX_USIZE: usize = usize::MAX;
 
     {
@@ -1248,7 +1247,7 @@ fn test_try_reserve_exact() {
     // This is exactly the same as test_try_reserve with the method changed.
     // See that test for comments.
 
-    const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
+    const MAX_CAP: usize = isize::MAX as usize;
     const MAX_USIZE: usize = usize::MAX;
 
     {
@@ -1391,7 +1390,8 @@ fn test_rotate_nop() {
 
 #[test]
 fn test_rotate_left_parts() {
-    let mut v: VecDeque<_> = (1..=7).collect();
+    let mut v: VecDeque<_> = VecDeque::with_capacity(8);
+    v.extend(1..=7);
     v.rotate_left(2);
     assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
     v.rotate_left(2);
@@ -1410,7 +1410,8 @@ fn test_rotate_left_parts() {
 
 #[test]
 fn test_rotate_right_parts() {
-    let mut v: VecDeque<_> = (1..=7).collect();
+    let mut v: VecDeque<_> = VecDeque::with_capacity(8);
+    v.extend(1..=7);
     v.rotate_right(2);
     assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
     v.rotate_right(2);
diff --git a/src/etc/gdb_providers.py b/src/etc/gdb_providers.py
index c351c3450f5..32b8d8e24c6 100644
--- a/src/etc/gdb_providers.py
+++ b/src/etc/gdb_providers.py
@@ -144,20 +144,16 @@ class StdVecDequeProvider:
     def __init__(self, valobj):
         self.valobj = valobj
         self.head = int(valobj["head"])
-        self.tail = int(valobj["tail"])
+        self.size = int(valobj["len"])
         self.cap = int(valobj["buf"]["cap"])
         self.data_ptr = unwrap_unique_or_non_null(valobj["buf"]["ptr"])
-        if self.head >= self.tail:
-            self.size = self.head - self.tail
-        else:
-            self.size = self.cap + self.head - self.tail
 
     def to_string(self):
         return "VecDeque(size={})".format(self.size)
 
     def children(self):
         return _enumerate_array_elements(
-            (self.data_ptr + ((self.tail + index) % self.cap)) for index in xrange(self.size)
+            (self.data_ptr + ((self.head + index) % self.cap)) for index in xrange(self.size)
         )
 
     @staticmethod
diff --git a/src/etc/lldb_providers.py b/src/etc/lldb_providers.py
index 8a9927e7d96..697ad4293c3 100644
--- a/src/etc/lldb_providers.py
+++ b/src/etc/lldb_providers.py
@@ -356,7 +356,7 @@ class StdSliceSyntheticProvider:
 class StdVecDequeSyntheticProvider:
     """Pretty-printer for alloc::collections::vec_deque::VecDeque<T>
 
-    struct VecDeque<T> { tail: usize, head: usize, buf: RawVec<T> }
+    struct VecDeque<T> { head: usize, len: usize, buf: RawVec<T> }
     """
 
     def __init__(self, valobj, dict):
@@ -373,7 +373,7 @@ class StdVecDequeSyntheticProvider:
     def get_child_index(self, name):
         # type: (str) -> int
         index = name.lstrip('[').rstrip(']')
-        if index.isdigit() and self.tail <= index and (self.tail + index) % self.cap < self.head:
+        if index.isdigit() and int(index) < self.size:
             return int(index)
         else:
             return -1
@@ -381,20 +381,16 @@ class StdVecDequeSyntheticProvider:
     def get_child_at_index(self, index):
         # type: (int) -> SBValue
         start = self.data_ptr.GetValueAsUnsigned()
-        address = start + ((index + self.tail) % self.cap) * self.element_type_size
+        address = start + ((index + self.head) % self.cap) * self.element_type_size
         element = self.data_ptr.CreateValueFromAddress("[%s]" % index, address, self.element_type)
         return element
 
     def update(self):
         # type: () -> None
         self.head = self.valobj.GetChildMemberWithName("head").GetValueAsUnsigned()
-        self.tail = self.valobj.GetChildMemberWithName("tail").GetValueAsUnsigned()
+        self.size = self.valobj.GetChildMemberWithName("len").GetValueAsUnsigned()
         self.buf = self.valobj.GetChildMemberWithName("buf")
         self.cap = self.buf.GetChildMemberWithName("cap").GetValueAsUnsigned()
-        if self.head >= self.tail:
-            self.size = self.head - self.tail
-        else:
-            self.size = self.cap + self.head - self.tail
 
         self.data_ptr = unwrap_unique_or_non_null(self.buf.GetChildMemberWithName("ptr"))
 
diff --git a/src/test/ui/hygiene/panic-location.run.stderr b/src/test/ui/hygiene/panic-location.run.stderr
index 216b31586da..0b23b1cc2f4 100644
--- a/src/test/ui/hygiene/panic-location.run.stderr
+++ b/src/test/ui/hygiene/panic-location.run.stderr
@@ -1,2 +1,2 @@
-thread 'main' panicked at 'capacity overflow', $SRC_DIR/alloc/src/collections/vec_deque/mod.rs:LL:COL
+thread 'main' panicked at 'capacity overflow', library/alloc/src/raw_vec.rs:518:5
 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace