[Pitch] Non-Escapable Types and Lifetime Dependency

Evolution Pitches
103

So many new keywords. Would much rather see a rust style lifetime annotation.

1 Like
104

Apologies if this has come up before, but I'd like to suggest this as the syntax for explicitly marking dependencies:

-> depends(x) NE    // shares the dependency of x, which must be non-escaping
-> mutating(x) NE   // depends on the scope of the mutation of x, which must be inout
-> borrowing(x) NE  // depends on the scope of the borrow of x, which must be borrowing

I understand that mutating and borrowing are redundant in the obvious sense of repeating information previously written in the declaration (sometimes as literally that same keyword). But:

  • Copied and scoped dependencies are different, and programmers will think of them as different.
  • There are ambiguous cases that require them to be disambiguated, such as when a function takes a non-consuming argument of non-escaping type.
  • I suspect that quite a lot of the functions that people write that return dependent values are going to be non-consuming methods on non-escaping types, so those ambiguous cases will be far from marginal.
  • The rules around inferring dependencies remove a lot of the need for these keywords in simple cases, which raises the relative frequency of the ambiguous cases.
  • Textually reinforcing the nature of the dependency is not actually bad.
  • The fact that there are formation restrictions on the dependencies is not a real problem.
9 Likes
105

Indeed. We originally proposed a similar syntax to what you have above. We later observed that all combinations of dependence syntax and parameter type were either illegal or redundant except one rare case: a nonescapable value may produce another nonescapable value that depends directly on the first nonescapable value.

The one example where we need a modifier for the dependence kind:

// An array that owns its elemente, but does not own its storage
struct FixedCapacityArray: ~Escapable {
  // Need the explicit 'scoped' modifier so 'self' cannot be modified while we have a Span.
  func getSpan() -> dependsOn(scoped self) Span
}

I'm not as motivated by this reasoning because, in the future, escapable types might also have dependencies. I'll explain in a separate post because it's a long discussion. This means we may also want to specify copied dependence on escapable types (currently we only allow 'scoped') If the source of a copied dependence has no lifetime dependence in the caller, then it would be ignored.

I was concerned about reusing borrowing because it needs to occur in parameter position, but does not mean the same thing as the borrowing parameter modifier:

func foo(arg1: borrowing A, arg2: borrowing(arg1) inout A) {
  arg2 = arg1
}

We could even have dependencies from a borrowed argument:

func foo(arg1: borrowing(arg2) borrowing A, arg2: consuming A) {
  consume(arg2)
  _ = arg1 // ERROR
}

Also note that, eventually we may end up with three different meaning for borrowing in the same declaration:

func foo(arg: borrowing A) -> borrowing(arg) borrow R

Another option:

lifetime(copy x) NE   // likely default when the source is nonescapable
lifetime(mutate x) NE // always redundant
lifetime(borrow x) NE

When bikeshedding syntax, keep in mind both the common case and the fully expressive case. We will need to allow a value to depend on multiple lifetimes, and maintain their distinction. So the general form of the dependence syntax should be thought of as:

dependsOn(target.component: source.component)

where the target can be inferred from context, but not its component:

Example:

  struct S: ~Escapable {
    @lifetime
    let a: T

    dependsOn(self.a: arg1) func foo(arg1: dependsOn(.a: arg2) S, arg2: T) -> dependsOn(.a: arg2) S
  }

With my suggestion, that becomes:

lifetime(target.component: [copy|mutate|borrow] source.component)

lifetime(self.a: arg1) func foo(arg1: lifetime(.a: arg2) S, arg2: T) -> lifetime(.a: arg2) S

3 Likes
106

One concern I have about this formulation is that if I'm understanding correctly it would essentially make borrowing(x) the easiest default for adopters to use since it would cover both escapable and non-escapable borrows, but for non-escapable borrows results in a lifetime that may be more restrictive than necessary for callers. I think there's values in the primary/default option assuming the maximal lifetime (i.e., shared dependency) and putting the narrower use case (scoped) in deliberate secondary position. If we don't, I worry it won't be uncommon for APIs to ship with borrowing(x) dependencies that really could be depends(x), resulting in a worse experience for API consumers.

Although, I suppose that the relationship is flipped for function parameters, where assuming the maximal lifetime is actually more restrictive on API consumers... so perhaps this is not actually a line of reasoning that leads anywhere particularly useful. :slight_smile:

2 Likes
107

A question that has come up a few times in the discussion about lifetime dependency in this thread is, how will Swift's lifetime dependency feature stack up to Rust, both in the near term, and in the future? I took some time to explore this topic. This question is important to answer because Rust is perhaps the only other successful mainstream programming language with a comparable feature, and yet we're doing something different, so we should understand how the functionality in Swift relates to Rust, and justify why we're doing something different. It's also important to ensure we have a design that not only handles simple cases well, but which can scale to handle more complex lifetime relationships.

The initial lifetime dependency proposal for Swift offers a limited lifetime dependency mechanism with the benefit that it allows for dependencies to be stated directly between a dependent value and its dependency without the need for abstractions like lifetime variables. This model allows for what I'll call "first-order" dependencies to be modeled between values, such as the dependency between a memory reference and the owner of the memory, but it loses expressivity when talking about aggregates or collections of independently lifetime-constrained values. Looking to the future, the proposal offers a vision for non-Escapable types to carry multiple lifetime members, which can track lifetimes independently, and which should match or exceed Rust in expressivity. However, Rust's design still has some ergonomic benefits that our eventual full lifetime model could learn from.

Note that, although I've followed Rust's development since 2009 and I think I have a decent intellectual understanding of its model, I don't write Rust very much, so I might get details of its model wrong, and Rust may be capable of expressing things in a way that I'm not aware of. Don't be afraid to point out anything I didn't get right here.

Comparing lifetime-dependent types and generics

First, let's compare how types with and without lifetime dependencies are declared in the two languages, and how generic types compose their lifetime dependency from their generic parameters.

Swift

In Swift, types are assumed to be escapable, meaning values of the type never have a lifetime dependency, so they implicitly satisfy the Escapable constraint. This includes generic parameters; <T> is assumed to represent an escapable type unless indicated otherwise. A type declares itself to be (potentially) lifetime-constrained by suppressing the implicit Escapable conformance, whether the type is directly lifetime-dependent or is composed of lifetime dependent elements. In the latter case, a type can indicate conditional escapability by conditional conformance:

// Int is lifetime-independent because it implicitly conforms to Escapable
struct Inches {
    var x: Int
}

// Ref is inherently lifetime-dependent
struct Ref<T>: ~Escapable {
    borrow pointee: T
}

// Optional can be lifetime-dependent.
enum Optional<T: ~Escapable>: ~Escapable {
    case none, some(T)
}
// However, it's lifetime-independent when its element type is.
// This is explicitly stated with a conditional conformance.
extension Optional: Escapable where T: Escapable {}

// Function generic over only escapable values
func onlyAcceptsEscapableValues<T>(_ x : T) -> Any {
    x
}

