Repository: rust-lang/rust
Pull request: Don't fuse in `MapWindows`

<!-- homu-ignore:start -->
<!--
If this PR is related to an unstable feature or an otherwise tracked effort,
please link to the relevant tracking issue here. If you don't know of a related
tracking issue or there are none, feel free to ignore this.

This PR will get automatically assigned to a reviewer. In case you would like
a specific user to review your work, you can assign it to them by using

    r? <reviewer name>
-->
<!-- homu-ignore:end -->

cc https://github.com/rust-lang/rust/issues/87155

Fusing makes the iterator larger, slower, more complicated, and less useful. Users who need fusing behavior can always use `.fuse()`, but there is no way to get non-fusing behavior from the fused version.

@rustbot label A-iterators

Changed files:
filename: library/core/src/iter/adapters/map_windows.rs
patch: @@ -14,10 +14,7 @@ pub struct MapWindows<I: Iterator, F, const N: usize> {
 }
 
 struct MapWindowsInner<I: Iterator, const N: usize> {
-    // We fuse the inner iterator because there shouldn't be "holes" in
-    // the sliding window. Once the iterator returns a `None`, we make
-    // our `MapWindows` iterator return `None` forever.
-    iter: Option<I>,
+    iter: I,
     // Since iterators are assumed lazy, i.e. it only yields an item when
     // `Iterator::next()` is called, and `MapWindows` is not an exception.
     //
@@ -26,7 +23,7 @@ struct MapWindowsInner<I: Iterator, const N: usize> {
     // we collect the first `N` items yielded from the inner iterator and
     // put it into the buffer.
     //
-    // When the inner iterator has returned a `None` (i.e. fused), we take
+    // When the inner iterator has returned a `None`, we take
     // away this `buffer` and leave it `None` to reclaim its resources.
     //
     // FIXME: should we shrink the size of `buffer` using niche optimization?
@@ -64,19 +61,16 @@ impl<I: Iterator, F, const N: usize> MapWindows<I, F, N> {
 impl<I: Iterator, const N: usize> MapWindowsInner<I, N> {
     #[inline]
     fn new(iter: I) -> Self {
-        Self { iter: Some(iter), buffer: None }
+        Self { iter, buffer: None }
     }
 
     fn next_window(&mut self) -> Option<&[I::Item; N]> {
-        let iter = self.iter.as_mut()?;
         match self.buffer {
             // It is the first time to advance. We collect
             // the first `N` items from `self.iter` to initialize `self.buffer`.
-            None => self.buffer = Buffer::try_from_iter(iter),
-            Some(ref mut buffer) => match iter.next() {
+            None => self.buffer = Buffer::try_from_iter(&mut self.iter),
+            Some(ref mut buffer) => match self.iter.next() {
                 None => {
-                    // Fuse the inner iterator since it yields a `None`.
-                    self.iter.take();
                     self.buffer.take();
                 }
                 // Advance the iterator. We first call `next` before changing our buffer
@@ -89,8 +83,7 @@ impl<I: Iterator, const N: usize> MapWindowsInner<I, N> {
     }
 
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let Some(ref iter) = self.iter else { return (0, Some(0)) };
-        let (lo, hi) = iter.size_hint();
+        let (lo, hi) = self.iter.size_hint();
         if self.buffer.is_some() {
             // If the first `N` items are already yielded by the inner iterator,
             // the size hint is then equal to the that of the inner iterator's.
@@ -253,12 +246,10 @@ where
     }
 }
 
-// Note that even if the inner iterator not fused, the `MapWindows` is still fused,
-// because we don't allow "holes" in the mapping window.
 #[unstable(feature = "iter_map_windows", issue = "87155")]
 impl<I, F, R, const N: usize> FusedIterator for MapWindows<I, F, N>
 where
-    I: Iterator,
+    I: FusedIterator,
     F: FnMut(&[I::Item; N]) -> R,
 {
 }

filename: library/core/src/iter/traits/iterator.rs
patch: @@ -1657,11 +1657,6 @@ pub const trait Iterator {
     /// items yielded by `self`). If 𝑘 is less than `N`, this method yields an
     /// empty iterator.
     ///
-    /// The returned iterator implements [`FusedIterator`], because once `self`
-    /// returns `None`, even if it returns a `Some(T)` again in the next iterations,
-    /// we cannot put it into a contiguous array buffer, and thus the returned iterator
-    /// should be fused.
-    ///
     /// [`slice::windows()`]: slice::windows
     /// [`FusedIterator`]: crate::iter::FusedIterator
     ///
@@ -1722,7 +1717,7 @@ pub const trait Iterator {
     /// assert_eq!(it.next(), None);
     /// ```
     ///
-    /// For non-fused iterators, they are fused after `map_windows`.
+    /// For non-fused iterators, the window is reset after `None` is yielded.
     ///
     /// ```
     /// #![feature(iter_map_windows)]
@@ -1739,44 +1734,47 @@ pub const trait Iterator {
     ///         let val = self.state;
     ///         self.state = self.state + 1;
     ///
-    ///         // yields `0..5` first, then only even numbers since `6..`.
-    ///         if val < 5 || val % 2 == 0 {
-    ///             Some(val)
-    ///         } else {
+    ///         // Skip every 5th number
+    ///         if (val + 1) % 5 == 0 {
     ///             None
+    ///         } else {
+    ///             Some(val)
     ///         }
     ///     }
     /// }
     ///
     ///
     /// let mut iter = NonFusedIterator::default();
     ///
-    /// // yields 0..5 first.
     /// assert_eq!(iter.next(), Some(0));
     /// assert_eq!(iter.next(), Some(1));
     /// assert_eq!(iter.next(), Some(2));
     /// assert_eq!(iter.next(), Some(3));
-    /// assert_eq!(iter.next(), Some(4));
-    /// // then we can see our iterator going back and forth
     /// assert_eq!(iter.next(), None);
+    /// assert_eq!(iter.next(), Some(5));
     /// assert_eq!(iter.next(), Some(6));
-    /// assert_eq!(iter.next(), None);
+    /// assert_eq!(iter.next(), Some(7));
     /// assert_eq!(iter.next(), Some(8));
     /// assert_eq!(iter.next(), None);
+    /// assert_eq!(iter.next(), Some(10));
+    /// assert_eq!(iter.next(), Some(11));
     ///
-    /// // however, with `.map_windows()`, it is fused.
     /// let mut iter = NonFusedIterator::default()
     ///     .map_windows(|arr: &[_; 2]| *arr);
     ///
     /// assert_eq!(iter.next(), Some([0, 1]));
     /// assert_eq!(iter.next(), Some([1, 2]));
     /// assert_eq!(iter.next(), Some([2, 3]));
-    /// assert_eq!(iter.next(), Some([3, 4]));
     /// assert_eq!(iter.next(), None);
     ///
-    /// // it will always return `None` after the first time.
-    /// assert_eq!(iter.next(), None);
+    /// assert_eq!(iter.next(), Some([5, 6]));
+    /// assert_eq!(iter.next(), Some([6, 7]));
+    /// assert_eq!(iter.next(), Some([7, 8]));
     /// assert_eq!(iter.next(), None);
+    ///
+    /// assert_eq!(iter.next(), Some([10, 11]));
+    /// assert_eq!(iter.next(), Some([11, 12]));
+    /// assert_eq!(iter.next(), Some([12, 13]));
     /// assert_eq!(iter.next(), None);
     /// ```
     #[inline]

filename: library/coretests/tests/iter/adapters/map_windows.rs
patch: @@ -284,3 +284,29 @@ fn test_size_hint() {
     check_size_hint::<5>((5, Some(5)), (1, Some(1)));
     check_size_hint::<5>((5, Some(10)), (1, Some(6)));
 }
+
+#[test]
+fn test_unfused() {
+    #[derive(Default)]
+    struct UnfusedIter(usize);
+    impl Iterator for UnfusedIter {
+        type Item = usize;
+
+        fn next(&mut self) -> Option<usize> {
+            let curr = self.0;
+            self.0 += 1;
+            if curr % 7 == 0 { None } else { Some(curr) }
+        }
+    }
+
+    let mut iter = UnfusedIter(1).map_windows(|a: &[_; 3]| *a);
+    assert_eq!(iter.by_ref().collect::<Vec<_>>(), vec![[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6]]);
+    assert_eq!(
+        iter.by_ref().collect::<Vec<_>>(),
+        vec![[8, 9, 10], [9, 10, 11], [10, 11, 12], [11, 12, 13]]
+    );
+    assert_eq!(
+        iter.by_ref().collect::<Vec<_>>(),
+        vec![[15, 16, 17], [16, 17, 18], [17, 18, 19], [18, 19, 20]]
+    );
+}