Does 'a: 't means 'a is same as 't?

The following code compiling fails.
It means 'a is as long as 't in the next<'a>(&'a mut self) .
I don't expect this, I even put the a into a block to force it shorter....But I failed to do that.

Why this happen?

struct WindowsMut<'t, T> {
    slice: &'t mut [T],
    start: usize,
    window_size: usize,
}

#[allow(dead_code)]
impl<'t, T> WindowsMut<'t, T> {
    fn next<'a>(&'a mut self) -> Option<&'a mut [T]>
    where
        'a: 't,
    {
        let retval = self.slice[self.start..].get_mut(..self.window_size)?;
        self.start += 1;
        Some(retval)
    }
}

fn main() {
    let mut x: WindowsMut<'_, i32> = WindowsMut::<'_, i32> {
        slice: &mut [1, 2, 3],
        start: 0,
        window_size: 3,
    };
    
    {
        let a = &mut x;
        a.next();
        drop(a);
    }
    x.next();
}

Does ‘a: ‘t means ‘a is same as ‘t?

No, it doesn't. It means that 'a is at least as long as 't. However, because mutable references are invariant in their lifetime, using/understanding such lifetime bounds is not as simple as that when mutable references are involved. Also note that an explicit lifetime annotation on &self is usually a code smell and is not what you want.

Anyway, what you are trying to do is simply not possible. You are trying to return a subslice of self.slice, which means returning mutable references to the elements of the window. Yet, the WindowsMut struct still has a mutable reference to the entire slice. That would cause aliased mutable references to the elements under the window. That is outright prohibited in Rust, so no amount of lifetime juggling will solve it.

It's no accident slices have a chunks_mut() and a windows() method, but not windows_mut().

Your next method takes an &'a mut self, where the type Self is WindowsMut<'t, T>, meaning it takes &'a mut WindowsMut<'t, T>. Since a reference can't outlive the thing it points to there's an implicit bound t': 'a from the existance of that type. The only way this bound can be satisfied together with your explicit 'a: 't bound is for 'a = 't.

The 'a: 't bound is useless, if you remove it it should work.

2 Likes

However, that results in a lifetime for the return value that is too short. Since this iterator doesn't own its data, only borrows it, the returned lifetime shouldn't depend on the lifetime of the iterator itself. Therefore, the desired return type would be &'t mut [T], with which it doesn't work.

BTW, the reverse where 't: 'a works (meaning iterator's whole slice t is borrowed for longer than slice a returned from the next call).

faint, That is what I want to do from the beginning....

You can't return overlapping &mut (exclusive) slices that live for as long as the whole slice, because that violates mutable aliasing and is unsafe.

let a = iter.next();
let b = iter.next();
use_both(a, b);

The exclusive slices must either never overlap (like chunks_mut()), or this code must not compile (that's the reason there's no windows_mut() on std Iterator). There's no third option for &mut slices.

1 Like

You also need to change the return type's lifetime to make that too short. OP was using 'a as lifetime for the return type and that worked. If you introduce the bound you're just requiring 't to be shorter, which is the opposite of what you want.

The iterator owns the mutable reference, and it needs to keep ownership of it even after a call to next because it needs it to return the next window. Thus the return lifetime depends on the lifetime of the &mut self borrow.

I didn't mean "too short" as in "doesn't compile"; I meant "too short" as in "not long enough to be useful".

I understand the technical necessity (as it should be apparent from my answers above), but the problem is that the usefulness of an iterator is severely limited when you can't hold on to several items at the same time. This contradicts with the technical necessity of non-overlapping mutable borrows, but it would still be desirable.

I read this post and made none sense at first.
Now I notice the thing I can't understand: why it doesn't work.

In general, I know it should not work -- that is exactly what rust try best to do -- while, I don't know how rust achieves this.

The simpler code:

struct WindowsMut<'t, T> {
    slice: &'t mut [T],
}

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

#[test]
fn get_mut() {
    let mut x: WindowsMut<'_, i32> = WindowsMut::<'_, i32> {
        slice: &mut [1, 2, 3],
    };

    println!("{:?}", x.next());
}

self.slice is of type &'t mut[i32], and the return type is &'t mut[i32], exactly matches each other.

while, rustc reports:
associated function was supposed to return data with lifetime 't, but it is returning data with lifetime 'a``

How did it realize that?

If you look at the error message, you can notice it points to the act of returning self.slice, and not to the signature. The signature is "correct" (or it would be correct, for what you are trying to do, if it were achievable).

The thing is, self.slice is behind a reference of lifetime 'a, i.e., &'a mut self. Now a mutable reference is non-copiable, so the only way you can return self.slice is by reborrowing it, which the compiler helpfully does instead of trying to move out of the reference, so your function body is effectively equivalent with:

impl<'t, T> WindowsMut<'t, T> {
    fn next<'a>(&'a mut self) -> &'t mut [T]
    where
        't: 'a,
    {
        &mut *self.slice
    }
}

And here's the core reason: if you borrow from behind a reference with some lifetime 'a, then you are not allowed to return a reference with a longer lifetime, only an equal or shorter one (this is what is meant by "references are covariant in their lifetime"). Doing that would allow you to cause dangling references.

Here, 'a is necessarily shorter (not longer) than 't, and this means that whatever you borrow from behind &'a mut self will also have this shorter 'a lifetime, despite it coming from a &'t mut reference. If you were to re-write the code using immutable references, it would work because immutable references don't need to be reborrowed, as they can be Copyed.

1 Like

.windows_mut() cannot be implemented with the stdlib's Iterator API, since .take(2).collect() would give you two concurrent &mut accesses that overlap over a same value, which contradicts the very essence of &mut.

If you want a .next()-based API, but one which does not allow for .collect()ing or concurrent usage of multiple items, then what you are looking for is for the LendingIterator API:

In there, you can even find:

There is a similar simplified and more commented example over here:

Screenshot 2022-09-16 at 20.49.47

1 Like