An Implementation Model for Rational Protocol Conformance Behavior

@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

I feel like 90% of this thread is over my head but this in particular I think I understand: In theory the meaning could change from scope to scope throughout different modules of the program, but wouldn’t this only happen if the programmer had conformed a type they don’t own to a protocol they also don’t own, which is something that we have long warned was risky?

Sure, but I think the point of this thread is to given this case a well-defined semantics.

Doug

Can this behavior/problem be changed/fixed without changing the behavior of existing code? (Please let us know if you want to keep the discussion here focused, without non-expert questions like this.)

We don't have a solution yet, so we don't know.

Doug

Yes, just as today when you take an X value out of a Set<X>, pass it across a boundary where X: Hashable is unknown, and stick it into a Set<X> with distinct type identity (as defined today).

Simpler example; according to your descriptions I think this would work today:

// Module A
public struct X {}

// Module B
extension X: Hashable { ... }
// Module B1
import B
getX() -> X { let b = Set(X()); return b.first! }

// Module C
extension X: Hashable { ... }
// Module C1
import C
setX(_ x: X) -> X { let c = Set(x) }

// Module D
import A
import B1
import C1
setX(getX())

As I understand it, the local variables b in B1 and and c in C1 are distinct types, using different X: Hashable conformances. Yet an X from one set gets returned from B1.getX() and passed into C1.setX(_), where it has a different Hashable conformance. I claim this is fine, because in D, where the passing happens, hashing an X has no meaning, so there's nothing B1.getX() can meaningfully promise to its clients about the thing it returned that would be violated by a different notion of X: Hashable.

I think it does.

  • B.uniqueXs has nominal type identity [X] with a conformance set containing the X: Equatable conformance from B.
  • In C, [X] has a the same nominal type identity, but its conformance set contains the X: Equatable conformance from C.
  • The two conformance sets conflict, so the extension declared for [X] in C doesn't apply to the [X] coming from B, and on the last line of D, B.uniqueXs.doSomething()is a compilation error.
  • B.uniqueXs.containsDuplicates() on the 2nd to last line of D would certainly be fine and return false if we could hide C's X: Equatable conformances (e.g. if it was internal). I think we can also allow it if the conformances are public, but don't hold me to that!

Note that because there are no existentials involved, all this information is available at compile-time, when it needs to be.

Not quite; your example is a little spare, but let me try…

The conformance set is in the type system and used to determine type compatibility, which, for any given types should be determinable at compile time. The conformance table is part of my implementation model—which I'm not sure we really want to discuss, but since you asked—it expresses a superset of what's in the conformance set, both because we probably don't want to be dynamically rebuilding this table every time a type leaves a relevant conformance scope, and so that existential dispatching works “correctly” (per me). You don't “lose” the whole conformance table just because an instance of a type crosses a conformance scope boundary, but conformances that aren't visible on the destination side of that boundary aren't part of the conformance set.

You could say the parts of the table representing hidden conformances become irrelevant to the static type system, and are eligible to be replaced when crossing into a context with conformances that would conflict if the table was interpreted as a conformace set.

I don't think so, but if after reading this you still do, let's dig into the details and figure it out.

1 Like

Okay.

Okay, so it's the fact that uniqueXs was defined in module B that makes it such that X: Equatable cannot differ when interacting with uniqueXs.

My example with excessArray only really differs from your example in one way, which is that excessArray is in module A, where there is no notion of X being Hashable. I expected that distinction not to matter, but now it seems that it is very different in your design. Specifically, it means that excessArray can be used/modified/whatever from any module, whether that module has some notion of X being Hashable or not (or sees conflicting notions of Hashable?). Whereas your uniqueXs is only usable from those modules that use B's conformance to Hashable (and don't see a conflicting conformance. Is that correct?

Doug

1 Like

Yes, or to be a little more general, it's the fact that uniqueXs was defined where an X: Equatable conformance was in scope.

Yes, just like today.

(or sees conflicting notions of Hashable ?)

Remains to be seen whether that's actually sound, but so far I see no reason to prevent it. X: Hashable is irrelevant in the scope where excessArray is defined.

It's Equatable in that example, but yes. The uniqueness is part of uniqueXs API contract and that is defined in terms of B's X: Equatable conformance.

The principle is that:

  • When conformances conflict, it means they (potentially) describe distinct semantics.
  • Every API has a contract that describes its semantic requirements and guarantees.
  • Conformances that are unknown on either side of an API boundary can't reasonably show up in the API's contract so cannot cause a semantic problem (see internal protocols).
  • It's no problem for a type to effectively gain or lose conformances when crossing an API boundary (internal protocols again).
  • The problem occurs when an API contract is written in terms of a conformance and the two sides of the API boundary (potentially) disagree about the semantics of that conformance.

Make sense?

1 Like