Another polymorphism

In this post we will try to see by a practical example what Boost.Variant is for. You can sometimes see examples that use type variant<int, double, string>, but to me they are artificial: I never needed to use something that is either a double or int; but I still consider this library useful. Even if you are already familiar with Boost.Variant an its concepts of “never-empty guarantee” and “static visitor”, I made sure there is still something you can get from reading this post.

Vtable-based polymorphism

We start with looking at the classical polymorphism based on virtual functions.

The goal of any polymorphism is to make sure that a given routine (a function, or function template) will work and do the right thing even though we do not know what types we will be actually working with. In other words, it is to implement a form of type erasure, a sort of boundary: behind it, there might be running different sub-routines at different times, but in front of it we always have the same algorithm.

There are many ways to achieve this effect. The vtable-based polymorphism has a couple of particular characteristics:

1. Fixed number of functions. You first decide on a complete and fixed interface: virtual member functions, and then only interact with objects of different types through this interface. Technically, you can overcome this constrain by using a dynamic_cast, but this is counter to vtable-based polymorphism idea, and in fact beats the purpose of using it in the first place, so we won’t discuss it further in this post.
2. Unlimited number of types. Once you have fixed the interface, anyone at any time can define a new type that can be used through the interface, as long as her type is conformant. Functions that operate on the interface, need not be aware of how many different types there will be.
3. type safety. If the interface has pure virtual functions, and I forget to implement any of them in my types, I get a compile-time error.

This is very useful in a number of cases. We can for instance use the vtable-based polymorphism to implement application plug-ins: when we write the primary program, we do not know what and how many different plugins people will add to it. But we do not need to care as long as we provide a good interface.

When this is not enough

Occasionally, what we need is something different. When my data structure models some real life situation, I often need to say that at a given ‘location’ I need one of two or three well defined alternatives.

Let me give you an example. Suppose we want to represent a sequence of physical containers (boxes) that will be loaded into a cargo hold. Each box can be one of:

1. A regular container — where you can put a certain amount of load that fits within a given size.
2. A multi-container — it consists of a sequence of smaller containers: each of them can be loaded as a regular container, but they all constitute one box that will be put on one cargo hold location. (The smaller containers cannot be further subdivided.)
3. Ballast — it looks like a container from the outside, and can be located in cargo hold as a regular container, but nothing can be loaded inside, and it serves a slightly different purpose.

I can represent each of them as a distinct type, each containing a different set of data:

struct Container
{
  Volume volume_allowance;
  Weight weight_allowance;
  bool is_air_conditioned;
  Id id;
  // more ...
};

struct MultiContainer
{
  vector<Container> containers;
  Id id;
  // more ...
};

struct Ballast
{
  BallastType type;
  Weight weight;
  // more ...
};

The question is how I should say that at a given location I expect one of the three types. This is of course achievable with a vtable-based polymorphism: I need to define an interface class, and then force my types to comply to the interface. If I cannot force them (because I am not in control of their definitions), I need to define wrapper types, that will contain the original type and comply to the interface. But there are two problems with this:

1. This does not convey the idea that I only want one of the three types, no additional interface implementations are expected or allowed.
2. The three types have really nothing in common (except for the fact that I want them at the same location). What functions should I put in the interface?

Regarding problem 1, you might dismiss it by saying, “so what: let’s just accept that someone might add another interface implementation”. This does not convey our intention any more, and may loose some optimization opportunities; but may still be acceptable a solution.

Problem 2 is more serious. The three types do not have a common interface. True, at some point in the program I need to treat them uniformly. But at the point of designing my data structures I do not know in advance how many different operations I will be performing on the types. I guess I might want to:

• get total weight allowance,
• get total volume allowance,
• check if any portion of a container is air conditioned,
• check if all of it is air conditioned,
• check if it is allowed to be loaded,
• check if it is ballast,
• check if it is divided into sub-containers,
• check if it can fit a load of a given volume,
• check if it has an id,
• get id,
• get list of id’s,
• who knows what else …

