Understanding Borrow checker

#1

I started using Rust a month ago and I’m still trying to understand nuances of borrow checker. Here’s the error Im getting

error[E0502]: cannot borrow `graph` as mutable because it is also borrowed as immutable
  --> src/main.rs:50:9
   |
47 |         let source = graph.get_node_by_value("source").unwrap();
   |                      ----- immutable borrow occurs here
...
50 |         graph.add_node("destination".to_string());
   |         ^^^^^ mutable borrow occurs here
51 |     }
   |     - immutable borrow ends here

I dont understand why the immutable borrow on line 47 ends AFTER line 51? Shouldn’t get_node_by_value release the immutable borrow right after? Because it is done immutably borrowing it.

0 Likes

#2

Could you please provide more code? There aren’t enough braces here to properly understand why the compiler is mad.


But if the two lines of code in the error message are in the same scope, and I use some inferences as to what’s going on then here’s the problem:

<graph's type>::get_node_by_value(&str)

returns Option<&T> (Or Result<T, ?>) which is .unwrap()ed and then put into source.
This means that there will be an immutable reference to T in source and therefore graph cannot be mutated. Rust guarantees that a &T's underlying value will not change and therefore it can’t guarantee that <graph's type>::add_node(String) will not mutate the underlying T

0 Likes

#3

Someone actually had the exact same question before: https://stackoverflow.com/questions/47618823/cannot-borrow-as-mutable-because-it-is-also-borrowed-as-immutable

The short answer is that source seems to be of a type that keeps a reference to the underlying graph (which makes sense if it is a node of the graph). So you cannot modify the graph as long as that node is in scope (which only goes out of scope at line 51).

0 Likes

#4

Borrows go out of scope in the reverse of the order they’re brought into scope. This makes sense in general, but can be frustrating when to you it’s obvious that you no longer need a borrow that’s in scope.

I believe the problem of a borrow existing longer than expected is being fixed. http://smallcultfollowing.com/babysteps/blog/2016/04/27/non-lexical-lifetimes-introduction/#problem-case-1-references-assigned-into-a-variable

0 Likes

#5

Thanks, all. Im clear now. but how about cases where a method takes a mut reference but return something not tied to reference? Say it returns Ok
Will that be too hard for compilers to figure out?

0 Likes

#6

In the link I shared, the method takes an &mut reference and returns nothing. It just alters the referent directly. The problem still occurs.


However, the borrow checker is already a bit smarter about methods.

thing.do_mutable_thing_to_self() shouldn’t prevent you from using thing again.


The issue with your example is still that the method on the graph has a value with a mutable reference.


A good pattern (in some cases at least) for building graphs is to not use pointers/references directly, but to stuff all the nodes in a vector and have the nodes refer to each other by index into that vector.

1 Like

#7

Hard to say without reading the rest of the code, but if you are using the 2018 edition, NLL should prevent your error … unless your code does something like this:

struct Graph<'a> { // the struct contains a lifetime
 // ...
}

impl<'a> Graph<'a> {
    fn get_node_by_value (&'a self, &'a str) -> Option<&'a String>
    {
        // ...
    }

    fn add_node (&'a mut self, String)
    {
    // ...
    }
}

If that is the case (this is a long shot!), then the problem comes from the defined methods taking the lifetime parameter 'a of the struct, which is 99.9% of the time not what you want.

Change your code to look like the following

struct Graph<'graph> { // Do not name a struct's lifetime 'a to prevent the confusion
 // ...
}

impl<'graph> Graph<'graph> {
    fn get_node_by_value (&'_ self, &'_ str) -> Option<&'_ String>
    {
        // ...
    }

    fn add_node (&'_ mut self, node: String)
    {
    // ...
    }
}
1 Like

#8

The code snippet in the OP is not my code. I copied it from the link @dthul shared (you must be a full-time web crawler…jk) . But I got answers to my question and also thanks for suggesting how to work with Graphs. Cheers!!

0 Likes

#9

Never seen '_ before. Looks something new in Rust 2018.

0 Likes

#10

Indeed! https://doc.rust-lang.org/nightly/edition-guide/rust-2018/ownership-and-lifetimes/the-anonymous-lifetime.html

2 Likes

#11

Yeah, it is as @yandros posted, but I’d be careful about using it multiple times, as because it doesn’t have a name, it can be confusing to follow. For example what was previously posted

fn get_node_by_value (&'_ self, &'_ str) -> Option<&'_ String>
{
    // ...
}

Could really just be explained as

fn get_node_by_value<'a> (&'a self, &'a str) -> Option<&'a String>

So, really what the '_ was doing was just replacing a new lifetime parameter from being declared.

0 Likes

#12

That’s not the desugaring you’re looking for.

It’s actually

fn get_node_by_value<'a, 'b> (&'a self, &'b str) -> Option<&'a String>

https://doc.rust-lang.org/nightly/nomicon/lifetime-elision.html

0 Likes

#13

Yep. what '_ really does is show the “holes” where lifetime ellision may happen.

An example to show why this is a good idea (or why implicit lifetime parameters was not):

Imagine you have the following code:

trait Compiler
{
    fn compile (
        self: &mut Self,
        program: &str,
    ) -> Ast
    {
        let tokens = self.tokenize(program);
        let ast = self.lift(tokens);
        let ast = self.const_propagate(ast);
        ast
    }

    fn tokenize (
        self: &mut Self,
        program: &str,
    ) -> Vec<Token>;
    
    fn lift (
        self: &mut Self,
        tokens: Vec<Token>,
    ) -> Ast;
    
    fn const_propagate (
        self: &mut Self,
        ast: Ast,
    ) -> Ast;
}
  1. with:

    type Token = String; // No lifetime parameters
    
    type Ast = ...       // idem
    

    It does compile.

  2. But when refactored to:

    //! Avoid String allocations
    
    type Token<'program> = &'program str;
    
    type Ast<'program> = ...
    
    

    Then, obviously, the code does not compile (no surprise there, the change is not small), but what is puzzling is the error message we then get:

    • error[E0499]: cannot borrow `*self` as mutable more than once at a time
        --> src/lib.rs:26:19
         |
      25 |         let tokens = self.tokenize(program);
         |                      ---- first mutable borrow occurs here
      26 |         let ast = self.lift(tokens);
         |                   ^^^^      ------ first borrow later used here
         |                   |
         |                   second mutable borrow occurs here
      

This is something very classical when wrong lifetimes are involved. You don’t get an error ar the “definition site” but at the caller site.

Let’s look at Compiler::tokenize then, but this time with “explicit holes”

impl Compiler {
    // ...
    fn tokenize (
        self: &'_ mut Self,
        program: &'_ str,
    ) -> Vec< Token<'_> >;

Ahah! Now we do see the “output hole” which means that lifetime ellision was kicking in, in the following manner:

impl Compiler {
    // ...
    fn tokenize<'compiler, 'program> (
        self: &'compiler mut Self,
        program: &'program str,
    ) -> Vec< Token<'compiler> >;

Which, thanks to naming lifetimes with actual explicit names, shows that we are getting Token<'compiler> instead of Token<'program> as was our intent in 2. We have found the problem, but not really thanks to borrowck obscure error:

  • If Rust had linted against the lack of a lifetime parameter in the type Vec<Token> (and Ast) before displaying other borrowck errors, fixing this compiler error would have been easier, specially for beginners.
1 Like