It took a bit of time to finish writing this reply, so it's somewhat redundant with the others.
Let's start with the non-lending iterator.
pub trait Iterator {
type Item;
fn next<'this>(&'this mut self) -> Option<Self::Item>;
}
Item is defined outside of the context of 'this. It's impossible for 'this to be part of the Item type in any implementation. That means that it's impossible for it to contain a (lifetime-tracked) borrow derived from &'this mut self in the return of next. And it has to be defined everywhere that the implementation is valid.
The language exploits this in various ways. For example:
fn example<I: Iterator<Item: std::fmt::Debug>>(mut iter: I) -> I::Item {
// Exclusively borrow `iter` to get an item.
let one = iter.next();
// And again... this exclusive borrow does not invalidate `one`.
let two = iter.next();
// So they're both usable here.
println!("{:?}", (&one, &two));
// And we can even return an item even though the iterator will
// be destructed before this function returns.
one.unwrap()
}
If Items were able to contain a borrow derived from &mut self, this couldn't compile. (Calling next or destructing iter would invalidate any items you previously got from calling next.)
We can have some exclusively-borrowing iterators with the standard Iterator, so why can't we have WindowsMut? Consider a window size of 2.
let arr = [0, 1, 2];
let mut iter = windows_mut::<_, 2>(&mut arr);
let one = iter.next().unwrap(); // &mut arr[0..2] ([0, 1])
let two = iter.next().unwrap(); // &mut arr[1..3] ([1, 2])
If one and two were able to be usable at the same time, we would have two active &muts to the same memory (where 1 is stored). This is a violation of one of Rust's foundational axioms -- &mut are exclusive -- and would thus be UB.
Therefore, whatever the specific error ends up being, a WindowsMut implementation with the standard Iterator trait must not be allowed to safely compile.
With a lending iterator, when the Item<'_> ends up containing a borrow derived from &mut self, you can never hold on to more than one item at a time. Calling next again requires a fresh exclusive borrow of the iterator, which -- unlike Iterator -- invalidates any outstanding borrowing items.
(The exclusively-borrowing iterators that do work with Iterator never hand out references to overlapping memory.)
@drewtato covered this well -- you can't get a &'long mut T out of a &'short mut &'long mut T.
The attempt at making WindowsMut work with the standard Iterator trait is actually an illustration of why this has to be enforced. If it compiled, callers could get overlapping &mut _s!
At the type system level, &'short mut &'long mut T implies 'long: 'short. This means that uses of 'short keep the 'long borrow alive... but not the other way around. If you could get a &'long mut T out from behind a &'short mut &'long mut T, the 'short can expire without invalidating your new &'long mut T -- and without invalidating the original &'long mut T. That is UB if the two &'long mut T overlap.
In the mutable slice iterator implementation I linked, we have to jump through some hoops to ensure there is no overlapping memory. But a proper WindowsMut implementation requires overlapping memory, so there is no sound workaround using Iterator.
A little more detail
Some(self.slice.get_mut(..WINDOW_SIZE)?.try_into().unwrap())
To get a &'a mut [..] from get_mut, you would need to call get_mut on the slice when it was not behind &mut self, to avoid a &'short mut &'long mut _ situation.
let slice = match self.first {
true => mem::take(&mut self.slice),
false => &mut mem::take(&mut self.slice)[1..],
};
self.first = false;
let window: &'a mut [T; WINDOW_SIZE] = slice.get_mut(..WINDOW_SIZE)?.try_into().unwrap();
// self.slice = slice;
Some(window)
But there's no way to properly restore self.slice since the portion you want to keep overlaps with the portion you want to return.
Yes.
The returned slice keeps *self -- the WindowsMut itself -- exclusively borrowed. You can't call next again until it's gone.
All the slices given out have the same borrow duration, and they do not keep the WindowsMut itself borrowed. Perhaps think of it like you had a Vec<&'a mut [T]> and you popped one out. The Vec itself doesn't stay borrowed after the pop even if you keep using the item (you can pop again while still using the item). It just gave you a borrow from elsewhere that it was holding onto.
You know the slices do not overlap, because they are exclusive (&mut _) and you can use them all at the same time (e.g. you can always collect a standard Iterator).
Do you mean something like this, which also compiles?
let mut slice = [1usize, 2, 3, 4];
let mut wm: WindowsMut<'_, usize, 1> = windows_mut(&mut slice);
let mr = &mut wm; // <--- "the same mutable borrow"
while let Some(i) = mr.next() {
*i = [0; 1];
}
println!("{:?}", mr);
println!("{:?}", wm);
Every call to mr.next() reborrows *mr for some duration that ends before the next call. If we unroll the loop a bit:
let mr = &mut wm; //-------------------------+
// |
if let Some(i) = mr.next() { //-----+ :
*i = [0; 1]; // | :
//----no more uses of i---------+ :
} // |
if let Some(i) = mr.next() { //-----+ :
*i = [0; 1]; // | :
//----no more uses of i---------+ :
} // |
// |
println!("{:?}", mr); // |
//----no more uses of mr---------------------+
It's harder to visualize the loop, but basically the compiler sees that there's a point in the control flow at the end of the loop body where the borrow doesn't need to be active any more, so it doesn't propagate to the subsequent call to next.
If you make the outer lifetime of mr nameable ('r), you can indirectly see that you must not be getting back &'r mut [T]s.
fn ex<'r, 'a>(mr: &'r mut WindowsMut<'a, usize, 1>) {
while let Some(i) = mr.next() {
// Uncomment this line to see an error
// let i: &'r mut _ = i;
*i = [0; 1];
}
println!("{:?}", mr);
}
