Blog series: Lockout: Advanced aspects of lifetimes (part 5!)

I decided to do more blogging. I’m going to be covering rather advanced aspects of the lifetime system.

The primary audience is people who have been writing Rust for a long time, yet still have trouble coming to grips with what lifetimes “really, truly mean.” In my case, there was a point in time not too long ago where I was even capable of using lifetime annotations correctly, yet unable to explain the thought process behind how I used them!

The key to getting over this hump was to finally realize that they have nothing to do with how long a value lives.

Don’t believe me? Hopefully I can do something about that:


Edit: Changed the thread subtitle from “Everything you know about lifetimes is wrong” to “Advanced aspects of lifetimes” since the old title felt too clickbaity.

28 Likes

Unless I’m missing something, the struct used in examples 1–3 (impl Struct { ... }) is not defined anywhere in the post. It’s evidently a newtype, but what exactly does it wrap?

Indeed it’s unspecified but you can assume it’s something like struct Struct(Vec<i32>).

Right, but the error one gets with that definition is more than x does not live long enough, as summarized in the example—which is why I’m asking about the precise type.

The error is “cannot infer an appropriate lifetime”, and I agree that the “outlives” relationship is part of what it’s complaining about, but it’s not the whole story. I suppose it would be helpful to specify the version of the compiler that was used for compiling the examples, along with the exact error code, if provided.

(Aside: rustc 1.27 produces the E0495 code for this error, while 1.29 doesn’t mention the error code at all.)

1 Like

Oops. This was in the post at some point but was somehow accidentally lost.

I was too lazy to put that example in the compiler, so I made up that error message. Sorry for the confusion!

I agree that it would be helpful to specify compiler version used, although I see @ExpHP just mentioned that he made up the error message (truthfully, I sort of subconsciously assumed the same - I didn’t try to reconcile the exact error message one would see vs the //ERROR: ... comment there). So I suppose another useful thing is to be either precise about the errors or indicate that the error message is made up.

I do think, however, that the example is about the “outlives” part. Since iter() is borrowing from self, and self is borrowed for an arbitrary (elided) lifetime, the lifetimes don’t match up and the compiler’s verbiage is the “cannot infer an appropriate lifetime …” message. If iter were defined as fn iter(&'static self) -> ... then it’d be fine, of course (not that one would typically write such code). I’m not sure what exactly you’re referring to with “… but it’s not the whole story”.

By the way, the actual compiler error message (1.29 stable) for this case is quite good:

error: cannot infer an appropriate lifetime
 --> src/lib.rs:6:16
  |
4 |     fn iter(&self) -> impl Iterator<Item=i32> + 'static {
  |                       --------------------------------- this return type evaluates to the `'static` lifetime...
5 |         // ERROR: Does not live long enough
6 |         self.0.iter().cloned()
  |         ------ ^^^^
  |         |
  |         ...but this borrow...
  |
note: ...can't outlive the anonymous lifetime #1 defined on the method body at 4:5
 --> src/lib.rs:4:5
  |
4 | /     fn iter(&self) -> impl Iterator<Item=i32> + 'static {
5 | |         // ERROR: Does not live long enough
6 | |         self.0.iter().cloned()
7 | |     }
  | |_____^
help: you can add a constraint to the return type to make it last less than `'static` and match the anonymous lifetime #1 defined on the method body at 4:5
  |
4 |     fn iter(&self) -> impl Iterator<Item=i32> + 'static + '_ {
  |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

It’s a bit worse, however, if you unelide the lifetime:

error: cannot infer an appropriate lifetime
 --> src/lib.rs:6:16
  |
4 |     fn iter<'a>(&'a self) -> impl Iterator<Item=i32> + 'static {
  |                              --------------------------------- this return type evaluates to the `'static` lifetime...
5 |         // ERROR: Does not live long enough
6 |         self.0.iter().cloned()
  |         ------ ^^^^
  |         |
  |         ...but this borrow...
  |
note: ...can't outlive the lifetime 'a as defined on the method body at 4:13
 --> src/lib.rs:4:13
  |
4 |     fn iter<'a>(&'a self) -> impl Iterator<Item=i32> + 'static {
  |             ^^
help: you can add a constraint to the return type to make it last less than `'static` and match the lifetime 'a as defined on the method body at 4:13
  |
