This is understanding notes for this presentation: C++ Type Erasure Demystified - Fedor G Pikus - C++Now 2024. Ppt at here.

Editor’s note: The std::variant section was corrected after the series adopted a stricter distinction between type erasure and closed tagged dispatch. The revised taxonomy is summarized in Polymorphism, Type Erasure, and std::function.

Core logic behind type erasure

  • Encapsulate type infomation in implementation, remove type information in interface
  • Different implementation for different types might be manually coded or generated by compiler(C++)
    • Template instantiation
    • Virtual inheritence
  • Compile time generates or selects the type-specific functions and tables.
    • Templates instantiate adapters with a uniform signature.
    • Virtual methods produce overrides and compiler-generated vtables.
    • Manually written function tables provide the same kind of executable route.
  • Construction records the matching runtime binding state, such as a vptr or erased invoker pointer.
  • Dispatch happens at runtime: Dispatch is all about redirection of function pointers,with the same signature
  • The user of the interface is not aware of the passed type information, hence the type is erased.

What’s the benifit of type erasure? Even though there is a type erased interface, like qsort, but when the qsort is actually used, we still need to pass correct implementation of the comparision function to qsort, we just defer the choice of implementation to later time. The qsort function acts as a variation point, it abstract the sorting logic functionality by using only the type erased compare function. When qsort is called, it binds the sorting logic to the actual type compare implementation. Without qsort that use the type-erased compare interface to implement common behavior of sorting, the type-erased compare interface will have no practical meaning:

  • The qsort algorithm stands for the common behavior, which utilize the type-erased interface
  • The implementation of this common behavior abstract out any specific type information
  • When the implementation of this common behavior is used, user decides which type it is actually operates on(the common behavior implementation still know nothing about type whatsoever)

Without this abstraction, we have to implement qsort for each individual type and the sorting algorithm has to be coded every time for each type. Now with type erasure, we only need to code the actual sorting algorithm once for all possible types. Of cource the compare function has to be implemented for each type, since each type has their own comparing logic.

Implementation methods for type erasure

  1. Virtual inheritance: redirection hanppens when using base class pointer to call implementation in derived class(whose type is erased)
  2. Static templated functions: C++ compiler will generate code implementation for each template instantiation. It’s the same as C, but code generated instead of manually written. Note that generated static functions are class members, which means that the amount of instantiations equals the number of generated class member functions.
  3. Vtable: similar as 2, this time use a vtable to point to generated static class member functions.

Note: Method 3 is how std::function is implemented.

#include <cstdlib>

// Following code are in *.cpp file, without Some exposed
// But user will call this code through type erased interface: void
// print_data(const void *p). This is the core of type erasure: encapsulate type
// infomation in implementation, remove type information in interface.
struct Some {
  int data;
};
bool less(const void *l, const void *r) {
  return static_cast<const Some *>(l)->data <
         static_cast<const Some *>(r)->data;
}

// The declaration in *.h, exposed to external user
// ! Here is where the type erasure happens
bool less(const void *, const void *);

// User of type erasure: qsort does not need to know which type it will sort,
// type is erased from qsort: type erasure is an abstraction for multiple
// implementations that provide the same behavior, the relevent behavior is what
// matters, not the type. In this example, `compare` parameter requires that two
// elements can be compared, qsort does not care about how it is compared, as
// long as it return a bool value. This gives chances to implement the compare
// logic in source code, instead of in interface code.

// Since type erasure is about abstraction of behavior, it alwarys involve
// redirection of function pointers, no matter which way it is implemented. This
// redirection of function pointer is called dispatch, which is another core
// brick in implementing type erasure. Dispatch might happen both at compile
// time or runtime.

// Compared with C, C++ ONLY add implementation methods for type erasure. In C,
// we have to manually write different implementations, like the `less` and
// `more` function in below. In C++, we have the compiler to generate different
// implementation code for us. They all involves template and are done at
// construction phase. The three ways are:
// 1. virtual inheritance: redirection hanppens when using base class pointer to
// call implementation in derived class(whose type is erased)
// 2. static templated functions: C++ compiler will generate
// code implementation for each template instantiation. It's the same as C, but
// code generated instead of manually written. Note that generated static
// functions are class members, which means that the amount of instantiations
// equals the number of generated class member functions.
// 3. vtable: Similar as 2, this time use a vtable to point to instead of
// generating static class member functions.

