Calculating score from tree child node help with borrow checker


#1

I’m working through a few exercises I’ve done in the past with other languages to help me get to grips with Rust. One of these exercises is calculating scores from an N-ary tree. I’m struggling with the borrow checker (I think it’s the borrow checker / ownership issues anyway) in getting the following test to pass:

#[test]
fn scores_a_node_with_one_child() {
    let child = TreeNode::new(None, Some(10));
    let parent = TreeNode::new(Some(vec![child]), None);

    assert_eq!(parent.score(), Some(10));
}

Here is the implementation I’ve currently got:

struct TreeNode {
    children: Box<Option<Vec<TreeNode>>>,
    score: Option<i32>,
}

impl TreeNode {
    fn new(children: Option<Vec<TreeNode>>, score: Option<i32>) -> TreeNode {
        TreeNode { children: Box::new(children), score }
    }

    fn score(&self) -> Option<i32> {
        match self.score {
            None => {
                match *self.children {
                    None => None,
                    Some(children) => &children[0].score()
                }
            },
            Some(score) => Some(score)
        }
    }
}

With this code, I get an error expecting:

error[E0308]: match arms have incompatible types
  --> src/lib.rs:19:17
   |
19 | /                 match *self.children {
20 | |                     None => None,
21 | |                     Some(children) => &children[0].score()
   | |                                       -------------------- match arm with an incompatible type
22 | |                 }
   | |_________________^ expected enum `std::option::Option`, found reference
   |
   = note: expected type `std::option::Option<i32>`
              found type `&std::option::Option<i32>`

error: aborting due to previous error

If I remove the reference, I get a whole host of errors about not being able to move out of borrowed content, being behind a reference and copy trait not being implemented.

I’m stuck in how I should proceed with this in Rust and would appreciate some pointers (no pun intended) that will help me to move forward and also, hopefully, understand the borrow checker and references a bit better. I’d like to achieve this without implementing the copy trait, which I believe should be achievable, I’m just not certain on the correct way to do so. Any suggestions?


#2

Here is a working version.

The “trick” is you want to match on the contents of the Box as a reference, which if you’re dereferencing the box in the match statement, you need the ref keyword in the match clause to indicate you want to borrow the contents.

Alternatively, you can write match &*self.children or match self.children.as_ref() to be a bit more explicit; in both of these cases, you don’t need the ref in the match arm.


#3

Ah, thanks. That’s super helpful and has saved me from pulling out what’s left of my hair!

I think match self.children.as_ref() is is the clearest of those.

Thanks again :+1: