ref-lifetimes.md

I have to insist on using explicit lifetimes for spec'ing. Both because I think it makes the rules a lot clearer, but also because it separates the safety rules from the language semantics. Let me introduce the description of lifetimes in a series of rules:

1. All expressions with a storage location (things you can take a ref to) have an implicit, language-defined lifetime. These lifetimes tend to be pretty simple. If you say

void M() {
    int x;
} 

The lifetime of int x is the same as the lifetime of method M. This is true for all structs. For fields of types, if the type is a class then the lifetime is the "global" (heap) lifetime. If it's a field of a struct, it's the lifetime of the containing struct. You can think of lifetimes as being part of the type, so while it looks like the type of x is int, it's really (x, $M), where $M is the lifetime of the method M.

2. The previous definition says that variables have the lifetime of the containing method. Methods also have lifetimes. The lifetime of a method is a unique lifetime that is smaller than the lifetime of its caller. Main has a special, non-global lifetime that we won't name because it's not important.

3. (2) states that methods have a unique lifetime that's smaller than its caller. But methods can have multiple callers! Once again, let's think about lifetimes as types. If we have a method which has different types, depending on how it's called, we already have a mechanism for that in the language. Generics! In fact, (2) is slightly wrong. Methods do not have unique lifetimes that are smaller than the callers -- method instantiations have a unique lifetime that's smaller than the caller, which implicitly passes its lifetime as part of the instatiation of the callees. Fortunately, we don't need to give names for any of these lifetimes as they are language-defined and cannot be changed, and aren't (currently) useful to refer to.

The above basically sums up the language without refs. There's not much to say, because lifetimes are never in conflict without refs, because structs copy, meaning the lifetimes don't have to match, and there's only one heap lifetime that's always the same.

Now, let's introduce refs. More rules.

4. Refs don't fall into the previous definitions. First, they have two lifetimes: the lifetime of the ref variable itself, which basically behaves like a regular variable, and the lifetime of the referent. We'll mostly refer here to lifetime of the referent, because we don't need any new rules for the variable itself, it looks like a struct variable.

5. Ref variables also don't have a unique, language-defined lifetime. They take the lifetime from their initializer. If you say

void M() {
    int x = 0;
    ref int r = ref x;
    ref int r2 = ref (new int[] { 0 })[0];
}

Then the lifetime of r is the lifetime of x, which is the lifetime of M. The lifetime of r2, however, is the lifetime of the first array element -- which is located on the heap. So the lifetime of r2 is the global lifetime. This matters for the next rule.

5. Ref variables must not have a longer lifetime than the storage they point to. This matters once we have ref-reassignment, as we could re-assign a ref to a location with a shorter lifetime than the ref itself.

6. It's now useful to have a language to talk about lifetimes explicitly. Let's use generic notation, since lifetimes are basically types. We would write the previous example as:

void M() {
    int x = 0;
    ref<$M> int r = ref x;
    ref<$global> int r2 = ref (new int[] { 0})[0];
}

We can relate $M and $global by saying that $global is a longer lifetime than all other lifetimes, so it can be assigned to all other lifetimes. This corresponds to type variance. Longer lifetimes are basically subtypes of shorter lifetimes.

7. What about ref parameters? They're interesting because they have lifetimes that come from the outside, i.e. they depend on the caller. This looks just like the method lifetime problem we discussed before. But now we need to have explicit parameterization for our new syntax.

void M<$a, $b>(ref<$a> int x, ref<$b> int y) { ... }

The lifetimes go at the beginning of the method parameter list, prefixed with $.

8. Since users don't write these lifetimes, they're implied for normal C# programs. The rule in C# is that, for all ref parameters, one lifetime is created for all the parameters and return types. So

ref int M(ref int x, ref int y) { ... }

would actually be

ref<$a> int M<$a>(ref<$a> int x, ref<$a> int y) { ... }

8. Lifetime safety follows the normal generic rules. So if the program would type check, it's safe.

