Lifetime in many ways are similar to types but also different. The goal of this post is to explain my mental model of rust's lifetime binding works, when it takes place, and a trick to force late lifetime binding when needed.
Here's a motivating example that I will use throughout this post.
// ========== concrete.rs ===========
// Foo<'_> implements ValueTrait defined in generic.rs
struct Foo<'a> {
value: &'a str
}
impl<'a> ValueTrait for Foo<'a> {
fn get_value(&self) -> &'a str {
self.value
}
}
// Here's a concrete implementation of how to build a Foo with &str
// with lifetime annotation explicitly spelled out
fn build<'b>(s: &'b str) -> Foo<'b> {
Foo {value: s}
}
// ======== generic.rs =========
// A trait that's implemented by a few different structs
trait ValueTrait {
fn get_value(&self) -> &str;
}
// A generic function that works for different types that implement
// the ValueTrait and different `build` functions.
fn generic_function<???>(build) {...}
The goal is to figure out how to write the function signature of generic_function.
Take 1 – the straight forward approach
The most straight forward approach is to write generic_function as
fn generic_function<T, F>(build: F)
where F: Fn(&str) -> T,
T: ValueTrait {...}
And the callsite would look like the following, with the concrete build function,
generic_function(build);
The code doesn't compile. Here's the playground link. It produces the following not-very-helpful error message.
Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
--> src/main.rs:29:5
|
29 | generic_function(build);
| ^^^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
|
= note: expected struct `Foo<'_>`
found struct `Foo<'_>`
note: the lifetime requirement is introduced here
--> src/main.rs:20:22
|
20 | where F: Fn(&str) -> T,
| ^
Isn't Foo<'_> the same as Foo<'_>? What is going on here?
Take 2 – specialize and work our way back
It works fine if we remove the generic over T. The following compiles (playground)
fn generic_function(build: impl Fn(&str) -> Foo) {
The above desugars to
fn generic_function<F>(build: F)
where F: for <'a> Fn(&'a str) -> Foo<'a> // here we uses the syntax for HRTB (https://doc.rust-lang.org/nomicon/hrtb.html)
which still compiles (given that I desugared it correctly).
Now let's add the generic argument T into the desugared version (playground).
fn generic_function<T, F>(build: F)
where F: for <'a> Fn(&'a str) -> T<'a>
{
The compiler is not happy but with a different error message.
Compiling playground v0.0.1 (/playground)
error[E0109]: lifetime arguments are not allowed on type parameter `T`
--> src/main.rs:20:36
|
20 | where F: for <'a> Fn(&'a str) -> T<'a>
| - ^^ lifetime argument not allowed
| |
| not allowed on type parameter `T`
|
note: type parameter `T` defined here
--> src/main.rs:19:21
|
19 | fn generic_function<T, F>(build: F)
| ^
The error message here would make more sense later; but for now it's kind of weird (and rustc --explain E0109 is not helpful). But it's OK, we can remove <'a> from T<'a> in the return position of the trait bound (this would later turn out to be the key).
fn generic_function<T, F>(build: F)
where F: for <'a> Fn(&'a str) -> T,
T: ValueTrait
{
This time (playground) it gives us a more useful error message, because we gave one lifetime a name,
error[E0308]: mismatched types
--> src/main.rs:29:5
|
29 | generic_function::<Foo, _>(build);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
|
= note: expected struct `Foo<'a>`
found struct `Foo<'_>`
It's saying we are expecting Foo<'a> which makes sense due to the trait bound on F, but we are providing Foo<'_> from the callsite. In the first attempt, we got error message saying "expecting Foo<'_> but got Foo<'_>; these two '_ s are different. One is the unresolved lifetime from the HRTB where F: for <'_> Fn(&'_ str) -> T, while the other is from the callsite generic_function::<Foo<'_>, _>. It only becomes obvious now, after we give the HRTB lifetime a different name.
Early vs. late lifetime binding
At a high level there are three steps performed by the rust compiler before it performs the borrow checking,
- desugaring
- monomorphism
- lifetime binding
Turns out a "more correct" version should be
- desugaring
- monomorphism + early lifetime binding
- late lifetime binding
More details can be found at the appendix of RFC3216 and Niko's blog post. The gist of it is that if a type (say T) is needed for monomorphism (e.g. stamping out an instance of a generic function), the lifetime is bound at the same time (early). Otherwise, the compiler would perform late lifetime binding, meaning that it would happily leave the lifetime stay generic, and only resolve it when it's used.
Now the earlier error messages start to make more sense. In the case of
fn generic_function<T, F>(build: F)
where F: for <'a> Fn(&'a str) -> T,
T: ValueTrait
{
the compiler needs to know T in order to stamp out the code for the function; hence it performs early binding for the lifetime - T becomes Foo<'_> from the caller. After the code is stamped out, the compiler starts late lifetime binding. HRTB's lifetime is late bound. At the place where we actually call build, in the body of the generic function, it binds 'a to the regional scope, which means T gets resolved to Foo<'a>. Conflict! That's exactly the error message we got earlier.
Remember earlier the compiler doesn't allow us to write T<'a> in the return position of the trait bound?
fn generic_function<T, F>(build: F)
where F: for <'a> Fn(&'a str) -> T<'a>
{
It makes sense now because T is early bound, while the HRTB's lifetime is late-bound. T<'a> in a HRTB doesn't make sense.
Take 3 – force late lifetime binding
We still haven't solved the original problem yet. We want to have a generic function over a type that implements ValueTrait and a build function. Here's a trick – credit to my colleague CJ that leverages GAT. Another problem solved by an extra level of indirection.
struct Foo<'a> {
value: &'a str
}
trait ValueTrait {
fn get_value(&self) -> &str;
}
impl<'a> ValueTrait for Foo<'a> {
fn get_value(&self) -> &'a str {
self.value
}
}
trait Builder {
type ValueType<'c>: ValueTrait;
fn build<'b>(s: &'b str) -> Self::ValueType<'b>;
}
struct FooBuilder{}
impl Builder for FooBuilder {
type ValueType<'c> = Foo<'c>;
fn build<'b>(s: &'b str) -> Foo<'b> {
Foo {value: s}
}
}
fn generic_function<BUILDER>()
where BUILDER: Builder
{
let owned = "123".to_string();
let built = BUILDER::build(owned.as_str());
println!("{:?}", built.get_value());
}
fn main() {
generic_function::<FooBuilder>();
}
generic_function is generic over a type that implements the Builder trait, with no lifetime associated. The compiler will only use the concrete type FooBuilder to stamp out a new version of the generic_function while the lifetime for build is not bound until it's called in BUILDER::build(owned.as_str()), at which point, the lifetime will resolve correctly to the regional scope - the body of the function - this behavior is what we want since the very beginning, and this is late life time binding.
Why doesn't rust make all lifetime late binding
Based on https://rustc-dev-guide.rust-lang.org/what-does-early-late-bound-mean.html#making-more-generic-parameters-late-bound, it looks like people generally agree late-binding is generally a good thing to have. Looks like the priority of making more things support late lifetime binding is just lower priority compared to other things for rust at the moment.
Unfortunately, information about early vs. late lifetime binding is scatter. In the meantime, I hope this post clears things up a bit.