1 files changed, 70 insertions, 108 deletions

diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs
index e696d7ed6..d9f393714 100644
--- a/library/alloc/src/collections/vec_deque/iter.rs
+++ b/library/alloc/src/collections/vec_deque/iter.rs
@@ -1,9 +1,6 @@
-use core::fmt;
 use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
-use core::mem::MaybeUninit;
 use core::ops::Try;
-
-use super::{count, wrap_index, RingSlices};
+use core::{fmt, mem, slice};
 
 /// An iterator over the elements of a `VecDeque`.
 ///
@@ -13,30 +10,20 @@ use super::{count, wrap_index, RingSlices};
 /// [`iter`]: super::VecDeque::iter
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct Iter<'a, T: 'a> {
-    ring: &'a [MaybeUninit<T>],
-    tail: usize,
-    head: usize,
+    i1: slice::Iter<'a, T>,
+    i2: slice::Iter<'a, T>,
 }
 
 impl<'a, T> Iter<'a, T> {
-    pub(super) fn new(ring: &'a [MaybeUninit<T>], tail: usize, head: usize) -> Self {
-        Iter { ring, tail, head }
+    pub(super) fn new(i1: slice::Iter<'a, T>, i2: slice::Iter<'a, T>) -> Self {
+        Self { i1, i2 }
     }
 }
 
 #[stable(feature = "collection_debug", since = "1.17.0")]
 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            f.debug_tuple("Iter")
-                .field(&MaybeUninit::slice_assume_init_ref(front))
-                .field(&MaybeUninit::slice_assume_init_ref(back))
-                .finish()
-        }
+        f.debug_tuple("Iter").field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish()
     }
 }
 
@@ -44,7 +31,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> Clone for Iter<'_, T> {
     fn clone(&self) -> Self {
-        Iter { ring: self.ring, tail: self.tail, head: self.head }
+        Iter { i1: self.i1.clone(), i2: self.i2.clone() }
     }
 }
 
@@ -54,72 +41,50 @@ impl<'a, T> Iterator for Iter<'a, T> {
 
     #[inline]
     fn next(&mut self) -> Option<&'a T> {
-        if self.tail == self.head {
-            return None;
+        match self.i1.next() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the first one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i1 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i1.next()
+            }
         }
-        let tail = self.tail;
-        self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
-        // Safety:
-        // - `self.tail` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) }
+    }
+
+    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i1.advance_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i1.advance_by(n - m).map_err(|o| o + m)
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let len = count(self.tail, self.head, self.ring.len());
+        let len = self.len();
         (len, Some(len))
     }
 
-    fn fold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            accum = MaybeUninit::slice_assume_init_ref(front).iter().fold(accum, &mut f);
-            MaybeUninit::slice_assume_init_ref(back).iter().fold(accum, &mut f)
-        }
+        let accum = self.i1.fold(accum, &mut f);
+        self.i2.fold(accum, &mut f)
     }
 
     fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
     where
-        Self: Sized,
         F: FnMut(B, Self::Item) -> R,
         R: Try<Output = B>,
     {
-        let (mut iter, final_res);
-        if self.tail <= self.head {
-            // Safety: single slice self.ring[self.tail..self.head] is initialized.
-            iter = unsafe { MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]) }
-                .iter();
-            final_res = iter.try_fold(init, &mut f);
-        } else {
-            // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
-            let (front, back) = self.ring.split_at(self.tail);
-
-            let mut back_iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() };
-            let res = back_iter.try_fold(init, &mut f);
-            let len = self.ring.len();
-            self.tail = (self.ring.len() - back_iter.len()) & (len - 1);
-            iter = unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
-            final_res = iter.try_fold(res?, &mut f);
-        }
-        self.tail = self.head - iter.len();
-        final_res
-    }
-
-    fn nth(&mut self, n: usize) -> Option<Self::Item> {
-        if n >= count(self.tail, self.head, self.ring.len()) {
-            self.tail = self.head;
-            None
-        } else {
-            self.tail = wrap_index(self.tail.wrapping_add(n), self.ring.len());
-            self.next()
-        }
+        let acc = self.i1.try_fold(init, &mut f)?;
+        self.i2.try_fold(acc, &mut f)
     }
 
     #[inline]
