An Inline-variant-visitor with C++ Concepts

Variants allow run-time handling of different types, without inheritance or virtual dispatch, and can be useful when designing loosely coupled systems. J.B.Coe and R.J.Mill [ Mill14 ] previously showed a technique to avoid writing boilerplate code when writing visitors for the traditional inheritance-based Visitor pattern. We modify the inline-visitor technique to handle variant-based visitation and use Concepts [ Sutton13 ] from the Concepts TS [ Concepts ] to switch run-time behaviour depending on syntactic properties of the class encountered.

Variants

A variant is a composite data type formed from the union of other types. At any point the type of the data contained within a variant can only correspond to one of the composite types. Variants are useful when data flow through a program needs to correspond to multiple possible types that are not logically related by inheritance. For instance, the data within a spreadsheet cell could be an integer, a floating point value or a text string. We can represent such a spreadsheet cell by a variant of int , double and string . We can use this variant type within our program as a function argument type or return type and defer type-specific handling to a later point.

The boost libraries offer a variant type [ Boost ] as does the eggs.variant library [ Eggs-1 ]. There are differences between the different offerings of variant but for the purposes of our inline visitor they are much the same and could be implemented as a union of types with an index used to determine which type is active (see Listing 1).

class ExpositionOnlyVariant
{
  union Data_t
  {
    int i_;
    double d_;
    string s_;
  };

  Data_t data_;
  size_t active_type_;
  
  size_t which() const { return active_type_; }
   
  // Other non-illustrative methods and
  // declarations
};
			

Our code examples focus on eggs.variant which is a lot more sophisticated than the exposition-only variant class above (especially where constexpr methods are concerned) [ Eggs-2 ].

Design decisions about exception safety and default construction are interesting and, at the time of writing, under much discussion among the ISO C++ standards body, but beyond the scope of this paper.

A visitor For variants

The Gang of Four [ GoF ] describe the Visitor pattern as “ Represent an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates. ”

We can use visitors to implement the type-specific handling our variant may require.

Writing a visitor on a variant type is a straightforward matter that entails determining the value of the discriminator and dispatching to a function that accepts the corresponding concrete type. For example, we could explicitly build a function that applies a visitor for our previously mentioned spreadsheet. See Listing 2.

using Cell = variant<int, double, string>;

template<typename R, typename Visitor> 
R apply(const Cell& c, Visitor&& v)
{
  switch (c.which()) {
    case 0: return v(get<0>(c));
    case 1: return v(get<1>(c));
    case 2: return v(get<2>(c));
    default: throw std::logic_error
      ("Bad variant type");
  }
}

struct DoubleCell_t
{
  int operator()(int n) { return n*2; }
  double operator()(double d) { return d*2; }
  string operator()(string s) { 
    return s.append(s); }
};

Cell DoubleCell(const Cell& c)
{
  return apply<Cell>(c, DoubleCell_t());
}
			

Generic code with templates

Templates in C++ allow the definition of functions and classes with generic types [ Vandevoorde02 ]. We can, for instance, define a generic function that doubles its argument.

  template<typename T>
  T double(const T& t)
  {
    return t*2;
  }
  
  assert(8.0 == double(4.0));

We can define an operator() template for a visitor which will mean it can be invoked on any type. This allows us to specify default behaviour for types that are not explicitly handled (function templates have lower precedence when it comes to overload resolution so a more specific function will be picked where available). See Listing 3.

struct DoubleCellWithGenerics_t {
  template<typename T>
  T operator()(const T& t) { return t*2; }

  string operator()(string s) {
    return s.append(s); }
};

Cell DoubleCellWithGenerics(const Cell& c) {
  return apply<Cell>(c,
  DoubleCellWithGenerics_t());
}
			

This is appealing; we can define default behaviour for our visitor (the generic member function) and define exceptions to this default behaviour (with specific overloads). In this case, the generic version uses operator* for all non- string members of the variant, and the string version resorts to an append member function.

