Archive for December, 2014

Tutorial on tag dispatching

Posted in Uncategorized on December 15, 2014 by Crazy Eddie

Update: Stephan T. Lavavej (aka STL) provided some feedback: “Overloading on true_type/false_type is still tag dispatching – indeed, it is the simplest, most common form.” I thought I had good reasons for distinguishing situations in which the type is pre-tagged by a trait or typedef as being “tag dispatching” from times when you need to calculate the tag or when the tag isn’t really documenting a concept but just an on/off kind of thing. I now think those reasons were flawed and any time you tag a type and then use that tag as an overload parameter is “tag dispatching”. There is a difference between these methods obviously, but not anything that distinguishes a separate technique. I’ve left the language in this article alone though.

There’s been some confused notions passed around recently that lead me to think there needs to be more information about probably one of the simplest, most powerful metaprogramming techniques that exist in C++: tag dispatching. The reason tag dispatching is powerful is that it leverages the language and the compiler to do work for you so that you don’t have to. It’s a technique whereby you use overload resolution rules to decide between otherwise ambiguous functions.

Concepts and tags

The first part to understand with regard to tag dispatching is the idea of “concepts”. Concepts are not yet a formal part of the C++ language, but they’re integral to discussing many of the components of the standard library–especially those parts that came from the STL.

There’s a good description of concepts over in the boost documentation. There they define a concept as:

A concept is a set of requirements consisting of valid expressions, associated types, invariants, and complexity guarantees. A type that satisfies the requirements is said to model the concept. A concept can extend the requirements of another concept, which is called refinement.

As that link discusses there are different aspects to a concept. There’s the legal expressions available for use on the types that implement the concept. This is the kind of thing that can be analyzed with introspection techniques–in C++ these often center around SFINAE. In this part of the concept we might ask whether, given value ‘x’ of type ‘T’ that implements a concept, whether ‘++x’ is a legal expression.

Other parts of a concept though can’t really be analyzed with C++ metaprogramming. The invariants for example can’t really be asserted at the static level. They can and should be asserted during debug builds, but most of the time that’s the only place where one could get the necessary information to check invariants. Complexity guarantees also can’t be statically analyzed and will be mostly impractical to assert in the product–you’re basically stuck testing if you even have that.

In C++ we address all this using tagging. We tag a type with something that can be accessed during compile time that tells us what concept a type is implementing. This unfortunately means we depend on the author of the type to tag it correctly, but there’s quite literally nothing we can do about that. We might be charged with not writing robust code, but we’re no less beholden to the developer than that we assume someone won’t subclass an interface and disobey the contract of that interface. There are languages such as Rust that try to solve this problem, but C++ does not so there’s really no solution to this problem here.

In C++ we tag types with other types. These tag types are just empty classes that will eventually be compiled out of the program. They may inherit other tags, which will be explained in the next section, but they’ll not be polymorphic so they’ll not have any associated RTTI information. We use them only as values as well and in such ways that they’re never actually used in the program–this allows the compiler to remove them from the final object code.

InputIterator is an example of a concept. The standard library provides the tag for this concept by defining input_iterator_tag. We gain access to this tag through iterator_traits, which contains an internal typedef called iterator_category. The standard also defines a default version of the iterator_traits template that tries to access the iterator_category within its parameter. This means that we can tag our custom iterators either by specializing this template or by just tagging the iterator internally like so:

struct custom_iterator
{
  using iterator_category = std::input_iterator_tag;
  // much more stuff...
};

The reason an external traits template is required is because pointers are also iterators, and we can’t tag them in this way. Thus the standard defines a couple partial specializations for pointers. Here’s the non-const version:

template < typename T >
struct iterator_traits<T*>
{
  using iterator_category = std::random_access_iterator_tag;
  // ... other useful stuff...
};

Even when this is not necessary though it can be beneficial to do provide a metafunction or traits template to retrieve the tag.

Concept refinement

