Ordering by constraints

Inthe previous post we have seen how constraint conjunction and disjunction works, and how a function template with constraints is a better match than a function template without constraints (provided that the constraints are satisfied) when determining the best overload. We have also mentioned that selecting a better match from two constrained templates is possible, but not obvious. In this post we will expand on this, and show how constraint conjunction and disjunction as well as concepts play an important role in ordering function overloads and class template specializations based solely on constraints. This is one of the situations where language concepts show their special properties.

The idea of selecting the most constrained of two (or more) constrained function templates came from the STL, where we can have two versions of algorithm std::advance : one that works on any kind of iterator (so it is already constrained by concept InputIterator , and another that works only for types that model RandomAccessIterator and provides a more efficient implementation. In C++89 this idea of a more specialized algorithm was achieved through techniques like tag dispatching. In C++17 we got if constexpr which often eliminates the need for providing overloads in cases where the set of known specializations is closed and known from the outset. For the remaining cases C++20 comes with a dedicated solution: ordering by template constraints.

The incarnation of the concepts that was planned for C++11 had a notion of concept refinement: concept RandomAccessIterator could explicitly declare that it is a refinement of concept BidirectionalIterator , and this way the compiler would know which overload to choose if one were constrained with RandomAccessIterator and the other with RandomAccessIterator . In contrast, C++20’s Concepts Lite have taken a different approach. Two constrained templated declarations can be partially ordered based on their constraints. For instance, given the following concept:

template <typename T>
concept Trivial = std::is_trivial_v<T>;

and the following two overloads:

template <typename T, typename U>
  requires Trivial<T>
void fun(T t, U u) { std::cout << "general"; }

template <typename T, typename U>
  requires Trivial<T> && Trivial<U>
void fun(T t, U u) { std::cout << "special"; }

If I try to call it with two trivial arguments:

fun(1, 2);

The second overload gets chosen because it is more constrained. Recall from the previous post that token && inside the requires -clause is not a logical-or operator: it is a constraint conjunction. A conjunction of constraint P with another constraint makes the declaration more constrained (like, more specialized) than a declaration with a single constraint P .

But if we substitute the type trait std::is_trivial_v for the concept in our two declarations:

template <typename T, typename U>
  requires std::is_trivial_v<T>
void fun(T t, U u) { std::cout << "general"; }

template <typename T, typename U>
  requires std::is_trivial_v<T> && std::is_trivial_v<U>
void fun(T t, U u) { std::cout << "special"; }

The same call:

fun(1, 2);

now becomes ambiguous and causes a compiler error. This looks surprising, and in order to explain this we have to understand when two sequences of characters in the source code represent the same constraint. Because this is the crux of the issue here: Trivial<T> in line 2 and Trivial<T> in line 6 in the former example represent the same constraint, whereas std::is_trivial_v<T> in line 2 and std::is_trivial_v<T> in line 6 in the latter example represent two different constraints, even though they render the same value.

This mechanism works as follows. The entire constraint associated with a given function is decomposed into conjuncitons and disjunctions of atomic constraints . An atomic constraint is an expression (that can be evaluated at compile-time) of type bool that cannot be further decomposed. Such decomposition works as follows:

1. P && Q is decomposed into constraint conjunction of P and Q .
2. P || Q is decomposed into constraint disjunction of P and Q .
3. The occurrence of the concept name with template arguments filled in, like in Trivial<T> , is replaced with the concept definition.

After this decomposition, two atomic constraints are considered identical if they are represented by the very same expression at the very same location in source code. Thus, going back to the example with type traits:

template <typename T, typename U>
  requires std::is_trivial_v<T>
void fun(T t, U u) { std::cout << "general"; }

template <typename T, typename U>
  requires std::is_trivial_v<T> && std::is_trivial_v<U>
void fun(T t, U u) { std::cout << "special"; }

The first overload has one atomic constraint P represented by expression std::is_trivial_v<T> in line 2. The second overload has two atomic constraints: the first constraint Q is represented by expression std::is_trivial_v<T> in line 6. While they are represented by the same sequence of characters, these expressions are defined at different locations — one at line 2, the other at line 6 — and only because of this they are considered different atomic constraints. So, the constraint of the first overload is P , the constraint of the second overload is Q ∧ R , with no relationship between the three atomic constraints. Therefore, we cannot determine which of the constraints is stricter.

Now, let’s analyze the example with concepts:

template <typename T>
concept Trivial = std::is_trivial_v<T>;

template <typename T, typename U>
  requires Trivial<T>
void fun(T t, U u) { std::cout << "general"; }

template <typename T, typename U>
  requires Trivial<T> && Trivial<U>
void fun(T t, U u) { std::cout << "special"; }

The first overload is constrained by a single concept. A concept-id (that is, concept plus arguments), like Trivial<T> , is not treated as an expression. In order to determine the atomic constraints, we have to look inside. Inside we find one atomic constraint P represented by expression std::is_trivial_v<T> in line 2. If we analyze the constraint of the second overload we get a constraint conjunction of two concept-ids. If we look inside the first, we get an atomic constraint Q represented by expression std::is_trivial_v<T> in line 2 . Thus, P and Q are represented by the same expression (sequence of characters) at the very same location (line 2) and therefore they are considered identical. So, the constraint of the first overload is P , the constraint of the second overload is P ∧ R . therefore we can conclude that the second constraint is more constraining.

The above illustrates the first special property of the concepts. A concept-id — that is, a concept with all its parameters filled in, like in Trivial<T> — is not an expression: is is an alias for an expression defined elsewhere: namely, in the concept definition. It is somewhat analogous to alias templates which are aliases on types. Both alias templates and concepts are templates that are never instantiated. This means that:

1. Their instantiation can never fail. (But the instantiation of something that they alias could fail.)
2. They cannot be specialized.

To reiterate, std::is_trivial_v<T> is an expression of type bool . Trivial<T> is an alias for an expression of type bool .

Now, let’s rewrite our two concept-constrained overloads using a shorter notation:

template <typename T>
concept Trivial = std::is_trivial_v<T>;

template <Trivial T, typename U>
void fun(T t, U u) { std::cout << "general"; }

template <Trivial T, Trivial U>
void fun(T t, U u) { std::cout << "special"; }

Now the concept appears inside angle brackets, and it is passed no arguments. Functionally, it is equivalent to the previous example; thus, a call to fun(1, 2) selects the second overload. The difference is only in notation. This illustrates two things. First, this is another special property of concepts: they can be used to introduce constraints to templates without a requires -clause .

Second, even though there is no token && in sight, we still have a constraint conjunction of two atomic constraints. So, while constraint disjunction can only be introduced by token || , constraint conjunction can be introduced in two ways: either by token && , or by sticking the constraints in more than one place in a template declaration. The following could also replace the second overload with the same effect:

template <Trivial T, typename U>
  requires Trivial<U>
void fun(T t, U u) { std::cout << "special"; }

In fact, we can use an even shorter notation for declaring templates constrained with concepts:

void fun(Trivial auto t, auto u) 
{ std::cout << "general"; }

void fun(Trivial auto t, Trivial auto u)
{ std::cout << "special"; }

This allows us to get rid of type names T and U . Using auto in function parameter list indicates that we are declaring a template. Additionally putting a concept name before the auto adds a constraint for the type of this parameter.

The subsumption relation

We have seen that P ∧ Q is more constraining than P . In a similar way P is more constraining than P ∨ Q . Now, as an exercise, we will take a look at the most general form of this relationship between constraints. The Standard, in order to define it, introduces the notion of constraint subsumption . The full definition can be found here . It is quoted below for convenience. We will subsequently illustrate it with an example.

To illustrate this mechanism, consider the following design of concepts for some hypothetical library for mathematical computations.

template <typename T>
concept Scalar = std::is_scalar_v<T>;

Concept Scalar represents all built-in types that have basic arithmetical operations such as addition, multiplication and similar. In addition to dealing with built-in types, this library allows the user to teach it to recognize user-defined “mathematical types”. In order to tell the library to recognize my type, say big_int , I have to specialize a template:

// provided by library:
template <typename T>
struct mathematical_traits
{
    constexpr static bool customized = false;
};

// customized by user:
template <>
struct mathematical_traits<big_int>
{
    constexpr static bool customized = true;
};

This customization is recognized by another concept in the library:

template <typename T>
concept CustomMath = mathematical_traits<T>::customized;

Finally, we have a concept (probably the most useful one) that recognizes any mathematical type: either a built-in or a user-defined one:

template <typename T>
concept Mathematical = Scalar<T> || CustomMath<T>;

Functions in the library use these concepts as constraints:

template <Mathematical T, Mathematical U>
void fun(T const&, U const&) { std::cout << "Q"; }

Function fun works for any two, potentially different, arithmetical types. However, a faster implementation can be provided if both types T and U represent a mathematical type in the same way, that is: they are either both scalar types, or they are both user-defined types customized using mathematical_traits . Declaration of this optimized overload reads:

template <typename T, typename U>
  requires (Scalar<T> && Scalar<U>) 
        || (CustomMath<T> && CustomMath<U>)
void fun(T const&, U const& ) { std::cout << "P"; }

Now, when user invokes function fun(1, 1) , and both overloads are viable candidates, the compiler has to determine if one of the overloads is more specialized by constraints than the other (and this one will get selected) or if we have an ambiguity. We will perform this process manually.

First we will determine if the constraint of the second overload (the one that displays “P”) subsumes the constraint of the first overload. We will call the constrain of the first overload Q and the constraint of the second overload P . For that we have to represent P in disjunctive form (an OR of ANDs), and Q in conjunctive form (an AND of ORs):

Now we have to show that all the following are true:

• P ₁ subsumes Q ₁ ,
• P ₂ subsumes Q ₁ ,
• P ₁ subsumes Q ₂ ,
• P ₂ subsumes Q ₂ .

Now, in order to show that P _i subsumes Q _j we have to indicate a conjunctive clause P _ia in P _i and a disjunctive clause Q _jb in Q _j such that P _ia is identical with Q _j . And indeed we have:

• for P ₁ and Q ₁ : Scalar<T> ,
• for P ₂ and Q ₁ : CustomMath<T> ,
• for P ₁ and Q ₂ : Scalar<U> ,
• for P ₂ and Q ₂ : CustomMath<U> .

Therefore, constraint P subsumes constraint Q . But in order to be sure there is no overload resolution ambiguity, we also have to show that Q does not subsume P . Let’s try to represent Q in disjunctive form, and P in conjunctive form. It is possible but longer, and in case of P hardly intuitive:

Here, we can show pairs of Q _i and P _j that do not have a common atomic constraint: for instance Q ₂ and P ₂ . Therefore Q does not subsume P . So, subsumption in our case only works one way, which means that the overload which displays “P” is a better match, and gets selected.

This also illustrates how many computations a compiler has to do during overload resolution (or matching class template partial specializations) when we put too complicated constraints involving conjunctions and disjunctions. Conjuncitons are generally unavoidable: we have seen how easily they get created even if we do not put token && anywhere. Therefore, it is advisable to avoid constraint disjunctions if possible in order not to increase compile times.

Inplementation of std::same_as

For the end, given what we have seen, let’s try to explain why concept std::same_as is defined in the following funny way:

namespace std 
{
  template <typename X, typename Y>
  concept __same_as = is_same_v<X, Y>;

  template <typename X, typename Y>
  concept same_as = __same_as<X, Y> && __same_as<Y, X>;
}

That is, name __same_as is an internal detail, and in reality, it can be different. However, the existence of the intermediate concept and the usage of conjunction is guaranteed by the C++ Standard. One might ask if the following definition would not be sufficient, given that type trait std::is_same_v is symmetric:

template <typename X, typename Y>
concept Same = std::is_same_v<X, Y>;

To understand why it is not sufficient, consider the following two function template overloads that need to use our concept:

template <typename T>
using value_type = typename T::value_type;

template <typename T, typename U>
  requires Same<value_type<T>, value_type<U>> 
void fun(T&, U&) {}

template <typename T, typename U>
  requires Same<value_type<U>, value_type<T>> 
        && std::regular<value_type<U>>
void fun(T&, U&) {}

They both require that T and U have a nested type value_type and that the both typedefs name the same type. The second overload additionally requires that this type is regular (copyable and equality-comparable). Not necessarily because the implementation can be faster, but perhaps because it can apply additional safety checks, like copying the value at the beginning and comparing it at the end. The order of T and U is different in the second overload inside Same , but we expect the concept to be symmetric, don’t we?

But if we call this overloaded function like this:

std::optional<int> oi;
fun(oi, oi);

We get an ambiguous result from overload resolution, because after normalization, the constraint of the first overload is:

std::is_same_v<value_type<T>, value_type<U>>

and the constraint of the second is:

std::is_same_v<value_type<U>, value_type<T>> ∧ …

This is a different atomic expression, so one constraint will never subsume the other. Also, the following definition will not do:

template <typename X, typename Y>
concept Same = std::is_same_v<X, Y> && std::is_same_v<Y, X>;

Because the two constraints after substitution and normalization are:

std::is_same_v<value_type<T>, value_type<U>> ∧

std::is_same_v<value_type<U>, value_type<T>>

and

std::is_same_v<value_type<U>, value_type<T>> ∧

std::is_same_v<value_type<T>, value_type<U>>

∧ …

They look the same token-wise, but are generated from different locations (even though the two locations appear in the same line: but on the different side of token && ). Only when we implement Same using an intermediate concept:

template <typename X, typename Y>
concept Same_ = std::is_same_v<X, Y>;

template <typename X, typename Y>
concept Same = Same_<X, Y> && Same_<Y, X>;

do we get normalized constraints

std::is_same_v<value_type<T>, value_type<U>> ∧

std::is_same_v<value_type<U>, value_type<T>>

and

std::is_same_v<value_type<U>, value_type<T>> ∧

std::is_same_v<value_type<T>, value_type<U>>

∧ …

But now all atomic expressions come from the very same location, and this will qualify for subsumption.

One other observation that we will make, but not delve into, is that another implementation of concept Same is possible, using a requires -expression :

template <typename X, typename Y>
concept Same_ = std::is_same_v<X, Y>;

template <typename X, typename Y>
concept Same = requires {
    requires Same_<X, Y>;
    requires Same_<Y, X>;
};

But it will also cause our overload resolution to fail, because the entire requires -expression is treated as a single atomic constraint.

And that’s it for today. It all may seem complicated, but this is because I focused on the most complicated aspects. Using concepts in practice is much simpler.