Help me to understand invariance and lifetime here

help
1

playground

What is the lifetime in the type of variable cell?
cell must be Cell<&'_ str> (an inferred lifetime in Cell type), and must outlive local variable s.

But due to the invariance of Cell and the signature fn f<'a>(s: &'a str, cell: &Cell<&'a str>),
it seems cell is ought to be the exact Cell<&'s str>, which means cell shouldn't be used any more once the local variable s is dropped.

I've gone throgh this thread, but I still can't deduce.

1 Like
2

Borrow shortening would be the short answer, but @steffahn definitely is typing a better answer now.

3

That’s indeed the right conclusion here, thus code like this

use std::cell::Cell;
fn f<'a>(s: &'a str, cell: &Cell<&'a str>) {
    cell.set(s);
    dbg!(cell);
}

fn main() {
    let refincell: &'static str = "";

    let cell: Cell<&'_ str> = Cell::new(refincell);
    {
        let s = String::from("local: s");
        f(&s, &cell);
    }
    &cell; // uses `cell`
}

where cell is used after s is dropped will fail to compile.

The lifetime 'c in the type of cell: Cell<&'c str> is not completely determined by the program, but there are some bounds. As long as lifetime bounds aren’t contradictory, the compiler accepts if lifetimes are a bit underspecified. Hence there’s no good exact answer to “What is the lifetime in the type of variable cell?”; if I needed to answer this question nonetheless, I would probably give you the longest possible lifetime it has, which would be a lifetime ranging up until the point where s is dropped.

The bounds there are in your playground are as follows:

  • the lifetime 'c must be at least as long as the last usage of the cell. Variables can in general only be used as long as the lifetimes in their types are still live.
  • the lifetime 'c can be at most as long as any string passed to any of the f(…, &cell) calls. This is because the type signature f<'a>(s: &'a str, cell: &Cell<&'a str>) means that the parameter s needs to have a lifetime that’s exactly 'c, however &'a str is covariant in 'a, so that, given that the lifetime in the Cell is fixed, the lifetime of any s passed to f must be at least as long as 'c, i.e. 'c can only be at most as long as any such lifetime
    • the lifetimes for these calls are:
      • in line 12, and 16: 'static
      • in line 15, the lifetime until s is dropped
  • the lifetime 'c must be compatible with the construction of cell in Cell::new(refincell);. Because of covariance of refincell: &'static str, this creates the restriction that 'c can be at most as long as 'static, which is no restriction at all

All-in-all, this means that

  • from the first condition, the lifetime 'c must be at least as long as until line 16 where cell is last used
  • from the other conditions, the lifetime 'c can be at most as long as 'static, which is no restriction; and it can be at most as long as until s is dropped.

All-in-all the lifetime 'c is thus some lifetime that ends between the last usage of cell in line 16, and the place where s is dropped immediately after line 16.

Note that lifetimes only restrict the end of life of things. The fact that the lifetime of s is involved does not prevent the cell from being used before s is first created.

If the line 18 is uncommented, then there’s a lifetime conflict because cell’s last usage is then later (in line 18), which means

  • the lifetime 'c must be at least as long as until line 18 where cell is last used
  • from the other conditions, the lifetime 'c can be at most as long as until s is dropped immediately after line 16

these conditions leave no possible choice for 'c, because s is dropped before the last usage of cell. And indeed the error message points out these two events (i.e. the place where s is dropped, and the place where cell is used; and also it points out the point where the connection between the lifetime in cell and the lifetime of s is made):

error[E0597]: `s` does not live long enough
  --> src/main.rs:15:11
   |
15 |         f(&s, &cell);
   |           ^^ borrowed value does not live long enough
16 |         f("seemingly `&'static str` but not", &cell);
17 |     }
   |     - `s` dropped here while still borrowed
18 |     f("error due to the lifetime of s", &cell);
   |                                         ----- borrow later used here

It doesn’t talk about the lifetime 'c (a name we came up with, by the way) of the cell, but instead the lifetime of how long s can be borrowed; but this is just an artifact of what order we deduce these things in and where exactly we report the inevitable conflict.

