Lifetime Annotations

Note: A + 'a bound is not yet accepted on a generic type's parameter, and an owning virtual reference, which is bounded by 'static, may not be given another. 'static written inside a parameter's type, on what a &mut points at, is refused.

To ensure borrowed references are always safe to use, they carry a lifetime constraint that restricts them from living beyond the scope they were created in. This constraint prevents a borrowed reference from pointing to an object that no longer exists. Borrowed references may move freely around the program, so long as they never try to travel beyond this lifetime barrier. Attempts to violate this lifetime constraint result in a compiler error.

For a borrowed reference used within the same function where it was borrowed, the compiler knows exactly which scope created the borrowed reference, and thus knows exactly what scope represents its lifetime barrier. However, a function that receives a borrowed reference from another function has no visibility into which scope created the borrowed reference. There is effectively a thick brick wall separating a called function from the function that calls it. Each cannot see anything about what the other is doing with borrowed references.

Lifetime Annotations on Function Signatures#

To bridge this knowledge gap, Cone looks for lifetime annotations on borrowed references in a function's signature.

fn dostuff(a &'a i32, b &'b i32) &'a i32, &'b i32 {..}

'a and 'b are lifetime annotations representing two possibly-different lifetime scopes. Lifetime annotations are used to establish lifetime relationships between borrowed references. In this example, this means the first return value has the same lifetime as a, and the second has the same lifetime as b.

A lifetime is written right after the reference's &, before its permission: &'a i32, &'a mut i32, &'a Array[u8]. Parameters are written name first, then type, with no colon. The global lifetime is 'static (below).

fn first(a &'a i32, b &'b mut i32) &'a i32 {..}
fn firstOf(a &'a Array[u8], b &'b i32) &'a Array[u8] {..}

Although the called function treats them as having the "same" lifetime, they might in fact have different lifetimes in the calling function. When references with two different lifetimes are treated as having the same lifetime, their understood lifetime would be the shortest one, as that is the only lifetime these references have in common.

Lifetime annotations may be omitted on some or all borrowed references on a function signature. All borrowed references without annotations are understood to have the same lifetime, as if they had all been marked by the same lifetime annotation. The above example is thus identical to:

fn dostuff(a &i32, b &'b i32) &i32, &'b i32 {..}

We can rule out the need for any lifetime annotations if the function does not receive at least two borrowed references in its parameters. We can also rule out them out if the borrowed references in parameters are all read-only (ro) and no borrowed reference is returned. Beyond this simple test, there are two specific situations where lifetime annotations might be required.

Returned borrowed references#

When a function returns a borrowed reference and accepts at least two borrowed references as parameters, lifetime annotations might be needed. Let's illustrate with a simple example:

fn caller(nbr i32) i32 {
  mut ref &i32;
  imm outer = 5;
  {
    imm inner = 10;
    ref = refswitch(nbr, &outer, &inner);
  }
  *ref; // Is this safe???
}

That final de-reference will not be safe if the called function looks like this:

fn refswitch(nbr i32, ref1 &i32, ref2 &i32) &i32 {
  if nbr < 0 {
    ref1;
  } else {
    ref2;
  }
}

The problem is that caller has no idea whether refswitch will return a reference to inner or outer. Since it could possibly be a reference to inner, that final de-reference could be unsafe, as inner is gone by the time the de-reference happens.

However, if we call a function that clearly indicates the returned reference only originates from ref1 (by marking ref2 as having a different lifetime 'a), then caller's logic is safe:

fn refswitch(nbr i32, ref1 &i32, ref2 &'a i32) &i32 {
  ref1;
}

If the signature shows the returned reference originates from ref2, caller once again triggers a compiler error:

fn refswitch(nbr i32, ref1 &'a i32, ref2 &i32) &i32 {
  ref2;
}

The lesson here is pretty simple: If a function returns a borrowed reference, make sure its lifetime annotation matches the borrowed reference(s) it could be sourced from. Then make sure that any borrowed references that are not the source for it are marked with a different lifetime. When correctly marked in this way, lifetime constraints will be properly enforced on both the caller and called functions.

The caller reads the signature the same way. A returned borrowed reference has the lifetime of the shortest borrowed reference passed to the call for a parameter whose lifetime it may hold, and it keeps those arguments frozen while it is used. A method's receiver counts as one of the arguments. Only the argument the result may hold is frozen:

fn pick(x &'a i32, y &'b i32) &'a i32 {..}

mut a = 1;
mut b = 2;
imm r = pick(&a, &b);
b = 6;                 // fine: r holds nothing of b
a = 5;                 // **ERROR** r still holds a borrow of a
print <- *r;

struct S {
  pub n i32;
  pub fn get(self &) &i32 { &n; }
}

mut s = new S(1);
imm r = s.get();
s.n = 3;               // **ERROR** r keeps the receiver frozen
print <- *r;

Where the result may hold only a lifetime of what an argument points at, not the argument itself (a struct's lifetime held by the receiver of one of its methods, or the inner lifetime of a &'a mut &'b T), the call keeps frozen only what the argument holds in that lifetime, not the argument, nor a local the argument borrows (reference layers). The full rules for returned borrows are those of borrowed references.

Mutable borrowed reference parameters#

When a function passes at least two borrowed references as parameters, at least one being mutable, lifetime annotations might be needed. Consider:

fn tryit() {
  imm i = 5;
  mut a = &i;
  {
    imm b = 10;
		refstore(&mut a, &b); // is this ok?
	}
}

It may call this function:

fn refstore(refmut &mut &i32, refval &i32) {
  *refmut = refval;  // Oh my!
}

Is that a problem? refstore assumes that both borrowed references point to objects of the same (smallest) lifetime. tryit knows that smallest lifetime is the scope of b, and that refstore might store refval in refmut (as it does!). So after the call, a may hold a borrow of b. That is no error by itself: a variable's lifetime is that of whatever it holds now, and a is not used again. The call is legal. What is refused is using a after b's block has ended, where it might point at b, gone; the error is reported where b goes out of scope while a still holds a borrow of it:

fn tryit() i32 {
  imm i = 5;
  mut a = &i;
  {
    imm b = 10;        // error: b goes out of scope while a still holds a borrow of it
    refstore(&mut a, &b);
  }
  *a;                  // used again here
}

Had a been what a parameter points at, or a global, which outlive tryit, the call itself would be refused: nothing after it could keep the borrow of b from outliving b.

The same risk arises whenever a call is handed a mutable (or unique) borrowed reference to anything that can hold a borrowed reference, not just to a borrowed reference itself: a struct with a borrowed-reference field, an Option or List of borrowed references, or a slice of them. A method's self &mut receiver counts the same way, so after a setter that stores its argument into a field of its receiver, or a push onto a list of borrowed references, the receiver may hold the borrow it was handed, and may not be used after that borrow's source is gone:

struct Holder {
  pub r &i32;
  pub fn set(self &mut, r &i32) { self.r = r; }
}

fn tryset() i32 {
  imm i = 5;
  mut h = new Holder(&i);
  {
    imm b = 10;        // error: b goes out of scope while h still holds a borrow of it
    h.set(&b);
  }
  *h.r;
}

Handing over a borrowed reference that lives at least as long as the place it could be stored in is always allowed.

What a method may not store in its receiver is a borrow of the receiver's own storage. pub fn grab(self &mut) { held = buf.view(); }, with buf and held both fields of self, would leave a value holding a borrow of one of its own fields, which its owner may then change or move (refill buf, push past its capacity) while held is still read. It is refused where it is written. The same holds for a function handed a &mut to the value, and for a call that could store it (words.push(text.view())). Store an index or an offset instead, or hold the buffer somewhere else and borrow it from there. A borrow the method was given may be stored, as above.

There are two ways to make this error go away. The first involves move b to the same scope as a, making the lifetimes truly equivalent. The other approach is to make the refstore function promise it won't store one reference inside the other, by marking their lifetimes as independent, so that a holds only what it held before:

fn refstore(refmut &mut &i32, refval &'b i32) {
  **refmut = *refval;
}

The lesson here is once again simple: If you pass a mutable borrowed reference, mark every other borrowed reference with a different lifetime annotation if you don't intend for it to be stored in the mutable borrowed reference.

Inside the function#

The annotations bind the called function as well. Inside it, a borrowed reference the caller lent may be returned only as a lifetime it is written with, or one that its where clause or its types order shorter. It may be stored only where what a parameter points at holds such a lifetime. No order between two names is inferred, except what a where clause declares and what a borrow of a value holding lifetimes implies (implied bounds):

struct R { pub n i64; }

fn bad(x &'a R, y &'b R) &'a R {
  y;                  // **ERROR** y's lifetime 'b is not one the result names
}
fn ok(x &'a R, y &'b R) &'a R where 'b >= 'a {
  y;                  // Ok: 'b lasts at least as long as 'a
}
fn put(d &mut &'b R, s &'a R) {
  *d = s;             // **ERROR** s is not of a lifetime that d holds
}

The 'static lifetime#

The global lifetime is 'static. A 'static parameter takes only a global borrow, a borrow of a global variable, and a borrow the caller lent may not be returned as 'static:

mut GLOBAL R = new R(1);

fn keep(s &'static R) i64 { s.n; }
fn leak(x &R) &'static R {
  x;                       // **ERROR** a borrow the caller lent is not global
}
fn caller() i64 {
  imm v = new R(5);
  keep(&GLOBAL);           // Ok
  keep(&v);                // **ERROR** a local's borrow is not global
}

'static may be written on a parameter's own reference or in the result, but not inside a parameter's type: fn read(slot &mut &'static R) is refused, since what a caller passes there is not checked to be global.

Implementing a trait#

A trait's implementation may promise more than the trait does: a result of 'static or of a longer lifetime, and a parameter of any lifetime where the trait's is 'static. A call through the trait is checked against the trait's signature, which holds its result to everything the signature lets it carry, so an implementation that carries less is safe:

struct R { pub n i64; }

mut THREE R = new R(3);

trait Source {
  pub fn top(self &) &R;
  pub fn note(self &, x &'static R);
}

struct Cursor['a] is Source {
  pub items &'a Array[R];
  pub fn top(self &) &'static R { &THREE; }       // promises more: a global borrow
  pub fn note(self &, x &R) { print <- x.n; }     // takes more: a borrow of any lifetime
}

The reverse is refused: an implementation that takes only a 'static borrow where the trait's parameter takes any, or whose result is tied to an argument where the trait's result is tied to the receiver, does not meet the trait.

Lifetime Annotations on Fields#

It is not enough to just constrain the lifetimes of borrowed references, we must also constrain the lifetimes of any data structures that contain borrowed references as fields. Consider:

struct Wrapper['a, 'b] {
  pub refa &'a u32;
  pub refb &'b u32;
}

Every Wrapper value contains two fields, both borrowed references, each with a different lifetime constraint. The lifetime of this value will be constrained by whichever ends up as the shorter of the two lifetimes:

fn process() {
  imm val = 5;
  makewrap(&val);
}

fn makewrap(valref &i32) Wrapper {
  imm val = 10;
  new Wrapper(valref, &val);  // oops
}

The Wrapper value is created in the makewrap function using a borrowed reference created in that function. Therefore, this value is lifetime-constrained to this function and may not be returned to process.

Declaring a struct's lifetimes#

A struct (or an enum) declares the lifetimes its fields name in its square brackets, apart from its type parameters: struct Wrapper['a, 'b], struct Cursor['a, T]. Its fields name those lifetimes and no others. A struct whose fields name exactly one lifetime may leave its brackets without it, and that one is taken as declared; one whose fields name two or more declares them all, so that a misspelled name is caught rather than taken for one more lifetime. Every borrowed reference a struct declaring lifetimes holds names one of them: an unnamed borrow there would be of whatever lifetime each signature using the struct leaves unnamed.

A lifetime changes neither a struct's layout nor its code, so it is never instanced: Wrapper['a, 'b] and Wrapper are one type, and a generic struct has one instance per type argument, none per lifetime. A struct is constrained by a lifetime only by holding a borrow: one declaring lifetimes but holding no borrow travels anywhere, and a generic one is constrained per instance (List[&R] is, List[i32] is not).

Lifetime Annotations on Types#

The same lifetime annotation principles we discussed earlier apply to functions that receive or return values which have borrowed references within them as fields.

fn process() {
  imm val = 5;
  makewrap(&val);
}

fn makewrap(valref &i32) &i32 {
  imm val = 10;
  getref(new Wrapper(valref, &val));
}

fn getref(wrap Wrapper['a, 'b]) &'a i32 {
  wrap.refa;
}

getref shows how lifetime annotations are specified on aggregate types: inside the struct's square brackets are two lifetimes, one for each lifetime the struct declares, in the order it declares them. Notice that the function returns the borrowed reference held by refa (the longer one), also signalled by the lifetime annotation on the return type. A use naming none, Wrapper, gives every lifetime the struct declares the signature's unnamed lifetime.

Were we to change getref to return refb instead, the makewrap function will be smacked with an error for trying to return a borrowed reference it created and which must not outlive its scope.

A value passed by value that holds a borrowed reference counts as one of the lifetimes its type names, the unnamed one where it names none, both for the lifetime a returned borrow takes and for where a borrow may be stored. Here the result is of h's 'a, so it outlives the borrow of y:

struct Holder['a] { pub r &'a i32; }

fn pick(h Holder['a], y &'b i32) &'a i32 { h.r; }

fn main() i32 {
  imm x = 1;
  mut r = &x;
  {
    imm y = 2;
    r = pick(new Holder(&x), &y);     // Ok: the result is of h's 'a, not y's
  }
  *r;
}

Written without lifetimes, fn pick(h Holder, y &i32) &i32, the Holder takes the unnamed lifetime that y has, the result may hold either, and the same call is refused where r is used after y is gone.

Lifetimes in a struct's methods#

Inside a struct's methods, Self (and so an unwritten self type) is the struct with its own lifetimes, which act there as the caller's lifetimes do. A method may so promise that its result points where a field points, not into the struct:

struct Cursor['a] {
  pub items &'a Array[R];
  pub at usize;
  pub fn next(self &mut) Option[&'a R] {
    if at < items.len() {
      imm r = &items[at];
      at = at + 1usize;
      return Some[&R](r);
    }
    None[&R];
  }
}

fn firstOf(items &Array[R]) Option[&R] {
  mut c = new Cursor(items, 0usize);
  c.next();     // Ok: points where items points, not into c
}

Because next's result is of the cursor's 'a, not of the &mut borrow of self, a call keeps frozen only what the cursor holds in 'a, and the result may outlive the cursor. Written without lifetimes, the result would share the receiver's borrow, and could not be returned. The method in turn may return only what its fields of 'a point at: &self.at, a borrow of the cursor itself, is of self's own lifetime, not 'a.

Two lifetimes in one struct#

A struct may hold borrows of two unrelated lifetimes. A value of it is usable wherever all its lifetimes hold, and what one of them holds is kept apart from the other's:

struct Parser['src, 'ar] {
  pub text &'src Array[u8];
  pub ar &'ar mut Scratch;
  pub at usize;
  pub fn word(self &mut) &'src Array[u8] { ... }
}

fn firstWord(text &Array[u8]) &Array[u8] {
  mut scratch = new Scratch(0);
  mut p = new Parser(text, &mut scratch, 0usize);
  p.word();     // Ok: the word is of the text, not of the local scratch
}

With one lifetime for both fields, the word could hold anything the parser holds, the local scratch arena included, and could not be returned. A borrow of one of two unrelated lifetimes may not be stored where the other's are held: that needs a where clause ordering them (below). A call whose signature names the struct's lifetimes as one, or orders them beyond the struct's own order, may move a borrow from one field to another, so after it the caller no longer knows which field holds which borrow, and keeps them all as one.

Where clauses ordering lifetimes#

Two lifetimes a signature names are unrelated unless its where clause orders them. 'a >= 'b says 'a lasts at least as long as 'b: a borrow of 'a may then be stored where 'b borrows are held, and returned where a 'b one is promised, but not the reverse. 'a == 'b orders each at least as long as the other. The order is transitive, and nothing beyond what the clauses say, and their transitive closure, is inferred.

fn put(d &mut &'b R, s &'a R) where 'a >= 'b {
  *d = s;       // Ok: 'a lasts at least as long as 'b
}
fn pick[T](x &'a T, y &'b T) &'b T where 'a >= 'b and T is Copy {
  x;
}

A caller reads the same order: it keeps put's second argument alive as long as the place its first points at is used. A where clause orders lifetimes on any function, generic or not, among the lifetimes its signature names; on a struct, struct Pair['a, 'b] where 'a >= 'b, among those it declares, in its methods and in every signature using it; and on a generic type's methods. Lifetime comparisons join each other and type clauses by and only: a lifetime is never instanced, so no instance settles which alternative of an or holds, and the body could rely on none of them. An or or a not over a lifetime comparison is refused.

Reference layers#

Each layer of a reference to a reference has a lifetime of its own, and what is read through a layer has the lifetime written inside it, not the layer's own:

fn first(x &'a mut &'b R) &'b R {
  *x;           // Ok: what x points at holds a 'b borrow
}
fn caller(p &R) &R {
  mut pp = p;
  imm z = &mut pp;
  first(z);     // Ok: of what pp holds, p's borrow, not of pp
}

Because the result is of the inner lifetime, the call keeps frozen only what the argument holds in it (p's borrow), not the argument z, nor pp, the local it borrows. After imm r = first(z);, pp may still be assigned while r is in use.

A borrow taken through an inner uni reference is a reborrow of it, which lasts no longer than the outer borrow, since the inner reference may be used again once the outer borrow ends: &uni **x for x &'a uni &'b uni R is of 'a, and may not be returned as 'b. Through an inner mut or read-only reference, which a copy may share, it is of the inner lifetime.

Implied bounds#

A borrow of a value holding lifetimes cannot outlast them: the value lives no longer than what it borrows, and the borrow no longer than the value. So wherever a signature names such a borrow, each lifetime the borrowed value holds is understood to last at least as long as the borrow's own, as if a where clause said so. &'a Pair['b] and &'a &'b R each imply 'b >= 'a, and a method's self & in a struct declaring 'a implies that 'a outlasts the unannotated borrow of self. So a method written with no lifetime of its own may return what a field points at, the result taking the shorter lifetime of the receiver's borrow:

struct H['a] {
  pub r &'a R;
  pub fn get(self &) &R { r; }    // Ok: 'a outlasts the borrow of self
}
fn inner(x &'a &'b R) &'a R {
  *x;           // Ok: 'b outlasts 'a
}

An implied bound runs one way only: the borrow of a Pair['b], of 'a, may not be returned as 'b. Two lifetimes no borrow relates and no where clause orders stay unrelated. A caller reads the same order, as it reads a where clause.

Lifetime bounds#

A lifetime is named on a borrowed reference or on a struct's use. A type whose insides a signature cannot see -- a generic function's type parameter, or what a virtual reference points at -- is given a bound instead, + 'a: any borrow inside lives at least as long as 'a, a lifetime the signature names. A bound adds what it says to the signature's order, as a where clause does; nothing is solved for.

On a type parameter. [T + 'a], [T Trait + 'a], or in the where clause, where T + 'a or where T is Trait + 'a (Generics). Inside the function, a value of type T may be stored where 'a borrows are held, or returned as 'a; without the bound, the borrows a T holds are of a lifetime of their own, which is neither:

fn put[T + 'a](d &mut &'a R, x T) {
  *d = x;           // Ok: what T holds lasts 'a
}
fn pick[T + 'a](x T, y &'a R) &'a R {
  x;                // Ok
}
fn putAny[T](d &mut &'a R, x T) {
  *d = x;           // Error: what T holds is not known to last 'a
}

A type argument holding no borrow meets every bound. One holding borrows meets it where each of them is known to last at least 'a: by its band (a global lasts every lifetime, and a value of the caller's own lasts no lifetime of its callee's signature), by a where clause or by what the caller's types imply. A call carries what an argument for T holds wherever 'a flows, so a borrow too short for where it was put is refused where it is used too late, and a caller naming its own lifetimes is held to its order:

fn caller(d &mut &'x R, v &'y R) {
  put(d, v);        // Error: 'y is not known to last 'x
}
fn ordered(d &mut &'x R, v &'y R) where 'y >= 'x {
  put(d, v);        // Ok
}
fn main() {
  imm g = new R(1);
  mut d = &g;
  {
    imm local = new R(2);
    put(&mut d, &local);
  }                 // Error: local goes out of scope while d still holds a borrow of it
  d.n;
}

T + 'static says T holds no borrow but of a global: inside, a value of T may be stored in a global or returned as 'static, and a call is refused an argument for it carrying any borrow that is not global, whether written as a borrow or held inside a value passed by value. A function is still instanced once per type argument, never per lifetime: the bound is the parameter's, not the use's. A type argument inferred from a call's arguments is instanced as the same type written would be, with no lifetime of the call: bounded or not, the instance's body holds what a parameter of type T lends as the caller's, and is checked once for every call. The bound is also what lets a parameter that asks for Sendable take a borrow that is imm, opaq or uni: [A Sendable + 'static], as thread.start writes it (Race condition safety).

