Skip to content

Latest commit

 

History

History
700 lines (575 loc) · 25.7 KB

0427-noncopyable-generics.md

File metadata and controls

700 lines (575 loc) · 25.7 KB
Raw

Noncopyable Generics

Table of Contents

Introduction

The noncopyable types introduced in SE-0390: Noncopyable structs and enums cannot be used with generics, protocols, or existentials, leaving an expressivity gap in the language. This proposal extends Swift's type system to fill this gap.

Motivation

Noncopyable structs and enums are intended to express value types for which it is not meaningful to have multiple copies of the same value.

Support for noncopyable generic types was omitted from SE-0390. For example, Optional could not be instantiated with a noncopyable type, which prevented declaration of a failable initializer:

struct FileDescriptor: ~Copyable {
  init?(filename: String) { // error: cannot form a Optional<FileDescriptor>
    ...
  }
}

Practical use of generics also requires conformance to protocols, however noncopyable types could not conform to protocols.

In order to broaden the utility of noncopyable types in the language, we need a consistent and sound way to relax the fundamental assumption of copyability that permeates Swift's generics system.

Proposed Solution

We begin by recalling the restrictions from SE-0390:

  1. A noncopyable type could not appear in the generic argument of some other generic type.
  2. A noncopyable type could not conform to protocols.
  3. A noncopyable type could not be boxed as an existential.

This proposal builds on the ~Copyable notation introduced in SE-0390, and introduces three fundamental concepts that together eliminate these restrictions:

  1. A new Copyable protocol abstracts over types whose values can be copied.
  2. Every struct, enum, class, generic parameter, protocol and associated type now conforms to Copyable by default.
  3. The ~Copyable notation is used to suppress this default conformance requirement anywhere it would otherwise be inferred.

Note: The adoption of noncopyable generics in the standard library will be covered in a subsequent proposal.

The Copyable protocol

The notion of copyability of a value is now expressed as a special kind of protocol. The existing ~Copyable notation is re-interpreted as suppressing a conformance to this protocol, as we detail below. This protocol has no explicit requirements, and it has some special behaviors. For example, metatypes and tuples cannot normally conform to other protocols, but they do conform to Copyable.

A key goal of the design is progressive disclosure. The idea of default conformance to Copyable means that a user never interacts with noncopyable generics unless they choose to do so, using the ~Copyable notation to suppress the default conformance.

The meaning of existing code remains the same; all generic parameters and protocols now require conformance to Copyable, but all existing concrete types do in fact conform.

Default conformance to Copyable

Every struct and enum now has a default conformance to Copyable, unless the conformance is suppressed by writing ~Copyable in the inheritance clause. In this proposal, we will show these inferred requirements in comments. For example, a definition of a copyable struct is understood as if the user wrote the conformance to Copyable:

struct Polygon /* : Copyable */ {...}

Furthermore, generic parameters now conform to Copyable by default, so the following generic function can only be called with Copyable types:

func identity<T>(x: T) /* where T: Copyable */ { return x }

Finally, protocols also have a default conformance to Copyable, thus only Copyable types can conform to Shape below:

protocol Shape /*: Copyable */ {}

Suppression of Copyable

So far, we haven't described anything new, just formalized existing behavior with a protocol. Now, we allow writing ~Copyable in some new positions.

For example, to generalize our identity function to also allow noncopyable types, we suppress the default Copyable conformance on T as follows:

func identity<T: ~Copyable>(x: consuming T) { return x }

This function imposes no requirements on the generic parameter T. All possible types, both Copyable and noncopyable, can be substituted for T. This is the reason why we refer to ~Copyable as suppressing the conformance rather than inverting or negating it.

As with a concrete noncopyable type, a noncopyable generic parameter type must be prefixed with one of the ownership modifiers borrowing, consuming, or inout, when it appears as the type of a function's parameter. For details on these parameter ownership modifiers, see SE-377.