This is the exact opposite of what an interface is supposed to be. An interface should consist of a small number of functions: easy to understand, and reflecting the common nature of the objects we are working with. My interface, in contrast, is not only going to be huge, but will keep growing each time, I am writing a new function and I find the current set of functions insufficient.

Instead, I could add a trivial interface with only one virtual function: the destructor, and simply use dynamic casting wherever I want to use the types.

This, of course, beats the whole idea of using a vtable-based interface. We will be bypassing the interface all the time. Ugly as it is, it will do the trick though, but it has one safety gap. If one day there comes a need to add a 4th type of cargo hold occupant that I did not anticipate in advance, the existing dynamic_casts will not take it into account by default; and if I forget to rewrite all the places manually, I will get a bug in my program logic: some parts of the program will be unprepared to handle the 4th type, even though they will compile.

Boost.Variant

The above is a kind of the problem that Boost.Variant is intended to solve. With Boost.Variant you declare your one-of-the-three type as:

using Block =
  boost::variant<Ballast, Container, MultiContainer>;

Now, type Block is either a Ballast or a Container or a MultiContainer and nothing else.

Block is a regular type: it is default constructible (if Ballast is), it is copyable and movable (provided that the three types are). It is even equality-comparable (provided that the three types are).

Type Block has all its sub-types encoded in its type. This opens room for a number of useful compile-time computations. For one, compiler can compute the sizeof required by Block: it is the size of the biggest of the three sub-types + one byte for the discriminator — it keeps track of which sub-type exactly a given object represents. This way, we do not require to allocate anything on the heap.

(Well, sometimes the above statement about the sizeof and heap allocation is not true, as we shall see later.)

Boost.Variant guarantees that objects of type Block always hold a valid instance of one of the three sub-types: they are never ’empty’. This is called a never-empty guarantee.

Type switch

Representing an ‘alternative’ of types is the easy part. The interesting question is how you use such thing. Boost.Variant allows you to query which type is currently stored in the object, but we do not want to do it. What we need is a higher-level mechanism of treating the variant polymorphically.

At some level we want to treat any of the sub-types of our Block uniformly. We want something that resembles a virtual function call: we pass it a reference to Block, and it should know what to do for any of its sub-types.

This is where we can see the full power of Boost.Variant. The following code demonstrates how we can use the concept of a static visitor to compute the weight allowance in any of Container or MultiContainer or Ballast.

struct Weight_allowance : boost::static_visitor<Weight>
{
  Weight operator()(const Container& cont) const
  {
    return cont.weight_allowance;
  }
     
  Weight operator()(const MultiContainer& multi) const
  {
    Weight wgt (0);
    for (const Container& cont : multi.containers)
      wgt += cont.weight_allowance;
    return wgt;
  }
     
  Weight operator()(const Ballast&) const
  {
    return Weight(0);
  }
};

Deriving from boost::static_visitor<Weight> indicates that this function object can be used to ‘unpack’ a variant. Its return type is Weight. Next, we give a recipe for computing the weight for each possible sub-type.

We invoke this ‘polymorphic function’ like this:

Block b = /* ... */;
Weight w = boost::apply_visitor(Weight_allowance(), b);

The additional function apply_visitor inspects the current state of the variant type and calls the correct routine. Additionally, it performs a compile-time computation to check if all the cases of variant sub-types have been considered: if we missed any, we get a compile-time error. It is particularly useful when at some point you need to introduce a new sub-type to the variant. The compiler errors (ugly as they are) immediately point you to all the places in the code that need to be reconsidered.

For a full working example of using Boost.Variant with static visitors see here.

If you look at the structure of the visitor definition (Weight_allowance above), in a way it resembles a switch statement. In a different language, we could express it as:

// NOT IN C++
Weight Weight_allowance(const Block& b)
{
  type switch (b)
  {
  case (const Container& cont):
    return cont.weight_allowance;

  case (const MultiContainer& multi):
    Weight wgt (0);
    for (const Container& cont : multi.containers)
      wgt += cont.weight_allowance;
    return wgt;

  case (const Ballast&):
    return Weight(0);
  }
}

