C++ function template specialization and generic functions in Swift

[zoecarver]

I don't have time to respond to all your points right now :) But here are a few thoughts.

Depends which of the several C++ meanings for “specialization” you intend . That's why I am using the word “concretization” instead to refer to a Swift generic type or function with all of its generic parameters replaced by concrete types.

I'm talking about the opposite. I'm talking about a full specialization. Or an overloaded definition of a class template.

Unconditional extensions should apply to all concretizations. Conditional extensions should apply according to their conditions.

This might be the most reasonable way to implement this. But it makes less sense when the full "specialization" (not concretization) is an entirely different type than the "templated version". (For example, X<int> vs X<void>.)

I imagine we'll want to be able to write a conformance of std::vector to Sequence for all Ts, don't you?

Yeah, I didn't do a good job describing what I mean. When we have a full specialization of a class template with a different definition, you would be forced to extend that type explicitly. So for the example (with struct A) A<char> would get extended with extension A: Y {} so would A<Foo> and A<std::vector<int>> but A<int> would not because it has a fully "specialized" (or overloaded) definition.

So extension std::vector : Sequence would mean std::vector would always be a Sequence (oops... well... not std::vector<bool> )

@dabrahams

Our conclusion was that a Swift generic using X must assume, in general, that X has no knowable API. The point of XManualModel is to provide a declaration of the common API shared by all specializations of X (that are used by the program):

protocol XManualModel { associatedtype Y: DefaultConstructible }
extension X: XManualModel {} // checked in phase 2 for each X concretization used

func g<X1: XManualModel>(_: X1) -> X1.Y { .init() } // normal Swift type-checking
func g<T>(_: X<T>) -> X<T>.Y { .init() }  // ditto; maybe a bit more development work

I assume "normal Swift type-checking" means phase one type-checking? Without the logic above, how can this be type-checked during phase one? We can't know if T = Void until after specialization has happened. Am I missing something?

If we apply the above logic, though, this could become a phase one error. Because if T == Void is true, then the extension won't apply so X == XManualModel is false. And I don't think it's unreasonable to ask that each fully specialized (or overloaded) class template definition must be explicitly extended.

[dabrahams (Dave Abrahams)]

@zoecarver

I'm talking about the opposite. I'm talking about a full specialization. Or an overloaded definition of a class template.

Yes, Swift doesn't have anything like that today. However, I think the ability to select witnesses that @Douglas_Gregor agreed to in the thread I referenced earlier, when carried to its logical conclusion, results in similar expressive power. You can already say things like this in Swift today, but the compiler can't yet cope:

protocol P {
  associatedtype StoredProperties = Void
}

struct X<T> : P {
  var storedProperties: StoredProperties
}

extension X where T == Int {
  typealias StoredProperties = (Int, String)
}

If the compiler could handle the above code, X<Int> and X<String> would almost be completely different types. Yes, they have a “var storedProperties”, but that's about all they have in common.

Unconditional extensions should apply to all concretizations. Conditional extensions should apply according to their conditions.

This might be the most reasonable way to implement this. But it makes less sense when the full "specialization" (not concretization) is an entirely different type than the "templated version". (For example, X<int> vs X<void> .)

Seems to me it's up to the programmer to make their extensions “make sense,” just as in pure Swift code.

When we have a full specialization of a class template with a different definition, you would be forced to extend that type explicitly. So for the example (with struct A ) A<char> would get extended with extension A: Y {} so would A<Foo> and A<std::vector<int>> but A<int> would not because it has a fully "specialized" (or overloaded) definition.

I don't see why a full specialization should be treated differently from a partial specialization. In the end, it's the same problem. And I don't see any reason to create special rules for extensions applying to specializations.

So extension std::vector : Sequence would mean std::vector would always be a Sequence (oops... well... not std::vector<bool> )

? There's no problem with std::vector<bool> conforming to Sequence AFAICT.

@dabrahams

Our conclusion was that a Swift generic using X must assume, in general, that X has no knowable API. The point of XManualModel is to provide a declaration of the common API shared by all specializations of X (that are used by the program):

protocol XManualModel { associatedtype Y: DefaultConstructible }
extension X: XManualModel {} // checked in phase 2 for each X concretization used

func g<X1: XManualModel>(_: X1) -> X1.Y { .init() } // normal Swift type-checking
func g<T>(_: X<T>) -> X<T>.Y { .init() }  // ditto; maybe a bit more development work

I assume "normal Swift type-checking" means phase one type-checking?

Yes.

Without the logic above, how can this be type-checked during phase one? We can't know if T = Void until after specialization has happened. Am I missing something?

