An Implementation Model for Rational Protocol Conformance Behavior

No, we cannot know about the duplicate conformances in the general case until we query for a specific conformance. And I’m the implementation Today, a type doesn’t carry its own conformances along with it; they are in a separate place where you can look up (eg) the witness table that makes X conform to Hashable.

2 Likes

I agree with (1)-(3). It’s mostly what we have today, modulo copious bugs.

Today you can “disambiguate” for (2) only crudely, by hiding the duplication from the compiler (eg, in the implementation details of two modules that don’t import each other).

One still has to decide what “as?” does when duplicates exist and are only discovered at runtime.

1 Like

I agree that your example shows unexpected and bad behavior in the presence of multiple conformances. However, changing the identity of a type based on the set of conformances visible at the point of use is, to me, untenable. It would mean that if you added a new protocol P to your own module, then made String conform to P, you could no longer use some other module’s API that takes an array of String (because now the arrays have different types).

2 Likes

As a technical matter, for a type with multiple conformances to the same protocol, how does Swift keep track of and know in the type's witness table that: in scope #1, it should call the version of the protocol conformance visible in scope #1, while in scope #2, it should call the version of the protocol conformance visible in scope #2?

Moving protocols to dynamic dispatch would go a long way toward making protocol behavior intuitive in Swift. I think developers expect that the most-specific implementation is the one that gets called, or the visible implementation to the caller with the least scope (e.g. internal in the calling module over public from an import).

1 Like

That's not actually the model I suggest we use. As I see it, there are two aspects to type

  • Nominal type identity, e.g. “Swift.Set<A.X>” or “A.X” (where A is a module)
  • Conformance set, e.g. {how A.X conforms to Hashable, how Swift.Set<A.X> conforms to Equatable}

When code expresses a requirement that two types are the same, it means:

  1. the nominal type identities are equal
  2. the conformance sets are non-conflicting

Two conformance sets conflict when they indicate the same nominal type conforms to a given protocol in two different ways.

In this model,

  • In your example, the conformance of String to P in my own module does not prevent an Array<String> created there from interoperating with any other APIs.
  • In my example, you could call doSomething() on the value produced by B.uniqueXs, but only by passing it through a context (module) where X does not conform to Equatable, and thus the concept of “unique Xs” has no meaning.

This model generalizes to scoped conformances this way for your example: if P is public but String: P is internal, another module could declare a different String: P conformance. Only then would that module's APIs involving String become incompatible with those from the module where the first conformance was defined.

1 Like

It's not that I have trouble analyzing an example like this one, when I'm thinking about the language rules as I understand them. But that's coming at it from the wrong end; I need to write programs.

When I try to express basic ideas of generic programming—which I happen to know the system was designed to support—the system lets me write code that looks as though it should express that intent, but actually subtly fails to. This bug illustrates.

The problem is that the rules as (not-)written don't support a usable programming model.

@adminstrator, Dave Abrahams' account appears to have been hijacked by Crusty. For further evidence, see SR-12692.

In other words, certain decisions necessarily would be deferred to runtime.

I'd like to believe efficient encoding is achievable.

Yes. They are two different systems. To avoid the natural tendency to try to harmonize one system with another, it would be best that they be fully decoupled.

In those cases where code should work, it must work. At the same time, it is important to be clear about what should not work. If a program does something that should not work, it should fail at compile time or crash at runtime. Code that looks like it works, but subtly does not work, is actively harmful.

Implicitly, you propose to defer discussion of (A) potential inconsistency with existing behavior and (B) implementation feasibility.

Consarn and dadburn it; a man can't have his fun anymore! OK, ye got me dead to rights, son.

18 Likes

It's great (for Swift) that you are calling attention to this! I've bumped into the problem described in that bug every now and then (trying to write efficient generic code for vectors, matrices, N-dimensional "tables" etc), and I've always thought that soon, maybe next year, this will be fixed/improved in some way and fully documented, they have a plan, it just takes time.

I'm surprised that this problem hasn't been recognized and dealt with until now though. I assumed the design and implementation of Swift was analyzed and tested for scenarios involving "express[ing] basic ideas of generic programming".

1 Like

To add one more from user side, when working within generic context, I've been using the same/different technique, that is, first identify the following:

[The same types]: well, not in a strict sense, but in terms of protocol conformance:

  • Same concrete types are the same (duh),
  • Generics with different specialisation are, still, the same.

[The different] methods:

  • Methods that's not part of a protocol requirement are different methods.
  • Methods that's not inherited are different methods.
  • Methods with different generic constraints are different methods.