OK, we're now completely caught up to C#6 (before ref structs).

There's one very important thing we can see already: the set of possible signatures that we can express in C# is far less than the set of legal, safe signatures that would be possible with explicit annotations. Without the scoped keyword there's really only one signature we can write for any method with ref parameters and returns. If we add scoped then we effectively force the scoped ref parameter to have a different lifetime than the return. So

ref int M(scoped ref int x, ref int y) { ... }

translates to

ref<$a> int M<$a, $b>(ref<$b> int x, ref<$a> int y) { ...}

For a method with N ref parameters and a ref return type, we have at most 2^N possible methods. Even restricting ourselves to one lifetime variable per ref parameter and return value, there are (N+1)^(N+1) possible signatures we could represent with explicit lifetimes. So we have to ensure that the combinations we want to allow can be expressed in our notation, as there's no possibility that we could express all safe options in just the scoped notation.

Next, let's add ref structs.

Ref structs have lifetime variables, just like ref parameters. Unlike ref parameters, we put the ref variables in the type definition, with the other generic parameters, e.g.

ref struct RS<$a> {
    ref<$a> int Item;
}

I believe today the defaults for ref structs are the same as the defaults for ref variables. So

RS M(RS rx, RS ry) { ... }

translates to

RS<$a> M<$a>(RS<$a> rx, RS<$a> ry) { ... }

I think this holds for combinations as well, i.e.

ref int M(Span<int> rs, ref int x) { ... }

is

ref<$a> int M<$a>(Span<$a, int> rs, ref<$a> int x) { ... }

For ref-to-ref structs, presumably we could use the same rule. The question is whether this is flexible enough for all scenarios. If we have a list of things we think should be allowed, they could probably be type-checked with this rule.

Here's my attempt to elaborate on the proposal and map more of C#'s ref safety concepts onto it.

Relational lifetime constraints

1. scoped introduces both another lifetime and a constraint between that and the calling method lifetime. Because we assumed 'scoped' variables hold references to a narrower scope, we allow values of 'unscoped' variables to be assigned into them, but not the other way around. I represented this by saying $b < $a, i.e. the scope of $b is "smaller" than that of $a. This is called a relational lifetime constraint. If we lacked this constraint, then the language wouldn't permit assignments in either direction, because either one could be wider or narrower than the other depending on the specific caller. No relationship would be known between them.

Span<int> M(scoped Span<int> s1, Span<int> s2)
{
    s1 = s2; // ok
}

// model as:
Span<$a, int> M<$a, $b>(Span<$b, int> s1, Span<$a, int> s2) where $b < $a
{
    s1 = s2; // ok
}

Lifetime argument inference

Let's consider briefly how the "inference" process works for lifetimes. Generally when two arguments go in for a given lifetime parameter, we pick the narrower one, because it reflects the narrower set of places the output is permitted to escape to. We say that a covariant conversion of the wider lifetimes to narrower lifetimes is occurring, which allows us to unify on the single narrowest lifetime.

Span<$a, int> M<$a>(Span<$a, int> s1, Span<$a, int> s2) { ... }

Span<$b, int> UseM<$b, $c>(Span<$c, int> s1, Span<$b, int> s2) where $c < $b
{
    return M(s1, s2); // error: inferred `M<$c>`, giving us result type `Span<$c, int>`, which cannot convert to return type `Span<$b, int>`.
}

This is very similar to how the "resulting lifetime" of an expression is determined. For example, M(arg1, arg2) will have a similar lifetime as cond ? arg1 : arg2.

This works for refs at the "top level", but it doesn't work for writable references to references. We'll get to why later.

Ref-to-ref-struct

This is where it really gets interesting because we get to explore why the current design has both a "calling method" scope and a narrower, special "return only" scope.

First, consider a ref struct which can hold a reference to its own field.

ref struct RS<$a>
{
    int field;
    ref<$a> int refField;
}

