An Implementation Model for Rational Protocol Conformance Behavior

mattrips · June 4, 2020, 6:05pm

Totally agree that that is a key part of the question.

Would very much like to learn your thoughts on what would be a good semantic model for Swift.

jrose · June 4, 2020, 6:21pm

Ah, I think somewhere along the way you've gotten the witness table (the run-time structure that represents a conformance) mixed up with the value witness table (the run-time structure that describes basic operations on a type). (No, I don't like that they're so similar in name either.) For each generic parameter, a generic function (or type) is given both the generic argument's type metadata and the witness table (conformance) for each protocol constraint on the parameter. The type metadata is globally unique and the conformance is specific to the protocol, so neither of them are a great place to stash additional information about the call site.

mattrips · June 4, 2020, 6:21pm

The presence of multiple modules in a scope or the existence of invisible and/or hard-to-see factors (e.g., see the fix for SR-12881) already seem to affect method dispatching in hard-to-predict / hard-to-describe ways. Doesn't changing the scope within which code exists already (potentially) change how it functions?

Apologies for the serial response...

jrose · June 4, 2020, 6:29pm

I admit I feel burned by this due to my past efforts on retroactive conformances, which is why most of my ideas nowadays tend towards just declaring outright that dynamic casts won't find any new types of conformance that we want to introduce. I do think there's room to improve around protocol hierarchies, but that since people don't usually conform to different layers of protocol hierarchies in different modules that it'd be simpler to come up with some kind of rule around that, whether it's formalizing patterns like withContiguousStorageIfAvailable or only searching in certain modules (based on already available information like a known conformance location, not call site) instead of doing a global search.

Yeah, it's true, we already do have that "problem" ("feature"?). I feel like collecting all visible conformances from a scope would magnify it because they're never explicitly named, whereas today with overload resolution / protocol witness checking you know which names are being looked up. But maybe it only feels that way to me as a compiler engineer, and a normal user of Swift wouldn't notice or care about the difference.

dabrahams · June 4, 2020, 6:39pm

No, I wasn't confused about anything other than how the VWT is reached from inside a generic function. The VWT I know to be extensible and also present even for unconstrained generic parameters, so it seemed a good central place to stash additional information. But if it's only accessible through the type metadata, that's not going to work and there has to be another place to put the information.

Douglas_Gregor · June 4, 2020, 7:12pm

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.

I believe there is enough leeway there to address SR-12881 in a reasonable manner, if we capture---at the point of DefaultIndices conformance to Collection---the potential set of distance(from:to) witnesses for that conformance (one in the extension of Collection, another in the extension of BidirectionalCollection, a third in RandomAccessCollection) and delay the decision of which witness to use until we have a specific concrete generic argument type (e.g., DefaultIndices<ClosedRange<Int>>. That can probably be made to line up with what overload resolution would do for a call to DefaultIndices<ClosedRange<Int>>(...).distance(from:to:) when we have fully concrete types at type-checking time.

Are those the semantics you want?

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. 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).

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.

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

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?

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?

As those discussions and this one have shown, 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.

I'm unable to map from your statement of intention and implementation sketch to the semantics you want. 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 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.

Doug

dabrahams · June 4, 2020, 8:25pm

You're still seriously missing the point here. This implementation model doesn't necessarily imply any semantic change, except maybe in cases that are currently completely unspecified and broken today. What gets put in the conformance table can easily be the exact witness tables that are used for generic programs today.

What the implementation model does is:

makes it possible to resolve some problems that most of us agree are wrong and/or undesired without running into considerations that are purely based on what can be done within today's implementation.
provides a workable mental model for users to think about generic dispatching, which I claim we currently do not have.

mattrips · June 4, 2020, 9:36pm

For reference purposes and additional food for thought, readers of this thread might also revisit the 2018-era discussion at Retroactive Conformances v. Swift-in-the-OS.

jrose · June 4, 2020, 10:30pm

Thanks, @mattrips. I probably should have called it out more explicitly. If you're not worn out from reading, Backwards-deployable Conformances also talks about how to tackles some of the problems in Retroactive Conformances vs. Swift-in-the-OS, but focusing on libraries shipped with Apple OSs. It's less relevant to the current discussion, but I don't want to leave the impression that there's been no progress on the issues I/we raised originally.

