dyno

Dyno: Runtime polymorphism done right

![Travis status][badge.Travis]

DISCLAIMER

At this point, this library is experimental and it is a pure curiosity. No stability of interface or quality of implementation is guaranteed. Use at your own risks.

Overview

Dyno solves the problem of runtime polymorphism better than vanilla C++ does. It provides a way to define interfaces that can be fulfilled non-intrusively, and it provides a fully customizable way of storing polymorphic objects and dispatching to virtual methods. It does not require inheritance, heap allocation or leaving the comfortable world of value semantics, and it can do so while outperforming vanilla C++.

Dyno is pure-library implementation of what's also known as [Rust trait objects][], [Go interfaces][], [Haskell type classes][], and [virtual concepts][]. Under the hood, it uses a C++ technique known as [type erasure][], which is the idea behind [std::any][], [std::function][] and many other useful types.

…

sh (cd dependencies && ./install.sh) # Install dependencies; will print a path to add to CMAKE_PREFIX_PATH mkdir build (cd build && cmake .. -DCMAKE_PREFIX_PATH="${PWD}/../dependencies/install") # Setup the build directory

cmake --build build --target examples # Build and run the examples cmake --build build --target tests # Build and run the unit tests cmake --build build --target check # Does both examples and tests cmake --build build --target benchmarks # Build and run the benchmarks

## Introduction
In programming, the need for manipulating objects with a common interface but
with a different dynamic type arises very frequently. C++ solves this with
inheritance:

```c++
struct Drawable {
  virtual void draw(std::ostream& out) const = 0;
};

struct Square : Drawable {
  virtual void draw(std::ostream& out) const override final { ... }
};

struct Circle : Drawable {
  virtual void draw(std::ostream& out) const override final { ... }
};

void f(Drawable const* drawable) {
  drawable->draw(std::cout);
}

…

c++
#include 
using namespace dyno::literals;

struct Drawable : decltype(dyno::requires_(
  "draw"_s = dyno::method
)) { };

This defines Drawable as representing an interface for anything that has a method called draw taking a reference to a std::ostream. Dyno calls these interfaces dynamic concepts, since they describe sets of requirements to be fulfilled by a type (like C++ concepts). However, unlike C++ concepts, these dynamic concepts are used to generate runtime interfaces, hence the name dynamic. The above definition is basically equivalent to the following:

struct Drawable {
  virtual void draw(std::ostream&) const = 0;
};

Once the interface is defined, the next step is to actually create a type that satisfies this interface. With inheritance, you would write something like this:

struct Square : Drawable {
  virtual void draw(std::ostream& out) const override final {
    out 
auto const dyno::concept_map = dyno::make_concept_map(
  "draw"_s = [](Square const& square, std::ostream& out) {
    out  This construct is the specialization of a C++14 variable template named
> `concept_map` defined in the `dyno::` namespace. We then initialize that
> specialization with `dyno::make_concept_map(...)`.

The first parameter of the lambda is the implicit `*this` parameter that is
implied when we declared `draw` as a method above. It's also possible to
erase non-member functions (see [the relevant section](#erasing-non-member-functions)).

This _concept map_ defines how the type `Square` satisfies the `Drawable`
concept. In a sense, it _maps_ the type `Square` to its implementation of
the concept, which motivates the appellation. When a type satisfies the
requirements of a concept, we say that the type _models_ (or is a model of)
that concept. Now that `Square` is a model of the `Drawable` concept, we'd
like to use a `Square` polymorphically as a `Drawable`. With traditional
inheritance, we would use a pointer to a base class like this:

```c++
void f(Drawable const* d) {
  d->draw(std::cout);
}

f(new Square{});

With Dyno, polymorphism and value semantics are compatible, and the way polymorphic types are passed around can be highly customized. To do this, we'll need to define a type that can hold anything that's Drawable. It is that type, instead of a Drawable*, that we'll be passing around to and from polymorphic functions. To help define this wrapper, Dyno provides the dyno::poly container, which can hold an arbitrary object satisfying a given concept. As you will see, dyno::poly has a dual role: it stores the polymorphic object and takes care of the dynamic dispatching of methods. All you need to do is write a thin wrapper over dyno::poly to give it exactly the desired interface:

struct drawable {
  template 
  drawable(T x) : poly_{x} { }

  void draw(std::ostream& out) const
  { poly_.virtual_("draw"_s)(out); }

private:
  dyno::poly poly_;
};

Note: You could technically use dyno::poly directly in your interfaces. However, it is much more convenient to use a wrapper with real methods than dyno::poly, and so writing a wrapper is recommended.

Let's break this down. First, we define a member poly_ that is a polymorphic container for anything that models the Drawable concept:

dyno::poly poly_;

Then, we define a constructor that allows constructing this container from an arbitrary type T:

template 
drawable(T x) : poly_{x} { }

The unsaid assumption here is that T actually models the Drawable concept. Indeed, when you create a dyno::poly from an object of type T, Dyno will go and look at the concept map defined for Drawable and T, if any. If there's no such concept map, the library will report that we're trying to create a dyno::poly from a type that does not support it, and your program won't compile.

