Mutably borrowing last initialized node of a tree

Viewed 53

I am trying to lazy-initialize a simple tree on first access of a node.

My tree struct:

struct Tree {
    true_branch: Option<Box<Tree>>,
    false_branch: Option<Box<Tree>>,
}

To do the lazy initialization on first access I would like to return a Result<&mut Tree, &mut Tree> which is an Ok(requested_node) if the node is already initialized or an Err(last_initialized_on_the_path_to_requested_node) so that the lazy initialization can continue from that node.

Getting a node, if it initialized works fine with get_mut but I cannot get the Result version, get_last_initialized_mut, to compile.

impl Tree {
    fn get_mut(&mut self, mut directions: impl Iterator<Item = bool>) -> Option<&mut Self> {
        let mut current = self;
        loop {
            match directions.next() {
                None => break,
                Some(true) => {
                    current = current.true_branch.as_deref_mut()?;
                }
                Some(false) => {
                    current = current.false_branch.as_deref_mut()?;
                }
            }
        }
        Some(current)
    }
    
    /// This does not compile
    fn get_last_initialized_mut(&mut self, mut directions: impl Iterator<Item = bool>) -> Result<&mut Self, &mut Self> {
        let mut current = self;
        loop {
            match directions.next() {
                None => break,
                Some(true) => {
                    let next = current.true_branch.as_deref_mut();
                    if next.is_none() {
                        drop(next);
                        return Err(current);
                    } else {
                        current = next.unwrap();
                    }
                }
                Some(false) => {
                    let next = current.false_branch.as_deref_mut();
                    if next.is_none() {
                        drop(next);
                        return Err(current);
                    } else {
                        current = next.unwrap();
                    }
                }
            }
        }
        Ok(current)
    }
}

The error:

error[E0499]: cannot borrow `*current` as mutable more than once at a time
  --> src/lib.rs:36:36
   |
27 |     fn get_last_initialized_mut(&mut self, mut directions: impl Iterator<Item = bool>) -> Result<&mut Self, &mut Self> {
   |                                 - let's call the lifetime of this reference `'1`
...
33 |                     let next = current.true_branch.as_deref_mut();
   |                                ---------------------------------- first mutable borrow occurs here
...
36 |                         return Err(current);
   |                                    ^^^^^^^ second mutable borrow occurs here
...
52 |         Ok(current)
   |         ----------- returning this value requires that `current.true_branch` is borrowed for `'1`

What I do not get is that I drop next on line 35 and then it says current is still borrowed on line 36, by the borrow by next on line 33.

I have tried breaking with an enum and returning outside of the loop based on the break type, dropping variables. Neither of them worked.

Playground

0 Answers
Related