[C++20] Concepts wrap up

Reference:
Oleksandr Koval - All C++20 core language features with examples
Andrzej - Requires-expression
Andrzej - Requires-Clause
Andrzej - Ordering by constraints

C++20 – My Favourite Code Examples - Nicolai Josuttis - ACCU 2022

Concept is also called placeholder types like 'using' or 'typedef'

Concepts

Named requirements, or concepts, are distilled from

• A set of related components (algorithms, containers, types)
• A set of common models

They create a simple way to match data types to components and know the result will work correctly

• For a specific component, requirements may be stronger than those required by the implementation
• Concept does not generate code; it's just a hint to compiler to check if the type is available.
• Do not introduce a concept for each member function (too fine grained)

The purpose is not to specify the implementation but to specify the meaning.

Requires expression

Rules

• requires-expression uses short-circuiting. Unlike naked template constexpr && conjunction which instantiate both left and right operands during compile time, requires-expression checks the constraints in the order in which they appear, and the moment the first non-satisfied constraint is detected, the checking of subsequent ones is abandoned.
  This trait is the foundation and purpose of using concept.
• Only the constraints in the body of the requires-expression have this property that invalid types and expressions are turned into a Boolean value. This trait can be used for checking if an expression is valid and provides early exit if one of the expression is invalid.

template<typename T>
requires (T x) // optional set of fictional parameter(s)
{
    // simple requirement: expression must be valid
    x++;    // expression must be valid

    // type requirement: `typename T`, T type must be a valid type
    typename T::value_type;
    typename S<T>;

    // compound requirement: {expression}[noexcept][-> Concept];
    // {expression} -> Concept<A1, A2, ...> is equivalent to
    // requires Concept<decltype((expression)), A1, A2, ...>
    {*x};  // dereference must be valid
    {*x} noexcept;  // dereference must be noexcept
    
    // dereference must  return T::value_type
    // https://en.cppreference.com/w/cpp/concepts/same_as
    {*x} noexcept -> std::same_as<typename T::value_type>;

    // nested requirement: requires ConceptName<...>;
    requires Addable<T>; // constraint Addable<T> must be satisfied
};

requires-expression can appear in places where compile time boolean type appears:

1. static_assert
2. if constexpr
3. template parameter
4. noexcept
5. explicit expression (since C++20)
6. etc.

template <typename T>
void clever_swap(T& a, T& b)
{
  constexpr bool has_member_swap = requires(T a, T b){
    a.swap(b);
  };

  if constexpr (has_member_swap) {
    a.swap(b);
  } else {
    using std::swap;
    swap(a, b);
  }
}


template <typename Iter>
struct S
{
  static_assert(requires(Iter i){ ++i; }, "no increment");
};

// -----
//identical
template <typename T, bool = requires{1;}>
struct S;

// same as:
template <typename T, bool = true>
struct S;

A requires-expression doesn’t have to appear inside any template; however, then its meaning is slightly different:
when any requirement is not satisfied, we get a compiler error rather than value false.
This could be used to test if a concrete class has a full interface implemented.
e.g.

#include "SuperIter.hpp"

constexpr bool _ = requires(SuperIter i) {
// stop compilation(hard error) if not satisfied since its not inside the template
  ++i;
};

Other usage:

requires(T v) {
  v.f();  // member function
  T::g(); // static member function
  h(v);   // free function
}

// if requires-expression need a variable; declare it at the signature
requires(T v, int i) {
  v.f(i);
}

Test if a callable return type is expected:

// need v.f(i) to return int
template <typename T>
int compute(T v)
{
  int i = v.f(0);
  i = v.f(i);
  return v.f(i);
}

requires(T v, int i) {
  { v.f(i) } -> std::convertible_to<int>;
}

requires(T v, int i) {
  { v.f(i) } -> std::same_as<int>; // exact int
}

Test function with noexcept:

requires(T v, int i) {
  { v.f(i) } noexcept -> std::same_as<int>;
}

Convertible:

requires(T v) {
  { v.mem } -> std::convertible_to<int>;
}

Nested type:

requires(Iter it) {
  typename Iter::value_type;
  { *it++ } -> std::same_as<typename Iter::value_type>;
}