To continue with an analogy with the swith-statement, you can use an equivalent of default label when defining a visitor. Consider the following example:

struct Is_ballast : boost::static_visitor<bool>
{
  bool operator()(const Ballast&) const { return true; }
    
  template <typename T>
  bool operator()(const T&) const { return false; }
};

It means “for Ballast return true, for anything else return false”. However, I would not recommend doing so. You do not know what the ‘anything else’ turns out to be in the future, when a new sub-type is added to the variant type. Or you may inadvertently apply the visitor to a wrong variant, like variant<int, long, float> — a visitor is not tied to a specific variant type. By using a catch-anything case, you loose the static safety feature.

The true power of the static visitor becomes visible when you have to dispatch on two variant types simultaneously.

Suppose we have a list of load pieces that we want to distribute into containers. Each piece of load can be either a single bundle, or a set of bundles, which for other reasons are treated as one object, but for the purpose of loading, if need be, they can be spit and located in a number of containers. This is represented by the following types:

struct Bundle
{
  Weight weight;
  Volume volume;
  Id id;
  bool requires_air_conditioning;
  // more ...
};

struct MultiBundle
{
  Id bundle_id;
  vector<Bundle> sub_bundles;
  // more ...
};

using LoadPiece = boost::variant<Bundle, MultiBundle>;

Now, we want to write a binary function that wants to inspect if a given Block can fit a given LoadPiece. This is how we do it with Boost.Variant:

struct Fits : boost::static_visitor<bool>
{
  bool operator()(const Container& c, const Bundle& b) const
  {
    return c.weight_allowance >= b.weight
        && c.volume_allowance >= b.volume;
  }
    
  bool operator()(const Container&   c,
                  const MultiBundle& mb) const
  {
    return bool("sum of bundles fits into c");
  }
    
  bool operator()(const MultiContainer& mc,
                  const Bundle&         b) const
  {
    for (const Container& c : mc.containers)
      if (Fits{}(c, b)) // self-call
        return true;
    return false;
  }
    
  bool operator()(const MultiContainer& mc,
                  const MultiBundle&    mb) const
  {
    return bool("all bundles fit across all sub containers");
  }
     
  template <typename T>
  bool operator()(const Ballast&, const T&) const
  {
    return false;
  }
};

I didn’t have room to implement all the cases decently, but you can see the idea. I can specify a procedure for each pair of sub-types in two variants.

Also note the last case: it reads, “if we have Ballast in the left-hand side and whatever in the right-hand side.”

Mach7

I checked how the same problem of applying a ‘polymorphic function’ to a variant can be solved with Mach7 library. Mach7 is an experimental library for pattern matching, and our problem of matching sub-types of variant fits into its scope. Mach7 does not require of us any inversion of control. With a number of clever macros it allows us to write a switch-like statement. Our above example with checking weight allowance in a given container looks like this:

Weight weight_allowance(const Block& block)
{
  Match (block)
  {
  Case (C<Container>())
    return match0.weight_allowance;
 
  Case (C<MultiContainer>())
    Weight wgt(0);
    for (const Container& cont : match0.containers)
      wgt += cont.weight_allowance;
    return wgt;
 
  Case (C<Ballast>())
    return Weight(0);
  }
  EndMatch
}

We can see that it gets really close to a built-in language feature. In fact Mach7 is an experiment that intends to pave the way for a future C++ language extension.

One thing to observe is that we do not choose the name for the matched reference to Container or MultiContainer. The name is chosen by the library: match0. It represents a match on the variable at index 0. We can get more than one index if we do a dispatch on more than one object, as in the case of our function that checks if a given load fits in a given container. In Mach7, such function looks like this:

bool fits(const Block& block, const LoadPiece& load)
{
  Match (block, load)
  {
  Case (C<Container>(), C<Bundle>())
    return match0.weight_allowance >= match1.weight
        && match0.volume_allowance >= match1.volume;
 
  Case (C<Container>(), C<MultiBundle>())
    return bool("sum of bundles fits into c");
 
  Case (C<MultiContainer>(), C<Bundle>())
    for (const Container& c : match0.containers)
      if (fits(c, match1)) // recursive call
        return true;
    return false;
 
  Case (C<MultiContainer>(), C<MultiBundle>())
    return bool("all bundles fit across all sub containers");
 
  Case (C<Ballast>(), C<Bundle>())
    return false;
 
  Case (C<Ballast>(), C<MultiBundle>())
    return false;
  }
  EndMatch
}

Here match0 represents a reference to a sub-type of variant Block, and match1 represents a reference to a sub-type of variant LoadPiece.

One thing to remember is because the type switch construct is open for extensions by nature, it does not check if we covered all possibilities in the Case branches, so it may be necessary to put the equivalent of default label to cover a future case when at some point we add a new sub-type to Block. In Mach7, this is spelled Otherwise and our first example could be rewritten as:

Weight weight_allowance(const Block& block)
{
  Match (block)
  {
  Case (C<Container>())
    return match0.weight_allowance;
 
  Case (C<MultiContainer>())
    return Weight(("compute correct answer...", 1));
 
  Case (C<Ballast>())
    return Weight(0);

  Otherwise()       // when nothing else matches
    assert(false);  // or whatever you need
  }
  EndMatch
}

For a full working example of using Boost.Variant with Mach7 see here.

I have run a small benchmark to see how fast Mach7 is compared to Boost.Variant visitors. For the benchmark code see here. Results show that Boost.Variant’s static visitor is faster than Mach7: 1.65 times on GCC 4.9.2, and 2.93 times on MSVC 14.0. (Both tested on Windows, with maximum optimizations enabled).

The never-empty guarantee

To guarantee that variant<A, B> always stores an object of either type A or B, in the face of exceptions, is harder than one might expect. Just imagine how you would implement a ‘mixed’ assignment like this:

variant<A, B> va = A{};
variant<A, B> vb = B{};
va = vb;

What does it mean to assign a B to an A? And how to implement it if any constructor of B could throw? For a detailed discussion of this problem see the design overview section of Boost.Variant documentation here. In short, in some cases the copy-assignment of variant performs a heap allocation.

An alternative design of variant proposed for standardization, does not allocate any memory on the heap, at the cost of compromising the never-empty guarantee to a certain extent. For more details see here and here. In short, while you cannot create a variant that holds neither A or B, you can get to such state in case an exception is thrown from the mixed copy assignment. An attempt to ‘visit’ such variant will result in exception.

Summary

The key point of this introduction is that Boost.Variant along with its concept of a static visitor offers another kind of polymorphism that makes different trade-offs and targets different use cases than the vtable-based solutions (like class inheritance or value-semantic type-erasure). The following table summarizes the differences.

polymorphism ▼	number of functions	number of types	Type safety
vtable-based	fixed	unlimited	yes
variant	unlimited	fixed	yes

When your use case matches the ‘profile’ of Boost.Variant, it is worth considering it instead of the classical vtable-based polymorphism. It is optimized for this use case and out-performs the alternatives; it is a bit more convenient to use. But most importantly: it reflects what you are modeling.

Acknowledgements

I am grateful to Yuriy Solodkyy for helping me understand the mechanics and the usage of Mach7 library.

References

1. Eric Friedman, Itay Maman, Boost.Variant Library.
2. David Sankel, “C++ Language Support for Pattern Matching and Variants”.
3. David Sankel, “A variant for the everyday Joe”.
4. Anthony Williams, “Standardizing Variant: Difficult Decisions”.
5. Axel Naumann, “Variant: a type-safe union (v4)”.
6. Yuriy Solodkyy, Mach7 Library.
7. Yuriy Solodkyy, Gabriel Dos Reis, Bjarne Stroustrup, “Open and Efficient Type Switch for C++”.
8. Vicente J. Botet Escriba, “C++ generic match function”.