Borrow checker vs singly linked list

help
1

I'm looking for help with this small experiment that I'm trying. Basically, I was trying to write some routines to go with the Cons List example from: Box<T> Points to Data on the Heap and Has a Known Size - The Rust Programming Language
and I ran into trouble with the borrow checker. (My goal here is to learn and experiment thus the fact that vectors are often more appropriate than linked lists or that there is actually a linked list implementation in the standard library or crate.io is not important.)

So I have this List struct for which I created a size() routine that counts the number of elements. Then I tried to make an add_recursive() routine that adds to the end of the list (yes, inefficiently, I know). What I'm struggling with is why the recursive add works fine but the non-recursive fails to compile.

enum List {
    Link(i32, Box<List>),
    Nil,
}

impl List {
    fn size(&self) -> u32 {
        let mut cnt = 0;
        let mut x = self;
        while let List::Link(_val, next) = x {
            cnt += 1;
            x = next;
        }
        cnt
    }

fn add_recursive(&mut self, val : i32) {
    match self {
        List::Link(_, next) => {
            next.add_recursive(val)
        },
        List::Nil => {
            *self = List::Link(val, Box::new(List::Nil));
        }
    }
}

pub fn go() {
    let mut l = List::Nil;
    println!("size={}, {:?}", l.size(), l);
    l.add_recursive(1);
    l.add_recursive(2);
    l.add_recursive(3);
    l.add_recursive(4);
    println!("size={}, {:?}", l.size(), l);
}

So that works great so far... here's the problem: I haven't figured out a way to make this non-recursive "add" compile. And it's not clear why the compiler is happy with the recursive form and not this one.

fn add2(&mut self, val : i32) {
    let mut x = self;
    while let List::Link(_val, next) = x {
        x = next;
    }
    *x = List::Link(val, Box::new(List::Nil));
}

error[E0499]: cannot borrow `x.1` as mutable more than once at a time
   --> src/main.rs:781:40
|
781 |             while let List::Link(_val, next) = x {
|                                        ^^^^ mutable borrow starts here in previous iteration of loop
...
785 |         }
|         - mutable borrow ends here

error[E0506]: cannot assign to `x` because it is borrowed
   --> src/main.rs:782:17
|
781 |             while let List::Link(_val, next) = x {
|                                  ---- borrow of `x` occurs here
782 |                 x = next;
|                 ^^^^^^^^ assignment to borrowed `x` occurs here

error: aborting due to 2 previous errors

Thanks in advance!

2

This is an annoying part of the current borrowck algorithm - it borrows lexically and doesn't see that x's borrow terminates inside the loop (and thus the assignment is safe).

The good news is the NLL (non-lexical lifetimes) feature (which should hopefully be released later this year) fixes it: play

1 Like
3

Ah! I had somehow convinced myself that NLL had dropped quite a while ago. Do you happen to know if it's in nightly?

I'm trying to think of ways that I could add curly brace blocks to avoid the problem but it seems that the issue is intrinsic to the destructuring done by the "white let" (or "if let" if I replace the while with a loop). I guess I can check for a link and then just directly reference the fields.

Thanks!

4

Yes, you can experiment with NLL using #![feature(nll)] on the nightly channel.

1 Like
5

Yeah, this is intrinsic AFAIK. Personally, I’d use a bit of unsafe code (raw ptrs) there to get around it.

1 Like