Tricky "lifetime may not live long enough" error on an Iterator wrapping a boxed iterator

help
1

Hi all,

I'm attempting to create a new type that wraps a complex iterator. The type owns some data of its own, and then creates an iterator over that data and passes values from that iterator out of its own next() method. Because the internal iterator is complex, I'm type erasing it and storing it in a Box rather than writing out the full type name in the struct declaration. Here's my reduced code example:

struct A<'a> {
    some_numbers: Vec<i32>,
    other_numbers: Vec<i32>,
    iter: Option<Box<dyn Iterator<Item = i32> + 'a>>,
}

impl<'a> A<'a> {
    fn new(some: Vec<i32>, other: Vec<i32>) -> A<'a> {
        A {
            some_numbers: some,
            other_numbers: other,
            iter: None,
        }
    }
}

impl<'a> Iterator for A<'a> {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        match &mut self.iter {
            Some(ref mut iter) => iter.as_mut().next(),
            None => {
                let mut new_iter = self
                    .some_numbers
                    .iter()
                    .chain(self.other_numbers.iter())
                    .cloned();

                let next_item = new_iter.next();
                self.iter = Some(Box::new(new_iter));

                next_item
            }
        }
    }
}

fn main() {
    let some: Vec<i32> = (0..12).collect();
    let other: Vec<i32> = (42..84).collect();

    let a = A::new(some, other);

    println!("{:?}", a.collect::<Vec<i32>>());
}

The error I get here is this:

error: lifetime may not live long enough
  --> src/main.rs:30:17
   |
17 | impl<'a> Iterator for A<'a> {
   |      -- lifetime `'a` defined here
...
20 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
...
30 |                 self.iter = Some(Box::new(new_iter));
   |                 ^^^^^^^^^ assignment requires that `'1` must outlive `'a`

If I understand correctly, the iterator I'm creating in the body of next() may go away at the end of the None block, despite being Boxed and assigned to self.iter. I'm confused by this. Shouldn't the assignment pass ownership of that iterator to self?

Another thing I'm not totally sure of in this example is the type of the internal iterator: Option<Box<dyn Iterator<Item = i32> + 'a>>. Does the + 'a at the end read "this value will live as long as A"?

A way I've tried to correct the error is by declaring a new lifetime on the next() method, apply it the &mut self, and constrain it to live as long as 'a. I get a different error with that approach:

error[E0195]: lifetime parameters or bounds on method `next` do not match the trait declaration
  --> src/main.rs:20:12
   |
20 |     fn next<'b: 'a>(&'b mut self) -> Option<Self::Item> {
   |            ^^^^^^^^ lifetimes do not match method in trait

I gues that's because the Iterator trait doesn't declare a lifetime?

I've spent enough time on this that I'm thinking I may be fundamentally misunderstanding something, or just taking the wrong approach to solving this. Is there another way I should be thinking about how to build this struct?

Thanks a lot!

2

that's correct

no it doesn't. box only moves the value from the stack to the heap, but doesn't change the lifetime in the type of the iterator.

esentially, you are creating a self-referential data structure, and you cannot do it with borrows (box changes nothing because the type has the lifetime in it).

sort of. the + 'a is a bound on the generic type T (i.e. dyn Iterator<Item=i32> in this case) of Box<T>, you can read it like this: the type T or dyn Iterator<Item=i32> can only be assigned to the value of types that has lifetime at least 'a.

that's also how the borrow checker report errors, e.g. in this line of code:

self.iter = Some(Box::new(new_iter));

the type of new_iter must outlive 'a, and its type has the same elided lifetime of &mut self, that's what this error message means:

even if you can change the signature of Iterator::next(), this still doesn't work.

in the expression &'b mut self, which is sugar for &'b mut Self, and substitute A<'a> for Self, you will get self: &'b &mut A<'a>. in such type, the bound 'b: 'a can only resovle to 'b == 'a, which is different from elided lifetime, but it's even worse.

I'd suggest redesign your system to avoid self-referential data structure. for example, design your custom iterator type manages the transient states using indices instead of directly borrowing the underlying data

for this particular example, there's another possibility, that is make your data also borrowed instead of owned (but this will change how the type can be constructed and used, which may or may not be desirable depending your use case), something like this:

struct A<'a> {
    some_numbers: &'a [i32],
    other_numbers: &'a [i32],
    iter: Option<Box<dyn Iterator<Item = i32> + 'a>>,
}
// usage like this:
let some: Vec<i32> = (0..12).collect();
let other: Vec<i32> = (42..84).collect();
let a = A::new(&some, &other);
5 Likes
3

In general, iterators are distinct data structures than the primary struct that owns the data, in part due to issues like this, but also due to concerns around iterator invalidation and the need to carry around iteration state more generally.

For example, if you can call next on the a: A<'_>, then you can create a &mut a (exclusive and mutable access to a and all its fields), so you could also do

a.some_number.clear();
a.sum_number.shrink_to_fit();

Which would invalidate a.iter -- in this particular case it would also be UB if allowed, as iter would contain a dangling pointer that reads freed memory (which demonstrates that it must not be allowed).

Instead you could create a separte struct that borrows from A. With use of -> impl Trait, you might not even need to do the grunt work defining a wrapper struct or implementing Iterator.

The rest of this comment might only make sense for your reduced example and not your actual use case.

If you don't need access to the iterated fields except for iteration, then the iterator as presented is useless once iteration completes. Vecs have a cheap "default value", so you could consume the iterated fields in order to create the iter field.

iter is no longer any borrowing, so there's no need for a lifetime. But then, there's no reason to delaying creation of iter, either. (Also no need erase the iterator type in this particular example.)

1 Like
4

Thank you both for your help here. These are all really helpful insights and suggestions!

This is really helpful context. I hadn't thought about iterator invalidation, but that's a whole thing my bespoke iterator doesn't handle.

This ended up being the solution I went with. It simplifies dealing with types a great deal (no more Box<T>) and lets me still create the iterators I need with standard library types.

5

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.