The conformance declaration of X<T> to XManualModel is checked in phase 2 for every concrete T, when the witness table for that conformance is built. If T turns out to be Void, you get the error that the program is using X<Void>, which doesn't conform to XManualModel as the second line says it must, because it is missing a nested type Y.

If we apply the above logic, though, this could become a phase one error. Because if T == Void is true, then the extension won't apply so X == XManualModel is false.

By “the above logic” you mean the logic you proposed?

FWIW, I don't believe it's possible to analyze all the specializations and visible SFINAE'd overload sets to validate a given extension of a C++ class template for all cases where the extension's conditions are met (i.e. in phase 1). But even if it were possible, because C++ templates are so ad-hoc, I don't think it's desirable. There may well be types nobody actually uses as parameters to that template for which the extension doesn't type-check. IMO it's important to be able to make general declarations in Swift about a given template, that don't hold for certain unused combinations of template parameters.

[zoecarver]

I think that maybe I'm still not quite properly expressing what my idea is. Maybe this example will help:

template <class T> struct X { using Y = T; };
template <> struct X<void> { };

// Now in Swift, I write...
protocol XManualModel { associatedtype Y: DefaultConstructible }
// What I'm proposing is the following does _not_ apply to X<Void>. 
// Either the user will get an error/fix-it saying they _must_ add 
// "where T != Void" or that will be implied and this extension will 
// only apply to the "first" struct (X<T>). 
extension X: XManualModel {}

func g<X1: XManualModel>(_: X1) -> X1.Y { .init() }
func h() -> Int { g(X<Int>()) } // Fine; type checked in phase one because there's only one "struct" we have to type check.
func h() { g(X<Void>()) } // Error: argument type 'X<Void>' does not conform to expected type 'XManualModel'. Still type checked in phase one.

// Now, I see the error above and write...
extension X where T == Void : XManualModel { }
// And I get the following errors during phase one type checking:
// Error: type 'X<Void>' does not conform to protocol 'XManualModel'
// Note: protocol requires nested type 'Y'

? There's no problem with std::vector conforming to Sequence AFAICT.

There's no problem at all. But my point is, with what I'm proposing, extension std::vector : Sequence only applies to std::vector<T> and not to std::vector<bool>. If you added extension std::vector where T == Bool : Sequence then they both would be Sequences (and so would std::vector<int> and std::vector<Foo> etc.).

FWIW, I don't believe it's possible to analyze all the specializations and visible SFINAE'd overload sets to validate a given extension of a C++ class template for all cases where the extension's conditions are met (i.e. in phase 1). But even if it were possible, because C++ templates are so ad-hoc, I don't think it's desirable. There may well be types nobody actually uses as parameters to that template for which the extension doesn't type-check. IMO it's important to be able to make general declarations in Swift about a given template, that don't hold for certain unused combinations of template parameters.

I agree. We shouldn't have the compiler do this one it's own. But when someone explicitly writes extension X where T == Void we can then go specialize X<Void> and type check it. That's why I'm suggesting we force users to write out those extensions anywhere they want to use an overloaded class template specialization in their Swift program, so we know what to type check. It works better for everyone IMO, because it also makes users less likely to write extensions for all overloads when they don't mean to.

[dabrahams (Dave Abrahams)]

@zoecarver

I think that maybe I'm still not quite properly expressing what my idea is. Maybe this example will help:

I assure you I fully understand what your idea is (or at least, nothing about your example changes my understanding of your idea). What I don't understand is

• What problem you're solving that balances the complexity cost of having nonuniform rules? You say “makes users less likely to write extensions for all overloads when they don't mean to,” but “writing extensions that apply to all concretizations when they don't mean to” is a problem people can have in Swift today, and we don't feel the need to add any special protections against it.
• Why you think that a special rule for full specializations that doesn't apply to partial specializations makes sense. I can easily write a partial specialization that effectively only applies to one concretization of the class template.

I also think there are a couple of holes in the way you're thinking about this:

• constraints like where T != Void are unlikely to ever be allowed in Swift, because they are an anti-pattern and create provable type-checking complexity explosion (with NOT and conjunctions you can create disjunctions) in the implementation.

• The h's you've written don't actually touch the cases where checking can only happen in phase 2. Try this:

  extension X: DefaultConstructible {} // just for completeness
  
  func h<T>(_: T.Type) { g(X<T>()) } // Must pass type checking in phase 1
  h(Void.self)                       // Must fail type checking in phase 2
  

[zoecarver]

I assure you I fully understand /what/ your idea is (or at least, nothing about your example changes my understanding of your idea). What I don't understand is

Fantastic, I think we're getting somewhere :)

You're right, this isn't quite as straight forward as I thought it would be . And thanks again for talking this through with me. Now let's see if I can answer these questions.