Now within a generic context, the rule would be that, same type does not use different methods. In whatIsIt above.

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

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

I'd already know that calling whatIsIt with Array would use the same implementation of whatAmI regardless of the type of Element since all Array are same type. Figuring out which one is probably much less important in this context, but I'd (correctly) guess that first one is used since it matches the Array condition to conform Q (which is unconditional).

Outside generic context, though, I have not the slightest idea which whatAmI I'm calling. Rather, the rule is so different since now generics are not the same type anymore.

It's probably not entirely accurate, even within status quo, and I'd be happy to be corrected! But this has worked well so far. Even from designing perspective. When I want to use different implementation on the same (not different) methods on the generic, I know not to use even protocol conformance, since that'd be futile. Instead I use other patterns like decorator, which admittedly is not available everywhere.

Not to mention it doesn't help much in the presence of multiple-module conformance.

Edit:
Admittedly using common word like same/different could make things difficult/confusing to discuss later on... :thinking:

1 Like

While that's true, if I may presume to interpret for @Crusty, I don't think that's quite what he meant. Because Swift can't in general be monomorphized, and because of separate compilation, it's inevitable that we'll be making some decisions at runtime. If the talk about addressing SR-12881 in the compiler is to be believed, it means making more of those decisions at runtime than we currently do, at least in some cases. I hope those decisions get made once when a new combination of parameters for a generic type is encountered rather than every time a generic function gets called, but so far @Douglas_Gregor seems to be going in the latter direction.

It sounds to me like Crusty meant that we don't want to be doing full overload resolution for generic dispatch, because it implies effectively encoding the overloading rules into the runtime and encoding enough information about the program source into binaries that those rules could be applied. It also sort of makes protocol requirements meaningless as customization points because they can be hijacked by arbitrary overloads.

In those cases where code should work, it must work. At the same time, it is important to be clear about what should not work. If a program does something that should not work, it should fail at compile time or crash at runtime. Code that looks like it works, but subtly does not work, is actively harmful.

Aye, but the devil's in the details. There's a lot of room for interpretation around “should,” “works,” and “looks like.”

Implicitly, you propose to defer discussion of (A) potential inconsistency with existing behavior and (B) implementation feasibility.

Not so much (A). I'd actually be grateful if we could come to some explicit agreements about which of the current behaviors are to be considered bugs. If we're not willing to change semantics of programs that rely on some of these behaviors, we'll need new language syntax to express the new behaviors. I have reason to think we want some of that syntax anyway (explicitly linking requirement-satisfying declarations with the protocols and requirements they satisfy) so that could be viewed as an opportunity.

Also, I don't mind discussing implementation feasibility as long as it doesn't become a barrier to even considering what the ideal semantics would be. The tactic taken by this pitch was to get over that barrier, but I'm also happy to leave feasibility aside while we have the other discussion.

1 Like

There's some confusing terminology in this area that is making the current implementation less obvious than it should be. I'll try to summarize quickly here to answer your question, but the ABI documentation on type layout describes how type metadata and witness tables are layed out in memory, and the generic signatures ABI document describes how generic arguments are encoded. All of this was also covered in an LLVM Developer Meeting talk in 2017 on Implementing Swift Generics. It's quite worthwhile if you'd like to understand the implementation model.

Anyway, I'll try here. There are three concepts getting munged together:

  • Type metadata: a unique description of a type, such as X or Set<X with a specific X:Hashable conformance>. You can get the type metadata in Swift itself: it's a value of type Any.Type.
  • Witness table: a description of a conformance of a given type (say, X) to a given protocol (Hashable). These aren't unique, due to retroactive conformances. For generic types (e.g., Set<Element>), there is a witness table "pattern" that will be instantiated once the generic arguments are known, so Set<X with a specific X:Hashable>-conforms-to-Hashable can be different from Set<Int with a specific Int:Hashable>-conforms-to-Hashable.
  • Value witness table: a special table that's like a witness table, but for the core operations on a type like copy, destroy, size/alignment, move, etc. You can't really get at this in Swift and it doesn't really matter for this discussion.

In the implementation, there is no "type witness table" that has all of the conformances. That's something @dabrahams is proposing.

To your question about how scope #1 and scope #2 can have the same type (let's use X again) but with different conformances (e.g., to Hashable), it's because anything generic that has a Hashable requirement takes an implicit parameter for the witness table that implements that conformance. So something like this:

func f<T: Hashable>(_ value: T) { 
  print(value.hashValue)
}

