SE-0494: Add `isIdentical(to:)` Methods for Quick Comparisons to Concrete Types

Evolution Proposal Reviews
123

Sure, you can correctly regard the function as never producing a false positive by this sort of tautological definition: are these the maximally useful semantics, and the most intuitive/straightforward formulation of those semantics, for the motivating problem?

1 Like
124

What about StaticString? It is not in the list of types in proposal.

I don’t know how exactly StaticString is created (and optimized), but it seems reasonable for 2 instances created by e.g. #fileID be identical if they are created in the same file.

1 Like
125

The thing is, for a thing that is almost solely designed for performance optimization, giving a name like isIdentical that looks so inline with a beginner's expectation of an equality check, is inevitably going to cause misuse. And the worst part is that in many cases it likely will work as an equality check, until it magically isn't, in a hard-to-reproduce way.

8 Likes
126

I think this is very real concern.

Naming is hard. Looks like we don't have a clear winner for the name:

Name Reasons against
isIdentical Not scary enough name, novices will confuse it with equality.
isKnownIdentical isKnownInterchangeable isKnownSubstitutable false is misleading: we DO know that the two are not identical, not that "we don't know".
isKnownEqual Counter examples: Array of non equatable is NOT equal (it's not equatable at all). Array of Double.nan is NOT equal.
isSubstitutable isInterchangeable "weaker semantic guarantee" than identity.
New Contenders
hasRepresentationKnownInterchangeable hasInterchangeableRepresentation
isSameRepresentation hasSameRepresentation
isInstanceIdentical hasIdenticalRepresentation hasSameIdentity

Edit: updated the table to include more variants.

1 Like
127

Some other variants:

isInstanceIdentical(to:)

hasIdenticalRepresentation(to:)

hasSameIdentity(as:)

128

We can’t design the language in such a way that all beginners will not misuse it. Doing the wrong things is part of learning experience. Beginners will definitely meet “out of bounds errors”, “unexpectedly found nil while unwrapping optional value“ and many other.
Beginners read official documentation (or its translated variant), study language in university or consume some other materials. I hardly imagine that while learning Swift they managed to completely skip == (never seeing it somewhere), and unexpectedly found `isIdentical`.

@tera has compared different terms above, we have not so much variants. Which one is the best from your point of view?

1 Like
129

That would be my preference as well. And it may be more discoverable with searches. i.e. if one is specifically trying to speed up ==, could a better name lead folks to find that new function more easily?

Couple other possibles: optimizedIsIdentical , optimizedIsEqual

130

I concur with @QuinceyMorris.

131

No, no, this is specifically not about "speeding up ==" Anything suggesting that would be a mistake. "if I could use an "optimised" equality test why would I ever want to use a "nonoptimised" one?". We should distance from Equatable as far as possible.

And the false of that would be misread as "is not trivially identical (but still is)".

2 Likes
132

There are some types where copying or moving a value doesn't guarantee that the new value is bitwise-identical, even ignoring padding bytes. For example, a type might have a custom "copy constructor" or "move constructor" (not currently possible in Swift, but possible with imported C++ types like std::string or std::vector). Additionally, a copy or move of a Swift function value might be a "thunk" of the original function value.[1] All of that basically means, if we ever feel the need to extend the isIdentical feature far enough, it might need to become even less deterministic; it might not even be possible to guarantee reflexivity.

I suppose if we ever extend the isIdentical feature to types containing weak references, that would be another source of nondeterminism.

With that in mind, I wonder if one of the difficulties of this proposal is a tension between generality and specificity. The proposal applies to concrete types like Array, where the semantics are relatively easy to specify, even applying to non-Equatable types. That lends itself to specific names, such as isIdentical (it also lends itself to APIs that expose even more implementation details, such as exposing identity). But the proposal also seeks to set a uniform standard for types in general, possibly extending into generic code in the future, which could include types where we aren't willing to make strong guarantees. That lends itself to general names that imply more undefined semantics, such as isKnownEqual.

  1. With types whose copies are never bitwise-identical, like std::vector, an isIdentical feature would probably not be useful. More problematic are types whose copies are sometimes bitwise-identical, such as std::string with the small-string optimization, and Swift function types. ↩︎

1 Like
133

Agreed. Though therein lies the problem with the proposed naming thus far.

Since the proposal outlines a special case that can be implemented to increase performance, I still content that a name describing the usage would be best.

1 Like
134

But really though… aren't we kind of "moving the goalposts" here? We are looking for some public API surface that returns some observable difference… but we then all of a sudden must enforce some arbitrary threshold past which an observable difference is no longer "tautological" and therefore a satisfactory API to disprove the existence of false negatives?

Suppose we weren't even talking about this proposal. Suppose we were just talking about classes today:

class C {
  let s: String
  
  init(_ s: String) {
    self.s = s
  }
  
  func isIdentical(to other: C) -> Bool {
    self === other
  }
}

let c1 = C("Hello, SE-0494!")
let c2 = c1
print(c2.isIdentical(to: c1)) // true
let s3 = C("Hello, SE-0494!")
print(s3.isIdentical(to: c2)) // false
print(s3.isIdentical(to: c1)) // false

This is almost identical to the previous example except we compare isIdentical on a class reference. But these references are the same values. There are no observable differences across any public API surface of these references except for the identity itself.

So we have a situation where all we as library maintainers can tell a product engineer is "these references are not identical because they have different identity". How is that not then tautological? How is that not just us saying "these references are not identical because these references are not identical"? How is that not then a "false negative" where we return false from isIdentical when two references share the same value in all observable public APIs?

This proposal will not expose identity directly. That is Bad Idea and has been discussed many times here before. But even if we did expose a "proxy identity" — the "raw guts" bit values of StringGuts — and then that was our API surface that returned some observable difference when isIdentical returns false… that wouldn't really be any different than us saying "these instances are not identical because they have different identity". Which is then not really any different than us saying "these instances are not identical because they are not identical".

Whether or not we expose the proxy identity or not… the isIdentical method can return false to indicate two instances are not identical. And the reason these instances are not identical is because we say so.

Either you're over-thinking this… or I'm under-thinking this. But somebody here seems to be mis-thinking this…

If the decision of LSG is that isIdentical is an unsound API because returning false from isIdentical implies two instances must have some observable change across some public API surface but we then go ahead and enforce some "threshold of tautology" and we then claim that some subset of the API surface cannot be an "observable change"… I'm not sure what more I can say to change your opinion about that. You are welcome to use your best judgement and present your opinion and LSG can use their best judgement and make their opinion and that can be the decision we move forward with.

135

This was discussed in the pitch thread:

This specific proposal we are reviewing today is focused on what we see as the most "high impact" concrete types from standard library that need isIdentical(to:). One major factor in that decision was that the concrete types in this proposal need private or internal state to return a meaningful result for isIdentical(to:). If a library maintainer outside of standard library can return a fast and accurate result for isIdentical(to:) with only public state… it's less of a reason for us to put it on our calendar right now as an implementation diff in standard library itself.

1 Like
136

Please let's focus here for a moment:

isKnownIdentical == false is misleading: we DO know that the two are not identical, not that "we don't know"

Correct. This is one of the many reasons I pushed back on that choice.

isKnownSubstitutable == false is misleading: we DO know that the two are not substitutable, not that "we don't know"

No. This is an incorrect statement. Whatever it is we choose to name this operation we are comparing a "proxy identity" internally in O(1) time. An important implication of those two proxy identities comparing as equal is that the concrete types must then be substitutable. But those two proxy identities not comparing as equal says nothing about whether or not the concrete types are substitutable. That's the whole point: returning a definitive yes-or-no answer to the "substitutability" question is O(n). Returning false to indicate "we don't know" is the price we pay to keep the operation O(1): we trade accuracy for speed.

isKnownInterchangeable == false is misleading: we DO know that the two are not interchangable, not that "we don't know"

Same as above.

For similar reasons to the previous comment isSubstitutable is also misleading: we would return false from isSubstitutable with the expectation that this can return false even if these concrete types are substitutable.

137

Supposing you declared it final class C—this is to allow us to gloss over some stuff—and supposing you proposed C.isIdentical(to:) as a concrete addition in this proposal, do you regard self === other as an appropriate implementation? How about self.s == other.s? How about self.s.isIdentical(to: other.s)? If more than one is appropriate, is one more ideal than another? And what do those answers tell you about the proposed semantics that you desire? What if C were instead a noncopyable struct?

138

I'm not totally sure I understand what this question is looking for… the === operator already is the "identical to" operator:

That definition and term of art has been shipping in Swift for ten plus years. Has this ever been controversial inside LSG?

I'm not totally sure I understand what this question is looking for… if you have the ability to continue that thought please just go ahead and state what your thought is.

All the concrete types in this proposal are Copyable. Without Copyable we AFAIK have no way to guarantee that self is always identical to self. I see no reason to begin a debate about how to define the semantics of isIdentical(to:) on types that are not Copyable… but please just go ahead and state what your opinion might be on that topic if you feel it is important to the discussion of the concrete types being presented in this proposal.

139

I am not asking rhetorical questions to make a point: I'm asking—given the example you provided—what are your desired semantics for C.isIdentical(to:)?

Recall the instructions from the Swift Evolution proposal template: "Describe the design of the solution in detail. [...] The detail in this section should be sufficient for someone who is not one of the authors to be able to reasonably implement the feature."

Suppose you incorporated C.isIdentical(to:) as a concrete addition in your proposal and assigned its implementation to me. How would I know which of the above implementations I listed—any or all—are "reasonable" implementations? Am I missing any other possibilities that give observably different behavior? Can you articulate the criteria I should go on to make that decision?

The question about noncopyable structs is to develop this question further because === doesn't exist, precisely so that we can't shortcut the discussion merely by saying, "Well, that decision's been made!" No worries if you're not familiar with noncopyable structs; go back to your original example—with a blank slate, what criteria should I go on to determine if something is a "reasonable" implementation for a type without a pre-established notion of identity?

140

I think maybe enough ink has been spilled today on this.

5 Likes
141

Two distinct instances of a noncopyable type are always inherently distinguishable from each other, no matter what API they provide. For example, two distinct atomic integers can never be considered identical, even if they happen to have the same value, and therefore the exact same underlying representation.

I believe isIdentical(to:) inherently only makes sense for Copyable types. The API-level practical definition I gave bases it on whether one value is distinguishable from a copy of the other -- if there is no way to make a copy, the definition is vacuous. We can certainly try generalizing it (e.g., by talking about whether there is a way to figure out if two borrows are borrowing the same instance) -- but I don't think there is much meat on that bone, as distinct noncopyable instances are always distinguished by ownership, whether or not their borrows are. It appears to me that it would be nonsensical to ask whether two noncopyable instances are identical. Would it not? (For example, what would be the method's type signature?)