@@ -132,8 +97,12 @@ impl<'a, T> Iterator for Iter<'a, T> {
         // Safety: The TrustedRandomAccess contract requires that callers only pass an index
         // that is in bounds.
         unsafe {
-            let idx = wrap_index(self.tail.wrapping_add(idx), self.ring.len());
-            self.ring.get_unchecked(idx).assume_init_ref()
+            let i1_len = self.i1.len();
+            if idx < i1_len {
+                self.i1.__iterator_get_unchecked(idx)
+            } else {
+                self.i2.__iterator_get_unchecked(idx - i1_len)
+            }
         }
     }
 }
@@ -142,63 +111,56 @@ impl<'a, T> Iterator for Iter<'a, T> {
 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
     #[inline]
     fn next_back(&mut self) -> Option<&'a T> {
-        if self.tail == self.head {
-            return None;
+        match self.i2.next_back() {
+            Some(val) => Some(val),
+            None => {
+                // most of the time, the iterator will either always
+                // call next(), or always call next_back(). By swapping
+                // the iterators once the second one is empty, we ensure
+                // that the first branch is taken as often as possible,
+                // without sacrificing correctness, as i2 is empty anyways
+                mem::swap(&mut self.i1, &mut self.i2);
+                self.i2.next_back()
+            }
         }
-        self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
-        // Safety:
-        // - `self.head` in a ring buffer is always a valid index.
-        // - `self.head` and `self.tail` equality is checked above.
-        unsafe { Some(self.ring.get_unchecked(self.head).assume_init_ref()) }
     }
 
-    fn rfold<Acc, F>(self, mut accum: Acc, mut f: F) -> Acc
+    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
+        let m = match self.i2.advance_back_by(n) {
+            Ok(_) => return Ok(()),
+            Err(m) => m,
+        };
+
+        mem::swap(&mut self.i1, &mut self.i2);
+        self.i2.advance_back_by(n - m).map_err(|o| m + o)
+    }
+
+    fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc
     where
         F: FnMut(Acc, Self::Item) -> Acc,
     {
-        let (front, back) = RingSlices::ring_slices(self.ring, self.head, self.tail);
-        // Safety:
-        // - `self.head` and `self.tail` in a ring buffer are always valid indices.
-        // - `RingSlices::ring_slices` guarantees that the slices split according to `self.head` and `self.tail` are initialized.
-        unsafe {
-            accum = MaybeUninit::slice_assume_init_ref(back).iter().rfold(accum, &mut f);
-            MaybeUninit::slice_assume_init_ref(front).iter().rfold(accum, &mut f)
-        }
+        let accum = self.i2.rfold(accum, &mut f);
+        self.i1.rfold(accum, &mut f)
     }
 
     fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
     where
-        Self: Sized,
         F: FnMut(B, Self::Item) -> R,
         R: Try<Output = B>,
     {
-        let (mut iter, final_res);
-        if self.tail <= self.head {
-            // Safety: single slice self.ring[self.tail..self.head] is initialized.
-            iter = unsafe {
-                MaybeUninit::slice_assume_init_ref(&self.ring[self.tail..self.head]).iter()
-            };
-            final_res = iter.try_rfold(init, &mut f);
-        } else {
-            // Safety: two slices: self.ring[self.tail..], self.ring[..self.head] both are initialized.
-            let (front, back) = self.ring.split_at(self.tail);
-
-            let mut front_iter =
-                unsafe { MaybeUninit::slice_assume_init_ref(&front[..self.head]).iter() };
-            let res = front_iter.try_rfold(init, &mut f);
-            self.head = front_iter.len();
-            iter = unsafe { MaybeUninit::slice_assume_init_ref(back).iter() };
-            final_res = iter.try_rfold(res?, &mut f);
-        }
-        self.head = self.tail + iter.len();
-        final_res
+        let acc = self.i2.try_rfold(init, &mut f)?;
+        self.i1.try_rfold(acc, &mut f)
     }
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<T> ExactSizeIterator for Iter<'_, T> {
+    fn len(&self) -> usize {
+        self.i1.len() + self.i2.len()
+    }
+
     fn is_empty(&self) -> bool {
-        self.head == self.tail
+        self.i1.is_empty() && self.i2.is_empty()
     }
 }