Cannot convert this tail recursive function into an iterative one due to lifetime error

[EFanZh]

Rust version: 1.37.0

This problem has been previously discussed on Stack Overflow and Rust Users Forum. And I think it is something the Rust compiler can improve on.

I was writing a function that remove the last node from a singly linked list:

struct Node<T> {
    value: T,
    next: Option<Box<Self>>,
}

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

fn remove_last_node_recursive<T>(node_ref: &mut List<T>) {
    let next_ref = &mut node_ref.as_mut().unwrap().next;

    if next_ref.is_some() {
        remove_last_node_recursive(next_ref);
    } else {
        *node_ref = None;
    }
}

Since the recursive call in the function is a tail call, I want to convert the function into an equivalent iterative one:

fn remove_last_node_iterative<T>(mut node_ref: &mut List<T>) {
    loop {
        let next_ref = &mut node_ref.as_mut().unwrap().next;

        if next_ref.is_some() {
            node_ref = next_ref;
        } else {
            break;
        }
    }

    *node_ref = None; // This line causes lifetime error.
}

The function above does not work due to lifetime error:

error[E0506]: cannot assign to `*node_ref` because it is borrowed
  --> src/main.rs:29:5
   |
18 | fn remove_last_node_iterative<T>(mut node_ref: &mut List<T>) {
   |                                                - let's call the lifetime of this reference `'1`
19 |     loop {
20 |         let next_ref = &mut node_ref.as_mut().unwrap().next;
   |                             -----------------
   |                             |
   |                             borrow of `*node_ref` occurs here
   |                             argument requires that `*node_ref` is borrowed for `'1`
...
29 |     *node_ref = None; // This line causes lifetime error.
   |     ^^^^^^^^^ assignment to borrowed `*node_ref` occurs here

I think I should be able to convert any valid tail recursive function into an equivalent iterative one without lifetime errors.

[andreytkachenko]

I think truth is on the compiler side, you just need to do some reborrow:

fn remove_last_node_iterative<T>(node_ref: &mut List<T>) {
    let mut current_ref = &mut *node_ref;
    
    loop {
        let next_ref = &mut current_ref.as_mut().unwrap().next;

        if next_ref.is_some() {
            current_ref = next_ref;
        } else {
            break;
        }
    }

    *node_ref = None; // This line causes lifetime error.
}

[EFanZh]

@andreytkachenko Your code sets node_ref which always points to the first node since you have changed the loop variable to current_ref. So instead of removing the last node, your code will clear the entire list.

[andreytkachenko]

@EFanZh Yep you right.

[EFanZh]

It seem that my iterative code actually works with nightly Rust with -Zpolonius option (https://users.rust-lang.org/t/how-do-you-remove-the-last-node-from-a-singly-linked-list/31805/7?u=efanzh). So I am closing this issue.