Rollup merge of #79479 - camelid:intersperse, r=m-ou-se

Add `Iterator::intersperse`

This is a rebase of #75784. I'm hoping to push this past the finish line!

cc `@jonas-schievink`

8 files changed, 189 insertions, 2 deletions

diff --git a/library/core/src/iter/adapters/intersperse.rs b/library/core/src/iter/adapters/intersperse.rs
new file mode 100644
index 00000000000..36232672549
--- /dev/null
+++ b/library/core/src/iter/adapters/intersperse.rs
@@ -0,0 +1,76 @@
+use super::Peekable;
+
+/// An iterator adapter that places a separator between all elements.
+#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
+#[derive(Debug, Clone)]
+pub struct Intersperse<I: Iterator>
+where
+    I::Item: Clone,
+{
+    separator: I::Item,
+    iter: Peekable<I>,
+    needs_sep: bool,
+}
+
+impl<I: Iterator> Intersperse<I>
+where
+    I::Item: Clone,
+{
+    pub(in crate::iter) fn new(iter: I, separator: I::Item) -> Self {
+        Self { iter: iter.peekable(), separator, needs_sep: false }
+    }
+}
+
+#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
+impl<I> Iterator for Intersperse<I>
+where
+    I: Iterator,
+    I::Item: Clone,
+{
+    type Item = I::Item;
+
+    #[inline]
+    fn next(&mut self) -> Option<I::Item> {
+        if self.needs_sep && self.iter.peek().is_some() {
+            self.needs_sep = false;
+            Some(self.separator.clone())
+        } else {
+            self.needs_sep = true;
+            self.iter.next()
+        }
+    }
+
+    fn fold<B, F>(mut self, init: B, mut f: F) -> B
+    where
+        Self: Sized,
+        F: FnMut(B, Self::Item) -> B,
+    {
+        let mut accum = init;
+
+        // Use `peek()` first to avoid calling `next()` on an empty iterator.
+        if !self.needs_sep || self.iter.peek().is_some() {
+            if let Some(x) = self.iter.next() {
+                accum = f(accum, x);
+            }
+        }
+
+        let element = &self.separator;
+
+        self.iter.fold(accum, |mut accum, x| {
+            accum = f(accum, element.clone());
+            accum = f(accum, x);
+            accum
+        })
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (lo, hi) = self.iter.size_hint();
+        let next_is_elem = !self.needs_sep;
+        let lo = lo.saturating_sub(next_is_elem as usize).saturating_add(lo);
+        let hi = match hi {
+            Some(hi) => hi.saturating_sub(next_is_elem as usize).checked_add(hi),
+            None => None,
+        };
+        (lo, hi)
+    }
+}
diff --git a/library/core/src/iter/adapters/mod.rs b/library/core/src/iter/adapters/mod.rs
index b8d3430f910..7dfbf32cea7 100644
--- a/library/core/src/iter/adapters/mod.rs
+++ b/library/core/src/iter/adapters/mod.rs
@@ -11,6 +11,7 @@ mod filter_map;
 mod flatten;
 mod fuse;
 mod inspect;
+mod intersperse;
 mod map;
 mod map_while;
 mod peekable;
@@ -41,6 +42,9 @@ pub use self::flatten::Flatten;
 #[stable(feature = "iter_copied", since = "1.36.0")]
 pub use self::copied::Copied;
 
+#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
+pub use self::intersperse::Intersperse;
+
 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
 pub use self::map_while::MapWhile;
 
diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs
index 3e74637b49f..569de719d03 100644
--- a/library/core/src/iter/mod.rs
+++ b/library/core/src/iter/mod.rs
@@ -395,6 +395,8 @@ pub use self::adapters::Cloned;
 pub use self::adapters::Copied;
 #[stable(feature = "iterator_flatten", since = "1.29.0")]
 pub use self::adapters::Flatten;
+#[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
+pub use self::adapters::Intersperse;
 #[unstable(feature = "iter_map_while", reason = "recently added", issue = "68537")]
 pub use self::adapters::MapWhile;
 #[unstable(feature = "inplace_iteration", issue = "none")]
diff --git a/library/core/src/iter/traits/iterator.rs b/library/core/src/iter/traits/iterator.rs
index 7ba16f89284..633175702d8 100644
--- a/library/core/src/iter/traits/iterator.rs
+++ b/library/core/src/iter/traits/iterator.rs
@@ -8,7 +8,7 @@ use crate::ops::{Add, ControlFlow, Try};
 use super::super::TrustedRandomAccess;
 use super::super::{Chain, Cloned, Copied, Cycle, Enumerate, Filter, FilterMap, Fuse};
 use super::super::{FlatMap, Flatten};
-use super::super::{FromIterator, Product, Sum, Zip};
+use super::super::{FromIterator, Intersperse, Product, Sum, Zip};
 use super::super::{
     Inspect, Map, MapWhile, Peekable, Rev, Scan, Skip, SkipWhile, StepBy, Take, TakeWhile,
 };
@@ -569,6 +569,28 @@ pub trait Iterator {
         Zip::new(self, other.into_iter())
     }
 
