# Help me to understand invariance and lifetime here

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

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

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

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:

• 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 `struct`s/`enum`s, 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

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

Feel free to do that if you like ^^

1 Like

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

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

Let me conclude.

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

Sounds good.

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.