1 files changed, 410 insertions, 0 deletions
diff --git a/third_party/rust/rayon/src/iter/intersperse.rs b/third_party/rust/rayon/src/iter/intersperse.rs
new file mode 100644
index 0000000000..798bdc1d67
--- /dev/null
+++ b/third_party/rust/rayon/src/iter/intersperse.rs
@@ -0,0 +1,410 @@
+use super::plumbing::*;
+use super::*;
+use std::cell::Cell;
+use std::iter::{self, Fuse};
+
+/// `Intersperse` is an iterator that inserts a particular item between each
+/// item of the adapted iterator.  This struct is created by the
+/// [`intersperse()`] method on [`ParallelIterator`]
+///
+/// [`intersperse()`]: trait.ParallelIterator.html#method.intersperse
+/// [`ParallelIterator`]: trait.ParallelIterator.html
+#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
+#[derive(Clone, Debug)]
+pub struct Intersperse<I>
+where
+    I: ParallelIterator,
+    I::Item: Clone,
+{
+    base: I,
+    item: I::Item,
+}
+
+impl<I> Intersperse<I>
+where
+    I: ParallelIterator,
+    I::Item: Clone,
+{
+    /// Creates a new `Intersperse` iterator
+    pub(super) fn new(base: I, item: I::Item) -> Self {
+        Intersperse { base, item }
+    }
+}
+
+impl<I> ParallelIterator for Intersperse<I>
+where
+    I: ParallelIterator,
+    I::Item: Clone + Send,
+{
+    type Item = I::Item;
+
+    fn drive_unindexed<C>(self, consumer: C) -> C::Result
+    where
+        C: UnindexedConsumer<I::Item>,
+    {
+        let consumer1 = IntersperseConsumer::new(consumer, self.item);
+        self.base.drive_unindexed(consumer1)
+    }
+
+    fn opt_len(&self) -> Option<usize> {
+        match self.base.opt_len()? {
+            0 => Some(0),
+            len => len.checked_add(len - 1),
+        }
+    }
+}
+
+impl<I> IndexedParallelIterator for Intersperse<I>
+where
+    I: IndexedParallelIterator,
+    I::Item: Clone + Send,
+{
+    fn drive<C>(self, consumer: C) -> C::Result
+    where
+        C: Consumer<Self::Item>,
+    {
+        let consumer1 = IntersperseConsumer::new(consumer, self.item);
+        self.base.drive(consumer1)
+    }
+
+    fn len(&self) -> usize {
+        let len = self.base.len();
+        if len > 0 {
+            len.checked_add(len - 1).expect("overflow")
+        } else {
+            0
+        }
+    }
+
+    fn with_producer<CB>(self, callback: CB) -> CB::Output
+    where
+        CB: ProducerCallback<Self::Item>,
+    {
+        let len = self.len();
+        return self.base.with_producer(Callback {
+            callback,
+            item: self.item,
+            len,
+        });
+
+        struct Callback<CB, T> {
+            callback: CB,
+            item: T,
+            len: usize,
+        }
+
+        impl<T, CB> ProducerCallback<T> for Callback<CB, T>
+        where
+            CB: ProducerCallback<T>,
+            T: Clone + Send,
+        {
+            type Output = CB::Output;
+
+            fn callback<P>(self, base: P) -> CB::Output
+            where
+                P: Producer<Item = T>,
+            {
+                let producer = IntersperseProducer::new(base, self.item, self.len);
+                self.callback.callback(producer)
+            }
+        }
+    }
+}
+
+struct IntersperseProducer<P>
+where
+    P: Producer,
+{
+    base: P,
+    item: P::Item,
+    len: usize,
+    clone_first: bool,
+}
+
+impl<P> IntersperseProducer<P>
+where
+    P: Producer,
+{
+    fn new(base: P, item: P::Item, len: usize) -> Self {
+        IntersperseProducer {
+            base,
+            item,
+            len,
+            clone_first: false,
+        }
+    }
+}
+
+impl<P> Producer for IntersperseProducer<P>
+where
+    P: Producer,
+    P::Item: Clone + Send,
+{
+    type Item = P::Item;
+    type IntoIter = IntersperseIter<P::IntoIter>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        IntersperseIter {
+            base: self.base.into_iter().fuse(),
+            item: self.item,
+            clone_first: self.len > 0 && self.clone_first,
+
+            // If there's more than one item, then even lengths end the opposite
+            // of how they started with respect to interspersed clones.
+            clone_last: self.len > 1 && ((self.len & 1 == 0) ^ self.clone_first),
+        }
+    }
+
+    fn min_len(&self) -> usize {
+        self.base.min_len()
+    }
+    fn max_len(&self) -> usize {
+        self.base.max_len()
+    }
+
+    fn split_at(self, index: usize) -> (Self, Self) {
+        debug_assert!(index <= self.len);
+
+        // The left needs half of the items from the base producer, and the
+        // other half will be our interspersed item.  If we're not leading with
+        // a cloned item, then we need to round up the base number of items,
+        // otherwise round down.
+        let base_index = (index + !self.clone_first as usize) / 2;
+        let (left_base, right_base) = self.base.split_at(base_index);
+
+        let left = IntersperseProducer {
+            base: left_base,
+            item: self.item.clone(),
+            len: index,
+            clone_first: self.clone_first,
+        };
+
+        let right = IntersperseProducer {
+            base: right_base,
+            item: self.item,
+            len: self.len - index,
+
+            // If the index is odd, the right side toggles `clone_first`.
+            clone_first: (index & 1 == 1) ^ self.clone_first,
+        };
+
+        (left, right)
+    }
+
+    fn fold_with<F>(self, folder: F) -> F
+    where
+        F: Folder<Self::Item>,
+    {
+        let folder1 = IntersperseFolder {
+            base: folder,
+            item: self.item,
+            clone_first: self.clone_first,
+        };
+        self.base.fold_with(folder1).base
+    }
+}
+
+struct IntersperseIter<I>
+where
+    I: Iterator,
+{
+    base: Fuse<I>,
+    item: I::Item,
+    clone_first: bool,
+    clone_last: bool,
+}
+
+impl<I> Iterator for IntersperseIter<I>
+where
+    I: DoubleEndedIterator + ExactSizeIterator,
+    I::Item: Clone,
+{
+    type Item = I::Item;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.clone_first {
+            self.clone_first = false;
+            Some(self.item.clone())
+        } else if let next @ Some(_) = self.base.next() {
+            // If there are any items left, we'll need another clone in front.
+            self.clone_first = self.base.len() != 0;
+            next
+        } else if self.clone_last {
+            self.clone_last = false;
+            Some(self.item.clone())
+        } else {
+            None
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let len = self.len();
+        (len, Some(len))
+    }
+}
+
+impl<I> DoubleEndedIterator for IntersperseIter<I>
+where
+    I: DoubleEndedIterator + ExactSizeIterator,
+    I::Item: Clone,
+{
+    fn next_back(&mut self) -> Option<Self::Item> {
+        if self.clone_last {
+            self.clone_last = false;
+            Some(self.item.clone())
+        } else if let next_back @ Some(_) = self.base.next_back() {
+            // If there are any items left, we'll need another clone in back.
+            self.clone_last = self.base.len() != 0;
+            next_back
+        } else if self.clone_first {
+            self.clone_first = false;
+            Some(self.item.clone())
+        } else {
+            None
+        }
+    }
+}
+
+impl<I> ExactSizeIterator for IntersperseIter<I>
+where
+    I: DoubleEndedIterator + ExactSizeIterator,
+    I::Item: Clone,
+{
+    fn len(&self) -> usize {
+        let len = self.base.len();
+        len + len.saturating_sub(1) + self.clone_first as usize + self.clone_last as usize
+    }
+}
+
+struct IntersperseConsumer<C, T> {
+    base: C,
+    item: T,
+    clone_first: Cell<bool>,
+}
+
+impl<C, T> IntersperseConsumer<C, T>
+where
+    C: Consumer<T>,
+{
+    fn new(base: C, item: T) -> Self {
+        IntersperseConsumer {
+            base,
+            item,
+            clone_first: false.into(),
+        }
+    }
+}
+
+impl<C, T> Consumer<T> for IntersperseConsumer<C, T>
+where
+    C: Consumer<T>,
+    T: Clone + Send,
+{
+    type Folder = IntersperseFolder<C::Folder, T>;
+    type Reducer = C::Reducer;
+    type Result = C::Result;
+
+    fn split_at(mut self, index: usize) -> (Self, Self, Self::Reducer) {
+        // We'll feed twice as many items to the base consumer, except if we're
+        // not currently leading with a cloned item, then it's one less.
+        let base_index = index + index.saturating_sub(!self.clone_first.get() as usize);
+        let (left, right, reducer) = self.base.split_at(base_index);
+
+        let right = IntersperseConsumer {
+            base: right,
+            item: self.item.clone(),
+            clone_first: true.into(),
+        };
+        self.base = left;
+        (self, right, reducer)
+    }
+
+    fn into_folder(self) -> Self::Folder {
+        IntersperseFolder {
+            base: self.base.into_folder(),
+            item: self.item,
+            clone_first: self.clone_first.get(),
+        }
+    }
+
+    fn full(&self) -> bool {
+        self.base.full()
+    }
+}
+
+impl<C, T> UnindexedConsumer<T> for IntersperseConsumer<C, T>
+where
+    C: UnindexedConsumer<T>,
+    T: Clone + Send,
+{
+    fn split_off_left(&self) -> Self {
+        let left = IntersperseConsumer {
+            base: self.base.split_off_left(),
+            item: self.item.clone(),
+            clone_first: self.clone_first.clone(),
+        };
+        self.clone_first.set(true);
+        left
+    }
+
+    fn to_reducer(&self) -> Self::Reducer {
+        self.base.to_reducer()
+    }
+}
+
+struct IntersperseFolder<C, T> {
+    base: C,
+    item: T,
+    clone_first: bool,
+}
+
+impl<C, T> Folder<T> for IntersperseFolder<C, T>
+where
+    C: Folder<T>,
+    T: Clone,
+{
+    type Result = C::Result;
+
+    fn consume(mut self, item: T) -> Self {
+        if self.clone_first {
+            self.base = self.base.consume(self.item.clone());
+            if self.base.full() {
+                return self;
+            }
+        } else {
+            self.clone_first = true;
+        }
+        self.base = self.base.consume(item);
+        self
+    }
+
+    fn consume_iter<I>(self, iter: I) -> Self
+    where
+        I: IntoIterator<Item = T>,
+    {
+        let mut clone_first = self.clone_first;
+        let between_item = self.item;
+        let base = self.base.consume_iter(iter.into_iter().flat_map(|item| {
+            let first = if clone_first {
+                Some(between_item.clone())
+            } else {
+                clone_first = true;
+                None
+            };
+            first.into_iter().chain(iter::once(item))
+        }));
+        IntersperseFolder {
+            base,
+            item: between_item,
+            clone_first,
+        }
+    }
+
+    fn complete(self) -> C::Result {
+        self.base.complete()
+    }
+
+    fn full(&self) -> bool {
+        self.base.full()
+    }
+}