How to get the below code compiled?

[LMJW]

I was trying to implement pop tail function but can't find an easy way to get it compiled

Can someone suggest a way to compile it? Basically I want to use ptr to check if this node is the tail node in linked list

Thanks in advance

pub type LLNODE<T: std::cmp::Ord> = Box<Node<T>>;

#[derive(Debug)]
pub struct LinkedList<T> {
    head: Option<LLNODE<T>>,
}
#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Option<LLNODE<T>>,
}

impl<T: std::cmp::Ord> LinkedList<T> {
    // push the value to the tail
    pub fn push_tail(&mut self, value: T) {
        let mut cur = &mut self.head;
        while let Some(inner) = cur {
            cur = &mut inner.next;
        }
        *cur = Some(Box::new(Node::new(value)));
    }

    pub fn pop_tail(&mut self) -> Option<T> {
        let mut ptr = &mut self.head;

        while let Some(inner) = ptr {
            if inner.next.is_some() {
                ptr = &mut inner.next;
            } else {
                break;
            }
        }

        let mut ret = None;
        //! Fail to compile here due to borrowed twice for ptr
        //! Not aware any easy fix on this
        std::mem::swap(ptr, &mut ret);
        ret.map(|v| v.data)
    }

}

impl<T> Node<T> {
    pub fn new(data: T) -> Self {
        Self { data, next: None }
    }
}

[steffahn]

Limitations of the borrow checker like these can often be overcome by conditionally “re-tracing” the path into a borrow that is only conditionally further used.

The compiler sees some kind of dependency here due to the fact that:

• inner depends on ptr, and
• ptr conditionally gets set to something depending on inner

without trying to fully go into any more detailed analysis of how exactly the borrow checker thinks about the lifetimes involved here, the main point is that inner is used unconditionally in the if statement

if inner.next.is_some() {
    ptr = &mut inner.next;
} else {
    break;
}

and the conditional assignment still influences the lifetime of inner even if the else branch is taken, so after leaving the else branch and the while loop with break, the mutable reference that lived in inner is still considered alive.

Long story short: rewriting the ptr = &mut inner.next into something no longer depending on inner fixes the problem

if inner.next.is_some() {
    ptr = &mut ptr.as_mut().unwrap().next; // conditionally re-tracing 
                                           // the path from `ptr` to `inner`
} else {
    break;
}

the unwrap here can’t fail because we already are in the while let Some(inner) = ptr loop that checked ptr to be Some, and thus there’s a good chance that the compile can optimize away the whole unwrap() call anyway

The above change removed the dependency of ptr on inner, which means that inner can be more short-lived and you can access ptr again after the loop.

---

Note that your original code not compiling is part of a known limitation of the borrow checker that will most likely get fixed eventually (i.e. maybe in a few years or so) with the new borrow checker “polonius” when that becomes part of standard rust. You can see it already compile on nightly with the unstable -Z polonius option here:

Compiler Explorer - Rust (rustc nightly)

[LMJW]

Thanks a lot for the detail explaination! Very insightful!