What problem you're solving that balances the complexity cost of having nonuniform rules? You say “makes users less likely to write extensions for all overloads when they don't mean to,” but “writing extensions that apply to all concretizations when they don't mean to” is a problem people can have in Swift today, and we don't feel the need to add any special protections against it.

I want to push back against this a little bit. I don't think the "problem people can have in Swift today" is quite the same. The example you gave with X<Int> and X<String> being "almost completely different types" above is compelling, but still not as common, or concretely different, as in C++.

In C++ X<Int> and X<Void> can essentially be aliased to completely different types. In Swift, it's still the same type, even if very different.

As you bring up, we can't write extension where T != Void, so without this solution, there's not really a way to extend only the non-specialized version of a class. In Swift, this is more OK because users know that fact when they write their generics. In C++, this isn't true, though. People may often write classes thinking that they can select specific specializations. We should have a way to accommodate that.

The balance, in my opinion, is two-fold. First, it seems to align more closely with how C++ operates. Second, if we could get rid of the second type-checking phase, or at least make it trivial, that would be fantastic both from a performance perspective and QoI.

Why you think that a special rule for full specializations that doesn't apply to partial specializations makes sense. I can easily write a partial specialization that effectively only applies to one concretization of the class template.

This was my bad. I shouldn't have brought up partial specializations vs full specializations. Even though I brought them up, let's forget about this distinction for a minute. I don't think it's relevant to this particular problem but there is probably some discussion around them that needs to happen.

constraints like where T != Void are unlikely to ever be allowed in Swift, because they are an anti-pattern /and/ create provable type-checking complexity explosion (with NOT and conjunctions you can create disjunctions) in the implementation.

I don't actually think we should have T != Void, that was mostly for exposition. I just wanted to make clear, this would not apply to the X<Void> overload, but it seems like that was already clear, and saying T != Void just created confusion.

Anyway, that being said, I think we could avoid the problems you bring up by requiring that T != all (and only) types that the class is specialized on. Essentially just providing clarity as to what the extension applies to. It would just be a different syntax for saying extension X where T == T or extension X<T>.

The h's you've written don't actually touch the cases where checking can only happen in phase 2. Try this:

Yes, you're right. These would technically be "phase two," but the type checking wouldn't be "go extend X<Void> and see if it works" it would be, "look up the type X<Void> and see if it has already been extended." The latter is extremely trivial and means we essentially just have to check if the argument types still match whereas the former means we have to do proper type checking of the whole extension/type.

[dabrahams (Dave Abrahams)]

@zoecarver

You're right, this isn't quite as straight forward as I thought it would be . And thanks again for talking this through with me.

Not a bit; having this kind of discussion is very helpful for me, too! Often the best solutions come from pushing at a problem from several different directions at once. So thank you, also.

What problem you're solving that balances the complexity cost of having nonuniform rules? You say “makes users less likely to write extensions for all overloads when they don't mean to,” but “writing extensions that apply to all concretizations when they don't mean to” is a problem people can have in Swift today, and we don't feel the need to add any special protections against it.

I want to push back against this a little bit. I don't think the "problem people can have in Swift today" is quite the same. The example you gave with X<Int> and X<String> being "almost completely different types" above is compelling, but still not as common, or concretely different, as in C++.

In C++ X<Int> and X<Void> can essentially be aliased to completely different types. In Swift, it's still the same type, even if very different.

Sure. But it's just a matter of degree, as far as I can tell. In Swift we can write extensions for X where T == Int and X where T == Void that add arbitrarily different API. The only thing the language really forces two concretizations of X to have in common is the names and access privileges of stored properties. By contrast, in C++, while you can make two concretizations of a class template arbitrarily different, that's still very uncommon. So this doesn't seem to me like a difference that should drive language rules.

@zoecarver

As you bring up, we can't write extension where T != Void, so without this solution, there's not really a way to extend only the non-specialized version of a class. In Swift, this is more OK because users know that fact when they write their generics. In C++, this isn't true, though. People may often write classes thinking that they can select specific specializations. We should have a way to accommodate that.

I guess I'm just not yet convinced it's important. To start with, I can't imagine any real cases where it's useful. Moreover the ability to extend a C++ class is not critical to making it usable—after all; you can't do that in C++—so this is “only” an issue of ergonomics. For me, ergonomics are very important, but less so than having a foundation that provides full access to any C++ API from Swift (and vice-versa).

One big advantage I see for the scheme I've outlined is that I can see clearly how it integrates with the Swift compilation process: conformance of each concretization of a class template is checked when its specialized witness table is built, and the rest of Swift compilation “proceeds as usual” (glossing over quite a few important details unrelated to templates). It seems obvious to me that there's no problem accessing every C++ class template API under this scheme.

