Lifetime problem: Cons List with "&mut" field

help
1 
enum List<'a,T:'a> {
    Cons(T, &'a mut List<'a,T>),
    Nil,
}

use List::{Cons, Nil};

fn main() {
let mut c0=Nil;
let mut c1=Cons(3,&mut c0);
let mut c2=Cons(2,&mut c1);
let mut c3=Cons(1,&mut c2);
}

===========================================
   Compiling playground v0.0.1 (file:///playground)
error[E0597]: `c1` does not live long enough
  --> src/main.rs:13:1
   |
11 | let mut c2=Cons(2,&mut c1);
   |                        -- borrow occurs here
12 | let mut c3=Cons(1,&mut c2);
13 | }
   | ^ `c1` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `c2` does not live long enough
  --> src/main.rs:13:1
....
....
=============================================

Who still borrow c1?
Is there a way works with "&mut List" field?

2

This situation is covered in chapter 5 of "Learning Rust With Entirely Too Many Linked Lists". Check out the whole book if you haven't already.

I think the problem is that since List<'a, T> is parameterized by only one lifetime, there is not enough information to check that nodes are dropped in order from tail to head. For a linked list of n nodes you would need n distinct lifetimes, but instead all the references in this list have the same lifetime 'a.

A pointer could work, or any of the other approaches in the link.

enum List<T> {
    Cons(T, *mut List<T>),
    Nil,
}
2 Likes
3

*mut is raw pointer, it is unsafe to use it.

4

When your type contains a mutable reference, the type becomes invariant over the lifetime of that reference ('a in this particular case). That means your type has to live for exactly the same lifetime as the reference.

In your example, every time you create a new Cons you extend the borrow of the Cons mutable reference you gave. The net effect here becomes that c1, c2, c3 all have to live for the exact same lifetime, which isn't true.

As @dtolnay mentioned, the "too many linked lists" book is a good read on how to create linked lists. If you're just starting out with Rust, I suggest you hold off on writing one of these :slight_smile:.

1 Like