A protocol can allow noncopyable conforming types by suppressing its inherited conformance to Copyable:

protocol Resource: ~Copyable {
  consuming func dispose()
}

extension FileDescriptor: Resource {...}

A Copyable type can still conform to a ~Copyable protocol.

What it means to write ~Copyable in each position will be fully explained in the Detailed Design section.

Detailed Design

This proposal does not fundamentally change the abstract theory of Swift generics, with its four fundamental kinds of requirements that can appear in a where clause; namely conformance, superclass, AnyObject, and same-type requirements.

The proposed mechanism of default conformance to Copyable, and its suppression by writing ~Copyable, is essentially a new form of syntax sugar; the transformation is purely syntactic and local.

The Copyable protocol

While Copyable is a protocol in the current implementation, it is unlike a protocol in some ways. In particular, protocol extensions of Copyable are not allowed:

extension Copyable {  // error
  func f() {}
}

Such a protocol extension would effectively add new members to every copyable type, which would complicate overload resolution and possibly lead to user confusion.

Default conformances and suppression

Default conformance to Copyable is inferred in each position below, unless explicitly suppressed:

  1. A struct, enum or class declaration.
  2. A generic parameter declaration.
  3. A protocol declaration.
  4. An associated type declaration; does not support suppression (see Future Directions).
  5. The Self type of a protocol extension.
  6. The generic parameters of a concrete extension.

The ~Copyable notation is also permitted to appear as the member of a protocol composition type. This ensures that the following three declarations have the same meaning, as one might expect:

func f<T: Resource & ~Copyable>(_: T) {}
func f<T>(_: T) where T: Resource & ~Copyable {}
func f<T>(_: T) where T: Resource, T: ~Copyable {}

A conformance to Copyable cannot be suppressed if it must hold for some other reason. In the above declaration of f(), we can suppress Copyable on T because Resource suppresses its own Copyable requirement on Self:

protocol Resource: ~Copyable {...}

Thus, nothing else forces f()'s generic parameter T to be Copyable. On the other hand, let's look at a copyable protocol like Shape below:

protocol Shape /*: Copyable */ {...}

If we try to suppress the Copyable conformance on a generic parameter that also conforms to Shape, we get an error:

func f<T: Shape & ~Copyable>(_: T) {...}  // error

The reason being that the conformance T: Copyable is implied by T: Shape, and cannot be suppressed.

Furthermore, a Copyable conformance can only be suppressed if the subject type is a generic parameter declared in the innermost scope. That is, the following is an error:

struct S<T /* : Copyable */> {
  func f<U /* : Copyable */>(_: T, _: U) where T: ~Copyable  // error!
}

The rationale here is that since S must be instantiated with a copyable type, it does not make sense for a method of S to operate on an S<T> where T might be noncopyable. For a similar reason the same rule applies to nested generic types.

Struct, enum and class extensions

We wish to allow existing types to adopt noncopyability without changing the meaning of existing code. Thus, an extension of a concrete type must introduce a default T: Copyable requirement on every generic parameter of the extended type:

struct Pair<T: ~Copyable>: ~Copyable {...}

extension Pair /* where T: Copyable */ {...}

The conformance can be suppressed to get an unconstrained extension of Pair:

extension Pair where T: ~Copyable {...}

An extension presents a copyable view of the world by default, behaving as if Pair were declared like so:

struct Pair<T /* : Copyable */> /* : Copyable */ {...}

An extension of a nested type introduces default conformance requirements for all outer generic parameters of the extended type, and each conformance can be individually suppressed:

struct Outer<T: ~Copyable> {
  struct Inner<U: ~Copyable> {}
}

extension Outer.Inner /* where T: Copyable, U: Copyable */ {}
extension Outer.Inner where T: ~Copyable /* , U: Copyable */ {}
extension Outer.Inner where /* T: Copyable, */ U: ~Copyable {}

