[swift-evolution] Pitch: Automatically deriving Equatable/Hashable for more value types

Tony Allevato tony.allevato at gmail.com
Thu May 4 17:23:08 CDT 2017

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.

On Thu, May 4, 2017 at 3:16 PM Xiaodi Wu via swift-evolution <
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> wrote:
>> On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <
>> 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> 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> 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
>>>> 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 falselet 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170504/1d2fc3c4/attachment-0001.html>

More information about the swift-evolution mailing list