How can I fix “cannot infer an appropriate lifetime for autoref” when implementing an iterator that returns mutable references?

Question

I'm trying to write a mutable iterator for a linked list called Thread where each element implements Block.

trait Block<'a> {
    fn next(&mut self) -> Option<&'a mut (dyn Block<'a> + 'a)> {
        None
    }
}

pub struct Thread<'a> {
    head: Box<dyn Block<'a> + 'a>,
}

impl<'a> Thread<'a> {
    fn iter_mut(&mut self) -> ThreadIterator<'a> {
        ThreadIterator {
            next: Some(self.head.as_mut()),
        }
    }
}

pub struct ThreadIterator<'a> {
    next: Option<&'a mut (dyn Block<'a> + 'a)>,
}

impl<'a> Iterator for ThreadIterator<'a> {
    type Item = &'a mut (dyn Block<'a> + 'a);

    fn next(&mut self) -> Option<&'a mut (dyn Block<'a> + 'a)> {
        self.next.take().map(|mut block| {
            self.next = block.next();
            block
        })
    }
}

Compiling this will output the error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:14:34
   |
14 |             next: Some(self.head.as_mut()),
   |                                  ^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 12:5...
  --> src/lib.rs:12:5
   |
12 | /     fn iter_mut(&mut self) -> ThreadIterator<'a> {
13 | |         ThreadIterator {
14 | |             next: Some(self.head.as_mut()),
15 | |         }
16 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:14:24
   |
14 |             next: Some(self.head.as_mut()),
   |                        ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 11:6...
  --> src/lib.rs:11:6
   |
11 | impl<'a> Thread<'a> {
   |      ^^
note: ...so that the types are compatible
  --> src/lib.rs:14:24
   |
14 |             next: Some(self.head.as_mut()),
   |                        ^^^^^^^^^^^^^^^^^^
   = note: expected `dyn Block<'_>`
              found `dyn Block<'a>`

This is why I need the 'a requirement for all Blocks (they are borrowing a Runtime):

struct Runtime {}

struct ExampleBlock<'a> {
    runtime: &'a Runtime,
    next: Box<dyn Block<'a> + 'a>,
}

impl<'a> Block<'a> for ExampleBlock<'a> {
    fn next(&mut self) -> Option<&'a mut (dyn Block<'a> + 'a)> {
        Some(self.next.as_mut())
    }
}

The first thing I tried was removing the mutable requirement from all references. Same errors.

I think the error is telling me that self.head.as_mut() is outliving self.head, so I must ensure that the lifetime of that reference is shorter than Thread<'a>. I thought I fulfilled this requirement with the 'a lifetime for ThreadIterator<'a>. In other words, you can't possibly drop Thread before ThreadIterator, right?

Edit:

I changed Block to a struct to simplify the code, though I need it to be a trait in the end.

struct Block {}

impl<'a> Block {
    fn next(&mut self) -> Option<&'a mut Block> {
        None
    }
}

pub struct Thread {
    head: Block,
}

impl<'a> Thread {
    fn iter_mut(&mut self) -> ThreadIterator<'a> {
        ThreadIterator {
            next: Some(&mut self.head),
        }
    }
}

pub struct ThreadIterator<'a> {
    next: Option<&'a mut Block>,
}

impl<'a> Iterator for ThreadIterator<'a> {
    type Item = &'a mut Block;

    fn next(&mut self) -> Option<&'a mut Block> {
        self.next.take().map(|mut block| {
            self.next = block.next();
            block
        })
    }
}

It is based off of https://rust-unofficial.github.io/too-many-lists/second-iter-mut.html.

The answer to `cannot infer an appropriate lifetime for autoref due to conflicting requirements` but can't change anything due to trait definition constraints was to introduce a Option for the iterator, which I have done. Lifetime parameter problem in custom iterator over mutable references and Reimplementation of LinkedList: IterMut not compiling didn't answer my question, though I have a hard time connecting my code to theirs.

I finally found something that does work:

pub struct Block {}

impl<'a> Block {
    fn next(&mut self) -> Option<&'a mut Block> {
        None
    }
}

pub struct Thread {
    head: Block,
}

impl Thread {
    fn iter_mut(&mut self) -> ThreadIterator<'_> { // The lifetime here is changed
        ThreadIterator {
            next: Some(&mut self.head),
        }
    }
}

pub struct ThreadIterator<'a> {
    next: Option<&'a mut Block>,
}

impl<'a> Iterator for ThreadIterator<'a> {
    type Item = &'a mut Block;

    fn next(&mut self) -> Option<&'a mut Block> {
        self.next.take().map(|mut block| {
            self.next = block.next();
            block
        })
    }
}

I'm having a hard time applying this to the original code, because there might be two different lifetimes, one for the iterator and one for the trait.

Answer 1

Answered by u/quixotrykd/:

The compiler seems to be choking here because it doesn't know how the lifetime on &mut self and ThreadIterator relate. As such, it has no way to guarantee that &mut self lives at least as long as the underlying borrow in ThreadIterator. Looking at your code here, that would be line 12 (note I've fixed your mistake in the above link).

You need to tell the compiler that the lifetime on the output ThreadIterator is the same as the input &mut self (or technically that it lasts at least as long, though you very likely want the same lifetime here), otherwise the compiler has no way to ensure that the "self" that's borrowed by &mut self stick around as long as the ThreadIterator's borrow. Looking at the rules for lifetime elision here, we can see that this doesn't apply to your code, and as such, you need to manually specify the lifetime on &mut self (otherwise it generates another, unrelated, anonymous lifetime, as indicated in the compiler's error message).

The fixed code:

pub trait Block<'a> { // Make public to resolve unrelated error
    fn next(&mut self) -> Option<&'a mut (dyn Block<'a> + 'a)> {
        None
    }
}

pub struct Thread<'a> {
    head: Box<dyn Block<'a> + 'a>,
}

impl<'a> Thread<'a> {
    fn iter_mut(&'a mut self) -> ThreadIterator<'a> { // Add lifetime to &self
        ThreadIterator {
            next: Some(self.head.as_mut()),
        }
    }
}

pub struct ThreadIterator<'a> {
    next: Option<&'a mut (dyn Block<'a> + 'a)>,
}

impl<'a> Iterator for ThreadIterator<'a> {
    type Item = &'a mut (dyn Block<'a> + 'a);

    fn next(&mut self) -> Option<&'a mut (dyn Block<'a> + 'a)> {
        self.next.take().map(|mut block| {
            self.next = block.next();
            block
        })
    }
}