Concepts can refine other concepts similar to how classes can inherit other classes. When a concept refines another concept it means that types implementing the refining concept also implement the refined concept. So for example concept ‘A’ might be refined by concept ‘B’. Say ‘A’ has the requirement that ‘x.foo()’ be a legal expression that results in a type convertible to bool. Concept ‘B’ can require additional expressions and can put further requirements on the result of ‘x.foo()’, saying it requires type bool rather than something convertible to bool for example–since bool is convertible to bool this is fine.

ForwardIterator is an example of a concept that refines another. It refines InputIterator and the main thing that it adds is the ability to iterate over the same range multiple times. This part of the refinement is an essential difference between an InputIterator and a ForwardIterator but it changes nothing about the static interface of the types that implement either. Using introspection alone you’d not be able to decide if an iterator has this ability or not–only tags solve this. Another thing it does is override the ‘*i++’ expression to return a reference. This obeys InputIterator’s version because a reference to ‘value_type’ is convertible to ‘value_type’. This is actually a rather unfortunate and short-sighted part of the standard library because it means filter and transform iterators don’t fit very well into the existing tag structure.

In C++ we represent the refinement relationship using inheritance in our tags. Thus in the standard library the tag for ForwardIterator is the aptly named forward_iterator_tag and it inherits from input_iterator_tag. This allows us to write tag-dispatched functions that specialize at the refinement level we want, catching all below. The advance function makes a good example to explain this because if ‘n’ is some value greater than 1 we want it to just jump directly to that new place given a random access iterator (an iterator for which ‘i += n’ is a valid expression).

Tag dispatching

A tag dispatched function is a function that catches types at a generic level, retrieves a tag labeling the type as implementing the different target concepts, and then uses that tag in an argument for implementation functions. Here’s a version of advance to explain:

// This version actually works more like 'next' in the standard library.
namespace detail_ {

template < typename ForwardIterator >
ForwardIterator advance(ForwardIterator it, int n, std::forward_iterator_tag)
{
    assert(n > -1 && "Can only move a forward iterator forward!");
    while (n--) ++it;
    return it;
}

template < typename RandomAccessIterator >
RandomAccessIterator advance(RandomAccessIterator it, int n, std::random_access_iterator_tag)
{
    it += n;
    return it;
}

}

template < typename Iterator >
Iterator advance(Iterator it, int n)
{
    using tag = typename std::iterator_traits<Iterator>::iterator_category;
    // We're doing this silly and not allowing input iterators, we should make a readable message
    static_assert(std::is_base_of<std::input_iterator_tag, tag>::value, "Can only advance ForwardIterators and their refinements.");

    return detail_::advance(it, n, tag{});
}

It’s actually debatable whether we want to have that static_assert in the entry function–I purposfully made the implementation terrible to raise this concern. We might want to allow people to provide an overload for that base iterator concept. In general though you don’t want to do this–you’re writing your dispatch functions to be as complete as they’ll ever be and you don’t want to try being too generic. YAGNI. Without the static_assert you’ll get what is known far and wide as, “template vomit,” which is where C++ gets its reputation for very long error messages. It probably wouldn’t be all that deep.

The way this code works depends on tags that have direct correlation to the concepts being implemented. RandomAccessIterator is a refinement of BidirectionalIterator, which is in turn a refinement of ForwardIterator. Furthermore we may soon have ContiguousIterator, which will be a refinement of RandomAccessIterator. The tags directly correlate to these concepts and their refinement relations through inheritance:

struct input_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

// in C++ 17 maybe
struct contiguous_iterator_tag : random_access_iterator_tag {};

// Orthoganal concept that doesn't refine any of the others and isn't refined by them
struct output_iterator_tag {};

C++ has a rule regarding function overloading that requires the compiler to chose the closest match. This means that when we pass a value of type bidirectional_iterator_tag, which due to inheritance is convertible to forward_iterator_tag, the compiler will pick the ForwardIterator version of our overload set. However, if instead random_access_iterator_tag or any subclass is passed in the RandomAccessIterator version will be chosen.

We accept the tag by value because we don’t care about slicing and to give the compiler a better opportunity to optimize that parameter out of the program.

