Is there a way to tell rustc when is is being too conservative about certain borrows?

Question

I'm playing around with building a very simple stack based evaluator in Rust and I've come up against an odd situation where I think the borrow checker is being too conservative:

use std::collections::HashMap;

pub type Value = i32;
pub type Result = std::result::Result<(), Error>;
type Op = Box<dyn Fn(&mut Evaluator) -> Result>;
type OpTable = HashMap<String, Op>;

pub struct Evaluator {
    stack: Vec<Value>,
    ops: OpTable,
}

#[derive(Debug, PartialEq)]
pub enum Error {
    DivisionByZero,
    StackUnderflow,
    UnknownWord,
    InvalidWord,
}

impl Evaluator {
    fn add(&mut self) -> Result {
        if let (Some(x), Some(y)) = (self.stack.pop(), self.stack.pop()) {
            self.stack.push(y + x);
            Ok(())
        } else {
            Err(Error::StackUnderflow)
        }
    }

    fn sub(&mut self) -> Result {
        if let (Some(x), Some(y)) = (self.stack.pop(), self.stack.pop()) {
            self.stack.push(y - x);
            Ok(())
        } else {
            Err(Error::StackUnderflow)
        }
    }

    pub fn new() -> Evaluator {
        let stack: Vec<Value> = vec![];
        let mut ops: OpTable = HashMap::new();

        ops.insert("+".to_string(), Box::new(Evaluator::add));
        ops.insert("-".to_string(), Box::new(Evaluator::sub));

        Evaluator { stack, ops }
    }

    pub fn eval(&mut self, input: &str) -> Result {
        let symbols = input.split_ascii_whitespace().collect::<Vec<_>>();

        // user definition
        if let (Some(&":"), Some(&";")) = (symbols.first(), symbols.last()) {
            if symbols.len() > 3 {
                let statement = symbols[2..symbols.len() - 1].join(" ");
                self.ops.insert(
                    symbols[1].to_string().to_ascii_lowercase(),
                    Box::new(move |caller: &mut Evaluator| caller.exec(&statement)),
                );
                return Ok(());
            } else {
                return Err(Error::InvalidWord);
            }
        }
        self.exec(input)
    }

    fn exec(&mut self, input: &str) -> Result {
        let symbols = input.split_ascii_whitespace().collect::<Vec<_>>();
        for sym in symbols {
            if let Ok(n) = sym.parse::<i32>() {
                self.stack.push(n);
            } else {
                let s = sym.to_ascii_lowercase();
                if let Some(f) = self.ops.get(&s) { // <--------------errors here
                    f(self)?; // <----------------------------|
                } else {
                    return Err(Error::InvalidWord);
                }
            }
        }
        Ok(())
    }
}

fn main() {
    let mut e = Evaluator::new();
    e.eval("1 2 +");
    println!("{:?}", e.stack);
    e.eval(": plus-1 1 + ;");
    e.eval("4  plus-1");
    println!("{:?}", e.stack);
}

I'm getting:

error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/main.rs:77:21
   |
76 |                 if let Some(f) = self.ops.get(&s) {
   |                                  -------- immutable borrow occurs here
77 |                     f(self)?;
   |                     -^^^^^^
   |                     |
   |                     mutable borrow occurs here
   |                     immutable borrow later used by call

For more information about this error, try `rustc --explain E0502`.
error: could not compile `evaluator` due to previous error

I believe this is because taking part of the hashmap (f) borrows all of self immutably, then I'm passing self mutably to f(). However, there is no real conflict here (I think).

I'm able to get around this by actually removing and reinserting the value:

    fn exec(&mut self, input: &str) -> Result {
        let symbols = input.split_ascii_whitespace().collect::<Vec<_>>();
        for sym in symbols {
            if let Ok(n) = sym.parse::<i32>() {
                self.stack.push(n);
            } else {
                let s = sym.to_ascii_lowercase();

                if self.ops.contains_key(&s) {
                    let f = self.ops.remove(&s).unwrap();
                    if let Err(e) = f(self) {
                        self.ops.insert(s, f);
                        return Err(e);
                    }
                    self.ops.insert(s, f);
                } else {
                    return Err(Error::InvalidWord);
                }
            }
        }
        Ok(())
    }

But this feels hacky and is a lot more verbose and inefficient. Am I missing something? Is there a way to tell the compiler the first version is ok?

Answer 1

The compiler is entirely correct, and so is your explanation: The call to get() needs a borrow on self.ops to return an &Op of the same lifetime. You then try to call that FnMut with a mutable borrow of self; this mutable borrow of self aliases with the immutable borrow on self.ops, and in theory it would be possible for an implementation of this FnMut to modify that borrowed Op through self, which is not allowed. The compiler prevented a situation where mutation occurs through an aliased pointer.

This situation often occurs when passing &mut self around, as immutable borrows on members of self which result in more borrows (&self.ops.get() has the same lifetime as &self) "lock" all of self.

While your second example is cumbersome, it is at least correct as proven by the compiler: By removing Op from the hashtable, the FnMut can't reach itself through self anymore, and mutation while aliasing is prevented.

A better approach is usually to avoid taking &mut self as an argument (&mut self as in &mut Executor).