Destructuring self and then returning it ("cannot borrow `*self` as mutable more than once at a time")

I'm implementing a binary tree and I want to write a method which returns a random node from the tree. Later I need to be able to mutate that random node by adding a child to it.

enum Tree<T> {
    Empty,
    Node(T, Box<Tree<T>>, Box<Tree<T>>),
}

impl<T> Tree<T> {
    pub fn random(&mut self) -> &mut Tree<T> {
        self.random_help(thread_rng().gen_range(0..self.size()))
    }

    fn random_help(&mut self, random_int: usize) -> &mut Tree<T> {
        match self {
            Tree::Empty => self,
            Tree::Node(_, left, right) => {
                use std::cmp::Ordering::*;
                let left_size = left.size();

                match random_int.cmp(&left_size) {
                    Equal => self,
                    Less => left.random_help(random_int),
                    Greater => right.random_help(random_int - left_size - 1),
                }
            }
        }
    }

    fn insert(&mut self, value: T) {
      // …
    }
}

This returns the following error:

error[E0499]: cannot borrow `*self` as mutable more than once at a time
  --> src/layout.rs:67:30
   |
59 |       fn random_help(&mut self, random_int: usize) -> &mut Tree<T> {
   |                      - let's call the lifetime of this reference `'1`
60 | /         match self {
61 | |             Tree::Empty => self,
62 | |             Tree::Node(_, left, right) => {
   | |                           ---- first mutable borrow occurs here
63 | |                 use std::cmp::Ordering::*;
...  |
67 | |                     Equal => self,
   | |                              ^^^^ second mutable borrow occurs here
...  |
71 | |             }
72 | |         }
   | |_________- returning this value requires that `self.1` is borrowed for `'1`

Is there any way around this or am I trying to do something which Rust just won't allow me to do?

I don't have a good solution to offer in safe/stable Rust, but I just want to note that this code will compile successfully with the next-generation borrow-checker Polonius.

(example using nightly rustc)

2 Likes

Here's an ugly but working solution in safe stable Rust, based on this previous thread:

impl<T> Tree<T> {
    fn random_help(&mut self, random_int: usize) -> &mut Tree<T> {
        match self {
            Tree::Empty => self,
            Tree::Node(_, ref left, _) => {
                use std::cmp::Ordering::*;
                let left_size = left.size();

                match random_int.cmp(&left_size) {
                    Equal => self,
                    Less => self.left_mut().unwrap().random_help(random_int),
                    Greater => self.right_mut().unwrap().random_help(random_int - left_size - 1),
                }
            }
        }
    }
    
    fn left_mut(&mut self) -> Option<&mut Self> {
        match self {
            Tree::Node(_, left, _) => Some(left),
            Tree::Empty => None,
        }
    }
    
    fn right_mut(&mut self) -> Option<&mut Self> {
        match self {
            Tree::Node(_, _, right) => Some(right),
            Tree::Empty => None,
        }
    }
    
    fn size(&self) -> usize {
        todo!()
    }
}

Playground

3 Likes

It works, thank you for providing both solutions! I enabled Polonius since I use nightly for box_syntax and box_patterns and what I'm working on is just a side project.

Edit: Actually, I went with the stable solution because compiling the project with Polonius takes like 6 minutes and for some reason I need to do it almost every time after I change something in the project.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.