Cyclic references and lifetimes

Question

I'm trying to create a struct that references itself (using Option<Box<>>). I can make something that works using just the struct, but I cannot make it compile when using some container for all of them.

This is the structure I'm trying to create (adapted from real example), that is able to create children that reference to the parent

pub struct Node<'a> {
    value: u32,
    parent: Option<Box<&'a Node<'a>>>,
}

impl<'a> Node<'a> {
    pub fn new_child(&'a self, value: u32) -> Node<'a> {
        Node {
            value,
            parent: Some(Box::new(&self)),
        }
    }
}

This works. However, when I try to build these nodes using a Graph-like container, the build fails:

Playground example

pub trait Graph {
    type NodeType;
    
    fn new_child(&self, value: u32) -> Self::NodeType;
}

struct GraphImpl<'a> {
    root: Node<'a>,
}

impl<'a> Graph for GraphImpl<'a> {
    type NodeType = Node<'a>;
    
    fn new_child(&self, value: u32) -> Self::NodeType {
        self.root.new_child(value)
    }
}

error:

   Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
  --> src/main.rs:32:9
   |
28 | impl<'a> Graph for GraphImpl<'a> {
   |      -- lifetime `'a` defined here
...
31 |     fn new_child(&self, value: u32) -> Self::NodeType {
   |                  - let's call the lifetime of this reference `'1`
32 |         self.root.new_child(value)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

error: could not compile `playground` due to previous error

I've tried adding different lifetime markers at many different places with no success. I've read different questions and answers and it's clear that I'm missing something (and I'm not understanding how lifetimes works in Rust :sad: ). I will really appreciate some help here... and some pointers so I can understand why it works (or it shouldn't work).

Thanks!

Does this answer your question? [Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct) — cafce25, Mar 27 '23 at 09:57
[Here's how you can fix you current problem, but it won't help you](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=02a0a594645eafe658347d0faee34823). — Chayim Friedman, Mar 27 '23 at 09:59
To make graphs, you would typically use an arena allocator. You can find a bunch of crates on crates.io under the tag [arena](https://crates.io/keywords/arena), you can read their description and pick the one that fits your usecase (most likely the first result, `typed-arena` will be fine for you). — jthulhu, Mar 27 '23 at 10:07
If you need to implement some recursive data structure you can do it only and only with pointers. See this book how it should to be https://rust-unofficial.github.io/too-many-lists/index.html — Hurry Blob, Mar 27 '23 at 11:23
@HurryBlob If by pointers you mean raw pointers, this is definitely not true. And even if you include all kinds of pointers, this is still not true - we have indices. — Chayim Friedman, Mar 27 '23 at 11:27
@ChayimFriedman yes, you are right. I mean the true-way for building recursive data structures. Another variants will make you troubles with borrowing, ownership, lifetimes and totally cloning. I talk about "how it should be" instead "how many ways we can do it". — Hurry Blob, Mar 27 '23 at 11:52
@HurryBlob "How it should be" depends very much on the exact problem. There is no general correct solution. And I think raw pointers are not the best even most of the time. They are last resort. — Chayim Friedman, Mar 27 '23 at 11:54
@ChayimFriedman It is not true. Rust has not another instruments to build RDS. Not children toys like code above, but efficiently, fast and memory less ways it is only and only pointers. I thankful for the dialogue. — Hurry Blob, Mar 27 '23 at 12:25
Please, don't focus on the `Graph`, `Node` names. It was a very bad naming choice. The real problem has nothing to do with a graph, I should have used `Parent` and `Child`. I understand [Why can't I store a value and a reference to that value in the same struct?](https://stackoverflow.com/questions/32300132/why-cant-i-store-a-value-and-a-reference-to-that-value-in-the-same-struct), but I don't think it is exactly this same use-case. Here the parent exist always before the child, lifetime _only_ needs to check that the child doesn't outlive its parent. — jgsogo, Mar 27 '23 at 21:22

score 1 · Answer 1 · answered Mar 27 '23 at 10:58

You can accomplish this as currently designed by forwarding the lifetime through the Graph trait:

pub trait Graph<'a> {
    type NodeType;
    
    fn new_child(&'a self, value: u32) -> Self::NodeType;
}

struct GraphImpl<'a> {
    root: Node<'a>,
}

impl<'a> Graph<'a> for GraphImpl<'a> {
    type NodeType = Node<'a>;
    
    fn new_child(&'a self, value: u32) -> Self::NodeType {
        self.root.new_child(value)
    }
}

This self-referential approach is pretty unidiomatic in rust, and I fear that it will not scale up well to larger examples. It's a lot more straightforward to build graphs out of indices into nodes stored in a flat vector, and avoid this entirely.

I shouldn't have used `Graph` and `Node` for my example. It was the first thing that came up to my mind when simplifying what I have in practice. The question is not about a graph, but about making it work (or maybe I need to think something else). I didn't want to touch the `trait` because it will force me to modify other implementations as well, but glad to see there is a _workaround_. I need to think about it. Thanks! — jgsogo, Mar 27 '23 at 21:12

Cyclic references and lifetimes

1 Answers1