I admit defeat.
A few weeks ago I was writing some Rust code, building basic data structures from scratch, just for practice and curiosity. At one point I wrote what I thought to be a fairly simple and straightforward function, and discovered that there is no way to convince the borrow checker of its correctness.
I spent a lot of time studying the code and a bunch of variations. After many attempts at fixing it, I am giving up: Rust will not allow this function to compile; the borrow checker wins this time.
As far as I can tell, this is a known weakness in the borrow checker, one that will be addressed in the future (with Polonius, I think.) I'll add a few links to relevant bugs, articles, etc. later on.
Introduction: Building a Simple BST in Rust §
A BST (Binary Search Tree) is pretty straightforward in Rust. There are a few different ways to do it, but mine happens to look like this:
/// A Binary Search Tree
pub struct BST<K, V> {
root: OptNode<K, V>,
}
/// A node in a Binary Search Tree
struct TreeNode<K, V> {
key: K,
val: V,
left: OptNode<K, V>,
right: OptNode<K, V>,
}
/// A place we can store a child node, or not.
struct OptNode<K, V>(Option<Box<TreeNode<K, V>>>);
As you can see, I am using the binary search tree as a key-value store. Most textbook examples of a BST just store one value, but I'll store two: key is used to find the node in the tree, and value is some payload data that doesn't affect the tree structure.
It's quite likely that a BST implementation will have many public methods that need to traverse the tree, looking for a particular key, or if it's not found, the place where that key would have been. So I'd like to write that logic only once, and have all the public methods call that utility function when they need to walk the tree.
This being Rust, we probably need two: one that allows mutation and one that doesn't.
The immutable tree-traversal function looks like this:
impl<K, V> OptNode<K, V>
where
K: Ord,
{
/// Locate the pointer to the desired node (or where it should be).
fn find<'a, 'q, Q>(&'a self, key: &'q Q) -> &'a OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
match current.0 {
None => break,
Some(ref node) => match key.cmp(&node.key) {
Ordering::Equal => break,
Ordering::Less => {
current = &node.left;
}
Ordering::Greater => {
current = &node.right;
}
},
}
}
current
}
}
This function works fine. The main body of the function is readable and friendly, and its operation is pretty simple. One could argue that it should return Option<&TreeNode>, but I wanted to make it as close as possible to the mutable version we'll see next.
The only tricky part might be the trait bounds: we've introduced some new type Q, with the constraint that K can be borrowed as a Q. This is a trick used in the standard library, for example in HashMap. This is what allows you to write hashmap.get("hello") on a HashMap<String, _>, without worring about String vs &str.
Trouble Begins §
Here is the mutable version of my tree-traversal function:
/// Locate the pointer to the desired node (or where it should be).
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
match current.0 {
None => break,
Some(ref mut node) => match key.cmp(&node.key.borrow()) {
Ordering::Equal => break,
Ordering::Less => {
current = &mut node.left;
}
Ordering::Greater => {
current = &mut node.right;
}
},
}
}
current
}
It's virtually identical to the immutable version, but unfortunately this function does not compile.
error[E0499]: cannot borrow `*current` as mutable more than once at a time
--> src/lib.rs:91:9
|
71 | fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
| -- lifetime `'a` defined here
...
80 | Some(ref mut node) => match key.cmp(&node.key.borrow()) {
| ------------ first mutable borrow occurs here
...
91 | current
| ^^^^^^^
| |
| second mutable borrow occurs here
| returning this value requires that `current.0.0` is borrowed for `'a`
I found it quite difficult to understand this error message, but as far as I can tell it's saying this:
- We started with a mutable reference called
current. This will be returned from the function, so this reference must exist until the end of the function. - We created a new mutable reference
node. We later derive another reference based onnode(either&mut node.leftor&mut node.right), which may be the function's return value. - Therefore the
nodereference must also exist until the end of the function. - Since both lifespans reach until the end, there is no way to set the reference lifetimes such that only one mutable borrow exists at a time.
Someone more familiar with the compiler internals could probably give a better explanation (please do!) but this is the best I could come up with after days of trawling for answers.
One bit of advice for anyone who is struggling with
cannot borrow ... as mutable more than onceerrors in recursive data structures: beware the posts from 2015-2018 that come up when searching for help. They mostly predate the modern borrow checker implementation (which supports non-lexical lifetimes), so their reasoning and advice are out of date and unhelpful.Answers that recommend adding a dummy temporary variable to fix borrow checker errors are probably wrong.
In a Hole? Keep Digging §
Here's an equivalent version that doesn't use match syntax:
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
if current.0.is_none() {
break;
}
if let Some(ref mut node) = current.0 {
if node.key.borrow() == key {
break;
}
if node.key.borrow() > key {
current = &mut node.left;
} else {
// node.key < key
current = &mut node.right;
}
}
}
current
}
This is basically the same thing, so it's not surprising that it fails in the same way. I find it a little easier to reason about the scope of each reference in this version.
Here's a strange thing, though: if I remove the break from the scope that has borrowed node, this new (but incomplete) version does compile:
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
if current.0.is_none() {
break;
}
if let Some(ref mut node) = current.0 {
if node.key.borrow() == key {
// break; // Huh?
}
if node.key.borrow() > key {
current = &mut node.left;
} else {
// node.key < key
current = &mut node.right;
}
}
}
current
}
I don't have a great understanding why this might be, but it does seem to be a variant on Rust issue 47680, which makes me feel a little less bad about not understanding: this isn't deliberately designed behavior; it's a quirk of the current compiler implementation (current meaning Rust 1.50, or nightly as of February 2021).
Getting It To Work §
I did find a few variations that work, though they all have ugly spots that leave me a little dissatisfied. I'll show them here:
Handle the break case in another scope
This one is inspired by the previous discovery that the break contributes to the problem. If I put the break branch into a separate scope, the borrow checker is satisfied.
I find this version a tiny bit annoying because it's probably obvious to future coders that all three cases should live together, so it will forever need a comment explaining why it's oddly structured, with a warning to not try to fix it (unless you live in a Polonius future).
It also bothers me that node.key.borrow() needs to be duplicated, though I doubt there's any real-world overhead. Are there nontrivial implementations of std::borrow::Borrow that would result in this code being less efficient? I have no idea.
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
if current.0.is_none() {
break;
}
// Warning: don't try to combine this case with the
// one that follows, or the borrow checker will be upset.
if let Some(ref node) = current.0 {
if node.key.borrow() == key {
break;
}
}
if let Some(ref mut node) = current.0 {
if node.key.borrow() > key {
current = &mut node.left;
} else {
// node.key < key
current = &mut node.right;
}
}
}
current
}
Don't derive the return value from node
This version evades the problem by doing the key comparison, then immediately discarding the node reference, instead doing a redundant unwrap of the Option. Will the compiler optimize away the panic branch of the duplicate unwrap? I hope it will, but I'm worried it might not.
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
match current.0 {
None => break,
Some(ref node) => match key.cmp(&node.key.borrow()) {
Ordering::Equal => break,
Ordering::Less => {
// Warning: the borrow checker is upset if we try to do
// it the obvious way: current = &mut node.left;
current = &mut current.0.as_mut().unwrap().left;
}
Ordering::Greater => {
current = &mut current.0.as_mut().unwrap().right;
}
},
}
}
current
}
Use unsafe
I guess I can just break the glass and use the big unsafe hammer. This seems kind of scary, and I don't really want to go here. I only included this attempt because I figured somebody would complain if I didn't at least consider this strategy.
fn find_mut<'a, 'q, Q>(&'a mut self, key: &'q Q) -> &'a mut OptNode<K, V>
where
Q: Ord,
K: Ord + std::borrow::Borrow<Q>,
{
let mut current = self;
loop {
match current.0 {
None => break,
Some(ref mut node) => match key.cmp(&node.key.borrow()) {
Ordering::Equal => break,
Ordering::Less => {
// SAFETY: this pointer is known to always be
// valid. We're only working around a known
// borrow checker issue.
let node = node as *mut Box<TreeNode<K, V>>;
unsafe { current = &mut (*node).left; }
}
Ordering::Greater => {
let node = node as *mut Box<TreeNode<K, V>>;
unsafe { current = &mut (*node).right; }
}
},
}
}
current
}
Epilogue §
I said at the beginning that I was defeated, and then showed three different ways to make it actually work. Maybe I should be a little less dramatic. It worked in the end, right?
I'm still a bit disappointed, though. I didn't succeed at my goal of getting the borrow checker to accept my program using straightforward idiomatic code. Instead I landed on a few acceptable workarounds, each of which comes with various minor annoyances attached. But as always, it was an interesting journey. I learned a bit more about the Rust compiler, especially the past and the future of the borrow checker.
For what it's worth, I did try running with -Zpolonius and my original code builds without errors. I hope that means that eventually this set of problems will just go away, but I'm not sure how optimistic I should be.
Is there a merit badge for "wrote some code that requires Polonius to compile"?
May you win all your arguments with the borrow checker.
Postscript §
A couple of other articles worth reading:
I think the Improperly Reduced Borrows section in the Rust Nomicon is referring to the same problem, but it's hard to know for sure.
I also found the discussion of reborrowing interesting, but while it's useful to understand the ways that mutable references are constrained, I ultimately don't think that it helps me understand what's going on in this particular program.