[Pitch] Non-Escapable Types and Lifetime Dependency

[Michael_Ilseman]

@Andrew_Trick

The stand-alone @lifetime annotation would give us a way work with lifetime dependence features that is decoupled from, and doesn't clutter function signatures.

For syntax, we should first consider how we want it rendered in documentation, then how we want to read the function declaration in syntax, and only then how we would want to write it in syntax.

For documentation, I increasingly feel that the decoupled form would be best, either as arrows, a separate box, or at least a separate line.

We could have interspersed syntax and the renderer could extract that info into a separate line. However, this rendering preference hints that we may prefer to similarly read declarations in syntax on a separate line.

As for writing the declaration, it took me an embarrassingly long time to realize that interspersed dependsOn(x) was a type annotation. The rules for where to put self's lifetime in the interspersed form will take a while to internalize. Finally, I am very hesitant to add more parenthesis interspersed with function declarations, as we already have tuples and closure syntax.

We use the argument name instead of the label:

@lifetimes(self: x, y: z, returnValue: z)
func foo(from x: X, to y: Y, using z: Z) -> Z

This is consistent with how the argument name, not the label, is used in the body of the function as well as in the documentation for that function.

The only time that I'd prefer to write an interspersed lifetime annotation would be when there's only one lifetime to specify, and hopefully the inference rules would make this exceedingly rare. The documentation could explicitly render the implicit lifetime dependence.

[Michael_Ilseman]

I think that we should split this proposal into 2, one which covers the current needs of Span and UTF8Span and one which covers the future needs of yet-to-be-pitched mutation.

Inferred lifetimes is sufficient for Span and UTF8Span. Span needs a non-escapable return value (or var) to have the lifetime of self. UTF8Span additionally wants a validating initializer, so it needs self to have the inferred lifetime of its sole borrowing parameter. The documentation engine can render these lifetimes explicitly, while someone reading or editing the declarations in a source editor would already be familiar with the types involved.

The rest of this proposal's complexity, from syntax to multiple lifetimes to the difference between inherited and scoped lifetimes, is not needed by anything being pitched in the near term. Mutation is where the complexity is, and I feel it makes sense to have progressive disclosure for the non-mutating cases.

[Joe_Groff]

@rauhul

@Joe_Groff

struct TwoOfThem: ~Escapable {
    lifetime a
    lifetime b
    var first: dependsOn(.a: self.a) First
    var second: dependsOn(.a: self.b) First
}

Typo? (Or maybe I didn’t grok the model)

@Joe_Groff

struct Nested: ~Escapable {
    lifetime a
    lifetime t: T
}

Similarly, is this missing a generic parameter?

Thanks, I fixed these examples.

[Joe_Groff]

@ellie20

If I'm not wrong, I think it would be the opposite. It would be possible to add a lifetime variable even without a default, because a new lifetime variable wouldn't affect any existing lifetime variables. Each new lifetime variable would implicitly have dependsOn(self) [1], which only affects that lifetime variable, not any others. The only way I can imagine a new lifetime variable causing breakage is if the compiler assumes that a type's self lifetime can be deduced from an exhaustive list of the type's lifetime variables.

If the lifetime exists, then (AIUI) it needs to be bound to something even if it isn't explicitly bound, which is where the default would come into play.

@ellie20

Meanwhile, it wouldn't be possible to remove a lifetime variable, because someone might've written it in their source code. At most, a lifetime variable could be turned into an alias of another lifetime variable or the self lifetime.

That's a fair point. The lifetime would have to continue to exist for source compatibility, though its actual impact on the value's dependency could be eliminated.

These sorts of evolution could perhaps be approximated in Rust using type aliases:

// V2 of a struct introduces a new lifetime dependency
struct FooV2<'a, 'b> { ... }

// Source compatibility alias defaults the new variable to 'a
type FooV1<'a> = FooV2<'a, 'a>
// type FooV1<'a> = FooV2<'a, 'static> // or to 'static

// V2 of a struct loses a lifetime dependency
struct BarV2<'a> { ... }

// Source compatibility alias discards the unnecessary lifetime
type BarV1<'a, 'b> = BarV2<'a>

[Joe_Groff]

@CharlesS

Obviously, none of these are ideal. Please, pretty please, I beg you, for the love of God, Montresor, can we please have a Spannable or similarly named protocol that provides some kind of method to get a Span of a collection's contents, and put it on the standard library? It would really help a lot in writing ergonomic Swift libraries.