It’s important that these relationships are consistent, otherwise people that use them may run into problems. The purpose of these tags is to filter input types to our functions down to the interface that function depends on. We break that if our tags don’t correlate directly with the concepts we’re claiming to implement.

Getting it wrong

In his technique comparison article, Mr. Fultz compares different methods to resolve generic overloads. Unfortunately the entire article is colored by his desired outcome, the last method. Especially problematic is the tag dispatching version because it confounds tags, which should be representing concepts, with a particular overload ordering. Here is his set of tags:

struct base_tag {};
struct sequence_tag : base_tag {};
struct range_tag : sequence_tag {};

These tags are meant to represent a static if logic rather than concepts but yet they still correlate with concepts. The range_tag is meant to represent dynamic sequences like std::vector, sequence_tag is for static sequences like std::tuple, and base_tag is the default, which assumes “streamable”. The goal, explained by the author elsewhere, is to implement logic like the following:

template < typename T >
void print(T const& t)
{
  if (is_range<T>) range_print(t);
  else if (is_sequence<T>) sequence_print(t);
  else stream_print(t);
}

This rather misses the point of tag dispatching though, which is to leverage the compiler to decide this stuff for you. The problems here can be seen if you consider something he claims about his tag deciding function: “Now even though this logic is little complicated it only needs to be written once.” One would assume he means we could use this logic for dispatching other functions, but if I used it for that I might write something like so:

namespace detail_ {

template < typename T >
void foo(T const& t, base_tag);

template < typename T >
void foo(T const& t, sequence_tag);

}

template < typename T >
void foo(T const& t)
{
  using tag = typename get_print_tag<T>::type;
  detail_::foo(t, tag{});
}

It doesn’t really matter how the detail parts are written, if I pass in a std::vector to foo then bad things are going to happen. I should be able to depend on it behaving correctly but I can’t. Granted, it’s going to error out at compile time given these particular concepts, but it’s not exactly going to be pretty. To avoid the template vomit phenomenon I’d have to write something like this:

template < typename T >
void foo(T const& t, sequence_tag)
{
    static_assert(is_sequence<T>::value, "Passing off a non-sequence as a sequence you silly sod!");
}

This shouldn’t be necessary.

Fixing it

So lets see if we can fix the issues. The first thing we should do is make sure the tags correspond with concepts correctly. We have two orthoganal concepts and one that’s just totally unrelated to the other two:

  1. Sequence: a static sequence
  2. Range: a dynamic sequence
  3. Streamable: something we can use the stream operator on

The first two are mutually incompatible. There’s no such thing as a static, dynamic sequence–a container is one or the other but not both. The third is entirely unrelated to either of the other. A type that is either Sequence or Range could either be or not be Streamable. Our corrected tags are then:

struct streamable_tag {};
struct range_tag {};
struct sequence_tag {};

At this point we can see that the problem doesn’t really decompose into something that tag dispatching can get a purchase on. There’s nothing at all for the compiler to decide. Underneath these different kinds of concept there is certainly room for tag dispatching. Ranges for example are one of a variety of different kinds within a hierarchy of concepts. Sequences also come in different kinds like ForwardSequence or BidirectionalSequence. All of these types will have different tags associated with them that can be dispatched upon, but they’ll not be attached to the same traits metafunction or typedefs as in the orthoganal hierarchy.

We can still do something very much like tag dispatching though by creating the static if/else logic that Mr. Fultz was after:

// Because technically we're just defaulting here, so we shouldn't tag the type as streamable
// if we don't know it is.
struct try_streaming_tag {};

template < typename T >
struct select_print_tag
  : mpl::eval_if
    <
      is_range<T>
    , mpl::identity<range_tag>
    , mpl::if_
      <
        is_sequence<T>
      , sequence_tag
      , try_streaming_tag
      >
    >
{};

Note that eval_if is used for the outer if because we don’t want the inner to be evaluated if the first check is true. As far as whether we do range first or sequence first it doesn’t matter–we could go either way and since they’re orthoganal and unrelated no call would change. What does matter though is the last one because we want to use range or sequence overloads if possible and default to the stream. Since ranges and sequences can be streamable there’s an ambiguity that must be resolved and we’re picking non-stream overload first. This is also why the whole issue can’t be quickly solved by simple enable_if checks (sequence vs. range could, but the streaming bit throws a wrench in).

