How do I create a Rust struct that can link to another instance of itself?

Question

I'm trying to create a chain of struct instances, like this:

Struct_instance_a:
id:1
prev:None

Struct_instance_b:
id:2
prev:Struct_instance_a

etc..

But getting this error from the compiler:

error[E0382]: borrow of moved value: `a`
error[E0382]: borrow of moved value: `a`
  --> src/main.rs:31:9
   |
28 |         let a = crate::Node::new(None, 1);
   |             - move occurs because `a` has type `Node`, which does not implement the `Copy` trait
29 |         let b=crate::Node::new(Some(a), 2);
   |                                     - value moved here
30 |
31 |         assert_eq!(a.id, b.prev.unwrap().id);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ value borrowed here after move

This is my code snippet:

fn main() {
    println!("hello");
}

pub struct Node {
    prev: Option<Box<Node>>,
    id: u64,
}

impl Node {
    fn new(prev: Option<Node>, id:u64) -> Node {
        Node {
            prev: match prev {
                None => None,
                Some(prev) => Some(Box::new(prev))
            },
            id
        }
    }
}


#[cfg(test)]
mod tests {

    #[test]
    fn test_children() {
        let a = crate::Node::new(None, 1);
        let b = crate::Node::new(Some(a), 2);

        assert_eq!(a.id, b.prev.unwrap().id);
    }

}

I'm new to Rust and trying to understand why this doesn't work. So far I've read about ownership and borrowing and lifetimes and tried a few combinations of those. It feels like I'm close to the solution but missing some fundamental piece of knowledge yet.

Answer 1

When you do Node::new(some(a), 2), then a is no longer accessible, it's ownership now belongs to b.

That's why, when you later do a.id it says value borrowed here after move, you moved the ownership to b, therefore you can't do a.id. The only way to access a is through b.prev.unwrap() (which is what you did.

If you want for the Node a to be accessible from both a and b.prev there's many ways to do that.

One of the ways involve not moving the value at all (so b never has ownership of a to begin with). This can be done with references:

fn main() {
    println!("hello");
}

pub struct Node<'inner_node> {
    prev: Option<&'inner_node Node<'inner_node>>,
    id: u64,
}

impl<'inner_node> Node<'inner_node> {
    fn new<'a>(prev: Option<&'a Node<'a>>, id: u64) -> Node<'a> {
        Node {
            prev,
            id
        }
    }
}


#[cfg(test)]
mod tests {

    #[test]
    fn test_children() {
        let a = crate::Node::new(None, 1);
        let b = crate::Node::new(Some(&a), 2);

        assert_eq!(a.id, b.prev.unwrap().id);
    }

}

This introduces lifetime annotations, which might not be what you want. In that case, you can use the RC struct, which is a smart pointer that allows a value to have multiple owners at the cost of some run-time checks:

use std::rc::Rc;

fn main() {
    println!("hello");
}

pub struct Node {
    prev: Option<Rc<Node>>,
    id: u64,
}

impl Node {
    fn new(prev: Option<Rc<Node>>, id: u64) -> Node {
        Node {
            prev,
            id
        }
    }
}


#[cfg(test)]
mod tests {
    use std::rc::Rc;


    #[test]
    fn test_children() {
        let a = Rc::new(crate::Node::new(None, 1));
        let b = crate::Node::new(Some(a.clone()), 2);

        assert_eq!(a.id, b.prev.unwrap().id);
    }

}

Note that for this to work we are doing a.clone(). This clones the RC pointer, it doesn't clone the node. So now there exists 2 pointers (a and b.prev) but only 1 (excluding b itself) Node.

One of the disadvantages of RC is that now the value inside is immutable. If you need to mutate the nodes, they would have to be Rc<RefCell<Node>> instead of Rc<Node>.

RefCell is another smart pointer, just like Rc. Where Rc allows a value to have multiple owners, RefCell allows to obtain a mutable reference (via run-time checks) to the inner object even if the RefCell itself is not mutable. By combining Rc and RefCell you can have multiple owners that can mutate the value.

Answer 2

I realized that I actually don't need to reference a directly once it's within b. Referencing just from b is enough. I updated my test to look like this and now it passes:

#[test]
    fn test_children() {
        let a = crate::Node::new(None, 1);
        let b = crate::Node::new(Some(a), 2);

        assert_eq!(1, b.prev.unwrap().id);
    }