Dynamic equality checking, and Equatable

equality
reflection
(Tanner Bennett) #1

Background

Swift's Equatable is defined like this:

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

Note that the arguments for == are defined as Self rather than Equatable. This has some implications and benefits:

  1. The arguments must be the same type at the call site.
  2. Because of #1, the function is generic in a way; each type gets its own implementation instead of one shared implementation that would have to unbox arguments.
  3. Because of #2, synthesized conformance to Equatable is fast. Boxing values carries overhead, and since the argument types are known at the call site, Equatable doesn't have to do any boxing.

However, there are some drawbacks:

  1. The arguments must be the same type.
  2. By implication, the arguments must be known to be the same type.
  3. The use of Self as in Equatable's definition restricts how Equatable can be used. You cannot declare collections or variables as a protocol type, like you can in Objective-C.

For example, #3 above makes any code similar to the following impossible:

let a: Equatable = ...
let b: Equatable = ...
a == b

As another example, by extrapolation, you cannot compare collections of Equatable either, unless they can be deduced to be the same type, such as within a generic function with the following signature:

func checkEqualArrays<T: Equatable>(a: [T], b: [T]) -> Bool

// This compiles
checkEqualArrays(a: [1, 2, 3], b: [1, 2, 5])
// This does not:
//    "Protocol type 'Any' cannot conform to 'Equatable'
//    because only concrete types can conform to protocols"
checkEqualArrays(a: [1, 2, 3], b: ["x", "y", "z"])

Going further down the rabbit hole, you cannot get around this by just adding an additional generic argument. This would allow the above code to compile, but the implementation of checkEqualArrays will not:

func checkEqualArrays<T: Equatable, U: Equatable>(a: [T], b: [U]) -> Bool {
    // Binary operator '==' cannot be applied
    // to operands of type '[T]' and '[U]'
    return a == b
}

Manual type-erasure and AnyHashable

If you've ever been to this dark place, as I'm sure many of you have, like me, you found yourself frustrated and annoyed. Without any other options, you turned to some form of type-erasure. Type-erasure is a workaround of sorts, but it's absolutely something that should be avoided in these instances. AnyHashable is an example of this if you've ever used it: it allows you to compare two Hashables for equality without ensuring they have the same concrete type at compile-time:

let a = AnyHashable(5)
let b = AnyHashable("x")
a == b // false

AnyHashable goes through a lot of boilerplate and uses what little reflection Swift currently offers to accomplish this. Unfortunately it doesn't alleviate the biggest problem I have with Equatable (and Hashable, by extension), which is that you can't declare variables or collections to store them directly, like you can in Objective-C.

Example: JSON objects and Any

Many APIs vend Any, such as JSONSerialization's .jsonObject(_:_:) methods. For testing purposes, you may want to compare the output of these methods to one another. You'll quickly find you can't:

let data: Data = ...
let json = (try JSONSerialization.jsonObject(with: data, options: [])) as! [String: Any]

XCTAssertEqual(json, otherJSON) // won't work

You might think you can get around this by making your own special protocol to replace the Any in that expression:

public protocol JSONValue: Equatable { }

extension Array : JSONValue where Element: JSONValue { }
extension Dictionary : JSONValue where Value: JSONValue { }
extension String : JSONValue { }
extension Date : JSONValue { }
extension Int : JSONValue { }
extension Bool : JSONValue { }
extension Double : JSONValue { }
...
extension NSNull : JSONValue { }

...
let json = (try JSONSerialization.jsonObject(with: data, options: [])) as! [String: JSONValue]

That last line sadly won't compile because of the Self requirements of Equatable. Type-erasure by hand could help here, maybe, but it's a very hacky solution to something the language itself should support.

Informal Pitch: OpaqueEquatable (or something similar)

Enter OpaqueEquatable. It would be a new protocol whose operator would accept boxed parameters instead of Self restricted parameters (hence the 'Opaque'). At runtime, the parameters would be checked first for type equality, then actual equality. The implementation might resemble this pseudocode:

protocol OpaqueEquatable {
    static func == (lhs: OpaqueEquatable, rhs: OpaqueEquatable) -> Bool
}