jrose · June 5, 2020, 1:00am

[Meta: I've been posting a lot and been (rightfully) called out on my negativity in private, so after this one I'm going to hold off on further replies till the weekend at least.]

This is a good point. Here's how I would summarize (what as I see as) the intent of our current model, ignoring dynamic casts, associated type inference, and the possibility of two conflicting visible conformances (one of Doug's examples):

When a conformance MyType: MyProtocol is declared, the compiler goes through each requirement and asks what function would be called, given what is known at that point in the program:
```
// Illustrative purposes only;
// the compiler does not actually synthesize a function to do this.
extension MyType {
  func __invoke_doSomething(with argument: Int) {
    self.doSomething(with: argument)
  }
}
```
If there are multiple overloads of doSomething(with:), the compiler picks the best one visible, just like it always does. The meaning of "best" is chosen at this point in time, which means that if one of the overloads is in a constrained extension based on a generic parameter of MyType, it won't get picked, because one implementation is picked to work with any MyType, whether it's MyType<Int> or MyType<[MyType<String?>]>. (It can take into account any constraints that are on the actual definition of MyType—perhaps that its argument has to be Equatable—as well as any constraints on the extension adding the conformance, if it's a conditional conformance.)

All of this is the same (idea) as overload resolution, which does not do dynamic dispatch in Swift. You'll often find me reciting "there are three ways to do type-based dispatch in Swift: invoking a protocol requirement, calling an overridable method on a class, or actually checking the type with a dynamic cast".
When a MyType value is passed to a generic function with a MyProtocol constraint or converted to an existential value, the compiler finds "the" conformance of MyType to MyProtocol, and passes that to the function. (The run-time representation of the conformance is the witness table, which contains all the "witnesses" to the requirements chosen in (1), as well as the associated types, and the conformances for any constraints on the associated types.) Note that this process doesn't look at the generic arguments of MyType except to populate the "associated types" section.
Later on, when a protocol requirement is invoked (through a generic argument or an existential value), the "witness" found in the table in (2) is called.

That's the model as I understand it. You and Doug have already called out a weak point in (2)—"what should happen if two conformances are visible?"—compounded (in SR-12513) by leaky import visibility that lets the compiler find extension members and see conformances from an import that's in another file in the same module. And there's also the weak point in (1)—"requirements are resolved at the point where the conformance is declared"—which caused the problem with DefaultIndices in SR-12881.

(1) and (2) are also the places Doug called out as places to run a "decision procedure"—either the witness chosen in (1) would be a compiler-synthesized function that picked the best overload when invoked, or the fetching of the witness table in (2) could pick the best overload when created.

But your original point stands. Why is it hard for users to think about generic dispatching? I'd guess that it's the same reason many users have trouble with this code:

extension Collection {
  func whatAmI() { print("Collection") }
}
extension Array {
  func whatAmI() { print("Array") }
}
func whatIsIt<C: Collection>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array
  whatIsIt(x) // Collection
}

For better or worse, most people's model of what generic code ought to do seems to match up with what C++ actually does: it should pick the best option based on the value you pass. It's only us Swift implementers who can look at that and say "that's overload resolution at run time", and shrink away because we've designed a language where overload resolution is non-trivial.

Changing this particular case to "work" doesn't even require a conformance table; it "just" means checking that the concrete type is an Array. There are many reasons why even this concerns me from a performance and code size perspective. But even putting those aside, is that really the interpretation we want for the code above? For Swift, I don't think it is—it's too ad hoc. Nothing links the various whatAmI operations but their names.

(EDIT: But of course, that's all that links the choices in overload resolution too, so this may not mean much.)

mattrips · June 5, 2020, 2:34am

I found your example compelling, but then thought about how it utilizes a non-required protocol method. Let's consider how using a required protocol method would change the result.

protocol P {
  func whatAmI()
}
extension P {
  func whatAmI() { print("P") }
}
extension Array: P {
  func whatAmI() { print("Array") }
}
func whatIsIt<C: P>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array
  whatIsIt(x) // Array
}

