Turning `&T` into `Rc<RefCell<T>>`

help
1

I am trying to port a tree into Rust and run into a problem when trying to write fn add_node

Focusing on

fn add_node(&mut self, child: Rc<RefCell<Node>>)

I am trying to update child.parent = self but it is not possible because I cannot turn &mut self into Rc<RefCell<Node>> and parent is expecting that.

#[derive(PartialEq, Eq, Default)]
struct Point {
    x: i64,
    y: i64,
}

struct Trees {
    tree_roots: Vec<Rc<RefCell<Node>>>,
}

impl Trees {
    /// updates `self` by attaching nodes to `self.tree_roots`
    fn generate(&mut self) {
        let point = Point::default();
        let new_parent = Rc::new(RefCell::new(Node::default()));
        let new_child = Rc::new(RefCell::new(Node::default()));

        self.attach(point, new_child.clone(), new_parent.clone());

        // new_parent and new_child needs to be used afterwards
        let _ = Rc::downgrade(&new_parent);
        let _ = Rc::downgrade(&new_child);
    }

    /// attach `new_root` to `self`, also mutate `new_child`
    fn attach(&mut self, point: Point, new_child: Rc<RefCell<Node>>, new_root: Rc<RefCell<Node>>) {
        // dummy condition
        let cond = true;

        if cond {
            *new_root.borrow_mut() = Node::new_logic1();
            *new_child.borrow_mut() = Node::new_logic2();

            // add `new_child` to `new_root`
            new_root.borrow_mut().add_node(new_child);

            // push `new_root` to self.tree_roots
            self.tree_roots.push(new_root);
        } else {
            // Some logic returning a new_child
            *new_child.borrow_mut() = todo!();
        }
    }
}

/// A node points to its parent and its children
#[derive(PartialEq, Eq, Default)]
struct Node {
    is_root: bool,
    point: Point,
    parent: Rc<RefCell<Self>>,
    children: Vec<Rc<RefCell<Self>>>,
}

impl Node {
    fn new(point: Point) -> Self {
        Self {
            point,
            ..Default::default()
        }
    }

    /// Some logic creating a Node
    fn new_logic1() -> Self {
        Self::default()
    }

    /// Some logic creating a Node
    fn new_logic2() -> Self {
        Self::default()
    }

    /// Add `child` to `self.children` and also make `self` the parent of
    /// the `child`, i.e. child.parent = self
    fn add_node(&mut self, child: Rc<RefCell<Self>>) {
        // make sure child is not the same as self
        debug_assert!(*child.borrow() != *self);

        child.borrow_mut().is_root = false;

        // problematic line.
        // How to turn `&T` or `&mut T` into Rc<RefCell<T>> to satisfy `self.parent`?
        //                          vvvvvvvvvvvvvvvvvvvvvvvvvvv
        child.borrow_mut().parent = Rc::new(RefCell::new(self));

        // at last, push `child` to `self.children`
        self.children.push(child);
    }
}

error[E0308]: mismatched types
   --> src/lib.rs:89:58
    |
89  |         child.borrow_mut().parent = Rc::new(RefCell::new(self));
    |                                             ------------ ^^^^ expected `Node`, found `&mut Node`
    |                                             |
    |                                             arguments to this function are incorrect
    |
note: associated function defined here
   --> /playground/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/cell.rs:820:18
    |
820 |     pub const fn new(value: T) -> RefCell<T> {
    |                  ^^^
2

You can't (without cloning the T which isn't what you want). &T temporarily borrows the T, whereas Rc<RefCell<T>> owns the T.

You could do this...

    fn add_node(this: Rc<RefCell<Self>>, child: Rc<RefCell<Self>>) {
        child.borrow_mut().is_root = false;

        child.borrow_mut().parent = this.clone();

        this.borrow_mut().children.push(child);
    }

            // add `new_child` to `new_root`
            Node::add_node(new_root.clone(), new_child);

...but I didn't test or think very hard about anything besides getting it to compile.

Your ownership story is going to be... challenging. Currently if this even works it probably leaks everything due to ownership loops.[1]

Incidentally, if this was supposed to check that you had two distinct Node locations in memory (versus the values of their fields)...

        // make sure child is not the same as self
        debug_assert!(*child.borrow() != *self);

...it was going to panic before the assert anyway, because that's what RefCell does when you have an outstanding RefMut<'_, _> and you try to borrow again.

If you get rid of the &mut Node and then hand it two equal nodes, I also believe it will then recurse forever instead, due to your derived PartialEq in combination with your ciruclar data structures.

I was going to test that, but your derived Default implementation also recurses forever, so it's not possible to create a Node with new.[2]

struct Node {
    is_root: bool,
    point: Point,
    parent: Rc<RefCell<Self>>,
    children: Vec<Rc<RefCell<Self>>>,
}

impl Node {
    fn new(point: Point, parent: Rc<RefCell<Self>>) -> Self {
        Self {
            point,
            ..Default::default()
            // Has to create `parent`
            // Calls <Rc<RefCell<Node>>>::default()
            // Has to create a Node
            // Calls <Node>::default()
            // Has to create `parent`
            // ...
        }
    }

You can't use Default unless you make that parent an Option or something.

OK, I'll leave it there. TL;DR, you'll be much better off not trying to implement a tree like this in Rust. It's a bad fit, especially as a project while you're still getting to know Rust.

Mandatory reading someone may have mentioned to you before.

  1. spoilers, it doesn't work currently ↩︎

  2. and then I decided I'd done enough ↩︎

1 Like
3

Parent links lead to sharing, and together with the need to update, that's shared mutability. Shared mutability is hard, bad, makes you cry, and kills kittens.

Don't use parent links via explicit pointers. If you need them, use node IDs and a separate (array or map) data structure to describe the child -> parent relationship. Or use a library designed for representing arbitrary graphs.

4

I don’t know if this is meant as just a placeholder, but this code doesn’t really do anything— The weak references can’t keep the Rcs alive in any case, and even if they did you drop them immediately.

In practice, you probably want the parent pointer to be a `Weak— Because you’re keeping a copy of all the roots, you don’t need the back references to avoid losing things. This will also take care of a lot of the infinite recursion for you. See this Playground for how that might work.

2 Likes
5

What do you mean about the redundancy here?

struct Node {
    // Redundant; if parent won't upgrade, this is the root.
    // is_root: bool,
    parent: Weak<RefCell<Self>>,
    ..
}

Do you mean

impl Node {
  fn is_root(&self) -> bool {
    // some logic to check if parent has upgraded? Weak::strong_count?
    if some_state_checker(self.parent) {
      true
    } else {
      false
    }
  }
}
6

Yes; either can be used. More specifically:

fn is_root(&self) -> bool {
    self.parent.strong_count() == 0
}

Or, perhaps more usefully:

    fn ancestors(mut this: Rc<RefCell<Self>>) -> impl Iterator<Item = Rc<RefCell<Self>>> {
        std::iter::from_fn(move || -> Option<_> {
            let parent = this.borrow().parent.upgrade()?;
            this = parent;
            Some(this.clone())
        })
    }
1 Like
7

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.