Before I knew about type erasure in C++ I thought it can not be done. After I learned about type erasure in C++ I still thought it can not be done. 😃
Introduction
According to every CV and LinkedIn profile I saw everybody except me is a fast learner and self starter. 😉
So if you fall into that category and want to learn what is type erasure there is plenty of cppcon talks and blogs explaining it. This article is mostly for people like me that read those blogs, saw those videos and said “WTF… virtual, template, inner, concept, wrapper, pointers… I still do not get it”.
Minimal code, only high level explanations that will hopefully help you to experience “aha moment”.
What is type erasure?
Wikipedia has horrible unhelpful description so let’s use the example you have probably used in your C++.
std::function<float(int,int)> can be constructed and assigned to using “normal” function that matches the signature(takes 2 integers and returns a float). But it can also be constructed/assigned using lambda or functor(struct with function call operator) that match those signature.
What is interesting here is that universe of possibilities is “infinite”. Unlike polymorphism or union/variant there is no need to inherit from some common type (polymorphism) or list all the types(like for union/variant).
If you want to see more usage examples cppreference has them, but the main idea here is that you see that std::function can work with different types without us mentioning them in the declaration of std::function or those types inheriting from some common base class. Only thing we need to specify is the function signature.
How does polymorphism work?
As the image above explains when your classes inherit from some other class/interface they tell the compiler that every instance of that object that will be created should be colored in color unique for that type. That way during runtime code that has a pointer to vehicle knows what function to call (based on the color of the vehicle it knows if vehicle is Bicycle or Rocket).
If you know about vtable you may know more precisely how this is implemented and that color is just a lie of simplification but for our understanding of the problem it is enough to remember that compiler colors different types in the inheritance hierarchy differently so that it can distinguish them at runtime.
Beside this it is important to remember that instances of “normal” types(types that are not involved in inheritance) are not colored.
How does union/variant work?
Variant is union where variant remembers what type is currently stored in union. Sounds great but it does not help us since you need to list all the types variant can hold and as we discussed the number of types in type erasure is “infinite”.
So how does the type erasure work?
If you remember me saying that std::function<float(int,int)> supports “infinite” different types you may want to reconsider if this is really true. It is not. 😃
You can go through source code and see where construction and assignment of your function happens and you could enumerate all possible types your function will be constructed with. This is obviously hard, makes code hard to change, may be impossible(getting types of lambdas without refactoring user code?) and is not practical.
But it gives us insight in how type erasure works.
Here is where hero of our story (and article title) enters the scene. Templated magical operator = enables us to know the types of the right hand side. In other words we know the types that may be assigned to our type erased type during runtime. But we still have a problem. In general we can not color those types. Remember how we said that types that do not participate in polymorphism can not be colored? Also we can not programmatically list them and make union/variant out of them…Damn it! But luckily our hero know another trick. He can make types.
He’s a Wizzard!. Type Wizzard. He can make a type that as member variable(payload) has the type on the right hand side of assignment and also it can be colored.
Our hero will use templates and inheritance for this.
Templates to make this new type unique and to specify the payload of this new type(payload is the type on the right hand side of =).
Inheritance to enable coloring of this new type. So we can distinguish them at run time. And that is mostly it.
I said this is mostly it since our hero will need to know what interface we want to implement so the base class he will use in inheritance can have the proper member functions. Call chain is quite long, but it goes like this:
- public function
- pointer to internal base (that points to some instance that inherits from internal base and has the payload of certain type) function.
- that instance of derived type calls the function on it’s payload.
Also you can implement functionality that enables users to query which type is currently stored, but back to the general idea that is simple although ingenious.
Use polymorphism to enumerate all the types using templated constructor/assignment operator, by creating new types that inherit from some common base. Then forward calls to erased interface using polymorphism.
Disclaimer: type erasure is “slow”, it is a long topic, but if you care about performance you should keep this in mind. Also beside assignment operator constructor is also magical, same magic that happens on assignment happens on construction.
If you insist on reading some code I wrote a small program with type erasure, but I do not guarantee it is good, so if I were you I would read More C++ Idioms version.
Could it be done better by language?
I did not give much thought to this, but my feeling is that language implementation of type erasure would make it much easier to use(currently it is quite verbose to create the library code, user code is trivial).
In particular currently you need to know what interface you are erasing(your internal base class needs to implement that interface). My guess is that compiler could implement generic type on which you can call any function as long as all possible types that are assigned to instance of that erased type implement that function.
