Traversing recursive type with a mutable reference

help
#1

I'm working with a binary tree type (simplified here):

enum Node {
    Good {
        left: Option<Box<Node>>,
        right: Option<Box<Node>>,
    },
    Bad,
}

To get a mutable reference to the leftmost node, what would be the minimal element in a BST, I wrote this code:

impl Node {
    fn left_child_mut(&mut self) -> Option<&mut Node> {
        match *self {
            Node::Good { left: Some(ref mut child), .. } => Some(child),
            _ => None,
        }
    }

    fn leftmost_mut(&mut self) -> &mut Node {
        let mut cur = self;
        
        while let Some(child) = cur.left_child_mut() {
            cur = child;
        }
        
        cur
    }
}

The borrow checker complains (playground) that *cur can't be mutably borrowed by left_child_mut(), because another mutable reference is returned on the last line. If I match on *cur directly in leftmost_mut() (basically inlining left_child_mut()), there's no issue. Since I have several methods that traverse a tree in this way, I'd like to avoid writing a match every time; is there a way to modify the code so that this works out?

(There are several questions on StackOverflow and this forum about similar-looking problems, but they all seem to boil down to the lack of NLLs, and I'm using the 2018 edition. I haven't had any luck with the posted solutions to these other problems, though I might be adapting them incorrectly to my case.)

#2

Just curious, is there some reason your node type has double-optioning? What's the difference between None and Some(Box::new(Node::Bad))?

#3

The real type looks like this:

enum Node<T> {
    Good {
        contents: T,
        left: Option<Box<Node<T>>>,
        right: Option<Box<Node<T>>>,
    },
    Bad {
        left: Box<Node<T>>,
        right: Box<Node<T>>,
    },
}

I elided the details that didn't matter for this question.

#4

Does this work?

impl Node {
  fn leftmost_mut(&mut self) -> &mut Node {
      let mut cur = self;
      
      while let Node::Good {left: Some(child),..} = cur {
          cur = child
      }
      
      cur
  }
}
#5

Sorry, I probably wasn't clear about this -- what I want is for leftmost_mut() to call out to left_child() instead of destructuring Node itself (because the real Node type is more complicated and I don't want to replicate the pattern match in every method that needs to traverse the tree).

#6

The answer is similar though. The main problem is limitations in Rust’s borrow checker. I don’t fully understand the details myself but the way you can tell is that it compiles with -Zpolonius, a WIP alternative borrow-checker which fixes this and similar limitations.

For the time being, trying to restructure the program may help, let’s see...

Already this doesn’t work:

    fn left_child_mut_of_self(&mut self) -> &mut Node {
        match self.left_child_mut() {
            None => self,
            Some(child) => child,
        }
    }

So to make the borrow checker happy, we probably need a new version of left_child_mut that returns Result<&mut Node, &mut Node> instead of Option<&mut Node>.

(The alternative would be to call it twice but that seems inefficient)

    fn left_child_mut_of_self(&mut self) -> &mut Node {
        if self.left_child_mut().is_some() {
            self.left_child_mut().unwrap()
        } else {
            self
        }
    }

With a Result<&mut Node, &mut Node> return type, there’s no need to borrow the node mutably a second time anymore and you can make it work like this.

2 Likes
#7

Perfect, thank you! It's a relief to know that this is a real limitation of the borrow checker and not bad reasoning on my part.

(And huh, I didn't realize you could use break with an expression like that.)

#8

It came in with 2018 edition:
https://doc.rust-lang.org/edition-guide/rust-2018/control-flow/loops-can-break-with-a-value.html

1 Like
#9

I'm not sure if it helps, but this recursive implementation seemed to work perfectly fine for me...

enum Node {
    Good {
        left: Option<Box<Node>>,
        right: Option<Box<Node>>,
    },
    Bad,
}

impl Node {
    fn leftmost_mut(&mut self) -> &mut Node {
        match self {
            Node::Good {
                left: Some(left), ..
            } => left.leftmost_mut(),
            _ => self,
        }
    }
}

(playground)

#10

Thanks! I was hoping to find (and @steffahn provided) an iterative implementation, for the usual efficiency reasons, but it's good to know it can be done recursively as well.

#11

But this is no better than that solution:

It only works because you removed the left_child_mut abstraction. However:

1 Like
#12

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.