Does Constraint Subsumption Only Apply to Concepts

Does constraint subsumption only apply to concepts?

Yes. Only concepts can be subsumed. The call to foo<int> is ambiguous because neither of the declarations is "at least as constrained as" the other.

If, however, C1 and C2 were both concepts instead of inline constexpr bools, then the declaration of the foo() that returns 0 would be at least as constrained as the declaration of the foo() that returns 1, and the call to foo<int> would be valid and return 0. This is one reason to prefer to use concepts as constraints over arbitrary boolean constant expressions.

Background

The reason for this difference (concepts subsume, arbitrary expressions do not) is best expressed in Semantic constraint matching for concepts, which is worth reading in full (I will not reproduce all the arguments here). But taking an example from the paper:

namespace X {
 template<C1 T> void foo(T);
 template<typename T> concept Fooable = requires (T t) { foo(t); };
}
namespace Y {
 template<C2 T> void foo(T);
 template<typename T> concept Fooable = requires (T t) { foo(t); };
}
X::Fooable is equivalent to Y::Fooable despite them meaning completely different things (by virtue of being defined in different namespace). This kind of incidental equivalence is problematic: an overload set with functions constrained by these two concepts would be ambiguous.

That problem is exacerbated when one concept incidentally refines the others.
namespace Z {
 template<C3 T> void foo(T);
 template<C3 T> void bar(T);
 template<typename T> concept Fooable = requires (T t) {
 foo(t);
 bar(t);
 };
}
An overload set containing distinct viable candidates constrained by X::Fooable, Y::Fooable, and Z::Fooable respectively will always select the candidate constrained by Z::Fooable. This is almost certainly not what a programmer wants.

Standard References

The subsumption rule is in [temp.constr.order]/1.2:

an atomic constraint A subsumes another atomic constraint B if and only if the A and B are identical using the rules described in [temp.constr.atomic].

Atomic constraints are defined in [temp.constr.atomic]:

An atomic constraint is formed from an expression E and a mapping from the template parameters that appear within E to template arguments involving the template parameters of the constrained entity, called the parameter mapping ([temp.constr.decl]). [ Note: Atomic constraints are formed by constraint normalization. E is never a logical AND expression nor a logical OR expression. — end note ]

Two atomic constraints are identical if they are formed from the same expression and the targets of the parameter mappings are equivalent according to the rules for expressions described in [temp.over.link].

The key here is that atomic constraints are formed. This is the key point right here. In [temp.constr.normal]:

The normal form of an expression E is a constraint that is defined as follows:

The normal form of an expression ( E ) is the normal form of E.

The normal form of an expression E1 || E2 is the disjunction of the normal forms of E1 and E2.

The normal form of an expression E1 && E2 is the conjunction of the normal forms of E1 and E2.

The normal form of an id-expression of the form C<A₁, A₂, ..., A_n>, where C names a concept, is the normal form of the constraint-expression of C, after substituting A₁, A₂, ..., A_n for C's respective template parameters in the parameter mappings in each atomic constraint. If any such substitution results in an invalid type or expression, the program is ill-formed; no diagnostic is required. [ ... ]

The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

For the first overload of foo, the constraint is C1<T> && C2<T>, so to normalize it, we get the conjunction of the normal forms of C1<T>₁ and C2<T>₁ and then we're done. Likewise, for the second overload of foo, the constraint is C1<T>₂ which is its own normal form.

The rule for what makes atomic constraints identical is that they must be formed from the same expression (the source-level construct). While both functions hvae an atomic constraint which uses the token sequence C1<T>, those are not the same literal expression in the source code.

Hence the subscripts indicating that these are, in fact, not the same atomic constraint. C1<T>₁ is not identical to C1<T>₂. The rule is not token equivalence! So the first foo's C1<T> does not subsume the second foo's C1<T>, and vice versa.

Hence, ambiguous.

On the other hand, if we had:

template <typename T> concept D1 = true;    
template <typename T> concept D2 = true;

template <typename T> requires D1<T> && D2<T> 
constexpr int quux() { return 0; }

template <typename T> requires D1<T> 
constexpr int quux() { return 1; }

The constraint for the first function is D1<T> && D2<T>. The 3rd bullet gives us the conjunction of D1<T> and D2<T>. The 4th bullet then leads us to substitute into the concepts themselves, so the first one normalizes into true₁ and the second into true₂. Again, the subscripts indicate which true is being referred to.