One benefit of lifetime dependencies will hopefully be that we need withSpan { } style APIs less often, since a span property with a lifetime dependency will be able to implicitly keep the source of the span alive long enough without making the developer write out the closure scope. That would make your #4 (taking a Span directly) more palatable, since the caller code would at worst look like foo(array.span) rather than array.withSpan { foo($0) }.

From an efficiency standpoint, code that only wants to process contiguous blocks of memory should IMO just take a Span directly, since being generic over a Spannable protocol would induce either unnecessary metadata passing and generic indirection, or unnecessary generic specialization, for a block of logic that largely doesn't care about the specific Spannable type that the span came from. Independent of this proposal, it would be good for the language to explore how we might make it easier to encourage the use of generic 'shells' around concrete implementations that minimize unnecessary propagation of genericity while still preserving cleanness and convenience at the API surface.

[Alvae (Dimi Racordon)]

I realize that all my talk about Hylo may have buried the lede. So at the risk of obnoxiously repeating myself, I'll re-state my concerns without appealing to another language.

I think lifetime dependencies are a very scary feature to bring in, especially because Swift already (partially) solves the lifetime dependency problem with a much simpler mechanism.

The purpose of my example with min was to demonstrate that subscripts already keep track of lifetimes, at least if we consider those written with _read/_modify accessors. We should also note that the type of the projected (i.e., lifetime-dependent) value is irrelevant. An Int may be lifetime dependent on another value because it is notionally a part of another value; that is, it belongs to a whole/part relationship. The fact that this Int may be copied to escape for free does not change this whole/part relationship.

One of my favorite examples is as follows:

struct Angle {
  var radians: Double
  var degrees: Double {
    _read { yield radians * 180.0 / .pi }
    _modify {
      var d = radians * 180.0 / .pi
      yield &d
      self.radians = d * .pi / 180.0
    }
  }
}

var a = Angle(radians: 0)
a.degrees += 90
print(a.radians) // ~(pi / 2)

Here, a.degrees is notionally part of a, just like a.radians is, and in that sense it is lifetime-dependent. Whether or not it's a Double does not matter.

This observation exemplifies that, in my opinion, whole/part relationships are actually more important than lifetimes for the user model. The former relates to tangible concepts (what is a span to an array, what is a key/value pair to a map, etc.) whereas lifetimes on their own are merely complications caused by reference semantics.

Both a.radians and [1, 2, 3].span(in: 0 ..< 5) are (notionally) parts of a some whole. The difference between the two is that the latter can't be escaped meaningfully without its whole. That is precisely where escapability enters the picture.

If we accept this premise, at least for the sake of the argument, subscripts become a far more attractive option to represent lifetime-dependent (really, notional parts) that any annotation system. From the user's perspective, we get the choice to:

• project a notional part with a subscript; or
• return an independent value from a function.

No annotation is necessary and, perhaps even more importantly, no additional type system feature is necessary either. The fact that Rust-like lifetime elision/inference can make a function with references "look" like a Hylo/Swift subscript doesn't reduce the complexity of the actual type system underneath. As a result, forming a complete understanding of the system requires thinking about lifetimes all the time, because lifetimes are actually part of signatures, whether they are stated explicitly or not.

Rust users have become used to "fight" their borrow checker, despite all the nice elision and inference. I worry that Swift users will have to do the same.

[Joe_Groff]

Early Rust once thought as you did. Yes, you can use a borrow-yielding coroutine as an extremely limited form of nonescaping value, but there are several limitations in doing so.

• If the yielded value requires a semantic guarantee that it not escape, the only way to enforce that is to ensure that its type has no operations that expose an owned value to callers, such as copying, initializers, or functions that return by value, since doing so would allow the owned value to be moved out of its scope.
• If the yielded value represents part of the owning value, rather than literally being part of the owning value, then treating it like part of the underlying value limits your ability to manipulate the yielded value.

The Span type in particular has both of these properties. An Array does not literally contain a Span as a field, but you could in principle have a span property that yields a borrowing Span over its elements. In order for this to be safe, Span would have to be noncopyable, and it would have to be impossible to construct a Span manually from the same endpoints. Noncopyability is already a severe expressivity limitation, but as a borrow, the Span you get would also have to be immutable. This rules out the ability to do gradual iteration over the span, such as by using popFront to eliminate elements as they get parsed, unless you write such code in an awkward recursive style. Neither the copyability nor the mutability constraint inherently apply to Span itself, only the elements it references. By treating Span as a non-escapable type, we can track that dependency on the immutability of the elements, while allowing Span itself to be freely copied and mutated within the scope of its dependency, allowing for natural gradual iteration and multi-pass processing.