// One more important fact is that all the C++ ways are of value semantics. The
// implementation is stored as value(function pointers can be seen as value of
// function variables).

// Now we can summarize type erasure as follow:

// Core logic of type erasure:
// 1. Encapsulate type infomation in implementation, remove type information in
// interface.
// 2. The interface provide same behavior, regardless of specific type

// Implementation steps of type erasure involve two distinct phase: how
// implementation code is generated at compile time and how those implementation
// is dispatched to at runtime:

// 1. Statically write type erased code implementation, either manually, or by
// compiler(C++). The type must be inside cpp, not in header(interface)
// 2. Dynamically dispatch function call to the right implementation at runtime.
// How the dispatch is done varies. It can simply be hard coded(like in C qsort
// example in following code). Or it can be done using virtual inheritance in
// C++. Either way, the dispatch, or redirection is determined during
// construction phase. As soon as the construction is complete, the dispatch
// manner is determined.

void qsort(void *base, size_t nmeb, size_t size,
           bool (*compare)(const void *, const void *));

// Following give another type that also use qsort
struct Tome {
  int data;
};
bool more(const void *l, const void *r) {
  return static_cast<const Tome *>(l)->data <
         static_cast<const Tome *>(r)->data;
}
bool more(const void *, const void *);

int main() {
  Some a[10];
  Tome b[10];
  // qsort is universal, thanks to the redirection of `compare` parameter
  qsort(a, 10, 4, less);
  qsort(b, 10, 4, more);
}

Abstraction of type

Type erasure, C++ template, C++ concept, virtual inheritence, what is the common characteristic among them? They both allow us to write code logic for a group of types, instead of just one type. The code logic is the common behavior for those types. The binding of specific types are deferred to later times: for type erasure and virtual inheritence, this binding is defered to runtime; for C++ template and C++ concept, this binding is deferred to compile time:

  • We can write binary libraries which can be used on difference types using type erasure and virtual inheritence
  • We can write templated source code libraries which can be used on difference types using C++ template and C++ concept

C++ concept is more restricted C++ template. In this series, C++ virtual inheritance is classified operationally as a special kind of type erasure: a base interface hides the derived type and the compiler-generated vtable acts as an operation table. This usage is broader than the common convention that reserves type erasure for wrappers such as std::function.

Keep code generation, binding, and dispatch distinct. Compile time generates type-specific functions and tables. Object construction records runtime binding state such as a vptr or an erased invoker. A later call dispatches through that already-generated state.

Type erasure of std::function

After the signature is specified through a template parameter, a std::function variable can store different callable types as long as they satisfy that signature. The binding operation generates type-specific adapters, then construction stores the callable and the matching manager and invoker state. Invocation dispatches through the stored invoker. Assignment may replace the callable and rebind all of that state together.

See std::function implementation

Type erasure of std::shared_ptr deleter

std::shared_ptr type use virtual base class to do type erasure. If user pass a custom deleter during construction, the pointer instance will be bound to a unified base class and points to the implementation of this custom deleter.

// Support for custom deleter and/or allocator
template <typename _Ptr, typename _Deleter, typename _Alloc, _Lock_policy _Lp>
class _Sp_counted_deleter final : public _Sp_counted_base<_Lp> {
  class _Impl : _Sp_ebo_helper<0, _Deleter>, _Sp_ebo_helper<1, _Alloc> {
    typedef _Sp_ebo_helper<0, _Deleter> _Del_base;
    typedef _Sp_ebo_helper<1, _Alloc> _Alloc_base;

  public:
    _Impl(_Ptr __p, _Deleter __d, const _Alloc &__a) noexcept
        : _M_ptr(__p), _Del_base(std::move(__d)), _Alloc_base(__a) {}

    _Deleter &_M_del() noexcept { return _Del_base::_S_get(*this); }
    _Alloc &_M_alloc() noexcept { return _Alloc_base::_S_get(*this); }

    _Ptr _M_ptr;
  };

public:
  using __allocator_type = __alloc_rebind<_Alloc, _Sp_counted_deleter>;

