Help with Complex Lifetimes

Hi there,

I am having trouble making the code below work. I have created something very close to a minimum example; playground can be found here:

The idea of the code is that there are a bunch of Entity classes that all get deserialised from disk by serde; Unit being one example. The entities are then added to an EntityPool and now the Entity has to be informed about which EntityPool it lives in (so it can look up other adjacent Entities in the same pool later).

So, that means that the Entities need a reference to the EntityPool. I understand that storing references in a struct is not great (someone on this forum has pulled me up on this before and I have taken that to heart). However, in this case I cannot see the alternative; clearly I cannot clone() the EntityPool as that would be defeating its purpose.

So, I sprinkled some 'a lifetime specifiers over the code and things improved, but I cannot figure out how to make this actually work. I am left with

error[E0308]: method not compatible with trait
  --> src/main.rs:22:5
   |
22 |     fn init(&mut self, pool: &'a EntityPool) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
   |
   = note: expected fn pointer `fn(&mut Unit<'a>, &'a EntityPool)`
              found fn pointer `fn(&mut Unit<'a>, &'a EntityPool)`

...which makes little sense to me. My feeling is that some of the 'a lifetime specifiers refer to the same thing while others do not. Could somebody please have a look at it? Here is the code:

use serde::Deserialize;
use serde_json;

/// EntityPool
pub struct EntityPool {
    // implementation omitted
}

pub trait Entity {
    fn init<'a>(&mut self, pool: &'a EntityPool);
}

#[derive(Deserialize)]
pub struct Unit<'a> {
    #[serde(skip)]
    pool: Option<&'a EntityPool>,

    key: String,
    name: String,
    description: Option<String>,
}

impl<'a> Entity for Unit<'a> {
    fn init(&mut self, pool: &'a EntityPool) {
        self.pool = Some(pool);
    }
}

fn main() {
    let ep = EntityPool {};
    let v = r#"
    {
        "key": "m",
        "name": "millimeter",
        "description": "some really small distance"
    }
    "#;

    let mut unit: Unit = serde_json::from_str::<Unit>(v).unwrap();
    // ep.add(unit); -- omitted
    unit.init(&ep);
}

More generally, I have reread the chapter in the book on lifetimes and all seems simple enough. It seems to be those complex cases that I cannot find good explanations for. For example what does a lifetime specifier on an impl, e.g. impl<'a>... actually mean? Could someone maybe point me to something I could read to fill that gap in my knowledge. Again, thank you for your generous time.

I move the lifetime to the struct, and declare the 'b is supertype of 'a.

use serde::Deserialize;
use serde_json;

/// EntityPool
pub struct EntityPool {}

pub trait Entity<'a> {
    fn init(&mut self, pool: &'a EntityPool);
}

#[derive(Deserialize)]
pub struct Unit<'a> {
    #[serde(skip)]
    pool: Option<&'a EntityPool>,

    key: String,
    name: String,
    description: Option<String>,
}

impl<'a, 'b: 'a> Entity<'b> for Unit<'a> {
    fn init(&mut self, pool: &'b EntityPool) {
        self.pool = Some(pool);
    }
}

fn main() {
    let ep = EntityPool {};
    let v = r#"
    {
        "key": "m",
        "name": "millimeter",
        "description": "some really small distance"
    }
    "#;

    let mut unit: Unit = serde_json::from_str::<Unit>(v).unwrap();
    unit.init(&ep);
}

Clearly, that is the case: your original init is itself generic over the lifetime called 'a, while in your impl, you do not make it generic, you make it inherit the lifetime 'a from the impl block.

Maybe it's easier to understand using an analogy, if I translate it from lifetime-land to type-land – the following code does not compile for the same reason:

trait Foo {
    // this says there must be a separate `Foo::foo<T>` function
    // _for every possible_ type `T`
    fn foo<T>(value: T);
}

struct Bar<T>;

impl<T> Foo for Bar<T> {
    // However, this says that `<Bar as Foo>::foo()` is
    // _one_ specific function for a _pre-set_ type `T`.
    // If you know your 1st-order logic, you know these
    // are very different beasts!
    fn foo(value: T) {
    }
}
3 Likes

