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”.
Advertisements
This entry was posted in programming and tagged , , , , , . Bookmark the permalink.

20 Responses to Another polymorphism

  1. Chris says:

    Small note: the first code example says `using Bulk = …` and then refers to the type as `Block`.

  2. viboes says:

    Thanks Andrzej for this yet awesome blog.

    As in Match3, I have proposed to generalize the visitation to any sum type in P0050 [1], so that we can visit variant, optional expected, … We will rework a little bit the proposal bu the essence is there.

    [1] the http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0050r0.pdf

  3. Anatoliy says:

    It would be nice if you make an overview of a ways to implement a visit function for applying visitors for variants.

  4. Mihai Todor says:

    Interesting article Andrzej. One thing that I don’t really understand is why you are constructing a bool from a string inside “struct Fits”. For example: “return bool(“sum of bundles fits into c”);”. I assume it’s something obvious, but I’m just not seeing it.

    Thanks!

    • Please do not preoccupy yourself with this detail. Writing the correct function would take too much space and distract the readers from the point of the article. So sum of bundles fits into c was supposed to be a comment. But in order to make the code conformant to C++ I wrapped it into a bool (which results in value true). In a real program, you would call a normal useful function.

      Maye that was too clever a hack.

  5. Pingback: Another polymorphism | Vehbi Neziri

  6. dragonp12 says:

    The visitors are a nice solution, although my design-POV issue with them (in particular with the more complex one like your ‘Fits’ example above) is that they require coupling the variant types together in the same class. I can’t think of a better solution, but it does feel a bit unclean!

    • I do not quite understand what you mean when you say “coupling the variant types together in the same class”.

      Do you mean that class Fits refers to two variant types Block and LoadPiece? Why is that considered unclean? Is the solution with Mach7 more clean?

      • dragonp12 says:

        I think it’s because I don’t see it as a huge improvement over an if or switch statement. All of the types have to be explicitly handled, and handled in the same class. This is what I meant by coupling; whereas other polymorphic interfaces (virtuals or generics) have their implementations entirely independent from one another, this solution requires them (i.e. Ballast, Container, MultiContainer) to be bound together in the visitor implementation for the collection of variants you’re interested in.

        That said, I’m not necessarily saying that it’s not a good solution to the problem; it’s just that I feel like there should be a cleaner way to do it!

        • viboes says:

          I believe that this is closer to subject oriented programming. No need to modify the existing object when you add features to your application. This increases IMHO the decoupling between classes.

          And yes, there should be a cleaner way to do it, but it should not consists in adding anything to the existing classes. Non-member function overloading is an alternative with its own characteristics.

        • Anatoliy says:

          “Decoupling” can be achived by using [“lambda visitor”](https://github.com/boostorg/spirit/blob/547076384ac4d9d6c94298015119c759f02c4882/include/boost/spirit/home/x3/support/utility/lambda_visitor.hpp) – is a visitor combinator function, that constructs a class derived from all the labmdas provided as a parameters. Fined-tuning can be carried out by using SFINAE on returning type.

        • I am still trying to understand what coupling you see that disturbs you.

          All of the types have to be explicitly handled, and handled in the same class.

          — To what class are you referring to in this sentence? In the examples from the post, are you referring to classes representing visitors? Like class Fits?

          Are you saying that the coupling you are uncomfortable with is the coupling between class Ballast (one of the sub-types of Block) and class Fits (representing a recipe for dealing with any sub-type of Block)?

          Because if so, you should be more comfortable with Mach7 solution. Of course, it uses macros and all, but it achieves the goal of addressing all the combinations of types without introducing any other class.

          Note that the solution with Boost.Variant and static visitor offers a useful decoupling: Ballast has no reference to Container and vice-versa. Class Container can be used in contexts other than being a sub-type of Block. Container is not aware that it can be a sub-type in Block. It can be also o sub-type in another Variant.

          Container is also ‘decoupled’ from visitor Fits: Container does not know and does not care if there are going to be any static visitors working on it. It just offers a minimum useful and exhaustive interface: its members:

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

          Class Fits is not a part of interface of Container. It is just an idea what we want to do locally with Container’s minimum interface.

          Further: Block is also decoupled from Fits. The variant does not know or care if you are going to use any static visitors: you might as well use Mach7.

          BTW, I am really grateful for your comments on this post. They help me understand where I fail to communicate clearly what I mean. I think I need to make another post to clarify.

      • dragonp12 says:

        (for some reason I can’t reply to your more-recent comment, sorry! Also, comment formatting isn’t obvious so hopefully I don’t get my tags wrong…)

        BTW, I am really grateful for your comments on this post. They help me understand where I fail to communicate clearly what I mean. I think I need to make another post to clarify.
        I think it might be me who’s not quite communicating clearly what I mean! Let me start again and re-state my issue without using the word ‘coupling’, and hopefully more clearly!

        In the above example you have a system that is interacting with three types that exhibit behaviour that you have defined as Block-like. It wants to use them interchangably/’polymorphically’, so a static_visitor is defined which knows about all three types and is applied to the variant when necessary:

        using Block =
          boost::variant<Ballast, Container, MultiContainer>;
        struct Weight_allowance : boost::static_visitor<Weight> { /* ... */ };
        Block b = /* ... */;
        Weight w = boost::apply_visitor(Weight_allowance(), b);
        

        Weight_allowance explictly knows (and is required to know) about the exact types that are involved in your variant. While this is definitely better than an equivalent switch statement (mainly due to the static verification that all of the variant types are handled), it doesn’t seem to give any benefits outside of ease-of-use in the specific system that you are using the Block variant in.

        If we later implement a new system which cares about a slightly different set of types (e.g. Ballast2, Container, NewContainer), we don’t seem to have much choice but to define a full new Weight_allowance2 visitor class which handles the new set of types.

        Contrast that with our two other types of polymorphism:
        – virtual polymorphism, where adding/handling a new type that conforms to the interface requires no change to existing code that uses objects of that interface.
        – compile-time polymorphism with templates, where the Weight_allowance concept could be implemented for each type using full template specialisation to select the appropriate behaviour.
        In each of these cases the addition of new types requires adding code only for the new type, and code that worked with the original types will work correctly with the additional types without any modification.
        (Although I’m not a great believer in rigid adherence to these principles, it seems like it violates the Open-Closed Principle)

        Ignoring my above issues with using variant, the Mach7 pattern-matching-based behaviour is quite neat and better than the standard visitor implementation, but it seems like the main benefits are syntax/readability – definitely worthy improvements, but I don’t see it as really changing the pattern hugely. I’m happy to accept that I’m missing something fundamental here though!

        Thanks for the responses, enjoying the discussion; I’ve been following your blog for a while but not dived into commenting until now.

        • Thanks for the explanation. I think I understand what you are saying. And no: you are not missing anything. That is the trade-off you make when you choose Boost.Variant; and you choose it when the trade-off sounds just the right thing to do: when the sub-types have practically nothing in common, and you would have to add dozens of member functions, each of which is used only once in the program.

          I only showed a subset of Mach7 that overlaps with Boost.Variant, but to some extent the library offers functionality that might address some of your expectations. When you handle, classes CA, CB and CC in the following hierarchy:

          struct Iface { ~Iface(){} };
          struct CA : Iface {};
          struct CB : Iface {};
          struct CC : Iface {};
          

          And then you add a new class CA2 derived from CA, the handler for CA picks it up by default.

        • dragonp12 says:

          Thanks, that’s a neat feature.

          Your example of how variants and visitors fit together in a more real-world example was quite useful, by the way. I think my default tool to reach for in that situation would be template specialisation – which avoids having to pollute the otherwise-unrelated types’ APIs that a vtable-based solution would require – but variant is clearly a valid option as well and it’s good to know more about it.

  7. Pingback: First Test | ZOLOKI

  8. Adam Badura says:

    Same thing struck me as well. Whenever I see variant examples (also for other languages) they are always “academic”. Sure, they show what can be done but in a way the leaves you wondering why would you ever want to do that in the first place.

    Your example makes more sens. But it is pretty specific. I would gladly see something more generic. Something that more people could relate to or even possibly deal with.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s