Fighting with the borrow checker - Understanding reference lifetime associated with match statement in rust

I've been trying to implement basic data structures in rust just to get the hang of how the borrow checker works, however while implementing a linked list I am running into a problem.

This is my code:

use std::cell::{Cell, RefCell};
use std::ptr::null;
use std::rc::Rc;

#[derive(Clone,Debug)]
pub struct ListNode {
    val: i32,
    next: Option<ListNodeRef>
}

type ListNodeRef = Rc<RefCell<ListNode>>;


pub fn GetNode(val: i32) -> ListNodeRef{
    Rc::new(RefCell::new(ListNode{ val, next: None}))
}

pub fn AddToList(head: &ListNodeRef, val: i32){
    let mut curr_head = head.borrow_mut();
    match &curr_head.next {
        Some(list_node) => {
            return AddToList(list_node, val);
        }
        None => {
            curr_head.next = Some(GetNode(val));
        }
    }
}

pub fn print_list(head: &ListNodeRef){
    let mut curr_node = head;
    while true {
        let temp = curr_node.borrow();
        println!("{}", temp.val);
        match temp.next {
            None =>{break;}
            Some(ref Node) => {curr_node = &Node}
        };
    }
}

Now I've been trying to implement the function which prints out the whole linked list, however I keep on getting the follow error:

What research have I done:

  1. Given I am using the Rc + RefCell in combination, getting an immutable value from it means calling the borrow function
  2. Since the next node is inside an option, hence have to pattern match it.

Now, given this is a reference I've also tried the following version(not using the ref pattern in match)

pub fn print_list(head: &ListNodeRef){
    let mut curr_node = head;
    while true {
        let temp = curr_node.borrow();
        println!("{}", temp.val);
        match &temp.next {
            None =>{break;}
            Some(Node) => {curr_node = &Node}
        };
    }
}

My questions:

  1. Why does it matter if temp does not live long enough? What use do we have for it after the pattern match?
  2. Wouldn't passing a reference to temp i.e &temp into the match statement solve the problem?
// error[E0597]: `temp` does not live long enough
// 18 |     let temp = curr_node.borrow(); // temp: Ref<'1, ListNode>
//    |         ---- binding `temp` declared here
// ...
// 25 |     match &temp.next {
//    |            ^^^^ borrowed value does not live long enough
// ...
// 29 | }
//    | -
//    | |
//    | `temp` dropped here while still borrowed
//    | borrow might be used here, when `temp` is dropped and runs the destructor for type `Ref<'_, ListNode>`
pub fn print_list(head: &ListNodeRef) {
    let mut curr_node = head; // curr_node: &'1 ListNodeRef
    
    // see the compiled deref_borrow fn below for explanation
    let temp = curr_node.borrow(); // temp: Ref<'1, ListNode>
    
    println!("{}", temp.val);
    // temp.next => (*Ref<'1, ListNode>).next
    //           => (*<Ref<'1, ListNode> as Deref>::deref(&'2 Ref<'1, ListNode>).next)
    //           => (*&'2 ListNode).next
    // ref node => &'_ (*&'2 ListNode).next => &'2 ListNodeRef
    // Note: the point is that '1 strictly outlives '2 (due to Deref::deref(&'any self) -> &'any T))
    //       '2 lives shorter than '1, thus the error
    match temp.next {
        None => (),
        Some(ref node) => curr_node = node, // node: &'2 ListNodeRef
    }; 
} // Ref<'1, ListNode> drops here

// `curr_node.borrow()`
//  1. Rc::deref(&'1 Rc<RefCell<ListNode>>) -> &'1 RefCell<ListNode>
//  2. RefCell::borrow(&'1 RefCell<ListNode>) -> Ref<'1, ListNode>
pub fn deref_borrow(head: &ListNodeRef) -> Ref<'_, ListNode> {
    let curr_node = head; // curr_node: &'1 ListNodeRef
    curr_node.borrow()
}

Rust Playground

P.S the while loop in OP doesn't influence lifetime analysis here, so I reduce it without the loop.

Another option is to write the function recursively to avoid the dangling pointer:

pub fn print_list(head: &ListNodeRef){
    let temp = head.borrow();
    println!("{}", temp.val);
    if let Some(node) = temp.next.as_ref() {
        print_list(node);
    }
}
1 Like

The Ref<'_, _> (temp) is the only thing giving you "permission" to look at the memory beyond it. You can think of it as a type of ReadGuard -- once you give up the guard, you give up access.

Due to how linked lists are designed, if you want to access the second member without cloning the Rcs, you need

  • Access to the head (a Ref to the head must be alive)
  • Access to the second member (a Ref to it must also be alive)

And more generally you need N Refs to be around in order to access the Nth member. It's the same problem discussed here.

Recursion such as @moy2010 demonstrated is one way to keep them all around; alternatively, you could clone the Rcs as you go (in which case you don't need to keep them around).


I believe the actual compiler error is because you're forcing the creation of a &'x Ref<'x, _> where 'x is the original lifetime of the Ref; i.e. forcing a Ref to be borrowed for the entirety of it's validity. That's incompatible with having a non-trivial destructor. It usually comes up with &mut or structs with invariant lifetime parameters, but here the assignment to the same variable is defeating covariance.

Sort of like this forces things by using the named lifetime.

(But the point about needing N Refs makes the details somewhat moot, since the design can't work as-is.)


Linked lists are a notoriously poor fit for the ownership and borrowing model, which is basically what the "too many linked lists" repo is about. You might want to read the whole thing.

3 Likes