The other general limitation of this approach is that it's sufficient only for the "first-order" dependency relationships as I described them in my post above. If we ever want to be able to support aggregates or collections of nonescaping values (Spans of Spans) then not being able to track the dependencies carried by the elements independent of the collection itself also leads to harsh expressivity limitations.

[Andrew_Trick]

@Joe_Groff

The other general limitation of this approach is that it's sufficient only for the "first-order" dependency relationships as I described them in my post above. If we ever want to be able to support aggregates or collections of nonescaping values (Spans of Spans) then not being able to track the dependencies carried by the elements independent of the collection itself also leads to harsh expressivity limitations.

Put another way, Swift APIs revolve around the Optional type and similar abstractions that require lifetime dependencies to handle nonescapable types.

[Alvae (Dimi Racordon)]

@Joe_Groff

If the yielded value requires a semantic guarantee that it not escape, the only way to enforce that is to ensure that its type has no operations that expose an owned value to callers, such as copying, initializers, or functions that return by value, since doing so would allow the owned value to be moved out of its scope.

Sure. But isn't that what ~Copyable and/or ~Escapable types would imply anyway?

I may miss something obvious but it doesn't seem to me that these operations are particularly difficult to subtract from an API. At least that is not significantly harder than teaching a type system about non-copyable and immovable/non-escapable types.

Rust decided that all types would be movable. This choice makes it difficult to prevent values (i.e., not borrows) from escaping but it is my understanding that Swift has to overcome the same problem, whether or or not it will grow a path-dependent lifetime system.

@Joe_Groff

By treating Span as a non-escapable type, we can track that dependency on the immutability of the elements, while allowing Span itself to be freely copied and mutated within the scope of its dependency, allowing for natural gradual iteration and multi-pass processing.

If you have a type to express "remote" parts, similar or identical to your borrow types, you can say that any other type accepting a remote part in its constructor becomes lifetime-dependent on the whole from which the remote part is taken. This approach gets you surprisingly far. For example, that is how Hylo tracks the lifetime dependencies of a lambda.

fun f(_ n: Int) {
  var g = fun[var m = 0]() -> Int {
    &m += n
    return m
  }
  print(&g())
  print(&g())
}

Here, g basically counts by strides of n. Crucially, g is mutable (it modifies m) and yet it "borrows" n immutably. I guess it would look like that in Swift:

struct G: ~Escapable {
  let n: Borrow<Int>
  mutating func call() -> Int { m += n; return m }
}
// Note: Again, the fact that `Int` is trivial to copy is irrelevant.

There are limitations, of course, such as the fact that I could never return g from f, even if technically its caller would be able to reason about the lifetime dependency between n and the return value, should we have Rust-like lifetime parameters or the path-dependent lifetimes suggested above. Under the proposal, in contrast, one could write func f(_ x: borrowing Int) -> dependsOn(x) G (I suppose). Moreover, we have not completely figured out the calculus surrounding remote parts and there are still open questions.

My broader point is that there exist points in the design space that can accommodate most use cases without going as far as (or ever farther than) Rust did. It is true that first-class references (or morally equivalent first-class borrows) give you more expressiveness but they also have costs. I am not at all convinced that the benefits of full-feature alias tracking are greater than this cost. Complex borrowing schemes can often be worked around and I am not too sad if some of them may require more awkward programming patterns or safe APIs wrapping unsafe operations if the type system as a whole can remain simpler. Of course, that's just my two cents.

@Andrew_Trick

Put another way, Swift APIs revolve around the Optional type and similar abstractions that require lifetime dependencies to handle nonescapable types.

We can use the aforementioned remote parts to address this use case. Also note that remote parts could likely be expressed as a struct in Swift using only ~Copyable if we had a way to yield from a lambda passed to withUnsafePointer(to:).

In any case, I wanted to state that full-feature alias tracking isn't the only way to express many of the things we'd like to do with projections. I think this point's been understood and so I won't insist further. This thread's proposal is quite interesting and I am excited to see where it leads.

[dabrahams (Dave Abrahams)]

I of course agree with Dimi. Expressing non-esapability is essential, but the important use-cases can be covered without introducing the complexity of a named lifetime system. It isn't important to be able to express every possible use case without using an (encapsulated) unsafe construct. We saw from the beginning of Hylo's design process that we'd need something like Span to fill the role of Swift's Slice, and we designed the language to accommodate that use case without introducing named lifetimes. Named lifetimes have been shown by Rust to be difficult for users. I realize this design isn't exactly the same as Rust's, but it's similar enough.