An extension of a type whose generic parameters must be copyable cannot suppress conformances:

struct Horse<Hay> {...}
extension Horse where Hay: ~Copyable {...}  // error

Protocol extensions

Where possible, we wish to allow the user to change an existing protocol to accommodate noncopyable conforming types, without changing the meaning of existing code.

For this reason, an extension of a ~Copyable protocol also introduces a default Self: Copyable requirement, because this is the behavior expected from existing clients:

protocol EventLog: ~Copyable {
  ...
}

extension EventLog /* where Self: Copyable */ {
  func duplicate() -> Self {
    return copy self // OK
  }
}

To write an unconstrained protocol extension, suppress the conformance on Self:

extension EventLog where Self: ~Copyable {
  ...
}

Associated types cannot have their Copyable requirement suppressed (see Future Directions).

Protocol inheritance

Another consequence that immediately follows from the rules as explained so far is that protocol inheritance must re-state ~Copyable if needed:

protocol Token: ~Copyable {}
protocol ArcadeToken: Token /* , Copyable */ {}
protocol CasinoToken: Token, ~Copyable {}

Again, because ~Copyable suppresses a default conformance instead of introducing a new kind of requirement, it is not propagated through protocol inheritance.

Conformance to Copyable

Structs and enums conform to Copyable unconditionally by default, but a conditional conformance can also be defined. For example, take this noncopyable generic type:

enum List<T: ~Copyable>: ~Copyable {
  case empty
  indirect case element(T, List<T>)
}

We would like List<Int> to be Copyable since Int is, while still being able to use a noncopyable element type, like List<FileDescriptor>. We do this by declaring a conditional conformance:

extension List: Copyable where T: Copyable {}

Note that the where clause needs to be written, because a conformance to Copyable declared in an extension does not automatically add any other requirements, unlike other extensions.

A conditional Copyable conformance is not permitted if the struct or enum declares a deinit. Deterministic destruction requires the type to be unconditionally noncopyable.

A conformance to Copyable is checked by verifying that every stored property (of a struct) or associated value (of an enum) itself conforms to Copyable. For a conditional Copyable conformance, the conditional requirements must be sufficient to ensure this is the case. For example, the following is rejected, because the struct cannot unconditionally conform to Copyable, having a stored property of the noncopyable type T:

struct Holder<T: ~Copyable> /* : Copyable */ {
  var value: T  // error
}

There are two situations when it is permissible for a copyable type to have a noncopyable generic parameter. The first is when the generic parameter is not stored inside the type itself:

struct Factory<T: ~Copyable> /* : Copyable */ {
  let fn: () -> T  // ok
}

The above is permitted, because a function of type () -> T is still copyable, even if a value of type T is not copyable.

The second case is when the type is a class. The contents of a class is never copied, so noncopyable types can appear in the stored properties of a class:

class Box<T: ~Copyable> {
  let value: T  // ok

  init(value: consuming T) { self.value = value }
}

For a conditional Copyable conformance, the conditional requirements must be of the form T: Copyable where T is a generic parameter of the type. It is not permitted to make Copyable conditional on any other kind of requirement:

extension Pair: Copyable where T == Array<Int> {}  // error

Conditional Copyable conformance must be declared in the same source file as the struct or enum itself. Unlike conformance to other protocols, copyability is a deep, inherent property of the type itself.

Classes

This proposal supports classes with noncopyable generic parameters, but it does not permit classes to themselves be ~Copyable. Similarly, an AnyObject or superclass requirement cannot be combined with ~Copyable:

func f<T>(_ t: T) where T: AnyObject, T: ~Copyable { ... }  // error

Existential types

The type Any is no longer the supertype of all types in the type system's implicit conversion rules.

The constraint type of an existential type is now understood as being a protocol composition, with a default Copyable member. So the empty protocol composition type Any is really any Copyable, and the supertype of all types is now any ~Copyable:

              any ~Copyable
               /         \
              /           \
   Any == any Copyable   <all purely noncopyable types>
        |
