[SE-0143] Dynamic casting for conditional conformances

Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

  - Doug

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

John.

···

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org> wrote:
Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

It's worth noting here that the standard library already provides a limited `_typeByName(_:)` function for Corelibs Foundation to use. That function will presumably become part of the ABI unless we design a public version in Swift 5.

···

On Dec 5, 2017, at 2:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org> wrote:

To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

--
Brent Royal-Gordon
Architechies

Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

I would also like to use this mechanism to replace the field type vector accessor function with something that operates on mangled field type strings instead, saving code size, so as long as that can be accommodated.

Slava

···

On Dec 5, 2017, at 3:42 PM, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

John.
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

We could do that for associated types, which would work for the left-hand sides of all of the requirements (because the left-hand side is always a type parameter) and would certainly be more efficient. However, it doesn’t handle the right-hand side of same-type requirements or superclass requirements, which can be of arbitrary type.

So, for the general case, we need the full encoding of types, and mangling already provides that. We could introduce a more optimal form of encoding for the direct cases—a metadata path for associated types would be one such optimization, as would the ability to have direct references to metadata (e.g., the protocol descriptor) rather than encoding the names of the types.

  - Doug

···

On Dec 5, 2017, at 3:42 PM, John McCall <rjmccall@apple.com> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

But that wouldn’t allow surfacing a func type(named: String) Standard Library function that worked on any type, wouldn’t it (like the Dictionary with non-Hashable key)?

···

On 6 Dec 2017, at 00:42, John McCall via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org> wrote:
Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

John.
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

I would also like to use this mechanism to replace the field type vector accessor function with something that operates on mangled field type strings instead, saving code size, so as long as that can be accommodated.

Yes, I can see how there's some nice synergy there, and it would certainly be good to avoid having to eagerly generate code for this operation. And it should be possible to optimize the cast operation in the runtime if we find ourselves executing it many times for different types.