On a virtual reference. &<Trait + 'a, or &<'r Trait + 'a with its own lifetime: the value it points at holds only borrows lasting at least 'a, which is at least 'r (an implied bound). The type holds 'a as well as its own lifetime, so wherever it is stored and read back out, what it carries goes where 'a borrows may. A value coerced to it, returned or stored through a parameter, may hold only borrows known to last 'a; a parameter &<Trait + 'static is handed only a value holding global borrows. A virtual reference with no bound is checked as before.

struct H['b] { pub r &'b i64; fn show(self &) i64 { *r; } }

fn keep(slot &mut &<'r Show + 'a, h &'r H['b]) where 'b >= 'a {
  *slot = h;        // Ok: what h holds lasts 'a
}
fn leak(slot &mut &<'r Show + 'a, h &'r H['b]) {
  *slot = h;        // Error: 'b is not known to last 'a
}
fn view(h &'r H['b]) &<'r Show + 'b {
  h;                // Ok
}

An owning virtual reference, So[Trait] or Rc[Trait], names no lifetime, so it may outlive any borrow: it is bounded by 'static. A value made one, where it is declared, assigned, passed or returned, may hold only global borrows: a borrow of a global, one the caller lent through a 'static parameter or a type parameter bounded by 'static, or none at all. A bound of another lifetime may not yet be written on an owning virtual reference.

