Today, ~E lifetimes are built on on a value dependency model. We want to migrate to a type-restricted model. A type-restricted model is essentially a generic type system for lifetimes, which I'll call "lifetime types".
Dependencies
@_lifetime(source)
func operation(source: Source) -> DestTypes
func operation<'a>(source: Source<'a>) -> Dest<'a>John has a working document that clearly explains the distinction. This is a working document (more of an outline) that summarizes the migration path from one model to the other at a high level.
It will help to think about these four levels of lifetime support in the language:
-
value lifetimes
-
mutable storage lifetimes (var : ~E)
-
nested lifetimes (~E elements)
-
generic lifetime (<T: ~E>)
For whole values with concrete types, the two models are isomorphic. Both convey exactly the same information.
Lifetime types do introduce significant implementation complexity in the form of lifetime type variables that must be resolved at each reference to the type variable.
Lifetime types will naturally allow lifetime restricted parameters:
func escapeSpan(span: Span<'static, T>)Although our current @_lifetime syntax does not support this, the feature isn't fundamental to one model vs. the other.
The main complexity with our current lifetime annotations has to do with the distinction between borrowed vs copied dependencies. Again, this is independent of the model. It has to do with the fact that Swift lacks first-class reference types. We have not yet designed an alternative syntax that would work with lifetime types.
When it comes to ~E mutable storage, the current model is less constrained and therefore more expressive than lifetime types. It is unclear whether stricter diagnostics will be more often burdensome or helpful. It's also unclear whether lifetime types will reduce the demand for data flow analysis required by the dependency model. Both models require data flow to track dependent uses. The dependency model reuses the same data flow engine to find the source of dependencies at each mutating operation, while lifetime types solve this as part of type resolution. It's unclear whether some aspects of lifetime type resolution will be deferred to a SIL-level dataflow pass, which would make lifetime types more complicated in this respect.
Let's consider the following
- local variables
- stored properties
- closure captures
- inout parameters
- abstract storage
In the dependency model, mutation and reassignment can add and remove dependencies from a variable--the variable's original and mutated values have different dependencies. This allows a local variable to be reused for distinct lifetimes.
Mutation adds dependencies:
func localVarMutate() {
var span = Span<Int>()
read(span) // ERROR with lifetime types
do {
let array = [1,2,3]
span = array.span
read(span)
}
}A lifetime type unifies the constraints on all values of span. So, theoretically, the first read should be an error because it does not occur within the lifetime of array.
Reassignment removes dependencies:
func reassignSpan() {
let a = [0, 1]
let b = [2, 3]
var span = a.span // a -> span
read(span)
span = b.span // b -> span
_ = consume a
read(span) // ERROR with lifetime types
}With lifetime types, the second read should be an error because it does occur within the lifetime of a.
We may want to continue supporting such usage by modeling whole value reassignment as if it were a type cast, but that would seem to require deferring lifetime type resolution until we can perform SIL-level dataflow.
The current model does not distinguish between the lifetime of a ~E stored property and that of its aggregate. So the problem of stored property lifetimes reduces to lifetime analysis of the aggregate's storage. We will consider nested lifetimes in the next section.
The current model does not yet support overriding dependencies the closure captures. I don't anticipate any migration problems.
inout parameters expose mutable storage in the function signature. As with mutable local variables, the inout parameter may gain or lose dependencies when the function is applied. When migrating to lifetime types, we could allow functions to opt-into depedency-like behavior by specifying that the incoming and outgoing values have different lifetimes.
In the current model, it is common for inout parameters (typically self of a mutating method) to gain dependencies. The only way to remove the incoming value's dependency, however, is with the immortal syntax as follows:
@_lifetime(span: immortal, borrow a)
func reassignSpan(span: inout Span<Int>, a: [Int]) {
span = a.span
}To guard against this, we could remove suport for immortal inout dependencies. This feature is not critical for any known public APIs.
Abstract storage is modeled via getters and setters. A setter is modeled as if self is an inout. As with other inout parameters we can prohibit using immortal to suppress the incoming value's dependency.
Nested lifetimes are required for composability of containers with ~E elements. The lifetime dependency model does not currently support this. Doing so would require introducing Lifetime Members.
@_lifetime(storage: Self)
@_lifetime(elements: Element)
struct Span<Element: ~E>: ~E {
@_lifetime(self.elements) // default
subscript(_ position: Index) -> Element
}All use cases for nested lifetimes that I have seen can be handled with the dependency model using lifetime members, and in most cases the lifetime annotation will be inferred via the same-type default rule. Nonetheless, lifetime types have important advantages for nested lifetimes.
Lifetime types naturally support nested lifetimes via the container's generic element type:
struct Span<Element: ~E>: ~E {
subscript(_ position: Index) -> Element // produces a value whose lifetime is independent from 'self'
}-
Lifetime dependencies place more annotation burden on the library author. Although I expect default lifetime rules to to cover most APIs, the annotations are nonetheless part of the semantics that need to be understood. The compiler will ensure that the library implementation satisfies the lifetime annotations, but it will still be possible to accidentally make a public API more or less restrictive than intended.
-
Without lifetime types, unsafe APIs will be extremely bug prone. Putting the lifetime annotation burden on the library author is very problematic for unsafe implementations, which require the use of lifetime overrides. This is particularly obvious when accessing storage via
UnsafePointer<T>. -
Lifetime types may offload a significent implementation burden from the passes that perform diagnostics. With lifetime types, nested lifetimes are naturally inferred from the structure of the outer type. This seems likely to result in more robust diagnostics which are less susceptible to different code patterns--although diagnostics would then potentially be susceptible to holes in the type system. It's not yet clear whether the simplicity of analyzing nested values that we gain with lifetime types will make up for the complexity of inferring and resolving the outer type's lifetime types.
-
Standard library containers are generic over their element types and rely on protocol conformance for generic collection algorithms. As explained in the next section, those generic algorithms are cumbersome to generalize without generic lifetime types. The dependency model forces concrete lifetime dependencies, and full generalization could result in an explosion of overloads.
It is possible to support containers of ~E elements prior to adding nested lifetimes to the language, and we could consider adding ~E element support to some standard library types early. This poses migration concerns for both the dependency and type models.
Code written for the current non-nested dependency model is generally forward compatible with a dependency model that includes lifetime members. One limitation is that protocols with mutating requirements cannot safely be refined with more precise lifetime dependencies. Here we discuss one such example. Since the dominant view is that nested lifetimes will be accomplished with lifetime types instead, most readers can skip ahead.
Given a protocol with two ~E members:
protocol PairProtocol: ~E {
associatedtype T: ~E
associatedtype U: ~E
var first: T {
get
@_lifetime(self: copy self, copy newValue)
set
}
var second: U { ... }
}In the dependency model, imagine refining PairProtocol so that a mutating method no longer propagates both dependencies:
protocol PairProtocol: ~E {
associatedtype T: ~E
associatedtype U: ~E
var first: T {
get
@_lifetime(self.first: copy newValue)
set
}
var second: U { ... }
}With the new protocol, this code is legal:
var anyPair: PairProtocol = OldPair(scopeA.x, scopeA.y)
anyPair.first = scopeB.x
let y = anyPair.second
// 'anyPair' is implicitly destroyed here
consume scopeB
read(y) // violates OldPair's lifetime (and possibly it's implementation)But if OldPair was defined without nested lifetimes, its setter would not be able to remove a dependency:
struct OldPair<T: ~E, U: ~E>: ~E, PairProtocol {
var first: T
get
@_lifetime(self: /*copy self,*/ copy newValue)
set
}
var second: U {...}
}This simply means that protocols with multiple ~E members cannot be fully refined with nested lifetime. This is unlikely to be a problem in practice.
Now let's consider migrating from the current non-nested dependency model to a lifetime types model, which naturally supports nested lifetimes.
"Container" structs or enums with ~E elements are forward compatible with lifetime types for all non-mutating methods. self is the dependency source for non-mutating methods that return a ~E element, which makes the lifetime of the resulting dependent element more constrainted in the current model than with lifetime types.
Ref<~E> and Span<~E> are forward compatible with lifetime types. The initializer of an immutable container establishes its lifetime dependencies, and those can't be changed by any of its methods. In the current model, the initialization and all uses of that immutable container must be within the lifetime of its initial element values. Furthermore, any element values retrieved from the container are restricted to the container's lifetime. Lifetime types impose the same requirement that the immutable container must be initialized within the elements' lifetimes. Lifetime types do, however, allow elements to outlive their container. This means that code valid for lifetime types is a superset of code supported under the current model.
func retrieveElement(container: InlineArray<Ref<R>>) {
let span = container.span
let ref = span[0]
return ref // ERROR: use outside of 'span' lifetime - OK with lifetime types
}Mutating methods are problematic because self is the dependency target (in addition to being a dependency source). The resulting mutated value of self can, therefore, have a more constrained lifetime than the incoming value of self. In the section called "Mutable storage - Local variables", we talked about the problem of mutating operations adding dependencies to a variable. With nested lifetimes, this problem is more prevalent because it arises with most mutating container APIs like append, insert, and the subscript setter. InlineArray<~E> is not forward compatible because of the subscript setter.
Similarly, a container protocol is only forward compatible with lifetime types if it has no mutable requirements. A mutable type may conform to such a protocol, but its mutating methods will never be exposed via the protocol, and, because the concrete type is not forward compatible, the mutating methods cannot be exposed to the new model.
In the "Mutable storage - Inout parameters" section, we discuss how lifetime types could emulate the dependencies behavior by allowing inout parameters to specify that the incoming and outgoing values have different lifetime types. If we were willing to commit to that feature, then we could give mutable containers, such as InlineArray, support for ~E element now and migrate those containers to lifetime types later.
Lifetime types support generic functions that are polymorphic over lifetime constraints.
Consider a transformer function that takes a generic transform closure. With the current dependency model, it can be written as follows:
@lifetime(copy arg)
func transformer<A: ~Escapable, R: ~Escapable>(
arg: A,
transform: @lifetime(copy arg) (_ arg: A) -> R
) -> R {
return transform(arg)
}This is fine for transforming across different shapes of the same dependent value, such as unwrapping an optional:
@lifetime(copy optionalSpan)
func foo(optionalSpan: Span<Int>?) -> Span<Int> {
return transformer(optionalSpan) { optionalSpan! }
}But the same transformer cannot be used to express dependencies on values other than the transformed argument. For example, the transform closure cannot return a captured value as follows:
@lifetime(copy anotherSpan)
func foo(optionalSpan: Span<Int>?, anotherSpan: Span<Int>) -> Span<Int> {
return transformer(optionalSpan) { anotherSpan }
}To handle both cases above, the transform closure must conservatively depend on both its argument and its captured values:
@lifetime(copy arg)
func transformer<A: ~Escapable, R: ~Escapable>(
arg: A,
transform: @lifetime(copy transform, copy arg) (_ arg: A) -> R)
-> R {
return transform(arg)
}
If, on the other hand, lifetimes constraints are encapsulted by generic type, then normal type erasure allows generic functions to operate on ~Escapable types without a-priori specifying depenency relationships. So, for example, the transformer no longer needs lifetime annotations:
func transformer<A: ~Escapable, R: ~Escapable>(
arg: A,
transform: (_ arg: A) -> R
) -> R {
return transform(arg)
}Lifetime types eliminate the need for the diagnostic pass to reason about the lifetime of generic ~E values, but instead require complex type inferrence.
In the current model, the lifetime checker analyzes the lifetimes of all ~E values in the transformer implementation. It checks that the returned value has a dependency on whichever argument are declared lifetime dependent sources. With lifetime types, on the other hand, the return value's lifetime cannot be checked because it has an abstract type parameterized on the function signature. Its dependencies won't be known until its type is fully specialized. That's not possible in Swift because generics are not compile-time monomorphised. The safety of this approach rests on the following principle: return values of abstract ~E types are always safe because type substitution guarantees that they depend on a scope provided by the calling function. In other words, a function can always return a ~E value as long as the value's type does not include a concrete lifetime scope. Ultimately, the calling code that binds the generic types will resolve the abstract lifetime constraints to scopes available in the caller. The caller's concrete implementation could be written just it is as in the current proposal, but we'll use syntax simlar to Rust to distinguish the two approaches and make it obvious that the lifetimes affect the resulting types:
func foo<'a, 'b>(optionalSpan: Span<'a, Int>?, anotherSpan: Span<'b, Int>) -> Span<'b, Int> {
return transformer(optionalSpan) { anotherSpan }
}The consequences for compiler design are significant. In general, the compiler can no longer determine lifetime dependencies from an abstract function type. Resolving lifetime dependencies instead requires a mechanism for global type inference. Now, the compiler must infer the closure's dependencies from its implementation. Here, it resolves transform's functions generic types A => Span<'a, Int>, R => Span<'b, Int>.
The @_lifetime annotations currently in use on generic APIs generally represent additional constraints that won't apply with lifetime types. So migrating to lifetime types usually means lifting those unnecessary constraints. Care must be taken, however, when multiple parameters of the same generic type appear in the signature. By default, the current model creates a dependency on all those parameters:
/* DEFAULT: @lifetime(copy a, copy b) */
func mergeElements<T: ~Escapable>(_ a: T, _ b: T, _ merge: (_ a: T, _ b: T) -> T) -> T {
return merge(a, b)
}Migration then simply means removing or ignoring the @_lifetime annotation.
But in some cases, lifetime types can introduce new lifetime restrictions. For example, if we explicitly annotate a function such that one of the ~E parameters is ignored:
@lifetime(copy a) /* NO dependency on b */
func mergeElements<T: ~Escapable>(_ a: T, _ b: T, _ merge: (_ a: T, _ b: T) -> T) -> T {
return merge(a, b)
}Then dropping the annotation would introduce a new scope restriction. To emulate the behavior with lifetime types, we need unbound generic lifetime, which is a form of higher-kinded type.
func mergeElements<scope a, scope b, T: ~Escapable>(_ a: @scoped(a) T, _ b: @scoped(b) T, _ merge: (_ a: @scoped(a) T, _ @scoped(b) b: U) -> T) -> T {
return merge(a, b)
}As this example shows, in some situations, lifetime types will cause an annotation explosion relative to the current dependency model.
We might think of unbounded generic lifetimes as a form of generic associated types, which is a restricted form of higher-kinded type. Here is a trivial example that makes an associated type explicit (WIP: I'm not sure this syntax makes sense):
protocol WithLifetime {
scope generic
associatedtype @scoped(generic) Ref: ~Escapable
}
struct TwoRefs<A: WithLifetime> {
scope a
scope b
first: @scoped(a) A.Ref
second: @scoped(b) A.Ref
}Supporting lifetimes in first order functions is essentially a problem of supporting lifetimes in a generic context.
The current dependency model allows a closure result to depend on borrows of all its captured variables. The closure definition syntax could be expanded to indicate which captures the closure result depends on. This has no effect on the partially applied closure's function type. For example, the closure could specify which captures have borrowed, copied, or mutable lifetimes.
func foo(_: () -> ()) {...}
let unrelated = ...
let array1 = [0, 1]
var span = array1.span
let array2 = [0, 1]
foo { @lifetime(span: borrow array2, copy span) in
_ = unrelated
span = (...) ? array2.span : span
}Lifetime types do away with such closure annotations. Instead, the closure context implicitly takes a generic lifetime parameter for every ~E capture. Those generic lifetimes are bound to the lifetime of the captured value from the parent function in which the closure is defined. This implies that all first-order functions have an implicit generic parameter that represents the closure context with all captured types and their lifetimes.
In the dependency model, first-order functions can often refer to ~E types without any lifetime annotation. With lifetime types, this requires support for an unbound lifetime type. Consider a simple reduce:
func reduce<S: BorrowingSequence, R>(initial: R, values: S, f: (R, Ref<S.Element>) -> R) -> R {
var r = initial
for v in values {
r = f(r, Ref(v)) // Ref(v) is scoped to the current loop iteration.
}
return r
}The dependency model does not need to model any lifetimes in the function type of f. But, with lifetime types, Ref has an implicit generic lifetime. The caller of reduce cannot bind that lifetime. Instead, it is bound inside the implementation of reduce to the current loop iteration.
In the case above, I expect the unbound lifetime to be handled by type system magic without affecting the programming model. There are, however, cases in which the unbound lifetime needs to be named. Consider adding another closure to the reduce function that returns a ~E value. With dependencies we write:
func reduce<S: BorrowingSequence, T: ~Escapable, R>(
initial: R,
values: S,
borrowElt: @_lifetime(borrow elt) (_ elt: S.Element) -> T,
f: (R, T) -> R) -> R
{
var r = initial
for v in values {
r = f(r, borrowElt(v))
}
return r
}With lifetime types, this demands a syntax for higher-rank polymorphism, which we've accomplished by referring to a parameter name:
func reduce<...>(...,
borrowElt: (_ elt: S.Element) -> @scoped(elt) T,
...)This syntax also needs to support referring to names from the declaration context. For example, if we want to return the closure's ~E result back from the closure-taking function:
func transformer<S, R: ~Escapable>(
source: S,
transform: (_ arg: S) -> @scoped(source) R
) -> R {
return transform(source)
}TBD: These examples have completely ignored the difference between borrowed and copied lifetimes.
Consider an Iterable protocol:
protocol Iterable<Element>: ~Copyable, ~Escapable {
associatedtype IterableIterator: ~Copyable & ~Escapable
associatedtype Element: ~Copyable & ~Escapable
where Element == IterableIterator.Element
@_lifetime(&self)
func makeIterator() -> IterableIterator
}Each call to makeIterator depends on a new local scope. This requires the associated type IterableIterator to be "unbound". As explained in the previous section, makeIterator can then be written as:
func makeIterator() -> @scoped(self) IterableIterator
On the other hand, Element need only be restricted to the iterable container. As such, its lifetime will be bound by the protocol conformance. We need something like an @unscoped attribute to distinguish between the two forms of associated types:
associatedtype @unscoped IterableIterator: ~Copyable & ~Escapable
associatedtype Element: ~Copyable & ~EscapableHere, @unscoped marks IterableIterator as a "generic associated type" (it has a higher-kinded lifetime), telling the compiler not to bind its lifetime during conformance.
Yielding accessors produce values that depend only on the coroutine's local execution scope. The @scoped syntax will need to support naming such a scope. For example:
struct Container {
var value: @scoped(value) Ref<T> { yielding borrow { ... } }
}