[swift-evolution] Overloading Generic Types

[Slava Pestov]

> On Feb 22, 2017, at 1:22 PM, David Sweeris via swift-evolution <swift-evolution at swift.org> wrote:
> 
>> 
>> On Feb 22, 2017, at 12:21 PM, Huon Wilson <huon at apple.com <mailto:huon at apple.com>> wrote:
>> 
>> 
>>> On Feb 22, 2017, at 10:20, David Sweeris via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>>> 
>>> What if we extended that to any type that’s ExpressibleByNilLiteral & Equatable?
>> 
>> Note that this is not how the Unsafe*Pointer optimization works: in that case, the type Unsafe*Pointer is not ExpressibleByNilLiteral, it just has some spare/guaranteed-to-be-unused sentinel values in its representation, that the compiler knows about. This also works for types like `enum X { case A, B }`: an optional like X? (and X??, all the way up to 254 ?’s) is also represented as a single byte, because there’s spare values that the compiler knows won't be used by valid instances of X.
>> 
>> Converting valid instances  to .none would break round-tripping: Optional(x)! would sometimes fail, if x was the sentinel value. This seems likely to cause generic code to stop working.
> 
> Oh, hey, yeah, good point! I should’ve thought about that bit more first. Would a `HasInvalidBitPattern` protocol work? 

This is basically how the optional payload optimization works behind the scenes. It’s not specific to optional, or having a certain payload type, it works for other enums also.

IRGen knows for each builtin type, what the valid and invalid bit patterns are. Basically reference types and unsafe pointers are the ones that are known to have invalid bit patterns (nulls, and for references, we also know the least significant 3 bits are always zero because of alignment). From this it can compute the valid and invalid bit patterns of tuple types and structs that appear in enum payloads also.

Slava

> protocol HasInvalidBitPattern {
>     /// An unreachable bit pattern. Very Bad Things are very likely to happen if this represents a valid value.
>     static var invalidBitPattern: Self {get} // probably use some private init to create this, or some other mechanism that doesn’t get exposed to the client
> }
> Then, the special-case Optional definition would be:
> enum Optional<T> : ExpressibleByNilLiteral where T: HasInvalidBitPattern & Equatable {
>     case some(T)
>     init(_ value: T) { self = .some(value) }
>     init(nilLiteral: ()) { self = .some(T.invalidBitPattern) }
>     var case none: (matches: Bool, associatedValue: Void) {
>         switch self {
>         case .some(let value): return (value == T.invalidBitPattern, ())
>         }
>     }
> }
> 
>> Example program for the enum optimization:
>> 
>> enum X {
>>     case A, B
>> }
>> 
>> typealias O2<T> = T??
>> typealias O4<T> = O2<O2<T>>
>> typealias O8<T> = O4<O4<T>>
>> typealias O16<T> = O8<O8<T>>
>> typealias O32<T> = O16<O16<T>>
>> typealias O64<T> = O32<O32<T>>
>> typealias O128<T> = O64<O64<T>>
>> typealias O256<T> = O128<O128<T>>
>> 
>> typealias O254<T> = O128<O64<O32<O16<O8<O4<O2<T>>>>>>>
>> typealias O255<T> = O254<T>?
>> 
>> func size<T>(_: T.Type) -> Int {
>>     return MemoryLayout<T>.size
>> }
>> 
>> print(size(X.self), // 1
>>       size((X?).self), // 1
>>       size(O254<X>.self), // 1
>>       size(O255<X>.self), // 2
>>       size(O256<X>.self)) // 3
>> 
>> (The last is 3 because the compiler currently essentially treats O255<X> like an opaque/all-values-valid 2-byte type, like Int16, and so adds an extra byte for the extra ?. It could theoretically be 2 if the unused values in the extra byte in O255<X> are reused.)
> 
> That’s quite interesting, thanks!
> 
> - Dave Sweeris
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org <mailto:swift-evolution at swift.org>
> https://lists.swift.org/mailman/listinfo/swift-evolution <https://lists.swift.org/mailman/listinfo/swift-evolution>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170222/cd9ebe63/attachment.html>