// Function generic over potentially non-escapable values
func alsoAcceptsNonescapableValues<T: ~Escapable>(_ x : T) -> Any {
    // error, `Any` requires `T: Escapable`
    x
}

Rust

Rust by contrast handles lifetime dependence through type structure. A concrete type is lifetime-constrained if it structurally contains lifetime variables. Conversely, a type with no lifetime variables, or in which all lifetime variables are bound to the 'static lifetime, is lifetime-unconstrained. Generic parameters are presumed to potentially contain lifetime variables, so generic types and functions work with lifetime-dependent values by default, without needing explicit annotation or conditional conformance. A generic parameter can be constrained to only accept lifetime-independent types by stating a 'static constraint. [More generally, a generic parameter can also be constrained to only include lifetimes that match or outlive 'a by stating a T: 'a constraint.] This introduces a distinction between directly lifetime-dependent types (which introduce type variables) and types that are potentially lifetime-dependent through composition:

// Inches is lifetime-independent because it has no lifetime variables
struct Inches {
    x: iptr
}

// Ref is inherently lifetime-dependent because it introduces a
// lifetime variable
struct Ref<'a, T> {
    pointee: &'a T
}

// Option is lifetime-dependent only when its payload is.
// This is inherent in the fact that `T` may be bound to a type
// involving lifetime variables, making the substituted `Option<Foo<'a>>`
// type lifetime-dependent, but `Option` does not itself introduce
// independent lifetime variables.
enum Option<T> {
    None, Some(T)
}
//
// No need for these to be explicit, since they're structurally true:
//
// impl<T: 'static> 'static for Option<T> {}
// impl<'a, T: 'a> 'a for Option<'a> {}

However, Rust code has to make 'static constraints explicit when code is generic over only lifetime-unconstrained values, such as when type-erasing values into dyn containers:

trait Trait {}

// Function generic over only escapable values
fn only_accepts_escapable_values<T: Trait + 'static>(x : T) -> Box<dyn Trait> {
    x
}

// Function generic over potentially non-escapable values
fn only_accepts_escapable_values<T: Trait>(x : T) -> Box<dyn Trait> {
    // error, `T` (which may have lifetime variables) may not live long enough
    // for `dyn Trait` (which has no lifetime variables) 
    x
}

Rust's model makes composition of lifetime-dependent types natural and largely automatic, with the tradeoff that generic code has to explicitly specify lifetimes when working with lifetime-independent values or lifetime dependencies that don't directly follow generic substitutions.

Swift can't adopt Rust's model directly because, as with the introduction of Copyable, we have to accept that the already-established Swift language assumes that all values are fully lifetime-independent, so there needs to be some way in which to opt types and generic parameters into carrying lifetime dependencies. Manifesting it as a protocol follows the established pattern we set with Copyable, although requiring composing types to state the conditional Escapable conformance does feel like a weakness compared to the "just works" model in Rust.

Swift stage 1: First-order lifetime dependencies

To gradually introduce lifetime dependencies as a concept into Swift, we plan to begin with what I'll call "first order" lifetime dependencies. This is a limited level of expressivity that allows for functions to describe lifetime dependencies among their arguments and return value, but without allowing for individual control of lifetimes in aggregates, wrappers, or collections. The goal is to provide enough of a feature for the "safe buffer pointer" Span type to be usable for efficiently and safely working with memory regions. This subset of functionality can't express many things that Rust can, but let's compare with Rust to get a sense of what the boundaries are.

Types

First-order lifetime dependencies only allow for describing the lifetime dependency of a value as a whole. This means that declaring a type to be ~Escapable in Swift is roughly akin to declaring it with a single lifetime variable in Rust:

struct Foo: ~Escapable { ... }
struct Bar: ~Escapable { ... }

struct Foo<'a> { ... }
struct Bar<'a> { ... }

When the type contains nonescapable fields, the notional lifetime variables of those fields' types are tied to the containing type's type variable:

struct Foobar: ~Escapable {
    var foo: Foo
    var bar: Bar
}

struct Foobar<'a> {
    foo: Foo<'a>,
    bar: Bar<'a>
}

And if a type is generic over nonescapable type parameters, those type parameters are also constrained to the same type variable:

struct Pair<T: ~Escapable, U: ~Escapable>: ~Escapable {
    var first: T
    var second: U
}

struct Pair<'a, T: 'a, U: 'a> {
    first: T,
    second: U
}

[Rust won't actually let you write that particular declaration since it considers the 'a in this case to be redundant, since structurally Pair has to depend on whatever lifetime constraints T and U carry. Making the lifetime variable explicit here hopefully helps make the point, though, that the initial Swift model only considers lifetime dependencies at the whole value level.]

Function dependencies

The initial Swift model allows for functions to indicate that a ~Escapable return value is lifetime-dependent on one of the arguments to the call. A function can state that its return value has the same lifetime constraint as one of its ~Escapable parameters, producing what the proposal calls a copied dependency:

func carry(x: Foo) -> dependsOn(x) Bar

which corresponds to a Rust declaration binding the return type's lifetime parameter to the input's:

fn carry<'a>(x: &'_ Foo<'a>) -> Bar<'a>

In either language, the result of a call can then be used within the same lifetime constraint as the argument, even if that argument's own lifetime ends:

let parent = S()
let bar: Bar
do {
    // make a `Foo` dependent on `parent`
    let foo = getDependentFoo(parent: parent)
    bar = carry(x: foo)
}
use(bar) // OK because the dependency is on `parent`, not on `foo`

let parent = S {};
let bar = {
    // make a `Foo` dependent on `&parent`
    let foo = get_dependent_foo(&parent);
    carry(foo)
}
use(bar) // OK because the dependency is on `&parent`, not on `foo`

In Rust, most lifetime dependencies have their origin in the formation of &'a T and &'a mut T references. Swift does not have first-class borrowing or inout types (yet?), and the formation of a borrow or inout reference is implicit as part of calling a function with borrowing or inout parameters. In order to represent dependencies on this implicit reference, the proposal also specifies scoped dependencies on a borrow or inout, which can be of any type, Escapable or not:

struct S {} // a normal escapable type

func borrow(x: borrowing S) -> dependsOn(/*scoped*/ x) Foo
func mutate(x: inout S) -> dependsOn(/*scoped*/ x) Foo

let parent = S()
let borrowed = borrow(x: parent)

If Swift didn't have borrowing and inout parameters as a primitive feature, but instead had explicit reference types, then the above might instead be expressed as a "copied dependency" on an explicitly-formed Borrow:

struct Borrow<T>: ~Escapable {...}
struct Inout<T>: ~Escapable {...}

func borrow(x: Borrow<S>) -> dependsOn(/*copy*/ x) Foo
func mutate(x: Inout<S>) -> dependsOn(/*copy*/ x) Foo

let parent = S()
let borrowed = borrow(x: Borrow(parent))