takes an implicit witness table parameter for that T: Hashable conformance. In scope #1 (e.g., module B from my original example), the caller to f will pass along the witness table it knows about, which is defined in module B. f will call hashValue via the witness table itself, so it gets the version from module B.

Same deal with scope #2 (module C): it passes down a different witness table from module C, so you get different behavior.

Doug

4 Likes

Looking at SR-12881 more closely, I misunderstood it. Sorry for the confusion; that's not something that would be fixed by a compiler change.

I would much rather talk about programming models based on some design ideas and a corpus of examples to evaluate those designs. Some understanding of the implementation and its constraints is useful, because this is an area with hard constraints on runtime performance, code size, and backward compatibility. I posted some resources here.

My reply to @mattrips notes how uniqueness is determined for type metadata. Specifically, it includes the witness tables used to satisfy generic requirements. The runtime model of Swift has always accounted for multiple conformances in this matter, even if the surface language hasn't dealt with it explicitly.

No, it doesn't give you that. Type metadata is unique. It points to a unique value witness table. Witness tables (for protocol conformances) aren't unique, and are only available with generics that have that conformance as a constraint. They aren't part of unconstrained existential (Any or Any.Type) or passed to an unconstrained generic function or type.

Great, that's how the implementation works today, and I agree that it's the right one.

I don't think this semantics works well. Let's extend our module A (the one that defines X) to also have a global array of X's:

public var excessArray: [X]

Now modules B and C, both of which have conformances of X: Hashable, append some elements of type X to excessArray with excessArray.append(X()). Based on your response over here, I think this is supposed to be well-formed (i.e., we allow both X instances to be in the same [X]), but then what? Do we track which X values used B's definition of Hashable and which X values used C's definition of Hashable so that as? can operate accordingly? Does it mean that the conditional conformance of [X] to Hashable should be contingent on all of the values in the array having the same Hashable conformance?

As I've said before, implementability looms large, and a lot of the ideas that have been tossed around in this space are dead-ends from an implementation point of view. Run-time performance, code size, and the existing ABI are all constraints on the possible semantics. It doesn't matter whether you discuss them in terms of unimplementable semantics or an unworkable implementation sketch, the same problems creep up because they are the product of real constraints. @jrose immediately pointed out issues with the implementation that (re-)started this discussion; I've tacked on more problem's I've seen.

I think it is a fundamental problem with the "scoped conformances" design and implementation you've pitched that that values are intended to capture conformances. Semantically, I think it's a problem because values get mixed together and transformed in various ways and you have no idea which transformations are supposed to preserve/change the set of conformances attached to that value. From an implementation standpoint, I think it's a problem because the code size of protocol conformances is already an issue for binary size (the WebAssembly folks are seeing this a lot) and adding on more tables of conformances per call-site would be make it unacceptably worse.

I think the most effective way to tackle this discussion is by talking about the design and examples, with implementers weigh in when we've strayed into "unimplementable" territory, but that only works if others accept that the implementers are trying to be helpful, or if they learn enough of the implementation to validate those claims themselves.

Doug

6 Likes

Doug, thank you for taking the time both to point me in the right direction and to provide an education along the way. Much appreciated.

@Douglas_Gregor Thank you for this! Just to clarify one point, if I do something like nm something.o | xcrun swift-demangle to look at the stuff in the binary, the protocol conformance descriptor is the thing that connects a runtime type to a protocol (where everything after the word descriptor is in really general terms), right? And that's at the conforming runtime type->protocol level (not at the individual method/property level or something more or less specific?)

So in a running program the possible mappings from a runtime type to a protocol is the set of those in memory at a given time. If I were in lldb and figured out a way to dump them out I could see the actual from-runtime-type-to-protocol mappings live. Then dynamic-loading another binary would change the state of the possible mappings live, right?

As you said, there's a lot going on with a lot of similar names and I'm trying to keep them straight, mostly by writing everything down as I figure it out. Thanks again!

Great, let's do that! As for understanding the implementation and its constraints, I have made an effort, both over the years and in recent weeks. It's certainly to the point that when I look through those resources, I'm not learning much of relevance to the issues being discussed here.

Yeah, when I wrote that I just wasn't expecting the non-uniformity I've since come to grasp: that

  • Set<A.X>” can mean N different types, but
  • A.X” can only mean one type.

IMO that's not just surprising, but problematic for producing coherent semantics, which is why I have proposed this alternative model for type identity.

Witness tables (for protocol conformances) aren't unique, and are only available with generics that have that conformance as a constraint. They aren't part of unconstrained existential ( Any or Any.Type ) or passed to an unconstrained generic function or type.

Just for the record, I already understood that.

