HELP: Borrow checking problem with custom linked list type

[Gonkalbell]

To get some practice with rust, I'm writing a singly linked list that inserts new items in sorted order. I'm currently getting a borrow checking error in my insert function, that I haven't been able to figure out. Here's the code in question:

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

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

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

impl<T> LL<T>
where
    T: PartialOrd + std::fmt::Debug,
{
    // ...

    pub fn insert(&mut self, data: T) {
        let mut link: &mut Link<T> = &mut self.head;

        while let Some(node) = link {
            if node.data > data {
                // This works if I assign link to something here, but I don't know what to assign it to so link will be unchanged for this iteration
                // break;
            }
            link = &mut node.next;
        }

        *link = Some(Box::new(Node { data, next: link.take() }));
    }
}

If I comment out that break; statement, I get this error:

error[E0506]: cannot assign to `*link` because it is borrowed
  --> src/lib.rs:32:9
   |
25 |         while let Some(node) = link {
   |                        ---- borrow of `*link` occurs here
...
32 |         *link = Some(Box::new(Node { data, next: None }));
   |         ^^^^^
   |         |
   |         assignment to borrowed `*link` occurs here
   |         borrow later used here

I can get it to compile by moving this link = &mut node.next; statement above the if statement, but that's not the behavior I want for this function. What I want is for the value of link to be unchanged if it's time to break out of the loop, but I'm not sure how to do that.

Edit: forgot to assign the next pointer on the new node

[mbrubeck]

This is a known limitation of the current borrow checker. The next-generation borrow checker Polonius will be able to compile this code successfully. You can try the experimental version in the nightly toolchain by compiling with rustc -Z polonius.

For now, you could work around this issue by using raw pointers instead of references in your loop. (There might also be an alternative that works in safe Rust, but I haven't found one yet.)

[mbrubeck]

Here's a workaround in safe Rust, inspired by @rschoon's answer to this previous question:

pub fn insert(&mut self, data: T) {
    let mut link: &mut Link<T> = &mut self.head;

    while let Some(node) = link {
        if node.data > data {
            break;
        }
        link = &mut link.as_mut().unwrap().next;
    }

    *link = Some(Box::new(Node { data, next: None }));
}