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

[Xiaodi Wu]

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 struct 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.x == rhs.x for all stored properties in T.
>>>
>>> A struct 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 hash
>>> values of the fields as its terms, in definition order.
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170504/8aa6b21e/attachment.html>