Short-circuiting in meta-functions

Short-circuiting in logical operations is a very useful and an often used feature:

if (cond_a() && cond_b())

Should cond_a() evaluate to false, cond_b() is guaranteed not to be evaluated. This is useful for two reasons. One is performance: if cond_b() is an expensive operation we do not want to evaluate it if we can determine the final result from only evaluating cond_a(). The other reason is program correctness:

if (ptr && ptr->is_ready())

Here the first operand is a precondition for the second operand, and we do not want the latter to be evaluated if the former isn’t true. Short-circuiting makes this work as desired.

For similar reasons, we might want to use short-circuiting of logical operations in meta-functions. However, in meta-functions this looks and works differently. This is what this post is about.

[Note: In this post we assume that the reader is familiar with meta-programming techniques described in this post.]

By a meta-function we mean a function that maps a type on a type, or a type on a value, or a value on a type. e.g., type trait std::is_trivial is a meta-function that takes a type as input and returns a value of type bool as output (when “called” like this: std::is_trivial<T>::value).

Why do we want short-circuiting in meta-functions? First, for faster compilation times. To illustrate this, let’s define a meta-function — as described in this post — for determining if a given class T has a nested type T::alternate_type:

// primary class template
template <typename T, typename /*unused*/ = void>
struct has_alternate 
: std::false_type
{
  // this version is selected when the following one
  // doesn't match
};

// class template partial specialization
template <typename T>
struct has_alternate<T, 
  std::void_t<typename T::alternate_type>>
: std::true_type
{
  // this version is selected if construct
  // typename T::alternate_type is a well-formed type 
};

It can be used like this:

struct A
{
  using alternate_type = int;
};

static_assert(has_alternate<A>::value);
static_assert(!has_alternate<int>::value);

While has_alternate is a meta-function, has_alternate<T>::value is a meta-function call. In order to determine the value of this “call”, class template has_alternate has to be instantiated. Class template instantiation is an expensive operation for the compiler, which may cause the compilation time to increase. So, if we have a composed condition, like:

if constexpr(std::is_trivial<C>::value &&
             std::is_trivial<D>::value &&
             has_alternate<C>::value  &&
             has_alternate<D>::value)

and the first operand is determined to be false, we would like to avoid futile instantiations of has_alternate. But in case of meta-functions the desired short-circuiting doesn’t work this way for operator &&: all class templates are instantiated first, if not for anything else then for the sole purpose of determining if the nested ::value is a valid construct naming a value, and of type that is convertible to bool.

The other reason for short-circuiting is to avoid breaking the compilation. To illustrate it, let’s consider the following example. We have a wrapper type that only works for trivial types and for some — but not all — it satisfies the constraint has_alternate that we defined above:

template <typename T> 
struct wrapper
{
  static_assert(std::is_trivial<T>::value);
    
  // may be present for some Ts:
  using alternate_type = 
    std::aligned_storage_t<sizeof(T), alignof(T)>;
};

In order to detect incorrect usages of this wrapper early, we have put a static_assert to inform the programmer about the bug at compile time. Now, we have a function template fun() that works for any type T:

template <typename T>
void fun(T const& v, void* /*unused*/) 
{
  /* ... */
}

The first argument represents a meaningful value. The second is never read, but is used as part of the trick to order the overloads. We will always be passing literal 0 as the the second argument. It will bind to type void* but will always be a worse match than the overloads of fun() that have int as the second parameter. This is a form of type dispatching as described in this post.

Now, we want to provide a better overload for those Ts where wrapper<T> works and has the nested type wrapper<T>::alternate_type. We could try to specify it like this:

template <typename T> 
  std::enable_if_t<
    std::is_trivial<T>::value &&
    has_alternate<wrapper<T>>::value
  >
fun(T const& v, int /*unused*/)
{
   /* ... */
}

The condition in enable_if_t is a conjunction (logical and) with two operands. The first one is a precondition for the second: we know that instantiating
has_alternate with a type that is not trivial would be a bug. But again, because operator && doesn’t do short-circuiting on meta-functions, this solution will not work. Trying to call:

std::string s;
fun(s, 0);

Will end up in causing the compile-time error rather than selecting the unconstrained overload. This is because both constructs, std::is_trivial<T>::value and has_alternate<wrapper<T>>::value, have to be materialized for their well-formedness to be determined; and in order to do this, template has_alternate has to be instantiated, and in the process of instantiation the static assertion will cause the compilation error. SFINAE does not work for errors resulting from template instantiation, as described in this post.