The constraint for the second function is D1<T>, which normalizes (4th bullet) into true₁.

And now, true₁ is indeed the same expression as true₁, so these constraints are considered identical. As a result, D1<T> && D2<T> subsumes D1<T>, and quux<int>() is an unambiguous call that returns 0.

Understanding what atomic constraints are

I don't understand why an atomic constraint needs to involve an assignment. Why is so?

Emphasis mine.

It doesn't need to involve an assignment. It's just that expression is the top-level grammar term for expressions, that encompasses all the other kinds of expressions. sizeof(T) > 1 is an expression, as is sizeof(T) >= 4, as is sizeof(T) > 1 && sizeof(T) >= 4.

What this grammar definition means is that an expression is either an assignment-expression or another expression , assignment-expression. The grammar is hierarchically arranged based on what we consider to be operator precedence:

, has the lowest precedence, so the grammar pulls that one out first. That's what happens when we define expression recurisvely as expression , assignment-expression
= has the next lowest precedence, so we pull that one out next.
And then the grammar for assignment-expression takes us to logical-or-expression (next lowest precedence)
And then logical-and-expression, etc.

An assignment-expression need not actually involve an assignment. It's actually any kind of arbitrarily complex expression. All we know about it is that it definitely does not involve a , because we already pulled that one out.

Separately from all of that, the intent is that two atomic constraints are the same if they are literally the same expression in a source file. That is, constraint subsumption only applies to concepts.

Concept subsumption working for functions, but not for structs

Overloading template classes wasn't allowed before concepts, and it still not allowed even with concepts. Use partial specialization:

template <typename T>
requires eight<T>
struct ffs {};

template <typename T>
requires basic<T>
struct ffs<T> {};

Or with the terse syntax:

template <eight T>
struct ffs {};

template <basic T>
struct ffs<T> {};

Note that in both cases, the constraints on the primary template automatically apply to all specializations.

Why can't we specialize concepts?

Because it would ruin constraint normalization and subsumption rules.

As it stands now, every concept has exactly and only one definition. As such, the relationships between concepts are known and fixed. Consider the following:

template<typename T>
concept A = atomic_constraint_a<T>;

template<typename T>
concept B = atomic_constraint_a<T> && atomic_constraint_b<T>;

By C++20's current rules, B subsumes A. This is because, after constraint normalization, B includes all of the atomic constraints of A.

If we allow specialization of concepts, then the relationship between B and A now depends on the arguments supplied to those concepts. B<T> might subsume A<T> for some Ts but not other Ts.

But that's not how we use concepts. If I'm trying to write a template that is "more constrained" than another template, the only way to do that is to use a known, well-defined set of concepts. And those definitions cannot depend on the parameters to those concepts.

The compiler ought to be able to compute whether one constrained template is more constrained than another without having any template arguments at all. This is important, as having one template be "more constrained" than another is a key feature of using concepts and constraints.

Ironically, allowing specialization for concepts would break (constrained) specialization for other templates. Or at the very least, it'd make it really hard to implement.

Disjunctions in a Concept requirement

Concepts are decomposed in conjunction and disjunction of atomic-constraints through a process called constraint normalization described in temp.constr.normal.

Only:

logical and &&,
logical or ||,
parenthesized expression ()
and id-expression of the form C<A1, A2, ..., An>, where C names a concept

are decomposed. All other expressions are atomic constraints.

So a require-expression is, as a whole, an atomic constraint. In the concept TS, require-expression were decomposed but in C++20 they are not._{As far as I remember, I just read all the papers of the c++ committee related to concepts, the reason was that require-expression normalization may cause a complexity explosion that could penalize compilation speed.}

So:

requires(T a, T b) { 
    requires requires(T a, T b){a.foo(b)} 
          || requires(T a, T b){a.bar(b)}; // Req 1
    { a.baz() }; // Req 2
    // and onward
};

is an atomic-constraint. And

  requires(T a, T b) { 
    {a.foo(b)} 
    { a.baz() }; // Req 2
     // and onward
    }
|| requires(T a, T b) { 
     {a.bar(b)} 
     { a.baz() }; // Req 2
      // and onward
     };

is the disjunction of two atomic constraint. (the two requires-expression)

