Recursive lifetime issue: child holding a reference to a parent of the same type

help
1

Hi!
I need to have a tree-like data structure, where every node is the same type, and where each child references it's parent. I tried different things, and eventually found one working, but I can't tell why it's working.
Some minimal example code is here in the playground.

In short, I want somthing like:

pub enum Tree<'parent> {
    Root,
    Child(&'parent Tree<'idk-what-to-put-here>),
}

Of course, this code doesn't work.

The solution I found (in the playground) is really weird:

enum Tree<'parent, 'grandparent> {
    Root,
    Child(&'parent Tree<'grandparent, 'parent>),
}

In the 0 field of Child, the 'grandparent and 'parent lifetimes are... inverted? compared to the order of the arguments in the struct. It's weird.

The closest post I found about this problem is this one, but I couldn't find a satisfactory answer here.

Can someone give me an explanation to this? And eventually a better solution?

2

Temporary references are a wrong feature for this.

  1. Self-referential structures are not allowed by the borrow checker in any way. Such cyclic dependency won't work in any useful way.

  2. Rust references are forbidden from storing data, by design. They are for borrowing data, which by definition is the opposite of owning (storing, permanently holding) data. &Child in a Tree struct is a promise that the Child object is not stored in the Tree. If you're hoping to make this a data structure holding tree nodes, then it's promising the opposite of what you want.

You should use owned objects (remove all &). Use Rc or Arc to have pointer indirection, and Weak to have a parent pointer if you must.

Alternatively, store all nodes in an arena, and then build a tree out of references into the arena (this will be limited to living in a scope where the arena lives, so it's suited for temporary trees that won't be stored/returned into larger scope). Arena implementation details require unsafe code, but you can find existing crates implementing it.

4 Likes
4

It probably still doesn't actually work in a useful way. The nested lifetimes, along with recursively swapping the left and right parameters, means that you still have something akin to your other attempt:

    pub enum Tree<'parent> {
        Root,
        Child(&'parent Tree<'parent>),
    }

Because the two lifetimes are actually forced to be the same. So we might as well go back to that version.[1]

The only reason this didn't compile:

    impl<'parent> Tree<'parent> {
        pub fn make_child(&self) -> Tree<'_> {
            Self::Child(self)
        }
    }

Is because you used the Self alias, which is aliasing Tree<'parent> exactly, meaning you would have to have a &'parent Tree<'parent> to pass in. Making self: &'parent Self is one way to make it compile, or you could instead use Tree::Child instead of Self::Child.

    impl<'parent> Tree<'parent> {
        pub fn make_child(&self) -> Tree<'_> {
            Tree::Child(self)
        }
    }

However, chances are low that you actually want something like this in practice, for the reasons @kornel outlined. (Just because it compiles doesn't mean it will be useful.)

  1. But here's an explanation of why that version compiled in case you want to know. ↩ī¸Ž

1 Like
5

Simply put, you are trying to express run time dynamic borrow scopes with compile tile scopes, witch obviously won't work.

6

Ok, thanks you all for the answers.

I finally found the solution, as quinedot mentioned:

That's something I had in mind with the return type, but not the actual enum construction.

I will use this solution, rather than an arena, because this tree is not meant for storage nor runtime flexibility. The entire tree structure will be stored in the stack, and lifetimes will be predictable, hardcoded. There will be no self-references, because the parents and the childs will be owned by the current scope, in the stack (the parent will never own the child).