Pitch: Automatically deriving Equatable/Hashable for more value types


(Tony Allevato) #1

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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide their
own implementations to ignore it.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be completely
implicit, or should users have to explicitly list conformance with Equatable
and Hashable in order for the compiler to generate the derived
implementation?

If derived conformances were made explicit, it could be argued that this
should also be done for consistency across raw-value enums as well. This
would be a source-breaking change, which should be avoided at this stage.
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change would make types that satisfy the rules above Equatable and
Hashable when they previously were not. It is not expected that there would
be any *behavioral* changes because of this; since Equatable and Hashable have
associated type requirements, users cannot be dynamically testing for
conformance to them at runtime.

Value types that already provide custom implementations of Equatable and
Hashable would keep the custom implementation because it would override the
compiler-provided default.

This change would potentially increase binary size when it generates
conformances that did not exist before, at least for types where it is not
possible to know that the conformances are unused and thus cannot be
dead-stripped (i.e., public types).
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate for
automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.
------------------------------
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
Rationale

On [Date], the core team decided to (TBD) this proposal. When the core team
makes a decision regarding this proposal, their rationale for the decision
will be written here.


(Xiaodi Wu) #2

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@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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely implicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?

If derived conformances were made explicit, it could be argued that this
should also be done for consistency across raw-value enums as well. This
would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change would make types that satisfy the rules above Equatable and
Hashable when they previously were not. It is not expected that there
would be any *behavioral* changes because of this; since Equatable and
Hashable have associated type requirements, users cannot be dynamically
testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and
Hashable would keep the custom implementation because it would override
the compiler-provided default.

This change would potentially increase binary size when it generates
conformances that did not exist before, at least for types where it is not
possible to know that the conformances are unused and thus cannot be
dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate
for automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.
------------------------------

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
Rationale

On [Date], the core team decided to (TBD) this proposal. When the core
team makes a decision regarding this proposal, their rationale for the
decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charlie Monroe) #3

I'm also leaning towards this being opt-in and the generation could be triggered by having AutoEquatable and AutoHashable protocols.