This could become irksome if there were many exceptions, and we have to know about types which need special handling ahead of time. For example, if we later extend Cell to include support for wide-character strings (e.g., std::u16string ), then we would need to add overloads to each visitor function to provide the required functionality. In addition, there's no way we could reasonably expect our visitor to cope with arbitrary user-defined types. Adding date or time representations to Cell would require even more overloads.

However, if we could predetermine sets of abstract data types to which the visitor can be applied, then we could define a small set of generic functions to accommodate those behaviours. That is, some methods would use operator* , while others used append , some might throw exceptions, and so on. Concepts make this easy.

Constraining templates with Concepts

Concepts are an extension to the C++ Programming Language, defined as an ISO Technical Specification [ Concepts ]. The Concepts extension allows the specification of constraints on template arguments in a straightforward, and often minimal way. While, templates can be restricted using SFINAE tricks with enable_if [ Vandevoorde02 ], Concepts provides a more readable notation and vastly improved support for overloading.

Listing 4 is a fully generic visitor written using concepts.

struct DoubleCellWithConcepts_t {
  int operator()(const Numeric& n) { return n*2; }
  string operator()(Appendable s) { 
  return s.append(s); }
};

Cell DoubleCellWithConcepts(const Cell& c) {
  return apply<Cell>(c,
  DoubleCellWithConcepts_t());
}
			

We only need two overloads to fully accommodate the breadth of abstractions included in our Cell representation. The first overload takes an argument of type Numeric and the second an argument of type Appendable . These are concepts. A concept is a compile-time predicate that defines a set of requirements on a template argument.

When a concept name is used in this way, it declares a function that accepts any type that satisfies the requirements of that concept. To help make that more explicit, we could have declared the first overload like this:

  template<typename T>
    requires Numeric<T>()
  int operator()(T n) { return n*2; }

Here, Numeric is explicitly evaluated by a requires clause. Of course, this is more verbose so we prefer notation above.

With this visitor, the Numeric overload defines the behaviour for the int and double members of Cell , For that matter, this will be the behaviour for any numeric type that might include in the future (e.g., vectors or matrices?). Similarly, the Appendable overload defines the behaviour for all sequence-like objects.

In this example, Numeric and Appendable are function templates, declared with the concept specifier. Here is the definition of Appendable that we use above:

  template<typename T>
  concept bool Appendable() {
     return requires(T& t, const T& u) {
       { t.append(u) } -> T&;
     };
  }

The requires expression in the body of the function enumerates the syntactic requirements to be satisfied by a type T . Here, we require T to have a member function append , taking an argument of the same type. The return value, specified by the -> T& must be implicitly convertible to T& . If any of those requirements are not satisfied, the concept is not satisfied.

Concepts are effective ways of specifying syntactic requirements. However, a meaningful concept definition also needs semantic requirements. What is append required to do? The concept used in this example is not especially well-designed because it isn’t obvious how to specify the semantics of an Appendable type, when we have only a single operation. Additional requirements like size and back would be helpful. In the future, we will endeavour to present only complete concepts.

Concepts are a very powerful tool and their first-class status in terms of compiler diagnostics make their consumption by non-expert users much more straightforward. Furthermore, the use of concepts will never add runtime overhead to your program. A technique like type-erasure could be used instead, but it can be difficult to implement, and it adds hidden runtime costs.

The Concepts TS has been sent for publication by ISO and is implemented in GCC trunk [ GCC ].

An inline-variant-visitor with Concepts

Defining the visitor outside the function in which it is used is necessary if it has generic functions. The inline-visitor pattern for the traditional visitor can be adapted to variant visitors and allow definition of concept-constrained generic functions inline at the point of use.

  auto DoubleCell(const Cell& c)
  {
    auto inline_cell_visitor 
       = begin_variant_visitor()
      .on([](Numeric n) { return n*2; })
      .on([](Appendable a) { return a.append(a); })
      .end_visitor();
    return apply<Cell>(c, inline_cell_visitor);
  }