requires inside requires means predicate:

requires(Iter it) {
  // 這個requires 是 requires clause; 不是 requires expression.
  // 故其後需為 predicate
  requires sizeof(it) <= sizeof(void*);
}

requires(Iter it) {
  *it++;
  // noexcept(*it++) act as predicate returns compile time boolean
  requires noexcept(*it++);
}

a requires-expression is a predicate itself, we can nest it:

requires(Iter it) {
  *it++;  // expression
  typename Iter::value_type;  // expression
  // double requires
  // second requrires is a predicate; boolean
  requires requires(typename Iter::value_type v) {
    *it = v;
    v = *it;
  };
}

// and this is WRONG:
requires (T v) {
  // Only test (typename T::value_type x) { ++x; }; is valid expression.
  requires (typename T::value_type x) { ++x; };
};

// CORRECT:
requires (T v) {
  // check if ++x is valid
  requires requires (typename T::value_type x) { ++x; };
};

Give a name to the set of constraints that we have created, so that it can be reused in different places in our program as a predicate, we have a couple of options.

1. Wrap it in a constexpr function:

template <typename Iter>
constexpr bool is_iterator()
{
  // inside a template, returns false if *it++ can't be done.
  return requires(Iter it) { *it++; };
}

// usage:
static_assert(is_iterator<int*>());

2. Initialize a variable template:

template <typename Iter>
constexpr bool is_iterator = requires(Iter it) { *it++; };

// usage:
static_assert(is_iterator<int*>);

3. Define a concept:

template <typename Iter>
concept iterator = requires(Iter it) { *it++; };

// usage:
static_assert(iterator<int*>);

4. Old school type trait:

template <typename Iter>
using is_iterator =
  std::bool_constant<requires(Iter it) { *it++; }>;

// usage:
static_assert(is_iterator<int*>::value);

However; this is WRONG and triggers hard compile error:

template <typename T>
constexpr bool value() { return T::value; }

template <typename T>
constexpr bool req = requires {
  // this predicate instantiation failed, hard error.
  requires value<T>();
};

// when instantiate value() its a HARD error while T has no ::value.
constexpr bool V = req<int>;

Correct way:

template <typename T>
constexpr bool req = requires {
  // rules 2.), exit early with False.
  T::value;
  requires value<T>();
};

constexpr bool V = req<int>;

Practical usages:

template <typename T>
  // T x, T y ; T&& x, T&& y; all works with same meaning
  requires requires (T& x, T& y) { x.swap(y); }
void swap(T& x, T& y)
{
  return x.swap(y);
}

Incorrect with hard error due to requires-expression not taking parameter as template type argument:

struct Machine {...};
struct Data{...};

// requires is not inside a template, 
// compile fail, hard error if m.monitor(std::move(d)) failed.
static_assert( !requires(Machine m, Data d) {
  m.monitor(std::move(d));
});

Fix it with putting requires-expression into template bracket:

template <typename M>
constexpr bool can_monitor_rvalue =
  requires(M m, Data d) { m.monitor(std::move(d)); };

static_assert(!can_monitor_rvalue<Machine>);

Concept

• A named set of such constraints or their logical combination.
• Both concept and requires-expression render to a compile-time bool value.
• A concept-id — that is, a concept with all its parameters filled in,
  like in Trivial<T> — is not an expression,
  it 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:
• Their instantiation can never fail.
  (But the instantiation of something that they alias could fail.)
• They cannot be specialized.

e.g.

template<typename T>
concept Addable = requires(T a, T b)
{
    a + b;
};

template<typename T>
concept Dividable = requires(T a, T b)
{
    a/b;
};

template<typename T>
concept DivAddable = Addable<T> && Dividable<T>;

template<typename T>
void f(T x)
{
    if constexpr(Addable<T>){ /*...*/ }
    else if constexpr(requires(T a, T b) { a + b; }){ /*...*/ }
}

Requires clause

• Actual constrain needs requires-clause.
• Appears at right after template<> block or as the last element of a function declaration, or even at both places at once, lambdas included.
• 後面接predicate

template<typename T>
requires Addable<T>
// Addable<T> && Subtractable<T>
auto f1(T a, T b) requires Subtractable<T>;

