`cannot infer an appropriate lifetime for autoref due to conflicting requirements` but can't change anything due to trait definition constraints

Question

I was implementing linked lists by following along too many linked lists. When trying to implement iter_mut(), I did it myself and made the following code:

type Link<T> = Option<Box<Node<T>>>;

pub struct List<T> {
    head: Link<T>,
}

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut::<T>(&mut self.head)
    }
}

pub struct IterMut<'a,  T>(&'a mut Link<T>);

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next<'b>(&'b mut self) -> Option<&'a mut T> {
        self.0.as_mut().map(|node| {
            self.0 = &mut (**node).next;
            &mut (**node).elem
        })
    }
}

I am to avoiding coersions and elisions because being explicit lets me understand more.

Error:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/third.rs:24:16
   |
24 |         self.0.as_mut().map(|node| {
   |                ^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'b` as defined on the method body at 23:13...
  --> src/third.rs:23:13
   |
23 |     fn next<'b>(&'b mut self) -> Option<&'a mut T> {
   |             ^^
note: ...so that reference does not outlive borrowed content
  --> src/third.rs:24:9
   |
24 |         self.0.as_mut().map(|node| {
   |         ^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 20:6...
  --> src/third.rs:20:6
   |
20 | impl<'a, T> Iterator for IterMut<'a, T> {
   |      ^^
note: ...so that reference does not outlive borrowed content
  --> src/third.rs:25:22
   |
25 |             self.0 = &mut (**node).next;
   |                      ^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

For more information about this error, try `rustc --explain E0495`.

I have looked at Cannot infer an appropriate lifetime for autoref due to conflicting requirements.

I understand a bit but not much. The problem that I am facing here is that if I try to change anything, an error pops saying that can't match the trait definition.

My thought was that basically I need to state somehow that lifetime 'b outlives 'a i.e <'b : 'a> but I can't figure out how to do it. Also, I have similar functions to implement iter() which works fine. It confuses me why iter_mut() produces such errors.

Iter

type Link<T> = Option<Box<Node<T>>>;

pub struct Iter<'a, T>(&'a Link<T>);

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.as_ref().map(|node| {
            self.0 = &((**node).next);
            &((**node).elem)
        })
    }
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter::<T>(&self.head)
    }
}

☝️This works.

Eclat

No answers yet, but this question is almost identical to this one. – Insectivorous

@SCappella, yes that's almost the exact some problem. The issue is not to compile the code. I am mainly interested in understanding the error. @Vivek's answer does clear some doubts and the linked question's comments are helpful aswell but still can't completely understand the error message and why the same works wth iter() – Eclat

Answer 1

The key thing is that you need to be able to somehow extract an Option<&'a mut T> from a &'b mut IterMut<'a, T>.

To understand why IterMut<'a, T> := &'a mut Link<T> can't work, you need to understand what exactly you can do with a mutable reference. The answer, of course, is almost everything. You can copy data out of it, change its value, and lots of other things. The one thing you can't do is invalidate it. If you want to move the data under the mutable reference out, it has to be replaced with something of the same type (including lifetimes).

Inside the body of next, self is (essentially) &'b mut &'a mut Link<T>. Unless we know something about T (and we can't in this context), there's simply no way to produce something of type &'a mut Link<T> from this. For example, if this were possible in general, we'd be able to do

fn bad<'a, 'b, T>(_x: &'b mut &'a mut T) -> &'a mut T {
    todo!()
}

fn do_stuff<'a>(x: &'a mut i32, y: &'a mut i32) {
    // lots of stuff that only works if x and y don't alias
    *x = 13;
    *y = 42;
}

fn main() {
    let mut x: &mut i32 = &mut 0;
    let y: &mut i32 = {
        let z: &mut &mut i32 = &mut x;
        bad(z)
    };
    // `x` and `y` are aliasing mutable references
    // and we can use both at once!
    do_stuff(x, y);
}

(playground link)

The point is that if we were able to borrow something for a short (generic) lifetime 'b and return something that allowed modification during the longer lifetime 'a, we'd be able to use multiple short lifetimes (shorter than 'a and non-overlapping) to get multiple mutable references with the same lifetime 'a.

This also explains why the immutable version works. With immutable references, it's trivial to go from &'b &'a T to &'a T: just deference and copy the immutable reference. By contrast, mutable references don't implement Copy.

---

So if we can't produce a &'a mut Link<T> from a &'b mut &'a mut Link<T>, we certainly can't get an Option<&'a mut T out of it either (other than None). (Note that we can produce a &'b mut Link<T> and hence an Option<'b mut T>. That's what your code does right now.)

So what does work? Remember our goal is to be able to produce an Option<&'a mut T> from a &'b mut IterMut<'a, T>.

If we were able to produce a IterMut<'a, T> unconditionally, we'd be able to (temporarily) replace self with it and hence be able to directly access the IterMut<'a, T> associated to our list.

// This actually type-checks!
fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    let mut temp: IterMut<'a, T> = todo!(); // obviously this won't work
    std::mem::swap(&mut self.0, &mut temp.0);
    temp.0.as_mut().map(|node| {
        self.0 = &mut node.next;
        &mut node.elem
    })
}

(playground link)

The easiest way to set things up so that this all works is by transposing IterMut<'a, T> a bit. Rather than having the mutable reference outside the option, make it inside! Now you'll always be able to produce an IterMut<'a, T> with None!

struct IterMut<'a, T>(Option<&mut Box<Node<T>>>);

Translating next, we get

fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    let mut temp: IterMut<'a, T> = IterMut(None);
    std::mem::swap(&mut self.0, &mut temp.0);
    temp.0.map(|node| {
        self.0 = node.next.as_mut();
        &mut node.elem
    })
}

More idiomatically, we can use Option::take rather than std::mem::swap (This is mentioned earlier in Too Many Linked Lists).

fn next<'b>(&'b mut self) -> Option<&'a mut T> {
    self.0.take().map(|node| {
        self.0 = node.next.as_mut();
        &mut node.elem
    })
}

(playground link)

---

This actually ends up being slightly different than the implementation in Too Many Linked Lists. That implementation removes the double indirection of &mut Box<Node<T>> and replaces it with simply &mut Node<T>. However, I'm not sure how much you gain since that implementation still has a double deref in List::iter_mut and Iterator::next.

Insectivorous

That took long to understand. Super helpful. Thanks you cured my 2 day headache. – Eclat

Well I realise now that idea to specify 'b : 'a ('b outlives a) wasn't a bad one if the trait accepted it. if we change fn bad<'a, 'b, T>(_x: &'b mut &'a mut T) -> &'a mut T to fn bad<'a, 'b : 'a, T>(_x: &'b mut &'a mut T) -> &'a mut T then compiler would accept it. The example you gave is really helpful and I would suggest anyone who stumbles accross this problem to play around with it (changing mut refs to immut refs and etc) – Eclat

Answer 2

Rust is trying to say that you have a dangling reference.

self.0.as_mut() // value borrowed
self.0 = <> // underlying value changed here. 

The problem is the following definition:

pub struct IterMut<'a,  T>(&'a mut Link<T>)

This can't encapsulate that you will have a "empty" node meaning reached the end of the node.

Use the structure as mentioned in the book like:

pub struct IterMut<'a,  T>(Option<&'a mut Node<T>>);

This ensures that you can leave None in its place when you run end of list and use take to modify the IterMut content behind the scenes.

Blume

That makes sense to me. But then how come iter() works? It almost similar. There I borrow value as as_ref() and then assign to self.0 inside closure which works without any errors. Could you help me understand that? – Eclat