CODEWITHSUNDEEP
structreferencecircular-referencerust
Grumdrig
Grumdrig

Reputation: 16975

What lifetimes do I use to create Rust structs that reference each other cyclically?

I'd like to have struct members that know their parent. This is approximately what I'm trying to do:

struct Parent<'me> {
    children: Vec<Child<'me>>,
}

struct Child<'me> {
    parent: &'me Parent<'me>,
    i: i32,
}

fn main() {
    let mut p = Parent { children: vec![] };
    let c1 = Child { parent: &p, i: 1 };
    p.children.push(c1);
}

I tried to appease the compiler with lifetimes without completely understanding what I was doing.

Here's the error message I'm stuck on:

error[E0502]: cannot borrow `p.children` as mutable because `p` is also borrowed as immutable
  --> src/main.rs:13:5
   |
12 |     let c1 = Child { parent: &p, i: 1 };
   |                               - immutable borrow occurs here
13 |     p.children.push(c1);
   |     ^^^^^^^^^^ mutable borrow occurs here
14 | }
   | - immutable borrow ends here

That makes some sense, but I'm not at all sure where to go from here.

Upvotes: 36

Views: 9257

Answers (1)

Chris Morgan
Chris Morgan

Reputation: 90852

It is not possible to create cyclic structures with borrowed pointers.

There is not any good way of achieving cyclic data structures at present; the only real solutions are:

  1. Use reference counting with Rc<T> with a cyclic structure with Rc::new() and Rc:downgrade(). Read the rc module documentation and be careful to not create cyclic structures that use strong references, as these will cause memory leaks.
  2. Use raw/unsafe pointers (*T).

Upvotes: 31

Related Questions