I may not yet understand what you're proposing, but it sounds like it demands a way to preliminarily type-check a function and lower it to SIL, but then re-lower it to different SIL when we know the C++ class template concretizations involved. If I understand what I've been told about the compiler implementation, that clashes pretty fundamentally with how it works.

The balance, in my opinion, is two-fold. First, it seems to align more closely with how C++ operates. Second, if we could get rid of the second type-checking phase, or at least make it trivial, that would be fantastic both from a performance perspective and QoI.

The second type-checking phase is a feature of how C++ operates. I'd love to get rid of it, but you can't instantiate C++ templates without it.

My inclination, FWIW, is to try to do something that's as close as possible to how Swift operates, because overall I consider Swift to have a more comprehensible and useful generics system, and I hope that C++ interoperability leads to people adopting Swift's mental model.

Anyway, that being said, I think we could avoid the problems you bring up by requiring that T != all (and only) types that the class is specialized on. Essentially just providing clarity as to what the extension applies to. It would just be a different syntax for saying extension X where T == T or extension X<T>.

Yes, and then we're back to partial specializations. It isn't possible to know whether a given category of generic parameters in Swift will match arbitrary partial specializations.

func f<T: SomeConstraint>(_:T) {
   print(X<T>.Y.self) // compile or not?
}

The h's you've written don't actually touch the cases where checking can only happen in phase 2. Try this:

Yes, you're right. These would technically be "phase two," but the type checking wouldn't be "go extend X<Void> and see if it works" it would be, "look up the type X<Void> and see if it has already been extended."

I understand what you're saying, and I see how it works for full specializations, but I don't see how it works for partial specializations.

Maybe I've been thick… are you suggesting treating every full or partial specialization of a C++ class template as a completely separate type?

The latter is extremely trivial and means we essentially just have to check if the argument types still match whereas the former means we have to do proper type checking of the whole extension/type.

I suppose I could be wrong, but I assume that we already have code for checking conformance of a concrete type to a protocol, so I'm not worried about implementability. I guess you're worried about compiler performance?

[zoecarver]

Not a bit; having this kind of discussion is very helpful for me, too! Often the best solutions come from pushing at a problem from several different directions at once. So thank you, also.

Sure. But it's just a matter of degree, as far as I can tell. In Swift we can write extensions for X where T == Int and X where T == Void that add arbitrarily different API. The only thing the language really forces two concretizations of X to have in common is the names and access privileges of stored properties. By contrast, in C++, while you can make two concretizations of a class template arbitrarily different, that's still very uncommon. So this doesn't seem to me like a difference that should drive language rules.

Fair enough. It's a matter of degree. We'll let the other points drive the decision.

I guess I'm just not yet convinced it's important. To start with, I can't imagine any real cases where it's useful. Moreover the ability to extend a C++ class is not critical to making it usable—after all; you can't do that in C++—so this is “only” an issue of ergonomics. For me, ergonomics are very important, but less so than having a foundation that provides full access to any C++ API from Swift (and vice-versa).

Well, if you want to use a class template with generics, I think it's essential. Otherwise, there's no way to show protocol conformance, so generics aren't really useful.

One big advantage I see for the scheme I've outlined is that I can see clearly how it integrates with the Swift compilation process: conformance of each concretization of a class template is checked when its specialized witness table is built, and the rest of Swift compilation “proceeds as usual” (glossing over quite a few important details unrelated to templates). It seems obvious to me that there's no problem accessing every C++ class template API under this scheme.

I'm weighing the complexity of adding this special case for extending C++ types vs. QoI, performance, and depending on how the above comment is resolved, the ability to use specialized C++ types with generics. If performance is the only issue, I agree, we should follow your scheme. But I think either of the other two might warrant the complexity.

The second type-checking phase is a feature of how C++ operates. I'd love to get rid of it, but you can't instantiate C++ templates without it.

We might need some vocab around this. I think we're all in agreement that "C++ type checking" needs to happen in "phase two" but I'm saying I'd like to mitigate/remove as much Swift type checking as possible. And ideally, the most we'd do is just check that we have protocol conformance/the correct argument types.

Maybe I've been thick… are you suggesting treating every full or partial specialization of a C++ class template as a completely separate type?

Yes, that is exactly what I'm suggesting. Though, now that you say it, maybe we don't have to do it that way. Interesting, I'll think about that a bit. Somehow that never occurred to me.

@dabrahams

I suppose I could be wrong, but I assume that we already have code for checking conformance of a concrete type to a protocol, so I'm not worried about implementability. I guess you're worried about compiler performance?

