Your own type predicate

In this post we will see how to define a type trait or a type predicate or a meta-function that would allow us to check at compile time whether a type exposes an interface that we need. That is, we want to check if a given type T has:

• nested typename result_type,
• static member function set_limit that takes one argument of type int,
• member function get_result that returns type const result_type& and that is declared not to throw exceptions,

In other words, the following expressions and constructs need to be valid for any variable x of type T:

T::result_type	is a type
T::set_limit(1)	return type unimportant
x.get_result()	returns const result_type&, throws nothing

By “checking” I mean being able to test it at compile time, for instance like this:

static_assert(is_acceptable<X>::value,
              "X does not have a desired interface");

We will do it in C++11. This is also going to be an introduction to “metafunctions” in C++.

I will not try to answer in detail the important question: why do we need such predicate. The short answer is: if we are writing a template library, we can use it to generate better (and shorter) error messages when a user is using our library incorrectly. For more on this, have a look at the advice from Boost Library Incubator, or this excellent talk by Vinnie Falco (which was in fact an inspiration for this post).

Writing a simple metafunction

Term “metafunction” is perhaps too impressive for the simple thing it describes. “Function” here means a function in the mathematical sense: that something is mapped onto something else; “meta” means that we do not mean invoking functions in the C language sense (initializing objects representing arguments to functions and performing a function call). Instead, a metafunction is a language construct, where you put one or more types and perhaps some compile-time constans, and the construct “produces” a different type (which can later be converted to a constant value).

So, going back to the initial code example:

static_assert(is_acceptable<X>::value,
              "X does not have a desired interface");

is_acceptable is a metafunction. It is a function in the mathematical sense. It takes a (one element) set of arguments — which in our case is type X — and maps it on a different type: is_acceptable<X>. Next, we “convert” this type into a Boolean value, by accessing its static data member value. Its type is bool.

Accessing static data member value is a traditional way in C++ of obtaining integral or Boolean values from types returned by metafunctions and we will follow it. In total, we can say that we have mapped from a type onto a Boolean value.

The most trivial metafunction we could define is this:

struct true_type
{
  static constexpr bool value = true;
};

And we can “invoke” it like this:

static_assert(true_type::value, "***");

This function is really trivial. It takes zero arguments and “returns” a type that always converts to Boolean value true. We can say that true_type is value true but encoded as a type rather than value.

It is not useful on its own, but is very useful as a building block for more practical meta-functions.

Using a corresponding, second building block:

struct false_type
{
  static constexpr bool value = false;
};

we can try to build some more meaningful functions. First task: a metafunction that detects if given types T and U are identical.

Since our metafunction needs to take parameters, we will have to use a class template. Most of the time our metafunction will return false, so let’s start with this case:

template <typename T, typename U>
struct is_same : false_type {};

Now, is_same is a class template, so in order to use it, you have to provide two types. Also, it derives from false_type, so accessing data member value works, and the result is always false:

static_assert(is_same<int, char>::value, "***");  // fires!
static_assert(!is_same<int, char>::value, "***"); // ok

But as it is now, it will give wrong result even for two ints. So let’s fix it. We will specialize the template for the case where T and U are identical.

template <typename T>
struct is_same<T, T> : true_type {};

This is called a partial template specialization. It has only one parameter in line 1 (the previous template had two), but it does not mean that we can use is_same with one parameter. It only means that we have defined a pattern in the sense of pattern matching. Class template is_same is always instantiated with two parameters, but once the two parameters are provided, the primary template and the specialization are inspected in order to determine which is a better match. The former is always a good match for any two types; the latter is a better match for two identical types. The definitions of two templates are significantly different: the former derives from false_type, the latter from true_type. This achieves the desired result:

static_assert(is_same<int, int>::value, "***");   // ok
static_assert(!is_same<int, char>::value, "***"); // ok

Now, the last exercise before we solve the real problem: we want to check if the size of a given type (as measured with operator sizeof) is 1. It is easy to do with expressions directly:

static_assert(sizeof(T) == 1, "***");

But we want it wrapped into a C++-style metafunction. We will also specialize class templates but in a more clever way. First, the primary template:

template <typename T, bool Small = (sizeof(T) == 1)>
struct is_small : false_type {};

This time we have a second parameter Small. It is not a type, it is a value, and more importantly it has a default value, so users will not know that there is a second parameter. They will just call it with a single type:

static_assert(!is_small<int>::value, "***");

Value Small keeps internally the answer to the question. But the template without specialization always represents value “false” (it is derived from false_type). While value Small is invisible outside, we can use it internally in providing the partial specialization:

template <typename T>
struct is_small<T, true> : true_type {};

This specialization is a better match for types where the value of condition Small (evaluated in the primary template) is true; and this specialization represents value “true”. Let’s test it:

static_assert(is_small<char>::value, "***");
static_assert(!is_small<int>::value, "***");

// the following are platform dependent, 
// but work in practice:
struct Empty {};
static_assert(is_small<bool>::value, "***");
static_assert(is_small<Empty>::value, "***");

But we can implement metafunction is_small in a different way. It is a bit more complicated, but it illustrates some mechanics of template instantiations. We will first define a meta-metafunction, enable_if. This also requires a primary template and a specialization:

template <bool Cond>
struct enable_if
{
  // empty body
};

template <>
struct enable_if<true>
{
  typedef void type;
};

Again, we have a class template which is parametrized by a Boolean constant. If the value is true, the class has a member typedef type; otherwise no typedef type is present. This gives us a very strange mapping. In the previous case of metafunction is_same<T, U>, T and U pair was mapped onto either type true_type or type false_type. In the current case, in construct typename enable_if<C>::type, Boolean value C is either mapped onto a valid type, or onto a type-system error, depending on whether C is true or false. The actual type is not important, it is this error versus non-error that is the crux here.

The usage of keyword typename is characteristic of C++ metaprogramming. Without it compiler would have to assume that name type refers to a static data member. Since C++11, we can instruct the compiler in a different way, which additionally makes the notation more concise, by using an alias template:

template <bool Cond>
using enable_if_t = typename enable_if<Cond>::type;

Now, we again had to use the typename, but only once. Henceforth, anyone can just refer to the nested type as enable_if_t<C>.

And we can similarly say that construct enable_if_t<C> maps C onto a valid type when C is true and onto a type-system error when C is false. This is the most extraordinary application of a notion of mapping I have seen in programming; and as we shall see in a moment, it is still useful in practice.

We can use enable_if_t to implement metafunction is_small2, again the master template and a specialization:

template <typename T, typename /*U*/ = void>
struct is_small2 : false_type {};

template <typename T>
struct is_small2<T, enable_if_t<sizeof(T) == 1>> : true_type {};

The primary template has two parameters. The second one has a default “value”, so the users will not know it is there. I also do not need to know it, so I do not even give it a name. The only reason I need 2nd parameter is for the specialization with one parameter T to be more specialized than the primary template, and in the specialization to have a placeholder where to put a type-or-error generated from enable_if_t.

The specialization takes any T and is always more specialized, and it always gets chosen… as long as it is correct. But we know that when the condition we check, sizeof(T) == 1, is false, enable_if_t will be a type-system error. But this is one of these special places where creating a type-system error while instantiating a template is not a compiler error. Or, to put it in other words, template argument substitution failure is not an error (which is abbreviated to SFINAE).

This means that when I instantiate template is_small2 with type int, the specialization is considered, but because substituting int for T fails (enable_if_t<sizeof(T) == 1> would be a type-system error), compiler simply concludes that this specialization will not work, and just goes with the primary template (which, unlike the specialization, derives from false_type).

(Interestingly, the C++ Standard does not describe this SFINAE behavior for class template specializations. However, all compilers implement it and the Committee members agree that this behavior is intended.)