I fear that Swift has lost an ethos of saying “no” to complexity that doesn't pull its weight and that this is an example.

[Andrew_Trick]

@Alvae

struct G: ~Escapable {
  let n: Borrow<Int>
  mutating func call() -> Int { m += n; return m }
}
// Note: Again, the fact that `Int` is trivial to copy is irrelevant.

We would need a MutableBorrow, but yeah, that's the idea. Lifetime dependencies makes this possible. The compiler doesn't generally have visibility into the type, so you end up with:

struct G: ~Escapable {
  @lifetime(copy n) // inferred
  init(n: Borrow<Int>)

  @lifetime(copy self) // inferred
  let n: Borrow<Int> { get { _n } }

We currently have an implementation of lifetime dependencies that is not significantly more complicated than ~Escapable. A dependency between a function parameter and its result is reduced to one of the primitive operations on ~Escapable values: copy, borrow, or mutate.

I don't think we have the luxury of expecting programmers to learn a new style to fit a small subset of APIs. Local variables and function composition should work as expected without the programmer needing to think about escapability or lifetime depedence.

@Alvae

In any case, I wanted to state that full-feature alias tracking isn't the only way to express many of the things we'd like to do with projections. I think this point's been understood and so I won't insist further. This thread's proposal is quite interesting and I am excited to see where it leads.

I don't understand what complexity you are referring to yet. Lifetime dependencies are logically projections that can be expressed at the function level. Rust has a complex type system designed to resolve those dependencies. But, after type resolution, the only thing the compiler should know about are those dependencies.

I think the argument here is against the complexity we would take on with named lifetimes in terms of the type system's rules for resolving dependencies and its diagnostic capabilities. Resolving a function's dependencies based on named lifetimes could become complicated when generic types are involved. That is not part of the current proposal, but people have understandably wanted to know if it would be possible to build upon the current design without the current semantics backing us into a corner. What's driving consideration of that feature is the ability to nest ~Escapable types without compromising usability and a desire to build new protocols that don't inherently assume copyability or escapability.

[CharlesS (Charles Srstka)]

Do we know yet whether ~Escapable and the types it enables, like Span, will be available in existing versions of macOS / iOS / etc. (), or will they only be available to projects that target not-yet-released versions of the OS?

[Karl]

We do not yet have back-deployment for types, so we probably shouldn’t expect it

[tshortli (Allan Shortlidge)]

Span specifically wouldn't be available for earlier deployment targets because it is a new type and there's no existing mechanism for back deploying types. Your own type that has ~Escapable may be deployable to older runtimes, though, depending on how the feature interacts with the language runtime. I suspect ~Escapable types are compatible with older runtimes. The proposal text says this:

These same considerations ensure that escapable types can be shared between previously-compiled code and newly-compiled code.

Maybe the proposal authors can clarify what to expect with regard to deployment target and using ~Escapable.

[Andrew_Trick]

Conditionally ~Escapable generics should back-deploy to the same extent as ~Copyable. Maybe @kavon can comment on the deployment target. Unconditionally nonescapable types, like Span cannot back deploy.

[kavon (Kavon Farvardin)]

Like noncopyable types, nonescapable types mostly are back-deployable for Apple platforms, except for specific situations. Today you cannot dynamically cast noncopyable types themselves at all, as there's some work needed in the runtime to make that work. Perhaps the same restriction is needed for non-escapable types.

The situation where things can go wrong is anything related to dynamic casts, with is, as? and as!, on a type that is Copyable, but has a generic parameter that is non-escapable/non-copyable. The runtime bundled into prior Apple platforms doesn't know how to check conformance requirements for Copyable and Escapable, so it will give bogus results when determining if a type conforms. Here's an example, compiled with -enable-experimental-feature NonescapableTypes -target arm64-apple-macos14:

protocol P {}

struct MyType<T: ~Escapable> {}
extension MyType: P /* where T: Escapable */ {}

func test<T: ~Escapable>(_ val: MyType<T>) -> (any P)? {
  return val as? any P
// error: runtime support for casting types with nonescapable 
//        generic arguments is only available in macOS 15.0.0 or newer
}

test(MyType<Int>()) // should succeed
test(MyType<NonEscapableThing>()) // should give nil

Notice that MyType is Copyable and I'm casting it to any P, to which it only conditionally conforms, if and only if that type T at runtime is actually Escapable. The machinery to check for escapability simply isn't present on older runtimes, so this becomes an availability error, to avoid bogus casts.