Our two examples, set side by side, reflect a fundamental difference in behavior. I suppose "many users have trouble" with your example due to this difference in behavior. But, I don't want to get this conversation hung up on subtleties of how things currently work.

I want to stay focussed on the question you pose about how we think it ought to work: "Is that really the interpretation we want?" I suppose my answer is, I could go either way on the interpretation. But, whatever the interpretation, I think it ought to apply the same way to both your example and my example.

mattrips · June 5, 2020, 3:30am

Having read a prior thread on the same subject, I kept thinking, and continue to think: Why isn't this a compile-time error?

Now, I understand your intent to be that this is and should be a compile-time error, but the compiler has a difficult time diagnosing it. If it is an error, do we need to consider it any further for purposes of talking about what the model should be?

I think this should be a compile-time error.

If there are two modules in scope that both supply a type called X, I believe it should be a compile-time error to use X without disambiguating. My answer doesn't change depending upon which module defines the function. If the reference to type X is ambiguous, it is an error.

In all of these cases, shouldn't the user be required to disambiguate the type-name collision at the point of use by prefixing the typename with the applicable module name?

Douglas_Gregor · June 5, 2020, 5:09am

It depends on which "this" you're referring to:

It is not wrong for either B or C to declare a conformance of X to Hashable. Retroactive conformances are allowed in the language, but they're tricky. No compile-time error here.
A program may very well import both modules B and C, perhaps in separate modules that don't even know about each other. You can't really produce a compile-time error without seeing B and C in the same place, and you probably don't want to: B might be some hidden dependency, and bringing it into your program shouldn't cause your program to be wrong just by its existence.
The module D in the example should produce a compile-time error somewhere. The correct place, in my opinion, is on the use of ==: the == for Set only works when the two Set types are the same, and these Set<X> types are different because they involve different X: Hashable conformances.

For me, it depends on what modules have been imported. If we only have

import A

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

then I agree that this must be a compile-time error, because X does not conform to Hashable.

However, I would say that

import A
import B

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

is correct. Moreover, it should match the type produced by getBSet() but not by getCSet().

There's a similar case for the function if defined in a module that imports A and C.

However, I expect a compile-time error if both conformances of X to Hashable are visible:

import A
import B
import C

func test(any: Any) {
  if let setOfX = any as? Set<X> { ... }  // error: multiple conformances of X to Hashable
}

There is only a single type X here, which is defined in module A. If modules B and C are both included in your program, then at runtime we have to decide what any as? Hashable should do, given that (for example) the two X: Hashable conformances might have different hash values. There are a few options here:

Crash the program, because we've hit an ambiguity and ambiguities are fatal at compile-time
Arbitrarily select one of the conformances; optionally warn the user what we did
Try to rank the conformances in some manner to give a well-defined answer, e.g., by using some information about the module in which the as? occurs
Refuse to choose a specific conformance, and return nil instead so the program can continue

Doug

Douglas_Gregor · June 5, 2020, 5:19am

In your example, when Array conforms to P, the Array version of whatAmI() is the most specialized already, so you get the right answer. Add this to your example and it will better parallel @jrose's:

extension Array where Element: P {
  func whatAmI() { print("Array<P>") }
}
extension Int: P {
  func whatAmI() { print("Int") }
}

The output will be:

Array<P>
Array

That's the one that bothers me most. A protocol requirement is meant to be a point of dynamic dispatch, where you jump to a version of the code that's been customized for the concrete type... but we don't actually get all of the customization we want (or expect).

I'm less bothered by @jrose's example because I don't feel like a call to a function that is neither an overridable method in a class or a protocol requirement should allow different behavior with different types at runtime.

I appreciate that we're gathering a corpus of examples and opinions. One needs those to evaluate designs.

Doug

mattrips · June 5, 2020, 6:40am

Doug, thank you for your time and patience. My first pass was a bit sloppy.

I now see in your example that getBSet() and getCSet() inherently provide disambiguation. So, there is no error at that stage. I agree that the error should occur upon use of == with two different types.

Right. There is no error unless both B and C are imported. If both are imported, the error is triggered when the function ambiguously refers to Set<X>.

