[swift-evolution] Pitch: Automatically deriving Equatable/Hashable for more value types
Xiaodi Wu
xiaodi.wu at gmail.com
Thu May 4 23:58:35 CDT 2017
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 at 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 at swift.org> wrote:
>
> Hi all,
>
> A conversation on Twitter last night brought up some interest in this
> feature and I was encouraged to revive this proposal.
>
> Jordan Rose mentioned
> <https://twitter.com/UINT_MIN/status/859922619578986496> on Twitter that
> it could possibly make it in by the Swift 4 deadline if others
> contributed—I have a WIP branch (albeit not currently working because I
> rebased after a couple months of it being idle) that does the work for
> enums but I got stuck on the mutually recursive cases. If this got
> approved, I'd love to collaborate with other interested folks to finish up
> the implementation.
>
> Link: https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad
>
>
> Deriving Equatable and Hashable for value types
>
> - Proposal: SE-0000
> <https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md>
> - Author(s): Tony Allevato <https://github.com/allevato>
> - Status: Awaiting review
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#rationale>
> - Review manager: TBD
>
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#introduction>
> Introduction
>
> Value types are prevalent throughout the Swift language, and we encourage
> developers to think in those terms when writing their own types.
> Frequently, developers have to write large amounts of boilerplate code to
> support equatability and hashability of value types. This proposal offers a
> way for the compiler to automatically derive conformance to Equatable and
> Hashable to reduce this boilerplate, in a subset of scenarios where
> generating the correct implementation is known to be possible.
>
> Swift-evolution thread: Universal Equatability, Hashability, and
> Comparability
> <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8919>
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#motivation>
> Motivation
>
> Building robust value types in Swift can involve writing significant
> boilerplate code to support hashability and equatability. Equality is
> pervasive across many value types, and for each one users must implement the
> == operator such that it performs a fairly rote memberwise equality
> test. As an example, an equality test for a struct looks fairly
> uninteresting:
>
> struct Foo: Equatable {
> static func == (lhs: Foo, rhs: Foo) -> Bool {
> return lhs.property1 == rhs.property1 &&
> lhs.property2 == rhs.property2 &&
> lhs.property3 == rhs.property3 &&
> ...
> }
> }
>
> What's worse is that this operator must be updated if any properties are
> added, removed, or changed, and since it must be manually written, it's
> possible to get it wrong, either by omission or typographical error.
>
> Likewise, hashability is necessary when one wishes to store a value type
> in a Set or use one as a multi-valued Dictionary key. Writing
> high-quality, well-distributed hash functions is not trivial so developers
> may not put a great deal of thought into them – especially as the number of
> properties increases – not realizing that their performance could
> potentially suffer as a result. And as with equality, writing it manually
> means there is the potential to get it wrong.
>
> In particular, the code that must be written to implement equality for
> enums is quite verbose:
>
> enum Token: Equatable {
> case string(String)
> case number(Int)
> case lparen
> case rparen
>
> static func == (lhs: Token, rhs: Token) -> Bool {
> switch (lhs, rhs) {
> case (.string(let lhsString), .string(let rhsString)):
> return lhsString == rhsString
> case (.number(let lhsNumber), .number(let lhsNumber)):
> return lhsNumber == rhsNumber
> case (.lparen, .lparen), (.rparen, .rparen):
> return true
> default:
> return false
> }
> }
> }
>
> Crafting a high-quality hash function for this enum would be similarly
> inconvenient to write.
>
> Swift already derives Equatable and Hashable conformance for a small
> subset of enums: those for which the cases have no associated values
> (including enums with raw types). Two instances of such an enum are equal
> if they are the same case, and an instance's hash value is its ordinal:
>
> enum Foo {
> case zero, one, two
> }
> let x = (Foo.one == Foo.two) // evaluates to falselet y = Foo.one.hashValue // evaluates to 1
>
> Likewise, conformance to RawRepresentable is automatically derived for
> enums with a raw type. Since there is precedent for derived conformances in
> Swift, we propose extending this support to more value types.
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#proposed-solution>Proposed
> solution
>
> In general, we propose that value types derive conformance to Equatable/
> Hashable if all of its members are Equatable/Hashable. We describe the
> specific conditions under which these conformances are derived below,
> followed by the details of how the conformance requirements are implemented.
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#protocol-derivability-conditions>Protocol
> derivability conditions
>
> For brevity, let P represent either the protocol Equatable or Hashable in
> the descriptions below.
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#derived-conformances-for-enums>Derived
> conformances for enums
>
> For an enum, derivability of P is based on the conformances of its cases'
> associated values. Computed properties are not considered.
>
> The following rules determine whether conformance to P can be derived for
> an enum:
>
> -
>
> An enum with no cases does not derive conformance to P, since it is
> not possible to create instances of such types.
> -
>
> An enum with one or more cases derives conformance to P if all of the
> associated values of all of its cases conform to P (either explicitly
> or derived).
>
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#derived-conformances-for-structs>Derived
> conformances for structs
>
> For a struct, derivability of P is based on the conformances of its
> stored instance properties *only*. Neither static properties nor computed
> instance properties (those with custom getters) are considered.
>
> The following rules determine whether conformance to P can be derived for
> a struct:
>
> -
>
> A struct with *no* stored properties does *not* derive conformance to P.
> (Even though it is vacuously true that all instances of a struct with
> no stored properties could be considered equal and hash to the same value,
> the reality is that such structs are more often used for
> grouping/nesting of other entities and not for their singular value, and we
> don't consider it worthwhile to generate extra code in this case.)
> -
>
> A struct with one or more stored properties derives conformance to P if
> all if the types of all of its stored properties conform to P (either
> explicitly or derived).
>
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#considerations-for-recursive-types>Considerations
> for recursive types
>
> For brevity in the discussion below, the term *members* refers only to
> those members that are checked for deriving conformances: *stored
> properties* for structs and *associated values* for enums.
>
> Recursive value types require a bit more care when determining whether a
> conformance can be derived. Consider the following enum with an indirect
> case:
>
> enum TreeNode {
> case empty
> case leaf(value: Int)
> case internal(left: TreeNode, right: TreeNode)
> }
>
> When examining the internal case, an application of the rules above
> implies that "TreeNode derives P if TreeNode conforms to P"—a recursive
> condition. In this situation, we note that any instance of this type—or of
> any recursive type—forms a finite tree structure because the recursion must
> be terminated eventually by using one of the other base cases. Therefore,
> without changing the outcome, we can assume for the purposes of
> determining whether T derives P that any members of type T already
> conform to P. If any members of different types prohibit deriving P, then
> we know that the whole type cannot derive it; likewise, if all of the other
> members permit deriving P, then we know that T can derive it by
> recursively applying the derived operation.
>
> This property can be extended to *mutually* recursive types as well.
> Consider this contrived example:
>
> enum A {
> case value(Int)
> case b(B)
> }
> enum B {
> case value(String)
> case c(C)
> }
> enum C {
> case value(Double)
> case a(A)
> }
>
> The rules state that—ignoring the trivial cases—"A derives P if B conforms
> to P," and "B derives P if Cconforms to P," and "C derives P if A conforms
> to P." The same observation about recursion and the finiteness of
> instances from above holds here, so we can generalize the rule above as
> follows:
>
> A type T can derive P if all members of T conform to P or are of types
> found in cycles that lead back to Tsuch that the members of those other
> types along the cycle also all conform to P or are themselves along such
> a cycle.
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#other-considerations>Other
> considerations
>
> When conditional conformances are supported in Swift, generic types should
> conditionally derive Equatable and Hashable for type argument
> substitutions where the rules above are satisfied.
>
> A notable side effect of this is that Optional<Wrapped> would derive
> Equatable and Hashable conformance when Wrapped conforms to those
> protocols, because it is an enum that would satisfy the rules described
> above. Its implementation would not need to be in the standard library (but
> there is also nothing preventing it from being there).
>
> Conditional conformances will also significantly improve derivability
> coverage over other payload/member types. For example, consider a struct containing
> a stored property that is an array of Equatable types:
>
> struct Foo {
> var values: [String]
> }
>
> Today, Array<String> does not conform to Equatable, so its presence would
> prohibit Foo from deriving Equatable. However, once Swift can express the
> conformance Array<Element>: Equatable where Element: Equatable, Foo would
> automatically derive Equatable as well. This makes derived conformances
> significantly more powerful.
>
> <https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad#implementation-details>Implementation
> details
>
> An enum T that derives Equatable will receive a compiler-generated
> implementation of static == (lhs: T, rhs: T) -> Bool that returns true if
> and only if lhs and rhs are the same case and have payloads that are
> memberwise-equal.
>
> An enum T that derives Hashable will receive a compiler-generated
> implementation of var hashValue: Int { get }that uses an unspecified hash
> function† to compute the hash value by incorporating the case's ordinal
> (i.e., definition order) followed by the hash values of its associated
> values as its terms, also in definition order.
>
> A struct T that derives Equatable will receive a compiler-generated
> implementation of static == (lhs: T, rhs: T) -> Bool that returns true if
> and only if lhs.x == rhs.x for all stored properties in T.
>
> A struct T that derives Hashable will receive a compiler-generated
> implementation of var hashValue: Int { get } that uses an unspecified
> hash function† to compute the hash value by incorporating the hash values
> of the fields as its terms, in definition order.
>
> † 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 at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170505/8ba7c2b9/attachment.html>
More information about the swift-evolution
mailing list