3 Likes
4

By the way, since you asked about invariance, the invariance of Cell came in a this point

in particular in the remark which I just abbreviated as “the lifetime in the Cell is fixed”. Invariance is arguably the less special behavior in this case. I took more time explaining how the covariance of &'a str weakens the constraints that come into play due to this function call.

Without any variance, calling f(foo, bar) would been that we need foo: &'a str and bar: &'b Cell<&'a str> for some lifetimes 'a and 'b, i.e. exactly matching lifetimes for the parameter types.

Variance allows implicit coercions, so that f(foo, bar) becomes something like f(coerce1(foo), coerce2(bar)), effectively, i.e. there’s an extra implicit step that can change the type being passed to f to be different from the actual type of foo, or `bar, respectively.

Coercions due to variance are (mostly) about coercing between some types that only differ in lifetimes. The direction of coercion is distinguished by covariance vs. contravariance, whereas invariance means that a particular lifetime cannot be changed at all.

The variance of the types involved are that

  • &'a str is covariant in 'a
  • &'b Cell<&'a str> is covariant in 'b and invariant in 'a

this means

  • &'a1 str can be coerced into &'a2 str as long as 'a1 is a longer lifetime than 'a2
    this means
  • &'b1 Cell<&'a1 str> can be coerced into &'b2 Cell<&'a2 str> as long as 'b1 is a longer lifetime than 'b2, while 'a1 and 'a2 have to be exactly the same lifetime

Determining these facts happens recursively. You need to know that

  • &'a T is covariant in 'a and covariant in T
    • or, without concrete names, you could say that &'_ _ is covariant in the first parameter and covariant in the second parameter
  • Cell<T> is invariant in T
    • or, without concrete names, you could say that Cell<_> is invariant in the first (and only) parameter

then you … well … the &'a str case is trivial then, because that’s just a special case of &'a T … for &'b Cell<&'a str>, we also immediately see that the thing is covariant in 'b, the question what the variance of that type in 'a is is interesting:

Type expressions are kind-of like trees:

tree for `&'b Cell<&'a ()>`

`&'_ _`
   | +-- `Cell<_>`
   |           +---- `&'_ _`
   |                   + +-- `()`
   |                   |
   |                   +-- 'a
   |
   +-- 'b

We consider the whole path down this tree from the root to the lifetime 'a in question:

  • entering &'_ _ in the second parameter
  • entering Cell<_> in the first (and only) parameter
  • entering &'_ _ in the first parameter

Now consider all the variances along this path

  • &'_ _ is covariant the second parameter
  • Cell<_> is invariant in the first parameter
  • &'_ _ is covariant the first parameter

Finally, we need to know how variances combine in a chain like that. The rule is simple:

  • start with covariance
  • covariance along the path doesn’t change anything
  • contravariance along the path flips the variance
  • invariance along the path is “infectious”, once your’re invariant in one step, the whole thing is invariant

Since the Cell<_> is invariant in the first parameter, we deduce that &'b Cell<&'a str> is invariant in 'a.