Since forming references in Rust is already explicit, the best analogy in Rust to a Swift scoped dependency is binding the result's lifetime parameter to a reference argument's lifetime:

struct S {} // a normal escapable type

fn borrow(x: &'a S) -> Foo<'a>
fn mutate(x: &'a mut S) -> Foo<'a>

let parent = S {};
let borrowed = borrow(&parent);

Any other borrowed or nonescapable parameters not involved in a Swift declaration's return dependency have their lifetime variables effectively ignored, as if elided or specified as '_ in Rust.

func borrow(from x: borrowing S, withHelpFrom y: Bar) -> dependsOn(x) Foo

fn borrow<'a>(from: &'a S, with_help_from: &'_ Bar<'_>) -> Foo<'a>

What you can't express

The initial Swift model can handle most cases involving one level of lifetime dependency (hence my calling it "first-order") between pairs of values. This is sufficient for many use cases, particularly working with memory regions containing escapable values dependent on an owner value. However, in its most limited form, it cannot represent dependencies involving more than one dependent and dependency. In Rust, the same type variable can be bound in any number of positions in a declaration:

fn foo<'a>(x: &'a Foo<'a>, y: &'a S) -> Bar<'a>

Because of Rust's lifetime subtyping rules, this has the effect not of requiring the reference &'a Foo<'a>, the value Foo<'a> itself, and the reference &'a S to have an exactly matching lifetime, but rather for there to be some common lifetime that all of the inputs share, which will then become the lifetime constraint for the result Bar. However, it's not a huge stretch to imagine the dependsOn syntax allowing for multiple dependencies to be specified. The above could perhaps be expressed in Swift as:

func foo(x: Foo, y: S) -> dependsOn(scoped x, copy x, copy y) Bar

although the "scoped" and "copy" terminology breaks down a bit here, since the resulting lifetime is not necessarily literally copied from or scoped to any of the individual parameters in the list, but is rather a lifetime that is matched or outlived by all of the stated lifetimes.

A more fundamental restriction rears its head when we start to look at aggregates or collections of lifetime-dependent values. In these situations, the first-order restriction begins to lose information, leading to expressivity limitations compared to a more elaborate system like Rust's. For instance, even a Pair of non-escapable elements cannot independently track the lifetimes of the two elements, since the following Swift:

struct Pair<T: ~Escapable, U: ~Escapable> {
    var first: T, second: U
}

var ne1 = NE()
var ne2 = NE()
let pair = Pair(first: ne1, second: ne2)
ne1 = pair.first

roughly corresponds to this in Rust:

struct Pair<'a, T: 'a, U: 'a> {
    first: T, second: U
}

let mut ne1: NE<'a> = NE {};
let mut ne2: NE<'b> = NE {};
let pair: Pair<'b, NE<'b>, NE<'b>> = Pair { first: ne1, second: ne2 };
ne1 = pair.first // <- ERROR

Since the first-order restriction lets a Pair carry only one lifetime dependency, its lifetime ends up being the shorter of its two elements' lifetimes, meaning that the longer-lived element cannot be extracted preserving its original lifetime.

This first-order restriction also leads to severe limitations when working with collections and spans of elements that are themselves lifetime-dependent. Consider an Array and Span that support nonescaping element types:

struct Array<T: ~Escapable>: ~Escapable {
    borrowing func span() -> dependsOn(scoped self) Span<T>

    mutating func append(_: dependsOn(copy self) T)
}

struct Span<T: ~Escapable>: ~Escapable {
    subscript() -> dependsOn(copy self) T
}

struct NE: ~Escapable {}

Code would reasonably want to access elements of the array through a span, and then feed those elements back into the original array. It's also reasonable to expect to take elements out of the array and use them with their original lifetime:

func test(a: NE, b: NE) -> NE {
    var array = [a, b]
    let element: NE
    do {
        let span = array.span()
        element = span[0]
    }
    array.append(element)
    let result = array.last
    return result
}

However, the single lifetime dependency restriction means that every successive method call produces a value with a stricter lifetime dependency than its arguments, meaning elements extracted from the span take on the lifetime dependency of the span, and elements extracted from the array take on the lifetime of the array. Overlaying the Swift code above with some hybrid Rust-like lifetime variable syntax:

// `a` and `b` have a lifetime 'a from the caller
func test<'a>(a: NE<'a>, b: NE<'a>) -> NE<'a> {
    // `array` has a lifetime 'b for the duration of the callee
    var array: Array<'b, NE<'b>> = [a, b]
    let element: NE<'b>
    do {
        // `span` has a lifetime 'c for the duration of borrowing `array`
        // in the `do` scope
        let span: Span<'c, NE<'c>> = array.span()
        // `element` therefore gets a lifetime 'c, but it needs at least
        // lifetime 'b to be assignable back into `array`
        element = span[0] // <- ERROR
    }
    array.append(element)
    // `result` gets a lifetime 'b copied from `array`, but it needs the
    // caller's lifetime 'a to be returnable
    let result: NE<'b> = array.last
    return result // <- ERROR
}

This suggests that the first-order lifetime dependency feature, as a general rule, is insufficient for expressing collections of values that themselves have lifetime dependencies.

Swift stage ∞: Named lifetimes

Ideally, we wouldn't paint ourselves into a corner with our lifetime dependency language design, so we should consider what a more complete lifetime feature for Swift looks like, and how what we're planning to ship in year one looks in context. Although Rust's model is a proven model for expressive handling of lifetimes, and its design handles lifetimes in a naturally compositional way when used with generic types, there are also opportunities for improvement:

  • Lifetime variables are always abstract and independent from scopes or declarations otherwise written in source code. This allows for flexibility and abstraction from type layouts without compromising safety, but introduces a layer of notational indirection that readers have to reason through. The dependsOn syntax for first-order lifetime dependencies directly relates the dependent value to the value it depends on, and it would be good to preserve that directness when possible even in more elaborate cases.
  • Swift places a high emphasis on library evolution. Rust's lifetime variables manifest as part of the generic signature of lifetime-dependent types, meaning that adding or removing them is a source-breaking change except in limited situations where the lifetime variables can always be elided. In principle, it should be possible to remove a lifetime variable, thereby eliminating a dependency from a type, or add a lifetime variable that defaults to 'static or an existing lifetime variable, without fundamentally breaking the API of a type.
  • Rust doesn't allow for a type to specify interior dependencies among fields of a type; for instance, a lifetime-independent value combining a dependent value with the value it depends on.

To provide comparable expressivity to Rust while addressing these shortcomings, the proposal alludes to named lifetimes as a future extension. This will allow ~Escapable types to specify multiple independent lifetimes to track as members of the type. Oftentimes, these lifetimes correspond directly to properties of the type. For instance, the Pair example above might be declared as:

struct Pair<T: ~Escapable, U: ~Escapable>: ~Escapable {
    lifetime var first: T
    lifetime var second: U
}

indicating that first and second are stored properties that have independent lifetime dependencies within Pair. The initializer and accessors for a type like this might specify how these lifetimes flow through the type as follows:

extension Pair {
    // A new Pair carries its `first` and `second` dependencies from their
    // corresponding element values
    init(first: T, second: U)
      -> dependsOn(.first: first, .second: second) Self

    // Accessing each field produces a value with the corresponding lifetime
    // dependency for that field.
    var first: dependsOn(self.first) T

    var second: dependsOn(self.second) U
}

This allows the usage example above to work:

var ne1 = NE()
var ne2 = NE()
let pair = Pair(first: ne1, second: ne2)
ne1 = pair.first

since it now corresponds to the following Rust:

struct Pair<'first, 'second, T: 'first, U: 'second> {
    first: T, second: U
}

let mut ne1: NE<'a> = NE {};
let mut ne2: NE<'b> = NE {};
let pair: Pair<'a, 'b, NE<'a>, NE<'b>> = Pair { first: ne1, second: ne2 };
ne1 = pair.first // OK now

Named lifetimes can be independent of the type's physical layout. Array and Span might be declared as follows:

struct Array<T: ~Escapable>: ~Escapable {
    // The lifetime of the elements in the array
    lifetime elements: T
    
    // A span's memory depends on this array, but its elements carry their
    // original dependency
    borrowing func span()
        -> dependsOn(.memory: scoped self, .elements: self.elements) Span<T>

    mutating func append(_ element: dependsOn(self.elements) T)
}

struct Span<T: ~Escapable>: ~Escapable {
    // The lifetime of the memory referenced by the span
    lifetime memory

    // The lifetime of the elements
    lifetime elements: T

    // Accessing elements preserves their original lifetime
    subscript(index: Int) -> dependsOn(self.elements) T
}

If we return to the example above:

func test(a: NE, b: NE) -> NE {
    var array = [a, b]
    let element: NE
    do {
        let span = array.span()
        element = span[0]
    }
    array.append(element)
    let result = array.last
    return result
}

it can now work as:

// `a` and `b` have a lifetime 'a from the caller
func test<'elements>(a: NE<'elements>, b: NE<'elements>) -> NE<'elements> {
    // `array` captures the elements' lifetime
    var array: Array<'elements, NE<'elements>> = [a, b]
    let element: NE<'elements>
    do {
        // `span` has a lifetime 'array for the duration of borrowing `array`,
        // but also preserves the element lifetime
        let span: Span<'array, 'elements, NE<'elements>> = array.span()
        // `element` carries the 'elements lifetime from the original
        // values
        element = span[0] // OK
    }
    array.append(element) // OK
    // `result` also gets the 'elements lifetime back from the original values
    let result: NE<'elements> = array.last
    return result // OK
}

Lifetime members can be typed, allowing for independent lifetimes to compose. The type of the elements lifetime in the Array and Span declarations above has type T corresponding to their generic parameter. When used with an element type that itself has multiple independent lifetime members, such as Pair, the element type's lifetime members are preserved and carried as subelements of the collection's lifetime:

var a = NE()
do {
    var b = NE()
    // Pair preserves `a` and `b`'s lifetimes independently...
    let pair = Pair(first: a, second: b)
    // ...meaning we can extract the value of `first` and use it with its
    // original lifetime to reassign back to `a`
    a = pair.first

    // We can create an Array carrying this compound lifetime dependency for
    // its `elements`...
    let array = [pair]

    // ...and when we extract an array's element, then the lifetime of
    // `elements.first` still allows us to use the first part of `Pair` with
    // its original lifetime
    a = array[0].first
}
consume(a)

So far this looks like a more verbose way to express compound lifetime dependencies that Rust's lifetime variables handle more or less automatically through generic substitution, though perhaps it's at least arguably more "direct" and less abstract in return. When it comes time to design and implement this model for Swift, we will probably want to spend time on ergonomics so that these common cases do not require a lot of boilerplate.

However, the named lifetime model also allows for the lifetime schema to be independent of generic substitution, unlike Rust. For instance, a type may want to be parameterized on potentially ~Escapable types while still itself remaining Escapable. For instance, a factory interface might work with lifetime-constrained types:

struct Factory<T: ~Escapable> /* : Escapable */ {
    var parameters: [String: Any]
    func create(in scope: borrowing T) -> dependsOn(scope) T
}

The Factory type itself has no reason to be lifetime constrained, and it may be useful to use the same factory to produce nonescaping values with different dependencies. In Rust, a type like Factory<Foo<'a>> would be structurally lifetime-constrained to 'a, and would only be able to construct Foo<'a> values with the same lifetime dependency. (Maybe it's possible in recent Rust to avoid this using higher-rank bounds and/or higher-kinded associated types, but I wasn't able to figure out how to do so.)

It's also useful to be able to package an owning value with one or more values that are lifetime-dependent on it. The Swift standard library does this for its COW collection types using Unsafe*Pointer, but it should be possible to express this safely using Span:

struct ArraySubset<T> {
    var owner: Array<T>
    var subrange: dependsOn(owner) Span<T>
}

Rust also can't express this sort of intra-value dependency directly (possibly until recently using the aforementioned features) since lifetime variables can only be declared as part of the generic signature and can't be directly bound to other declarations.

It's also possible that a type may be lifetime-dependent in ways that don't directly correspond to its generic parameterization:

protocol SomeProto {
    associatedtype Dependent: ~Escapable
}

struct Foo<T: SomeProto>: ~Escapable {
    // The dependency is parameterized on an associated type of `T` rather
    // than on T itself.
    lifetime parent: T.Dependent
}

This model should also allow for more flexibility in library evolution. A type could grow additional fields with potentially newly- independent lifetime dependencies, as long as those dependencies default to either immortal or an existing lifetime member of the type:

// This used to be a pair, but library evolution forced us to add a third
// field
struct Pair<T: ~Escapable, U: ~Escapable>: ~Escapable {
    // in version 1.0
    lifetime var first: T
    lifetime var second: U

    // added in version 2.0
    // the `third` lifetime defaults to `immortal` in existing code...
    lifetime third = immortal

    // ...since the `third` field defaults to nil. but new code which sets
    // `third` to non-nil can carry a different constraint
    var third: dependsOn(self.third) (any ~Escapable)? = nil
}

This will be important for staging in this more expressive lifetime model on top of the first-order model we plan to deliver initially, since any ~Escapable types that get published under the first-order model will effectively have only one lifetime member, and many of those types will want to be able to independently track additional lifetimes after we broaden the model.

Translating Rust to Swift named lifetimes

To test the theory that named lifetimes in Swift should be able to express anything that Rust can, and compare the ergonomics of the two languages' models, let's try translating some Rust constructs to this future version of Swift. Lifetime variables in a Rust type declaration:

struct Foo<'a, 'b> {...}

would map to individual lifetime members of the corresponding Swift type. The Swift type also has to become ~Escapable:

struct Foo: ~Escapable {
    lifetime a
    lifetime b
    ...
}

Non-'static generic parameters of a Rust type declaration:

struct Bar<'a, 'b, T: 'static, U, V> {...}
struct Baz<T: 'static, U, V> {...}

get corresponding typed lifetime members in the analogous Swift declaration. The Swift declaration becomes conditionally Escapable based on those generic parameters:

struct Bar<T, U: ~Escapable, V: ~Escapable>: ~Escapable {
    lifetime a
    lifetime b
    lifetime u: U
    lifetime v: V
}
// Bar is always ~Escapable because it has independent lifetimes

struct Baz<T, U: ~Escapable, V: ~Escapable>: ~Escapable {
    lifetime u: U
    lifetime v: V
}
// Baz has no lifetime variables independent of U and V, so can be
// conditionally Escapable
extension Baz: Escapable where U: Escapable, V: Escapable {}

Rust also allows for generic constraints involving lifetime and type variables. 'a: 'b indicates that the lifetime 'a must match or outlive 'b, and T: 'a indicates that any lifetime variables within T must all match or outlive 'a:

struct Zim<'a, 'b, T: 'a, U: 'b> where 'a: 'b { ... }

These correspond to dependencies among the lifetime members of the analogous Swift declaration, with the wrinkle that dependsOn communicates the opposite relation to : in Rust:

struct Zim<T: ~Escapable, U: ~Escapable>: ~Escapable {
    lifetime a dependsOn(t)
    lifetime b dependsOn(a, u)
    lifetime t: T
    lifetime u: T
}

That covers the core of what can be expressed in the generic signature of a type declaration. Inside the declaration, each field in a Rust struct can have a type parameterized by any of the lifetime parameters in the declaration:

struct First<'a> {...}
struct Second<'a> {...}
struct Third<'a> {...}

struct TwoOfThem<'a, 'b> {
    first: First<'a>,
    second: Second<'b>
}

struct ThreeOfTheSame<'a> {
    first: First<'a>,
    second: Second<'a>,
    third: Third<'a>
}

struct Nested<'a, T> {...}

struct Compound<'a, 'b, 'c> {
    foo: Nested<'a, First<'b>>,
    bar: Nested<'b, Second<'c>>
}

The analogous Swift declarations might specify the lifetime bindings as dependencies:

struct First: ~Escapable {
    lifetime a
}
struct Second: ~Escapable {
    lifetime a
}
struct Third: ~Escapable {
    lifetime a
}

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

struct ThreeOfTheSame: ~Escapable {
    lifetime a

    var first: dependsOn(.a: self.a) First
    var second: dependsOn(.a: self.a) First
    var third: dependsOn(.a: self.a) First
}

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

struct Compound: ~Escapable {
    lifetime a
    lifetime b
    lifetime c

    var foo: dependsOn(.a: self.a, .t.a: self.b) Nested<First>
    var foo: dependsOn(.a: self.b, .t.a: self.c) Nested<Second>
}

Conclusions

The initial lifetime dependency proposal provides enough functionality to support reference-like types whose referents are not themselves lifetime-constrained, but has severe limitations for expressing aggregates or collections of elements that themselves have lifetime constraints. The future direction of named lifetimes appears to provide Swift with a path to comparable expressivity to Rust lifetime variables, perhaps even exceeding Rust's expressivity in situations where lifetime dependencies need to evolve over a framework's lifetime or form relations that don't correspond to generic substitutions. However, Rust's model handles composition patterns implicitly with comparably less boilerplate than the current Swift design proposes, and its undeniable success suggests that even if carrying dependencies through generic substitution doesn't cover 100% of all possible use cases, it does cover enough of them to satisfy most Rust users. Even if we want to allow flexibility beyond what Rust allows, the ergonomics of Swift's lifetime feature could potentially benefit from default behavior that follows generic substitutions.

Also, although the dependsOn syntax offered by the proposal reads reasonably well for first-order dependencies, and it can be stretched to handle multiple named lifetimes, there are reasonable concerns about its readability as the length of the annotation expands. It may be worth exploring a declaration-level attribute as an initial syntax, and reconsider introducing shorthand for common cases as they arise after the feature is more widely adopted into the Swift ecosystem.

40 Likes
108

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

Similarly, is this missing a generic parameter?

I agree, but I think it's worth harping on. There's a limited amount of code context programmers can keep sorted in their brain while reading. The hypothetical syntax here spreads the lifetime dependency information out with a lot of intermediate characters that (I think) really works against clarity.

I think its also worth seeing a more complete example of the proposed syntax combined with ~Copyable and isolation keywords because thats what library authors will have to be able to read , write, and keep straight in their heads.

I'm not sure I agree here.

Swift programmers are extremely used to the "notional indirection" of substituting generic type parameters multiple times within function and type signatures. I dont think removing the indirection there would improve clarity, e.g. func pop(array : Array) -> elementOf(Array) is strictly worse than the current syntax. (this is obviously not even a real option for a number of reasons).

The indirection specifically helps programmers see where different parameters share common types.

6 Likes
109
(Retracted)

I don't think that's true.

In the proposed syntax, dependsOn(a) T in a method signature means that T's (maximum possible) lifetime is greater than or equal to a's lifetime. If it were the other way around, then you wouldn't be able to escape the T value outside the immediate scope, because the compiler would have no way of knowing that the T value is still within its own lifetime, even if it's still within a's lifetime.

So, analogously, lifetime t dependsOn(a) would mean that t's lifetime is greater than or equal to a's lifetime. In Rust, T: 'a means the same thing: that the lifetime of T is greater than or equal to 'a.

I think the value of dependsOn is really that it means "only depends on". By default, the Swift compiler would assume that a lifetime can depend on anything, like dependsOn(all). dependsOn(immortal) is kind of like dependsOn(nothing). So, perhaps unintuitively with the name, dependsOn expands a lifetime instead of restricting it, by narrowing down the possible dependencies. It can be thought to be equivalent to escaping(with:) or something similar.

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.

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.

Edit: Retracted some stuff. I forgot that lifetime parameters in functions would be caller-decided (universal) rather than callee-decided (existential).

  1. Analogous to how Rust always assumes that a type's lifetime is outlived by each of its lifetime parameters. Interestingly, this means that self.a.b always outlives self.a, which always outlives self, and so on. Changing a lifetime to a "nested" lifetime always results in an expanded lifetime. ↩︎

2 Likes
110

I think it would be beneficial to draw an analogy between "named lifetimes" and associated types, and contrast associated types with generic parameters. In Rust, lifetimes use generic parameter syntax. I think it would be better to use associated type syntax, like the pitch and @Joe_Groff suggest.

Associated type syntax is more expressive and extensible. For example, one can add a new associated type to an existing protocol without breaking compatibility, just like how @Joe_Groff suggests that one can add a new lifetime to an existing type.

There can only be a few generic parameters in a type before it becomes unwieldy. If we didn't have associated types, then, for example, the following declaration (inspired by @rauhul's example)

func pop<C: Collection>(_ collection: C) -> C.Element?

would exhibit "generic parameter explosion", because it'd have to list each associated type, and restate the constraints between those associated types.

