A `windows_mut` method on slice

libs
1

I noticed that there is a windows method on slice, allowing accessing to the items with a sliding window, but there isn't a windows_mut method allowing mutation within the window. Is there any previous discussion about this or is this just missing because no one has a demand for it?

In my case, I want to divide a big integer represented as a mutable slice of words, by a double word. I need to have a window of width two sliding through the words and make changes inplace. It's feasible to work around this by using chunks_exact_mut, but I need to write a lot of utility code, and I would rather use unsafe access to the slice.

2

And similarly, there's an unstable method called array_windows, why don't we add an array_windows_mut just like the array_chunks_mut?

3

Because it would be UB.

An iterator must give out independent items that can live at the same time -- that's how collect can work, for example. But if windows_mut existed you could use it to get two &muts to the same item, and that situation is immediate UB.

So this will need lending iterators (formerly streaming iterators) before it can be offered.

See Add `Iterator::map_windows` by frank-king · Pull Request #94667 · rust-lang/rust · GitHub for discussion of something that we could possibly do in the mean time.

9 Likes
4

It is a technical limitation. Unfortunately, windows_mut is currently impossible to express in Rust. The problem is clear once you look at type signatures with fully specified lifetimes:

pub fn windows(self: &[T], size: usize) -> Windows<'_, T> ;

pub struct Windows<'a, T: 'a>;

impl<'a, T> Iterator for Windows<'a, T> {
    type Item = &'a [T];

    fn next(&mut self) -> Option<&'a [T]>;
}

Note that the lifetime of the Option in the return type of Iterator::next is tied to the lifetime of the entire Windows instance, rather than to the lifetime of the &mut self borrow. This means that all returned slices must be able to coexist simultaneously, which is impossible for &mut [T] slices.

The proper signature should be

impl<'a, T> Iterator for Windows<'a, T> {
    type Item<'b> = &'b [T];

    fn next<'b>(&'b mut self) -> Option<Slef::Item<'b>> where 'a: 'b;
}

but this is currently impossible, since it requires the associated type Item to be generic in 'b. This is gated by the feature generic associated types.

3 Likes
5

Thanks for the clear explanation! I didn't expect this to be related to GAT lol.

6

Is this documented in the core library? I didn't know this rule existed, thanks for the info

7

It’s less of a special “rule” and more of a direct consequence of the fact that the Iterator::next method has a type signature where the return type doesn’t depend on the lifetime of &mut self.

Explicitly documenting this further as an existing “limitation” probably makes more sense once there’s an official “lending iterator” trait one can point to. On second thought… looking at the lengthy existing module-level documentation, perhaps there is a nice place around this section where we could add a remark on the fact that items from the iterator cannot be … well, how to put this … “containing references whose lifetime is limited to a single call to .next()” perhaps; together with some explanation why.

12 Likes
8

Maybe you should add your use-case to the great GAT stabilization ticket: Stabilize generic associated types by jackh726 · Pull Request #96709 · rust-lang/rust · GitHub

/me checks that ticket for updates, is interested to see "Blocked (at least in part) by GATs: Rust in the linux kernel"

9

Note that if by "word" you mean "primitive integer" (or other simple Copy type), then you can indirect through Cells to get what you want.

  1. Use https://doc.rust-lang.org/std/cell/struct.Cell.html#method.from_mut to turn your &mut [u32] into &Cell<[u32]>.
  2. Use https://doc.rust-lang.org/std/cell/struct.Cell.html#method.as_slice_of_cells to turn the &Cell<[u32]> into &[Cell<u32>].
  3. Use https://doc.rust-lang.org/std/primitive.slice.html#method.windows to get an iterator of the windows-of-cells
  4. Use the Cell methods to update the words as needed.

This has zero runtime overhead. But it'll force you to stay single-threaded so you can't use it to introduce data races.

Which makes me wonder if it's be worth adding a windows_of_cells function to slices. It's not strictly necessary, but Cell::from_mut(x).as_slice_of_cells().windows(n) isn't exactly discoverable, and it'd be a good place to talk about why there's no windows_mut. Conveniently, it wouldn't even require a different iterator type -- it's just be -> Windows<'_, Cell<T>> instead of windows's -> Windows<'_, T>.

EDIT (much later): I added docs under https://doc.rust-lang.org/std/primitive.slice.html#method.windows talking about this approach.

3 Likes
10

Cool! This trick looks interesting, and it would be great if we could at least add some documentation about this work around (maybe in the documentation of window()?)

11

While it would be unsound to have a windows_mut() that returns an Iterator, that doesn't mean you can't have mutable windows at all in current Rust, just that they can't be presented as an Iterator in particular.

pub fn for_each_window_mut<T, F>(slice: &mut [T], size: usize, mut function: F)
where
    F: FnMut(&mut [T])
{
    for start in 0..=(slice.len().saturating_sub(size)) {
        function(&mut slice[start..][..size]);
    }
}

#[test]
fn test() {
    let mut data = [1, 2, 3, 4, 5, 6];
    let mut seen = Vec::new();
    for_each_window_mut(&mut data, 3, |window| {
        seen.push(window.to_vec());
        for element in window {
            *element *= 10;
        }
    });
    
    assert_eq!(seen, vec![
        vec![1, 2, 3],
        vec![20, 30, 4],
        vec![300, 40, 5],
        vec![400, 50, 6],
    ]);
}

Adding mutable windows to the standard library should probably wait for lending iterators, rather than adding the above function since it isn't very general — I only mean to point out that you don't need to wait for language changes or employ GAT workarounds, if all you want to do is write a clean loop over windows.

4 Likes
12

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.