Any chance for this proposal to be extended by adding "PointerEquatable" for classes? In many cases, pointer equality is just enough and having the class equatable by pointer allows e.g. better array inter-op (e.g. removing an object doesn't require getting an index first)...

···

On May 4, 2017, at 10:37 PM, Tony Allevato via swift-evolution <swift-evolution@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 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 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.

† We intentionally leave the exact definition of the hash function unspecified here. A multiplicative hash function with good distribution is the likely candidate, but we do not rule out other possibilities. Users should not depend on the nature of the generated implementation or rely on particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding derived conformances

Any user-provided implementations of == or hashValue will override the default implementations that would be provided by the compiler. This is already the case possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open questions

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a struct from being included in automatically generated equality tests or hash value computations. This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely implicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

If derived conformances were made explicit, it could be argued that this should also be done for consistency across raw-value enums as well. This would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact on existing code

This change would make types that satisfy the rules above Equatable and Hashable when they previously were not. It is not expected that there would be any behavioral changes because of this; since Equatable and Hashable have associated type requirements, users cannot be dynamically testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and Hashable would keep the custom implementation because it would override the compiler-provided default.

This change would potentially increase binary size when it generates conformances that did not exist before, at least for types where it is not possible to know that the conformances are unused and thus cannot be dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>Rationale

On [Date], the core team decided to (TBD) this proposal. When the core team makes a decision regarding this proposal, their rationale for the decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #4

I should add, requiring opt-in doesn't necessarily mean one must break
source compatibility for enums currently with derived equality. That can be
grandfathered in.

Later, we can even explore more comprehensive functionality when an enum is
declared "Foo : Int". In my opinion, the ideal endpoint in Swift N (where N

4) is true value subtyping; absent that, it would only make sense that

Foo would at least conform to all the protocols to which Int conforms. A
longer-term discussion clearly out of scope here, but mentioned only to say
that existing magic doesn't need to be rolled back necessarily.

While we're on this topic though, it'd be really nice to revisit Equatable
and Hashable for tuples; that's one place where implicit magic may be the
best way to go. Currently, tuples of arity 6 or less benefit from a manual
hack to be Equatable, but we can clearly do better.

···

On Thu, May 4, 2017 at 17:01 Xiaodi Wu <xiaodi.wu@gmail.com> 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@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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely implicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?

If derived conformances were made explicit, it could be argued that this
should also be done for consistency across raw-value enums as well. This
would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change would make types that satisfy the rules above Equatable and
Hashable when they previously were not. It is not expected that there
would be any *behavioral* changes because of this; since Equatable and
Hashable have associated type requirements, users cannot be dynamically
testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and
Hashable would keep the custom implementation because it would override
the compiler-provided default.

This change would potentially increase binary size when it generates
conformances that did not exist before, a


(Brent Royal-Gordon) #5

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.

Another benefit is that the problem you're currently having with recursion goes away: from outside the type, you merely need to check if conformance is declared.

Explicit with no special syntactic marker is definitely the way to go. It would work just like Codable is slated to.

With such a scheme, consideration can be made to accommodating classes too.

I would think only final classes could participate in this, since a subclassable class would need to allow subclasses to override equality, and you can't override a static `==` operator method.

(My time is not unlimited right now, but I'd be willing to help with either the proposal or its implementation. This would be a great thing to get into Swift 4.)

···

On May 4, 2017, at 3:01 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies


(Xiaodi Wu) #6

As the documentation for Equatable discusses, the goal is to distinguish
"equality" (==) from "identity" (===). If I understand it correctly, the
goal is to *discourage* mixing the two concepts.

Moreover, while writing a memberwise comparison is tedious and writing a
memberwise hash is even error-prone, writing "return lhs === rhs" is both
straightforward and impossible to mess up, so having special magic for that
use case is much harder to justify.

···

On Thu, May 4, 2017 at 23:45 Charlie Monroe via swift-evolution < swift-evolution@swift.org> wrote:

I'm also leaning towards this being opt-in and the generation could be
triggered by having AutoEquatable and AutoHashable protocols.

Any chance for this proposal to be extended by adding "PointerEquatable"
for classes? In many cases, pointer equality is just enough and having the
class equatable by pointer allows e.g. better array inter-op (e.g. removing
an object doesn't require getting an index first)...

On May 4, 2017, at 10:37 PM, Tony Allevato via swift-evolution < > swift-evolution@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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely implicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?

If derived conformances were made explicit, it could be argued that this
should also be done for consistency across raw-value enums as well. This
would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change would make types that satisfy the rules above Equatable and
Hashable when they previously were not. It is not expected that there
would be any *behavioral* changes because of this; since Equatable and
Hashable have associated type requirements, users cannot be dynamically
testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and
Hashable would keep the custom implementation because it would override
the compiler-provided default.

This change would potentially increase binary size when it generates
conformances that did not exist before, at least for types where it is not
possible to know that the conformances are unused and thus cannot be
dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate
for automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.
------------------------------

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
Rationale
On [Date], the core team decided to (TBD) this proposal. When the core
team makes a decision regarding this proposal, their rationale for the
decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Charlie Monroe) #7

As the documentation for Equatable discusses, the goal is to distinguish "equality" (==) from "identity" (===). If I understand it correctly, the goal is to *discourage* mixing the two concepts.

Moreover, while writing a memberwise comparison is tedious and writing a memberwise hash is even error-prone, writing "return lhs === rhs" is both straightforward and impossible to mess up, so having special magic for that use case is much harder to justify.

There doesn't need to be any magic - why would there need to be?

public protocol PointerEquatable: AnyObject, Equatable, Hashable {
  
  public static func ==(lhs: Self, rhs: Self) -> Bool {
    return lhs === rhs
  }
  
  public var hashValue: Int {
    return ObjectIdentifier(self).hashValue
  }
  
}

I'm not saying it's super hard but while we're at it, we might as well include something like this in case identity is enough for equality, in such case

class Foo: PointerEquatable { }

is enough for the class to be hashable and equatable. It's all opt-in, there's no magic - I don't quite see the downside to it.

···

On May 5, 2017, at 6:58 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Thu, May 4, 2017 at 23:45 Charlie Monroe via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
I'm also leaning towards this being opt-in and the generation could be triggered by having AutoEquatable and AutoHashable protocols.

Any chance for this proposal to be extended by adding "PointerEquatable" for classes? In many cases, pointer equality is just enough and having the class equatable by pointer allows e.g. better array inter-op (e.g. removing an object doesn't require getting an index first)...

On May 4, 2017, at 10:37 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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 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 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.

† We intentionally leave the exact definition of the hash function unspecified here. A multiplicative hash function with good distribution is the likely candidate, but we do not rule out other possibilities. Users should not depend on the nature of the generated implementation or rely on particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding derived conformances

Any user-provided implementations of == or hashValue will override the default implementations that would be provided by the compiler. This is already the case possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open questions

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a struct from being included in automatically generated equality tests or hash value computations. This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely implicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

If derived conformances were made explicit, it could be argued that this should also be done for consistency across raw-value enums as well. This would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact on existing code

This change would make types that satisfy the rules above Equatable and Hashable when they previously were not. It is not expected that there would be any behavioral changes because of this; since Equatable and Hashable have associated type requirements, users cannot be dynamically testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and Hashable would keep the custom implementation because it would override the compiler-provided default.

This change would potentially increase binary size when it generates conformances that did not exist before, at least for types where it is not possible to know that the conformances are unused and thus cannot be dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>Rationale

On [Date], the core team decided to (TBD) this proposal. When the core team makes a decision regarding this proposal, their rationale for the decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Andrew Bennett) #8

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).

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@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@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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely implicit, or should users have to explicitly list conformance
with Equatable and Hashable in order for the compiler to generate the
derived implementation?

If derived conformances were made explicit, it could be argued that this
should also be done for consistency across raw-value enums as well. This
would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact
on existing code

This change would make types that satisfy the rules above Equatable and
Hashable when they previously were not. It is not expected that there
would be any *behavioral* changes because of this; since Equatable and
Hashable have associated type requirements, users cannot be dynamically
testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and
Hashable would keep the custom implementation because it would override
the compiler-provided default.

This change would potentially increase binary size when it generates
conformances that did not exist before, at least for types where it is not
possible to know that the conformances are unused and thus cannot be
dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives
considered

The original discussion thread also included Comparable as a candidate
for automatic generation. Unlike equatability and hashability, however,
comparability requires an ordering among the members being compared.
Automatically using the definition order here might be too surprising for
users, but worse, it also means that reordering properties in the source
code changes the code's behavior at runtime. (This is true for hashability
as well if a multiplicative hash function is used, but hash values are not
intended to be persistent and reordering the terms does not produce a
significant *behavioral* change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>
Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose
Cheyo Jimenez for providing great real-world examples of boilerplate needed
to support equatability for some value types, and to Mark Sands for
necromancing the swift-evolution thread that convinced me to write this up.
------------------------------

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
Rationale

On [Date], the core team decided to (TBD) this proposal. When the core
team makes a decision regarding this proposal, their rationale for the
decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Chris Lattner) #9

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.

