Bridging C++ Templates with Interop

Bridging Generic APIs

In this post I'm going to lay out how I propose we bridge generic C++ APIs to Swift.

Refresher

If you’re already familiar with both Swift generics and C++ templates, feel free to skim this section and move on to "Goals."

C++ Templates

In C++ templates can be used for generic programming. Templates, as their name suggests, are a feature that allows users to create a syntactic template for either a function or class which essentially allows the caller to perform textual substitution of various types. These are not too far away from C macros, but are substantially more complicated powerful.

Let’s look at an example:

template<class T> void play(T t) { t.play(); } 

Here we have a simple C++ function template. It takes an argument t and calls play on it.

struct Horn { void play(); };
struct Bell { void play(); };
struct Rock { /* This struct is empty. */ };

play(Horn());
play(Bell());
play(Rock());

We can call play with any type. Above, we call play with three different types: Horn, Bell, and Rock. The compiler will create a specialization of play for each type that it’s called with. For example, the compiler might generate some code like this when compiling the above snippet:

void play(Horn t) { t.play(); }
void play(Bell t) { t.play(); }
void play(Rock t) { t.play(); } 

Notice that the generated (specialized) functions are not templates. Also note, this isn’t great for code size, even though most templates are inlined.

However, if you try to compile this, you’ll actually get an error. The last specialization of play is invalid because Rock does not have a play method. Because types are substituted in from top to bottom, you often see hard-to-understand errors that are deep inside library code in C++:

<source>:1:38: error: no member named 'play' in 'Rock'
template<class T> void play(T t) { play(); }
                                   ~ ^
<source>:2:39: note: in instantiation of function template specialization 'test<Rock>' requested here
template<class T> void caller2(T t) { play(t); }
                                      ^
<source>:3:39: note: in instantiation of function template specialization 'caller2<Rock>' requested here
template<class T> void caller3(T t) { caller2(t); }
                                      ^
<source>:7:5: note: in instantiation of function template specialization 'caller3<Rock>' requested here
    caller3(Rock());
    ^
1 error generated.

To sum up, templates are:

  1. Textual replacements (or specializations).
  2. Specialized at compile time.
  3. Template types are not constrained, therefore templates themselves are not type checked.
  4. No performance overhead.

Swift Generics

Let’s write a generic Swift function that does the same thing as our C++ function template:

func play<T>(_ t: T) { t.play() }

This looks pretty much the same as our C++ function template but there are some key differences. First, when we try to compile this, we actually get an error: value of type 'T' has no member 'play'. To resolve this error, we must explicitly call out what requirements we are imposing on T. In this case, we are requiring that T has a method called play. So, to resolve this error, we add a protocol Player and constrain T to be a Player:

protocol Player {
    init()
    func play()
}

func play<T: Player>(_ t: T) { t.play() }

Protocols allows our swift generic to be type safe and verified at the call site which means the compiler no longer need to specialize play at compile time (which is better for code size among other things).

This is a really big deal and one of the primary reasons that the Swift generics model works so well. When the Swift compiler forces users to express all the requirements of a generic in the function signature, it allows Swift generics to be expressive and type safe making them much easier and safer to use. It also means we never get the 20 call deep substitution failures that C++ programmers know and love (see above).

To sum up, generics are:

  1. Checked without specialization.
  2. Constrained with protocols.
  3. Can be called through library boundaries and at runtime.