auto l = []<typename T> requires Addable<T>
    (T a, T b) requires Subtractable<T>{};

template<typename T>
requires Addable<T>
class C;

// infamous `requires requires`. First `requires` is requires-clause,
// second one is requires-expression. Useful if you don't want to introduce new
// concept.
template<typename T>
requires requires(T a, T b) {a + b;}
auto f4(T x);

// Or simply
template<Addable T>
void f();

• Template template parameters can be constrained.
• Template argument must be less or equally constrained than parameter.
• Unconstrained template template parameters can accept constrained templates as arguments.

template<typename T>
concept Integral = std::integral<T>;

template<typename T>
concept Integral4 = std::integral<T> && sizeof(T) == 4;

// requires-clause also works here
template<template<typename T1> requires Integral<T1> typename T>
void f2(){}

// f() and f2() forms are equal
template<template<Integral T1> typename T>
void f(){
    f2<T>();
}

// unconstrained template template parameter can accept constrained arguments
template<template<typename T1> typename T>
void f3(){}

template<typename T>
struct S1{};

template<Integral T>
struct S2{};

template<Integral4 T>
struct S3{};

void test(){
    f<S1>();    // OK
    f<S2>();    // OK
    // error, S3 is constrained by Integral4 which is more constrained than
    // f()'s Integral
    f<S3>();

    // all are OK
    f3<S1>();
    f3<S2>();
    f3<S3>();
}

Functions with unsatisfied constraints is undeclared and violating constraints is not a hard error its just not visible. Thus while not visible, if we call it and there's no other function overload, will cause hard error.

template<typename T>
struct X{
    void f() requires std::integral<T>
    {}
};

void f(){
    X<double> x;
    x.f(); // error
    auto pf = &X<double>::f; // error
}

Unlike partial specialized templates; if SFINAE match failed it'll fall back to primary template; requires clause substitute failed it'll simply disable the template function/class.

template <typename T>
  requires is_trivial_v<typename T::value_type>
void fun(T v);

template <typename T>
void fun(T v) { std::cout << "2"; }

int main()
{
  fun(1);  // displays: "2"
}

The predicate used in requires clause is well formed iff:

1. can be evaluated at compile-time
2. its type is exactly bool.
3. otherwise hard error.

Requires clause expression allows:

1. literals true and false;
2. names of variables of type bool of forms:
   value,
   value<T>,
   T::value,
   ns::trait<T>::value;
3. concept-ids, such as Concept<T>;
4. requires-expressions
5. Any other expression needs to be wrapped in parentheses.

e.g.

template <typename T>
  requires (!is_trivial_v<T>)
void fun(T v);

Both are valid:

template <typename T>
  // just be aware that typename T::value_type is a hard failure if T has no value_type type.
  requires !is_trivial_v<typename T::value_type>
void fun(T v);

also valid:

template <typename T>
concept value_type_valid_and_trivial
  = is_trivial_v<typename T::value_type>;

template <typename T>
  requires (!value_type_valid_and_trivial<T>)
void fun(T v);

||/&& disjunction/conjunction definition:
will continue/discontinue validate second template clause if first failed/failed.

1. constraint disjunction can only be introduced by token ||
2. constraint conjunction can be introduced in two ways:
1. either by token &&,
2. or by sticking the constraints in more than one place in a template declaration.

e.g.

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

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

constraint subsumption

http://eel.is/c++draft/temp.constr.order

// variadic form
// not a constraint disjunction;
// instead, we get a single atomic constraint with semantics
// "first check if all of this compiles and only
// then determine Boolean value".
// 也就是 Ts::value_type 若不存在則是 HARD ERROR!
// 只有 concept and requires expression 容許 expression error 並回傳'false'
template <typename... Ts>
  requires (is_trivial_v<typename Ts::value_type> || ...)
void fun(Ts... v);

// allow disjunction
template <typename T>
concept trivial_value_type
  = std::is_trivial_v<typename T::value_type>;

template <typename... Ts>
  // trivial_value_type 是 predicate囉!
  requires (trivial_value_type<Ts> || ...)
void fun(Ts... v);

Constrained auto