Completely agreed.

-Chris

···

On May 4, 2017, at 3:01 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, May 4, 2017 at 15:37 Tony Allevato via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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 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 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.

† We intentionally leave the exact definition of the hash function unspecified here. A multiplicative hash function with good distribution is the likely candidate, but we do not rule out other possibilities. Users should not depend on the nature of the generated implementation or rely on particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding derived conformances

Any user-provided implementations of == or hashValue will override the default implementations that would be provided by the compiler. This is already the case possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open questions

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a struct from being included in automatically generated equality tests or hash value computations. This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely implicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

If derived conformances were made explicit, it could be argued that this should also be done for consistency across raw-value enums as well. This would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact on existing code

This change would make types that satisfy the rules above Equatable and Hashable when they previously were not. It is not expected that there would be any behavioral changes because of this; since Equatable and Hashable have associated type requirements, users cannot be dynamically testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and Hashable would keep the custom implementation because it would override the compiler-provided default.

This change would potentially increase binary size when it generates conformances that did not exist before, at least for types where it is not possible to know that the conformances are unused and thus cannot be dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>Rationale

On [Date], the core team decided to (TBD) this proposal. When the core team makes a decision regarding this proposal, their rationale for the decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(John McCall) #10

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.

···

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org> wrote:

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@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 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 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.

