9

I need to define a binary search tree where each node has access to the parent:

enum Tree<'a> {
    Leaf,
    Node {
        left: Box<Tree<'a>>,
        right: Box<Tree<'a>>,
        parent: &'a Tree<'a>,
        data: u64,
    }
}

impl <'a> Tree<'a> {
    pub fn new(data: u64, parent: &'a Tree) -> Tree<'a> {
        Tree::Node {
            left: Box::new(Tree::Leaf),
            right: Box::new(Tree::Leaf),
            parent,
            data
        }
    }
    pub fn insert_at_left_leaf(&'a mut self, data: u64) {
        match *self {
            Tree::Leaf => panic!("Leaf has no children"),
            Tree::Node {ref mut left, ..} => {
                **left = Tree::new(data, self);
            }
        }
    }
}

fn main() {
    let parent = Tree::Leaf;
    let mut t = Tree::Node {
        left: Box::new(Tree::Leaf),
        right: Box::new(Tree::Leaf),
        parent: &parent,
        data: 1u64
    };
    t.insert_at_left_leaf(2);
}

playground

However, I get the following compilation error:

error[E0502]: cannot borrow `*self` as immutable because `self.left` is also borrowed as mutable
  --> src/main.rs:24:42
   |
23 |             Tree::Node {ref mut left, ..} => {
   |                         ------------ mutable borrow occurs here
24 |                 **left = Tree::new(data, self);
   |                                          ^^^^ immutable borrow occurs here
25 |             }
26 |         }
   |         - mutable borrow ends here

What is the paradigmatic way to do this in safe Rust? Specifically, when I insert a new node as the leaf of an existing node, I do not want to re-allocate space for it. There is already space allocated for the Leaf and I want to simply overwrite it with the new node.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
user1413793
  • 9,057
  • 7
  • 30
  • 42
  • 4
    That's **not a tree**. If it has a parent pointer, it's a *graph*, not a *tree*. – Shepmaster Jul 14 '17 at 17:52
  • 26
    I disagree. Having a parent pointer is an implementation detail. Ultimately what makes the data structure a tree or a graph is the API it exposes (i.e. from the user's standpoint are their cycles or not in the data structure?). – user1413793 Jul 14 '17 at 17:54
  • The compiler doesn't care that you are only exposing half of the graph - the concept of ownership within a graph is not easily expressible and that's what the compiler is telling you. – Shepmaster Jul 14 '17 at 17:58
  • @Shepmaster This is a special case of a graph. For that reason I don't think it should be closed as duplicate: A solution that will work in this case (e.g. using `Rc` for child pointers and weak references for parent pointers) won't necessarily work for general graphs. – interjay Jul 14 '17 at 17:59
  • @interjay the duplicate target also has a node with children and parents and an answer suggests using `Rc`, just as you suggest; why do you think that's not a valid target? – Shepmaster Jul 14 '17 at 18:01
  • It is still unclear to me why what I am doing is unsafe. It seems perfectly valid for a child to have a reference to the parent and in turn be owned by the parent. The child can only go out of scope when the parent relinquishes ownership of it and there is no problem of dangling pointers. – user1413793 Jul 14 '17 at 18:02
  • 2
    @Shepmaster I looked at the other duplicate which said that it is impossible in safe Rust. By the way, the Rust documentation refers to a tree with parent pointers as a tree, not a graph: https://doc.rust-lang.org/std/rc/struct.Weak.html – interjay Jul 14 '17 at 18:03
  • 1
    I didn't say it was *unsafe*. You can totally have a value contain a reference to itself, *so long as you never modify or move it*, which is not what most people want. See [Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/q/32300132/155423) for details — your parent would store a child which would have a reference to the parent, thus you are storing a reference to yourself. – Shepmaster Jul 14 '17 at 18:07
  • Remember that *safe Rust* is only capable of expressing a certain subset of the programs that are *actually safe*. Use of the `unsafe` keyword allows the programmer to say "no, **I guarantee** that this code is safe by Rust's safety rules even though the compiler cannot see that it is". You cannot write code that is *actually unsafe* regardless of how many keywords you add. – Shepmaster Jul 14 '17 at 18:13
  • 1
    "You cannot write code that is actually unsafe regardless of how many keywords you add." - that's just not true. In an unsafe block you can write code that dereferences unallocated memory which is absolutely unsafe. For example: unsafe { let p = 1; let q = p as *const i64; println!("{:?}", *q); } – user1413793 Jul 14 '17 at 18:25
  • @user1413793 you are correct; I used ambiguous phrasing — I'm sorry I confused the issue. I meant to say something closer to: "You *must never* write code that is actually unsafe regardless of how many keywords you add." – Shepmaster Jul 14 '17 at 18:29
  • 2
    I don't agree that this is a duplicate of either of the marked questions. I've nominated for reopening. – BurntSushi5 Jul 14 '17 at 20:53
  • @user1413793: "It seems perfectly valid for a child to have a reference to the parent and in turn be owned by the parent." Which do you drop first? If you drop the parent first, the child has a dangling pointer to it when it gets dropped. If you drop the child first, the parent has a dangling pointer to it when *it* gets dropped. Neither of these are situations Rust will allow in safe code. – DK. Jul 17 '17 at 07:24
  • By rust's ownership rules, only the parent may drop the child as the parent owns it. So, the parent (or whoever owns the parent) can safely drop the left (or right) child with no dangling pointers. Because the child only has a reference to the parent, this is perfectly okay. – user1413793 Jul 18 '17 at 15:39

0 Answers0