Concepts without Concepts

“Concept” can mean two things in the context of C++ generic libraries:

1. Something informal: something we know about template parameters, and can tell to other human programmers, e.g. in documentation.
2. A language feature.

This post is about concepts in the first sense. It claims that we had concepts for quite a while already, and shows how we can use them to make generic libraries easier to use.

We start with an ordinary template declaration:

template <typename T, typename A = allocator<T>>
class vector<T, A>;

According to C++ rules, T can be any type whatsoever. But do we agree on the scope of “any”? For instance int& is a type, void is a type, const int is a type.

But that is not a problem in practice because we intuitively know what types can and what types cannot be used as arguments to vector. This is because there is a concept around. It may be not even specified in documentation, but we clearly sense it.

But relying on the intuition, or even written documentation, has its limits. The following is the classical motivating example from an introduction to C++ concepts (as language feature):

#include <list>
#include <algorithm>
#include <iostream>

int main()
{
  std::list<int> il {6, 2, 4};
  std::sort(il.begin(), il.end());
  for (int i : il) std::cout << i << " ";
}

This program looks simple, clear and correct at first, but in fact it ends in compile-time failure. But what is striking the most is not that we have an error, but the contents of the error message.

For GCC error message see here.
For Clang error message see here.

Long story short, the error message is very long and it is difficult to understand what the source of problem is in our code. I do not even show it here.

One could conclude from this that a language feature like Concepts Lite just must be added to the language, so that we never see these ugly and cryptic error messages again.

But one could conclude something rather different also: why did the implmenters of these versions of the Standard Library not put an effort to generate better error messages from their generic library, using the means available today?

Let’s try to do it ourselves. We will implement our own function sort. We start by wrapping std::sort:

template <typename RAI>
void sort2(RAI begin, RAI end)
{
  std::sort(begin, end);
}

Let’s ignore the custom sorting criterion, and solve the problem for sorting with operator<.

Now, let’s define a meta-function that tells us whether a given type is a random-access iterator or not. Because this is in fact the source of the compiler error: std::sort only works on random-access iterators.

For every iterator that is designed to work with STL algorithms, we expect that there exists a specialization of class template std::iterator_traits, and that this specialization for random-access iterators has nested type definition iterator_category that is either std::random_access_iterator_tag or something derived thereof.

We can express it with a type trait:

template <typename RAI>
struct is_random_access_iterator :
  std::is_base_of<
    std::random_access_iterator_tag,
    typename std::iterator_traits<RAI>::iterator_category
  >
{};

We can try to make use of it now:

template <typename RAI>
void sort2(RAI begin, RAI end)
{
  static_assert(is_random_access_iterator<RAI>::value,
                "requires a random-access iterator");
  std::sort(begin, end);
}

The result of compiling this function template with a bad iterator looks more-less like this:

error: static_assert failed "requires a random-access iterator"
  static_assert(is_random_access_iterator<RAI>::value,
  ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: in instantiation of function template specialization
      'sort2<std::__1::__list_iterator<int, void *> >'
      requested here
    sort2(il.begin(), il.end());
    ^
<< SAME LONG AND OBSCURE MESSAGE FOLLOWS >>

The error report starts with a clear message: a call to sort2 triggers assertion failure because it requires the argument to be a random-access iterator, or more formally, to satisfy the condition is_random_access_iterator.

What is disappointing, and may be surprising, is that despite the static assertion failure we still see the long and ugly error message, which may shadow our clear message at the top.

This is because, while the language requires that compiler issues a diagnostic message upon assertion failure, and that the compilation must not succeed, it does not require that the compilation process must stop immediately. Therefore the compiler proceeds (even though it knows it must report failure ultimately) in order to collect as many information as possible about the context of the failure and give it to us.

We can easily dodge this. Instead of static_asserting, we can do what Concepts Lite do: hide a function whose constraints are not satisfied:

template <typename RAI>
  typename std::enable_if<
             is_random_access_iterator<RAI>::value
           >::type
sort2(RAI begin, RAI end)
{
  std::sort(begin, end);
}

Now the message we get says that no matching overload was found. The three compilers I tested this on: Clang, GCC and Visual C++, also mention that they have seen our sort2 but rejected it. Additionally, Clang treats std::enable_if almost as a keyword, and is able to tell that the overload was deliberately removed from the overload set because is_random_access_iterator<RAI>::value returned false. See it here.

GCC also mentions, std::enable_if in error message, so it should not take much time until we realize what the problem is.

Arguably, using std::enable_if in the declaration makes it less readable. In C++14, we can improve the readability slightly by using an alias template std::enable_if_t.

To further improve the readability of the error message, in a portable way (on all compilers), we can create two overloads of sort2 that are switched between by a compile-time Boolean condition. One does the sorting, the other does a static_assert. Do you know how to do it?

#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>

template <typename RAI>
struct is_random_access_iterator
  : std::is_base_of<std::random_access_iterator_tag,
  typename std::iterator_traits<RAI>::iterator_category>
{};

template <typename RAI>
std::enable_if_t<is_random_access_iterator<RAI>::value>
sort2(RAI b, RAI e)
{
  std::sort(b, e);
}

template <typename FI>
std::enable_if_t<!is_random_access_iterator<FI>::value>
sort2(FI, FI)
{
  static_assert(is_random_access_iterator<FI>::value,
                "requires a Random-Access Iterator");
}

int main()
{
  std::list<int> il{ 6, 2, 4 };
  sort2(il.begin(), il.end());
  for (int i : il) std::cout << i << " ";
}

The real life

So far, we were addressing the particular case where a weaker category of iterator is passed where a random-access iterator is expected. In this case, we can safely use std::iterator_traits because they are guaranteed to be specialized for any iterator category. But in real programs, we also want to get informative and friendly error messages, when sort2 is passed something that is not an iterator at all.

Now the problem is a more difficult one, and requires of a generic library author a bit of creativeness. We will create a meta-function get_tag which for a given type T returns:

• if T is an iterator: the corresponding iterator category tag,
• otherwise: void.

template <typename T>
  typename std::iterator_traits<T>::iterator_category
  get_tag_(T const&);

void get_tag_(...);

template <typename T>
  using get_tag = decltype(get_tag_(std::declval<T>()));

This function declaration with ellipsis is a good old C declaration of a variadic function, taking any number of arguments of any type. You could think that nobody should have any business using them in C++ now that we have variadic templates. But they are used all right by generic programming geeks, for their special properties connected to overload resolution. The special properties are these:

• a variadic function is always a viable match,
• a variadic function is always the worst match.

Whenever our alias template get_tag is ‘evaluated’ for a given type T, we pretend that we call function get_tag_. There are two overloads to select from. If T is an iterator (and std::iterator_traits<T>::iterator_category represents a valid nested type) the first overload is considered a better match than the second one: it gets chosen, and its return type selected. In contrast, when T is not an iterator, std::iterator_traits<T>::iterator_category is not even well-formed, and the function declaration cannot even be parsed. Therefore, compiler pretends it hasn’t seen the first overload of get_tag_ at all (this is called SFINAE), and as the result, it can only see one overload, the variadic function, which is always the worse viable candidate, but in this case it is also the best one.

Because we are using decltype we are only pretending we are evaluating functions, so they are not even required to have definitions (bodies). In fact, we are only interested in the types they return. When the first overload is selected, the return type is the iterator category tag: when the second one is selected, we get void.

Now implementing the type-trait is quite trivial:

template <typename T>
  using is_random_access_iterator = 
  std::is_base_of<std::random_access_iterator_tag, get_tag<T>>;

What we can learn from this exercise is that implementing a decent type trait for checking a function template parameters is doable but hard. It might get even harder, in fact. In our example we are quite lucky that the Standard requires of the iterators to specialize std::iterator_traits.

In general case, we will have to use tools like “expression-based SFINAE” or Boost’s Type Traits Introspection Library to inspect the properties of types (like presence of nested typedefs, or member functions). In fact, Boost comes with a library precisely for this purpose: Boost Concept Check Library.

But I do not expect just everybody to use these tricks. We are talking about the authors of generic libraries, who need to understand the tricks related to templates and two-phase look-up anyway. The authors of STL implementations can surely handle techniques like the one shown above.

Sometimes clever detection and reporting of potential programmer bugs goes beyond concept checking. Let me give you one example from Boost.Optional library. It provides operator<< for using boost::optional with IOStreams, but because the implementation requires the inclusion of an expensive header, <iostream>, it is provided in a separate file, that users include only when they need the stream operations. But this turned out to be bug-prone. When someone wanted to write boost::optional to a stream and forgot to include the dedicated header, it turned out that the statement like the one below compiled fine:

boost::optional<std::string> opts;
std::cout << opts; 

This worked because opts in pre-C++11 compilers is implicitly convertible to bool and the expression is equivalent to:

std::cout << bool(opts); 

(Well, the situation is more complicated: the implementation used the safe-bool idiom, but the result was the same.) In order to prevent this, in the primary header, the streaming operator has been declared but not defined. This still avoids the inclusion of <iostream> and prevents a bug by generating an error. But this is a linker error that may be difficult to track down, scares people off and does very little to make the life of the user programmers easier.

Ultimately, a certain trick has been employed. boost::optional<T> is derived from a tag-class optional_tag. In the main header file we define a streaming operator only for optional_tag. And its implementation simply triggers a static_assertion with a message saying that, if your intention is to output the contents of optional object, you should include the dedicated header. You can see the implementation here.

And that’s it for today. Note that I do not intend to say that we do not need concepts in the language. I just observe that we can do better than just wait for them to get added. In fact, I am just repeating Robert Ramey’s advice from Boost Library Incubator.