Cannot mutably borrow immutable field, cannot borrow as mutable

Hi, I'm a beginner in rust.
When I implement a linked list. I have some problems.
Can someone debug for me ?
https://gist.github.com/anonymous/25e316fc7cfd981ddc372dbe44fe6144
Thank for your help.

First, for the lists there's a tutorial you've might have seen: Learning Rust With Entirely Too Many Linked Lists

As for references, you can't go from an immutable reference to a mutable one. Once you borrow something with &, then everything borrowed from that later has to be & as well. You can go from &mut to &mut or &, but not the other way.

There's a difference between mut p = &l and p = &mut l. The mut next to the variable means you can reassign the variable, or modify it when it owns a value. The &mut means it's a reference through which you can modify the reference's destination. It's sort of like const char *ptr vs char *const ptr in C.

In your code:

let mut p = &l;

That's a mutable p (so you can do p = &q; p = &r; p = &s) to immutable (read-only) l content, so while you can make it point anywhere, you can't modify anything in the things it points to.

For this particular error you need:

let mut p = &mut l;

Which allows changing where p points to, but also is a mutable reference, so also allows modifying the object it points to.

However, the whole loop needs more changes to look safe to the borrow checker. Lists are one particular example that is not a good fit for the borrow checker (see the article at the top of the post)

1 Like
  • Use owned values whenever you can. Mutable references are the most limited kind in the language, since they require to be exclusive and require the object to remain completely valid at all times (not easy with lists when you manipulate next pointer, which makes it temporarily invalid). Here you want to destroy one list and build another, so you can take ownership of nodes you're destroying.

  • There are many helper methods to make use of Option easier.

I got it a bit further, but still stuck :slight_smile: The problematic line is q = &mut q.next, and to be honest I'm not sure why it doesn't pass:

@kornel

I tried to run your code "Rust Playground" but it raise more many new errors.

cannot borrow q.0 as mutable more than once at a time

Here's the solution I was able to come up with:

1 Like

Yes, that's because it's an approach that the borrow checker doesn't understand. C-like approach with loops, and multiple mutable references is generally difficult to prove to be safe. More functional programming style is a better fit for the borrow checker.

In cases like this a change of approach is needed. I've posted another answer which uses recursion, and some extra methods of Option to limit where references are active. The code is much shorter, although may be hard to understand if you're not familiar with these methods.

Yes. Thank you for your help. I'll try to find out more. :smiley:

OK, I've made it simpler:

Another trick is to use a separate match that returns a primitive or owned value, and changing references later, instead of trying to do too much inside a single match that makes references mixed up.

1 Like

I think another option, along your original lines, is the following (replacing the match statement):

if node.value != k {                        
    if q.is_none() {
         *q = Some(node);
    } else {
          q.as_mut().map(|n| n.next = Some(node));
      }
}
1 Like

@vitalyd
I tried your solution and it worked. Can you explain me why that when I use:

    match *q
    {
        Some(ref mut node1) =>
        {
            node1.next = value;
            q = &mut node1.next;
        },
        None => {}
    }

It cause the error:

error[E0499]: cannot borrow `q.0` as mutable more than once at a time
  --> removeKFromList.rs:40:34
   |
40 |                             Some(ref mut node1) =>
   |                                  ^^^^^^^^^^^^^
   |                                  |
   |                                  second mutable borrow occurs here
   |                                  first mutable borrow occurs here
...
63 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `q` because it is borrowed
  --> removeKFromList.rs:43:33
   |
40 |                             Some(ref mut node1) =>
   |                                  ------------- borrow of `q` occurs here
...
43 |                                 q = &mut node1.next;
   |                                 ^^^^^^^^^^^^^^^^^^^ assignment to borrowed `q` occurs here

error: aborting due to previous error(s)

The borrow of q lasts for the entire match statement there. The explicit is_none if/else approach keeps the borrows confined to the respective if/else blocks. Using map (and other functional approaches, as @kornel mentioned) also helps because they help in keeping borrow scope confined. Otherwise, it's easy to run into non-lexical borrow and other borrow scoping issues.

I still can't understand why it has cannot mutably borrow field of immutable binding error as image below @@
image
a is mutable; so a.next; so a.next.take() should work as expected?

a is an Rc<Node<T>> - an Rc only gives you an immutable reference to the inner value. The fact that a binding is mutable doesn't matter. take() needs a &mut self borrow of the Option, which you can't get from an Rc. You can try using Rc<RefCell<Node<T>>> instead, and then borrow the interior node mutably dynamically.

1 Like