Well, if we're instantiating a new, never before seen to the Swift compiler concretization, we need to do full type checking of that type, I think. Not just protocol conformance checking. But, if we've forced a user to create that type before, then we can just load the "cached" version.

[dabrahams (Dave Abrahams)]

@zoecarver

I guess I'm just not yet convinced it's important. To start with, I can't imagine any real cases where it's useful. Moreover the ability to extend a C++ class is not critical to making it usable—after all; you can't do that in C++—so this is “only” an issue of ergonomics. For me, ergonomics are very important, but less so than having a foundation that provides full access to any C++ API from Swift (and vice-versa).

Well, if you want to use a class template with generics, I think it's essential. Otherwise, there's no way to show protocol conformance, so generics aren't really useful.

Maybe we're talking about a different “it” in this case. I meant that it wasn't clear to me that having “a way to extend only the non-specialized version of a class” is important. “My” scheme (short for ”what I came up with Google colleagues“) doesn't provide for that and yet I think it clearly allows one to “use a class template with generics.” So what are you saying is essential?

One big advantage I see for the scheme I've outlined is that I can see clearly how it integrates with the Swift compilation process: conformance of each concretization of a class template is checked when its specialized witness table is built, and the rest of Swift compilation “proceeds as usual” (glossing over quite a few important details unrelated to templates). It seems obvious to me that there's no problem accessing every C++ class template API under this scheme.

I'm weighing the complexity of adding this special case for extending C++ types vs. QoI, performance, and depending on how the above comment is resolved, the ability to use specialized C++ types with generics. If performance is the only issue, I agree, we should follow your scheme. But I think either of the other two might warrant the complexity.

It's good that you're weighing all those factors. FWIW, though, I don't see it as a special case. Remember that because of SFINAE and the way template member functions work, even without any specializations, the API of two concretizations of a class template can look (almost?) arbitrarily different. If the template is declared to conform to a protocol, each concretization needs to have its own witness table to be generated, and I don't see a way of building that witness table without doing the work of matching up types to the signatures of the requirements, which is the type checking work I'm talking about.

The second type-checking phase is a feature of how C++ operates. I'd love to get rid of it, but you can't instantiate C++ templates without it.

We might need some vocab around this. I think we're all in agreement that "C++ type checking" needs to happen in "phase two"

Just be 100% sure we're on the same page, C++ type-checking has two phases. Phase 1 can happen along with regular Swift type checking, but phase 2 depends on monomorphization.

but I'm saying I'd like to mitigate/remove as much Swift type checking as possible. And ideally, the most we'd do is just check that we have protocol conformance/the correct argument types.

I'm sorry, I'm confused, because “check that we have protocol conformance” is exactly what I'm saying needs to happen in phase 2.

Maybe I've been thick… are you suggesting treating every full or partial specialization of a C++ class template as a completely separate type?

Yes, that is exactly what I'm suggesting. Though, now that you say it, maybe we don't have to do it that way. Interesting, I'll think about that a bit. Somehow that never occurred to me.

I guess because of the SFINAE I mentioned earlier I don't see what that buys us.

Well, if we're instantiating a new, never before seen to the Swift compiler concretization, we need to do full type checking of that type, I think. Not just protocol conformance checking.

Sure. Aside from extensions, that's just regular C++ type-checking. And because in “my” scheme the class template by itself has no knowable API absent a concretization, all of the knowable API from Swift's point of view depends on the declared protocol conformances. That means we are just left with checking the conformance.

But, if we've forced a user to create that type before, then we can just load the "cached" version.

Yes, I'm sure we all take it for granted that the compiler will memoize all of the work associated with any given concretization.

[zoecarver]

I'm starting to come around to "your scheme." Just a few more clarifications.

@dabrahams

Maybe we're talking about a different “it” in this case. I meant that it wasn't clear to me that having “a way to extend only the non-specialized version of a class” is important. “My” scheme (short for ”what I came up with Google colleagues“) doesn't provide for that and yet I think it clearly allows one to “use a class template with generics.” So what are you saying is essential?

For

template <class T> struct X { using Y = T; };
template <> struct X<void> { using Z = char; };

protocol XManualModel { associatedtype Y: DefaultConstructible }

IIUC extension X: XManualModel {} will mean that X<Void> is essentially unusable. Is the correct?

@dabrahams

Sure. Aside from extensions, that's just regular C++ type-checking. And because in “my” scheme the class template by itself has no knowable API absent a concretization, all of the knowable API from Swift's point of view depends on the declared protocol conformances. That means we are just left with checking the conformance.