The error was copying names from your code, so it's a little more clear if you rename the 'a in the trait declartion to 'b. But only a little.

impl<'a> means "I'm implementing something for a generic lifetime, which I'm calling 'a". Within the impl block, every 'a must refer to the same lifetime. (But only inside a block -- just like you can have totally different variables named foo in different functions.) So in your OP code, this:

impl<'a> Entity for Unit<'a> {
    fn init(&mut self, pool: &'a EntityPool) {
        self.pool = Some(pool);
    }
}

Is saying "I'm implementing Entity for Unit<'a> where 'a can be any lifetime. This is the definition for fn init, which takes &mut self and a reference to an EntityPool, which has the same lifetime, 'a, as Unit<'a>."

This is where the compiler chokes, because the function declaration in the trait declaration was:

fn init<'a>(&mut self, pool: &'a EntityPool);

Which says "this trait has a fn init which is generic over any lifetime, which I'm calling 'a; it takes a &mut self and a reference to an EntityPool with lifetime 'a." Note that 'a here is uncontrained, it could be any lifetime. If you implement the trait, this function in your impl must accept any lifetime. But when you tried to define it, you said it had to be the same as the Unit<'a> lifetime.

Looking at it from the other direction, init is supposed to be callable with a EntityPool reference of any lifetime. But you're only defining it when the reference lifetime is at least as long as that of Unit<'a>. Now, this is what you want -- if you called it with a lifetime shorter than that of Unit<'a>, there are going to be lifetime problems -- but it doesn't match the trait declaration.

Next let's consider @araloren's fix. First, they make trait Entity generic over a lifetime, and use that lifetime in the declaration of fn init.

pub trait Entity<'a> {
    // &'a is now constrained by the trait impl
    fn init(&mut self, pool: &'a EntityPool);
}

This means that init no longer takes a reference to an EntityPool with any lifetime, it takes one with a lifetime specific to the trait. One could implement the trait for only the 'static lifetime, for example; the function would then require the 'static lifetime on the pool parameter.

Then, in the impl Entity for Unit, they declare and use two generic lifetimes, 'a and 'b.

impl<'a, 'b: 'a> Entity<'b> for Unit<'a>

'b: 'a means that 'b outlives 'a. So then saying Entity<'b> for Unit<'a> means, "I'm implementing Entity<'b> for Unit<'a> where 'b outlives 'a". In particular, they're not implementing it when 'a outlives 'b -- or in terms of the fn init parameters, the &'b EntityPool reference must last longer than the Unit<'a> (which you are putting it into).

This describes exactly what you want. But let's consider one more variation which also works for this use case. We'll keep the generic trait but implement it like this instead:

impl<'a> Entity<'a> for Unit<'a> 

Why does this also work? If you call unit.init(&ep) in a situation where the lifetime of &ep is longer than that of unit, the compiler is happy to coerce the lifetime to match by shrinking it. You may see this in the wild, as it's easier to type and arguably easier to reason about.

Thank you so much for providing me with those elaborate answers. I feel like that got me a lot closer to putting the full puzzle together. If you would bear with me, with your help, I will poke a little bit deeper.

Lifetime Specifier Scope

One thing I have not read anything much about is the scope of a lifetime parameter. Some of you touched on that a little further up. It seems to be the case that each lifetime specifier has some sort of scope depending on the context. Let me summarise my assumptions and you put me right should I get it wrong.

Functions

fn foo<'a, 'b>(para_a: &'a String, para_b: &'b String) -> &'b String {
    para_b
}

I assume that the function itself is the scope; all lifetime specifiers declared by fn foo<'a, 'b> that have the same name refer to the same lifetimes specifiers. That is, the 'b in the para_b is the same 'b declared in the return parameter.

Structs

pub struct EntityPool<'c> {
    key: &'c String,
    name: &'c String,
}

The lifetime specifier 'c is referring to the same lifetime throughout.

Methods

impl<'a, 'd> EntityPool<'d> {
    fn moo<'c>(para_a: &'a String, para_b: &'d String, para_c: &'c String) -> &'d String {
        para_b
    }
}

