Why can lifetimes not be inferred?

For your example there are already two different lifetime annotations that work:

  • unified input lifetime:

    fn longest<'a> (x: &'a str, y: &'a str) -> &'a str
    
  • minimum lifetime on output (unified output)

    fn longest<'a, 'x: 'a, 'y: 'a> (x: &'x str, y: &'y str) -> &'a str
    

Even if in this case both are equivalent in usage (thus an arbitrary choice could be made), I could image that not being always the case.

Moreover, in general, the types (and lifetimes!) appearing at the function header define its "API", i.e., how it should be called.

It is a better strategy to explicit the "API" of a function, thus forcing the implementation to be consistent with the header, than the other way around: letting the "API" be inferred from the implementation, since it leads to implicit (potentially breaking) API changes every time the implementation changes.

9 Likes

Thanks for pointing that out, Yandros. I guess, the second valid annotation will be covered in the section 'Advanced lifetimes', so I will read on happily...

The second one is a trick involving a technical thing behind lifetimes: variance.

I added a third lifetime parameter 'a which cannot be bigger than 'x nor bigger than 'y (i.e., which must smaller or equal than the minimum of 'x and 'y), thus being a valid output value (since a &'x str can thus be seen as a reference with a shorter or equal lifetime: &'c str ; and same for &'y str). In other words, it "unifies into the smaller lifetime"

It is equivalent in practice to the first one, since the "same input lifetime for both arguments" will make Rust perform that kind of unification upfront.

2 Likes

I don't think I agree with the explanation.

You don't need variance to explain the 3-parameter version. There are just three different lifetimes, with explicit "outlives" relationships: the compiler can choose 'x and 'y to be the "exact" lifetimes of the parameters, and choose 'a to be the "exact" lifetime of the result. Variance doesn't need to play in here because all the lifetimes are exact and the outlives-relationships between them are explicit.