isIdentical(to:) implements the equivalence relation that we'd get if we took the substitutability "requirement" of Equatable seriously. This is quite important to get through, as we do need to soon generalize Equatable to allow noncopyable/nonescapable conformers, and that inherently means accepting that == does not imply substitutability in any "global" sense -- it is just an arbitrary equivalence relation that the type's author thought was most useful/practical.

3 Likes
142

The Language Steering Group talked about this today.

The LSG is inclined towards accepting SE-0494 under the name isTriviallyIdentical(to:):

  • "trivial" to emphasize that this should be a fast O(1) check, ideally as simple as a bitwise comparison[1], rather than a deep comparison; and
  • "identical" to emphasize that is not an equality check and is not specifically required to be consistent with Equatable, which the providing type needn't even conform to.

Since this name has not been extensively discussed, the review period is being extended until Monday, October 13th, to gather additional feedback.

On non-naming subjects, the LSG agrees with the proposal that there is no immediate need for a protocol, and we accept Karoy's suggestion that this also be added to the Unsafe*BufferPointer and UTF8Span APIs. These aspects of SE-0494 are hereby accepted, and we ask that the extended review period focus on the remaining naming issue.

I'd like to thank the community for its active and thoughtful engagement in this review so far.

John McCall
Review Manager

  1. not meant to be a normative requirement, and without meaning to open discussion about padding ↩︎

19 Likes