struct H { pub r &R; fn show(self &) i64 { r.n; } }

fn boxit(h H) So[Show] {
  new So[H](h);     // Error: h holds a borrow the caller lent
}
fn boxGlobal(r &'static R) So[Show] {
  new So[H](new H(r));     // Ok: what it holds is global
}
fn boxAny[T Show + 'static](x T) So[Show] {
  new So[T](x);     // Ok
}

Invariant lifetimes#

Every lifetime so far is a scope: a borrow of it may go anywhere inside that scope and nowhere beyond it, and two of them are ordered by which lasts longer. An invariant lifetime, written with an equals sign, '=a, is no scope. It is equal only to itself, has no order with any other lifetime, and a value carrying one may go anywhere: be returned, stored, passed. What it protects is not when a reference is used but with what: a reference of an invariant lifetime is a key, which reaches nothing on its own, and the only way in is through the value of the same invariant lifetime that made it, its lock. A dynamic arena is the lock, and the references it hands out are its keys:

struct Pair['=a] { pub left &'=a R; pub right &'=a R; }

fn sum(ar &DynArena['=a], p &Pair['=a]) i64 {
  ar[p.left].n + ar[p.right].n;   // Ok: the arena and the keys are one brand
}

fn main() {
  mut a = DynArena.empty();
  mut b = DynArena.empty();
  imm p = new Pair(a.alloc(new R(1)), a.alloc(new R(2)));
  sum(&a, &p);                   // Ok: 3
  sum(&b, &p);                   // Error: p's keys are a's, not b's
  p.left.n;                       // Error: a key reaches nothing on its own
}

ar[key] reads what the key names; in set position (ar[key] = v, ar[key].f = v, ar[key].f += 1, a method taking self &mut) it writes it. Dereferencing a key, reading its field or calling its method directly is refused: the key alone gives no access. The compiler checks every use as an identity between the arena's lifetime and the key's, so at run time ar[key] is the key's own pointer and nothing more.

Brands. Inside a function, each invariant lifetime is a brand, compared only by identity. A name its signature writes is one brand, for the whole body. A function whose result names an invariant lifetime that none of its parameters does creates a fresh one at each call site: DynArena.empty() is such a function, so two arenas are always two brands, and a key of one used with the other is refused at compile time. Inside such a function, the name is the brand of whatever it returns, given by the first value the body binds to it; a body handing back two arenas of different brands as that one name is refused. A call binds each name in the callee's signature to the brand its arguments carry, and the result carries the brands so bound: a key ar.alloc(v) returns carries ar's. Recursion is fine: each activation's brands are its own.

Loops. An arena made inside a loop lasts only for that loop pass, so its brand is the pass's: a key from one pass may not be kept for a later one, nor carried out of the loop by a break. A fixed number of arenas, each with its own name, made before the loop, may be used in every pass.

Where clauses. where '=a == '=b declares two invariant names one brand, so a key of one opens an arena of the other, and a caller must give both the same. '=a >= '=b, or '=a == 'b with an ordinary lifetime, is refused.

Types. A struct declares an invariant lifetime in its brackets, as it does any other, struct Graph['=a] { ... }, so a value holding keys carries the brand, and a use names it, Graph['=a], in its place: an ordinary lifetime is not given where an invariant one is declared, and a signature always names a struct's invariant lifetimes. A body may name its signature's invariant lifetimes in a type, List[&'=a Node['=a]].empty(), and no others. A generic holds keys like any value; a key stays a key inside it. A key is a plain reference, &'=a T: a slice or a virtual reference takes no invariant lifetime. What a key names lives as long as its arena, past every scope, so it holds no borrow.

Invariant lifetimes are what make a dynamic arena safe without a check at run time: an ordinary borrow would bind the arena's values to one scope, and a counted or generational reference would pay for a check at every use. The cost is that a key is only ever useful beside its own arena, which a function's signature says by naming one brand for both.