And finaly:

     ( requires(T a, T b) { a.foo(b); } || requires (T a, T b) { a.bar(b); } )
  && requires(T a, T b) { a.baz(); /* and onward */};

is the conjunction of a disjunction with an atomic constraint.

C++20: Concepts of multiple types and its constraint, correct syntax?

You can write it like this:

template <typename T1, typename T2>
    requires AreEqComparable<T1, T2>
bool are_equal(T1 a, T2 b)
{
    // ...
}

Here, we use a requires-clause to impose a requirement on the type template parameters.

Requires clause positioning in C++20 function templates

The wording in this area has moved around a bit. In C++20, we had this rule in [temp.over.link]/7:

Two function templates are equivalent if they are declared in the same scope, have the same name, have equivalent template-heads, and have return types, parameter lists, and trailing requires-clauses (if any) that are equivalent using the rules described above to compare expressions involving template parameters. Two function templates are functionally equivalent if they are declared in the same scope, have the same name, accept and are satisfied by the same set of template argument lists, and have return types and parameter lists that are functionally equivalent using the rules described above to compare expressions involving template parameters. If the validity or meaning of the program depends on whether two constructs are equivalent, and they are functionally equivalent but not equivalent, the program is ill-formed, no diagnostic required.
[Note 7: This rule guarantees that equivalent declarations will be linked with one another, while not requiring implementations to use heroic efforts to guarantee that functionally equivalent declarations will be treated as distinct.
// guaranteed to be the same
template <int I> void f(A, A<I+10>);
template <int I> void f(A, A<I+10>);

// guaranteed to be different
template <int I> void f(A, A<I+10>);
template <int I> void f(A, A<I+11>);

// ill-formed, no diagnostic required
template <int I> void f(A, A<I+10>);
template <int I> void f(A, A<I+1+2+3+4>);
-end note]

In your example:

template <typename T>
    requires Fooable<T>
void do_something(T&); // (1)

template <typename T>
void do_something(T&) requires Fooable<T>; // (2)

These are functionally equivalent (they have the same constraints, basically) but not equivalent (they have different template-heads - the requires clause after the template parameters is part of the template-head), which makes this ill-formed no diagnostic required. In practice, because they're not equivalent, they're different overloads - but because they're functionally equivalent, any attempt to call would be ambiguous between them.

As I point out in the other answer, these have the same meaning - it's just that you have to stick with one form for the declaration and the definition if you split them.

The current wording, after Davis Herring's omnibus paper P1787, involves going up to [basic.scope.scope]/4:

Two declarations correspond if they (re)introduce the same name, both declare constructors, or both declare destructors, unless [...] each declares a function or function template, except when [...] both declare function templates with equivalent non-object-parameter-type-lists, return types (if any), template-heads, and trailing requires-clauses (if any), and, if both are non-static members, they have corresponding object parameters.

This makes the two do_somethings not correspond, which makes them different function templates. We don't run into the new functionally equivalent but not equivalent rule (so we're not ill-formed, no diagnostic required), but we just have two function templates that are necessarily ambiguous in all cases. So... not the most useful thing in the world.

How is the best constrained function template selected with concepts?

So how is the "more efficient" sort #2 chosen?

It works because there is a partial ordering on constraints (defined by the subsumes relation).

sort #2 (the one with the randomaccess_iterator) is more constrained than sort #1 (the one with bidirectional_iterator) because randomaccess_iterator subsumes bidirectional_iterator:

template <class It>
concept bidirectional_iterator = requires /*...*/;

template <class It>
concept randomaccess_iterator = bidirectional_iterator<It> && requires /*...*/;

To make this work constraints are aware at the language level of conjunctions and disjunctions.

The process for determining if a declaration is more or less constrained than another goes like this: Constraint normalization -> constraint subsumes relation -> (defines) constraint partial ordering -> (determines) declarations are more/less constraint relation.

Simplified, normalization is the substitution of the concepts template parameters in the parameter mapping of constraints.

Example:

template <class T> concept integral        = std::is_integral_v<T>;
template <class T> concept signed_integral = integral<T> && std::is_signed_v<T>;
template <class T> concept integral_4      = integral<T> && sizeof(T) == 4;

void foo_1(integral auto)        // #0
void foo_1(signed_integral auto) // #1 
void foo_1(integral_4 auto)      // #2