<all copyable types>

This default conformance is suppressed by writing ~Copyable as a member of a protocol composition:

protocol Pizza: ~Copyable {}
struct UniquePizza: Pizza, ~Copyable {}

let t: any Pizza /* & Copyable */ = UniquePizza()  // error
let _: any Pizza & ~Copyable = UniquePizza()  // ok

Source Compatibility

The default conformance to Copyable is inferred anywhere it is not explicitly suppressed with ~Copyable, so this proposal does not change the interpretation of existing code.

Similarly, the re-interpretation of the SE-0390 restrictions in terms of conformance to Copyable preserves the meaning of existing code that makes use of noncopyable structs and enums.

ABI Compatibility

This proposal does not change the ABI of existing code.

Adding ~Copyable to an existing generic parameter is generally an ABI-breaking change, even when source-compatible.

Targeted mechanisms are being developed to preserve ABI compatibility when adopting ~Copyable on previously-shipped generic code. This will enable adoption of this feature by standard library types such as Optional. Such mechanisms will require extreme care to use correctly.

Alternatives Considered

Alternative spellings

The spelling of ~Copyable generalizes the existing syntax introduced in SE-0390, and changing it is out of scope for this proposal.

Associated types without defaulting behavior

A simple design for suppressed associated types was considered, where the default conformance in a protocol extension applies only to Self, and not the associated types of Self. For example, we first declare a protocol with a ~Copyable associated type:

protocol Manager {
  associatedtype Resource: ~Copyable
}

Now, a protocol extension of Manager does not carry an implicit Self.Resource: Copyable requirement:

extension Manager {
  func f(resource: Resource) {
    // `resource' cannot be copied here!
  }
}

For this reason, while adding ~Copyable to the inheritance clause of a protocol is a source-compatible change, the same with an associated type is not source compatible. The designer of a new protocol must decide which associated types are ~Copyable up-front.

Requirements on associated types can be written in the associated type's inheritance clause, or in a where clause, or on the protocol itself. As with ordinary requirements, all three of the following forms define the same protocol:

protocol P { associatedtype A: ~Copyable }
protocol P { associatedtype A where A: ~Copyable }
protocol P where A: ~Copyable { associatedtype A }

If a base protocol declares an associated type with a suppressed conformance to Copyable, and a derived protocol re-states the associated type, a default conformance is introduced in the derived protocol, unless it is again suppressed:

protocol Base {
  associatedtype A: ~Copyable
  func f() -> A
}

protocol Derived: Base {
  associatedtype A /* : Copyable */
  func g() -> A
}

Finally, conformance to Copyable cannot be conditional on the copyability of an associated type:

struct ManagerManager<T: Manager>: ~Copyable {}
extension ManagerManager: Copyable where T.Resource: Copyable {}  // error

This design for associated types was initially implemented but ultimately removed from this proposal, because of the source compatibility issues. A more comprehensive design that allows for some way of preserving source compatibility requires a separate proposal due to the open design issues.

Inferred conditional copyability

A struct or enum can opt out of copyability with ~Copyable, and then possibly declare a conditional conformance. It would be possible to automatically infer this conditional conformance. For example, in the below,

struct MaybeCopyable<T: ~Copyable> {
  var t: T
}

The only way this could be valid is if we had inferred the conditional conformance:

extension MaybeCopyable: Copyable /* where T: Copyable */ {}

Feedback from early attempts at implementing this form of inference suggested it was more confusing than helpful, so it was removed.

Extension defaults

One possible downside is that extensions of types with noncopyable generic parameters must suppress the conformance on each generic parameter.

It would be possible to allow library authors to explicitly control this behavior, with a new syntax allowing the default where clause of an extension to be written inside of a type declaration. For example,