Simply put, if the type of any and the local meaning of Set<X> are distinct, the cast fails.

Great, that's how the implementation works today, and I agree that it's the right one.

In my alternative model, it's only slightly different. The cast fails iff:

  • The nominal type identity of the thing stored in any is not Set<X>, or
  • The conformance set of any conflicts with the conformance set of a locally created Set<X>.

No.

Does it mean that the conditional conformance of [X] to Hashable should be contingent on all of the values in the array having the same Hashable conformance?

Yes, but not in a way that implies checking the elements. In any given scope, it's not possible for them to have different Hashable conformances, because X only has a single conformance to Hashable in any given scope.

Run-time performance, code size, and the existing ABI are all constraints on the possible semantics. It doesn't matter whether you discuss them in terms of unimplementable semantics or an unworkable implementation sketch, the same problems creep up because they are the product of real constraints.

I have no interest in a discussion that doesn't eventually account for real-world constraints, which keep all of us honest. However, I hope you'll forgive me if I think some of the nay-saying is the product of a failure to accord me due credit for understanding and—to some extent—a lack of imagination. I've had more than my share of experiences around Swift, including recently, where that has turned out to be the case. And again, I'm not pointing any fingers; I don't think communication about hard issues like these necessarily goes any more smoothly in other communities.

I think it is a fundamental problem with the "scoped conformances" design and implementation you've pitched that that values are intended to capture conformances.

Only existential values in any meaningful sense. If you thought otherwise, you've misunderstood what I suggested. Conformances travel around with values through generic contexts today, but they become decoupled from those values when the corresponding generic constraints disappear. The same thing happens in the model I proposed.

Semantically, I think it's a problem because values get mixed together and transformed in various ways and you have no idea which transformations are supposed to preserve/change the set of conformances attached to that value.

That already applies to existentials.

From an implementation standpoint, I think it's a problem because the code size of protocol conformances is already an issue for binary size (the WebAssembly folks are seeing this a lot) and adding on more tables of conformances per call-site would be make it unacceptably worse.

Not that I'm interested in pressing for any particular implementation at this point, but just so you understand that even from the beginning, I haven't been simply ignoring that issue:

  • It's my understanding that we currently pass a set of witness tables on the stack to every generic call
  • At least for targets where ABI stability is not an issue, which I presume to include WebAssembly, we could immediately stop doing that because the conformance table would be available through type metadata.
  • I admit that I haven't thought through whether those overheads can be eliminated for ABI-stable platforms without a hard ABI break, though I suspect it may be possible to do something for code that doesn't need to back-deploy.

I think the most effective way to tackle this discussion is by talking about the design and examples, with implementers weigh in when we've strayed into "unimplementable" territory, but that only works if others accept that the implementers are trying to be helpful, or if they learn enough of the implementation to validate those claims themselves.

I have no doubts about all participants' good intentions, Doug, and I hope you'll accept that I'm trying to learn all about the implementation so we can be on the same page. As I said, I think if there are relevant facts I don't understand at this point, it's down to a very few details. It's hard to focus on a talk or document where you already know most of what's being said, but I'm willing to set set aside the time to go through each of those resources in detail if you think it will make a difference.

1 Like

Yes, a protocol conformance descriptor maps 1:1 with a conformance as stated in (or implied by) the source code. So for something like:

extension Array: Equatable where Element: Equatable { ... }

The protocol conformance descriptor will note that Array is conforming to Equatable, but it also includes all of the conditional requirements for that conformance (Element: Equatable), the module in which that conformance was written, and the witness information needed to create a witness table for a given instantiation of Array. If you're into C++, you can see the data structure here.

Yes. I think the new swift-inspect tool can help you see this information.

Doug

Thank you again! I will read through the compiler source. I build swift-inspect once back when it was a pull request but I have to get it built again and run it through some stuff I'm working on.

Sure, we can say that X only has a single conformance to Hashable in a given scope (or it's an ambiguity error). But values get passed from one scope to another, so as far as I can tell, the meaning of Hashable for a given value can change through the life of the program.

Part of my confusion with your model comes from the uniqueXs example, which I've sorta duplicated in excessArray (oops). I inferred from your discussion there that your proposed design somehow addresses the problem in that example, but I don't see how that can be the case. The conformance table will be "lost" as soon as you add an element to excessArray. Is my understanding correct? If so, that seems like this design is suffering from the same problems we have now with algorithm specialization, where code behaves one way within a generic context (it maintains the conformances from the scope where we went from concrete to generic/existential) and a different way within a concrete context (it uses the conformances in the current scope). Is that an accurate statement?

Doug