Finally, the strangest and most important part of the definition above is that of the draw method:

void draw(std::ostream& out) const
{ poly_.virtual_("draw"_s)(out); }

What happens here is that when .draw is called on our drawable object, we'll actually perform a dynamic dispatch to the implementation of the "draw" function for the object currently stored in the dyno::poly, and call that. Now, to create a function that accepts anything that's Drawable, no need to worry about pointers and ownership in your interface anymore:

void f(drawable d) {
  d.draw(std::cout);
}

f(Square{});

By the way, if you're thinking that this is all stupid and you should have been using a template, you're right. However, consider the following, where you really do need runtime polymorphism:

drawable get_drawable() {
  if (some_user_input())
    return Square{};
  else
    return Circle{};
}

f(get_drawable());

Strictly speaking, you don't need to wrap dyno::poly, but doing so puts a nice barrier between Dyno and the rest of your code, which never has to worry about how your polymorphic layer is implemented. Also, we largely ignored how dyno::poly was implemented in the above definition. However, dyno::poly is a very powerful policy-based container for polymorphic objects that can be customized to one's needs for performance. Creating a drawable wrapper makes it easy to tweak the implementation strategy used by dyno::poly for performance without impacting the rest of your code.

Customizing the polymorphic storage

The first aspect that can be customized in a dyno::poly is the way the object is stored inside the container. By default, we simply store a pointer to the actual object, like one would do with inheritance-based polymorphism. However, this is often not the most efficient implementation, and that's why dyno::poly allows customizing it. To do so, simply pass a storage policy to dyno::poly. For example, let's define our drawable wrapper so that it tries to store objects up to 16 bytes in a local buffer, but then falls back to the heap if the object is larger:

struct drawable {
  template 
  drawable(T x) : poly_{x} { }

  void draw(std::ostream& out) const
  { poly_.virtual_("draw"_s)(out); }

private:
  dyno::poly> poly_;
  //                   ^^^^^^^^^^^^^^^^^^^^^ storage policy
};

Notice that nothing except the policy changed in our definition. That is one very important tenet of Dyno; these policies are implementation details, and they should not change the way you write your code. With the above definition, you can now create drawables just like you did before, and no allocation will happen when the object you're creating the drawable from fits in 16 bytes. When it does not fit, however, dyno::poly will allocate a large enough buffer on the heap.

Let's say you actually never want to do an allocation. No problem, just change the policy to dyno::local_storage. If you try to construct a drawable from an object that's too large to fit in the local storage, your program won't compile. Not only are we saving an allocation, but we're also saving a pointer indirection every time we access the polymorphic object if we compare to the traditional inheritance-based approach. By tweaking these (important) implementation details for you specific use case, you can make your program much more efficient than with classic inheritance.

Other storage policies are also provided, like dyno::remote_storage and dyno::non_owning_storage. dyno::remote_storage is the default one, which always stores a pointer to a heap-allocated object. dyno::non_owning_storage stores a pointer to an object that already exists, without worrying about the lifetime of that object. It allows implementing non-owning polymorphic views over objects, which is very useful.

Custom storage policies can also be created quite easily. See `` for details.

Customizing the dynamic dispatch

When we introduced dyno::poly, we mentioned that it had two roles; the first is to store the polymorphic object, and the second one is to perform dynamic dispatch. Just like the storage can be customized, the way dynamic dispatching is performed can also be customized using policies. For example, let's define our drawable wrapper so that instead of storing a pointer to the vtable, it instead stores the vtable in the drawable object itself. This way, we'll avoid one indirection each time we access a virtual function:

struct drawable {
  template 
  drawable(T x) : poly_{x} { }

  void draw(std::ostream& out) const
  { poly_.virtual_("draw"_s)(out); }

private:
  using Storage = dyno::sbo_storage;                      // storage policy
  using VTable = dyno::vtable>; // vtable policy
  dyno::poly poly_;
};

Notice that nothing besides the vtable policy needs to change in the definition of our drawable type. Furthermore, if we wanted, we could change the storage policy independently from the vtable policy. With the above, even though we are saving all indirections, we are paying for it by making our drawable object larger (since it needs to hold the vtable locally). This could be prohibitive if we had many functions in the vtable. Instead, it would make more sense to store most of the vtable remotely, but only inline those few functions that we call heavily. Dyno makes it very easy to do so by using Selectors, which can be used to customize what functions a policy applies to:

struct drawable {
  template 
  drawable(T x) : poly_{x} { }

  void draw(std::ostream& out) const
  { poly_.virtual_("draw"_s)(out); }

private:
  using Storage = dyno::sbo_storage;
  using VTable = dyno::vtable>,
    dyno::remote
  >;
  dyno::poly poly_;
};

Given this definition, the vtable is actually split in two. The first part is local to the drawable object and contains only the draw method. The second part is a pointer to a vtable in static storage that hol