extension OpaqueEquatable {
    static func == (lhs: OpaqueEquatable, rhs: OpaqueEquatable) -> Bool {
        if type(of: lhs) == type(of: rhs) {
            // Get method reference to what is currently
            // the synthesized Equatable implementation
            let isEqual: (?, ?) -> Bool = type(of: lhs).==
            return isEqual(lhs, rhs)
        }
        
        return false
    }
}

Quick note: a definition like this isn't actually possible to use, because nothing can conform to it without giving this error: Member operator '==' must have at least one argument of type 'T' where T is the conforming type. I will ignore this for now though.

Ideally, everything—somehow including Any—would conform to this protocol, or at least be able to conform to it by opting-in within your own project:

extension Any: OpaqueEquatable { }

It might also make sense for one of OpaqueEquatable and Equatable to conform to the other, but I'm not sure which. I'll leave that up to discussion below, as I'm not sure what the benefits and consequences of OpaqueEquatable: Equatable vs Equatable: OpaqueEquatable are, or which one should be the default to make APIs as easy to use while still remaining performant.

With OpaqueEquatable, the following should be possible:

public protocol JSONValue: OpaqueEquatable { }

extension Array : JSONValue where Element: JSONValue { }
extension Dictionary : JSONValue where Value: JSONValue { }
extension String : JSONValue { }
etc ...

...
// OK
let json = (try JSONSerialization.jsonObject(with: data, options: [])) as! [String: JSONValue]
// OK
XCTAssertEqual(json, otherJSON)

Edit: as @anandabits mentioned, this doesn't necessarily have to be a protocol. Anything with the semantics of a top-level function like isEqual(_ lhs: Any, _ rhs: Any) -> Bool or better would be suitable.

Edge cases

Any includes everything, even functions and closures. As long as the behavior is documented, I think any of these would be fine since it rarely makes sense to compare closures anyway:

  • Throw a runtime error when comparing functions or closures
  • Allow functions/methods to be compared, but not closures
  • Allow functions/methods and closures to be compared, where the same closure source-declaration is always equal to itself, regardless of captured variables

What are your thoughts and concerns? Would you find this useful or not?

(Matthew Johnson) #2

I agree that dynamic equality checking is something that would be useful to support.

We don't need to introduce a protocol though. It's possible to implement an API that takes two values of type Any, returning true when both values are of the same type and that type implements Equatable or false otherwise. The implementation requires some black magic but users don't need to worry about that.

4 Likes
Adding a polymorphic Equatable?
(Tanner Bennett) #3

Anything that simple is a win in my book. I thought a protocol might be more ergonomic though, since Any includes functions and closures, and we might somehow be able to exclude those from being used at compile time if we used a protocol with some compiler magic instead of relying on Any.

Then again, I can imagine scenarios where I might find it useful to compare functions. I've edited my post near the end to bring up this edge case.

(👑🦆) #4

This topic has come up many, many times before. Here's one which shows some alternatives. I can't remember if one of the previous discussions includes an "official" answer for why Equatable is this way, but I assume one of them does. It's certainly a well-known limitation.

What you propose (OpaqueEquatable) is also a kind of type erasure. I'm not sure what you mean by "by hand", but you can largely automate it with a protocol requirement + default implementation (see below).

If it's just for testing, you could test against a known deserialised copy or serialise it, then compare the data/string versions.

Anyway, here's a modified version of your example which includes a simple kind of "polymorphic" equatable. If it's just for testing, you can modify the #if true lines to something meaningful (I don't think we have a compile-time conditional for @testable builds, but that might be worth adding...):

protocol JSONValue {
  #if true
  func isEqual(to: JSONValue) -> Bool
  #endif
}
extension Array: JSONValue where Element: JSONValue {}
extension Dictionary: JSONValue where Value: JSONValue {}
extension String: JSONValue {}
extension Date: JSONValue {}
extension Int: JSONValue {}
extension Bool: JSONValue {}
extension Double: JSONValue {}
extension NSNull: JSONValue {}
extension AnyHashable: JSONValue {}
extension NSArray: JSONValue {}
extension NSDictionary: JSONValue {}

#if true
extension JSONValue where Self: Equatable {
  func isEqual(to: JSONValue) -> Bool {
    guard let other = to as? Self else { return false }
    return self == other
  }
}