If you apply these rules to other examples, you can e.g. deduce that fn(fn(&'a ())) is covariant in 'a, but for this you’ll need to know that fn(_) -> _ is contravariant in its first parameter (the argument type), [and the return type is implicitly ()]. This chain has two steps of contravariance, which flips variance twice, and the result is covariance again.

One detail I haven’t mentioned yet, to complete the rules of deducing variance of types:

If a lifetime appears multiple times in a type expression, you need to deduce the variance for each occurrence independently and combine the results with a new rule. E.g. fn(&'a ()) -> &'a (). You can figure out that this type is

  • contravariant in the first occurrence of 'a
  • covariant in the first occurrence of 'a

The rule to combine these is that different types of variance are incompatible, and always result in invariance. So the conclusion is that fn(&'a ()) -> &'a () is invariant in 'a.

For custom structs/enums, variance can be hard to figure out because it’s implicit and also doesn’t appear in the rustdoc documentation. The compiler automatically deduces it, following the rules above. So e.g. for a struct

struct S<'a>(fn(&'a ()) -> &'a ());

the compiler infers that S<'a> is invariant in 'a.

3 Likes
5

@steffahn Thank you soooooo much. You just save my whole day.
Would you mind if I translate your awesome answer into Chinese note taking?

6

Feel free to do that if you like ^^

1 Like
7

Let me mention, just to be sure in case you somehow didn’t know about it yet: The Rustonomicon has a good introductory page about variance, too: Subtyping and Variance - The Rustonomicon

1 Like
8

I didn’t quite complete this example, actually, since I got so deep into explaining how to determine variance after this section.

With implicit coercions due to variance, i.e.

the vall to f(foo, bar) therefore means that the coerced types of foo and bar need to be … let’s write it as … coerce1(foo): &'a str and coerce2(bar): &'b Cell<&'a str> for some lifetimes 'a and 'b.

The types of foo and bar themselves then are

  • foo: &'a1_foo str for some lifetime 'a1_foo that is longer than 'a,
  • bar: &'b1_bar Cell<&'a1_bar> for lifetimes such that 'b1_bar is longer than 'b and 'a1_bar is the same as 'a

Next, we can ignore the intermediate lifetimes to deduce the constraints on the type of foo and bar themself:

  • 'a1_foo is longer than 'a, which is the same as 'a1_bar,
    and 'a1_bar is the lifetime 'c in the type of cell: &Cell<&'c str> in our calls to foo(…, &cell)

    • this is where the constraint that

      ultimately comes from

  • what exactly the lifetime 'b is doesn’t matter to us; 'b can be any lifetime shorter than (or equal to) the lifetime 'b1_bar
  • (for completeness, note that there is also a relation between 'b and 'a; the type &'b Cell<&'a str> does require that 'b is shorter than 'a. The same applies to 'b1_bar and 'a1_bar. This isn’t very important in this case because 'b1_bar and 'b can (equal to each other and) be really, really short anyway, e.g. lasting just as long as the call to f itself, so that any condition of the form “'b is shorter that …” is trivially fulfilled).
1 Like
9

Let me conclude.

The contract of lifetime

Let 'c denote the lifetime parameter the compile is happy with: let cell: Cell<&'c str> = Cell::new(refincell);

Then the signature fn f<'c>(s: &'c str, cell: &Cell<&'c str>) means that:

  • as long as the reference passed to s keeps valid, cell can hold on to its liveness;
  • once the data referenced by s is dropped, the cell can no longer be used;
  • that's to say the lifetime in the type of cell
    • shortens each time a shorter lifetime is passed to s;
    • gets resolved when all lifetime bounds are met

The role of variance

Cell is invariant wrt 'c in cell: &Cell<&'c str>, so 'c should remain unchanged when the lifetime in variable is passed to the argument cell.

However, this does not prevent implicit variance transformation of other arguments:
& is covariant wrt 'c in s: &'c str, so for a given 'c, the lifetime of any reference passed to the argument s can be at least as long as 'c.
In the following example, code passes only when 'static: 'c, 'string: 'c and 's: 'c are all met.

use std::cell::Cell;
fn f<'a>(s: &'a str, cell: &Cell<&'a str>) {
    cell.set(s);
    dbg!(cell);
}

fn main() {
    let string = String::from("outer: string");
    let refincell = &string;

    let cell: Cell<&'_ str> = Cell::new(refincell);
    f("alive", &cell);
    {
        let s = String::from("local: s");
        f(&s, &cell); 
        f(&string, &cell);

        // string is allowed to drop early if cell is no longer used
        // the lifetime '_ in Cell<&'_ str> stops here and the constraint 'string: '_ still holds
        drop(string);
        //f("error due to the lifetime of string", &cell); // this line violates 'string: '_
    }
    //f("error due to the lifetime of s", &cell); // this line violates 's: '_
}
1 Like
10

Sounds good.

11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.