(In reality this is not exactly true; there really is no such thing as an "exact" lifetime because the compiler can choose the lifetime of any reference to be as big or small as necessary. But the point remains that you don't need variance to explain the three-lifetime version of longer, at least for simple uses.)

Here's an example I used in a recent thread on almost the exact same question:

let mut s1 = String::from("foo");
let x: &str = &s1;
println!("{}", x);
let s2 = String::from("quux");
let y: &str = &s2;
let _l = longest(x, y);
s1.clear();
println!("{}", y);

x and y are references that must have different lifetimes. But longest(x, y) works either with the one-lifetime version or the three-lifetime version (or the two-lifetime version from the other thread). How come? The three-lifetime version can just say:

  • 'x is the lifetime of x
  • 'y is the lifetime of y
  • 'a is the lifetime of _l
  • All the constraints ('x: 'a, 'y: 'a) are satisfied, so we're done.

But the one-lifetime version needs to say:

  • 'a is the lifetime of _l, which is shorter than the lifetimes of x or y
  • But it's OK to pass x to a formal parameter of a shorter lifetime because &'a T is covariant in 'a
  • And it's OK to pass y to a formal parameter of a shorter lifetime for the same reason.

Long story short, there's no difference between these three annotations:

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str
fn longest<'a, 'b: 'a>(x: &'a str, y: &'b str) -> &'a str
fn longest<'a, 'x: 'a, 'y: 'a> (x: &'x str, y: &'y str) -> &'a str

They mean the same thing and expose the same API. This is true of both mutable (&'a mut T) and shared (&'a T) references because both are covariant in 'a, but there can be a difference with other types, because not every type is covariant in its lifetime parameters. Consider:

fn longest<'a, 'x: 'a, 'y: 'a>(x: Foo<'x>, y: Foo<'y>) -> Foo<'a>
fn longest<'a>(x: Foo<'a>, y: Foo<'a>) -> Foo<'a>

You'd have to know what kind of variance Foo<'a> has in 'a to know whether these two are equivalent or not.

1 Like

Did you mean covariant?

1 Like

Yep, "variant" means "covariant". I borrowed this from an older version of the nomicon, but it has since been updated to read "covariant" so I will adjust my usage accordingly.

1 Like

You are broadly agreeing with what I said:

And there are two point of views here, both valid:

  • Since "if 'a outlives 'b, then &'a str is a subtype of &'b str" is "obvious", there is no need to talk about variance;

  • But if we forget about "obviousness", one can objectively say the following:

    1. Rust defines type F<'a> = &'a str as being covariant;
    2. Hence "if 'a outlives 'b, then &'a str is a subtype of &'b str".

First of all, as a co-author of the book, thank you!

Second, I think there’s a deeper reason here that’s being missed. Yes, Rust could look at function bodies and infer lifetimes. Not doing so is a choice. The reason is the same reason we don’t infer the types of functions (lifetimes are types!). Rust views the function signature as the holy contract, and the body is expected to follow it. If we inferred the signature, changing the body could change the type. And if that happened, you could create breaking changes without realizing it. You also would get far worse error messages, as the error would be in the caller of the functions, not the line you changed in the body. Does that make sense?

16 Likes

I have actually had the same thought as the original poster and your response is a key point. In Haskell, specifying the types of functional arguments and values is optional, but my sense is that it is discouraged and rarely done, for exactly the reason you give.

I will also agree (I believe I've said it previously) that the revised Rust book's lifetime explanation is a big step forward from the original. I think much of the problem is that the way Rust handles lifetimes is necessarily complex and therefore difficult to explain. I don't think any of us would expect a book on quantum electrodynamics or general relativity to be easy reading. While I don't think Rust lifetimes are quite in that category (sorry), it's clearly a challenging area. For those still struggling with this, I recommend Jim Blandy's book, in addition to the book that you co-authored. The combination of the two will shed a lot of light on this vexing issue. (When writing C code, K&S and Harbison and Steele are never far from reach.)

I also strongly recommend avoiding situations where subtle lifetime issues are likely to come up. Do you really need to store references in that struct? Do you know about Rc? It can be your friend.

1 Like

The same reason you have to put types on functions, rather than having the compiler infer them: good error messages when things go wrong.

Rust's philosophy is that the implementation details of other methods should never affect the method you're writing right now. Thus it insists that you give a full-and-complete signature (note that lifetime elision only looks at the signature so it's not a counter-example) so that it can check the body of that function against that signature, and check calls to the function against that signature.

That way if you make a mistake in one function, you only get errors about that function.

4 Likes

This thread raises an interesting question, though, now that the compiler does allow lifetime elision in some cases, could it infer lifetimes in the following?

fn longest(x: &str, y: &str) -> &str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

It currently doesn't, but from a high level view, it seems it should be able to.

Lifetime elision is independent of the body (using only signature), but inference you're referring to depends on the concrete code written. This dependency is something we want to avoid, as was stated before.

1 Like

It absolutely could decide on a way to handle elision for the case (multiple input lifetimes, none of them on self, and at least one output lifetime). It could say that in this case it assumes they're all the same.

So far, however, the case hasn't been made that that's usually the right answer for such a signature. It certainly is for this case, but isn't in many other cases -- get_by_key(x: &HashMap<&str, &str>, k: &str) -> &str doesn't want that lifetime pattern, for example.

And we can see from std::cmp::min that using references directly might not even be the best way to write this -- min doesn't need lifetime elision because it just takes Ts, and if those Ts happen to actually be references the correct thing happens.

1 Like

The reasoning, that lifetime inference might lead to inadvertantly changing the Interface of a function, when just changing the implementation, sounds striking to me.
Thank you all for the explanation !

3 Likes

I puzzled over this response for a while, and couldn't quite figure out why we seemed to see things so differently, but almost a week later it has just clicked that you are talking about compiling the function itself whereas I was thinking about its caller. Of course, you have to apply variance somewhere to unify the lifetimes; the difference between one lifetime and three lifetimes is which function actually unifies them.

2 Likes

Yep. It is difficult to phrase these things clearly for each and everyone of the readers, since:

(Taken from this blog post, bold emphasis mine)

2 Likes

The statement that:

seems contradictory with a paragraph from the book:

However, when a function has references to or from code outside that function, it becomes almost impossible for Rust to figure out the lifetimes of the parameters or return values on its own.

I figure that either both arguments from this thread are valid:

  1. API stability,
  2. some more nuanced lifetime cases,

or maybe the book could get an update of that paragraph because in reality Rust really could always determine lifetimes automatically but we would risk breaking API after body swapping. What do you think?

I agree that this paragraph is not correct. To my knowledge there is no technical reason (at least, certainly not the one that is provided!) why complete inference of lifetime bounds is not supported; the compiler could easily assign each lifetime in the signature a unique name and generate 'a: 'b bounds based on the body. It is just deliberately unsupported in favor of API stability.

4 Likes

I've added a comment pointing to this thread to an already existing book issue (#1710) at GitHub.

2 Likes