† We intentionally leave the exact definition of the hash function unspecified here. A multiplicative hash function with good distribution is the likely candidate, but we do not rule out other possibilities. Users should not depend on the nature of the generated implementation or rely on particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding derived conformances

Any user-provided implementations of == or hashValue will override the default implementations that would be provided by the compiler. This is already the case possible today with raw-value enums so the same behavior should be extended to other value types that are made to implicitly conform to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open questions

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a struct from being included in automatically generated equality tests or hash value computations. This could be valuable, for example, if a property is merely used as an internal cache and does not actually contribute to the "value" of the instance. Under the rules above, if this cached value was equatable, a user would have to override == and hashValue and provide their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit or implicit derivation

As with raw-value enums today, should the derived conformance be completely implicit, or should users have to explicitly list conformance with Equatable and Hashable in order for the compiler to generate the derived implementation?

If derived conformances were made explicit, it could be argued that this should also be done for consistency across raw-value enums as well. This would be a source-breaking change, which should be avoided at this stage.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#impact-on-existing-code>Impact on existing code

This change would make types that satisfy the rules above Equatable and Hashable when they previously were not. It is not expected that there would be any behavioral changes because of this; since Equatable and Hashable have associated type requirements, users cannot be dynamically testing for conformance to them at runtime.

Value types that already provide custom implementations of Equatable and Hashable would keep the custom implementation because it would override the compiler-provided default.

This change would potentially increase binary size when it generates conformances that did not exist before, at least for types where it is not possible to know that the conformances are unused and thus cannot be dead-stripped (i.e., public types).

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#alternatives-considered>Alternatives considered

The original discussion thread also included Comparable as a candidate for automatic generation. Unlike equatability and hashability, however, comparability requires an ordering among the members being compared. Automatically using the definition order here might be too surprising for users, but worse, it also means that reordering properties in the source code changes the code's behavior at runtime. (This is true for hashability as well if a multiplicative hash function is used, but hash values are not intended to be persistent and reordering the terms does not produce a significant behavioral change.)

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#acknowledgments>Acknowledgments

Thanks to Joe Groff for spinning off the original discussion thread, Jose Cheyo Jimenez for providing great real-world examples of boilerplate needed to support equatability for some value types, and to Mark Sands for necromancing the swift-evolution thread that convinced me to write this up.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>Rationale

On [Date], the core team decided to (TBD) this proposal. When the core team makes a decision regarding this proposal, their rationale for the decision will be written here.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Matthew Johnson) #11

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 May 4, 2017, at 5:23 PM, Tony Allevato via swift-evolution <swift-evolution@swift.org> wrote:

On Thu, May 4, 2017 at 3:16 PM Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@apple.com <mailto:rjmccall@apple.com>> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #12

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@apple.com> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution < > swift-evolution@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@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@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.


(Tony Allevato) #13

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@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@apple.com> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution < >> swift-evolution@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@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@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


(Xiaodi Wu) #14

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.

Another benefit is that the problem you're currently having with recursion
goes away: from outside the type, you merely need to check if conformance
is declared.

Explicit with no special syntactic marker is definitely the way to go. It
would work just like Codable is slated to.

Right. I think we've got broad agreement (woohoo!) that this is the sweet
spot.

With such a scheme, consideration can be made to accommodating classes too.

I would think only final classes could participate in this, since a
subclassable class would need to allow subclasses to override equality, and
you can't override a static `==` operator method.

I work so rarely with classes that I'm embarrassed to have to ask this
question: can classes not satisfy Equatable with a `public class func ==`?