  // __d(__p) must not throw.
  _Sp_counted_deleter(_Ptr __p, _Deleter __d) noexcept
      : _M_impl(__p, std::move(__d), _Alloc()) {}

  // __d(__p) must not throw.
  _Sp_counted_deleter(_Ptr __p, _Deleter __d, const _Alloc &__a) noexcept
      : _M_impl(__p, std::move(__d), __a) {}

  ~_Sp_counted_deleter() noexcept {}

  virtual void _M_dispose() noexcept { _M_impl._M_del()(_M_impl._M_ptr); }

  virtual void _M_destroy() noexcept {
    __allocator_type __a(_M_impl._M_alloc());
    __allocated_ptr<__allocator_type> __guard_ptr{__a, this};
    this->~_Sp_counted_deleter();
  }

  virtual void *_M_get_deleter(const std::type_info &__ti) noexcept {
#if __cpp_rtti
    // _GLIBCXX_RESOLVE_LIB_DEFECTS
    // 2400. shared_ptr's get_deleter() should use addressof()
    return __ti == typeid(_Deleter) ? std::__addressof(_M_impl._M_del())
                                    : nullptr;
#else
    return nullptr;
#endif
  }

private:
  _Impl _M_impl;
};

_Deleter type is erased at compile time, std::shared_ptr type will only store a pointer of _Sp_counted_base type, which makes the std::shared_ptr type not depend on custom deleters.

More about binding

After a type is erased, we have to bind to the correct implementations. The implementation must coorespond to this type, otherwise, there will be errors if we pass a void pointer to this implementation, since inside this implementation, the void pointer will be cast back to this type. Of course, there can be multiple implementations for this type, but, there is only one binding. Better use examples:

  • Binding state remains valid until an operation explicitly replaces or destroys the owning object.
  • For a virtual class, construction initializes the object’s vptr for its current construction stage and dynamic type. Ordinary program logic does not rewrite vptrs manually.
  • For template functions, which binds at compile time, it’s fixed after compilation, and cannot be changed.
  • For std::function, multiple objects with the same signature can contain different callables. Copy or target assignment changes an object’s callable and matching adapter state together; invocation then follows the new stored invoker: 
    template <typename _Res, typename... _ArgTypes>
template <typename _Functor, typename, typename>
function<_Res(_ArgTypes...)>::function(_Functor __f) : _Function_base() {
typedef _Function_handler<_Res(_ArgTypes...), _Functor> _My_handler;

if (_My_handler::_M_not_empty_function(__f)) {
  _My_handler::_M_init_functor(_M_functor, std::move(__f));
  _M_invoker = &_My_handler::_M_invoke;
  _M_manager = &_My_handler::_M_manager;
}
}

    After construction, invocation uses that binding until assignment replaces the callable and its matching manager and invoker state.

std::variant

  • std::variant<Ts...> is a type-safe union with closed tagged dispatch, not type erasure. Every supported alternative remains visible in the public variant<Ts...> type.
  • _M_index / index() records which alternative is active. std::visit and lifetime operations may use a switch, jump table, or function-pointer table to select the matching Ti handler.
  • std::visit(f, v) is instantiated for the concrete callable and complete alternative list. Runtime chooses the active alternative; it does not erase the visitor type or the enumerated alternatives.
  • std::variant is therefore runtime polymorphism without type erasure. A table-based implementation is a dispatch technique, not the criterion for erasure.
  • Full treatment: V — Closed Tagged Dispatch. RTTI / dynamic_cast: Part VI. Double-dispatch usage: Double Dispatch with std::variant and std::visit.

std::any

  • std::any is type erasure — same core as Core logic: one interface type at the use site (std::any), stored value type hidden until any_cast, binding fixed when the any is constructed.
  • Manager pointer as tag — _M_manager points at _Manager<T>::_S_manage, a type-specific static function; all lifetime ops (destroy, clone, move) dispatch through one unified function-pointer signature with opcodes — parallel to std::function’s _M_manager.
  • Open set — any copy-constructible T at each construction site; contrast closed std::variant<Ts...>. Public ctor/dtor/copy/move signatures never name T; per-type logic lives in _Manager<T> instantiated at the bind site.
  • Full treatment: Type Erasure VII — std::any.
  • Series synthesis: Type Erasure VIII — Final Thoughts.