Let's look at the impl block above in the context of the struct declared prior. The impl declares 'a and 'd. The same 'd is then used on EntityPool while the same 'a is used in the method itself. 'a and 'd are "inherited" by the method, while 'c is declared locally on the method. I assume that for a single method in the impl block that makes little difference, but if there was a second method moo2

fn moo2<'c>(para_a: &'a String, para_b: &'d String, para_c: &'c String) -> &'d String {
    para_b
}

...then we would have tied the lifetimes of its parameters para_a and para_b to the lifetimes of the corresponding parameters in moo, right? 'c, I assume, remains unconstraint as it is declared locally in each case.

Does the compiler tie the 'c on struct EntityPool<'c> to the 'd in impl<'a, 'd> EntityPool<'d>? What does that relationship look like?

Traits

pub trait Entity<'a> {
    fn init(&mut self, pool: &'a EntityPool);
}

I assume, this works analogous to structs further up. The 'a in the declaration is "inherited" by the method, but the method could naturally also declare its own or additional lifetime specifiers. When one then implements the trait for a struct, as in

impl<'a, 'b: 'a> Entity<'b> for Unit<'a> {
    fn init(&mut self, pool: &'b EntityPool) {
        self.pool = Some(pool);
    }
}

does the compiler bind the 'a from the trait declaration to the 'b of the implementation?

Sorry, this got a bit long, but I feel this has not been covered well in either the book or any other articles as far as I can tell. It might seem trivial, but I don't think this goes without saying.

My advice overall is to follow @H2CO3's lead and substitute generic type parameters for lifetime parameters when you're working out what they mean on this level. If you already understand generic types, it will generally give you the right idea.

Yes, you got it.

Yes , EntityPool is generic over a lifetime, and the references key and name share that lifetime.

To be honest, I'm surprised there's not an "unconstrained lifetime" error for 'a in this example. But to answer the first question, yes, all the same-named 'a and 'd parameters are tied together.

I wouldn't say they're tied together, really. The blocks stand alone; changing one isn't going to change the meaning of the other from a distance. They're only "tied together" insomuch as one defines the data structure, and the other defines an associated function for that data structure. All uses of the data structure must conform to its definition, including within the impl. (So the two references within must always have the same lifetime, for example.)

The 'c on struct EntityPool<'c> indicates that the struct is generic over a lifetime, and in the rest of the declaration, that lifetime can be named using 'c -- and is used to declare that the lifetime is that of the two references contained within the data structure. The 'd in impl<'a, 'd> is because this implementation is generic over two lifetimes, one of which we're calling 'd. And we're implementing for the struct EntityPool<'d> -- because there are no further predicates (where clauses, etc) we're implementing for every possible lifetime EntityPool<'_> may take, every possible concrete type based on the generic EntityPool<'_>.

Here in particular is where I appeal to @H2CO3's suggestion of how to think of this. If we had a struct Vec<T> { /* ... */ } , we could later do:

impl<U> Vec<U> {
    fn len(&self) -> usize { /* ... */ }
}

We're defining length no matter what kind of type is being stored in our Vec. It's sort of like saying "I don't care what the type is". If we add some where clauses or used U: Clone or whatever, we'd be saying "I don't care what the type is, provided it meets these conditions". And if we dropped the generic U and used impl Vec<SomeConcreteType> instead, we'd be saying "I'm only implementing for this one concrete type".

These all work the same way with lifetimes. impl<'a> means I don't care about what lifetime, impl<'a, 'b: 'a> is putting conditions on the lifetimes but is still generic, and impl SomeType<'static> is only implementing for the concrete type with a static lifetime.

Yes -- in fact, it is already doing so in your example, but the lifetime has been elided. This is equivalent:

    fn init<'s>(&'s mut self, pool: &'a EntityPool);

(More about lifetime elision.)

Same as before, I wouldn't put it this way; they don't change each other's meanings. You can either implement a concrete trait like Entity<'static> (or From<usize>), or implement a trait generically with some lifetime parameter (or type parameter). Rust wants you to be explicit about which, and if you're going the generic route, you moreover explicitly declare the generic parameters with the impl<...>. It doesn't change what the trait is. It's how to specify you're writing a generic implementation and how to give the generic parameters names.