Why can lifetimes not be inferred?

#1

Hello again, kind rust-pros.

in my studies of the second Version of The Book,I just completed the section about lifetimes. First, congratulations to the authors !!! With the first Version, I had severe problems to grasp what lifetimes really mean, and why they are needed. This somewhat abstract topic is now covered excellently, imho.

Of course,I did some experiments, modifying the example code given, and came across this:

fn main() {
    let string1 = String::from("abcd");
    let string2 = "xyz";

    let result = longest(string1.as_str(), string2);
    println!("The longest string is {}", result);
}

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

As I expected, the compiler does not accept this code, and tells me exactly what’s wrong with the lifetime of parameter y.

What I’m now wondering about: If the compiler can tell me that, why do I have to annotate lifetimes at all - at least in this simple scenario ? Obviously, the compiler exactly knows, what the correct annotations would be, so why can it not simply infer them ?

Thanks in advance for any answers

3 Likes
#2

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.

7 Likes
#3

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…

#4

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.

1 Like
#5

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.

#6

Did you mean covariant?

1 Like
#7

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.

#8

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".
#9

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?

13 Likes
Rust - What would be your top and flop?
#10

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
#11

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.

2 Likes
#12

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.

#13

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
#14

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
#15

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
#16

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.

1 Like
#17

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)

1 Like