[swift-evolution] Synthesizing Equatable, Hashable, and Comparable for tuple types

[Joe Groff]

> On Nov 28, 2017, at 8:33 PM, Tony Allevato <tony.allevato at gmail.com> wrote:
> 
> On Tue, Nov 28, 2017 at 11:23 AM Kelvin Ma via swift-evolution <swift-evolution at swift.org> wrote:
> On Tue, Nov 28, 2017 at 12:59 PM, Joe Groff via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> > On Nov 28, 2017, at 10:52 AM, Vladimir.S <svabox at gmail.com> wrote:
> >
> > On 27.11.2017 20:28, Joe Groff via swift-evolution wrote:
> >>> On Nov 20, 2017, at 5:43 PM, Chris Lattner via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> >>>
> >>>
> >>>> On Nov 20, 2017, at 5:39 PM, Kelvin Ma via swift-evolution <swift-evolution at swift.org <mailto:swift-evolution at swift.org>> wrote:
> >>>>
> >>>> when SE-185 <https://github.com/apple/swift-evolution/blob/master/proposals/0185-synthesize-equatable-hashable.md> went through swift evolution, it was agreed that the next logical step <https://www.mail-archive.com/swift-evolution@swift.org/msg26162.html> is synthesizing these conformances for tuple types, though it was left out of the original proposal to avoid mission creep. I think now is the time to start thinking about this. i’m also tacking on Comparable to the other two protocols because there is precedent in the language from SE-15 <https://github.com/apple/swift-evolution/blob/master/proposals/0015-tuple-comparison-operators.md> that tuple comparison is something that makes sense to write.
> >>>>
> >>>> EHC conformance is even more important for tuples than it is for structs because tuples effectively have no workaround whereas in structs, you could just manually implement the conformance.
> >>>
> >>> In my opinion, you’re approaching this from the wrong direction.  The fundamental problem here is that tuples can’t conform to a protocol.  If they could, synthesizing these conformances would be straight-forward.
> >> It would be a tractable intermediate problem to introduce built-in conformances for tuples (and perhaps metatypes) to Equatable/Hashable/Comparable without breaching the more general topic of allowing these types to have general protocol conformances. I think that would cover the highest-value use cases.
> >
> > So, shouldn't we do this first step ASAP and then design a good common solution to allow tuples/metatypes/funcs to confirm to custom protocols in some next version of Swift?
> > I really believe this is the good practical decision and will be supported by community if such proposal will be on the table.
> > Is there any drawback in such step?
> 
> The expected behavior of tuple Equatable/Hashable/Comparable seems obvious to me (though I could well be missing something), and any behavior we hardcode should be naturally replaceable by a generalized conformance mechanism, so it's primarily a "small matter of implementation". There would be some implementation cost to managing the special case in the compiler and runtime; the tradeoff seems worth it to me in this case, but others might reasonably disagree. Not speaking for the entire core team, I would personally support considering a proposal and implementation for builtin tuple Equatable/Hashable/Comparable conformance.
> 
> -Joe
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> i wouldn’t know how to implement this but i could write up this proposal in a few days 
> 
> I've been looking the past couple days at how to generalize the protocol conformance machinery to support structural types (even if we don't support arbitrary conformance syntactically, at least being able to hardcode the ones we want to synthesize initially). My free time isn't exactly plentiful, but I'm hoping to make some decent progress, so I'm happy to help where I can on this since it's a natural follow-up to my other Equatable/Hashable work!

If I were going to look into implementing this, my first-pass approach would be something like this. It's not necessarily the best or most optimal approach, but it might get you started:

- Introduce a new ProtocolConformance subclass for tuple conformances, that collects the required protocol conformances from all the elements
- Enhance the AST and type checker conformance lookup machinery, such as lookupConformance and conformsToProtocol, to work with tuples, by returning TupleProtocolConformances where applicable
- In IRGen, lower a reference to a TupleProtocolConformance into a runtime call that grabs the conformance for a tuple type to a given protocol with the given element conformances
- In the runtime, implement these runtime calls similar to how we generate structural type metadata, with a uniquing cache that instantiates a unique witness table for each unique (type, element conformances...) key. It should be possible to implement the witness methods themselves in C++ in a way that works dynamically with any tuple type.

There might be follow-up work we'd want to do to be able to concretize the builtin witnesses in SIL for optimization purposes, but the above should get something working.

-Joe