Iterator over Mutable Windows of Slice

[declanvk]

I would like to iterator through all neighboring pairs of element in a vector. At first I thought that I could use exact_chunks_mut (which is behind a feature flag), but then I realized the the chunk_* family produces slices that do not overlap. I turned to the windows function, but was unable to find a variant that provided mutable access.

Is it possible to solve this issue without resulting to unsafe code?

Example code:

let mut nodes: Vec<Node<P, P::Constraint>> = Vec::new();
for constraint in constraints {
    let header = root.columns
        .entry(constraint.clone())
        .or_insert_with(|| Header::new(&constraint));

    let node = Node::new(possibility, header);
    nodes.push(node);
}


for pair in nodes.windows_mut(2) { // currently does not exist
    let (left, right) = pair.split_at_mut(1);

    left[0].add_right(&mut right[0]);
    right[0].add_left(&mut left[0]);
}

If I wanted to roll my own windows_mut, what would be some of the challenges associated with that?

Thanks,
Declan

[ExpHP]

windows_mut cannot be soundly implemented as an iterator even with unsafe code, due to limitations of the Iterator trait. Basically, because Self::Item can only be a single type, all returned items will have type &'a mut [T] with the same lifetime 'a, meaning their lifetimes will effectively overlap.

You can write something that is almost an iterator. Basically just a regular struct with a method like Iterator::next, except that the lifetime in the output is bound to a much shorter lifetime (the &mut self in next):

impl<'a, T> WindowsMut<'a, T> {
    fn next(&mut self) -> Option<&mut [T]> { ... }
}

and use it like

// can't use `for`; not an iterator
while let Some(window) = windows.next() {
    ...
}

I think this can be implemented in safe code even.

[declanvk]

Thank you for your help!

[HadrienG]

Just to clarify, windows_mut cannot be a method of Iterator because if you ran collect() on such an iterator, you would get a Vec of overlapping mutable slices, thusly violating Rust's "no mutable aliasing" guarantee.

The design which @ExpHP presented (so-called streaming iterator) avoids this problem because you are not allowed to hold multiple outputs of the iterator at the same time.

[Neutron3529]

Is a window_mut_each which is similar to for_each still possible?
window_mut_each returns () just like what for_each did, thus it won't suffer from the collect issue.
or something like window_mut_scan?

[mbrubeck]

Yes, you can implement windows_mut_each like this:

fn windows_mut_each<T>(v: &mut [T], n: usize, mut f: impl FnMut(&mut [T])) {
    let mut start = 0;
    let mut end = n;
    while end <= v.len()  {
        f(&mut v[start..end]);
        start += 1;
        end += 1;
    }
}

Playground

[Yandros]

FWIW, here is what a more full solution involving the mentioned .next() basic method would look like:

implementation

mod lib {
    use ::core::convert::Infallible;

    pub
    struct WindowsMut<'iter, Item : 'iter, const N: usize> {
        slice: &'iter mut [Item],
        start: usize,
    }
    
    impl<'iter, Item : 'iter, const N: usize> WindowsMut<'iter, Item, { N }> {
        pub
        fn next (self: &'_ mut Self)
          -> Option<&'_ mut [Item; N]>
        {
            // Advance for the next iteration
            let start = self.start;
            self.start = start.checked_add(1)?;
            
            Some({
                use ::core::convert::TryInto;
                self.slice
                    .get_mut(start ..)?
                    .get_mut(.. N)?
                    .try_into()
                    .unwrap()
            })
        }
        
        
        pub
        fn try_fold<Acc, E, F> (
            mut self: Self,
            acc0: Acc,
            mut f: F,
        ) -> Result<Acc, E>
        where
            F : FnMut(Acc, &'_ mut [Item; N]) -> Result<Acc, E>,
        {
            let mut acc = acc0;
            while let Some(window) = self.next() {
                acc = f(acc, window)?;
            }
            Ok(acc)
        }
        
        pub
        fn try_for_each<E, F> (
            self: Self,
            mut f: F,
        ) -> Result<(), E>
        where
            F : FnMut(&'_ mut [Item; N]) -> Result<(), E>,
        {
            self.try_fold((), |(), window| f(window))
        }
        
        pub
        fn fold<Acc, F> (
            self: Self,
            acc0: Acc,
            mut f: F,
        ) -> Acc
        where
            F : FnMut(Acc, &'_ mut [Item; N]) -> Acc,
        {
            self.try_fold(acc0, |acc, window| {
                    Ok::<_, Infallible>(f(acc, window))
                })
                .unwrap_or_else(|unreachable| match unreachable {})
        }
        
        pub
        fn for_each (self, mut f: impl FnMut(&'_ mut [Item; N]))
        {
            self.fold((), |(), window| f(window))
        }
    }

    #[allow(nonstandard_style)]
    pub
    trait windows_mut {
        type Item;

        fn windows_mut<const N: usize> (self: &'_ mut Self)
          -> WindowsMut<'_, Self::Item, { N }>
        ;
    }
    
    impl<Item> windows_mut for [Item] {
        type Item = Item;
        
        fn windows_mut<const N: usize> (self: &'_ mut Self)
          -> WindowsMut<'_, Self::Item, { N }>
        {
            WindowsMut { slice: self, start: 0 }
        }
    }
}

fn main ()
{
    use lib::windows_mut;
    
    let mut v = vec![42, 22, 5];
    v.windows_mut::<2>().for_each(|window| {
        dbg!(&window);
        window[1] += window[0];
    });
    dbg!(v);
}

• Playground

---

EDIT: this is now featured in a fully-fledged crate:

lending-iterator