More Rust problems (and a sketch of a solution)

September 11, 2016 - Tagged as: en, rust.

It’s a nice coincidence that after a good productive weekend of Rust hacking I saw this blog post about why the author is dropping Rust. I’ve been doing a lot of Rust programming lately (I have at least 3 programs –not libraries– that I’m hoping to publish in the near future), and I’m surprised to see that no one mentioned in the discussion threads about this blog post what IMHO is one of the most annoying problems with Rust.

Borrow checker rejects some programs that are perfectly valid in other languages, and by itself this isn’t a problem. Similar things happen in all languages ¹. One of the first problems I encountered after started to write Rust was the OP’s second problem, namely, cyclic data structures (or graphs, but more specifically, widgets with parent/child relations). However, there is at least one pretty good solution for this, and all you need is to think harder and experiment with alternative designs. I’m actually very happy with my solution to this (which is also discovered independently by many people, for an example, see petgraph).

However, there are problems that basically can’t be solved in Rust without paying some runtime costs or using bad practices. See my previous blog post for some examples. In this post I’m going to show another, and more annoying, problem.

self borrows all of its fields

This is a problem that happened in pretty much every single Rust program I’ve ever written. In a method, you can’t borrow some fields, and call another &mut self method. This is because methods borrow the whole self, so you get an error saying that you can’t borrow self twice.

As an example, imagine writing a compiler. For some reason you want to collect all the variables defined in a scope, and then generate fresh variables for those. You may do something like this:

struct FreshGen { /* abstract */ }

struct Var { /* abstract */ }

impl FreshGen {
    fn fresh(&mut self) -> Var {
        unimplemented!()
    }
}

struct Compiler {
    fresh_gen: FreshGen,
    vars_in_scope: Vec<Var>,
}

impl Compiler {
    fn fresh(&mut self) -> Var {
        self.fresh_gen.fresh()
    }

    fn gen_locals(&mut self) {
        let mut fresh_vars = vec![];
        for var in self.vars_in_scope.iter() {
            fresh_vars.push(self.fresh());
        }
        // use fresh_vars
    }
}

Can you see any problems here? When I compile this with nightly 11/9/2016, I get this annoying error message:

error[E0502]: cannot borrow `*self` as mutable because `self.vars_in_scope` is also borrowed as immutable
  --> <anon>:24:29
   |
23 |         for var in self.vars_in_scope.iter() {
   |                    ------------------ immutable borrow occurs here
24 |             fresh_vars.push(self.fresh());
   |                             ^^^^ mutable borrow occurs here
25 |         }
   |         - immutable borrow ends here

So basically, self.vars_in_scope is borrowed from self, and then self.fresh() is called while vars_in_scope is still borrowed. Even though self.fresh() doesn’t have anything to do with self.vars_in_scope, this is not allowed because the compiler simply doesn’t care about what pieces of self methods actually borrow. For me this is probably the #1 most annoying problem with Rust.

Now, I believe this problem is solvable. I imagine an algorithm like this:

It works in two steps.

1. We generate, for every method, borrow sets. A borrow set is a set of fields that are, at some point in the method, borrowed from self.

2. For every method call statement in every method, we look at intersections of currently borrowed fields and the borrow set of callee (i.e. (1) for the method being called).

(1) works like this:

workset = set of all methods
caller-graph = graph of all methods, with edges from callees to callers

# initially none of methods borrow any fields
for method in methods:
    method.borrows = empty set

while workset is not empty:
    work = workset.pop()
    for statement in work.statements:
        for field in self.borrowed_at(statement):
            if not work.borrows.contains(field):
                work.borrows.insert(field)
                for caller in caller-graph[work]:
                    workset.insert(caller)

For a statement that has a method call, borrowed_at() returns the borrow set of the method being called. So when we update borrow set of a method, we add its callers to the workset and borrowed_at() will return more variables next time, propagating the information in the graph from callees to callers.

Now, for the second step, we first need to generate “live ranges” of borrowed fields. Assume that they’re generated.

for method in methods:
    for borrowed_field in method.borrows():
        for field_live_range in borrowed_field.live_ranges():
            # for methods called in the range
            for method in method_calls(field_live_range):
                if method.borrows().contains(borrowed_field):
                    error("can't borrow twice")

I sketched this in 30 minutes so I don’t expect this to work perfectly. Also, 4-level nested for loops look scary! But this is just to give an idea of how this might be solved.

In the example I showed above, borrow set of fresh would be {fresh_gen}, and borrow set of gen_locals would be {vars_in_scope, fresh_gen}. Now we look at live ranges of variables borrowed from self in gen_locals.

• vars_in_scope lives between lines 2-4 in the method.
• fresh_gen lives in line 3 in the method.

Since each variable has only one live range here, clearly there won’t be any intersections. So this would pass the borrow checker.

If fresh was also borrowing vars_in_scope, we’d get an error because vars_in_scope would now have two “live ranges”: between lines 2-4 as before, and in line 3. Since those intersect, we get an error.

(Again, this is a very quick sketch, so let me know if I’m missing something.)