'auto parameters' for normal functions to make them generic which alike generic lambdas.
Concepts can be used to constrain placeholder types(auto/decltype(auto)) in various contexts.
For parameter packs, MyConcept... Ts requires MyConcept to be true for each element of the pack, not for the whole pack at once,

e.g. requires<T1> && requires<T2> && ... && requires<TLast>

template<typename T>
concept is_sortable = true;

auto l = [](auto x){};
void f1(auto x){}               // unconstrained template
void f2(is_sortable auto x){}   // constrained template

template<is_sortable auto NonTypeParameter, is_sortable TypeParameter>
is_sortable auto f3(is_sortable auto x, auto y)
{
    // notice that nothing is allowed between constraint name and `auto`
    is_sortable auto z = 0;
    return 0;
}

template<is_sortable auto... NonTypePack, is_sortable... TypePack>
void f4(TypePack... args){}

int f();

// takes two parameters
template<typename T1, typename T2>
concept C = true;
// binds second parameter
// means C<int, double>
C<double> auto v = f();

struct X{
    operator is_sortable auto() {
        return 0;
    }
};

auto f5() -> is_sortable decltype(auto){
    f4<1,2,3>(1,2,3);
    return new is_sortable auto(1);
}

Partial ordering by constraints

Reference:
https://akrzemi1.wordpress.com/2020/05/07/ordering-by-constraints/

atomic constraint

An atomic constraint is an expression (that can be evaluated at compile-time) of type bool that cannot be further decomposed.

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.
4. 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.
   This is helped by SSA (https://en.wikipedia.org/wiki/Static_single_assignment_form)

Take away:

1. 不要使用naked trait 因為 trait 在不同處即便definition相同name mangling仍為不同

2. 使用在一處的concept.

3. 避免 unordered concept constraints.

Verbose definition

1. Aside from specifying requirements for a single declaration, constraints can be used to select the best alternative for a normal function, template function or a class template.
2. Constraints have a notion of partial ordering:
1. one constraint can be at least or more constrained than the other
2. they can be unordered(unrelated)
3. Compiler normalization constraint into a conjunction/ disjunction of atomic constraints.
4. C1 && C2 is more constrained than C1; C1 is more constrained than C1 || C2; and any constraint is more constrained than the unconstrained declaration.
5. When more than one candidate with satisfied constraints are present, the most constrained one is chosen.
6. If constraints are unordered, the usage is ambiguous.

template<typename T>
concept integral_or_floating = std::integral<T> || std::floating_point<T>;

template<typename T>
concept integral_and_char = std::integral<T> && std::same_as<T, char>;

void f(std::integral auto){}        // #1
void f(integral_or_floating auto){} // #2
void f(std::same_as<char> auto){}   // #3

// calls #1 because std::integral is more constrained
// than integral_or_floating(#2)
f(int{});
// calls #2 because it's the only one whose constraint is satisfied
f(double{});
// error, #1, #2 and #3's constraints are satisfied but unordered
// because std::same_as<char> appears only in #3
f(char{});

void f(integral_and_char auto){}    // #4

// calls #4 because integral_and_char is more
// constrained than std::same_as<char>(#3) and std::integral(#1)
f(char{});

Compiler decomposition of concept

1. During decomposition, the concept name is replaced with its definition but requires-expression is not further decomposed.
2. Two atomic constraints are identical only if they are represented by the same expression at the same location.
   This is helped by SSA (https://en.wikipedia.org/wiki/Static_single_assignment_form)
   Indicates naked traits in different location has different name mangling.
   Thus we use single position 'concept' and used it in multiple places; which still they are all the same.
   trick:
   concept C = C1 && C2 is decomposed to conjunction of C1 and C2 while
   concept C = requires{...} becomes concept C = Expression-Location-Pair and its body is not further decomposed.
3. If two concepts have common or even the same requirements in their requires-expression, they will always be unordered due to their requires-expressions are 'not equal' or they are 'equal' but at 'different source locations.'
4. The same happens with duplicated usage of a naked type traits - they always represent different atomic constraints because of different locations, thus, cannot be used for ordering.

template<typename T>
requires std::is_integral_v<T>  // uses type traits instead of concepts
void f1(){}  // #1

template<typename T>
requires std::is_integral_v<T> || std::is_floating_point_v<T>
void f1(){}  // #2

// error, #1 and #2 have common `std::is_integral_v<T>` expression
// but at different locations(line 2 vs. line 6), thus, #1 and #2 constraints
// are unordered and the call is ambiguous
f1(int{});

template<typename T>
// requires-expression is not decomposed; and C1 is in single place
concept C1 = requires{
    requires std::integral<T>;
};

template<typename T>
// requires-expression is not decomposed; and C2 is in single place
concept C2 = requires{
    requires (std::integral<T> || std::floating_point<T>);
};

void f2(C1 auto){}  // #3
void f2(C2 auto){}  // #4

// error, since requires-expressions are not decomposed, #3 and #4 have
// completely unrelated and hence unordered constraints and the call is
// ambiguous
f2(int{});

More examples

template <typename T>
// Trivial is an atomic constraints and it's at single place and being used
// in multiple places.
concept Trivial = std::is_trivial_v<T>; 


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

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

// #1 and #2 's Trivial<T> are the same.

fun(1, 2); // choose second implementation.

// Or can be written as
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"; }

Naked trait example

template <typename T, typename U>
// #1 std::is_trivial_v<T> is an atomic constraints
  requires std::is_trivial_v<T>
void fun(T t, U u) { std::cout << "general"; }

template <typename T, typename U>
// #2 std::is_trivial_v<T> is an atomic constraints
  requires std::is_trivial_v<T> && std::is_trivial_v<U>
void fun(T t, U u) { std::cout << "special"; }

// #1 and #2 's std::is_trivial_v<T> are atomic
//constraints and they are not the same since they are in difference location.

// ambiguous; while #1 and #2 's std::is_trivial_v<T> are not the 'same'
fun(1, 2); 

i.e
std::is_trivial_v<T> is an expression of type bool.

Trivial<T> is an alias for an expression of type bool.

Short-circuiting in meta-functions

https://akrzemi1.wordpress.com/2019/12/23/short-circuiting-in-meta-functions/
https://akrzemi1.wordpress.com/2014/06/26/clever-overloading/
https://akrzemi1.wordpress.com/2017/12/02/your-own-type-predicate/
https://en.cppreference.com/w/cpp/types/conjunction

SFINAE does not work for errors resulting from template instantiation.
For lazy-evaluation in template, do not access type's data members(type, value etc.)
(which ask compiler to trigger type instantiation) until use.
std::conjunction is our friend
possible implementation:

template<class...> struct conjunction : std::true_type { };
template<class B1> struct conjunction<B1> : B1 { };
template<class B1, class... Bn>
struct conjunction<B1, Bn...>
    : std::conditional_t<bool(B1::value), conjunction<Bn...>, B1> {};

e.g.

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

For runtime lazy-evaluation:

// Wrong
bool eager_and(bool cond1, bool cond2)
{
  if (!cond1) return false;
  if (!cond2) return false;

  return true;
}

// 此處 ptr 與 ptr->is_ready() 都已經跑了...
return eager_and(ptr, ptr->is_ready());

// Correct
template <typename Pred1, typename Pred2>
bool lazy_and(Pred1 cond1, Pred2 cond2)
{
  if (!cond1()) return false;
  // cond2() 會跑只有 cond1() returns true.
  if (!cond2()) return false;

  return true;
}

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

In C++20, requires clause itself's conjunction logic is lazy evaluated.

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

Old trick for old dog

https://akrzemi1.wordpress.com/2014/06/26/clever-overloading/
tag dispatching and enable_if
e.g.

#include <type_traits>

template <typename U>
T value_or_(U const& v, std::true_type) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or_(F const& f, std::false_type) const
{
  if (*this)
    return this->value();
  else
    return f();
}

Better with C++20

template <typename U>
T value_or(U const& v) const
{
  return value_or_(v, std::is_convertible<U, T>{});
}

Use concept to fine grain an API to avoid ambiguous.

template<typename Coll>
concept HasPushBack = requires (Coll c, Coll::value_type v) {
    c.push_back(v);
};


void add(auto& coll, const auto& val) {
    if constexpr (requires {coll.push_back(val);}) {
        coll.push_back(val);
    } else {
        coll.insert(val);
    }
}