osa1 feed

Rust borrow checker woes

March 28, 2016 - Tagged as: en, rust.

I’ve been doing some Rust hacking in my free time, and unfortunately while it’s way, way better than how it was when I first tried it (around 0.4 or 0.6 IIRC), it still has some problems that encourage redundant runtime operations or bad programming practices. In this post I’ll give three examples that are all caused by dumb borrow checker. As you’ll see, in all cases the cost is either bad programming practices or runtime costs (which is really ironic, given that one of the design goals of Rust is performance).

1. No local reasoning about borrowing rules of constructors

It’s types that borrow, not values, and that makes sense. If you have an Option<&'a T> where 'a is coming from some other variable x, 1) x needs to live longer than this Option value 2) you can’t borrow x mutably while keeping the Option in scope (or the other way around, you can’t borrow Option mutably while keeping x in scope).

This makes sense because in compile time, given an Option<&'a T>, you can’t make any assumptions on Option’s actual value. Since Some constructor of the Option type will borrow the T here, you just have to assume that values of this type always borrow T (and that’s why we have &'a in the type).

The problem is that it’s sometimes possible to do some local reasoning, and not doing that is too restrictive. Suppose you have this:

struct ListOfThings {
    list : Vec<Thing>,
}

struct Thing {
    name : String,
    // other fields here -- this is expensive to copy!
}

impl Thing {
    fn do_something(&mut self) {}
}

impl ListOfThings {
    fn do_something(&mut self, name : &str) {
        match self.find_thing_mut(name) {
            None => {
                self.init_thing(name.to_owned());
                self.do_something(name)
            },
            Some(t) => {
                t.do_something()
            },
        }
    }

    fn find_thing_mut<'a>(&'a mut self, name : &str) -> Option<&'a mut Thing> {
        self.list.iter_mut().find(|t| t.name.as_str() == name)
    }

    fn init_thing(&mut self, name : String) {
        self.list.push(Thing { name: name })
    }
}

The important part is this expression:

match self.find_thing_mut(name) {
    None => {
        self.init_thing(name.to_owned());
        self.do_something(name)
    },
    Some(t) => {
        t.do_something()
    },
}

The error we get is:

<anon>:18:17: 18:21 error: cannot borrow `*self` as mutable more than once at a time [E0499]
<anon>:18                 self.init_thing(name.to_owned());
                          ^~~~
<anon>:18:17: 18:21 help: see the detailed explanation for E0499
<anon>:16:15: 16:19 note: previous borrow of `*self` occurs here; the mutable
                          borrow prevents subsequent moves, borrows, or
                          modification of `*self` until the borrow ends
