Tuples conform to Equatable, Comparable, and Hashableの実装

わいわいswiftc #24 https://iosdiscord.connpass.com/event/199431/

Transcript

1. Tuples conform to Equatable, Comparable, and Hashableͷ࣮૷ Θ͍Θ͍swiftc #22 @kateinoigakukun 1
2. ࣗݾ঺հ @kateinoigakukun • Merpay Expert Team Πϯλʔϯ • SwiftWasmϝϯςφ 2
3. ࠓ·Ͱͷ໰୊ let points = [(x: 128, y: 316), (x: 0, y: 0), (x: 100, y: 42)] let origin = (x: 0, y: 0) // error: type '(x: Int, y: Int)' cannot conform to 'Equatable'; // only struct/enum/class types can conform to protocols if points.contains(origin) { // do some serious calculations here } // error: type '(x: Int, y: Int)' cannot conform to 'Comparable'; // only struct/enum/class types can conform to protocols let sortedPoints = points.sorted() // error: type '(x: Int, y: Int)' cannot conform to 'Hashable'; // only struct/enum/class types can conform to protocols let uniquePoints = Set(points) 3
4. λϓϧ͕͋Δͱࣗಈ࣮૷΋Ͱ͖ͳ͘ͳͬͯͨ struct Restaurant { let name: String let location: (latitude: Int, longitude: Int) } // error: type 'Restaurant' does not conform to protocol 'Equatable' extension Restaurant: Equatable {} // error: type 'Restaurant' does not conform to protocol 'Hashable' extension Restaurant: Hashable {} 4
5. ࣮͸͢ͰʹΦʔόʔϩʔυ͸͋Δ SE-0015: Tuple comparison operators .gybͰίʔυੜ੒͞ΕͯΔɻ @warn_unused_result public func == <A: Equatable, B: Equatable, C: Equatable>(lhs: (A,B,C), rhs: (A,B,C)) -> Bool { return lhs.0 == rhs.0 && lhs.1 == rhs.1 && lhs.2 == rhs.2 } @warn_unused_result public func < <A: Comparable, B: Comparable, C: Comparable>(lhs: (A,B,C), rhs: (A,B,C)) -> Bool { if lhs.0 != rhs.0 { return lhs.0 < rhs.0 } if lhs.1 != rhs.1 { return lhs.1 < rhs.1 } return lhs.2 < rhs.2 } ... 5
6. SE-0283ͱ͸ શͯͷཁૉ͕EquatableɺComparableɺHashableͷ͍ͣΕ͔ʹ ४ڌ͍ͯ͠Δ৔߹ɺλϓϧࣗମ΋ͦͷϓϩτίϧʹ४ڌ͢Δ ϓϩϙʔβϧ͸डཧ͞Εɺ࣮૷΋͋Δ͕ϝΠϯετϦʔϜʹ͸ ೖͬͯͳ͍ https://github.com/apple/swift-evolution/blob/master/proposals/0283-tuples-are-equatable-comparable-hashable.md 6
7. func isEqual<T: Equatable>(_ lhs: T, _ rhs: T) -> Bool { lhs == rhs } // Ok, Int is Equatable thus the tuples are Equatable isEqual((1, 2, 3), (1, 2, 3)) // true struct EmptyStruct {} // error: type '(EmptyStruct, Int, Int)' does not conform to protocol 'Equatable' // note: value of type 'EmptyStruct' does not conform to protocol 'Equatable', // preventing conformance of '(EmptyStruct, Int, Int)' to 'Equatable' isEqual((EmptyStruct(), 1, 2), (EmptyStruct(), 1, 2)) // We don't take into account the labels for equality. isEqual((x: 0, y: 0), (0, 0)) // true 7
8. func isLessThan<T: Comparable>(_ lhs: T, _ rhs: T) -> Bool { lhs < rhs } let origin = (x: 0, y: 0) let randomPoint = (x: Int.random(in: 1 ... 10), y: Int.random(in: 1 ... 10)) // In this case, the first element of origin is 0 and the first element // of randomPoint is somewhere between 1 and 10, so they are not equal. // origin's element is less than randomPoint's, thus true. isLessThan(origin, randomPoint) // true // We don't take into account the labels for comparison. isLessThan((x: 0, y: 0), (1, 0)) // true 8
9. let points = [(x: 0, y: 0), (x: 1, y: 2), (x: 0, y: 0)] let uniquePoints = Set(points) // Create a grid system to hold game entities. var grid = [(x: Int, y: Int): Entity]() for point in uniquePoints { grid[point]?.move(up: 10) } // We don't take into account the labels for hash value. (x: 0, y: 0).hashValue == (0, 0).hashValue // true grid[(x: 100, y: 200)] = Entity(name: "Pam") print(grid[(100, 200)]) // Entity(name: "Pam") 9
10. ࣮૷ํ਑ λϓϧͷϓϩτίϧద߹ΛҰൠԽ͢Δͷ͸ϋʔυͳͷͰɺ EquatableɺComparableɺHashableʹରͯ͠ΞυϗοΫͳ࣮૷ Λ͢ΔɻίϯύΠϥతʹ͸ٕज़ෛ࠴ʹͳΔ͕ɺଟ͘ͷϢʔβʔ Λٹ͏͜ͱΛ༏ઌͯ͠Δɻ ࢀߟɿSpecial Case Protocol Conformance: Long-term Tradeoffs for Near-term Conformance 10
11. • ຊ౰͸͜͏͍͏ίʔυΛඪ४ϥΠϒϥϦʹೖΕ͓͚ͯͩ͘ʹ ͍ͨ͠ɻ • ͕ɺҰൠԽ͢Δʹ͸Մม௕δΣωϦΫεͳͲͷॏΊͷݴޠػ ೳ͕ඞཁ extension Tuple: Equatable where T1: Equatable, T2: Equatable, ... { public static func ==(_ lhs: Self, _ rhs: Self) -> Bool { ... } } 11
12. ࣮૷಺༰ PR apple/swift#28833 1. ௨ৗͷϓϩτίϧίϯϑΥʔϚϯεͷଞʹ BuiltinProtocolConformanceͷ֓೦Λ௥Ճ 2. ܕਪ࿦ثͷରԠ 3. ϥϯλΠϜϥΠϒϥϦʹBuiltinProtocolConformanceΛ࣮૷ 4. IRGenͰBuiltinProtocolConformanceΛࢀর͢ΔΑ͏ʹίʔ υੜ੒ ࠓ೔ͷϝΠϯτϐοΫ͸3ͱ4 12
13. ⾠ આ໌ͷͨΊɺٙࣅSwiftΛ࢖ͬͨΓɺ࣮ࡍ͸C++Ͱॻ͔Εͨϥ ϯλΠϜؔ਺ΛSwiftͰ؆୯ʹॻ͖௚ͨ͠Γͯ͠·͢ɻ 13
14. ௨ৗͷϓϩτίϧద߹ WitnessTable͕੩తʹܾ·Δ৔߹ 14
15. func isEqual<T: Equatable>(_ lhs: T, _ rhs: T) -> Bool { lhs == rhs } _ = isEqual(1, 2) // false // ↓తͳײ͡ʹίϯύΠϧ͞ΕΔ func isEqual(_ lhs: T, _ rhs: T, type: T.Type, witnessTable: WitnessTable) -> Bool { let fn = witnessTable[Equatable.==] return fn(lhs, rhs) } let Int_Equatable_WitnessTable: WitnessTable = [ Equatable.==: Int.==, ] _ = isEqual(1, 2, Int.self, Int_Equatable_WitnessTable) // false 15
16. ௨ৗͷϓϩτίϧద߹ WitnessTable͕ಈతʹܾ·Δ৔߹ 16
17. ίϯύΠϧલ public struct Box<T> { public let value: T } extension Box: CustomStringConvertible where T: CustomStringConvertible { var description: String { value.description } } func stringify<T: CustomStringConvertible>(_ target: T) -> String { return target.description } func boxStringify<T: CustomStringConvertible>(_ target: T) -> String { return stringify(Box(value: target)) } _ = boxStringify(1) // "1" 17
18. ίϯύΠϧޙ func stringify(_ target: T, type: T.Type, witnessTable: WitnessTable) -> String? { return witnessTable.description(target) } func boxStringify(_ target: T, type: T.Type, witnessTable: WitnessTable) -> String { let witnessTable = swift_getWitnessTable(Box<T>.self, CustomStringConvertible.self) return stringify(Box(value: target), Box<T>.self, witnessTable) } let Int_CustomStringConvertible_WitnessTable: WitnessTable = [ CustomStringConvertible.description: Int.description, ] _ = boxStringify(1, Int.self, Int_CustomStringConvertible_WitnessTable) // "1" 18
19. swift_conformsToProtocol͸Ͳ͏΍ͬͯWitnessTableΛऔ ಘͯ͠Δͷʁ // ඪ४ϥΠϒϥϦ public protocol CustomStringConvertible { ... } public extension Int: CustomStringConvertible { ... } let Int_CustomStringConvertible_WitnessTable: WitnessTable = [ CustomStringConvertible.description: Int.description, ] let localConformances = [ Conformance( type: Int.self, conforming: CustomStringConvertible.self, witnessTable: Int_CustomStringConvertible_WitnessTable ), ... ] _registerProtocolConformances(localConformances) 19
20. // ϥϯλΠϜϥΠϒϥϦ var globalConformances: [Conformance] = [] func _registerProtocolConformances(_ conformances: [Conformance]) { globalConformances.append(conformances) } func swift_getWitnessTable(_ type: Any.Type, _ proto: Protocol.Type) -> WitnessTable? { for conformance in globalConformances { if conformance.type == type && conformance.conforming == proto { return conformance.witnessTable } } return nil } https://github.com/apple/swift/blob/41f74e4/stdlib/public/runtime/ImageInspectionCommon.cpp 20
21. BuiltinProtocolConformance for λϓϧ ͭ·Γɺλϓϧ޲͚ͷWitness TableͱConformanceΛϥϯλΠ ϜϥΠϒϥϦʹ࡞͓͚ͬͯ͹ɺ੩త/ಈతͳϢʔεέʔεʹରԠ Ͱ͖Δɻ 21
22. खॻ͖ Tuple.== bool swift::_swift_tupleEquatable_equals(OpaqueValue *tuple1, OpaqueValue *tuple2, SWIFT_CONTEXT Metadata *swiftSelf, Metadata *Self, void *witnessTable) { auto tuple = cast<TupleTypeMetadata>(Self); auto table = reinterpret_cast<void**>(witnessTable); // Loop through all elements, and check if both tuples element is equal. for (size_t i = 0; i != tuple->NumElements; i += 1) { auto elt = tuple->getElement(i); // Get the element conformance from the private data in the witness table. auto conformance = reinterpret_cast<const WitnessTable *>(table[-1 - i]); auto value1 = reinterpret_cast<OpaqueValue *>( reinterpret_cast<char *>(tuple1) + elt.Offset); auto value2 = reinterpret_cast<OpaqueValue *>( reinterpret_cast<char *>(tuple2) + elt.Offset); // Grab the specific witness for this element type. auto equatableTable = reinterpret_cast<void * const *>(conformance); auto equalsWitness = equatableTable[WitnessTableFirstRequirementOffset]; auto equals = reinterpret_cast<StaticInfixWitness *>(equalsWitness); // Call the equal function auto result = equals(value1, value2, elt.Type, elt.Type, conformance); // If the values aren't equal, this tuple isn't equal. :) if (!result) return false; } // Otherwise this tuple has value equality with all elements. return true; } https://github.com/apple/swift/pull/28833/files#diff-c289d2fa8030a8b0648018ab48d060bb32554aa01b96399c406702089ef0033cR148-R184 22
23. खॻ͖Protocol Conformance Descriptor __asm( #if defined(__ELF__) " .type __swift_tupleEquatable_private, @object\n" " .local __swift_tupleEquatable_private\n" " .comm __swift_tupleEquatable_private, 128, 16\n" " .protected " TUPLE_EQUATABLE_CONF "\n" " .type " TUPLE_EQUATABLE_CONF ", @object\n" " .section .rodata\n" #elif defined(__MACH__) " .zerofill __DATA, __bss, __swift_tupleEquatable_private, 128, 4\n" " .section __TEXT, __const\n" #elif defined(_WIN32) " .lcomm __swift_tupleEquatable_private, 128, 16\n" " .section .rdata, \"dr\"\n" #pragma comment(linker, "/EXPORT:_swift_tupleEquatable_conf,DATA") #endif " .globl " TUPLE_EQUATABLE_CONF "\n" " .p2align 2\n" TUPLE_EQUATABLE_CONF ":\n" // This is an indirectable relative reference to the GOT entry for the // Equatable protocol descriptor. " .long " INDIRECT_RELREF_GOTPCREL(EQUATABLE_DESCRIPTOR_SYMBOL) "\n" // 769 is the MetadataKind::Tuple " .long 769\n" // This indicates that we have no witness table pattern. We use a generic // witness table for builtin conformances. " .long 0\n" // 196640 are the ConformanceFlags with the type reference bit set to // MetadataKind, the has resilient witness bit, and the generic witness table // bit. " .long 196640\n" // This 1 is the ResilientWitnessesHeader indicating we have 1 resilient // witness. " .long 1\n" // This is an indirectable relative reference to the GOT entry for the // Equatable == method descriptor. " .long " INDIRECT_RELREF_GOTPCREL(EQUATABLE_EE_METHOD_DESCRIPTOR) "\n" // This is a direct relative reference to the equals witness defined below. " .long (" TUPLE_EQUATABLE_EQUALS ") - .\n" // The witness table size in words. " .short 0\n" // The witness table private size in words & requires instantiation. " .short 1\n" // The witness table instantiator function. " .long 0\n" // This is a direct relative reference to the private data for the // conformance. " .long __swift_tupleEquatable_private - .\n" #if defined(__ELF__) " .size " TUPLE_EQUATABLE_CONF ", 40\n" #endif ); 23
24. extern "C" const ProtocolConformanceDescriptor _swift_tupleEquatable_conf; extern "C" const ProtocolConformanceDescriptor _swift_tupleComparable_conf; extern "C" const ProtocolConformanceDescriptor _swift_tupleHashable_conf; static const ProtocolConformanceDescriptor *getTupleConformanceDescriptor( const ProtocolDescriptor *protocol) { if (protocol == &EQUATABLE_DESCRIPTOR) { return &_swift_tupleEquatable_conf; } if (protocol == &COMPARABLE_DESCRIPTOR) { return &_swift_tupleComparable_conf; } if (protocol == &HASHABLE_DESCRIPTOR) { return &_swift_tupleHashable_conf; } return nullptr; } static const WitnessTable * swift_conformsToProtocolImpl(const Metadata *const type, const ProtocolDescriptor *protocol) { ... // If we're asking if a tuple conforms to a protocol, handle that here for // builtin conformances. if (auto tuple = dyn_cast<TupleTypeMetadata>(type)) { if (tupleConformsToProtocol(tuple, protocol)) { auto descriptor = getTupleConformanceDescriptor(protocol); C.cacheResult(type, protocol, descriptor->getWitnessTable(type), /*always cache*/ 0); } } ... } 24
25. ੩తͳProtocol Conformance Descriptorͷࢀর std::string IRGenMangler::mangleProtocolConformanceDescriptor( const RootProtocolConformance *conformance) { // Builtin conformances are different because they don't use a mangled name // for their conformance descriptors. For now, we use predefined symbol names // just in case in the future we have some conflict between actual // conformances and these builtin ones. if (isa<BuiltinProtocolConformance>(conformance)) { auto &ctx = conformance->getType()->getASTContext(); if (conformance->getType()->is<TupleType>()) { auto equatable = ctx.getProtocol(KnownProtocolKind::Equatable); auto comparable = ctx.getProtocol(KnownProtocolKind::Comparable); auto hashable = ctx.getProtocol(KnownProtocolKind::Hashable); if (conformance->getProtocol() == equatable) { return "_swift_tupleEquatable_conf"; } if (conformance->getProtocol() == comparable) { return "_swift_tupleComparable_conf"; } if (conformance->getProtocol() == hashable) { return "_swift_tupleHashable_conf"; } llvm_unreachable("mangling conformance descriptor for unknown tuple \ protocol"); } llvm_unreachable("mangling conformance descriptor for unknown builtin type"); } ... } 25
26. ͕͜͜ਏ͍ΑBuiltinProtocolConformance • ݴΘͣ΋͕ͳΠϯϥΠϯΞηϯϒϦ͕ਏ͍ 26
27. ճආࡦ1 • ίϯύΠϥͰඪ४ϥΠϒϥϦͷͨΊ͚ͩʹίʔυੜ੒͢Δ 27
28. ճආࡦ2 • LLVM IRͰॻ͘ 28