Does GAT include “owned” as a lifetime value

Inspired by the clarity of the following:

... a statement I know is true.

Is it ok to say that the only reason we need to parameterize lifetimes is because it’s a compile-time analysis? Or is it because the compiler only performs the analysis “one function at a time”.

Otherwise, when lifetime types can’t be inferred (multiple possibilities), why not fail only when the caller creates the case that violates the rules?

The answer has to be more a limitation of only interpreting “one function at a time”... which means we can navigate lifetimes with more inference by combining logic under a single scope. Perhaps self-evident because each new scope creates a new opportunity to create a new lifetime type.

Bear with me. This matters because it might help better understand lifetimes - they are what they’re good for.

Part of this “churning” on lifetimes has todo with the contrast with “traditional” type parameters where the end user creates a concrete type with values that have constructors of a specific type. E.g., Vec<MyType> happens with vec![MyType{}].

This is not the case for lifetimes. They are more like values, not a type parameter (this conflicts with my understanding that a rust type has two kind parameters to create a type, lifetime kind and type kind)

  1. They don’t have constructors so can’t be “typed”; the best I could think of is scope as the constructor.

  2. Lifetimes are not absolute but relative (so a single lifetime only has meaning in relation to the lifetime of the app; similarly, single scope, single lifetime type; in contrast, String means something on its own).

  3. ‘static is a value of a lifetime that lasts as long as the app (relative equality); but equating lifetimes to that of the app is likely not the best description because lifetime values only have meaning in relation to other lifetimes. So, ultimately values as “always the longest” or “always long enough” by the compiler (where many values can be qualified as such).

... lifetimes help the compiler compiler make conclusions “one function at a time”. It has no use beyond that.

GATs will work for the lifetime kind but not type kind (as best I can determine). What range of lifetimes does the new parameter enable?

  1. ‘a parameter accepts what as values?

  2. What value can I use when there is no lifetime? (owned values); is borrow & owned “a bridge too far”

  3. Concretely, where I had to implement many instances of a trait, where can I specify just one using a GAT?

Thanks in advance to anyone that can help me reconcile the above.

Because it's a compile-time analysis. Keep in mind that the compiler could analyze multiple function bodies at once. So the function signatures should give all the necessary information. This requires lifetimes to be parameterized.

Lifetime analysis is done by a limited form of SAT solving. Limited, because we want to solve our problems in a reasonable amount of time, but not too limited that we exclude many useful programs.

Rust does have two kinds (in the type theoretic sense), lifetimes and types (actually 3 once const_generics lands, we'll also have terms).

Most lifetimes don't have explicit constructors, but that doesn't really matter. you can infer lifetimes. (Analogous to how you can infer types)

A single lifetime can be thought of as a single scope. Sure, scopes can relate to other scopes, similar to how Strings can relate to other Strings. There are other ways to interpret lifetimes, which may or may not be more useful (depending on context).

Your last definition is the best, "always long enough".

It will eventually work for both, but lifetimes are easier exactly because their analysis is simple (compared to trait solving, not to discount lifetime solving).

A lifetime, who's value is almost always inferred by the compiler. But its value could also be provided by lifetime parameter or as 'static

This is ambiguous

trait Foo {
    type Bar<'a>;
}

struct FooImpl;

impl Foo for FooImpl {
    type Bar<'_> = FooImpl;
}

fn use_foo<F: FooImpl<Bar<'_> = FooImpl>>

Which of 'a or the two '_ do you mean when you say 'a

I go over some code in Generalizing over Generics in Rust (Part 1) - AKA Higher Kinded Types in Rust | Rusty Yato that would greatly benefit from GATs (the subject of a future Part 2). The basic idea is that instead of doing

trait OneTypeParam<T> {
    type This;
}

You would do

trait OneTypeParam {
    type This<T>;
}

Which has some subtle differences, but the same general idea. This allows you to greatly reduce boilerplate when using OneTypeParam (Especially when you need to be generic over a number of different types T)

3 Likes

I think it's better to think of lifetimes as like types, but chosen by the compiler, not the programmer. They're definitely not value-like, because they don't have any runtime existence and they don't affect code generation.

Because lifetimes are chosen by the compiler and not by you, you can't materialize one out of thin air and say "use this lifetime"; all you can say is things like "if you give me a reference that lives for at least some lifetime, let's call it 'a, I can give you back a reference that also lives for at least 'a." That's why named lifetimes only show up as parameters (except 'static). You don't pick lifetimes; you work with what the compiler gives you.

Note that for almost all programs there are many different ways to assign lifetimes that will work. It's also not defined exactly what the extent of any actual lifetime is (except in trivial cases). The compiler has complete free rein to pick any lifetimes that let the program compile. (Strictly speaking, it doesn't even have to actually choose a lifetime; it only has to prove that one must exist.)

Right, this is the "chosen by the compiler" bit. But note that lifetimes don't have to correspond to scopes; under stacked borrows they actually correspond to portions of the control flow graph, which may not bear any relation to lexical scopes. —edit to clarify: Stacked Borrows is not a compile-time analysis; it's a model to explain what kind of aliasing is and isn't OK. The static analysis that rustc does during borrow checking is a more conservative layer on top of what SB technically allows. Rust has had three borrow checkers that do different kinds of analysis: (old) scope-based, (current) MIR-based aka "non-lexical lifetimes" and (experimental, nightly-only) Polonius. If you want to understand how the compiler actually does the analysis, I suggest starting with the NLL tag on nikomatsakis's blog.

3 Likes

To answer the question in the title, no GAT doesn't include an "owned" lifetime. Instead, let's consider this example:

trait Foo {
    type Bar<'a>;
    fn get_bar<'a>(&'a self) -> Self::Bar<'a>;
}

impl Foo for Bar {
    type Bar<'a> = &'a str;
    fn get_bar<'a>(&'a self) -> &'a str {
        ...
    }
}

So in the above, the type constructor Bar can take a lifetime and produce some type. E.g. if we call Bar::get_bar<'a>, then it has the return type &'a str. If we instead call Bar::get_bar<'b>, then we get the different return type &'b str. By doing this, the returned &str is tied to the lifetime on &self.

However, if we change it to

impl Foo for Bar {
    type Bar<'a> = String;
    fn get_bar<'a>(&'a self) -> String {
        ...
    }
}

Now, suddenly, if we call Bar::get_bar<'a>, we get the type String. But also, if we call Bar::get_bar<'b>, we also get the same type String. By not having the resulting type depend on the lifetime, the type becomes owned.

So there's no "owned" lifetime value, because with GAT you are choosing a function that takes a lifetime, not a lifetime. When you choose a function that returns the same type for all lifetimes, it is owned, but when the function returns different types, it is not.

4 Likes

Thank you for all of the responses. Good stuff to mull-over.

A quote that is starting to have me understand the lifetime and ownership range is from @alice

“...returns the same type for all lifetimes” is the encoding of ownership in this “lifetime” vernacular.