Iterator over Mutable Windows of Slice


#1

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


#2

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.


#3

Thank you for your help!


#4

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.