Note that I used type void as the default for the second template parameter. I also used void for type inside enable_if. In either case I never rely on the fact that it is actually void: I just need any type. Because type void is special in C++, I just re-used it to indicate other special use cases. Any other type would do as well.

The entities we have defined, true_type, false_type, is_same and enable_if are useful tools for meta-programming tricks and type traits, and they are in fact already defined in the C++11 Standard Library. They are a bit more complicated and more developed, but the idea stays the same. Additionally, in C++14 we have alias template enable_if_t.

void_t

There is one more metaprograming tool that we need to define before we solve our problem.

template <typename ...>
struct void_t_impl
{
  typedef void type;
};

template <typename ... T>
using void_t = typename void_t_impl<T...>::type;

And in fact in newer compilers, which fix C++14 issue 1558, it can be implemented even more cleanly:

template <typename... T>
using void_t = void;

This meta-metafunction is perhaps even more bizarre than enable_if_t. Rather than mapping values on values, or types on types, it maps validity on validity. We have a construct that is parametrized by an arbitrary number of parameters — other constructs that potentially represent valid types — and this construct in turn also potentially represents a valid type, provided that all parameters represent valid types.

For instance, consider the following construct:

void_t<int, std::string::value_type>

Each of the two arguments is a construct representing a valid type, thus the entire construct is also a valid construct representing a type. The type is void but again, this is irrelevant: it is only relevant that it is a valid type.

Next, in the following case:

void_t<typename T::value_type, U>

This construct is valid for {T = std::string, U = int} but is invalid for {T = int, U = int}.

We can say that void_t is a Boolean AND function, where value True is represented by construct representing a valid type, and value False is represented by a construct that does not represent a valid type.

What it buys us, is that we have arbitrary number of slots (template arguments) where we can put constructs potentially referring to types — some of them may be in fact invalid types — and we change it to a single construct that we have to test for correctness. The only thing we now need to make use of this facility is a SFINAE context, where a potential type-system error is “converted” into a decision, which overload or template specialization to select.

void_t has turned out to be so useful that we are goting to get it with the Standard Library in C++17.

Building our type trait

