Conflicting Lifetimes - Burrowed Content is Unable to Outlive Container

Question

I'm trying to implement Iterator for one of my structs:

pub struct Node {
    pub val: Vec<usize>,
}

pub struct NodeIter<'a, 'b> {
    val: &'a Vec<usize>,
    env: &'b mut Env,

    index: usize,
}

impl<'a, 'b> Iterator for NodeIter<'a, 'b> {
    type Item = &'b mut Obj;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.val.len() {
            return Some(self.env.get_obj_at_mut(self.val[self.index]))
        }

        self.index += 1;

        None
    }
}

and upon compilation get the following error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src\core\nodes.rs:20:23
   |
20 |         Some(self.env.get_obj_at_mut(self.val[self.index]))
   |                       ^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime defined here...
  --> src\core\nodes.rs:19:13
   |
19 |     fn next(&mut self) -> Option<&'a mut Obj> {
   |             ^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src\core\nodes.rs:20:14
   |
20 |         Some(self.env.get_obj_at_mut(self.val[self.index]))
   |              ^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined here...
  --> src\core\nodes.rs:16:6
   |
16 | impl<'a> Iterator for NodeIter<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src\core\nodes.rs:20:9
   |
20 |         Some(self.env.get_obj_at_mut(self.val[self.index]))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `Option<&'a mut Obj>`
              found `Option<&mut Obj>`

I understood the issue to be that the &mut Obj from get_obj_at_mut (which returns a &mut Obj with a lifetime of 'b, same as env) might outlive &mut self leaving a null reference in its place. The issue is that env is bound by a mutable reference and may last beyond NodeIter

So I tried two options:

1. 'b: 'c:

impl<'a, 'b> NodeIter<'a, 'b> {
    fn next_impl<'c>(&'c mut self) -> Option<&'b mut Obj> where 'b: 'c {
        if self.index < self.val.len() {
            return Some(self.env.get_obj_at_mut(self.val[self.index]))
        }

        self.index += 1;

        None
    }
}

this fails, stating that 'b cannot outlive 'c

2. 'c: 'b

impl<'a, 'b> NodeIter<'a, 'b> {
    fn next_impl<'c>(&'c mut self) -> Option<&'b mut Obj> where 'c: 'b {
        if self.index < self.val.len() {
            return Some(self.env.get_obj_at_mut(self.val[self.index]))
        }

        self.index += 1;

        None
    }
}

this allowed next-impl to successfully compile, but it cannot be called from next due to the lifetime limitations

I know this might be similar to other questions about Rust lifetimes, but I haven't been able to figure out why 'b can't outlive 'c and more generally how to implement Iterator

I'm still new to Rust, so any help would be much appreciated

EDIT

pub fn get_obj_at_mut(&mut self, index: usize) -> &mut Obj {
        &mut self.symbols[index]
}

this is in the impl block for Env, where symbols is an owned Vec of Obj

Answer 1

Your attempted implementation would make it possible to hold two mutable borrows to the same Obj value if val contains a duplicate index. Consider what would happen if val contained a duplicate index and the user of this code .collect()ed the iterator into a Vec! That situation is not allowed by Rust's memory safety rules, and that's ultimately why the next() implementation fails to compile.

In fact, any implementation you could come up with is going to trip on that fundamental problem: nothing prevents Iterator::next() from being invoked again while you still hold a mutable reference returned from a prior call, and the language can't guarantee that all the mutable references produced by the iterator will alias different values.

So how do things like iter_mut() on slices work? Easy: they use unsafe code. unsafe is where you tell the compiler that you have done the work yourself to prove that what you're doing doesn't violate any of Rust's safety rules, and so it lets you do some extra things that you can't normally do.

If you want to do this without using unsafe code, you are going to have to swap the iteration around so that you call iter_mut() on whatever collection is internal to your Env and filter it down based on the indices in a Node. This obviously has performance implications, and it also is very likely to iterate in a different order.

Here is a complete example showing how that can work, with placeholder methods for Env:

pub struct Env;
pub struct Obj;

impl Env {
    #[allow(unreachable_code)]
    pub fn iter_mut(&mut self) -> impl Iterator<Item=&mut Obj> {
        todo!();
        
        std::iter::empty()
    }

    pub fn get_obj_at_mut(&mut self, _: usize) -> &mut Obj {
        todo!();
    }
}

pub struct Node {
    pub val: Vec<usize>,
}

impl Node {
    pub fn iter_mut<'a>(&'a self, env: &'a mut Env)
        -> impl Iterator<Item=&'a mut Obj>
    {
        env.iter_mut()
            .enumerate()
            .filter_map(move |(index, v)|
                if self.val.contains(&index) { Some(v) } else { None }
            )
    }
}

If the performance and ordering implications of this approach aren't acceptable, then unsafe code is your only resort. In particular, you must verify that val contains no duplicate indices or you will violate Rust's rule that there must be at most one usable mutable reference to any given value.

If you have verified this before you construct the NodeIter value then you can use unsafe code to convince Rust that what you're doing here is okay. Note that in this code I've also fixed the bug where the index is never incremented, because you return early.

impl<'a, 'b> Iterator for NodeIter<'a, 'b> {
    type Item = &'b mut Obj;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.val.len() {
            let obj = self.env.get_obj_at_mut(self.val[self.index]);
            self.index += 1;

            // SAFETY: We already verified that self.val contains
            // no duplicate indices, and nobody can modify it while
            // we hold a reference to it, so it's not possible for
            // this iterator to produce two references to the same
            // value.

            // Convert to a pointer then back, which makes Rust
            // blind to the lifetime of the original reference.
            Some(unsafe { &mut *(obj as *mut _) })
        } else {
            None
        }
    }
}