Newbie question on borrowing

help
1

Hello,

I'm new to rust and spend the last days to make myself acquianted with the basic concepts. Despite of reading the documentation as well as other resources, I have a hard time understanding what is going on in this trivial scenario:

trait Node<'a> {}

struct Root {}

struct Child<'a> {
    parent: &'a Node<'a>
}

impl <'a> Node<'a> for Root {}

impl <'a> Node<'a> for Child<'a> {}

fn main() {
    let root = Root { };
    let child1 = Child { parent: &root };
    let child2 = Child { parent: &child1 }; // this is fine
    let child3 = Child { parent: &child2 }; // <-- error: borrowed value does not live long enought
}

The compiler complains at the line where child3 is created, that the "borrowed value (&child2) does not live long enough". It also informs me that "values in a scope are dropped in the opposite order they are created". I'm fine with that, but cannot see why this is a problem here.

Any help is much appreciated!

Thanks
Martin

1 Like
2

For trees maybe a weak rc to the parent? Trying to do trees with & references is tricky - I ended up using Rc + RefCell for my tree with a weak rc to the parent.

3

Since you’re storing a trait object inside Child, you need to use 2 lifetime parameters:

struct Child<'a, 'b: 'a> {
    parent: &'a Node<'b>
}

You can sometimes get away with a single lifetime parameter for both the borrow and the type itself, but this doesn’t work when trait lifetime parameters are involved. I can elaborate if you’re interested.

1 Like
4

Thanks for your answer. I'll look into RC and RefCell when I figured out how lifetimes work. Currently, I'm not looking for an implementation of this specific data structure, but rather try to understand how the compiler works.

5

Thanks vitalyd. I'm trying to figure out what is going on here from the compiler's perspective. From what I have learned, all nodes created in the code from my original post are owned by the same scope ( = the main function), and are destructed in opposite order. Why does child2 not survive till the end of the scope?

Also, I do not understand how a second lifetime parameter fixes this. Can you elaborate more on this, please? Is this explained somewhere in the docs? Thanks again for your time.

6

It does survive - there's absolutely nothing wrong in your main() function. This is sort of what I meant in my reply in a sibling thread about being proficient with lifetimes: there's a difference between understanding lifetimes and deciphering error messages :slight_smile:.

In this case, the issue is a bit more complex because you're using a trait object for a trait with a lifetime parameter (i.e. &'a Node<'a>) . Before explaining this one, let's look at an example using only structs:

struct Node<'a> {
    parent: Option<&'a Node<'a>>,
}

fn main() {
    let root = Node { parent: None };
    let child1 = Node {
        parent: Some(&root),
    };
    let child2 = Node {
        parent: Some(&child1),
    };
    let child3 = Node {
        parent: Some(&child2),
    };
}

This compiles without any issue, even though on the surface it looks very similar: we have a &'a Node<'a> reference (the Option wrapper is unimportant). So it's the same lifetime parameter used for the reference as well as the Node type itself.

We can tell that the 'a in both positions is actually different in terms of real scopes for which the data is borrowed and for how long the referent is alive. However, the compiler is able to "squeeze down" the lifetime of Node<'a> such that this works out. In Rust this is known as subtyping/variance. One way to express it in layman's terms is "something with a longer lifetime can be substituted in places where a shorter lifetime is expected" - this is known as some type being variant - a more straightforward example might be Node<'static> can be used in any place where a Node<'a>, for some generic lifetime parameter 'a, is expected. There's more to be said about variance/subtyping, but I'll leave it at this to not go off into the weeds. We can talk about it some more if you'd like however.

Coming back to your case now. You're not using an ordinary struct, like the Node<'a> in my example. Instead, you have a trait object with a lifetime parameter. A trait object with a lifetime parameter is invariant - this is the opposite of what I wrote in the previous paragraph: you cannot substitute a longer lived one where a shorter one is expected.

Given this, &'a Node<'a> will require that the borrow of Node and the Node itself live for exactly the same lifetime - there's no "squeezing down" of anything allowed. So the compiler attempts to borrow child2 for its entire lifetime, and this makes things go sideways because the borrow is essentially extended to the entire main() block (that's why the compiler is telling you that child2 is dropped after the scope ends).

This is a good time to also mention that a feature coming soon, NLL, will fix your example code as-is. But, it's still important to understand what's going on here, I think.

By introducing two lifetime parameters, we can more explicitly express the relationship between how long we're borrowing a Node and how long the Node itself is valid for. &'a Node<'b>, where 'b: 'a, is saying we're borrowing the node for some lifetime 'a, but the node's valid lifetime (i.e. 'b) outlives it (this is necessary to express because otherwise you might hold a reference to a node for longer than it itself is valid for, e.g. its internal references go away prematurely).

Hope that helps. If something's unclear, let me know and I can try to elaborate.

5 Likes
7

Wow, thank you very much for this!

1 Like