Hmm, I guess I thought we'd have to do more "Swift type checking." Could you walk me through how you're proposing we import and type-check the following case (and call it with Int.self and Void.self)?

template<class> struct X { int x; };
tempalte<> struct X<void> {}; 

func test<T>(_ T.Type) -> Int32 { X<T>().x }

Or maybe to make it more "real world" an equivilant program:

func getFront<T, N>(arr: std::array<T, N>) -> T { arr.front() }

If N == 0 then .front() may not exist.

Yes, I'm sure we all take it for granted that the compiler will memoize all of the work associated with any given concretization.

I'm saying something slightly different, in what I'm proposing, the compiler would have to already have "memorized" a given concretization in order for it to be instantiated. That's how I suggest we prevent later type checking.

[dabrahams (Dave Abrahams)]

@zoecarver

For

template <class T> struct X { using Y = T; };
template <> struct X<void> { using Z = char; };

protocol XManualModel { associatedtype Y: DefaultConstructible }

IIUC extension X: XManualModel {} will mean that X<Void> is essentially unusable. Is the correct?

Not necessarily. Because X<void> is a full specialization, it can be completely type-checked in phase 1 (as it would be in plain C++) and I see no problem with allowing:

typealias Char = X<Void>.Z

to compile in Swift.

But as the code stands, using X<Void> as an XManualModel must to fail to compile, and in “my” scheme that would happen in phase 2 when the conformance to XManualModel is validated as part of creating the witness table.

Aside

Of course you could always do something like this to make it conform:

extension X where T == Void { typealias Y = Int }

In fact, the use of any full concretization of X can be type-checked in phase 1 without XManualModel. So

typealias Unsigned = X<UInt>.Y

Should work the same way as the X<Void> example. It's just cases where the concretization of X depends on a generic parameter, like

struct A<T> { typealias B = X<T>.Y }

that can't be allowed to compile without a conformance declaration (e.g. X : XManualModel) that describes the API we should expect to find on concretizations of X, because there is no other reliable guide to what that API is supposed to look like.

Could you walk me through how you're proposing we import and type-check the following case (and call it with Int.self and Void.self )?

template<class> struct X { int x; };
template<> struct X<void> {}; 

func test<T>(_: T.Type) -> Int32 { X<T>().x }

This is a case where the concretization of X used by test depends on a generic parameter of test, so we can't compile test without a declaration of X's conformance to some protocol, describing the API X has for the concretizations used by test.

If you change test so it doesn't access a member, you can add

extension X: DefaultConstructible {}

and successfully compile the first part of the return expression for Int.self and Void.self. To access the member x, you need something like:

protocol XProtocol: DefaultConstructible { var x: Int {get} }
extension X: XProtocol {}

And then everything compiles unless monomorphization (phase 2) encounters X<Void> being used as XProtocol, at which point the conformance check fails.

As a user, there are lots of ways to deal with that scenario. For example, you could instead have written

extension X: XProtocol where T: Equatable {}
func test<T: Equatable>(_: T.Type) -> Int32 { X<T>().x }

Which, because Void is not Equatable, compiles fine and makes the error happen earlier.

Or maybe to make it more "real world" an equivilant program:

func getFront<T, N>(arr: std::array<T, N>) -> T { arr.front() }

If N == 0 then .front() may not exist.

Non-type generic parameters gets us into a whole new feature set that will be needed by Swift, and with them, I expect where clauses with inequalities and various other generic features, so you'd write something like:

func getFront<T, N>(arr: std::array<T, N>) -> T where N > 0 { arr.front() }

protocol StdArrayProtocol {
  ...
  var front: T where N > 0 { get } 
}

extension CxxStd.Array: StdArrayProtocol {}

I realize numerical inequalities present similar problems for the type checker as type inequalities, and I don't have an answer to that argument at the moment.

Yes, I'm sure we all take it for granted that the compiler will memoize all of the work associated with any given concretization.

I'm saying something slightly different, in what I'm proposing, the compiler would have to already have "memorized" a given concretization in order for it to be instantiated. That's how I suggest we prevent later type checking.

Sorry, it still sounds to me like we're saying the same thing. That's a standard technique used in C++ compilers and the Swift compiler, IIUC.

[zoecarver]

OK, I think I'm on board with "your scheme" now. I understand how it all fits together. There are some things that are... unideal. But I think it's as good as we're going to get while trying to marry these inherintly contradictory models.

The scheme you propose fit's better with Swift's generic model, and people migrating C++ to Swift probably like that model, so I think it's a good idea to try to match it as much as possible.

I was thinking that forcing specialization conformance was a "problem" to be solved, but actually, I think it's a feature. It forces people to write more expressive APIs.