public enum Either<T: ~Copyable, U: ~Copyable> {
  case a(T)
  case b(U)

  // Hypothetical syntax:
  default extension where T: Copyable, U: ~Copyable
}

// `T` is copyable, but `U` is not, because of the defaults above:
extension Either /* where T: Copyable */ { ... }

This becomes much more complex for protocols that impose conformance requirements on their own associated types:

protocol P: ~Copyable {
  associatedtype A: P, ~Copyable

  // Hypothetical syntax:
  default extension where A: Copyable
}

extension P {
  // A is Copyable. What about A.A? A.A.A? ...
}

Besides the unclear semantics with associated types, it was also felt this approach could lead to user confusion about the meaning of a particular extension. As a result, we feel that explicitly suppressing Copyable on every extension is the best approach.

Recursive Copyable

The behavior of default Copyable conformance on associated types prevents existing protocols from adopting ~Copyable on their associated types in a source compatible way.

For example, suppose we attempt to change IteratorProtocol to accommodate noncopyable element types:

protocol IteratorProtocol: ~Copyable {
  associatedtype Element: ~Copyable
  mutating func next() -> Element?
}

An existing program might declare a generic function that assumes T.Element is Copyable:

func f<T: IteratorProtocol /* & Copyable */>(iter: inout T) {
  let value = iter.next()!
  let copy = value  // error
}

Since IteratorProtocol suppresses its Copyable conformance, the generic parameter T defaults to Copyable. However, T.Element is no longer Copyable, thus the above code would not compile.

One can imagine a design where instead of a single default conformance requirement T: Copyable being introduced above, we also add a requirement T.Element: Copyable. This would preserve source compatibility and our function f() would continue to work as before.

However, this approach introduces major complications, if we again consider protocols that impose conformance requirements on their associated types.

Consider this simple protocol and function that uses it:

protocol P: ~Copyable {
  associatedtype A: P, ~Copyable
}

func f<T: P>(_: T) {}

Our hypothetical design would actually introduce an infinite sequence of requirements here unless suppressed:

func f<T: P>(_: T) /* where T: Copyable, T.A: Copyable, T.A.A: Copyable, ... */ {}

Of course, it seems natural to represent this infinite sequence of requirements as a new kind of "recursive conformance" requirement instead.

Swift generics are based on the mathematical theory of string rewriting, and requirements and associated types define certain rewrite rules which operate on a set of terms. In this formalism, a hypothetical "recursive conformance" requirement corresponds to a rewrite rule that can match an infinite set of terms given by a regular expression. We would then need to generalize the algorithms for deciding term equivalence to handle regular expressions. While there has been research in this area, the design for such a system is far beyond the scope of this proposal.

~Copyable as logical negation

Instead of the syntactic desugaring presented in this proposal, one can attempt to formalize T: ~Copyable as the logical negation of a conformance, extending the theory of Swift generics with a fifth requirement kind to represent this negation. It is not apparent how this leads to a sound and usable model and we have not explored this further.

Future Directions

Suppressed associated types

Supporting the full generality of associated types with suppressed Copyable requirements, while providing a mechanism to preserve source compatibility is a highly desirable goal. At the same time, it is a large, open design problem. A few ideas were considered (see Alternatives Considered) but it was ultimately determined to be too complex to tackle in this proposal.

Standard library adoption

The Optional and UnsafePointer family of types can support noncopyable types in a straightforward way. In the future, we will also explore noncopyable collections, and so on. All of this requires significant design work and is out of scope for this proposal.

Tuples and parameter packs

Noncopyable tuples and parameter packs are a straightforward generalization which will be discussed in a separate proposal.

~Escapable

The ability to "escape" the current context is another implicit capability of all current Swift types. Suppressing this requirement provides an alternative way to control object lifetimes. A companion proposal will provide details.

Acknowledgments

Thank you to Joe Groff and Ben Cohen for their feedback throughout the development of this proposal.