Cannot assign to `n.left` which is behind a `&` reference

[devmetal]

Dear all,

I'm really stuck with this problem. I try to create some basic algorithm implementation in rust, just for learning. I'm coming from lanugages like javascript, python and go.

I like to create a bin tree insert alg.

struct Node<'a> {
    val: isize,
    left: &'a Option<Box<Node<'a>>>,
    right: &'a Option<Box<Node<'a>>>,
}

impl Node<'_> {
    fn new<'a>(val: isize) -> Node<'a> {
        Node {
            val,
            left: &None,
            right: &None,
        }
    }
}

struct BinTree<'a> {
    root: Option<Box<Node<'a>>>,
}

impl BinTree<'_> {
    fn insert(&mut self, z: isize) {
        let z_node = Some(Box::new(Node::new(z)));
        let mut x = &self.root;
        let mut y;

        loop {
            y = x;
            x = match x {
                Some(n) => {
                    if z < n.val {
                        &n.left
                    } else {
                        &n.right
                    }
                }
                None => {
                    break;
                }
            }
        }

        if let Some(n) = y {
            if z < n.val {
                n.left = &z_node;
            } else {
                n.right = &z_node;
            }
        } else {
            self.root = z_node;
        }
    }
}

The error output:

error[E0594]: cannot assign to `n.left` which is behind a `&` reference
  --> src/binstree.rs:45:17
   |
45 |                 n.left = &z_node;
   |                 ^^^^^^^^^^^^^^^^ `n` is a `&` reference, so the data it refers to cannot be written

error[E0594]: cannot assign to `n.right` which is behind a `&` reference
  --> src/binstree.rs:47:17
   |
47 |                 n.right = &z_node;
   |                 ^^^^^^^^^^^^^^^^^ `n` is a `&` reference, so the data it refers to cannot be written

I read about the references in rust. But i completelly los about it. I tought y is going to be a reference to a option -> box -> node and i can mutate. But this error for me means nothing Pls im struggle with this like hours.

Thanks

[alice]

You don't want references in your struct, so change it to this:

struct Node {
    val: isize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

The error is because an immutable reference (i.e. & instead of &mut) does not let you mutate the thing it points at.

[alice]

In general, working with structures similar to linked lists is often difficult in Rust. I encourage you to read the following tutorial:

Learn Rust With Entirely Too Many Linked Lists

[devmetal]

Hi, thank you for the answer!

Indeed the code now looks more familiar to me, but the error still there.
My problem is that i not understand the problem itself.

struct Node {
    val: isize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new<'a>(val: isize) -> Node {
        Node {
            val,
            left: None,
            right: None,
        }
    }
}

struct BinTree {
    root: Option<Box<Node>>,
}

impl BinTree {
    fn insert(&mut self, z: isize) {
        let z_node = Some(Box::new(Node::new(z)));
        let mut x = &self.root;
        let mut y;

        loop {
            y = x;
            x = match x {
                Some(n) => {
                    if z < n.val {
                        &n.left
                    } else {
                        &n.right
                    }
                }
                None => {
                    break;
                }
            }
        }

        if let Some(n) = y {
            if z < n.val {
                n.left = z_node;
            } else {
                n.right = z_node;
            }
        } else {
            self.root = z_node;
        }
    }
}

error[E0594]: cannot assign to `n.left` which is behind a `&` reference
  --> src/binstree.rs:45:17
   |
45 |                 n.left = z_node;
   |                 ^^^^^^ `n` is a `&` reference, so the data it refers to cannot be written

error[E0594]: cannot assign to `n.right` which is behind a `&` reference
  --> src/binstree.rs:47:17
   |
47 |                 n.right = z_node;
   |                 ^^^^^^^ `n` is a `&` reference, so the data it refers to cannot be written

error: aborting due to 2 previous errors

[alice]

The problem is that n is an immutable reference, so you cannot modify anything through it.

[alice]

Here is a way to make it compile:

Rust Playground

[H2CO3]

Two things:

1. Rust is immutable-by-default and it has transitive immutability. You can't mutate a let binding without mut, and you can't mutate anything behind at least one immutable reference. So neither of &Node, &&mut Node, &mut &Node, etc. allows you to mutate the Node itself. That is one of the core propositions of Rust, the RWLock pattern in action — you are allowed to either share xor mutate, but never both.
2. Typically, when writing a data structure, you want to use owned types rather than temporary borrows. You can still get mutable references to a given substructure in a method taking &mut self.

All in all, you probably meant something like this. Some additional notes:

• Declaring an uninitialized variable is unidiomatic. Although the compiler performs control flow sensitive liveness analysis, and you can't cause UB with it, it's still ugly. Rust is an expression language. Most language constructs that alter control flow (such as if and match) are expressions — use them! In Rust, we typically program with values rather than side effects.
• You don't need an explicit lifetime annotation on the Node::new() function. There's nothing generic over any lifetime in there.

[devmetal]

Thanks. For both. But one more thing. I tried those examples, and its compiling and working. Just the binary tree algorithm is broken. I need an extra variable to store the "previous" node. Because right now the tree is not growing, every time just set a new root.

Rust Playground

[alice]

The reason you are running into trouble with an implementation that remembers both the current and parent node is that the compiler is worried that something like this may be happening:

1. You use y to modify something.
2. This modification destroys whatever Box that x is pointing inside.
3. You try to use x afterwards, which would be an use-after-free.

That the above doesn't happen is a necessary but not sufficient condition for the code to compile. To actually make it compile, you have to actually convince the compiler that it doesn't happen, and this can be very difficult when your structure looks like a linked list.

[H2CO3]

To add to Alice's answer, you can just stop right before the last (non-existent) leaf instead: Playground.

[devmetal]

Thank you both of helps and explanations And the linked list tutorial is amazing. Lot of help. The rust is realy wierd language compared to javascript what is my main focus and area.
But i like it Thanks for you guys now i understand a little more. Still blank areas but not hopeless.