Tracking Issue for Iterator::map_windows (feature iter_map_windows)

[LukasKalbertodt]

Feature gate: #![feature(iter_map_windows)]

This is a tracking issue for Iterator::map_windows:

Calls the given function f for each contiguous window of size N over self and returns an iterator over the outputs of f.

In the following example, the closure is called three times with the arguments &['a', 'b'], &['b', 'c'] and &['c', 'd'] respectively.

#![feature(iter_map_windows)]

let strings = "abcd".chars()
    .map_windows(|[x, y]| format!("{}+{}", x, y))
    .collect::<Vec<String>>();

assert_eq!(strings, vec!["a+b", "b+c", "c+d"]);

Public API

impl Iterator {
    fn map_windows<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>
    where
        Self: Sized,
        F: FnMut(&[Self::Item; N]) -> R;
}

struct MapWindows<I: Iterator, F, const N: usize> { ... }

impl<I, F, R, const N: usize> Iterator for MapWindows<I, F, N>
where
    I: Iterator,
    F: FnMut(&[I::Item; N]) -> R;

impl<I: Iterator + fmt::Debug, F, const N: usize> fmt::Debug for MapWindows<I, F, N>;

Steps / History

• Implementation: Add Iterator::map_windows #82413
• Implementation: Add Iterator::map_windows #94667
• Optimize with buffer of size 2 * N
• Any other iterator-related traits?
  • DoubleEndedIterator
  • FusedIterator
  • TrustedLen
• Compile fail on N=0, rather than panic. Blocked on a solution for compile errors in callers that are generic over N and would want a fallback for N=0.
• Final comment period (FCP)
• Stabilization PR

Unresolved Questions

• &[I::Item; N] vs ArrayView<'_, I::Item, N> Tracking Issue for Iterator::map_windows (feature iter_map_windows) #87155 (comment)

[dtolnay]

Copied from #94667 (comment):

Taking GAT for consideration, should the mapper function be FnMut(&[I::Item; N]) -> R or something like FnMut(ArrayView<'_, I::Item, N>) -> R? Where ArrayView is mentioned in rust-lang/generic-associated-types-initiative#2.

• It can save memory, only the same size as the array window is needed,
• It is more efficient, which requires less data copies,
• It is possibly compatible with the GATified version of LendingIterator::windows.
• But it prevents the array pattern matching like iter.map_windows(|_arr: [_; N]| ()), unless we extend the array pattern to allow matching the ArrayView.

[Nydauron]

I have been working on implementing the compile-time check on N (Nydauron@31ffa40). Currently, the change works on all doc tests using ./x test library/core --doc -- Iterator::map_windows, but fails compilation when trying to run all tests ./x test library/core -- Iterator::map_windows with the following error:

error[E0080]: evaluation of `std::iter::MapWindows::<std::iter::Repeat<i32>, {closure@library/core/tests/iter/adapters/map_windows.rs:173:46: 173:58}, 0>::N_NOT_ZERO` failed
    --> /home/<USER>/Git/rust/library/core/src/panic.rs:106:9
     |
79   | / pub macro panic_2021 {
80   | |     () => ({
81   | |         // Create a function so that the argument for `track_caller`
82   | |         // can be moved inside if possible.
...    |
106  | |         $crate::panicking::panic_fmt($crate::const_format_args!($($t)+...
     | |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the evaluated program panicked at 'array in `Iterator::map_windows` must contain more than 0 elements', /home/<USER>/Git/rust/library/core/src/iter/adapters/map_windows.rs:60:9
107  | |     }),
108  | | }
     | |_- in this expansion of `$crate::panic::panic_2021!` (#2)
     |
    ::: /home/<USER>/Git/rust/library/core/src/iter/adapters/map_windows.rs:60:9
     |
60   |   ...   assert!(N != 0, "array in `Iterator::map_windows` must contain more than 0 elements...
     |         -------------------------------------------------------------------------------------
     |         |
     |         in this macro invocation (#1)
     |         in this macro invocation (#2)
     |
    ::: /home/<USER>/Git/rust/library/core/src/macros/mod.rs:1538:5
     |
1538 | /     macro_rules! assert {
1539 | |         ($cond:expr $(,)?) => {{ /* compiler built-in */ }};
1540 | |         ($cond:expr, $($arg:tt)+) => {{ /* compiler built-in ...
1541 | |     }
     | |_____- in this expansion of `assert!` (#1)

note: the above error was encountered while instantiating `fn std::iter::MapWindows::<std::iter::Repeat<i32>, {closure@library/core/tests/iter/adapters/map_windows.rs:173:46: 173:58}, 0>::new`
    --> /home/<USER>/Git/rust/library/core/src/iter/traits/iterator.rs:1747:9
     |
1747 |         MapWindows::new(self, f)
     |         ^^^^^^^^^^^^^^^^^^^^^^^^

For more information about this error, try `rustc --explain E0080`.
error: could not compile `core` (test "coretests") due to previous error

Any idea why this is happening on ./x test library/core and not ./x test library/core --doc?

EDIT: Fixed the issue. It ended up being the test that checked for panic with a zero-width array.

[Jules-Bertholet]

From the docs:

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 contigious array buffer, and thus the returned iterator should be fused.

I'm not sure I understand the reasoning here. Couldn't/shouldn't the iterator return overlapping windows for each run of successive Somes yielded by the inner iterator? IOW, remove this line:

rust/library/core/src/iter/adapters/map_windows.rs

Line 82 in e908cfd

self.iter.take();

[GrayJack]

Taking GAT for consideration, should the mapper function be FnMut(&[I::Item; N]) -> R or something like FnMut(ArrayView<'_, I::Item, N>) -> R? Where ArrayView is mentioned in rust-lang/generic-associated-types-initiative#2.

• It can save memory, only the same size as the array window is needed,
• It is more efficient, which requires less data copies,
• It is possibly compatible with the GATified version of LendingIterator::windows.
• But it prevents the array pattern matching like iter.map_windows(|_arr: [_; N]| ()), unless we extend the array pattern to allow matching the ArrayView.

I like the idea of using ArrayView and making array pattern match ArrayView as well