class Program
{
    public static void M()
    {
        RS<$M> rs = default; // $M indicates `rs` is allowed to refer to local variables in `M()`.
        rs.refField = ref rs.field;
    }
}

Note that C#'s lifetime rules don't consider the combination or compatibility of field types involved in expressions. In effect, we assume that every ref struct has a capability like the above when deciding the lifetimes of expressions.

Now, let's look at what happens with ref-to-ref-struct in a method signature. Let's first assume no return only lifetime exists. Let $c be the calling method lifetime which is used generally for references which are allowed to escape the current method.

void M(ref RS item) { ... }

// model as:
void M<$c>(ref<$c> RS<$c> item)
{
    item.refField = ref item.field; // ok
}

Because the lifetime of the reference and referent are equal, we are allowed to assign the reference to the referent and create a "cycle".

RS UseM(RS rs)
{
    M(ref rs); // error?
    return rs;
}

// model as:
RS<$c1> UseM<$c1>(RS<$c1> rs)
{
    M(ref rs); // error?
    return rs;
}

If we permit the above, then rs will contain a reference to rs, and we can return that reference to the caller. Now the caller has a reference to dead stack memory. So what rule are we missing?

In the call to M(), two lifetimes "come in" for lifetime parameter $c. The first is $UseM, the lifetime of local variables in UseM(). This means roughly the same thing as the current method scope in the ref fields spec. The second is $c1, the lifetime parameter of UseM(). Since $UseM is narrower, we choose it as the lifetime argument.

Now we look at the expression ref rs. Its type is effectively ref<$UseM> RS<$c1>. To use it as an argument here, we need to convert it to the parameter type ref<$UseM> RS<$UseM>. The conversion of RS<$c1> to RS<$UseM> is specifically what is problematic. Converting the variable to a narrower lifetime allows a narrower reference to be written in, and for that narrower reference to be observed by a component which sees that same variable as having a wider reference. This is just like converting List<string> to List<object>--yes, every string you read out is valid as an object, but we disallow the conversion to stop you from writing in any object when the underlying list still expects string.

The rule we suggest is therefore: A writable referent has an invariant lifetime. (A readonly referent still has a covariant lifetime.)

Now we have a rule which makes the method M(ref RS) safe, but useless. It can only be called with a reference to an RS variable which refers to the same lifetime as the one the RS variable is declared in. This is what we discovered when designing the ref fields feature for C# 11, and we eventually settled on the following complication to restore it to usefulness.

Let us instead model the method as the following, where $r is the "return only" scope, and $c is the "calling method" scope.

void M(ref RS rs) { ... }

// model as:
void M<$r, $c>(ref<$r> RS<$c> rs) { } where $r < $c

Now we can try calling it again in the same way.

RS<$c1> UseM<$c1>(RS<$c1> rs)
{
    M(ref rs); // ok: inferred `M<$UseM, $c1>` as the lifetime arguments.
    return rs;
}

These separate scopes allow us to assume that rs will not contain a reference cycle after the return.

Now we can consider a more conventional "method arguments must match" scenario.

void Mix(ref RS rs1, ref RS rs2) { ... }

// model as:
void Mix<$r, $c>(ref<$r> RS<$c> rrs1, ref<$r> RS<$c> rrs2)
{
    rrs1 = rrs2;
    rrs2 = rrs1; // either one of these are permitted

    rrs1.refField = ref rrs2.field;
    rrs2.refField = ref rrs1.field; // both of these are disallowed!
}

void UseMix<$r1, $c1>(ref<$r1> RS<$c1> rrs1, RS<$UseMix> rs2)
{
    Mix(ref rrs1, ref rs2); // error: inferred `Mix<$r1, $UseMix>`. Cannot convert argument `rrs1` of type `ref<$r1> RS<$c1>` to parameter of type `ref<$r1> RS<$UseMix>`.
}

