Why do I need the type annotation here?

Question

In this leetcode invert binary tree problem, I'm trying to borrow a node wrapped in an Rc mutably. Here is the code.

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
        let mut stack: Vec<Option<Rc<RefCell<TreeNode>>>> = vec![root.clone()];
        while stack.len() > 0 {
            if let Some(node) = stack.pop().unwrap() {
                let n: &mut TreeNode = &mut node.borrow_mut();
                std::mem::swap(&mut n.left, &mut n.right);
                stack.extend(vec![n.left.clone(), n.right.clone()]);
            }
        }
        root
    }
}

If I change the line let n: &mut TreeNode to just let n = &mut node.borrow_mut(), I get a compiler error on the next line, "cannot borrow *n as mutable more than once at a time" It seems like the compiler infers n to be of type &mut RefMut<TreeNode>, but it all works out when I explicitly say it is &mut TreeNode. Any reason why?

Answer 1

A combination of borrow splitting and deref-coercion causes the seemingly identical code to behave differently.

The compiler infers n to be of type RefMut<TreeNode>, because that's what borrow_mut actually returns:

pub fn borrow_mut(&self) -> RefMut<'_, T>

RefMut is a funny little type that's designed to look like a &mut, but it's actually a separate thing. It implements Deref and DerefMut, so it will happily pretend to be a &mut TreeNode when needed. But Rust is still inserting calls to .deref() in there for you.

Now, why does one work and not the other? Without the type annotation, after deref insertion, you get

let n = &mut node.borrow_mut();
std::mem::swap(&mut n.deref_mut().left, &mut n.deref_mut().right);

So we're trying to call deref_mut (which takes a &mut self) twice in the same line on the same variable. That's not allowed by Rust's borrow rules, so it fails.

(Note that the &mut on the first line simply borrows an owned value for no reason. Temporary lifetime extension lets us get away with this, even though you don't need the &mut at all in this case)

Now, on the other hand, if you do put in the type annotation, then Rust sees that borrow_mut returns a RefMut<'_, TreeNode> but you asked for a &mut TreeNode, so it inserts the deref_mut on the first line. You get

let n: &mut TreeNode = &mut node.borrow_mut().deref_mut();
std::mem::swap(&mut n.left, &mut n.right);

Now the only deref_mut call is on the first line. Then, on the second line, we access n.left and n.right, both mutably, simultaneously. It looks like we're accessing n mutably twice at once, but Rust is actually smart enough to see that we're accessing two disjoint parts of n simultaneously, so it allows it. This is called borrow splitting. Rust will split borrows on different instance fields, but it's not smart enough to see the split across a deref_mut call (function calls could, in principle, do anything, so Rust's borrow checker refuses to try to do advanced reasoning about their return value).