(My time is not unlimited right now, but I'd be willing to help with either

···

On Fri, May 5, 2017 at 12:41 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

On May 4, 2017, at 3:01 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:
the proposal or its implementation. This would be a great thing to get into
Swift 4.)


(Xiaodi Wu) #15

I see. You're not suggesting magic.

The problem stands that the design of Equatable explicitly encourages the
distinction between identity and equality (it even says: "equality is
separate from identity"). It follows that we should *not* provide a default
implementation that forwards one to the other; if someone determines that
this is right for their particular class, then they can trivially write it
themselves.

This goes back to the very high bar for inclusion of something in the
standard library. An additional protocol like this needs to hold its own
weight, encourage rather than discourage patterns that we aim to promote,
help avoid rather than promote misuse, be commonly useful, and be difficult
to write on one's own--among other criteria outlined by Ben Cohen. For many
of these criteria, I think your proposed protocol does not pass the bar.

···

On Fri, May 5, 2017 at 00:06 Charlie Monroe <charlie@charliemonroe.net> wrote:

On May 5, 2017, at 6:58 AM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

As the documentation for Equatable discusses, the goal is to distinguish
"equality" (==) from "identity" (===). If I understand it correctly, the
goal is to *discourage* mixing the two concepts.

Moreover, while writing a memberwise comparison is tedious and writing a
memberwise hash is even error-prone, writing "return lhs === rhs" is both
straightforward and impossible to mess up, so having special magic for that
use case is much harder to justify.

There doesn't need to be any magic - why would there need to be?

public protocol PointerEquatable: AnyObject, Equatable, Hashable {

public static func ==(lhs: Self, rhs: Self) -> Bool {
return lhs === rhs
}

public var hashValue: Int {
return ObjectIdentifier(self).hashValue
}

}

I'm not saying it's super hard but while we're at it, we might as well
include something like this in case identity is enough for equality, in
such case

class Foo: PointerEquatable { }

is enough for the class to be hashable and equatable. It's all opt-in,
there's no magic - I don't quite see the downside to it.

On Thu, May 4, 2017 at 23:45 Charlie Monroe via swift-evolution < > swift-evolution@swift.org> wrote:

I'm also leaning towards this being opt-in and the generation could be
triggered by having AutoEquatable and AutoHashable protocols.

Any chance for this proposal to be extended by adding "PointerEquatable"
for classes? In many cases, pointer equality is just enough and having the
class equatable by pointer allows e.g. better array inter-op (e.g. removing
an object doesn't require getting an index first)...

On May 4, 2017, at 10:37 PM, Tony Allevato via swift-evolution < >> swift-evolution@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.

† We intentionally leave the exact definition of the hash function
unspecified here. A multiplicative hash function with good distribution is
the likely candidate, but we do not rule out other possibilities. Users
should not depend on the nature of the generated implementation or rely on
particular outputs; we reserve the right to change it in the future.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#overriding-derived-conformances>Overriding
derived conformances

Any user-provided implementations of == or hashValue will override the
default implementations that would be provided by the compiler. This is
already the case possible today with raw-value enums so the same behavior
should be extended to other value types that are made to implicitly conform
to these protocols.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#open-questions>Open
questions
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#omission-of-fields-from-generated-computations>Omission
of fields from generated computations

Some commenters have expressed a desire to tag certain properties of a
struct from being included in automatically generated equality tests or
hash value computations. This could be valuable, for example, if a property
is merely used as an internal cache and does not actually contribute to the
"value" of the instance. Under the rules above, if this cached value was
equatable, a user would have to override == and hashValue and provide
their own implementations to ignore it.

<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#explicit-or-implicit-derivation>Explicit
or implicit derivation

As with raw-value enums today, should the derived conformance be
completely implicit, or should users have to explicitly list conformance
with


(Andrew Bennett) #16

That's correct, consistent with Encoding/Decoding (SE-0166
<https://github.com/apple/swift-evolution/blob/master/proposals/0166-swift-archival-serialization.md>)
it is sufficient to just do this:

struct MyType: Hashable {

  var foo: Int

  var bar: Float

}

Now MyType should get a generated implementation because each member is
also Hashable.

There's more details in the proposal near:

···

An enum T that derives Equatable will receive a compiler-generated
implementation of

On Fri, May 5, 2017 at 8:15 AM, Xiaodi Wu <xiaodi.wu@gmail.com> 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@apple.com> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution < >> swift-evolution@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@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@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.


#17

Currently:

class C: Equatable {
    class func == (lhs: C, rhs: C) -> Bool {
        return lhs === rhs
    }
}

Yields an error, “Operator '==' declared in non-final class 'C' must be
'final'”.

Nevin

···

On Fri, May 5, 2017 at 1:47 AM, Xiaodi Wu via swift-evolution < swift-evolution@swift.org> wrote:

On Fri, May 5, 2017 at 12:41 AM, Brent Royal-Gordon < > brent@architechies.com> wrote:

I would think only final classes could participate in this, since a
subclassable class would need to allow subclasses to override equality, and
you can't override a static `==` operator method.

I work so rarely with classes that I'm embarrassed to have to ask this
question: can classes not satisfy Equatable with a `public class func ==`?


(Michael Ilseman) #18

If an extension on your type declares a hashValue property, what should be the semantics? Is that an error (conflicts with default provided one), or is that one used?

···

On May 4, 2017, at 3:20 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org> wrote:

That's correct, consistent with Encoding/Decoding (SE-0166 <https://github.com/apple/swift-evolution/blob/master/proposals/0166-swift-archival-serialization.md>) it is sufficient to just do this:

struct MyType: Hashable {
  var foo: Int
  var bar: Float
}

Now MyType should get a generated implementation because each member is also Hashable.

There's more details in the proposal near:
An enum T that derives Equatable will receive a compiler-generated implementation of

On Fri, May 5, 2017 at 8:15 AM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> 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@apple.com <mailto:rjmccall@apple.com>> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 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 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.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Tony Allevato) #19

Thanks for your feedback, everybody!

I've updated the gist
<https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad> to
reflect what seems to be a consensus here:

* Derived conformances are now opt-in (this makes the recursive case *much*
cleaner, and the complexity involved in that section has been completely
removed)
* Classes are supported now as well

Please take a look at the updated version and let me know if there are any
concerns! If folks like it, I'll prepare a pull request.

···

On Fri, May 5, 2017 at 8:16 AM Nevin Brackett-Rozinsky via swift-evolution < swift-evolution@swift.org> wrote:

On Fri, May 5, 2017 at 1:47 AM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

On Fri, May 5, 2017 at 12:41 AM, Brent Royal-Gordon < >> brent@architechies.com> wrote:

I would think only final classes could participate in this, since a
subclassable class would need to allow subclasses to override equality, and
you can't override a static `==` operator method.

I work so rarely with classes that I'm embarrassed to have to ask this
question: can classes not satisfy Equatable with a `public class func ==`?

Currently:

class C: Equatable {
    class func == (lhs: C, rhs: C) -> Bool {
        return lhs === rhs
    }
}

Yields an error, “Operator '==' declared in non-final class 'C' must be
'final'”.

Nevin
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Matthew Johnson) #20

If an extension on your type declares a hashValue property, what should be the semantics? Is that an error (conflicts with default provided one), or is that one used?

How does Codable handle the equivalent question?

···

On May 8, 2017, at 3:17 PM, Michael Ilseman via swift-evolution <swift-evolution@swift.org> wrote:

On May 4, 2017, at 3:20 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

That's correct, consistent with Encoding/Decoding (SE-0166 <https://github.com/apple/swift-evolution/blob/master/proposals/0166-swift-archival-serialization.md>) it is sufficient to just do this:

struct MyType: Hashable {
  var foo: Int
  var bar: Float
}

Now MyType should get a generated implementation because each member is also Hashable.

There's more details in the proposal near:
An enum T that derives Equatable will receive a compiler-generated implementation of

On Fri, May 5, 2017 at 8:15 AM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> 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@apple.com <mailto:rjmccall@apple.com>> wrote:

On May 4, 2017, at 6:10 PM, Andrew Bennett via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@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 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 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.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution