Concept archetypes

Concepts in the form added in C++20 used to be called lite. This is because they do not provide one quite important functionality: having the compiler check if the author of a constrained template is only using operations and types allowed by the constraining concept. In other words, we can say that our template only requires operations A and B to be valid, but we can still use some other operations inside and this is fine with the compiler. In this post we will show how this is problematic, even for programmers aware of the issue, and how to address it with concept archetypes.

(Note: I have edited this post since it was originally published based on the feedback from the readers. The changes are indicated with the blueish color.)

This example is a bit artificial, but we have to make it small. We will use function sum() as an example of a generic algorithm. It implements the addition of two values, provided that they are addable:

template <Addable T>
T sum(T a, T b);

We require that our Ts are regular and provide operators + and +=:

template <typename T>
concept Addable = 
  std::regular<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
  }; 

With these constraints satisfied we can provide various implementations of addition. For instance this one:

template <typename T>
T sum_impl(T a, T b)
{
  assert (a >= b);
  a += b;
  return a;
}

template <Addable T>
T sum(T a, T b)
{
  if (b > a) 
    return sum_impl(b, a);
  else
    return sum_impl(a, b);
}

Let’s pretend that we have discovered that the most efficient implementation is when we use += rather than + and when the bigger number is on the left-hand side. The point is, when we have provided the interface, in form of a concept, it is our business how we want to implement the function, as long as we satisfy the contract. Another minor observation is that we can call an unconstrained template form a constrained template, and this is fine.

Now suppose we are implementing a generic library that other people are going to use. A function template is not a piece of code that can be executed. It will only become one when instantiated with user provided types. The fact that the template definition compiles does not mean that the body is correct: most of errors from templates show up when we try to instantiate them. So, in order to ship a decent library, we have to test if our template can be instantiated for addable types:

int main()
{
  int i = 1, j = 2;
  std::cout << sum(i, j) << std::endl;

  double x = 2.25, y = 5.25;
  std::cout << sum(x, y) << std::endl;
}

This compiles, runs and outputs:

3
7.5

So, the implementation works. But these are very basic types. What if the users will use their custom addable types with our function? This also needs to be tested. Let’s use Boost.Rational library:

#include <boost/rational.hpp>

// verify if the type can be used with the library
static_assert(Addable<boost::rational<int>>);

int main()
{
  boost::rational<int> q1{1, 2}; // 1/2
  boost::rational<int> q2{1, 3}; // 1/3
  std::cout << sum(q1, q2) << std::endl;
  std::cout << sum(q2, q1) << std::endl;
}

This outputs:

5/6
5/6

So it works! We can also check with Boost’s big int library:

#include <boost/multiprecision/cpp_int.hpp> 

static_assert(Addable<boost::multiprecision::cpp_int>);

int main()
{
  boost::multiprecision::cpp_int i{"770000"}, 
                                 j{"119999"};
  std::cout << sum(i, j);
}

Works and outputs:

889999

Now we can confidently ship our library to the customers.

Our customer intends to use the library with the standard library type: std::complex. As the first step, she verifies if her type satisfies our concept:

#include <complex> 
#include "addable_library.hpp"

static_assert(Addable<std::complex<double>>);

This compiles fine, so std::complex<double> does model Addable. Now, she can correctly use the library:

int main()
{
  std::complex<double> z1{1, 0}, z2{0, 1};
  std::cout << sum(z1, z2);
}

And this program fails to compile. We get an old-style template error message, exposing the internal implementation of code of our library function, which uses operator>. And std::complex<double> does not provide operator > or >=.

Now it turns out our implementation uses operations that we did not list in the concept. But because types that are Addable and don’t provide relational operations are so infrequent, this bug could have gone unnoticed for a long while. It is not easy to spot this even in a short, simple function. And the compiler doesn’t try to help us. (As a side note, there are good reasons why compilers had better not do it.)

In order to avoid this situation, we have to check ourselves if in the implementation of a template we are only using the interface that we require in the concept. In order to do this, we have to define an archetype for our concept; that is, a type that only provides the interface indicated in the concept and not a single operation more.

Let’s try to define one for our concept:

template <typename T>
concept Addable = 
  std::regular<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
  }; 

We start with an empty class:

class A {};

But it is not really empty: its interface already provides constructors (default, copy, move), assignments (copy, move), destructor, and a couple of others, like operator& and operator,. In order for our type to really be empty we would have to declare these operations as deleted. But because our concept already requires the aforementioned constructors, assignment and destructor to exist, we will not delete them. More, in order to be explicit about our intentions we will mark them as defaulted:

class A
{
public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;
};

This type already satisfies concept std::semiregular, which is part of std::regular, which in turn is part of our concept Addable. It doesn’t do anything useful, but it is fine: its goal is only to satisfy the concept. We can test it:

static_assert(std::semiregular<A>);

Now, in order to satisfy std::regular, our type needs to provide equality and inequality operators. In C++20 we can do it with one declaration:

class A
{
public:
  // ...
  friend bool operator==(A const&, A const&) = default;
};

// test it:
static_assert(std::regular<A>);

Now, our two addition operators. We could do it like this:

class A
{
public:
  A& operator+=(A const&) { return *this; }
  friend A operator+(A const&, A const&) { return {}; }
  
  // ...
};

But that would not be the minimum satisfaction of our concept. Recall:

template <typename T>
concept Addable = 
  std::regular<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
  }; 

The requirement for operator+ is that its result be convertible to T but not necessarily T. If we miss that, we are risking the same problem as we observed with operator>: an algorithm constrained by Addable may rely on the result of addition being exactly T. Most of the types satisfy it, so it would go unnoticed, but a library user may later be using a type where the result of addition is not T, but something convertible to it. So, we have to take this into account. A minimal implementation could look like this:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  // ...
};

The full class definition:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;

  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  friend bool operator==(A const&, A const&) = default;
};

We can now give it a better name and test if the archetype actually satisfies the concept:

using AddableArchetype = A;
static_assert(Addable<AddableArchetype>);

Now we have proved that our archetype models the concept, and we are convinced (although this cannot be statically proven) that it is a minimum interface that models the concept. In other words, now we are convinced we have an archetype. But is it really the the minimum interface that models the concept? See the next post to find out.

As a next step, we can use it to test the implementation of our algorithm. We simply define a non-template function that instantiates the algorithm sum with our archetype:

inline void test_concept_usage(AddableArchetype a,
                               AddableArchetype b)
{
  sum(a, b);
}

This function is never called; parameters a and b are never initialized. Only the existence of the function body is enough to guarantee that the entire implementation of sum is instantiated and therewith tested for using only the declared operations.

And it is tested. The program fails to compile. The error message is an old-style one, exposing the implementation details: type AddableArchetype does not provide operator> or operator>=. This is the same error that we have seen before. But this time it is the library author that sees the error before the library is shipped, rather than the library user when it is too late. Our test has discovered a bug. The bug is either in the implementation of function sum(), or in concept Addable — it is not clear yet. But because we are warned ahead of time, we can make a conscious choice.

We have a couple of options. First, we can decide that the implementation of our algorithm went too far. Such implementation is illegal and has to be changed so that it only uses operations required by the concept. Second, we can draw an opposite conclusion: the experience from implementing the algorithm the way we did shows that our initial idea about what the concept should require was incorrect, and it now has to be refined. The decision to modify a concept does not come easily, but may be necessary when we have learned something new about our domain while implementing algorithms. Finally, it is possible to provide two overloads of sum(): one that requires less of its arguments, and the other that offers optimizations:

template <Addable T>
T sum(T a, T b);
 
template <Addable T>
  requires std::totally_ordered<T>
T sum(T a, T b);

Suppose we make the call: concept Addable will also require the type to provide relational operators; this will make it close to the algebraic structure ordered group. (This is not necessarily the best decision, but I want to illustrate how the process of altering a concept works.) We have to change the definition of the concept:

template <typename T>
concept Addable = 
  std::regular<T> &&
  std::totally_ordered<T> &&
  requires(T x, T y) {
    { x += y } -> std::same_as<T&>;
    { x +  y } -> std::convertible_to<T>;
  }; 

Now our archetype no longer models the concept. The static check that we added will remind us of this:

static_assert(Addable<AddableArchetype>);
//            ^--- this now fails

We can fix our archetype by replacing the defaulted equality operator with defaulted spaceship operator:

class A
{
  struct Rslt { 
    operator A() { return {}; } 
  };

public:
  A() = default;
  A(A&&) = default;
  A(A const&) = default;
  A& operator=(A &&) = default;
  A& operator=(A const&) = default;
  ~A() = default;
    
  void operator&() const = delete;
  friend void operator,(A const&, A const&) = delete;

  A& operator+=(A const&) { return *this; }
  friend Rslt operator+(A const&, A const&) { return {}; }
  
  friend auto operator<=>(A const&, A const&) = default;
};

Now the archetype models the updated concept again, and the static test test_concept_usage passes which gives us the confidence that our algorithm uses only operations defined in the concept. Users of the library will still not be able to use it with std::complex<double>, but this time, they will get a clear message up front: your type does not model concept Addable.

And that’s it. For a final note, in this example we have seen an archetype with trivial implementation. It is possible to make the archetype actually do something useful, like counting the number of invocations of individual functions from the interface, or throwing exceptions from functions for the purpose of testing exception safety.