This seems like its pretty verbose, and it is, but we can now use this function and the tags without screwing up:


template < typename T >
void print(T const& t, try_streaming_tag) { std::cout << t; }

template < typename T >
void print(T const& t, range_tag) { for (auto const& v : t) print(v); }

template < typename T >
void print(T const& t, sequence_tag)
{
  fusion::for_each(t, [](auto const& v) { print(v); });
}

template < typename T >
void print(T const& t)
{
  using tag = typename select_print_tag<T>::type;
  print(t,tag{});
}

No artificial, arbitrary, and ill-conceived inheritance hierarchy for the tags is necessary here. The only reason for tags to inherit from each other is if they are reflecting concepts that refine each other. This allows the base-class resolution to trigger the use of overloads for the base-concept. We don’t need or even desire that here.

It’s hard to justify using tags like this. We’re not really benefiting from them at all. We still have to teach the compiler how to select the tag, so we’re not re-using the compiler’s logic. It does seem more legible though than either the “function overloading” or “conditional overloading” examples from the original blog. The former because that version has to repeat the logic in the select metafunction above for each function (with some sharing between them, which IMO just makes it harder to understand), and the latter because it’s a little bit macro heavy. The selection logic is also more focused this way, but that’s not really usual for tag dispatching (where the selection logic isn’t even in code but in the compiler).

Another method that is perhaps arguably better would be to use std::true_type and std::false_type as tags and just have is_xxx parameters–almost tag dispatching but not quite. Would work like so:


template < typename T, typename Ignore >
void print(T const& t, std::true_type, std::false_type, Ignore)
{
  range_print(t);
}

template < typename T, typename Ignore >
void print(T const& t, std::false_type, std::true_type, Ignore)
{
  seq_print(t);
}

template < typename T >
void print(T const& t, std::false_type, std::false_type, std::true_type)
{
  std::cout << t;
}

// Tick traits don't appear to return the standard bool types so we need some translation
template < typename T >
struct test_ : mpl::if_<T, std::true_type, std::false_type> {};

template < typename T >
using test = typename test_<T>::type;

template < typename T >
void print(T const& t)
{
  print(t, test<is_range<T>>{}, test<is_sequence<T>>{}, test<is_streamable<T>>{});
}

There’s some key differences here. First of all, if there ever were a Sequence that was also a Range we’d get a compile failure because there’s no overload to accept it. This is probably desirable because it would point this out rather than just silently defaulting one way or the other. Second of all the if/else logic required by both my former example and all of Mr. Fultz’s examples is gone. This version truly puts that effort on the compiler to figure out, we just give it the patterns and where to get the constraints…and we didn’t need tags at all. Finally, non-streamable types that don’t fit the other two concepts don’t wait to be inside the stream overload to abort during compilation. There’s no overload for that situation either.

Just overload it when you can!

There’s a couple branches from the original version that I didn’t address.

The first is the variant version. This one is actually not necessary and does nothing interesting, variant already knows how to print itself because it overloads the stream operator.

The second is for std::string. This one is important because unless we do something we’ll use the range version of the print function. The way I’ve written it we’d get the same output, but it’s gonna be the slow way and it’s completely logical that we’d put commas between range items–something we’d not want to happen to strings. The way to deal with this though is blazingly simple and requires nearly zero special consideration:

void print(std::string const& str) { std::cout << str; }

Concluding remarks

There’s a lot of reasons to prefer tag-dispatching and the similar construct I explained here over heavy use of SFINAE and/or deep macros. Neither of these latter tools should be discarded, but both introduce complexities that should be avoided when possible. There’s a lot that can be done with tags and things like tags to simplify code. It’s important though that when doing so you don’t try to outsmart the compiler, which can lead you to making poor decisions. Function overloading, with or without tags, can be a very powerful tool.