Lifetime: can't build iterator over borrowed content


#1

Hi,
I am having problem with lifetime. I have a structure which iterates over referenced content. And I am having hard times understanding compiler error. I’ve build minimalistic example which replicate the similar iterator and it works without problem, so i know that generally I am in the right direction.

Gives me

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter in function call due to conflicting requirements
   --> src/lib.rs:244:24
    |
244 |             let res = &self.file_info.file_meta.row_groups[self.row_group_idx];
    |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 242:5...
   --> src/lib.rs:242:5
    |
242 | /     fn next(&mut self) -> Option<<Self as Iterator>::Item> {
243 | |         if self.row_group_idx < self.file_info.file_meta.row_groups.len() {
244 | |             let res = &self.file_info.file_meta.row_groups[self.row_group_idx];
245 | |
...   |
250 | |         }
251 | |     }
    | |_____^
note: ...so that reference does not outlive borrowed content
   --> src/lib.rs:244:24
    |
244 |             let res = &self.file_info.file_meta.row_groups[self.row_group_idx];
    |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 239:1...
   --> src/lib.rs:239:1
    |
239 | impl<'a> Iterator for RowGroupIter<'a> {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: ...so that the types are compatible:
            expected std::iter::Iterator
               found std::iter::Iterator

But this example works fine:

#[derive(Debug)]
struct Item { }

struct Data<'a> {
    list: &'a Vec<Item>
}

struct DataIter<'a> {
    data: &'a mut Data<'a>,
    i: usize,
}

impl<'a> Iterator for DataIter<'a> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        if self.i < self.data.list.len() {
            let res = &self.data.list[self.i];
            self.i += 1;
            Some(res)
        } else {
            None
        }
    }
}

fn main() {
    let list = vec!(Item{}, Item{}, Item{});
    let mut data = Data {list: &list};

    let iter = DataIter{data: &mut data, i: 0};
    iter.for_each(|s| println!("{:?}", s));
}

What is the difference and why local reference in one case is returned fine and in another is “too short”?


#2

The example you’ve given does not correctly mimic the scenario of your code, the following is the fixed example and gives the same error when compiling your project

#[derive(Debug)]
struct Item { }

struct Data {
    list: Vec<Item>
}

struct DataIter<'a> {
    data: &'a mut Data,
    i: usize,
}

impl<'a> Iterator for DataIter<'a> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        if self.i < self.data.list.len() {
            let res = &self.data.list[self.i];
            self.i += 1;
            Some(res)
        } else {
            None
        }
    }
}

fn main () {
}

playground

As to why, it seems that iterators cannot return references to values inside itself. My intuition is that you need borrow self.data temporarily before you can access self.data.list, but the temporary reference is limited to the lifetime of next(), thus bounding the lifetime of the returned reference.

I have no idea if my intuition is correct. Either way, you’ll need to wait for someone else who’s much more familiar with Rust to answer it properly. But hopefully the fix helps a bit for testing ideas and stuff.


#3

The problem is that the Iterator holds a mutable borrow, but iterates immutably. I’m not sure why you are doing this. This works:

#[derive(Debug)]
struct Item { }

struct Data {
    list: Vec<Item>
}

struct DataIter<'a> {
    data: &'a Data,
    i: usize,
}

impl<'a> Iterator for DataIter<'a> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        if self.i < self.data.list.len() {
            let res = &self.data.list[self.i];
            self.i += 1;
            Some(res)
        } else {
            None
        }
    }
}

fn main () {
}

The only change is the mutability of the inner reference of DataIter.

The issue here is quite simply is that while the reference your iterator passed out is alive, you could mutate the vector, which might lead to memory unsafety. The compiler can’t prove that the data the borrow points to is always alive.

If you need mutable mutation, you need a second DataIterMut, which holds a mutable borrow and hands out mutable borrows.


#4

@skade, thanks for your answer! I couldn’t believe you, so I wrote an example to illustrate your point:

struct Item { }

struct Data {
    list: Vec<Item>
}

struct DataIter<'a> {
    data: &'a mut Data,
    i: usize,
}

impl<'a> Iterator for DataIter<'a> {
    type Item = &'a Item;

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        // Replaced by `unimplemented!()` to simulate what would happen
        // if the compiler would allow vchekan's code.
    	unimplemented!();
    }
}

impl<'a> DataIter<'a> {
	fn clear(&mut self) {
		self.data.list.clear();
	}
}

fn main() {
	let mut data = Data { list: vec![Item{}, Item{}] };
	let mut dataIter = DataIter{ data: &mut data, i: 0};
	let first = dataIter.next().unwrap();
	dataIter.clear();                     // release the memory associated to `data[0]`
        let first_used = first;               // do something with `data[0]`
}

The compiler accepts this code. I did not expect this because I (wrongly) believed the compiler would also in this case consider a “downgrade” from a mutable reference (&mut data in my code sample) to an immutable reference (first in my code sample) as still borrowing as mutable from the borrow checker’s point of view. I learned something new! Thank you!


#5

That’s because the output’s lifetime is unassociated with the &mut self borrow of the iterator. This is perhaps better seen without lifetime elision:

fn next<'b>(&'b mut self) -> Option<&'a Item>

The 'a is associated with the iterator itself (ie DataIter<'a>), but isn’t the scope of the mutable borrow of it.

Borrow of self is extended only if the output lifetime is associated with borrow of self.

When the iterator holds a mutable borrow of Data and tries to return an immutable reference to its content, the compiler rejects it because mutable references can only be moved or reborrowed. In the case of an iterator, you can’t move the mutable reference because the iterator itself is borrowed in next(). So you need a reborrow. But you can’t reborrow for a longer lifetime (for 'a while only holding a mutable borrow for the “anonymous” lifetime, which is just verbiage for an elided lifetime), and that’s essentially what the error message means in the original case.


#6

Thanks @skade, after some thinking, I understand reasoning.

Compiler message though, still does not make any sense :frowning:
In both cases lifespan of res reference is the same, but in non-mutable case it is decided to have larger lifetime than than in mutable case.