Is this double mutable borrow issue solveable?

help
1

I just started with Rust, and I might have some confusion surrounding what I can and cannot do. Excuse me for maybe asking the same question as someone else on this forum, I did a fair bit of searching but it was either the issue with keywords I was using, or the fact that the form of the question didn't quite match mine.

I'm implementing a parser, and somewhere inside the traits of my code I have this utility function for reducing an expression:

fn match_reduce<E, F>(&mut self, set: T, i: E, mut f: F) -> E
where
  F: FnMut(E, Self::Item) -> E
{
  let mut res = i;
  while let Some(item) = self.match_pop(set) {
    res = f(res, item)
  }
  res
}

This declaration is, as far as I understand from the lack of compiler messages, is completely fine. However, an issue rises when I try to use it to parse a right-associative expression:

let lhs = self.parse_expr_op(level - 1);
self.lexer.match_reduce(li.tokens, lhs, |lhs, tok| {
  let op = find_op_by_token(li, tok);
  Box::new(match li.arity {
    Arity::Binary => Node::BinaryExpr(op, lhs, self.parse_expr_op(level)),
    Arity::Unary => Node::UnaryExpr(op, lhs),
  })
})

This code has a double mutable borrow. First time, when calling self.lexer.match_reduce. The second time we borrow when calling self.parse_expr_op. Both functions modify the internal state of the lexer. Since the reduce borrows lexer as mutable and calls the closure, which again borrows lexer as mutable (through .lexer field of the parser), we have two mutable borrows at the same time.

I know that I can rewrite this code such that it uses a simple while loop, and in fact, it actually becomes 1 line shorter. That's probably the best solution anyway. However as I'm new to Rust, I'm curious if there's a secret Jutsu to use here that would allow me to use the reduce abstraction.

I'm open to all kinds of advice. Thanks in advance.

2

Maybe something like this:

fn match_reduce<E, F>(&mut self, set: T, i: E, mut f: F) -> E
where
  F: FnMut(&mut Self, E, Self::Item) -> E
{
  let mut res = i;
  while let Some(item) = self.match_pop(set) {
    res = f(self, res, item)
  }
  res
}

let lhs = self.parse_expr_op(level - 1);
self.lexer.match_reduce(li.tokens, lhs, |this, lhs, tok| {
  let op = find_op_by_token(li, tok);
  Box::new(match li.arity {
    Arity::Binary => Node::BinaryExpr(op, lhs, this.parse_expr_op(level)),
    Arity::Unary => Node::UnaryExpr(op, lhs),
  })
})
3

Now that doesn't really work. Note that match_reduce is defined on lexer, in which case self is lexer, but parse_expr expects the parser as the argument.

Even if I did modify the original function to use parser as pass-through parameter, the compiler can still figure it out, because, in a sense, we haven't really done anything, just passed the reference self as a parameter into another function and it's still a double borrow there.

4

I think Rust might be guaranteeing something for you by forbidding this code. The function f can't put self in a weird state (e.g. if the inner parse failed).

5

this is the problem.

inside the closure, you call Parser::parse_expr_op(), which needs the entire Parser, but part of (specifically, the lexer field of) the Parser object is already borrowed outside of the closure by Lexer::match_reduce().

when you use a regular loop, it compiles, this means the usage of the two borrows don't actually overlap, e.g. each fraction of them might be interleaving with each other.

but when you put one usage inside a closure, all the small segments (that were originally interleaving with the other borrow) were combined into a single large chunk, but the borrow checker doesn't "see through" function boundaries.

6

Right, it is the problem. What should I do about it? I understand there's probably not much of a generic advice that's possible to give me, so for now, as a simplest solution I'm reverting to plain loops.

7

The problem is that the closure borrows self, making it unusable outside, and this loan is for the entire lifetime of the closure, rather than on-and-off as you flip between reduce and parse.

You can express this "you can use self but only temporarily while I call you" by passing the self (Parser) as closure's argument. This way the closure won't need to get exclusive loan of self for itself.

// go through the parser to give it entire `self`
self.match_reduce(li.tokens, lhs, |the_extra_arg_with_the_parser, lhs, tok| {
   the_extra_arg_with_the_parser.parse_expr_op();
});
1 Like