0

I want to implement a binary tree. My main language is C++ so the code is probably not idiomatic Rust, but compiling the following code:

use std::rc::Rc;

struct Node {
    left: Option<Rc<Node>>,
    right: Option<Rc<Node>>,
    data: String,
}


impl Node {
    fn new(_data: String) -> Node {
        Node {
            data : _data.clone(),
            left : None,
            right : None,
        }
    }

    fn insert_left(&mut self, mut node: &Rc<Node>) {
        self.left = Some(node.clone());
    }

    fn insert_right(&mut self, mut node: &Rc<Node>) {
        self.left = Some(node.clone());
    }
}

fn main() {
    let mut root = Rc::new(Node::new(String::from("root")));
    let mut left = Rc::new(Node::new(String::from("left")));
    root.insert_left(&left);
}

I have the compilation error:

error: cannot borrow immutable borrowed content as mutable
  --> so.rs:31:9
   |
31 |         root.insert_left(&left);
   |         ^^^^

error: aborting due to previous error

I can't understand what is wrong here. After some try-mistake iterations I found out that problem lies in the insert_left() function: if self is an immutable reference, then it compiles with commented out content, but an immutable reference does not allow my to accomplish my goal.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Alex
  • 9,891
  • 11
  • 53
  • 87
  • 2
    Have you looked at the [**23 other questions with the same error message**](http://stackoverflow.com/search?q=is%3Aq+cannot+borrow+immutable+borrowed+content+as+mutable)? What makes *this* question different from any of those? There's even one titled [Changing a node in a tree in Rust](http://stackoverflow.com/q/28008585/155423), which seems highly relevant. A good amount of [effort is expected from question askers](http://meta.stackoverflow.com/q/261592/155423), and at least finding other questions with the same error message and data structure seems a bare minimum. – Shepmaster Dec 08 '16 at 17:15
  • 1
    As for idiomatic Rust, you should not call your variable `_data`. Leading underscores are used to indicate *unused variables*. That variable is very much used. – Shepmaster Dec 08 '16 at 17:17
  • @Shepmaster what is the better convention for input arguments of constructing functions? – Alex Dec 08 '16 at 17:31
  • 2
    In general, there's nothing wrong with variable shadowing in Rust. However, there's no shadowing occurring here; just calling it `data` is fine. Remember that the name is *shown to users* when they browse your documentation as well. – Shepmaster Dec 08 '16 at 17:33

1 Answers1

8

Here's a MCVE of your problem:

use std::rc::Rc;

struct Node;

impl Node {
    fn insert_left(&mut self) {}
}

fn main() {
    let root = Rc::new(Node);
    root.insert_left();
}

You can arrive at an example like this by removing as much code as possible while still getting the same error. This process helps tremendously to build understanding of the problem.

The problem is that Rc disallows mutation of any kind. As stated in the documentation:

Shared pointers in Rust disallow mutation by default, and Rc is no exception. If you need to mutate through an Rc, use Cell or RefCell.

Therefore, there's no way to go from a Rc<Foo> to a &mut Foo, which would be needed to call the insert_left method.

As documented, you can use one of the types that allows interior mutability, such as a Cell or RefCell. These function a bit like a mutex, but are not valid for multithreaded scenarios. They ensure that only one mutable reference to a value is available at a time, a key component of Rust's safety.

If you don't need the functionality of Rc's sharing, you can just move to having an Option<Box<Node>> as well.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366