<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Dec 5, 2017, at 3:42 PM, John McCall <<a href="mailto:rjmccall@apple.com" class="">rjmccall@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class="">On Dec 5, 2017, at 5:28 PM, Douglas Gregor via swift-dev <<a href="mailto:swift-dev@swift.org" class="">swift-dev@swift.org</a>> wrote:</div><div class=""><div class="" style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;">Hi all,<div class=""><br class=""></div><div class="">The main missing piece for conditional conformances (<a href="https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md" class="">https://github.com/apple/swift-evolution/blob/master/proposals/0143-conditional-conformances.md</a>) is support for dynamic casting. Right now, dynamic casting that queries a conditional conformance will always fail. Here’s an example:</div><div class=""><br class=""></div><blockquote class="" style="margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class=""><div class=""><font face="Menlo" class="">protocol P {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> func foo()</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">struct X : P {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> func foo() { print("X.P") }</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">struct Y<T> {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> var wrapped: T</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">extension Y: P where T: P {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> func foo() { wrapped.foo() }</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">func tryAsP(_ value: Any) {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> if let p = value as? P {</font></div></div><div class=""><div class=""><font face="Menlo" class=""> p.foo()</font></div></div><div class=""><div class=""><font face="Menlo" class=""> }</font></div></div><div class=""><div class=""><font face="Menlo" class="">}</font></div></div><div class=""><div class=""><font face="Menlo" class=""><br class=""></font></div></div><div class=""><div class=""><font face="Menlo" class="">let yx = Y(wrapped: X())</font></div></div><div class=""><div class=""><font face="Menlo" class="">tryAsP(yx)</font></div></div></blockquote><div class=""><br class=""></div><div class="">This won’t print anything, but should print “X.P”. We’d like to fix that :)</div><div class=""><br class=""></div><div class="">Joe Groff, Slava, and I discussed an approach to implement dynamic casting for conditional conformances, which I’d like to outline here.</div><div class=""><br class=""></div><div class=""><b class="">Background</b></div><div class="">The Swift runtime expresses the conformance of a specific type (say Array<Int>) to a particular protocol (say, Equatable) using a<span class="Apple-converted-space"> </span><i class="">witness table</i>. 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 (<a href="https://llvm.org/devmtg/2017-10/#talk15" class="">https://llvm.org/devmtg/2017-10/#talk15</a>) gives a bunch of background here.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class=""><b class="">Protocol Conformance Records</b></div><div class="">Whenever code declares conformance of a particular type to a given protocol, the compiler emits a “protocol conformance record” (documented at <a href="https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records" class="">https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-conformance-records</a>). 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. </div><div class=""><br class=""></div><div class=""><b class="">Conditional Requirements in Protocol Conformance Records</b></div><div class="">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 <a href="https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics" class="">https://github.com/apple/swift/blob/master/docs/ABI/Mangling.rst#generics</a>) already encodes arbitrary generic requirements, so we can put a string comprised of the mangled conditional requirements into the protocol conformance record.</div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">Note that the conditional requirements can be arbitrarily complicated. For example, given:</div><div class=""><br class=""></div><blockquote class="" style="margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class=""><font face="Menlo" class="">extension Dictionary: P where Value == (Key) -> Bool { … }</font></div></blockquote><div class=""><br class=""></div><div class="">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). </div><div class=""><br class=""></div><div class=""><b class="">Looking up Type Metadata For a Mangled Name</b></div><div class="">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.,</div><div class=""><br class=""></div><blockquote class="" style="margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class=""><font face="Menlo" class="">func type(named: String) -> Any.Type?</font></div></blockquote><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">To get here, we’ll also need to extend the nominal type descriptor (<a href="https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor" class="">https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#nominal-type-descriptor</a>) 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.</div><div class=""><br class=""></div><div class=""><b class="">Looking Forward: Generalized Existentials</b></div><div class="">Generalized existentials (<a href="https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials" class="">https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#generalized-existentials</a>) 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.,</div><div class=""><br class=""></div><blockquote class="" style="margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class=""><font face="Menlo" class="">var a: Any<Collection where .Element: Equatable></font></div><div class=""><font face="Menlo" class="">a = [1, 2, 3, 4, 5]</font></div><div class=""><font face="Menlo" class="">a = Set([“a”, “b”, “c”])</font></div></blockquote><div class=""><br class=""></div><div class="">To get there, we can change (or extend) the protocol metadata (<a href="https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata" class="">https://github.com/apple/swift/blob/master/docs/ABI/TypeMetadata.rst#protocol-metadata</a>) to contain a complete generic signature, which can be evaluated dynamically using the same mechanisms described above. For example:</div><div class=""><br class=""></div><blockquote class="" style="margin: 0px 0px 0px 40px; border: none; padding: 0px;"><div class=""><font face="Menlo" class="">func f(any: Any) {</font></div><div class=""><font face="Menlo" class=""> if let c = any as? Any<Collection where .Element: Equatable> { … }</font></div><div class=""><font face="Menlo" class="">}</font></div></blockquote><div class=""><br class=""></div><div class="">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.</div><div class=""><b class=""><br class=""></b></div><div class="">Thoughts?</div></div></div></blockquote><div class=""><br class=""></div>Couldn't we just encode a metadata path for the associated type and then do the conformance lookup?</div></div></blockquote><br class=""></div><div>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.</div><div><br class=""></div><div>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.</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>- Doug</div><div><br class=""></div></body></html>