If we can all agree that this is the correct path forward, we can start discussing more of the implementation details. Such as how we should represent concretizations and specializations in this model, and how much we want to lean on automatically generated protocols (we might need something like this for inheritance anyway).

---

@dabrahams

Not necessarily. Because X<void> is a full specialization, it can be completely type-checked in phase 1 (as it would be in plain C++) and I see no problem with allowing:

typealias Char = X<Void>.Z

to compile in Swift.

But as the code stands, using X<Void> as an XManualModel must to fail to compile, and in “my” scheme that would happen in phase 2 when the conformance to XManualModel is validated as part of creating the witness table.

I guess the problem I was bringing up is that X<Void> would always have a phase-two type-checking error because it doesn't conform to XManualModel. But, I think the solution you bring up later, requiring extension X: XManualModel where T: Equatable might be a sufficient solution (I forgot something like this could work).

Non-type generic parameters gets us into a whole new feature set that will be needed by Swift, and with them, I expect where clauses with inequalities and various other generic features, so you'd write something like:

Let's leave non-type generic parameters for another discussion (I know I brought them up, but I'm not sure I have the mental capacity to handle both this and the other discussion points in this thread).

@dabrahams

Yes, I'm sure we all take it for granted that the compiler will memoize all of the work associated with any given concretization.

I'm saying something slightly different, in what I'm proposing, the compiler would have to already have "memorized" a given concretization in order for it to be instantiated. That's how I suggest we prevent later type checking.

Sorry, it still sounds to me like we're saying the same thing. That's a standard technique used in C++ compilers and the Swift compiler, IIUC.

No, I'm saying that the compiler must have already memorized the concretization in phase-one type checking before the type could be concretized with a generic argument. Currently, I think compilers use that when possible, but if they need to create a new type, they won't error if they haven't seen it before. I had thought that would remove the need for some type checking in phase-two, but I actually don't think that it gives us anyting anymore. And it adds a lot of complexity/weirdness.

[dabrahams (Dave Abrahams)]

@zoecarver

OK, I think I'm on board with "your scheme" now. I understand how it all fits together.

Lovely!

There are some things that are... unideal.

Indeed. I hope they can be mitigated once we have a solid foundation in place (scoped conformances would support some useful mitigation strategies, BTW).

I was thinking that forcing specialization conformance was a "problem" to be solved, but actually, I think it's a feature. It forces people to write more expressive APIs.

If I understand you correctly, I agree. If we buy the idea that Swift's generic programming model is a good thing™, and derives some of that goodness™ from generic constraints and explicit conformance declarations, I have no problem saying they may be needed in order to use dependently-typed C++ templates from Swift generics.

If we can all agree that this is the correct path forward, we can start discussing more of the implementation details. Such as how we should represent concretizations and specializations in this model, and how much we want to lean on automatically generated protocols (we might need something like this for inheritance anyway).

I'm ready!

FWIW, I don't think we can expect the compiler to generate the right protocols automatically in all cases, and I'm not sure I know how to do even a decent job, so I'd prefer to start by building code generation helper tools (like some of Xcode's refactoring functionality) that spit out something the programmer can use as a starting point. I also view exploring in that area as a completely separable, relatively low-priority task.

I'm not sure what you have in mind regarding inheritance, though.

Let's leave non-type generic parameters for another discussion (I know I brought them up, but I'm not sure I have the mental capacity to handle both this and the other discussion points in this thread).

Yes please, sir!

No, I'm saying that… but I actually don't think that it gives us anyting anymore. And it adds a lot of complexity/weirdness.

I'm afraid I still don't understand, but it sounds like you're saying it's not worth pursuing. If you change your mind, LMK and we can try again.

[zoecarver]

I'm ready!

Sorry for the slow response. Hopefully, nobody else wanted to weigh in with arguments against "your scheme." Anyway, let's proceed by clarifying some things brought up earlier.

If you're asking about it as a short-term step toward full interoperability, though, I say again, "whatever works!"

While this isn't what might be implemented at first, I think we should at least discuss the long-term plans before we even start implementing short-term steps so that we don't accidentally start off in the wrong direction altogether.

Just be 100% sure we're on the same page, C++ type-checking has two phases 3 . Phase 1 can happen along with regular Swift type checking, but phase 2 depends on monomorphization.

OK let's discuss these type checking phases one more time to make sure we're on the same page.

Phase one is the current Swift type-checking phase. And this phase includes non-dependent C++ type checking but does not include name lookup of templates that aren't "trivially concreted."

The second type-checking phase happens after monomorphization and is where we concretize templates based on Swift generic concretization of types higher up in the call stack. Any Clang type-checking errors or warnings are propagated up to the user. And conformance is checked by the Swift compiler for any newly monomorphed types.

