Confusion understanding lifetimes in a complex iterator

help
1

Hi all,

Playground: Rust Playground

Problem

I'm having trouble implementing a custom iterator for the situation described below, and I hope someone might be able to help:

I am writing a sequential ray tracer for optical systems design where I need to iterate over (Gap, Surface, Option<Gap>) triplets. Each triplet is a single step in the ray trace of a system, and there is always one more surface than there are gaps. I have the following requirements:

  1. A system has many submodels in which the sequence of gaps are different and owned by each submodel
  2. A system only has one sequence of surfaces that can be shared amongst all its submodels
  3. The surfaces need to be mutable, but they must not be mutated during iteration

Since I need multiple ownership of my surfaces and occasionally need to mutate them, I decided to wrap them in a Rc<RefCell<...>>. This way I thought I could keep the Ref guard on the surfaces to keep the borrow alive while I was iterating over the submodel.

Attempt at a solution

struct Model {
    surfs: Rc<RefCell<Vec<Surf>>>,
    gaps: Vec<Gap>,
}

Next, I write the iterator struct as follows:

struct ModelIter<'a> {
    model: &'a Model,
    index: usize,
    guard: Ref<'a, Vec<Surf>>,
}

impl<'a> ModelIter<'a> {
    fn new(model: &'a Model) -> Self {
        // Borrow the surfaces here for the lifetime of the ModelIter
        let guard: Ref<'a, Vec<Surf>> = model.surfs.borrow();
        Self {
            model,
            index: 0,
            guard,
        }
    }
}

The guard field is necessary so that the Ref returned by the RefCell's borrow method is not dropped during the lifetime of the iterator.

Compiler Error

So far, so good. Unfortunately, I have not managed to implement the Iterator trait on this struct because I can't get the lifetimes to work out correctly.

impl<'a> Iterator for ModelIter<'a> {
    type Item = Step<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index == self.model.gaps.len() - 1 {
            // We are at the last gap
            let result = Some((
                &self.model.gaps[self.index],
                &self.guard[self.index + 1],
                None,
            ));
            self.index += 1;
            result
        } else if {
        //...
        }
    }
}

The compiler states:

error: lifetime may not live long enough
  --> src/main.rs:44:13
   |
32 | impl<'a> Iterator for ModelIter<'a> {
   |      -- lifetime `'a` defined here
...
35 |     fn next(&mut self) -> Option<Self::Item> {
   |             - let's call the lifetime of this reference `'1`
...
44 |             result
   |             ^^^^^^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

error: could not compile `playground` (bin "playground") due to 1 previous error

I think that likely my lifetime annotations are incorrect in the struct definitions, but I can't seem to understand really what's going on.

Any advice would be appreciated! Thanks!

2

The Iterator::next method cannot hand out any references to things owned by itself, and your ModelIter owns the Ref it is trying to hand out references to. I would change guard from a Ref<...> to a &'a Ref<...> and pass it instead of having new create it.

2 Likes
3

To explain the error - your ModelIter owns guard so it can't return a reference to it with current Iterator trait. (Look for "rust lending iterators" for more details on that), to fix it - you probably want to remove guard from it and calculate it inside next...

1 Like
4

Thank you for the responses! Ownership of the Ref by the iterator was indeed the issue.

If I change the Iterator to take a reference to the Ref instead, then the compiler is happy:

struct ModelIter<'a> {
    surfs: &'a Ref<'a, Vec<Surf>>,
    gaps: &'a Vec<Gap>,
    index: usize,
}

impl<'a> ModelIter<'a> {
    fn new(surfs: &'a Ref<'a, Vec<Surface>>, gaps: &'a Vec<Gap> ) -> Self {
        Self {
            surfs,
            gaps,
            index: 0,
        }
    }
}
5

If I understand your architecture correctly, you can avoid this and its costs by storing the Vec<Surf> in the system instead of in the models. This does mean that internal operations on a model, like the iterator, have to take &[Surf] as well as &Model, but it avoids needing the Rc or the RefCell (and it's possible to provide a wrapper that transparently borrows both for a clean public API, if desired).

This is entirely optional — it's generally idiomatic Rust to prefer a design that passes more references over one which makes it less clear when and how data is mutated, but there aren't particularly strong disadvantages to your current design if the relevant fields are private.

If the ModelIterator is able to have an &'a Ref<'a, Vec<Surf>>, then it can equally well store an &'a [Surf] borrowed from the same Ref. This makes the iterator potentially more efficient, because accessing the Surfs requires only 1 pointer indirection (&[_]) instead of 3 (&_, Ref<_>, and Vec<_>). This also makes the ModelIterator code simpler, and able to be reused in different situations with different sources of [Surf] and [Gap] than the ones you currently have (if that ever comes up).

2 Likes
6

Thanks a lot @kpreid .

I think you're right in that this can be simplified by relying only slices, but also right in that this will slightly obscure the mapping between the physics model and the code.

Of course I'll need to benchmark it to be sure, but my guess is that any performance bottlenecks won't come from wrapping the surfaces in multiple smart pointers. I can expect at most about ~50 surfaces (less on average) and it's computing hundreds of ray/surface intersections at each surface that will take time.

I really appreciate your input on this. I'll give it some thought for a while.

7

This makes your code (just like most ray-tracers) a very good candidate for parallelization. But you can't access data in a RefCell from multiple threads — unless you borrow it once and share the reference to the contents you get from that. Either that or my other previous suggestion will be parallelizable (the data needed for iteration will be Send + Sync).

If you care at all about performance, parallelism for jobs like this is a huge benefit. Add rayon and try it out — it's easy and, in my weird opinion, fun.

2 Likes
8

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.