+    /// Places a copy of `separator` between all elements.
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(iter_intersperse)]
+    ///
+    /// let hello = ["Hello", "World"].iter().copied().intersperse(" ").collect::<String>();
+    /// assert_eq!(hello, "Hello World");
+    /// ```
+    #[inline]
+    #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]
+    fn intersperse(self, separator: Self::Item) -> Intersperse<Self>
+    where
+        Self: Sized,
+        Self::Item: Clone,
+    {
+        Intersperse::new(self, separator)
+    }
+
     /// Takes a closure and creates an iterator which calls that closure on each
     /// element.
     ///
diff --git a/library/core/tests/iter.rs b/library/core/tests/iter.rs
index ec4b49da384..7376e7848ef 100644
--- a/library/core/tests/iter.rs
+++ b/library/core/tests/iter.rs
@@ -3505,3 +3505,85 @@ pub fn extend_for_unit() {
     }
     assert_eq!(x, 5);
 }
+
+#[test]
+fn test_intersperse() {
+    let xs = ["a", "", "b", "c"];
+    let v: Vec<&str> = xs.iter().map(|x| x.clone()).intersperse(", ").collect();
+    let text: String = v.concat();
+    assert_eq!(text, "a, , b, c".to_string());
+
+    let ys = [0, 1, 2, 3];
+    let mut it = ys[..0].iter().map(|x| *x).intersperse(1);
+    assert!(it.next() == None);
+}
+
+#[test]
+fn test_intersperse_size_hint() {
+    let xs = ["a", "", "b", "c"];
+    let mut iter = xs.iter().map(|x| x.clone()).intersperse(", ");
+    assert_eq!(iter.size_hint(), (7, Some(7)));
+
+    assert_eq!(iter.next(), Some("a"));
+    assert_eq!(iter.size_hint(), (6, Some(6)));
+    assert_eq!(iter.next(), Some(", "));
+    assert_eq!(iter.size_hint(), (5, Some(5)));
+
+    assert_eq!([].iter().intersperse(&()).size_hint(), (0, Some(0)));
+}
+
+#[test]
+fn test_fold_specialization_intersperse() {
+    let mut iter = (1..2).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+
+    let mut iter = (1..3).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+
+    let mut iter = (1..4).intersperse(0);
+    iter.clone().for_each(|x| assert_eq!(Some(x), iter.next()));
+}
+
+#[test]
+fn test_try_fold_specialization_intersperse_ok() {
+    let mut iter = (1..2).intersperse(0);
+    iter.clone().try_for_each(|x| {
+        assert_eq!(Some(x), iter.next());
+        Some(())
+    });
+
+    let mut iter = (1..3).intersperse(0);
+    iter.clone().try_for_each(|x| {
+        assert_eq!(Some(x), iter.next());
+        Some(())
+    });
+
+    let mut iter = (1..4).intersperse(0);
+    iter.clone().try_for_each(|x| {
+        assert_eq!(Some(x), iter.next());
+        Some(())
+    });
+}
+
+#[test]
+fn test_try_fold_specialization_intersperse_err() {
+    let orig_iter = ["a", "b"].iter().copied().intersperse("-");
+
+    // Abort after the first item.
+    let mut iter = orig_iter.clone();
+    iter.try_for_each(|_| None::<()>);
+    assert_eq!(iter.next(), Some("-"));
+    assert_eq!(iter.next(), Some("b"));
+    assert_eq!(iter.next(), None);
+
+    // Abort after the second item.
+    let mut iter = orig_iter.clone();
+    iter.try_for_each(|item| if item == "-" { None } else { Some(()) });
+    assert_eq!(iter.next(), Some("b"));
+    assert_eq!(iter.next(), None);
+
+    // Abort after the third item.
+    let mut iter = orig_iter.clone();
+    iter.try_for_each(|item| if item == "b" { None } else { Some(()) });
+    assert_eq!(iter.next(), None);
+}
diff --git a/library/core/tests/lib.rs b/library/core/tests/lib.rs
index 9e8ec706021..fba3294e0bb 100644
--- a/library/core/tests/lib.rs
+++ b/library/core/tests/lib.rs
@@ -51,6 +51,7 @@
 #![feature(array_value_iter)]
 #![feature(iter_advance_by)]
 #![feature(iter_partition_in_place)]
+#![feature(iter_intersperse)]
 #![feature(iter_is_partitioned)]
 #![feature(iter_order_by)]
 #![feature(cmp_min_max_by)]
diff --git a/src/librustdoc/clean/utils.rs b/src/librustdoc/clean/utils.rs
index 2cde0c209ee..a6c090c6576 100644
--- a/src/librustdoc/clean/utils.rs
+++ b/src/librustdoc/clean/utils.rs
@@ -8,7 +8,6 @@ use crate::clean::{
 };
 use crate::core::DocContext;
 
-use itertools::Itertools;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Res};
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index e8bf664d45c..7ed64c5813f 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -17,6 +17,7 @@
 #![feature(type_ascription)]
 #![feature(split_inclusive)]
 #![feature(str_split_once)]
+#![feature(iter_intersperse)]
 #![recursion_limit = "256"]
 
 #[macro_use]