Like this 
func pop<
    C,
    Element,
    Index,
    Iterator,
    ... /* the other associated types */
>(_ collection: C) -> Element?
where
    C: Collection<
        Element,
        Index,
        Iterator,
        ...
    >,
    Index: Comparable,
    Iterator: IteratorProtocol<Element>,
    ...

In Rust, it's uncommon for a type to have more than a few lifetime parameters, which I suspect is at least in part to avoid lifetime parameter explosion. A maximally expressive signature would have separate lifetime parameters for each lifetime in each field, like MyStruct<'a, 'b, 'c, ...>, and restate the constraints between those lifetimes. Such complex lifetime constraints can be expressed much more succinctly using associated type syntax.

We usually express complex associated type constraints using a where clause, to prevent signatures from becoming cluttered. I think it would be good to similarly express complex lifetime constraints using a declaration-level clause, like @Joe_Groff suggests. A user likely wouldn't always need to know upfront the complex lifetime constraints of a specific declaration. I feel that in the common case, "the return value depends on the parameters" will be enough information.

5 Likes
111

This proposal contains quite interesting ideas, but it leaves me a little concerned about the complexity that it brings to Swift in general. Further, I think that some of Swift features offer unique opportunities to simplify interactions with lifetime and those seem to be missing.

To give a little context, I am one of the designers of Hylo, a programming language that shamelessly steals from Swift but emphasizes even more on mutable value semantics. @dabrahams talked about it a little while ago (the language was called Val back then) and I'm not about to hijack this post to advertise my language but I'll just introduce some key relevant features.

All types are considered immovable and non-copyable by default in Hylo. So you can consider that any generic parameter has a ~Escapable bound by default. You can also consider that all function parameters have a borrowing modifier by default. We also have inout, which has similar semantics as Swift.

When you can express non-copyable types, you typically end up with a linear (or at least affine) type system, like Rust. When you can express immovable types, you typically need some additional mechanism to communicate the result of an abstraction. In Rust we use references. But since Hylo is all about value semantics, what do we do?

Hylo has subscripts, like Swift:

subscript min<T: Comparable>(_ x: T, _ y: T): T {
  if y > x { yield y } else { yield x }
}

This declaration should look like the _read accessor of a subscript in Swift. We must write min that way in Hylo because the instance of an unconstrained T can't be moved or copied (T would have both ~Copyable and ~Escapable bounds in Swift). So there is no way to "return" the minimum of two values. But we can "project" one!

Hylo also lets us bind the result of a subscript. That is in contrast to Swift where subscripts can only be used as sub-expressions. So we can write the following:

public fun foo() -> Int {
  let a = 4
  let b = 2
  let c = min[a, b]
  print(c)
  return c // error: `c`'s lifetime is bound to `a` and `b`
}

The program doesn't compile because it is trying to escape a value whose lifetime is bound to local variables. So as we can see, we used subscripts to define a simple lifetime dependency: the result of a subscript depends on the lifetime of the subscript's arguments.

This approach lets us implement first-order dependencies without the proposed dependsOn annotation. We only need to declare subscripts instead of functions. The latter return independent values and the former project lifetime-dependent ones.

The proposed dependsOn annotation offers a finer control over the arguments whose lifetimes are being tracked. But we can achieve a similar result in Hylo using different passing conventions. For example:

subscript min(_ x: T, _ y: T, by precedes: sink [](T, T) -> Bool): T {
  if precedes(y, x) { yield y } else { yield x }
}

Here, we said that precedes is an independent value because it is passed with the sink convention. That means the lifetime of the argument won't be part of the lifetime of the projected value. So you can think of this system having different defaults than the one proposed above: projected values are lifetime-dependent on all arguments unless explicitly stated otherwise.

Note that we can also project mutable values, which also fits very well into Swift's subscript design:

subscript min(_ x: yielded T, _ y: yielded T, by precedes: sink [](T, T) -> Bool): T {
  let { if precedes(y, x) { yield y } else { yield x } }
  inout { if precedes(y, x) { yield &y } else { yield &x } }
}

public fun main() {
  var a = 4
  var b = 2
  inout c = &min[&a, &b, by: (x, y) => x < y]
  print(c) // Prints "2"
  &c += 1
  print(b) // Prints "3"
}

Here, yielded means that the argument will be taken with the same capability as the one requested on the projection, which is inout in this example. So not only can we express a value dependent on the lifetime of an abstraction's arguments, we can also express a value dependent on the mutability of an abstraction's arguments.

Hylo suffers similar limitations as the one described in @Joe_Groff's post w.r.t. to aggregates of lifetime-dependent things. We can express a pair of two remote parts but we can't track individual lifetimes. FWIW, I personally believe the complexity of any system capable of doing that gets more expensive than the benefits it brings. I would be okay if people had to write safe APIs abstracting over unsafe features to address this issue. That is why I am concerned about Swift embracing such a complexity.

Nonetheless, I find the idea of idea of expressing lifetimes as dependent members interesting. I can buy that it would help library evolution but I remain skeptical about scalability.

I'd also like to note that an annotation of the form dependsOn(self.elements) involves a path-dependent type, which is a feature that has been thoroughly explored in Scala. In fact, named lifetimes as presented in the proposal are very reminiscent of Scala's capture checking, which is an ongoing project that aims at generalizing Rust lifetimes. It might be worth a look.

Note that the team developing capture checking is currently contemplating quantification over capture sets (i.e., quantification over the "arguments" that would go in dependsOn), which sadly comes back full circle to Rust's lifetime parameters. That is why I'm concerned about scalability.

15 Likes
112

I know this is basically an aside but I would caution that being able to syntactically express this is very far from the compiler being able to handle it, and it making sense.

Or, to put it another way -- in Rust you can make the fields of a struct borrow eachother, the problem is that this often leads to a semantic deadlock where the struct gets tangled up in its own lifetimes (with pinning being introduced as a system for doing this in a more usable way).

So for instance, what you want here is that ArraySubset is freely relocatable, with the understanding that subrange points to something that is stable under relocation of owner. But this is in direct conflict with the typical meaning of borrows, where you in fact want to prevent things from being relocated! And indeed if you were to move that Array out and let its destructor run, the subrange would be invalidated! And yet somehow moving the whole struct is fine!

These kinds of self-referential relocatable types based on stable allocations are a Very different beast from "borrows". Unfortunately I can't formalize that for you, it's just an intuitive understanding I have from working on exactly these kinds of types in Rust and Swift :sweat_smile:

(edit: I guess I could appeal to the fact that borrows ultimately bottom out in a bunch of constraints about regions of code, and this self-referential constraint just... fundamentally does not pertain to any region of code.)

11 Likes
113

Thanks for sharing current thinking on the path to declaring lifetime dependencies. It's a lot of work to compare across languages, but Rust as a leader in this case is an important point of reference.

You make my heart sing. What happened to where clauses?