auto test1()
{
    foo_1(std::uint16_t{});  // calls #0
    foo_1(std::uint32_t{});  // calls #2

    foo_1(std::int16_t{});   // calls #1
    //foo_1(std::int32_t{}); // error ambiguous between #1 and #2
}

the normal form of integral is std::is_integral_v<T>
the normal form of signed_integral is std::is_integral_v<T> ∧ std::is_signed_v<T>
the normal form integral_4 is std::is_integral_v<T> ∧ sizeof(T) == 4
signed_integral subsumes integral
integral_4 subsumes integral
#1 is more constraint than #0
#2 is more constraint than #0

Example:

template <class T> concept integral            = std::is_integral_v<T>;
template <class T> concept signed_integral_sad = std::is_integral_v<T> &&
                                                     std::is_signed_v<T>;
template <class T> concept integral_4_sad      = std::is_integral_v<T> && sizeof(T) == 4;

void foo_2(integral auto)             // #0
void foo_2(signed_integral_sad auto); // #1
void foo_2(integral_4_sad auto);      // #2

auto test2()
{
    foo_2(std::uint16_t{});   // calls #0
    //foo_2(std::uint32_t{}); // error ambiguous between #0 and #2

    //foo_2(std::int16_t{});  // error ambiguous between #0 and #1
    //foo_2(std::int32_t{});  // error ambiguous between #0, #1 and #2
}

the normal form of integral is std::is_integral_v<T>
the normal form of signed_integral_sad is std::is_integral_v<T> ∧ std::is_signed_v<T>
the normal form integral_4_sad is std::is_integral_v<T> ∧ sizeof(T) == 4

However there is a rule

§13.5.1.2 Atomic constraints [temp.constr.atomic]

Two atomic constraints, e1 and e2, are identical if they are formed from the same appearance of the same expression [...]

This means that the std::is_integral_v<T> atomic expressions from the 3 normal forms are not identical between them because they were not formed from the same expression. So:

there is no subsumes relation
there is no more constraint relation

Which leads to the extra ambiguities.

§ 13.5.1 Constraints [temp.constr.constr]

A constraint is a sequence of logical operations and operands that specifies requirements on template arguments. The operands of a
logical operation are constraints. There are three different kinds of
constraints:

(1.1) conjunctions (13.5.1.1)

(1.2) disjunctions (13.5.1.1), and

(1.3) atomic constraints (13.5.1.2).

§13.5.1.1 Logical operations [temp.constr.op]

There are two binary logical operations on constraints: conjunction and disjunction. [Note: These logical operations have no corresponding
C++ syntax. For the purpose of exposition, conjunction is spelled
using the symbol ∧ and disjunction is spelled using the symbol ∨]

§13.5.3 Constraint normalization [temp.constr.normal]

The normal form of an expression E is a constraint (13.5.1) that is defined as follows:

(1.1) The normal form of an expression ( E ) is the normal form of
E.

(1.2) The normal form of an expression E1 || E2 is the
disjunction (13.5.1.1) of the normal forms of E1 and E2.

(1.3) The normal form of an expression E1 && E2 is the conjunction
of the normal forms of E1 and E2.

(1.4) The normal form of
a concept-id C<A1, A2, ..., An> is the normal form of the
constraint-expression of C, after substituting A1, A2, ..., An for
C’s respective template parameters in the parameter mappings in each
atomic constraint. [...]

(1.5) The normal form of any other
expression E is the atomic constraint whose expression is E and
whose parameter mapping is the identity mapping.

The process of obtaining the normal form of a constraint-expression is called normalization.

§13.5.4 Partial ordering by constraints [temp.constr.order]

A constraint P subsumes a constraint Q if and only if, for every disjunctive clause Pi in the disjunctive normal form
¹³⁰ of P, Pi subsumes every conjunctive clause Qj in
the conjunctive normal form ¹³¹ of Q, where

(1.1) a disjunctive clause Pi subsumes a conjunctive clause Qj
if and only if there exists an atomic constraint Pia in Pi for
which there exists an atomic constraint Qjb in Qj such that Pia
subsumes Qjb, and

(1.2) an atomic constraint A subsumes
another atomic constraint B if and only if A and B are identical
using the rules described in 13.5.1.2.

[Example: Let A and B
be atomic constraints (13.5.1.2). The constraint A ∧ B subsumes A,
but A does not subsume A ∧ B. The constraint A subsumes A ∨ B,
but A ∨ B does not subsume A. Also note that every constraint
subsumes itself. — end example]