This function is now hardened against future changes in the definition of the variant, Cell . Adding a new Appendable member to that variant would not require changes to this function. In fact, unless a future change adds entirely new categories (i.e., concepts) of members to the variant, we should never have to modify this function again (unless it contains a bug).

The inline-variant-visitor is implemented in much the same way as the inline-visitor [ Mill14 ]: an inner composable function object is recursively built up and finally instantiated.

Conclusion

We have presented a method for generating visitors inline for variants where the run-time type-specific handling can be specified in generic terms depending on syntactic properties of the run-time type. Concept-based handling of variants can facilitate the writing of generic header-only libraries that make use of variant<Ts...> arguments. Type-specific handling of user-defined types, unknown to the library author, can be simply specified in terms of supported concepts.

Although there are slight differences in optimised assembler output with and without the inline-variant-visitor, there is no measurable run-time penalty for its use.

Appendix

Implementation of a concept-enabled inline-variant-visitor (Listing 5).

#include <string>
#include <utility>

// These using declarations are for publication
// brevity only
using std::make_pair;
using std::move;
using std::pair;
using std::nullptr_t;

template <typename F, typename T> concept bool UnaryFunction() {
  return requires(const F &f, const T &t) {
    { f(t) }
  };
}

template <typename F, typename BaseInner,
  typename ArgsT>
struct ComposeVariantVisitor {
  struct Inner : BaseInner {
    Inner(ArgsT &&a) : BaseInner(move(a.second)),
    f_(move(a.first)) {}

    using BaseInner::operator();

    template <typename T>
    requires UnaryFunction<F, T>() 
      auto operator()(const T &t) {
      return f_(t);
    }

  private:
    F f_;
  };

  ComposeVariantVisitor(ArgsT &&args) :
    m_args(move(args)) {}
	
  template <typename Fadd> auto on(Fadd &&f) {
    return ComposeVariantVisitor<Fadd, Inner,
        pair<Fadd, ArgsT>>(
        make_pair(move(f), move(m_args)));
  }

  auto end_visitor() { return Inner(move(m_args)); }

  ArgsT m_args;
};

struct EmptyVariantVisitor {
  struct Inner {
    struct detail_t {};

    Inner(nullptr_t) {}

    void operator()(detail_t &) const {}
  };

  template <typename Fadd> auto on(Fadd &&f) {
    return ComposeVariantVisitor<Fadd, Inner,
        pair<Fadd, nullptr_t>>(
        make_pair(move(f), nullptr));
  }
};

EmptyVariantVisitor begin_variant_visitor() {
   return EmptyVariantVisitor(); }
			

References

[Boost] http://www.boost.org/doc/libs/1_59_0/doc/html/variant.html

[Concepts] Sutton, Andrew (ed). ISO/IEC Technical Specification 19217. Programming Languages – C++ Extensions for Concepts, 2015.

[Eggs-1] http://eggs-cpp.github.io/variant/

[Eggs-2] http://talesofcpp.fusionfenix.com/post-20/eggs.variant---part-ii-the-constexpr-experience

[GCC] svn://gcc.gnu.org/svn/gcc/trunk

[GoF] E. Gamma et al., Design Patterns . Addison-Wesley Longman, 1995.

[Mill14] Robert Mill and Jonathan Coe, ‘Defining Visitors Inline in Modern C++’. Overload 123, October 2014.

[Sutton13] Andrew Sutton, Bjarne Stroustrup, ‘Concepts Lite: Constraining Templates with Predicates’. https://isocpp.org/blog/2013/02/concepts-lite-constraining-templates-with-predicates-andrew-sutton-bjarne-s

[Vandevoorde02] Vandevoorde, David; Nicolai M. Josuttis (2002). C++ Templates: The Complete Guide Addison-Wesley Professional. ISBN 0-201-73484-2.