(As an unschooled outsider I have a perhaps-naive question. If it's not helpful to the discussion, please ignore; in particular, I can only ask if I know people won't be taxed with merely educating others.)

Early in Swift's life I was very attracted to where clauses because it seemed they could form canonical statements about type constraints, and it lead to a design practice of establishing semantics in a where clause, and then possibly later building expressivity through sugar. The where clause could be swift-centric and forms a complete logical basis for reasoning about constraint soundness and implementation completeness, while the sugar can track usage and conventions from usage history and other languages.

Partly I ask because design discussions get tangled in expressivity and usage concerns; concepts can hardly form the basis for discussion while terms are changing and secondary considerations interfere.

Swift has constraints on (at least) types, function parameters/results, and functions, with respect to some aspect/feature/trait like ownership or lifetime or memory region, etc. In my mind I typically rewrite a feature with respect to one of these features in something like a where-clause.

E.g., one could express the @escapable parameter for func f(_ x: @escaping () -> Void) as something like where x.lifetime > f.lifetime

We're familiar with type T as a referent, but some constraints are on the concrete variable (e.g., given two parameters of the same type, only one might be @escapable). Similarly there may be constraints on the function or on a given function call (beyond any constraints on the function type), binding its lifetime to a parameter.

(Sometimes I think of concrete, runtime constraints as "when" clauses, reserving "where" for staticly-determinable compile-time constraints.)

So it would seem helpful to formalize or at least conventionalized this where language around constraints, establishing permitted and planned referents, features thereof, and relations. Then design discussions can be expressed clearly in those terms.

Part of the answer why that's not happening now may be that Swift's current where clauses are not usable in the more general case but can't be changed. Even so, it would seem normalizing a language could help design discussions.

Either way the language should be designed with the type-checker and runtime in mind. People should be able to reason from the constraints themselves to whether they're implementable, and perhaps even cost them out in type-checking or runtime and metadata overhead.