Now, back to our task. We want our meta-predicate to detect the following (for any type T, and any value x of type T:

T::result_type	is a type
T::set_limit(1)	return type unimportant
x.get_result()	returns const result_type&, throws nothing

We will apply the same technique as with is_small2: the primary template will always “return” false_type, the specialization will “return” true_type but will be disabled unless all the requirements are met.

The primary template:

template <typename T, typename = void>
  struct is_acceptable
  : false_type {};

For the specialization we will start with only checking for the nested typedef result_type:

template <typename T>
  struct is_acceptable <T, void_t<typename T::result_type>>
  : true_type {};

For now we are only using one slot of void_t. If typename T::type does not represent a valid type, the specialization is skipped and we are going with the primary template.

Now, second thing we should check is if we can call a static member function set_limit with argument of type int. There is a slight problem here: void_t works well with valid/invalid types, but now we need to check a valid/invalid expression. Luckily, there is an easy way to convert a valid/invalid expression into a valid/invalid type: decltype. Let’s try it:

template <typename T>
  struct is_acceptable <T, void_t<
    typename T::result_type,
    decltype(T::set_limit(1))
  >>
  : true_type {};

Now we are using two slots of void_t. decltype inside void_t means that we are testing the validity of an expression.

Now, we need to check if the call to a nullary member function get_result is valid for some variable x of type T. And we have another difficulty here: it is not possible to just insert a name of the variable in the middle of template parameter list.

We could try to do it like this:

template <typename T>
  struct is_acceptable <T, void_t<
    typename T::result_type,
    decltype(T::set_limit(1)),
    decltype(T{}.get_result())
  >>
  : true_type {};

And it would “work” to some extent, but with this we also introduce a yet another inadvertent constraint that T is default-constructible. We do not want this. We want to accept types without a default constructor! But we can still reuse the trick with a temporary. We will need to create a yet another auxiliary general-purpose helper function:

template <typename T>
T declval() noexcept
{
  static_assert(sizeof(T) == 0, "***");
}

The condition inside static_assert can never be true for any T so the program will fail when you try to instantiate its body. But because the condition is dependent on T, the compiler cannot test it until the body is actually instantiated. Thus the definition alone is fine. And also calling this function inside the “unevaluated context” is fine:

decltype(declval<int>())

because in such contexts function template bodies are not instantiated. We only need this function for its declaration; and its declaration has this useful property: the return type of this function is exactly the type we pass as the template argument. Thus, when we type declval<T>() it actually means, “for some temporary object of type T. If you need a temporary reference rather than an object, no problem, just type: declval<T&>(). (This tool has been found to be so useful that it is also part of C++11 Standard Library.)

Now the solution is simple:

template <typename T>
  struct is_acceptable <T, void_t<
    typename T::result_type,
    decltype(T::set_limit(1)),
    decltype(declval<T>().get_result())
  >>
  : true_type {};

Next, how to check that the last expression is declared not to throw exception? We have operator noexcept for just this purpose:

static_assert(noexcept(declval<T>().get_result()), "***");

However, the operator returns true or false, but what the interface of void_t requires is valid or invalid type. we will have to map from true to a valid type and from false to a type-system error. We already know a tool for exactly this purpose: enable_if_t:

template <typename T>
  struct is_acceptable <T, void_t<
    typename T::result_type,
    decltype(T::set_limit(1)),
    decltype(declval<T>().get_result()),
    enable_if_t<noexcept(declval<T>().get_result())>
  >>
  : true_type {};

As we can see, enable_if_t inside void_t means we are testing a Boolean condition. Finally, we need to check that the retun type of get_result is const result_type&.

One way to do it is to check the type of an expression with decltype than test if it is identical with the desired type using a type trait we already know: is_same (or use one from the Standard Library: std::is_same). Then, because the latter returns true/false use enable_if_t to adapt the result to the interface of void_t. The last check will be longer, but no more difficult than the others:

template <typename T>
  struct is_acceptable <T, void_t<
    typename T::result_type,
    decltype(T::set_limit(1)),
    decltype(declval<T>().get_result()),
    enable_if_t<noexcept(declval<T>().get_result())>,
    enable_if_t<
      is_same<decltype(declval<T>().get_result()),
              const typename T::result_type&
             >::value
    >
  >>
  : true_type {};

And because what we typically do with values returned from functions is to use them to copy-initialize a new object:

Calc c; // is_acceptable<Calc>::value is true
Result r = c.get_result(); // copy-initialization

We are only interested if Calc::result_type is convertible to Result: they do not necessarily have to be the same type. We can relax our constraint from is_same to std::is_convertible. In fact, this is what Concepts Lite typically do.

Concepts Lite

If we used Concepts Lite (which are shipped with GCC 6), our meta-function could be rewritten as:

template <typename T>
concept bool is_acceptable = requires(T x, int i)
{
  typename T::result_type;
  T::set_limit(i);
  { x.get_result() } noexcept -> const typename T::result_type&;
};

The first two constraints look quite obvious, the third requires some explanation. Expression in braces must be well-formed. The following noexcept means that the entire expression must be detected as not throwing exceptions: either we are only using built-in operations, or functions declared noexcept. The type following the arrow is a requirement that the type of the tested expression must be convertible to the type. There is no direct way to say that a given expression must have exactly a given type. So, people when they want to specify an exact return type use a hack:

template <typename T>
concept bool is_acceptable = requires(T x, int i)
{
  // ...
  { x.get_result() } noexcept
     -> Same<const typename T::result_type&>;
};

Same is a concept counterpart of type trait is_same:

template <typename T, typename U>
concept bool Same = is_same<T, U>::value;

The semantics of the hacky constraint is, expression x.get_result() returns some type Z and of this type we require that constraint Same<Z, const typename T::result_type&> is satisfied.

The version of our predicate using Concepts Lite is much shorter and cleaner. One reason for this is that we can declare variables x and i and we can use them to build valid expressions. No need for using declval. In fact, there is a way to write a concept-like constraint in C++11, where we can also operate on variable names and do away with declval.

“Requires” in C++11

First, we will define an auxiliary class which contains our constraint encoded in a member function template. It is a function, so it can have and it make use of function parameters:

struct is_acceptable_c
{
  template <typename T>
  auto require(T x, int i) -> void_t</*...*/>;
};

I use name require instead of requires because I am thinking in terms of future C++, where requires is to be a reserved keyword. Now, we will make use of the fact that when function return type is declared with an arrow, we can access the names (and the types) of function’s input parameters. Thus, our constraints from above can be rewritten as:

struct is_acceptable_c
{
  template <typename T>
  auto require(T x, int i) -> void_t<
    typename T::result_type,
    decltype(T::set_limit(i)),
    decltype(x.get_result()),
    enable_if_t<noexcept(x.get_result())>,
    enable_if_t<
      is_same<decltype(x.get_result()),
              const typename T::result_type&
             >::value
    >
  >;
};

Note that in line 7 I am referring to variable x.

Now, this function has a declaration but no body. All the relevant parts are embedded in function declaration. It is correct to have it, as long it is not instantiated. For a given type X we would like to instantiate its declaration but not its body. You can do it by taking the address of this function template instantiation in an unevaluated context (such as decltype):

decltype(&is_acceptable_c::require<X>);

Now, implementing our type trait is not much different than the initial attempts:

template <typename T, typename = void>
struct is_acceptable
: false_type {};

template <typename T>
struct is_acceptable <T, void_t<
  decltype(&is_acceptable_c::require<T>)
>>
: true_type {};

This gives one additional benefit over previous solutions: the definition of a constraint is separated from the machinery of class template specializations. We could define one reusable template models like below, which abstracts away the definition of class templates and specializations.

We will be using it like this:

template <typename T>
using is_acceptable = models<is_acceptable_c, T>;

That is, you give us the definition of concept constraints (is_acceptable_c) and a set of concept parameters (in our case only T), and you get a predicate in return. The implementation follows; it consists of a primary class template, a specialization, and an alias:

template <typename /*_*/, typename C, typename... Args>
struct models_ : std::false_type {};

template <typename C, typename... Args>
struct models_<void_t<decltype(&C::template require<Args...>)>,
               C, Args...>
  : std::true_type {};

template <typename C, typename... Args>
  using models = models_<void, C, Args...>;

The master template takes the concept constraints class (C) and a list of types to test the concept against (remember that some concepts define a constraint on a number of types). The first argument is artificial. We only need it to fix it in the specialization. Because this time we are dealing with a parameter pack, we cannot put additional argument with default value at the end, therefore we put it in the front with no default.

The specialization, in the slot for the artificial parameter, instantiates the function declaration as before. Note the peculiar use of keyword template in line 5. The history is similar with that for typename C<...>::type. Without the additional keyword template compiler would have to assume that C::require refers to a static data member of C and the following character < is a less-than operator.

Finally, because we do not want the users to be aware of the additional first parameter we provide type alias models which hides the parameter.

And we could keep on improving the solution, but there is no reason for doing it ourselves, as we already have a good library exactly for this purpose.

Tick

Tick is a c++11 library for defining and making use of concept-like meta-predicates on types. With Tick, our predicate could be defined as follows:

#include <tick/builder.h>

TICK_TRAIT(is_acceptable)
{
  template<class T>
  auto require(T&& x) -> valid<
    typename T::result_type,
    decltype(T::set_limit(1)),
    is_true_c<noexcept(x.get_result())>,
    decltype(returns<const typename T::result_type&>(x.get_result()))
  >;
};

We can see that Tick applies a similar trick with member function template require and hides other machinery behind a clever macro TICK_TRAIT.

Unfortunately, in Tick’s require we are not allowed to add random function parameters. so rather than testing “for any i of type int” I am testing “for value 1”. But this can be worked around by by providing additional parameter int with default value.

Similarly, having to type typename T::result_type time and again is a bit tedious, and it makes the last constraint particularly long. We can introduce an alias in the template parameter list.

With these hacks applied, the definition of our type trait reads:

TICK_TRAIT(is_acceptable)
{
  template<class T, 
           class ResultT = typename T::result_type>
  auto require(T&& x, int i = 1) -> valid<
    typename T::result_type,
    decltype(T::set_limit(i)),
    decltype(x.get_result()),
    is_true_c<noexcept(x.get_result())>,
    decltype(returns<ResultT const&>(x.get_result()))
  >;
};

range-v3

Last, because Tick based its ideas on range-v3 library, I was curious how my type trait could be implemented in the latter library. Range-v3 is actually for working with STL containers, generators and algorithms through ranges (rather than iterators), but it uses its own implementation of concepts internally, so why not try it.

The scheme for defining constraints is similar: we specify them in return type of a member function template:

struct is_acceptable_r
{    
  template<class T, class U>
  auto requires_(T&& x, U&& y) 
    -> decltype(concepts::valid_expr(/*valid expressions*/));
};

Here, however, rather than providing a list of valid types, we provide a list of valid expressions. And while before we were converting expression constraints to types, here we will be sometimes converting type constraints to expressions. The full implementation of my type predicate is not as short as with previous techniques, and before I provide it, I need to define a yet another meta-programming tool:

template <bool C>
using bool_ = std::integral_constant<bool, C>;

This maps a Boolean type encoded as either true or false value of type bool, onto a Boolean value encoded as either std::true_type or std::false_type. Concept mechanism from ranges-v3 likes this C++ meta-programming way of encoding Boolean values. In C++17 we get this mapping function with the Standard Library: it is called std::bool_constant.

Here is the implementation of my trait:

#include <range/v3/utility/concepts.hpp>
namespace cc = ranges::concepts;

struct is_acceptable_r
{    
  template<class T,
           class ResultT = typename T::result_type>
  auto requires_(T&& x, int i) -> decltype(cc::valid_expr(
    cc::has_type<const ResultT&>(x.get_result()),
    ((void)T::set_limit(i), -1),
    cc::is_true( bool_<noexcept(x.get_result())>{} )
  ));
};

template <typename T>
using is_acceptable = bool_<(cc::models<is_acceptable_r, T>())>;

Some explanation. Line 9 says that expression x.get_result() is valid and that its return type is exactly const ResultT&.

Line 10 says that expression T::set_limit(i) is valid. But I couldn’t just type T::set_limit(i), because its return type is void, and it cannot be passed as argument to function valid_expr. So, I apply the trick with comma operator and type (T::set_limit(i), -1) and the return value of this expression is decltype(-1). Unless for some T function set_limit returns a strange type with overloaded comma operator, and then we have no clue what the return type is (and if it is not void again). So, in order to avoid this problem, we cast the left-hand side operand to void.

In line 11, a helper function from the library checks if a given expression is valid and evaluates to “true”, but by “true” it understands the object of type true_type (or at least something with static constant member data value of type bool). So, I need to map the result from operator noexcept using my meta-function bool_.

Finally, in line 16 I turn a class with constraints into a type predicate. This is a bit different from how rane-v3 defines concepts; but my goal is to define a C++-like type predicate, which can be used like this:

static_assert(is_acceptable<X>::value, "**");

It is my impression that the choice to list valid expressions (as in range-v3) rather than to list valid types (as in Tick) makes the definitions longer and more clumsy on average.

In fact, ranes-v3 library is installed in Wandbox, so we can test our example online.

And that’s it for today.

Acknowledgements

I am grateful to Paul Fultz II for helping me understand the details of Tick library.

For writing the range-v3 example, I used this post from Eric Niebler’s great blog.