Now on to the question of whether each concretization of C++ types and functions should be its own type or not.

Currently, there is no guarantee that a generic Swift function is concretized into a new "specialization" of that function. Whereas, in C++, every function template is just that, a template. So a copy is made for each set of type substitutions.

We need to decide how much of the time we want to make new concretization for each set of type substitutions. I propose we follow C++ in this regard and always create a new specialized function (or concretization). Later on, we can introduce a more dynamic solution that may benefit code size.

As for generic types, I don't think Swift ever creates separate concretizations (I could be wrong, though). In my opinion, this is a bit less cut and dry. But I again suggest we do the same thing as C++ and create a new type for each concretization. Otherwise, there are types I'm not sure we could properly import and concretize.

What I meant to say is "for any C++ templates that are able to be imported as Swift generics". What can and cannot be imported as a Swift generic is out of the scope of this proposal.

I understand. What /I'm/ saying is that I'm not sure there exists a C++ template that can sensibly be imported as a Swift generic. The properties of Swift generics are just very different from those of C++ templates, and thinking of them as one thing (and especially representing them as one thing in the compiler) may not make sense.

Just to be clear, I'm only talking about using generics as, essentially, a way to represent the syntax of supplying type substitutions to a C++ template. If not with generics, how would you suggest we implement this?

Something that I've hardly mentioned, but that I should probably clarify, is that I think we're going to need to treat generic and protocols very similarly. That is, we won't be able to have un-concretized functions that have arguments with protocol types. And therefore we can't allow functions with arguments with protocol types to be public.

[dabrahams (Dave Abrahams)]

@zoecarver sorry I never responded to this, and I don't know where you're at with this project, but I thought of a way to get substantial interop between Swift generics and C++ templates without delaying all checking to monomorphization time and without a lot of conformance declarations to constrain the C++. LMK if you'd like to pick up the discussion somewhere.

[zoecarver]

No worries. I'd love to hear what you're thinking, that sounds awesome. Want to discuss here? (I can also create a new thread if you'd like.)

For the record, I have this patch and this post describing what I think the best next steps are for function templates. This might not be the long term strategy, but I think it will help move us forward for the time being (and might be used with future designs).

[dabrahams (Dave Abrahams)]

Basically what you want to do is instantiate the templates on archetypes (synthesized types that minimally satisfy the properties you know hold, inside the Swift generic, about the template arguments). I'd be surprised if the Swift generics typechecker wasn't already using archetypes of some kind to do its work. if that works, you can say the generic typechecks as-is. It doesn't get you out of having to monomorphize and instantiate the template to make sure it still gives a consistent result, but what it does is allow you to avoid assuming, e.g., that all class templates are empty unless you have a bunch of supporting hand-written Swift conformance declarations to tell you what conclusions the generics system can draw. Those will still be necessary for some cases, certainly, but this means you get a lot more interop without making the user do any work.

From what I understand from my better-educated friends, this is System 𝐹𝜔, with templates playing the role of type operators, and instantiation on archetypes playing the role of symbolic execution.

HTH,
Dave

[zoecarver]

Sorry for such a delayed response. I've gotten pulled away to implement C++20 ranges, so I don't have as much time for Swift as I would like. Anyway...

IIUC, you're suggesting that we convert protocols to archetypes so that we can type check conditional conformance (or any conformance) of class templates to another protocol?

If we bring back the equatable example,

// C++
template<class> struct X { int x; };
template<> struct X<void> {}; 
// Swift
extension X: XProtocol where T: Equatable {}
func test<T: Equatable>(_: T.Type) -> Int32 { X<T>().x }

Here Equatable would be converted into an archetype which we'd use to instanciate X and see if it worked?

This does seem to solve our problem quite nicely. Thanks for the update. I'll keep playing around with this, but I think it may very well be a viable solution.

Zoe

[zoecarver]

I suppose the problem is when we have plain-old protocol conformance to an explicitly-specialized class template. For example, what if we removed the where clause?

// C++
template<class> struct X { int x; };
template<> struct X<void> {}; 
// Swift
extension X: XProtocol {}
func test<T>(_: T.Type) -> Int32 { X<T>().x }

Now our archetype is an empty struct struct {} which still picks the unspecialized class template, so this compiles. But T could also be any primitive: Int, Void, etc. that would convert into a non-class type. A bad solution would be to instantiate all non-conditional protocol conformances with an empty struct and all primitive types we know about (in this case, when we instantiated X with void, protocol conformance would fail with an error along the lines of "when T is void X does not conform to XProtocol"). That would be terrible for compile time, but it would be potentially do-able.

Any thoughts on a better way to solve this?