Lifetime issue with ouroboros, implementing iterator over inner collection behind RefCell

I need to implement iterator over underlying collection (say, a vector) which is behind RefCell. There is a similar question on StackOverflow: returning-iterator-of-a-vec-in-a-refcell. My real-world iterator logic is more complex so I don't want to simply forward vector's iterator - I actually want to implement Iterator trait myself. I settled on using ouroboros crate, which was also suggested here, but I can't get past the below lifetime error.

Here's code to reproduce (cannot run on the playground as ouroboros dependency is not there):

use std::cell::{Ref, RefCell};

use ouroboros::self_referencing;

#[derive(Debug)]
struct Foo(u32);

struct Container {
    bar: RefCell<Vec<Foo>>,
}

impl Container {
    fn iter_foo(&self) -> VecRefIterator {
        VecRefIteratorBuilder {
            vec_borrow: self.bar.borrow(),
            vec_iter_builder: |vec_borrow: &Ref<Vec<Foo>>| vec_borrow.iter(),
        }.build()
    }
}

#[self_referencing]
struct VecRefIterator<'a> {
    vec_borrow: Ref<'a, Vec<Foo>>,
    #[borrows(vec_borrow)]
    #[covariant]
    vec_iter: std::slice::Iter<'this, Foo>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.borrow_vec_iter().next()
    }
}

fn main() {
    let container = Container {
        bar: RefCell::new(vec![Foo(1), Foo(2)])
    };

    let it = container.iter_foo();
    while let Some(foo) = it.next() {
        println!("{foo:?}");
    }
}

This yields a lifetime error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/main.rs:33:14
   |
33 |         self.borrow_vec_iter().next()
   |              ^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined here...
  --> src/main.rs:32:13
   |
32 |     fn next(&mut self) -> Option<Self::Item> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:33:9
   |
33 |         self.borrow_vec_iter().next()
   |         ^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
  --> src/main.rs:29:6
   |
29 | impl<'a> Iterator for VecRefIterator<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/main.rs:32:46
   |
32 |       fn next(&mut self) -> Option<Self::Item> {
   |  ______________________________________________^
33 | |         self.borrow_vec_iter().next()
34 | |     }
   | |_____^
   = note: expected `<VecRefIterator<'a> as Iterator>`
              found `<VecRefIterator<'_> as Iterator>`

Basically it fails because I'm not allowed to annorate next(&mut self) with 'a lifetime. This seems like exactly the use-case that ouroboros should help handle.. how is it supposed to work?

Thanks!

Well, your API, if rustc didn’t complain, would allow creating VecRefIterator<'a> from &'a Container, and then &'a Foo from &mut VecRefIterator<'a>, after which the iterator could be dropped. I.e.

fn first_ref<'a>(x: &'a Container) -> &'a Foo {
    x.iter_foo().next().unwrap()
}

would compile, which obviously cannot work! There’s no place for the Ref to be held.

3 Likes

Or in other words,

You can't implement IntoIterator for VecRefWrapper directly because then the internal Ref would be consumed by into_iter(), giving you essentially the same situation you're in now.

still applies. (All Iterators implement IntoIterator.)

The "Alternative solution" on SO demonstrates a way to return an iterator directly (by returning Ref-guarded items).

1 Like

Thank you @quinedot, @steffahn,

Is there any other way to desgin the API (implementing Iterator trait, and not IntoIterator on reference), without having to essentially re-implement iterator like in the Alternate Solution? I would naively think there should be a way to leverage the existing vector's iterator? There doesn't necessarily have to be VecRefIterator struct (but then I don't see what else could hold the Ref). The other answers I linked to suggested this should be possible..

The reason I was hesitant going with the "alternative solution" is because my real-world iterator would need to modify some of the items (e.g. by cloning) - so if iterator returns Ref, it means my new/cloned values would additionally have to be wrapped with Ref which seemed like an unnecessary overhead. But I suppose there's just no way around this.

If you're sometimes cloning things, you'll have to distinguish between returning borrowed and owned values in some way -- whether you use references or Refs. Perhaps via Cow or something like it with a variant for Ref instead of &.

That is to say, you won't be returning & or Refs for newly created/cloned values, as they'd have to be stored somewhere, and Iterators can't return references to things they own (that would be a lending iterator).


In general if you want to utilize some other iterator's implementation in your own, you can just store the other iterator in your struct, and call iterator methods on it as needed. If you decide it's ok to go with the "return a non-iterator from which you can still get an iterator" approach, that would be leveraging the existing vector's iterator. If you want to return an iterator directly, you'll have to be keeping guards around, but can leverage the demonstrated Ref-returning iterator instead.

(In either case, replace the implementation of YourIter<'_> and definition of Item as needed.)

2 Likes

@quinedot just wanted to thank you again for your help! I ended up going with the "return a non-iterator from which you can still get an iterator" approach as a much simpler one (albeit yielding a slightly more akward API) and also returning Cow, as my iterator sometimes returns owned values.

1 Like

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.