Lifetimes error I don't understand

[yonatan-linik]

I have this piece of code:

struct OVec {
    a: Vec<f64>,
}

impl OVec {
    fn len(&self) -> usize {
        self.a.len()
    }
}

impl From<Vec<f64>> for OVec {
    fn from(value: Vec<f64>) -> Self {
        let mut v = Self {
            a: Vec::with_capacity(value.len()),
        };
        for p in value {
            v.a.push(p);
        }
        v
    }
}

struct OMut<'o> {
    a: &'o mut f64,
}

struct OVecIterMut<'o> {
    v: &'o mut OVec,
    index: usize,
}
impl<'o> Iterator for OVecIterMut<'o> {
    type Item = OMut<'o>;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.index >= self.v.len() {
            None
        } else {
            self.index += 1;
            Some(OMut {
                a: unsafe { self.v.a.get_unchecked_mut(self.index - 1) },
            })
        }
    }
}
impl<'o> OVec {
    fn iter_mut(&'o mut self) -> OVecIterMut<'o> {
        OVecIterMut { v: self, index: 0 }
    }
}

I am getting the following error:

error: lifetime may not live long enough
|
31 | impl<'o> Iterator for OVecIterMut<'o> {
| -- lifetime 'o defined here
...
34 | fn next(&mut self) -> Option<Self::Item> {
| - let's call the lifetime of this reference '1
...
39 | / Some(OMut {
40 | | a: unsafe { self.v.a.get_unchecked_mut(self.index - 1) },
41 | | })
| |______________^ method was supposed to return data with lifetime 'o but it is returning data with lifetime '1

I don't understand why the lifetime is reduced like this when the compiler knows self.v lives for 'o, why would it reduce the lifetime of a member of it to '1?

And a side note: when removing the mutability of the f64 borrow, the code compile.

[vague]

Because the Iterator trait in std is a giving trait, not a lending trait.

Same question these days

Iterator: lifetime may not live long enough method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

The pattern is called lending iterator, and the solution in stable Rust is via GAT: use ::lending_iterator::prelude::*; use std::io::{BufRead, Result}; pub struct SourceHandler<R> where R: BufRead, { reader: R, source: String, } impl<R> SourceHandler<R> where R: BufRead, { pub fn new(reader: R) -> Self { Self { reader, source: String::new(), } } } pub struct SourceHandlerIter<'a, R> where R: BufRead, { source_handler: &'…

[kpreid]

@yonatan-linik

the compiler knows self.v lives for 'o

The compiler knows that *self.v is valid for 'o, but the same is not true of borrows of *self.v. In order to ensure non-overlap of mutable references, reborrows through mutable references can't live as long as the original reference — they can only live as long as the shortest involved lifetime, which in this case is the lifetime of the &mut self via which you got access to v.

(This is specific to mutable references — immutable references are not exclusive, so they do not need this lifetime shortening.)

In general, you cannot write an Iterator over mutable references, taken from a slice, from scratch, without using unsafe code to bypass the lifetime checking [see correction below by @2e71828] while using indexing — because the compiler doesn't analyze your self.index += 1 to see that it ensures non-overlap, so if the borrow checker allowed this code, it would be unsound. (You are already using unsafe code, but only to bypass bounds checking.)

Your code looks to me to be equivalent to the usual slice iter_mut(), so for practical programming rather than a learning exercise, you should use the existing std::slice::IterMut iterator, or a wrapper around it. For applications that aren't exactly regular iteration, split_first_mut() or split_at_mut() might be useful.

[yonatan-linik]

So something like this would be a solution?:

unsafe {
    let elem = OMut {
        a: &mut *(self.v.a.get_unchecked_mut(self.index - 1) as *mut _),
    };
    Some(elem)
}

[kpreid]

No, that's UB because get_unchecked_mut takes &mut self, and that mutable borrow of self.v.a overlaps with the iterator's previously returned &muts which may still be alive. The iterator must store a raw pointer, not a reference, and avoid any operations which turn that pointer into a reference until you've narrowed it down to the specific non-overlapping reference.

You should use the built-in std::slice::IterMut instead of doing this. Unsafe code is tricky to write, and so to increase overall reliability, whenever possible, you should rely on already-written and thoroughly tested unsafe code rather than writing your own.

[2e71828]

@kpreid

In general, you cannot write an Iterator over mutable references, taken from a slice, from scratch, without using unsafe code to bypass the lifetime checking

This isn't quite true. You can use pattern matching to do it safely:

struct OVecIterMut<'o> {
    v: &'o mut [f64],
}

impl<'o> Iterator for OVecIterMut<'o> {
    type Item = OMut<'o>;
    
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        match std::mem::replace(&mut self.v, &mut []) {
            [] => None,
            [head, tail @ ..] => {
                self.v = tail;
                Some(OMut { a: head })
            }
        }
    }
}

impl<'o> OVec {
    fn iter_mut(&'o mut self) -> OVecIterMut<'o> {
        OVecIterMut { v: &mut self.a[..] }
    }
}

Rust Playground

[kpreid]

Thank you for the correction! I also see now that split_first_mut() does exactly that — I has assumed it was internally unsafe like split_at_mut() is.

[quinedot]

It wasn't your question, but this

impl From<Vec<f64>> for OVec {
    fn from(value: Vec<f64>) -> Self {
        let mut v = Self {
            a: Vec::with_capacity(value.len()),
        };
        for p in value {
            v.a.push(p);
        }
        v
    }
}

Is more succinctly written as this

impl From<Vec<f64>> for OVec {
    fn from(value: Vec<f64>) -> Self {
        Self {
            a: value.into_iter().collect()
        }
    }
}

But even better written as this

impl From<Vec<f64>> for OVec {
    fn from(a: Vec<f64>) -> Self {
        Self { a }
    }
}

There's no reason to transfer items to a new Vec<f64> since you already own the original. (And if you didn't, you could just clone.)