And if a constraint were expressible in where clauses in Swift, it seems like it would help to have a pattern of rolling out experimental features (and diagnostic fix-it's) restricted to where clauses (and perhaps to subject where clauses to availability constraints). This would establish utility before usability, and could permit some advanced, narrow features to be deployed without running the gauntlet of widespread understandability.

So given the language stages:

  • conceptual (discussion: desirable, feature topology...)
  • feasible (validated possible)
  • implemented (experimentally available for review)
  • released
  • (deprecated, unsupported)

It's clear that actual, supported where clauses are a subset of the conceptual, and that some of the conceptual type constraints may be never be implemented as where clauses. But I think expressibility in constraint clauses should be the goal and standard, and having at least conceptual where clauses can avoid usage or usability discussions before a feature has been established as sound, understandable, and implementable.

E.g., in this case, the comparison with Rust would translate rust locutions into Swift where clauses before comparing them with the current state. Rust experts could validate the translation, and the rest would still understand the gaps between Rust and Swift. Then we can avoid the current necessity of using dueling code examples for the semantic comparison.

4 Likes
114

Sadly these have been conflated for most of the design process of non-copyable types. Non-copyable types were originally envisioned to solve the Atomic problem, but it was eventually realized that stable allocations are a requirement above and beyond that of non-copyable types, so Atomic got its own bespoke, underscored, undocumented attribute: @_staticExclusiveOnly.

1 Like
115

The stable addressability comes from @_rawLayout, not @_staticExclusiveOnly. That attribute just disallows people from putting Atomic in a var.

7 Likes
116

Sorry. Either way, though, the existence of @_rawLayout is still a sign there’s unexplored territory here.

3 Likes
117

Scratching at this a little has raised a bunch of questions for me. (These appear to be very close to what @Gankra has said, just stated differently.)

Establishing a lifetime dependency between subrange and owner would, at first glance, make it impossible to ever mutate owner, as subrange will be tied to a constantly active borrow of it. (Such slice types are usually expected to be mutable (and also range-replaceable) collections.)

For ArraySubset to be copyable, it must be okay to tie a copy of the span to a copy of the collection. This is okay for strictly copy-on-write collection types like the standard Array, but it will not work for collections that have any inline storage -- copies of spans over such storage would continue to reference the original instance, making the lifetime dependency invalid.

Additionally, copy-on-write behavior is a library-level semantic promise that isn't at all statically enforced; thus, even the idea of tying a Span to the lifetime of an Array is fundamentally unsafe. Array stores its contents within an instance of a class type, and nonmutating/borrowing Array methods are technically free to mutate that -- the only thing preventing that is a pinky promise from the authors of the standard library. To make an ArraySubset-style construct truly safe, I think we would need to also invent first-class language support for copy-on-write containers.

We did play with this owner+pointers idea many times over the years, but in practice the stdlib overwhelmingly prefers to represent such slices using indices, not unsafe pointers.

struct Slice<Base: Collection> {
  var base: Base
  var subrange: Range<Base.Index>
}

(The standard ArraySlice type is a horrific counterexample; it is indeed (sort of) built around an owner and an unsafe pointer, but this is a regrettable historical blemish; it decidedly isn't a pattern we want anyone to emulate.)

Indices entirely solve the safety problem, and they also have full support for discontiguous storage. They generally do come with some potential(!) runtime overhead, but I have to wonder if getting rid of that is worth all this complexity -- if it is possible to very efficiently materialize a span over a range of known-valid indices in a contiguous collection, why would we insist on storing it?

7 Likes
118

The problem of implementing safe copy-on-write containers is interesting, but independent of this proposal. It is possible for a copy-on-write container with stable contiguous storage to safely provide a Span that depends on the container's value rather than some local access to the container. This proposal presumes that's a desirable programming model, regardless of how easy it is to safely implement copy-on-write. I actually think it's important to support this to allow function-level composition without requiring coroutines at every level between the Span's accessor and the code that uses the Span.

In Joe's example, the Array owner is mutable, which does make enforcement difficult:

struct ArraySubset<T> {
    var owner: Array<T>
    var subrange: dependsOn(owner) Span<T>
}

Mutating the owner array would invalidate the subrange. The compiler would need to locally prove that the scope that mutates owner also reassigns subrange to something that depends on the new owner value. It's easier to reason about the immutable case, which is probably more commonly useful anyway:

struct ArraySubset<T> {
    let owner: Array<T>
    var subrange: dependsOn(owner) Span<T>
}

This works because array elements have a stable address indepenent of the array value itself. And the immutable owner value keeps the array elements pinned regardless of where the owner value moves. The compiler's local analysis just needs to be sure that subrange does not outlive the lifetime of owner. owner could be moved to a local variable, or to a different struct, as long as subrange moves with it in the same scope, as determined by a local analysis.

You're absolutely right that any container that does not have a stable address for its elements will require a local scope that guarantees a stable address. All its spans will depend on that scope, not on the original value.

2 Likes
119

I expect to be able to write this in Swift without any dependence qualifier using inferred dependence on values of the same type:
See swift-evolution/proposals/NNNN-lifetime-dependency.md at 4152b2e405ef0c83aaa76dfb6dddf01abfbc8fa7 · swiftlang/swift-evolution · GitHub

// Result dependsOn(x, y) is inferred.
func min<T: ~Escapable>(_ x: T, _ y: T, by precedes: (T, T) -> Bool) -> T {
  if precedes(y, x) { return y } else { return x }
}

This will all be meaningless for integers, but for the sake of discussion, I'll continue with the example...
Borrow<T> is not part of this proposal, but once we have that, borrowed values of any (copyable or escapable) type could be passed to min to guarantee no copying:

let result = min(Borrow(x), Borrow(y)) // Result is Borrow<type(of: x)>

We also expect support a borrow qualifier on generic types. Then you don't even need the ~Escapable qualifier to avoid copying within the implementation:

func min<T>(_ x: T, _ y: T, by precedes: (T, T) -> Bool) -> borrow T {
  if precedes(y, x) { return y } else { return x } // does not need to copy 'x' or 'y'
}

Whether we actually want to infer the above dependence is not as clear.

We also expect to generalize _read/_modify coroutines:

func min(_ x: T, _ y: T, by precedes: sink (T, T) -> Bool) -> yield T {
  if precedes(y, x) { yield y } else { yield x }
}

In this case the yield has the same semantics as the borrow T case above, but coroutines would allow arbitrary cleanup upon coroutine exit.

5 Likes
120

I'd like to present a @lifetime annotation as a temporary syntax alternative that we can use to separate the discussion about the long-term viability of the syntax from discussions about semantics. The proposal now describes this in an alternatives consider section:
swift-evolution/proposals/NNNN-lifetime-dependency.md at 4152b2e405ef0c83aaa76dfb6dddf01abfbc8fa7 · swiftlang/swift-evolution · GitHub

Lifetime dependencies started as an annotation. We came up with the dependsOn type modifier syntax, as opposed to other (less invasive?) alternatives, for the purpose of the proposal. We did this for a couple of reasons:

  1. It reads well in the common case without excess baggage. Even in cases where the dependence would be inferred, library authors may want to be explicit, and diagnostics or documentation systems may produce the expanded syntax:

    func foo(arg: Arg) -> dependsOn(arg) Result

  2. It (sort of) generalizes to function signatures

    func bar(f: (_ arg: Arg) -> dependsOn(arg) Result)
    or
    func bar(f: (Arg) -> dependsOn(0) Result)

We are still bikesheding the spelling of the dependsOn type modifier. (I'm biased toward lifetime). But people are rightly concerned that any type modifier will overwhelm the original function signature once we start expressing dependencies on nested lifetimes. Consider these examples from Joe's post above:

struct Array<T: ~Escapable> {
   lifetime elements: T
   
   borrowing func span()
        -> dependsOn(.memory: scoped self, .elements: self.elements) Span<T>
}
struct Span<T: ~Escapable> {
   lifetime memory: Self
   lifetime elements: T
    
   subscript(index: Int) -> dependsOn(self.elements) T
}

The dependencies above can all be inferred because the lifetime declarations would bind a lifetime to a type within this declaration context. Nonetheless, we want to be sure that the syntax we adopt can handle cases like this. We may want more experience with nested lifetimes before commiting to that syntax.

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.

struct Array<T: ~Escapable> {
   lifetime elements: T

   @lifetime(.memory: borrow self)
   @lifetime(.elements: copy self.elements)
   borrowing func span() -> Span<T>
}
struct Span<T: ~Escapable> {
   lifetime memory: Self
   lifetime elements: T
    
   @lifetime(copy self.elements)
   subscript(index: Int) -> T
}

If people generally agree with this strategy, then we can move the syntax aspects of this proposal into a future direction. Meanwhile we can continue evaluating the more sophisticated syntax under an experimental flag.

One caveat... as Joe said, any syntax that handles nested lifetimes, including the @lifetime annotation, reverses the direction used in Rust. That's a natural consequence of using function-like syntax for the annotation. In other words this:

@lifetime(target.component: [copy|borrow|mutate] source.component)

is more natural than:

@lifetime([copy|borrow|mutate] source.component: target.component)

because argument labels are the "argument sink" and arguments to the right of the label are the "argumnt source".

Rust lifetimes are related in the opposite direction because it wants to fix the dependence into a subtype relation: subtype: supertype. Since Swift has no indication that lifetimes are part of the type, I don't think the inconsistency will be a problem.

I also felt it was worth mentioning the where clause syntax as a proposed alternative:

swift-evolution/proposals/NNNN-lifetime-dependency.md at 4152b2e405ef0c83aaa76dfb6dddf01abfbc8fa7 · swiftlang/swift-evolution · GitHub

I like this syntax because it doesn't clutter the function signature with nested parenthesis. But, as with the annotation, it won't generalize to function signatures.

8 Likes
121

While we're talking about Span, here is a pitch/plea/entreaty:

Since the purpose of Span is to provide a safer replacement for the various withUnsafeBytes, withUnsafeBufferPointer, and other such methods, we're presumably also going to want to add new, similar methods to most of the standard library types to replace these. Given this, can we please put the protocol that describes this functionality in the standard library rather than in Foundation?

Currently, if you're making a library that needs to do work with low-level byte buffers, like say, a compression library or a parser for some binary type, you've got a few options, none of which are great:

  1. Require Foundation, so you can have your function take some DataProtocol or some ContiguousBytes. Unfortunately, this means anyone who uses your library also needs to require Foundation, which many clients of a low-level library won't want.
  2. Don't require Foundation, and have your function take something like some Sequence<UInt8>. Unfortunately, now you have to use less-performant Sequence methods instead of being able to load a large chunk of memory at once, so your library is now less efficient.
  3. Don't require Foundation, but declare your own protocol that provides withUnsafeBufferPointer, and extend the standard library types like Array<UInt8>, ContiguousArray<UInt8>, etc. to conform to it. Now you can be efficient, and you don't require Foundation. Great, but now a client that does use Foundation can't pass a Data to your function.
  4. Make all your functions take UnsafePointers directly, and force the client to deal with getting the pointer on their own. This works but makes for a much less clean API.
  5. Make two versions of your library, one which requires Foundation and one which does not.

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.

4 Likes
122

The beginnings of this are in the "safe access to contiguous memory" (aka Span) proposal. Rounding out the story (in particular, the patterns and protocols you're describing here) will be part of new protocols that support collection-style algorithms over non-copyable data. All of this will go in the standard library.

Contiguous collections will be able to use something like withSpan { }, but we need to support partially-discontiguous collections without copying as well, so I expect that we'll end up with something that actually vends a sequence of spans (with some conveniences for sequence-like objects of copyable elements that lets you use them like a buffered stream without needing to do much/any work). @lorentey has been working on prototypes of these ideas, which I expect will get pitched on Evolution as this pitch and Span (which are necessary building blocks) and the lifetime annotations proposal (which is a major quality-of-life enhancement for those API) begin to settle down.

5 Likes