std::conjunction

The Standard Library provides a solution for applying logical conjunction for meta-functions with the short-circuiting property in the form of another meta-function called std::conjunction. First we will demonstrate the working solution and then we will describe how it works:

template <typename T> 
std::enable_if_t<
  std::conjunction<
    std::is_trivial<T>, 
    has_alternate<wrapper<T>>
  >::value
>
fun(T const& v, int /*unused*/)
{
   /* ... */
}

Note that the two arguments passed to std::conjunction are not Boolean values. What we pass is not std::is_trivial<T>::value but std::is_trivial<T>. We are passing the type trait that we will be using and the type we will be inspecting, but we are not inspecting it just yet. Construct std::is_trivial<T> names the class template instantiation, but does not actually perform the instantiation: it is just a name. The instantiations are performed only later, and only as needed when evaluating std::conjunction by typing ::value at the end. In other words, std::conjunction performs a lazy evaluation of its parameters. It is analogous to the concept of run-time lazy evaluation. Let me explain. Suppose we were to implement a function for computing a logical and operation (because for some reason we are not satisfied with operator &&). A C++ function call mechanism doesn’t have lazy evaluation by default, so the following will not work as desired:

bool eager_and(bool cond1, bool cond2)
{
  if (!cond1) return false;
  if (!cond2) return false;
  
  return true;
}

return eager_and(ptr, ptr->is_ready());

But we can provide a lazily evaluated version that takes lambdas rather than values as operands:

template <typename Pred1, typename Pred2>
bool lazy_and(Pred1 cond1, Pred2 cond2)
{
  if (!cond1()) return false;
  if (!cond2()) return false;
  
  return true;
}

return lazy_and([&]{ return bool(ptr); },
                [&]{ return ptr->is_ready(); });

What happens here is that we pass the operations as well as their arguments to the function, but we are not evaluating them. It is only the function that will evaluate them if they are needed.

An analogous thing happens inside std::conjunction, but at compile time and using template mechanism. Its implementation gets 0 or more class names of the form trait_N<T>, like:

conjunction<trait_1<T>, trait_2<T>, trait_3<T>>::value

It first instantiates class trait_1<T> by accessing value trait_1<T>::value. If this value is false this becomes the the final result of conjunction and other classes are not instantiated. If trait_1<T>::value evaluates to true, then the next trait needs to be inspected in a similar way, and the process is repeated. The whole implementation of std::conjunction could look like this:

// conditional_t<Cond, A, B> is a type derived from 
// A when condition Cond is true, and a type derived
// from B when condition Cond is false

template <bool Cond, typename OnTrue, typename OnFalse>
struct conditional_t : OnFalse {};

template <typename OnTrue, typename OnFalse>
struct conditional_t<true, OnTrue, OnFalse> : OnTrue
{};


// conjunction<...>::value is true unless
// any of the operands is false

template<typename... Conds>
struct conjunction : std::true_type {};

// conjunction<Cond1>::value is equivalent
// to Cond1::value

template<typename Cond1>
struct conjunction<Cond1> : Cond1 {};

// Recursive check ...

template<class C1, class... Cs>
struct conjunction<C1, Cs...> 
  : conditional_t<bool(C1::value),
                  conjunction<Cs...>, 
                  C1
                 > {};

We can also use std::conjunction to solve our other problem, with if constexpr:

if constexpr(std::conjunction<std::is_trivial<C>,
                              std::is_trivial<D>,
                              has_alternate<C>,
                              has_alternate<D>>::value)

The Standard Library has also lazy meta-functions disjunction, negation, and conditional_t which works similar to the one we defined above.

The future

In C++20 things like the one we are discussing in this post will become much simpler. First, when we use requires clauses the conjunction that they provide is already lazy:

template <typename T> 
requires std::is_trivial<T>::value 
      && has_alternate<wrapper<T>>::value
void fun(T const& v)
{
   /* ... */
}

Even though it is still spelled &&, it is no longer a normal logical operator: it is lazy with regard to compile-time predicates, and additionally treats each operand as an “atomic constraint” when comparing two constrained templates in order to check which is more specialized. Second, we no longer need the trick with the second function argument. Concepts naturally provide an ordering on function overloads, so that if we have two overloads and both match, then the one which is more constrained gets selected.