[swift-evolution] Pitch: Automatically deriving Equatable/Hashable for more value types
Matthew Johnson
matthew at anandabits.com
Thu May 4 19:24:39 CDT 2017
> On May 4, 2017, at 5:23 PM, Tony Allevato via swift-evolution <swift-evolution at swift.org> wrote:
>
> When I initially wrote an earlier version of this proposal last year, I was imagining implicit derivation (as it is today for no-associated-value enums). However, now that I'm deeper into it (and have tried implementing some of it), I think explicit is the way to go.
>
> My main reason for changing my mind is that I think it will make the mutually recursive cases much easier. Today, with implicit derivation, I have to traverse the full cycles to figure out if equatability/hashability permeates through the full type graph starting from a particular type. With explicit derivation, I should just be able to look at the immediate member types to see if they *declare* the conformance, and if it can't be derived (because a stored property/associated value is not E/H), then it's an error on *that* type.
>
> My only reservations have been the inconsistency with no-associated-value enums and raw value enums, where the derivation is currently implicit. But I think the benefits of making it explicit outweigh the disadvantages.
>
> Regarding syntax, some folks in the last discussion on this topic preferred a "derived" keyword, but I feel that's unnecessary, and if Codable provides precedent for not having such a keyword, we should stick with that.
Huge +1 to this proposal and +1 to making it explicit following the precedent set by Codable. Thank you for driving this forward Tony!
In addition to the specific examples in the proposal I think it’s important to point out that this proposal will make it more feasible in general for libraries require Equatable or Hashable conformances of user-supplied types - doing so will no longer place the burden of manual conformance on all of these types.
It would be nice to see enums without associated values require explicit conformance as well in the future but that should be a separate proposal.
>
> On Thu, May 4, 2017 at 3:16 PM Xiaodi Wu via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> I'm imagining no syntax; effectively, as though there exists an "extension Equatable where [ all members : Equatable ]" with a default implementation.
>
>
> On Thu, May 4, 2017 at 17:13 John McCall <rjmccall at apple.com <mailto:rjmccall at apple.com>> wrote:
>> On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> I agree, let's make it opt-in.
>>
>> This looks really great, I'm excited to get generated conformance for Equatable/Hashable in time for Swift 4.
>>
>> I think it's worth mentioning that Encoding/Decoding generated conformance is already accepted and implemented in Swift 4. The implementation and acceptance criterion for Equatable/Hashable is likely to be very similar.
>>
>> For the open questions, I think for the sake of getting this into Swift 4 we should go for explicit derivation, and don't allow omission of fields (yet).
>
> Is there a syntax proposal for explicit derivation? Or are you imagining that just declaring the conformance but failing to implement it should trigger derivation?
>
> John.
>
>>
>> Omission is nice-to-have, but likely to be a long-winded bike-shed.
>>
>> Changing from explicit to implicit is a loss of information, and has a large impact on the language, it can't easily be undone, so it requires a large discussion when it's decided. It only adds a little additional convenience to the user though.
>>
>> I suggest we discuss implicit generation and allowing omission with follow-up proposals, they will very likely be additive non-breaking changes. For this proposal we play it safe and stick to explicit conformance and no omission of fields.
>>
>>
>> On Fri, May 5, 2017 at 8:01 AM, Xiaodi Wu via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> Hmm, I can see the appeal of automatically deriving Equatable and Hashable conformance, but I'd like that to be opt-in. That is, types should declare that they are Equatable or Hashable to begin with. It wouldn't have to take extra syntax, as compiler magic could effectively synthesize default implementations for == and/or hashValue when all members are themselves Equatable or Hashable, respectively. With such a scheme, consideration can be made to accommodating classes too.
>> On Thu, May 4, 2017 at 15:37 Tony Allevato via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
>> Hi all,
>>
>> A conversation on Twitter last night brought up some interest in this feature and I was encouraged to revive this proposal.
>>
>> Jordan Rose mentioned <https://twitter.com/UINT_MIN/status/859922619578986496> on Twitter that it could possibly make it in by the Swift 4 deadline if others contributed—I have a WIP branch (albeit not currently working because I rebased after a couple months of it being idle) that does the work for enums but I got stuck on the mutually recursive cases. If this got approved, I'd love to collaborate with other interested folks to finish up the implementation.
>>
>> Link: https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad>
>>
>>
>> Deriving Equatable and Hashable for value types
>>
>> Proposal: SE-0000 <https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md>
>> Author(s): Tony Allevato <https://github.com/allevato>
>> Status: Awaiting review <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
>> Review manager: TBD
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#introduction>Introduction
>>
>> Value types are prevalent throughout the Swift language, and we encourage developers to think in those terms when writing their own types. Frequently, developers have to write large amounts of boilerplate code to support equatability and hashability of value types. This proposal offers a way for the compiler to automatically derive conformance to Equatable and Hashable to reduce this boilerplate, in a subset of scenarios where generating the correct implementation is known to be possible.
>>
>> Swift-evolution thread: Universal Equatability, Hashability, and Comparability <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#motivation>Motivation
>>
>> Building robust value types in Swift can involve writing significant boilerplate code to support hashability and equatability. Equality is pervasive across many value types, and for each one users must implement the == operator such that it performs a fairly rote memberwise equality test. As an example, an equality test for a struct looks fairly uninteresting:
>>
>> struct Foo: Equatable {
>> static func == (lhs: Foo, rhs: Foo) -> Bool {
>> return lhs.property1 == rhs.property1 &&
>> lhs.property2 == rhs.property2 &&
>> lhs.property3 == rhs.property3 &&
>> ...
>> }
>> }
>> What's worse is that this operator must be updated if any properties are added, removed, or changed, and since it must be manually written, it's possible to get it wrong, either by omission or typographical error.
>>
>> Likewise, hashability is necessary when one wishes to store a value type in a Set or use one as a multi-valued Dictionary key. Writing high-quality, well-distributed hash functions is not trivial so developers may not put a great deal of thought into them – especially as the number of properties increases – not realizing that their performance could potentially suffer as a result. And as with equality, writing it manually means there is the potential to get it wrong.
>>
>> In particular, the code that must be written to implement equality for enums is quite verbose:
>>
>> enum Token: Equatable {
>> case string(String)
>> case number(Int)
>> case lparen
>> case rparen
>>
>> static func == (lhs: Token, rhs: Token) -> Bool {
>> switch (lhs, rhs) {
>> case (.string(let lhsString), .string(let rhsString)):
>> return lhsString == rhsString
>> case (.number(let lhsNumber), .number(let lhsNumber)):
>> return lhsNumber == rhsNumber
>> case (.lparen, .lparen), (.rparen, .rparen):
>> return true
>> default:
>> return false
>> }
>> }
>> }
>> Crafting a high-quality hash function for this enum would be similarly inconvenient to write.
>>
>> Swift already derives Equatable and Hashable conformance for a small subset of enums: those for which the cases have no associated values (including enums with raw types). Two instances of such an enum are equal if they are the same case, and an instance's hash value is its ordinal:
>>
>> enum Foo {
>> case zero, one, two
>> }
>>
>> let x = (Foo.one == Foo.two) // evaluates to false
>> let y = Foo.one.hashValue // evaluates to 1
>> Likewise, conformance to RawRepresentable is automatically derived for enums with a raw type. Since there is precedent for derived conformances in Swift, we propose extending this support to more value types.
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#proposed-solution>Proposed solution
>>
>> In general, we propose that value types derive conformance to Equatable/Hashable if all of its members are Equatable/Hashable. We describe the specific conditions under which these conformances are derived below, followed by the details of how the conformance requirements are implemented.
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#protocol-derivability-conditions>Protocol derivability conditions
>>
>> For brevity, let P represent either the protocol Equatable or Hashable in the descriptions below.
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#derived-conformances-for-enums>Derived conformances for enums
>>
>> For an enum, derivability of P is based on the conformances of its cases' associated values. Computed properties are not considered.
>>
>> The following rules determine whether conformance to P can be derived for an enum:
>>
>> An enum with no cases does not derive conformance to P, since it is not possible to create instances of such types.
>>
>> An enum with one or more cases derives conformance to P if all of the associated values of all of its cases conform to P (either explicitly or derived).
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#derived-conformances-for-structs>Derived conformances for structs
>>
>> For a struct, derivability of P is based on the conformances of its stored instance properties only. Neither static properties nor computed instance properties (those with custom getters) are considered.
>>
>> The following rules determine whether conformance to P can be derived for a struct:
>>
>> A struct with no stored properties does not derive conformance to P. (Even though it is vacuously true that all instances of a struct with no stored properties could be considered equal and hash to the same value, the reality is that such structs are more often used for grouping/nesting of other entities and not for their singular value, and we don't consider it worthwhile to generate extra code in this case.)
>>
>> A struct with one or more stored properties derives conformance to P if all if the types of all of its stored properties conform to P (either explicitly or derived).
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#considerations-for-recursive-types>Considerations for recursive types
>>
>> For brevity in the discussion below, the term members refers only to those members that are checked for deriving conformances: stored properties for structs and associated values for enums.
>>
>> Recursive value types require a bit more care when determining whether a conformance can be derived. Consider the following enum with an indirect case:
>>
>> enum TreeNode {
>> case empty
>> case leaf(value: Int)
>> case internal(left: TreeNode, right: TreeNode)
>> }
>> When examining the internal case, an application of the rules above implies that "TreeNode derives P if TreeNode conforms to P"—a recursive condition. In this situation, we note that any instance of this type—or of any recursive type—forms a finite tree structure because the recursion must be terminated eventually by using one of the other base cases. Therefore, without changing the outcome, we can assume for the purposes of determining whether T derives P that any members of type T already conform to P. If any members of different types prohibit deriving P, then we know that the whole type cannot derive it; likewise, if all of the other members permit deriving P, then we know that T can derive it by recursively applying the derived operation.
>>
>> This property can be extended to mutually recursive types as well. Consider this contrived example:
>>
>> enum A {
>> case value(Int)
>> case b(B)
>> }
>>
>> enum B {
>> case value(String)
>> case c(C)
>> }
>>
>> enum C {
>> case value(Double)
>> case a(A)
>> }
>> The rules state that—ignoring the trivial cases—"A derives P if B conforms to P," and "B derives P if Cconforms to P," and "C derives P if A conforms to P." The same observation about recursion and the finiteness of instances from above holds here, so we can generalize the rule above as follows:
>>
>> A type T can derive P if all members of T conform to P or are of types found in cycles that lead back to Tsuch that the members of those other types along the cycle also all conform to P or are themselves along such a cycle.
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#other-considerations>Other considerations
>>
>> When conditional conformances are supported in Swift, generic types should conditionally derive Equatable and Hashable for type argument substitutions where the rules above are satisfied.
>>
>> A notable side effect of this is that Optional<Wrapped> would derive Equatable and Hashable conformance when Wrapped conforms to those protocols, because it is an enum that would satisfy the rules described above. Its implementation would not need to be in the standard library (but there is also nothing preventing it from being there).
>>
>> Conditional conformances will also significantly improve derivability coverage over other payload/member types. For example, consider a struct containing a stored property that is an array of Equatable types:
>>
>> struct Foo {
>> var values: [String]
>> }
>> Today, Array<String> does not conform to Equatable, so its presence would prohibit Foo from deriving Equatable. However, once Swift can express the conformance Array<Element>: Equatable where Element: Equatable, Foo would automatically derive Equatable as well. This makes derived conformances significantly more powerful.
>>
>> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#implementation-details>Implementation details
>>
>> An enum T that derives Equatable will receive a compiler-generated implementation of static == (lhs: T, rhs: T) -> Bool that returns true if and only if lhs and rhs are the same case and have payloads that are memberwise-equal.
>>
>> An enum T that derives Hashable will receive a compiler-generated implementation of var hashValue: Int { get }that uses an unspecified hash function† to compute the hash value by incorporating the case's ordinal (i.e., definition order) followed by the hash values of its associated values as its terms, also in definition order.
>>
>> A
>>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170504/7e696e2c/attachment.html>
More information about the swift-evolution
mailing list