[Note: The subsumption relation defines a partial ordering on constraints. This partial ordering is used to determine

(2.1) the best viable candidate of non-template functions (12.4.3),

(2.2) the address of a non-template function (12.5),

(2.3) the matching of template template arguments (13.4.3),

(2.4) the partial ordering of class template specializations (13.7.5.2), and

(2.5) the partial ordering of function
templates (13.7.6.2).

— end note]

A declaration D1 is at least as constrained as a declaration D2 if

(3.1) D1 and D2 are both constrained declarations and D1’s
associated constraints subsume those of D2; or

(3.2) D2 has no associated constraints.

A declaration D1 is more constrained than another declaration D2 when D1 is at least as constrained as D2, and D2 is not at
least as constrained as D1.

130) A constraint is in disjunctive normal form when it is a
disjunction of clauses where each clause is a conjunction of atomic
constraints. [Example: For atomic constraints A, B, and C, the
disjunctive normal form of the constraint A ∧ (B ∨ C) is (A ∧ B) ∨ (A ∧ C). Its disjunctive clauses are (A ∧ B) and (A ∧ C). — end
example]

131) A constraint is in conjunctive normal form when it is a
conjunction of clauses where each clause is a disjunction of atomic
constraints. [Example: For atomic constraints A, B, and C, the
constraint A ∧ (B ∨ C) is in conjunctive normal form. Its
conjunctive clauses are A and (B ∨ C). — end example

C++20 Concepts : Which template specialization gets chosen when the template argument qualifies for multiple concepts?

This is because concepts can be more specialized than others, a bit like how template order themselves. This is called partial ordering of constraints

In the case of concepts, they subsumes each other when they include equivalent constraints. For example, here's how std::integral and std::signed_integral are implemented:

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

template<typename T> //   v--------------v---- Using the contraint defined above
concept signed_integral = std::integral<T> && std::is_signed_v<T>;

Normalizing the constraints the compiler boil down the contraint expression to this:

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

template<typename T>
concept signed_integral = std::is_integral_v<T> && std::is_signed_v<T>;

In this example, signed_integral implies integral completely. So in a sense, a signed integral is "more constrained" than an integral.

The standard writes it like this:

From [temp.func.order]/2 (emphasis mine):

Partial ordering selects which of two function templates is more
specialized than the other by transforming each template in turn (see next paragraph) and performing template argument deduction using the function type.
The deduction process determines whether one of the templates is more specialized than the other.
If so, the more specialized template is the one chosen by the partial ordering process.
If both deductions succeed, the partial ordering selects the more constrained template as described by the rules in [temp.constr.order].

That means that if there is multiple possible substitution for a template and both are choosen from partial ordering, it will select the most constrained template.

From [temp.constr.order]/1:

A constraint P subsumes a constraint Q if and only if, for every disjunctive clause P_i in the disjunctive normal form of P, P_i subsumes every conjunctive clause Q_j in the conjunctive normal form of Q, where
a disjunctive clause P_i subsumes a conjunctive clause Q_j if and only if there exists an atomic constraint P_ia in P_i for which there exists an atomic constraint Q_jb in Q_j such that P_ia subsumes Q_jb, and
an atomic constraint A subsumes another atomic constraint B if and only if A and B are identical using the rules described in [temp.constr.atomic].

This describe the subsumption algorithm that compiler use to order constraints, and therefore concepts.

Is a requires expression an atom when normalizing constraints?

Yes your understanding is correct. For subsumption (what you denote by <) to occur, there has to be a certain relationship between the normal forms of the constraint expression. And if one examines the constraint normalization process:

[temp.constr.normal]
1 The normal form of an expression E is a constraint that is defined as follows:
The normal form of an expression ( E ) is the normal form of E.
The normal form of an expression E1 || E2 is the disjunction of the normal forms of E1 and E2.
The normal form of an expression E1 && E2 is the conjunction of the normal forms of E1 and E2.
The normal form of a concept-id C<A1, A2, ..., An> is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C's respective template parameters in the parameter mappings in each atomic constraint. If any such substitution results in an invalid type or expression, the program is ill-formed; no diagnostic is required.

[ ... ]
The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

one sees that logical AND expressions, logical OR expressions, and concept-ids are the only expressions that get "broken down".

Does Constraint Subsumption Only Apply to Concepts