Hacking Equatable conformance on Void

Every time the issue comes up of conforming Void to Equatable — or even the broader suggestion of synthesising conformance for Equatable for arbitrary tuples where each element is Equatable — the discussion often results in a rabbit hole like this:

  • Making structural types conform to protocols
  • Tuples (A, B) as sugar for e.g Tuple<A, B>
  • Variadic generics

… and the whole thing comes to a stop as the issue becomes too large to tackle.

I wonder: Is is possible to "hoist" the logic concerning equality up the stack somehow, and as a special case, allowing Void to be treated as an Equatable in generic code? Without going all the way to The Perfect Solution™?

Is it possible to somehow do this in small additive steps:

  • First allow Void to be equatable
  • Second, allowing element-wise equatable tuples to be equatable
  • ...
  • ...
  • Full-fledged variadic generics, general protocol-conformance for structural types, etc

… where each new iteration perhaps can reimplement the former in terms of the latter?

Now that we have Result and Combine's Publisher etc in the mainstream, it is a real shame that we always have to special-case generic code over these types when they wrap Void.

3 Likes

I think it makes perfect sense for us to provide special-case conformances of tuples and other structural types to common protocols, instead of holding out for more complicated features.

10 Likes

What set of conformances do you have in mind? I would love to see at minimum Hashable and Codable. I have used Unit and Pair in my own code to work around the conformance limitation and these conformances would cover the vast majority of cases. IIRC all of the rest are conformances to my own protocols.

The ones that seem obvious to me are:

  • Tuples of Equatable, Hashable, Comparable, and Codable should conform to the protocol with elementwise implementations (and () should conform as the degenerate case of each)
  • Metatypes should be Hashable by type equality
  • Existentials with an Equatable or Hashable constraint should be Equatable and/or Hashable by AnyHashable's implementation
14 Likes

That looks like a great list to me!

Can you elaborate on this? We don’t really have existentials of Equatable and Hashable today so I’m confused. FWIW, I have wanted AnyEquatable relatively often in use cases where I do not want to impose a Hashable constraint.

We ought to! At minimum, we could remove the restriction on existentials of Equatable, but I'd rather we allow existentials of all protocols.

1 Like

Agreed. I would be very happy to see this happen! :grinning: I thought maybe that was one of the more complicated features you referred to.

It’s not clear to me how Comparable would work here, but certainly Equatable, Hashable, and Codable should be straightforward. Nor has it ever been controversial, to my recollection—the limiting factor here has always been lack of an implementation.

Comparable should do lexicographical ordering, like the ad-hoc overloads of < on tuples do already.

11 Likes

I’m glad you think so. Although I kinda already thought you would. I’ve seen this issue come up several times over the years and it seems like a non-controversial issue that “everybody” wants.

But there’s no reason for me to formally pitch this without an implementation, and I’m at a loss. I have no idea where to start, or even how understand how the compiler code base is structured. It seems like an impossible job without a lot of hand holding.

You mention conforming tuples to Hashable, Comparable etc. But I ask again: Is the task at hand too big?

Would limiting the scope to allow Void to be equatable, and only that, be a good start? It requires no parsing of the tuple elements, I would presume. But somewhere something needs to special case trivial zero-element tuple and unconditionally answer true when asked. I have no idea where or what, though.

The implementation approach I would take might be something like this:

  • Introduce a new ProtocolConformance subclass in the compiler for BuiltinProtocolConformances to represent these conformances, and teach the various parts of the type checker that look up protocol conformances to know about these conformances.
  • Implement protocol witness tables in the Swift runtime. It should be possible in C++ to write implementations of these operations that would work for any tuple, metatype, and/or existential type.
  • Compile references to BuiltinProtocolConformances into references to these tables in the runtime.

And then for performance:

  • Teach the SIL specializer how to expand method references into BuiltinProtocolConformances for specific types, in order to allow optimization for concrete types.

Doing all of this just for Void might make laying the initial infrastructure easier. Once this is all done, I think it should be an incremental amount of additional work to generalize to all tuples, or to other kinds of structural types.

6 Likes

Oh yes please!

In a different thread, instead of making tuples conform to protocols, I'm wondering if it's possible to just have nominal types with tuple members pierce into the tuple (recursively for nested tuples).

Could it make sense to emit these builtin witness tables during SILGen for the Swift module? I see that self conformances are also emitted during this time too. This allows for the conformance descriptor to be emitted in swift5_proto section.

I ask because I've messed around with implementing it right in the runtime, and you can make the witness table, but the conformance descriptor class won't let you construct an instance of it, which leads me to believe that I'll have to make a dummy struct with the same layout? Anyways, in the conformance descriptor's type reference, would we have to add a new metadata option because tuples don't have context descriptors :stuck_out_tongue:

Maybe a more meta question: Do protocol witness tables need a conformance descriptor? Can they just include the witness?

It might be useful to teach the SIL optimizer how to generate witness tables for specific tuple conformances as a way of enabling specialization and devirtualization, but there isn't a canonical place to emit the witnesses like there are for protocol self-conformances, since tuples exist in every module.

The pair of (type metadata, conformance descriptor) is what is used to identify a unique protocol conformance within a process, so some sort of conformance descriptor is necessary. How are protocol self conformances represented currently? It'd be reasonable to introduce a new type reference format for structural types.