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 }; |
Listing 1 |
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()); } |
Listing 2 |
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()); } |
Listing 3 |
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()); } |
Listing 4 |
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(); } |
Listing 5 |
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.
Overload Journal #129 - October 2015 + Programming Topics
Browse in : |
All
> Journals
> Overload
> o129
(5)
All > Topics > Programming (877) Any of these categories - All of these categories |