An Implementation Model for Rational Protocol Conformance Behavior

[dabrahams (Dave Abrahams)]

@Douglas_Gregor

@dabrahams

Can we not store a pointer to it wherever @Douglas_Gregor was talking about putting his decision procedure ("in some runtime hooks we have during witness table realization")?

I'm talking about the witness table itself, i.e., the mapping the protocol requirements to specific witnesses that implement those requirements. At the point where (say) Array is defined to conform to Collection , we can record additional information about what other potential witnesses existed (but didn't apply) and choose among them.

Then I suppose we could at least do what I've proposed for constrained generics, e.g. by tucking the information into (a copy of) the first witness table. If there's truly no way to extend the information passed to unconstrained generics, it would mean…

I hope this is irrelevant because of what I've learned below about distinct types

making the semantics of dynamic downcasting a value of generic parameter type to a protocol existentials inconsistent with those of generic dispatching in some cases. We'd have the option to limit the inconsistency to cases where the generic parameter is unconstrained. Happy to elaborate more if this isn't obvious to you. I'm still hoping there's a way out of this jam, but I don't think it's fatal to the idea.

I believe there is enough leeway there to address SR-12881 in a reasonable manner,

I must admit I'm a bit confused as to why several people have posted in this thread about addressing that bug via compiler changes, since it has a fix in the library. If it's because you think the existing standard library code should work as written, then that's news(!) to me and we're into new territory in two dimensions:

1. We'd have an opportunity to describe the rules that make that code work
2. We'd be changing the semantics of existing code

Others will disagree I know, but I'm not at all opposed to #2. In fact think it is necessary in some areas of the generics system (whether for SR-12881 remains to be seen). I'm an enthusiastic supporter of #1, which, it seems to me, is obviously a precondition for #2. Also before we move on to #2 I'd like to talk about how the rules of #1 line up with the solutions to other problems in the generics system that seem closely related to me. In particular:

• Problems with algorithm specialization and conditional conformances.
• Problems with conformances in multiple modules (edit: good news—I see this one might almost be considered fixed if someone would just document how it's supposed to work!)
• The inability of anyone other than the owner of a protocol to extend the set of specializable algorithms that operate on models of the protocol.

I believe that it's possible to resolve all three of those within the implementation model I'm pitching here, which is part of why I pitched it. If you'd rather talk about it in terms of programming models, that would be great. As I noted at the beginning of the thread I've had some trouble making headway with that tack, but I'm happy to try again.

... schnipp scheme for fixing SR-12881 presumably(?) without changing library code…
Are those the semantics you want?

Thanks for asking, but I'm a bit bewildered by the question. I filed SR-12881 to report that library components aren't working properly. As I'm sure you know, I've filed plenty of bugs about the generics system recently, but that isn't one of 'em. Mostly though, I don't have any grasp on how what you've described generalizes or what rules would govern the semantic change going into effect. Obviously, I'm not interested in a compiler change that just affects that one example, and I'm pretty sure that's not what you mean to propose, but please can you describe the programming model or the implementation model in a way that tells me more than just how you expect the compiler to deal with one or two pieces of code?

Note that, due to retroactive conformances, there may be more than one witness table for a given conformance of a type X to a protocol P . Those witness tables may have different witnesses (of course), and both may be used at run time. This can result in having two types that would be spelled the same way in source code actually be distinct because they use different conformances.

I'm aware.

Let's make this concrete:

// Module A
public struct X { }

// Module B
import A
public extension X: Hashable  { ... }

public func getBSet() -> Set<X> { ... }

// Module C
import A
public extension X: Hashable  { ... }

public func getCSet() -> Set<X> { ... }

The types Set<X> produced by modules B and C are distinct, because they use different conformances of X: Hashable . The Swift runtime will keep them distinct, with different type metadata pointers (each of which includes the appropriate witness table).

You mean, it already does that? That's wonderful! I suppose one can square this with Jordan's assertion that type metadata is unique for a given type because they're considered different types, but that's actually just what I'd like to see happen with scoped conformances and basically would allow the conformance table I've pitched in my implementation model to be stashed in the value witness table.

I hate to ask, but is any of this (and the implications for program semantics) written down somewhere?

The Swift compiler has known problems with this if you import both B and C into a fourth module, e.g.,

// Module D
import A
import B
import C

func test() {
  let setX1 = getBSet()
  let setX2 = getCSet()
  if setX1 == setX2 { ... }  // SHOULD be an compile-time error, probably won't be, might crash in runtime
}

PR #31895 is a step toward fixing this, but this is important: having multiple retroactive conformances affects type identity.

I'm totally fine with that (not the runtime crash, but that multiple overlapping conformances affects type identity).

@jrose makes an excellent point about as? being tricky, which is what I brought up the above:

@jrose

But I really think the "irrational behavior" is on the part of as? , not conformances, and I don't think that all generic functions should pay a price so that as? gets more sensible behavior.

Let's say I have code like this:

func test(any: Any) {
  if let setOfX = any as? Set<X> { ... }
}

And somehow I end up feeding the results of getBSet() and getCSet() into it. What do we expect to happen? Does your answer change depending on which module defines the test(any:) function?

Great question! This sounds tricky at first but the more I think it through, the more obvious the answer becomes: the cast fails (produces nil) unless the type metadata for Set<X> at the point of the cast matches the type metadata pointer for any, i.e. unless the X used to form any conforms to Hashable the same way that an X instance would if it were created locally. Simply put, if the type of any and the local meaning of Set<X> are distinct, the cast fails.

Another example:

func testHashable(any: Any) {
  if let h = any as? Hashable { /* assume Hashable doesn't have a Self requirement */ }
}

Now arrange for an instance of X to get passed in here. What do we expect to happen? Does your answer change depending on which module defines the testHashable(any:) function?

This one is easy; I expect the semantics laid out in the scoped conformances pitch. The cast succeeds iff a conformance of X to Hashable was visible in the scope where X was first bound to a generic parameter or the X instance was converted to an existential. The Hashable existential instance behaves according to that conformance.

…implementation concerns weigh heavily here, because a lot of what people abstractly want are not implementable in an efficient and/or backwards-compatible manner. That doesn't mean we should drive the discussion from the implementation, though. We have to know what actually semantics we want, and then the push-pull of design and implementability can kick in.

Yes please! I just want to start by getting to a common language for describing the semantics we want. Having previously failed to have the discussion from an abstract programming model POV, I pitched an implementation model here that

• I could easily understand
• Seemed consistent with your stated intent
• Was flexible enough to express the semantics I want, if deployed in one particular way
• Seemed implementable (and apparently it is?) so would not immediately draw fire on that score (#FAIL!)

I'm unable to map from your statement of intention and implementation sketch to the semantics you want.

No surprise; I didn't lay out any semantics in this pitch, because every time I try to describe the semantics I want—and I promise I'm not pointing any fingers here—it feels to me like someone more familiar than me with the current implementation either:

• declares the semantics unimplementable and out of the question, or
• proceeds from the current implementation as a given in a way that closes off discussion of possible semantics.

By pitching a possible implementation model, I was trying to set up a basis for the discussion that wouldn't immediately lead to a dead end.

Answering my bolded questions above would help me understand the goal, then I can tell you what is achievable w.r.t. implementation. You answered some similar questions in Ergonomics: generic types conforming "in more than one way", but we're in a different thread…

Sorry I couldn't answer the first question; I just don't have the context I need to do so yet. I think I answered the other questions pretty solidly, though. But my actual goal here was to lay the groundwork for any kind of productive discussion of semantics at all. In the thread you referenced, I asked you many direct questions to try to get a handle on your design intent. When the reply tersely declined to address most of them I decided that maybe I needed to try a different angle. I'm very glad that we seem to be engaging productively on this topic now!

…and these kinds of semantic decisions haven't been recorded/explained anywhere. They really need to be, because I don't think anyone can understand the intended semantics without these kinds of small examples to reason through.

Amen to that, brother! I've just been trying to unlock the semantic decisions from the brain of the person I presume to have made them. And small examples are definitely necessary, but as a means of illustrating semantics that can be described more generally.