Goals

  • Import as many C++ APIs as possible (support APIs that don't fit in the Swift model).
  • Preserve the semantics that APIs are written with:
    • Some generic C++ APIs expect concrete types (for example, they might static assert or call non-template code using a template type).
    • Some generic APIs use template type parameters in very textual way (such as constructing, initializing, or destructing them manually).
  • Preserve C++ performance by default:
    • Boxing is unacceptable in some cases (for example, boxing every element of a std.vector may be an unacceptable performance overhead).
    • These requirements go hand-in-hand with the semantic requirements.
  • C++ APIs must work out of the box (they shouldn’t require user-provided shims).
  • Finally, Swift should provide a path for generic C++ APIs to move towards the Swift model.

Function Templates

Given these goals, I propose that the compiler specialize C++ function templates at the call site. Swift should match the C++ model when calling a C++ function but prevent these C++ semantics from leaking into Swift codebases. For example, here play will be specialized with Horn:

func main() { play(Horn()) }

And if I call play with Rock I'll get a substitution failure. (This is roughly what is already implemented on main, today.)

To prevent these C++ semantics from leaking into the rest of the Swift codebase, we must make sure that Swift generic APIs don’t take on this same model when they call C++ function templates. We must make sure that they instead keep the Swift generics model. Let’s look at an example to see how this works. Here I’m calling play with a constrained generic:

func startButtonPressed<T: Player>(_ t: T) { play(t) }

The compiler will still create a specialization of the C++ template play but it will specialize it with a constrained generic (which might sound a bit odd). Here, the constrained generic T is acting both as an archetype and a generic implementation.

By wrapping the C++ function template in a Swift generic, I am essentially converting the C++ model to the Swift model. I am providing a non-specialized implementation that can be used with any type, and I am expressing the requirements imposed on our template type parameter.

Let’s go into more depth on that last point. When the compiler specializes a C++ template with a constrained generic, it is specializing the template with a type that expresses the minimal guaranteed requirements. This means, if I don’t express all the requirements that the template imposes on T I’m going to get an error. This is really nice, because it means I get helpful errors at the call site rather than substitution failures later on. Let’s write that function again to see exactly what this means:

func startButtonPressed<T>(_ t: T) { play(t) }

Now, there’s no constraint on the generic parameter T so the compiler will essentially specialize play with an empty struct. This causes a substitution failure which the compiler can re-write as the following error (or something similar): Requirement of func play not expressed in generic constraint. Did you mean to constrain T?

In this proposed model, users will be able to consume all their generic C++ APIs without any additional work. Their APIs will use C++ semantics (and have C++ performance) by default. However, it will also give users the ability to opt-into Swift semantics where that makes sense, and gives them the flexibility to define their Swift-overlays in whatever way fits their particular API/use case. In this way, we can address every one of our goals.

Class Templates

Now, let’s take a look at class templates. If a class template is specialized with a set of concrete types, then it can follow the same model as a function template (that is, roughly, the C++ model); a specialization of the class template will be generated using the concrete types and used by Swift. When methods are called by Swift, they will be lazily instantiated, to again match the C++ model. This is important so that users can consume as many APIs as possible.

Unfortunately, when it comes to Swift generics, the “function template model” no longer works. While it may work to specialize class templates with constrained generics in some cases, we must severely limit their use (if they are allowed at all), specifically when it comes to using them as parameter types. Let’s look at why it’s so problematic to use “non-specialized class templates” as parameter types:

template<class T>
void test1(std::vector<T>);

void test2(std::vector<int>);

func generic<T>(_ v: std.vector<T>) {
  test1(v)
}

func concrete(_ v: std.vector<CInt>) {
  test2(v)
}

func main() {
  let vec = std.vector<CInt>()
  generic(vec) // Needs vec to be abstract.
  concrete(vec) // Needs vec to be concrete.
}

In the above example, depending on the call, vec needs to be both abstract and concrete. It needs to be a proper generic when passed to generic but also needs to match the (concrete) parameter convention that test2 is exposing.

The only way to get around this would be to 1) impose unacceptable requirements on the use of templates in Swift (i.e., leak the C++ model into the whole Swift program) or 2) create a new type of foreign generic which stores a concrete template specialization in some box, then rewrite any C++ function template that uses a dependent type to work with the “foreign generic.” Beyond the fact that 2) is extremely difficult to implement, it would likely have such odd semantics that it wouldn’t be very useful.

That being said, not all hope is lost...

Extensions

Not having a good solution for using class templates with the Swift generics model isn’t ideal, but it can be relieved with good support for extensions. Why? Because support for extending non-specialized class templates to conform to protocols will allow protocols to fill the role of “generic class templates”. Building off the example from above, a user could re-write the following API:

func countElements<T>(_ x: std.vector<T>) { ... }

to

func countElements<T: RandomAccessCollection>(_ x: T) { ... }

with an extended conformance:

extension std.vector: RandomAccessCollection { ... }

For specializations of class templates with all concrete types, extensions work as expected (the same way they work for any concrete type, imported or native), except that every required member is eagerly instantiated. Things get more interesting when non-specialized class templates are extended, though.

When a user extends a non-specialized class template (as is shown in the code snippet above) the compiler does nothing. However, every time a specialization of std.vector is requested (i.e with var vec = std.vector<Int>()) the compiler will essentially copy the extension, substituting in the concrete type (in this case std.vector<Int>) for the extended type. This allows users to continue to use all their APIs, and even extend certain specializations of a class template that doesn’t always conform to a protocol. It gives user their expected performance and semantics. And it does all this while avoiding substitution failures.

Errors, when a specialized type does not conform to a protocol will appear at the extension-site, not the call site (though we will probably put a note there). Let’s look at an example:

template<class T> struct AudioDevice {
  void play() { T().play(); }
};

// Error: 'AudioDevice' does not conform to 'Player' when 'T' is 'Rock'. Did you mean to make this extension conditional?
extension AudioDevice: Player {}

// Note: specialization of AudioDevice<Rock> requested here.
var ad = AudioDevice<Rock>

Errors at the extension-site allow users to more easily reason about their code and immediately see the issue. What’s the down side? These kinds of extensions probably can’t make it across library boundaries. Though, I’d like to investigate this more (so if you have ideas, let me know).

17 Likes

CC @dabrahams @Alex_L @John_McCall @Douglas_Gregor @egor.zhdan

Very interesting take on the problem. A question arises about how C++20 concepts play into the mix, since they are being introduced, have been introduced, to state constraints and requirements on types using to instantiate C++ templates?

I think it would be valuable to support extensions across module/library boundaries. I believe we can support copying an extension that's applied to a C++ class template using its interface that's defined in module's interface file if its methods/properties are marked as @inlinable. Then the consuming Swift module can copy it fully and apply to a specific specialization of the class template. Wdyt of this approach? We would need to provide good diagnostics to the users in that case though, to ensure that the users understand that the public extensions for C++ class templates must have @inlinable members.