InlineArray should conform to Equatable and Hashable when Element does.
Motivation
Not having these conformances is pretty annoying.
Proposed solution
Add the missing conformances.
Detailed design
That's it. That's the whole design.
Ok, fine:
These conformances implement elementwise equality, not identity.
The element hashes are mixed in index order.
Equality is permitted but not required to early-out (i.e. the implementation does not guarantee that InlineArray.== is constant time, nor does it guarantee not to access any elements after the first mismatch).
Source compatibility
If you wrote your own extension to provide these conformances, you should be able to delete it with minimal fuss, unless you implemented wildly different semantics for some reason. That was a bad idea.
We are adding an Equatable conformance to another type. This slightly enlarges the set of candidates for expressions involving == or !=, and might result in needing to break up or disambiguate expressions that are right at the limit of typechecker performance today.
ABI compatibility
N/A
Implications on adoption
The actual protocol conformance implementations will back-deploy to the introduction of InlineArray, allowing users to declare their own retroactive conformance if needed.
Future directions
None worth mentioning.
Alternatives considered
Implement identity rather than elementwise equality. This is arguably also a valid choice, but it's neither interesting nor particularly useful.
To answer the inevitable Chesterton's Fence question: it didn't make sense to include these when InlineArray was first added to the stdlib, because we didn't have SE-0499 yet. Now we do, and we should add these.
It's reasonable to suggest that we should add more of the conformances unlocked by 499, but Equatable and Hashable are by far the most painful missing ones and I'd like to get them squared away.
Is there a reason an implementation would not want to short-circuit? Or is this meant mainly to speak to implementations for BitwiseCopyable elements that might operate on the raw memory (e.g., an InlineArray<N, UInt8> might end up looking at more bytes than strictly the ones it needs to because of how they get loaded into memory)?
Sure, someone trying to write elliptic curve primitives on a type backed by InlineArray probably wants a constant time comparison. We are not making that guarantee for this API (partially because it's hard to really deliver in almost any language other than assembly targeting a specific uArch, partially because other use cases do not want it).
In the other direction, yeah, if you have an InlineArray<16, UInt8> on arm64 or x86, we want to either load 64-bit words, xor pairs, and check for zero, or just use a SIMD comparison. Either one of those unconditionally loads all sixteen bytes.
Happily the trivialest implementation in the stdlib is: lhs.span._elementsEqual(to: rhs.span), which, while the codegen still isn't quite perfect, does achieve O(n).
Maybe not a very compelling reason not to short-circuit… but if InlineArray can deliver a Span in guaranteed constant time and that Span can deliver a constant-time check for identity then IIUC there can at least be a legit workaround for that with existing public APIs.
Is the question whether or not we should short-circuit in the negative direction? If two InlineArray values have a different count value we return false right away?
I remember experimenting with inline arrays before and being surprised why there were not (much or at all) faster compared to normal arrays. This behaviour explains why.
The beauty of the count being part of the type is that comparing two inline arrays will always have the same count, so this fast path is done at compile time
Are non-copyable element types supported? You should still spell out the actual extension declaration and where clause here.
If you mean that the witnesses are @_alwaysEmitIntoClient, that's insufficient. Witness tables don't backward deploy today, so use of these conformances in generic context would be limited to newer deployment targets.
The pitch says that retroactive conformances declared by users can depend on the witnesses from the standard library because those witnesses are back deployed. The witness tables for the canonical conformance shouldn't play a role in these retroactive conformances.
