Tracking Issue for `Iterator::map_windows` (feature `iter_map_windows`) #87155

LukasKalbertodt · 2021-07-15T11:13:55Z

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

Unresolved Questions

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

The text was updated successfully, but these errors were encountered:

dtolnay · 2023-02-28T05:28:02Z

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.

…, r=Mark-Simulacrum Add `Iterator::map_windows` Tracking issue: rust-lang#87155. This is inherited from the old PR rust-lang#82413. Unlike rust-lang#82413, this PR implements the `MapWindows` to be lazy: only when pulling from the outer iterator, `.next()` of the inner iterator will be called. ## Implementaion Steps - [x] Implement `MapWindows` to keep the iterators' [*Laziness*](https://doc.rust-lang.org/std/iter/index.html#laziness) contract. - [x] Fix the known bug of memory access error. - [ ] Full specialization of iterator-related traits for `MapWindows`. - [x] `Iterator::size_hint`, - [x] ~`Iterator::count`~, - [x] `ExactSizeIterator` (when `I: ExactSizeIterator`), - [x] ~`TrustedLen` (when `I: TrustedLen`)~, - [x] `FusedIterator`, - [x] ~`Iterator::advance_by`~, - [x] ~`Iterator::nth`~, - [ ] ... - [ ] More tests and docs. ## Unresolved Questions: - [ ] Is there any more iterator-related traits should be specialized? - [ ] Is the double-space buffer worth? - [ ] Should there be `rmap_windows` or something else? - [ ] 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 · 2023-12-11T01:32:11Z

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 · 2024-04-10T16:02:51Z

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();

LukasKalbertodt added C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. labels Jul 15, 2021

dtolnay mentioned this issue Aug 29, 2021

Permit impl item to end with semicolon tree-sitter/tree-sitter-rust#118

Merged

frank-king mentioned this issue Mar 6, 2022

Add Iterator::map_windows #94667

Merged

16 tasks

Nydauron mentioned this issue Feb 15, 2024

Add MapWindows compile fail check for N=0 #121156

Closed

the8472 mentioned this issue Mar 7, 2024

const if to supress instantiation/codegen of unreachable branches rust-lang/rfcs#3582

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tracking Issue for `Iterator::map_windows` (feature `iter_map_windows`) #87155

Tracking Issue for `Iterator::map_windows` (feature `iter_map_windows`) #87155

LukasKalbertodt commented Jul 15, 2021 •

edited by the8472

Loading

dtolnay commented Feb 28, 2023

Nydauron commented Dec 11, 2023 •

edited

Loading

Jules-Bertholet commented Apr 10, 2024

Tracking Issue for Iterator::map_windows (feature iter_map_windows) #87155

Tracking Issue for Iterator::map_windows (feature iter_map_windows) #87155

Comments

LukasKalbertodt commented Jul 15, 2021 • edited by the8472 Loading

Public API

Steps / History

Unresolved Questions

dtolnay commented Feb 28, 2023

Nydauron commented Dec 11, 2023 • edited Loading

Jules-Bertholet commented Apr 10, 2024

Tracking Issue for `Iterator::map_windows` (feature `iter_map_windows`) #87155

Tracking Issue for `Iterator::map_windows` (feature `iter_map_windows`) #87155

LukasKalbertodt commented Jul 15, 2021 •

edited by the8472

Loading

Nydauron commented Dec 11, 2023 •

edited

Loading