An Implementation Model for Rational Protocol Conformance Behavior

Evolution Pitches
106

Quoting out of order to condense related things:

Yeah, now I see it! I still maintain you can remove removing the Q: Equatable refinement and associated extension on R without changing anything substantive about your example, though.

So, under the existing model (as I understand it), id2 is handled statically at compile time, while b() is handled dynamically at run time.

I…guess you could put it that way(?) but it's a bit misleading. The whole point of id2 is to get out of the way of any overloads that might be more specific than P's id requirement and thereby coax its use of id to be dynamically dispatched through the P witness table. Most people do this in examples by writing a generic function:

func id2<T: P>(x: T) -> String { x.id }

I interpret your example and question to @Douglas_Gregor to be focussed on changing the model. My example and question are focussed on understanding whether certain observed behavior is a bug or consistent with the intended behavior.

Well, those things are all bound up together, ain't they? If Doug confirms my understanding, my next question will be whether he's confident that the community and core team will accept the semantic change as a bug fix.

Finally, as I understand the intended behavior of the existing model, in your example, the output is expected and correct while, in my example, the intended output might be unexpected and incorrect.

This is why we need that documentation thread, really. These notions are all completely fuzzy at the moment, partly because of what you mentioned in #74. As I understand it, your example is more-obviously a bug than mine, but it's not clear whether we need new language features to handle my example or whether that can be considered a bug, too. The former approach wouldn't be terrible, as it would give us an opportunity to address a cluster of related issues I raised in #32.

1 Like
107

[quote="Douglas_Gregor, post:53, topic:37171"]

After further investigation of SR-12881, it appears that the example code, when run in much older versions of Swift, actually does call the correct implementation of distance(from:to:), and so produces the correct output rather than trapping.

Is this seeming change in protocol conformance behavior due to something changing in the Standard Library, or in protocol conformance behavior generally (perhaps usage of the override keyword and @_nonoverride annotation), or something else?

108

You could always try bisecting for the offending commit.

Wow, when did override become legal on protocols?

109

I wish I was setup to do that. I'm hoping that someone who is will lend a hand. :slight_smile:

September 2018, just prior to the public release of 4.2. See, Introduce overrides of protocol members and drop them from witness tables #19034.

110

Is that a language feature (i.e. with an evolution proposal) or just magic for the standard library?

111

The latter. The motivation appears to be (i) a reduction in binary size for the Standard Library and (ii) flexibility re: ABI and restating protocol requirements in inheriting protocols. Here is the initial note from the pull request:

When a protocol restates a requirement from its inherited protocol, track that as an override the same way we do with overrides in classes. Such overrides are recorded in the AST but are omitted from the witness table itself. This makes restating protocol requirements in inheriting protocols ABI-neutral, so we can restate protocol requirements to influence associated type inference without baking those decisions into the ABI.
As part of this, introduce tools that allow us to audit all of the restated protocol requirements within the standard library, via a warning new warning flag ( -warn-implicit-overrides ) to warn about such requirements, as well as an appropriate suppression mechanism ( override to treat it as an override, @_nonoverride to give it a new witness table entry). Only those restated requirements that are meant to have a semantic effect, like BidirectionalCollection.index(_:offsetBy:) , should use @_nonoverride , because it commits us to having that entry in the witness table forever.
Rolling this out in the standard library shrinks the size of the standard library binary by 196k.
Implements rdar://problem/43870489.

112

Yeah, I read the PR comment already. The reason I asked if it's standard library magic is because, if that's what it is, the legality of using override on protocols (even if the compiler accepts it) is at best highly questionable

113

Also, see, the notes, here: [Standard library] Audit protocol member overrides in protocols.

114

After digging through 2017-18 era pull requests for the Collection hierarchy, it slowly dawned on me that some of the examples that we are discussing tie back to the introduction of conditional protocol conformance. Much of what is now done via conditional conformance was hardwired previously. As that hard-wiring was removed from the Standard Library and replaced with conditional conformance, it is apparent that the Standard Library team ran into quirks like that highlighted by SR-12881.

To my eye, @dabrahams example, above, is a minimized version of SR-12881. That example is illustrative of a quirk of protocol conformance behavior attendant to use of conditional protocol conformance in a hierarchy. Please see the recent exploration of that example by @Jens and the related analysis by @Nevin, here. It is illuminating.

When the Standard Library team ran into this sort of behavior, it appears that they developed a work around. See, Work-around incorrect name resolution with conditional Bidir…, and Refactor out impl methods of BidiCollection; NFC. The essence of the work around is to avoid the issue by putting the real method in an underscored version (e.g., _distance(from:to:)). The default implementation of the protocol requirement is just a pass-through to the underscored method. When running into a conditional conformance-related witness table issue, the Standard Library team could avoid the issue by calling the underscored method directly. The underscored methods are internal.

At least, that is my interpretation of what I'm seeing. Perhaps others could correct and clarify what I've written.

So, when the SR-12881 example tries to call distance(from:to:) from inside of generic_distance(from:to:) on an extension of Collection, it runs into the same problem. However, it cannot call the underscored method as a work around.