Why do you say there is only a single type X? We get two different types of Set<X>, "because they use different conformances of X: Hashable." So, shouldn't the two different X: Hashable also be considered as two different types? And, then, when the program attempts to instantiate an X without disambiguation, shouldn't that result in a compile-time error?

Thanks again. Good stuff.

Douglas_Gregor · June 5, 2020, 6:51am

There is a single type X, defined in A. It has a unique identity that is unchanged by it's conformances.

We have two different types spelled Set<X> in the source code because one is Set<X where X:Hashable comes from module B> and the other is Set<X where X: Hashable comes from module C>. One X, two Set<X>, because required conformances are part of type identity for uses of generic types.

X is not ambiguous. Trying to form the type Set<X> where two different conformances of X to Hashable are visible should be a compile-time error.

Doug

mattrips · June 5, 2020, 7:17am

Hmm. In Jordan's example, why shouldn't the Array version of whatAmI() be afforded the most "specialized" treatment?

Yuck.

When I further amend the example by removing the requirement that protocol P have a whatAmI() method, the output becomes:

// Array<P>
// P

Is there a semantic model underlying why we have different behavior depending upon whether or not a protocol-provided implementation is a requirement of the protocol?

To me it feels natural that a change in the concrete type could change behavior. But, I'm troubled by the idea that a function could produce different behavior depending upon whether or not it happens to be a protocol requirement.

mattrips · June 5, 2020, 7:27am

Got it. Thank you.

Can the existence of the duplicate Hashable conformances reasonably be detected at compile time at the point at which an X is instantiated, for instance as part of constructing the witness table for X? If so, should the conflicting conformances be considered an error?

Jens · June 5, 2020, 9:15am

Just to add my reaction as a humble user. For this particular example, my mental model of Swift's generics (which took a while to develop) allows me to not get surprised or confused. This example is in my opinion not showcasing any of the really-hard-to-understand parts. I include the example here again for completeness:

protocol P {
  func whatAmI()
}

extension P                      { func whatAmI() { print("P")        }  }
extension Array: P               { func whatAmI() { print("Array")    }  }
extension Array where Element: P { func whatAmI() { print("Array<P>") }  }
extension Int: P                 { func whatAmI() { print("Int")      }  }

func whatIsIt<C: P>(_ value: C) {
  value.whatAmI()
}

func test() {
  let x = [1, 2, 3]
  x.whatAmI() // Array<P>
  whatIsIt(x) // Array
}
test()

By looking at this program I can predict (and not get surprised) by the output. The generic function whatIsIt has a typeparameter C which is constrained only by C: P which means that the compiler knows nothing about C except what it knows about P. That is, it knows about P's requirement whatAmI() and can call that required method (as implemented by various particular Cs), but it does so without knowing anything about eg Element or Array, it cannot get any information from any if its call sites, it's just its signature that matters.

The only way to make whatIsIt print "Array<P>" too (which I guess might be what some would expect?) would be to rewrite the example in a way that lets the compiler know more/enough about C. As the example is currently written, it is clear that within the body of whatIsIt, the compiler has no idea about Element: P or that C can sometimes be an Array. It only knows that some C conforms to P and if that C happens to implement P's requirement rather than use a default implementation, it will call C's implementation.

That said, there are many other things I get confused by in Swift's generics, like this example which @dabrahams linked to in the OP. (Note that I do not have a clear expectation about what the intended/best/fixed behavior should be in that example, especially so when taking @Nevin's "fun fact" into account.)

But perhaps my confusion there is just caused by the same rules I claim to understand here, I haven't thought about it enough to know if that might be the case.

filip-sakel · June 5, 2020, 9:58am

@Douglas_Gregor said “A protocol requirement is meant to be a point of dynamic dispatch“ and I completely agree. Also in you example the method that is declared conditionally when the Array’s Element conforms to P, I don’t see why the final output would be correct. For example, we could write:

protocol P { func whatIAm() }

...

extension Array: P {
    func whatIAm() { print(“Array”) }
    
    func whatIAm() where Element: P 
        { print(“Array<P>”) }
}

When written this way, I think the user’s expectation would be that since the second method is more specific it will be called instead of the first one, especially when considering that whatIAm() is a protocol requirement.