Okay, the basic idea seems reasonable to me. I guess my biggest concern is the use of just mangled names, since it seems like that will pose a lot of problems with private or local types. When Ashley was working on the remote-mirrors metadata, we had the idea of using descriptor "strings" that could embed a reference to a nominal type descriptor (or something like that) instead of just relying on a name. (A name would still be reasonable for a type that's not known to be defined within the linkage unit, of course.)

More specific comments:

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

Well, you actually need something more sophisticated: you need (1) an operation that looks up types in the context of a known generic environment and (2) an operation that tries to match a generic environment from a type.

In AST terms:
  func matchEnvironment(GenericSignature, Type, TypeMetadata) -> GenericEnvironment?
  func substitute(GenericEnvironment, Type) -> TypeMetadata?

Note specifically that the matching type could be something like [(T, T)], i.e. could have implicit equality requirements. The match operation should just be a matter of simultaneously recursing into the type expression and metadata and verifying structural identity (for concrete components of the type expression) or equality of inference (for abstract components).

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types.

Yeah, this is going to get quite complicated.

John.

···

On Dec 5, 2017, at 7:01 PM, Slava Pestov <spestov@apple.com> wrote:

On Dec 5, 2017, at 3:42 PM, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

Woah. That’s kinda awful… it parses “Foo.Bar” as a class name and looks for class Bar in module Foo.

  - Doug

···

On Dec 10, 2017, at 4:47 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

On Dec 5, 2017, at 2:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

It's worth noting here that the standard library already provides a limited `_typeByName(_:)` function for Corelibs Foundation to use. That function will presumably become part of the ABI unless we design a public version in Swift 5.

But that wouldn’t allow surfacing a func type(named: String) Standard Library function that worked on any type, wouldn’t it (like the Dictionary with non-Hashable key)?

As I noted to John, we still need to handle the general case for the right-hand side of a same-type constraint, which can be an arbitrary type. That requires all of the functionality of type(named:).

That said, from my perspective, adding type(named:) is entirely “gravy”. We get it for free from this implementation plan, but IMO it could be added to some later version of Swift and that would be fine.

  - Doug

···

On Dec 5, 2017, at 3:56 PM, David Hart <david@hartbit.com> wrote:

On 6 Dec 2017, at 00:42, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

John.
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

But that wouldn’t allow surfacing a func type(named: String) Standard Library function that worked on any type, wouldn’t it (like the Dictionary with non-Hashable key)?

As I noted to John, we still need to handle the general case for the right-hand side of a same-type constraint, which can be an arbitrary type. That requires all of the functionality of type(named:).

That said, from my perspective, adding type(named:) is entirely “gravy”. We get it for free from this implementation plan, but IMO it could be added to some later version of Swift and that would be fine.

I agree that surfacing it in the stdlib is gravy, but implementing the underlying mechanism is important, IMO. Field type vector accessors are a large contributor to binary code size (I wouldn’t be surprised if it was 5-10% for some projects) and implementing a more efficient encoding for ABI stability would be nice.

Slava

···

On Dec 5, 2017, at 4:05 PM, Douglas Gregor via swift-dev <swift-dev@swift.org> wrote:

On Dec 5, 2017, at 3:56 PM, David Hart <david@hartbit.com <mailto:david@hartbit.com>> wrote:

  - Doug

On 6 Dec 2017, at 00:42, John McCall via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:
Hi all,

The main missing piece for conditional conformances (https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:

protocol P {
  func foo()
}

struct X : P {
  func foo() { print("X.P") }
}

struct Y<T> {
  var wrapped: T
}

extension Y: P where T: P {
  func foo() { wrapped.foo() }
}

func tryAsP(_ value: Any) {
  if let p = value as? P {
    p.foo()
  }
}

let yx = Y(wrapped: X())
tryAsP(yx)

This won’t print anything, but should print “X.P”. We’d like to fix that :slight_smile:

Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.

Background
The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a witness table. Witness tables contain the actual associated types as well as function pointers for each of the requirements of a protocol. Slava and John’s talk on Implementing Swift Generics (https://llvm.org/devmtg/2017-10/#talk15) gives a bunch of background here.

When a conformance is conditional, the witness table also stores the conditional requirements. So, the witness table for Array<Int>: Equatable has to store the witness table Int: Equatable. In the example above, the witness table for Y<X>: P needs to store a pointer to the witness table X: P. The compiler knows how to pass along the witness tables needed for a conditional conformance, but for runtime casting to work, we need to (1) evaluate all of the conditional requirements to determine whether they apply (e.g., does T: P for a specific T?) and then (2) pass those witness tables along when building the witness table. The cast should fail if any of the conditional requirements goes unsatisfied, and produce a valid witness table otherwise.

Protocol Conformance Records
Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records). These protocol conformance records state the type declaring conformance (e.g., Y) and the protocol (e.g., P), and then provide a witness table accessor to form the witness table given type metadata for a specific type instance (e.g., Y<X>). In the case of a conditional conformance, this accessor also needs to be passed the witness tables for any conditional requirements, e.g., the witness table for X: P.

Conditional Requirements in Protocol Conformance Records
Somehow we need to dynamically evaluate the conditional requirements. For example, we need to know that for the X<T>: P conformance to be valid, we need T: P to hold for the given T. So, we’ll extend the protocol conformance record with an encoding of those requirements. Fortunately, we already have a way to encode arbitrary generic requirements: the mangling of a generic-signature (see https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.

When evaluating a conditional conformance, we demangle the conditional requirements to get something like: “T must conform to P”. We then need to substitute the type arguments (e.g., X) for the corresponding type parameters (T) to form type metadata for the requirements. In this case, we’d get the type metadata pointer for Y and the protocol descriptor for P, and then call swift_conformsToProtocol() to determine whether the requirement holds. If it does, swift_conformsToProtocol() produces the Y: P witness table we need to pass along to the witness table accessor.

Note that the conditional requirements can be arbitrarily complicated. For example, given:

extension Dictionary: P where Value == (Key) -> Bool { … }

Even though the result of evaluating this same-type requirement doesn’t need to be passed along to the witness table accessor, we still need to evaluate the requirement to determine whether the conditional conformance to P applies. To do so, we will need to substitute type arguments for both Value and Key, and need to form the type metadata representing the (substituted) function type (Key) -> Bool to determine if it is equivalent to the (substituted) type of Value (which is then determined by type metadata pointer equality because the runtime uniques type metadata).

Looking up Type Metadata For a Mangled Name
To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

To get here, we’ll also need to extend the nominal type descriptor (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor) to contain the generic signature of a nominal type. That let’s us safely create specializations of generic types. For example, if one tries to form Dictionary<A, B> where A does not conform to Hashable, type(named:) should return “nil” rather than an invalid type. The same logic that will be used to form type metadata when checking conditional requirements will apply here. Indeed, it’s probably worth proposing type(named:) as a separate language feature on the path to conditional conformances.

Looking Forward: Generalized Existentials
Generalized existentials (https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials) allows us to express more kinds of “existential” type in the language, e.g., “A Collection of some type of Element that we know is Equatable”, e.g.,

var a: Any<Collection where .Element: Equatable>
a = [1, 2, 3, 4, 5]
a = Set([“a”, “b”, “c”])

To get there, we can change (or extend) the protocol metadata (https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:

func f(any: Any) {
  if let c = any as? Any<Collection where .Element: Equatable> { … }
}

We should make the metadata change to allow this form of generalized existentials before locking down the ABI, even if we don’t settle on the feature in the surface language.

Thoughts?

Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?

John.
_______________________________________________
swift-dev mailing list
swift-dev@swift.org <mailto:swift-dev@swift.org>
https://lists.swift.org/mailman/listinfo/swift-dev

_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

Yes, I can see how there's some nice synergy there, and it would certainly be good to avoid having to eagerly generate code for this operation. And it should be possible to optimize the cast operation in the runtime if we find ourselves executing it many times for different types.

Okay, the basic idea seems reasonable to me. I guess my biggest concern is the use of just mangled names, since it seems like that will pose a lot of problems with private or local types.

As long as we mangle the unique private or local discriminator prefix, it shouldn’t be a problem. We’re not looking up global symbols by name, but scanning some kind of metadata section in the binary, which would presumably still have metadata for private and local types.

When Ashley was working on the remote-mirrors metadata, we had the idea of using descriptor "strings" that could embed a reference to a nominal type descriptor (or something like that) instead of just relying on a name. (A name would still be reasonable for a type that's not known to be defined within the linkage unit, of course.)

Yes, this would be a useful optimization, but I don’t think it’s a pre-requisite for getting an initial implementation going before the ABI is finalized.

In AST terms:
  func matchEnvironment(GenericSignature, Type, TypeMetadata) -> GenericEnvironment?
  func substitute(GenericEnvironment, Type) -> TypeMetadata?

By GenericEnvironment do you really mean a substitution map?

Slava

···

On Dec 6, 2017, at 10:00 PM, John McCall <rjmccall@apple.com> wrote:

Also note that the remote mirrors library already implements these operations in terms of TypeRefs, which are wrappers around mangled type strings. So there should be some potential for code reuse here.

Slava

···

On Dec 6, 2017, at 10:04 PM, Slava Pestov via swift-dev <swift-dev@swift.org> wrote:

In AST terms:
func matchEnvironment(GenericSignature, Type, TypeMetadata) -> GenericEnvironment?
func substitute(GenericEnvironment, Type) -> TypeMetadata?

By GenericEnvironment do you really mean a substitution map?

Yes, I can see how there's some nice synergy there, and it would certainly be good to avoid having to eagerly generate code for this operation. And it should be possible to optimize the cast operation in the runtime if we find ourselves executing it many times for different types.

Okay, the basic idea seems reasonable to me. I guess my biggest concern is the use of just mangled names, since it seems like that will pose a lot of problems with private or local types.

As long as we mangle the unique private or local discriminator prefix, it shouldn’t be a problem. We’re not looking up global symbols by name, but scanning some kind of metadata section in the binary, which would presumably still have metadata for private and local types.

Among other things, I have to note that this will make it much more difficult to dead-strip type metadata because we'll have to assume that somebody might have a string reference to it.

When Ashley was working on the remote-mirrors metadata, we had the idea of using descriptor "strings" that could embed a reference to a nominal type descriptor (or something like that) instead of just relying on a name. (A name would still be reasonable for a type that's not known to be defined within the linkage unit, of course.)

Yes, this would be a useful optimization, but I don’t think it’s a pre-requisite for getting an initial implementation going before the ABI is finalized.

I feel like if you try to use a purely name-based solution, you are going to end up solving the same problems but worse. Also, of course, it will be much more difficult to revise the expected representation after ABI is finalized.

In AST terms:
func matchEnvironment(GenericSignature, Type, TypeMetadata) -> GenericEnvironment?
func substitute(GenericEnvironment, Type) -> TypeMetadata?

By GenericEnvironment do you really mean a substitution map?

Yes, sorry, confused my terms.

John.

···

On Dec 7, 2017, at 1:03 AM, Slava Pestov <spestov@apple.com> wrote:

On Dec 6, 2017, at 10:00 PM, John McCall <rjmccall@apple.com> wrote:

Needed to implement NSCoding on Linux. They did limit it to "Foo.Bar" at least, deliberately excluding anything more complicated.

Jordan

···

On Dec 12, 2017, at 14:15, Douglas Gregor via swift-dev <swift-dev@swift.org> wrote:

On Dec 10, 2017, at 4:47 PM, Brent Royal-Gordon <brent@architechies.com <mailto:brent@architechies.com>> wrote:

On Dec 5, 2017, at 2:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

It's worth noting here that the standard library already provides a limited `_typeByName(_:)` function for Corelibs Foundation to use. That function will presumably become part of the ABI unless we design a public version in Swift 5.

Woah. That’s kinda awful… it parses “Foo.Bar” as a class name and looks for class Bar in module Foo.

Makes sense. A type(named:) would serve their use case better, of course.

  - Doug

···

On Dec 12, 2017, at 2:29 PM, Jordan Rose <jordan_rose@apple.com> wrote:

On Dec 12, 2017, at 14:15, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

On Dec 10, 2017, at 4:47 PM, Brent Royal-Gordon <brent@architechies.com <mailto:brent@architechies.com>> wrote:

On Dec 5, 2017, at 2:28 PM, Douglas Gregor via swift-dev <swift-dev@swift.org <mailto:swift-dev@swift.org>> wrote:

To perform that mapping from a mangled type in a conditional requirement to type metadata, we effectively need an operation to take a mangled type name and turn it into a type metadata pointer. This is something we could surface in the Swift standard library/runtime as, e.g.,

func type(named: String) -> Any.Type?

to take a mangled type name and try to get the type metadata for it. From there, one can query protocol conformances that (say) allow one to construct instances of the arbitrarily-named type. Think of it as NSClassFromString for any type in the Swift language, including specializations of generic types.

It's worth noting here that the standard library already provides a limited `_typeByName(_:)` function for Corelibs Foundation to use. That function will presumably become part of the ABI unless we design a public version in Swift 5.

Woah. That’s kinda awful… it parses “Foo.Bar” as a class name and looks for class Bar in module Foo.

Needed to implement NSCoding on Linux. They did limit it to "Foo.Bar" at least, deliberately excluding anything more complicated.