While not ideal, one API/ABI stable solution to consider is to (a) teach the workaround technique, and (b) in the Standard Library, make the workarounds public so that problems like SR-12881 can be solved directly.

115

Please, someone explain to me why my bug SR-12881 keeps getting tied back to my thread when AFAICT they have nothing to do with one another! I'm bewildered again.

If you think of my example above as a bug that supposedly ought to print "Q Q," it has no efficient remedy without changes to the compiler, and no remedy at all—efficient or otherwise—that prevents the problem from happening again when another protocol refinement R: Q with its own id and conditional conformance of X comes along. SR-12881, on the other hand, has a perfectly good fix in the standard library, thanks to @Nevin.

I'm not sure about your analysis, since Nevin's fix doesn't use any underscored methods; it just forwards implementations through to its stored collection.

116

For me, the connection with SR-12881 is that it's a concrete form of SR-12692, in that if the example in SR-12692 magically worked, SR-12881 would probably not need a workaround. (I think that makes sense; maybe someone else can explain it better.)

You've convinced me that this is something that would be desirable to fix. I've been trying to think of a model that will do something useful in the following code and having a hard time:

// Contrived.swift
protocol ContrivedProto {
  associatedtype Assoc
  func doSomething()
}

extension ContrivedProto where Assoc: Comparable {
  func doSomething() { print("Assoc is Comparable") }
}
extension ContrivedProto where Assoc: Hashable {
  func doSomething() { print("Assoc is Hashable") }
}
extension ContrivedProto where Assoc == String {
  func doSomething() { print("Assoc is String, specifically") }
}
extension ContrivedProto where Assoc == (String, String) {
  func doSomething() { print("Assoc is two Strings, specifically") }
}
extension ContrivedProto where Assoc == (String, String, String) {
  func doSomething() { print("Assoc is three Strings, specifically") }
}
extension ContrivedProto {
  func doSomething() { print("we don't know anything about Assoc") }
}

struct ContrivedImpl<Wrapped>: ContrivedProto {
  typealias Assoc = Wrapped
}

// Client.swift
ContrivedImpl<Int>().doSomething() // compiler correctly emits an error: ambiguous use of 'doSomething()'

func makeItDoSomething<SomeContrived>(_ x: SomeContrived) where SomeContrived: ContrivedProto {
  x.doSomething()
}

makeItDoSomething(ContrivedImpl<Int>()) // does this result in a run-time error message?

makeItDoSomething(ContrivedImpl<(String, String, String)>()) // there are only two valid options but does that mean we have to test for all of them at run time?