With this, we've reached a decent point of usability, except that now we assume and require that the variables referenced by rrs1 and rrs2 have equal lifetimes. If a caller came in with references to different lifetimes, as in UseMix(), they would get errors. If they don't need to write to the references in Mix, they can change ref to in and have things work. In the current world where ref-to-ref-struct fields are disallowed, this limitation is something we can mostly live with.

However, it's easy to imagine this falling over once ref-to-ref-struct fields are added to the language, and lifetime parameters are not. We might be able to imagine a scheme where, after a certain number of indirections, a "widest" lifetime is automatically chosen for the fields. This means that many structures which rely on a narrower-to-wider gradation as references are traversed, won't be able to be composed into such fields which have an equal lifetime as their referents. More investigation is needed to determine whether this could lead to a tractible user experience for ref-to-ref-struct fields.

Looks good to me, only a few notes:

I represented this by saying $b < $a, i.e. the scope of $b is "smaller" than that of $a. This is called a relational lifetime constraint.

We actually already have this constraint in C#, it's :, i.e.

void M<T, U>() where T : U;

One subtlety is that bigger lifetimes are actually the subtype, though, so if you wanted to say

void M<$a, $b>() where $a < $b;

you would actually write

void M<$a, $b>() where $b : $a;

The rule we suggest is therefore: A writable referent has an invariant lifetime. (A readonly referent still has a covariant lifetime.)

This looks right, but technically I don't think you need a new rule, this is just how generics work and if you model lifetimes as generics, this falls out naturally. For example,

void M2(string s, object o)
{
    ref String rs = ref s;
    ref object ro = ref o;
    o = s; // OK
    ro = ref rs; // error, ref assignment is invariant
}

And yeah, ref readonly could probably be safe, but we don't allow that in C# (because we didn't add support when we added ref readonly) so I don't think we should allow it for lifetimes either until we add it for both.

Let us instead model the method as the following, where $r is the "return only" scope, and $c is the "calling method" scope.

Those scope names are fine for adding clarity, but I just want to note that they're unnecessary. The variables are generic so there's no particular restriction on what lifetime goes in there (calling method, calling method of the calling method, etc) as long as the constraint where $r < $c is satisfied.

However, it's easy to imagine this falling over once ref-to-ref-struct fields are added to the language, and lifetime parameters are not

Yup. But this is to be expected when we chose to add only one "scoped" modifier to the language. The complexity of lifetimes we can represent is really, really small compared to the space of safe lifetimes. I doubt there's a particularly clever thing we could design here as each method and struct needs to be type-checked separately and therefore can't use any information beyond its own signature to decide the lifetime variable assignment. We just don't have many bits of information to work with.

If we eventually end up with too many scenarios to express, I think we need to bring this back to LDM for recommendations. If we want more functionality we'll need more bits of information.

Great points. Using : for constraints does emphasize the analogy between generics and lifetimes. I'm tempted to read $b : $a as "values with lifetime $b can be converted to have lifetime $a", or just "$b is-convertible-to $a". Just like Subtype : BaseType means "Subtype is-convertible-to BaseType.

And yeah, ref readonly could probably be safe, but we don't allow that in C# (because we didn't add support when we added ref readonly) so I don't think we should allow it for lifetimes either until we add it for both.

Would agree that making the allowance in both generics and lifetimes would be best. We did ship the behavior where changing ref RefStruct parameters to in RefStruct removes arg-mixing errors, and we have seen users depend on it. If we go through with reformulating our rules based on generics, we might just want to take the opportunity to add the same allowance for the type of a readonly referent--so, make ro = ref rs legal in your example.

I'm going to try and see what happens when we map this concept onto ref struct RS<T> allow T : ref struct. i.e. what happens when T might be something with a non-global lifetime. How and where do we check that referent does not have a shorter lifetime than reference. Span<Span<int>> is something people end up wanting to do. Might also be good to dig a little more into examples of concrete types which have ref fields of ref struct type too.