4 |     fn iter<'a>(&'a self) -> impl Iterator<Item=i32> + 'static + 'a {
  |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Note the + 'static + 'a suggestion it shows at the bottom.

1 Like

You just wrote out the rest of the story in that paragraph :slight_smile: What I meant is that, IME, there are two distinct classes of borrow-checking errors that stump people: one is related to attempts to return references to locally-created objects (and other function-local matters), which is not difficult to explain, while the other involves more complex relationships, variance, etc. I believe that the given example is in the second category.

2 Likes

Ah yeah, ok, I see what you mean. In fact, I think this is what @ExpHP probably meant in the blog when he said he’s suspicious of people claiming they truly understand lifetimes :slight_smile:. I’m also of the same opinion: understanding the latter is much more difficult and likely only possible after substantial trial-and-error because the existing docs don’t cover those things in needed depth.

2 Likes

I edited it to address some of the above comments (diff).

Spolier alert: While trying to sort out the rest of my thoughts and decide what specifically to focus on in part 2, it became clear to me that I have no alternative: The only way to put the rest of my material in context is to design our own primitive sort of borrow checker.

(good thing, too I guess; saves me the trouble of people getting distracted by the differences between the old checker and nll)

2 Likes

&'a mut A is covariant in 'a and invariant in A .

Oh my, this is embarrassing, for years I was sure myself and told others that &mut is invariant in both the type and the lifetime =/

I also very much feel that I don’t actually really understand lifetimes. And I agree that the main bit I don’t understand is “what is the purpose of lifetimes”. More formally, I “understand” how lifetime inference works: given a source of a function, you write down a set of constraints and then find a minimal solution.

What I don’t understand is why this is sound, what are the progress and preservation properties.

Not having aliasing is a part of that but not the whole truth. Like, how re borrowing works? It does create a second &mut reference to the same data?

I think I have sort-of intuitive understanding here, that you freeze some paths, and that you keep an eye on Drop (unless it has an eyepatch), but I definitely don’t have a clear picture in my head of all of the constraints, and how they result in soundness. I think this might be the best explanation of what actually happens?

I really wish someone writes a series of blog-posts where they implement a small minirust language from scratch, together with the borrow-checker.

In contrast, I think I do understand type-inference, both in terms of how constraints are created, and why it works: because static x: Cat type ascription guarantees that runtime type of x will have all of `Cat’s methods. Thinking about it more, perhaps I miss the run-time thingy of which a lifetime is a static approximation?

3 Likes

This too is one of the many, many mental models I’ve toyed with in the past and ultimately rejected; in this case, because it felt too abstract and intangible.

This is what really makes me really excited to continue the series, because the lifetimes in this new mental model have a substance to them. They’re kind of a form of taint carried around by objects, describing all the ways a given object can’t be used.

Ironically, at the rate Part 2 is going, it seems like you’re almost going to get your wish here. …minus the bit about actually implementing it. (That’s hardcore!)

It turns out there’s an awful lot to say about borrow checking, even just dealing in a subset of the language with no function calls!

(Edit: I say this somewhat in jest though. As any software engineer knows, an algorithm without an implementation is indistinguishable from a fairy tale =P)

3 Likes

Part 2 is out!

It introduces a simple borrow checker and explores a bunch of examples that can be handled without any consideration of lifetimes in the type system. The purpose is to help introduce a basic framework for talking about the kinds of problems we’ll face once we start bringing calls to arbitrary functions into the mix.

5 Likes

Briefly reading the beginning of this post I find it much more interesting and compelling than the introductory post to the series. I’m definitely going to have to spend some time on this one. I find this exploration very interesting. @ExpHP Thanks for doing this.

2 Likes

Something very interesting and unexpected happened when I started to write part 3.

I decided to take a quick look at one more example before diving into function calls. It is the archetypal example of why &mut T is invariant in T. I figured it would be interesting to see how it gets handled in a borrow checker with no concept of lifetimes (and therefore, invariance).

fn bad_extension() {
    let mut outer_ref: &i32 = &0;
    let mut boxy = Box::new(0);
    {
        // secretly hide a read-lock inside outer_ref by indirection
        let evil: &mut &i32 = &mut outer_ref;
        *evil = &*boxy;
    }
    // invalidate the read lock
    boxy = Box::new(0);

    assert_eq!(outer_ref, &0); // UB!
}

What’s funny is: It isn’t handled. And it does not look like an easy fix!

I’m really going to have to ponder over this one. Up until now I was convinced that function calls were the sole motivation for lifetimes!

1 Like

So to be clear:

This is invalid in full Rust because outer_ref is &'static i32. Then we try to assign effectively &'boxy i32 to it, which does not satisfy 'boxy <: 'static. This is the lifetimes model.

This gets through the model presented here, because outer_ref doesn’t lock anything to begin with, but you stick a lock in there by mutating it.

This could be resolved by saying you can’t change a value’s held set of locks (ie the locks are a property of the binding and not the value itself), but then are you really not using lifetimes anymore? You’re just calling them by another name :stuck_out_tongue:

Good one! I really like your light-hearted “let’s explore together” writing style.
I am certain I will follow this to the end, I feel you’re taking me on a collaborative expedition!
Kudos for managing to keep this complex, abstract topic fairly light-hearted!

See, the thing is, I can’t even do that! I don’t think there is any tractable way for my borrow checker to realize that outer_ref is modified by the *evil = &*boxy line.

For instance, what if evil was instead Box<(Box<i32>, (&mut (i32, &mut i32)))>? How could the borrow checker determine that a write to *(evil.1).1 can modify outer_ref?

I’m not 100% sure yet, but I believe that storing information in the type of &mut i32 may be the only tractable solution. (meaning: lifetimes!)

1 Like

You could disallow references to references.

If you take a look at some of the new .net core stuff, you’ll see what this ends up looking like if you only handle function calls (not data structures): no lifetimes. (Really, it looks quite a bit like rust functions in a world where everything must be elided, with no explicit lifetimes allowed.)

I’m both intrigued and confused! I assume you’re talking about the Dependency Injection lifetimes? Reading about them, it looks like these lifetimes are solving a completely different problem altogether; in fact, they even have a runtime effect!

Maybe I’m missing something? If they really are solving a similar problem, it’s be interesting to see somebody write about them from the perspective of a Rust user.


Basically, while I still hadn’t worked out the “killer example” yet, Part Three was basically supposed to explain that the reason we need lifetimes was because we want borrow checking to use local reasoning.

fn opaque(&i32, &mut i32, &i32) -> (&i32, &i32);

Basically, without lifetimes, the compiler must assume the worst: when we call this function, all borrows returned by the function must hold all of the locks from all things given to it. Lifetimes allow this to be more refined.