One path tries to make these last two calls into compiler errors by generating the conformance for the instantiated type in Client.swift (or at least a "conformance request" where the runtime can fill it in, I don't know). I'm still trying to think through the ramifications of that (ignoring whether it's possible to do without an ABI break, and what to do with dynamic casts).

Another says that we can use one of Doug's strategies to resolve witnesses at run time. This example shows some of my first-level concerns with that, but maybe the answer is that we have to be more explicit about which alternate candidates might get used at run time, instead of "all of them".

The final path I can think of is leaving things the way they are today: witnesses are chosen at compile time with only local information, and the way to get conditional behavior is with explicit requirements like withContiguousStorageIfAvailable, but with compiler support added so that you can actually write them. That might be enough if our primary use case is protocol hierarchies, but it does have the cost of adding a requirement to the base protocol. (This might be equivalent to the previous option with explicit opt-in, but I'm not sure.)

All of this gets more complicated with additional protocol extensions outside the defining module, especially with compile-time resolution because it'd be much easier to have two types that are spelled the same but have different witnesses.

117

It's your own fault! :wink: By intention or not, you wrote an example that is a minimized version of SR-12881. Check it out:

  • P = Collection
  • Q = BidirectionalCollection
  • X = DefaultIndices
  • id = distance(from:to:)
  • id2 = generic_distance(from:to:)

I'm just following your lead.

I concur. Unless it absolutely is not possible, a compiler fix would be much better than trying to teach users to recognize the issue and workaround it.

I'm not so sure that the fix is perfectly good. For one thing, it changes protocol conformance behavior of DefaultIndices in a way that might break the code of other users.

Also, the fix essentially takes advantage of the same concept of an internal workaround that my prior post described. The fix that @Nevin wrote is equivalent to, in your example, giving X its own implementation of id, and then, inside of that implementation, rerouting to a path that has access to Q's implementation of id. I don't think you'd want library authors to have to build those sorts of workarounds into their libraries. It's easy to mess it up.

[EDIT: No offense to @Nevin. What he wrote is totally correct in terms of the pattern established in the Standard Library, and he did a great and fast job of it, and it works.]

2 Likes
118

/me scratches head

How is this not a concrete form of SR-12692 , being the exact example there? Furthermore, as it says there, no fix for the problem in SR-12692 exists without language changes, whereas as I have pointed out over and over, that's not the case for SR-12881. That makes SR-12881 just as different from SR-12692 as my example above.

Sheesh, could you have made that example a little more condensed? It's hard to see what you're trying to do here, but IIUC the essence is that you're exploring how the compiler should deal with ambiguous, equally-good, conformances.

As I've said several times in this thread, I'm quite sure it's easy to prove that many such ambiguities can't be detected until run time. ContrivedImpl<Int> doesn't have to appear anywhere in source code where the compiler can forbid the use of doSomething():

func contrive<T>(_ x: T) {
   ContrivedImpl<T>().doSomething()
}

As I've also said, one possible strategy is to simply (deterministically) pick one matching conformance when there are ambiguities. Protocol requirements have semantic requirements, and all equally-good candidates should produce reasonable results.

And as I've also also said, there's a cluster of issues here that includes the inability to retroactively add algorithms that are dispatched based on conformances, and the inability to definitively associate different implementations of the same algorithm, that maybe should be addressed together. If there was a different way to write such things, we could avoid changing the semantics of existing code, make the language more expressive, and deal with the ambiguity issues on their own terms, at least giving people finer control over how they are resolved.

1 Like
119

Yeah, sorry, this wasn't intended to be a disagreement with anything you've said in the latter half of the thread, just a single example that highlights a number of design decisions we'd have to make. In a compile-time-resolved world, contrive doesn't get to use any of the more specific conformances.

I think the example you have as a concrete form of SR-12692 is a valid example of SR-12692. I think SR-12881 is also an example of SR-12692, but one that's part of a subset that can be resolved without language changes. I could be wrong though, if there's a way to fix SR-12692 that wouldn't fix the behavior of DefaultIndices.

2 Likes
120

Okay, I follow you that far, at least.

How, exactly? I don't see it. If you're worried about breaking users, changing the semantics of existing code in a way that potentially affects all conditionally-conforming types seems like a much greater risk to me.

Well, it's not calling BidirectionalCollection's implementations on self; it's calling the implementations provided by the _elements property. But I sort of get where you're going with the analogy: everything would have been fine if the implementation for BidirectionalCollection had kicked in, but since it won't, the fix is to do, ultimately, the same thing that implementation will do. But that only works because all operations are being dispatched through _elements here; I don't think there's any workaround in the general case.

No, I wouldn't; not at all.

121

I didn't think you were disagreeing. I'm just saying, if you're exploring what I think you're exploring (still haven't confirmed/denied that!) I believe we have to accept some ambiguities will only be known at run time, and we need a non-crashing way to deal with them.

In a compile-time-resolved world, contrive doesn't get to use any of the more specific conformances.

I'm not sure what you're really saying there. “contrive doesn't get to use any of the more specific conformances” is one possible answer, but I think that pretty much amounts to a repeat of the same problem you're trying to fix.

I think the example you have as a concrete form of SR-12692 is a valid example of SR-12692. I think SR-12881 is also an example of SR-12692, but one that's part of a subset that can be resolved without language changes. I could be wrong though, if there's a way to fix SR-12692 that wouldn't fix the behavior of DefaultIndices.

There is. As I just mentioned a new language feature could be created to express specializable generic algorithms. SR-12692 is about what it's possible to express in the language today. SR-12881 is about a bug in the standard library implementation (brought on, most certainly, by a misleading language semantics that makes it easy to think you're expressing something you're not, i.e. SR-12692).

122

Yeah, I don't think it's a desirable solution [and maybe shouldn't have even brought it up]. It's just a possible self-consistent solution: a conformance is created anew at the point it is requested, using the witnesses visible there, instead of looked up globally. I think that probably breaks a ton of things, though—imagine a more specific hash(into:) being visible in this context but not that one. It's even worse than conflicting conformances in different modules. :-)

1 Like
123

It isn't pretty, but if the Collection hierarchy of protocols exposed its underscored implementations, like _index(_ :offsetBy:) -> Index, SR-12692 and a whole class of these problems could be worked around without language changes. With that said, I'd VERY MUCH prefer that conditional protocol conformance did not have the quirk that leads to this class of problems.

I was writing without really thinking that part through to its conclusion. As I now think it through, it seems very unlikely that a user's code will be broken by the fix. Thank you.

If a language-changing adjustment of protocol conformance is to be made, it will be a steep hill to climb. To get over that hill, the alternatives will need to be explored, and proven to be lacking. So, I'm looking at the alternatives. It would be fair to say that I'm jumping the gun. You tell me.

124

No, I think you've misunderstood SR-12692. It is not about Collection. It is about what the language allows a generic library author to express. Making changes to the standard library doesn't do anything to address that bug.

I don't think I understand how that's a response to what I said, or even really what you might mean by it. I do get the sense you feel criticized, so let me be clear: I'm not criticizing any exploration you might be doing. I am pointing out, since you brought up code breakage, that addressing SR-12692 by changing the semantics of existing code will definitely break some users.

We could also address SR-12692 by adding new language features, and while I'm not yet convinced it's the answer, it could avoid breaking existing code and provide some other benefits, so we should explore that direction too.

125

Didn't mean to sound that way. You are leading what, in my view, is a very important and much needed discussion, with many facets to it. I'm working hard to contribute, but am pushing the limits of my own knowledge and experience. So, I'm quite seriously saying, let me know if I get too far afield.

Well said.

Do you have something particular in mind?