<anon>:16         match self.find_thing_mut(name) {
                        ^~~~
<anon>:24:10: 24:10 note: previous borrow ends here
<anon>:16         match self.find_thing_mut(name) {
...
<anon>:24         }
                  ^
<anon>:19:17: 19:21 error: cannot borrow `*self` as mutable more than once at a time [E0499]
<anon>:19                 self.do_something(name)
                          ^~~~
<anon>:19:17: 19:21 help: see the detailed explanation for E0499
<anon>:16:15: 16:19 note: previous borrow of `*self` occurs here; the mutable
                          borrow prevents subsequent moves, borrows, or
                          modification of `*self` until the borrow ends
<anon>:16         match self.find_thing_mut(name) {
                        ^~~~
<anon>:24:10: 24:10 note: previous borrow ends here
<anon>:16         match self.find_thing_mut(name) {
...
<anon>:24         }
                  ^

find_thing_mut() really needs to return a ref, because Thing is expensive to copy. The problem is since None has type Option<&'a mut Thing> where a is the lifetime of self, we can’t call a &mut self when that None is in scope. This is annoying and could be improved by doing some local reasoning. In our case, since we know that None can’t borrow anything (it doesn’t have any references), we could refine our information about currently borrwed values, and let this compile.

There are a couple of solutions. One half-solution is to use something like standard HashMap’s entry(). Imagine doing something like:

use std::collections::hash_map::HashMap;

struct ListOfThings {
    list : HashMap<String, Thing>,
}

struct Thing {
    field1 : i32,
    // other fields here -- this is expensive to copy!
}

impl Thing {
    fn do_something(&mut self) {}
}

impl ListOfThings {
    fn do_something(&mut self, name : &str) {
        match self.list.get_mut(name) {
            None => {
                self.list.insert(name.to_owned(), Thing { field1: 123 });
            },
            Some(t) => {
                t.do_something();
            }
        }
    }
}

The error we get:

<anon>:20:17: 20:26 error: cannot borrow `self.list` as mutable more than once at a time [E0499]
<anon>:20                 self.list.insert(name.to_owned(), Thing { field1: 123 });
                          ^~~~~~~~~
<anon>:20:17: 20:26 help: see the detailed explanation for E0499
<anon>:18:15: 18:24 note: previous borrow of `self.list` occurs here; the
                          mutable borrow prevents subsequent moves, borrows, or
                          modification of `self.list` until the borrow ends
<anon>:18         match self.list.get_mut(name) {
                        ^~~~~~~~~
<anon>:25:10: 25:10 note: previous borrow ends here
<anon>:18         match self.list.get_mut(name) {
...
<anon>:25         }
                  ^

This is exactly the same error we got before. The solution is to use the Entry API:

use std::collections::hash_map::{HashMap, Entry};

struct ListOfThings {
    list : HashMap<String, Thing>,
}

struct Thing {
    field1 : i32,
    // other fields here -- this is expensive to copy!
}

impl Thing {
    fn do_something(&mut self) {}
}

impl ListOfThings {
    fn do_something(&mut self, name : &str) {
        match self.list.entry(name.to_owned()) {
            Entry::Vacant(ve) => {
                ve.insert(Thing { field1: 123 });
            },
            Entry::Occupied(mut oe) => {
                oe.get_mut().do_something();
            }
        }
    }
}

Some things to note here:

  1. We had to give ownership of the key to the lookup function (HashMap::entry()). This potentially means copying a value just to lookup. Ideally we’d only need to do this when inserting to the map. HashMap::get() doesn’t have this problem.

  2. I said “half-solution” because this doesn’t really make the original code working. See how I removed a line in the first case in my HashMap-based implementation. If I change the first case to this:

            match self.list.entry(name.to_owned()) {
                Entry::Vacant(ve) => {
                    ve.insert(Thing { field1: 123 });
                    self.do_something(name)
                },

    It’d still fail as Entry keeps a reference to self. Of course you could always do things like:

            match self.list.entry(name.to_owned()) {
                Entry::Vacant(ve) => {
                    let mut thing = Thing { field1 : 123 };
                    thing.do_something();
                    ve.insert(thing);
                },

    Which works, but that’s quite different from our original program. Note that if we still had a method like init_thing() and has to pass Entry to that, it’d still fail with same error message. So yeah, not quite a solution.

The solution I use is this:

impl ListOfThings {
    fn do_something(&mut self, name : &str) {
        let thing : Option<*mut Thing> = self.find_thing_mut(name).map(|t| (t as *mut _));
        match thing {
            None => {
                self.init_thing(name.to_owned());
                self.do_something(name)
            },
            Some(t) => {
                unsafe { (*t).do_something() }
            },
        }
    }
}

(missing parts are the same as the original code),

I basically work around the borrow checker by using a raw pointer and an unsafe block, and hope that my .map() will be compiled as a no-op.

2. References to self in method values

A code like this fails if the method is mutable in self: self.f(self.x). As a running example:

struct Widget {
    pos_x : i32,
    pos_y : i32,
}

impl Widget {
    pub fn draw(&mut self) {
        self.draw_at(self.pos_x, self.pos_y);
    }

    pub fn draw_at(&mut self, pos_x : i32, pos_y : i32) {}
}

These are the errors:

<anon>:8:22: 8:32 error: cannot use `self.pos_x` because it was mutably borrowed [E0503]
<anon>:8         self.draw_at(self.pos_x, self.pos_y);
                              ^~~~~~~~~~
<anon>:8:9: 8:13 note: borrow of `*self` occurs here
<anon>:8         self.draw_at(self.pos_x, self.pos_y);
                 ^~~~
<anon>:8:34: 8:44 error: cannot use `self.pos_y` because it was mutably borrowed [E0503]
<anon>:8         self.draw_at(self.pos_x, self.pos_y);
                                          ^~~~~~~~~~
<anon>:8:9: 8:13 note: borrow of `*self` occurs here
<anon>:8         self.draw_at(self.pos_x, self.pos_y);
                 ^~~~

Basically the method itself (self.draw_at) borrows self mutably, and since arguments are evaluated after the function in a function application, we get this borrow checker error. The solution is simple in this case:

let pos_x = self.pos_x;
let pos_y = self.pos_y;
self.draw_at(pos_x, pos_y);

3. Variables that live across loops

Suppose you have a loop that internally calls some &mut self methods, and when it returns, it returns something with a reference to &self. Something like:

pub struct TUI {
    field1: i32,
}

pub enum TUIRet<'a> {
    Abort,
    KeyHandled,
    Input(&'a str),
}

impl TUI {
    pub fn idle_loop<'a>(&'a mut self) -> TUIRet<'a> {
        loop {
            self.draw();

            match self.keypressed() {
                ret @ TUIRet::Abort => { return ret; },
                ret @ TUIRet::Input(_) => { return ret; },
                _ => {},
            }
        }
    }

    pub fn keypressed(&mut self) -> TUIRet {
        panic!()
    }

    pub fn draw(&self) {}
}

Can you see what could go wrong here? Here’s the error:

<anon>:18:13: 18:17 error: cannot borrow `*self` as immutable because it is also borrowed as mutable [E0502]
<anon>:18             self.draw();
                      ^~~~
<anon>:20:19: 20:23 note: previous borrow of `*self` occurs here; the mutable
                          borrow prevents subsequent moves, borrows, or
                          modification of `*self` until the borrow ends
<anon>:20             match self.keypressed() {
                            ^~~~
<anon>:26:6: 26:6 note: previous borrow ends here
<anon>:16     pub fn idle_loop<'a>(&'a mut self) -> TUIRet<'a> {
...
<anon>:26     }
              ^
<anon>:20:19: 20:23 error: cannot borrow `*self` as mutable more than once at a time [E0499]
<anon>:20             match self.keypressed() {
                            ^~~~
<anon>:20:19: 20:23 help: see the detailed explanation for E0499
<anon>:20:19: 20:23 note: previous borrow of `*self` occurs here; the mutable
                          borrow prevents subsequent moves, borrows, or
                          modification of `*self` until the borrow ends
<anon>:20             match self.keypressed() {
                            ^~~~
<anon>:26:6: 26:6 note: previous borrow ends here
<anon>:16     pub fn idle_loop<'a>(&'a mut self) -> TUIRet<'a> {
...
<anon>:26     }
              ^

This is probably the worst of all. The weird part is that this works:

    pub fn idle_loop<'a>(&'a mut self) -> TUIRet<'a> {
        loop {
            self.draw();
            return self.keypressed();
        }
    }

Only solution I could find here was to remove the references to self, by just copying the value to Input. This unfortunately means more redundant copying.