// Might be worth duplicating these for NSArray/NSDictionary as well.
// I didn't think through all the edge-cases...
extension Array where Element: JSONValue {
  func isEqual(to: JSONValue) -> Bool {
    guard let other = to as? Array<JSONValue>,
          count == other.count else { return false }
    return (0..<count).allSatisfy { self[$0].isEqual(to: other[$0]) }
  }
}
extension Dictionary where Value: JSONValue {
  func isEqual(to: JSONValue) -> Bool {
    guard let other = to as? Dictionary<Key, JSONValue>,
          count == other.count else { return false }
    return allSatisfy { (k, v) in other[k].map { v.isEqual(to: $0) } ?? false }
  }
}
#endif

A quick test:

let testJSON =
    """
    {
      "test": [ 1, 2, 3 ],
      "another": "99"
    }
    """
    let data = testJSON.data(using: .utf8)!

    let obj = try! JSONSerialization.jsonObject(with: data, options: [])
	let jsObj = obj as! JSONValue
    assert(jsObj.isEqual(to: jsObj))

    let obj2 = try! JSONSerialization.jsonObject(with: data, options: [])
    let jsObj2 = obj2 as! JSONValue
    assert(jsObj.isEqual(to: jsObj2))

    let testJSON2 =
    """
    {
      "test": [ 4, 5, 6 ],
      "another": "66"
    }
    """
    let data2 = testJSON2.data(using: .utf8)!
    let obj3 = try! JSONSerialization.jsonObject(with: data2, options: [])
    let jsObj3 = obj3 as! JSONValue
    assert(jsObj.isEqual(to: jsObj3) == false)
(Tanner Bennett) #5

What you propose (OpaqueEquatable) is also a kind of type erasure.

Ah, yes. I almost referred to it as such in the post because that's what I thought too, but didn't want to confuse anyone if that wasn't quite right.

I'm not sure what you mean by "by hand"

As opposed to not needing to type-erase things at all to compare them when the compiler doesn't enforce same-type comparison, like so:

let a: OpaqueEquatable = 5
let b: OpaqueEquatable = 5
a == b

If it's just for testing

It's not just for testing, this was just an example. There are real-world use-cases for this that shouldn't require workarounds.

Your type-erasing example is clever, but, I did address it after my example when I said "Type-erasure by hand could help here, maybe, but it's a very hacky solution to something the language itself should support." And I think that holds true here. You need to implement massive boilerplate for every collection you might want to compare, and you have to do it all again every project you wish to do this in.

I don't think we should be recommending this sort of thing; we should focus on patching this hole in the language.

(Matthew Johnson) #6

As I said previously, this is possible to implement in Swift today. If there is enough support for the idea it wouldn’t be too difficult to get a proposal put together with an implementation that introduces an API for dynamically comparing two unconstrained existential values.

Instead of focusing on mechanics, I recommend focusing on identifying the exact API you want to have available. There are several reasonable variations on semantics for the comparison. For example:

/// - returns: `true` when both values are of the same type that conforms to `Equatable` and compare equal.  
///            `false` if that comparison fails, and `nil` if the values are of different or non-`Equatable` types.
func areEqual(_ lhs: Any, _ rhs: any) -> Bool?

/// - returns: `true` when both values are of the same type that conforms to `Equatable` and compare equal.  
///            `false` otherwise.
func areKnownEqual(_ lhs: Any, _ rhs: any) -> Bool

/// - returns: `true` when both values are of different types or of the same type that conforms 
///             to `Equatable` and compare not equal.  `false` otherwise.
func areKnownDifferent(_ lhs: Any, _ rhs: any) -> Bool

What are the desired semantics?

(Rex) #7

Don't want to dismiss this idea outright but I think there need to be stronger use cases. Your first example makes me wonder why you're comparing those two arrays to begin with. Your second can be solved using algebraic data types or at a minimum can use what's stated here Adding a polymorphic Equatable?

Explicitly, your JSON example can be solved by relying instead on algebraic data types like many open source JSON libraries already offer. This blog post looks like it gives an example https://medium.com/grand-parade/parsing-fields-in-codable-structs-that-can-be-of-any-json-type-e0283d5edb

Edit for clarity: Conforming enum JSONValue: Equality from that blog example should work since all associated values are Equatable.

1 Like