How is the best constrained function template selected with concepts?

Question

In a presentation of concepts something like this was shown:

template 
void sort(It begin, It end);            // #1

template 
void sort(It begin, It end);            // #2

std::list l{};
sort(l.begin(), l.end()); // #A  -> calls #1

std::vector v{};
sort(v.begin(), v.end()); // #B  -> calls #2

For the call #A it's simple: only sort #1 is viable as the constraint random_access_iterator is not satisfied so it calls #1.

But for the call #B both sorts are viable as both constraints (random_access_iterator and bidirectional_iterator are satisfied). So how is the "more efficient" sort #2 chosen? The presenter said "it just works".

user_2805305 · Answer

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 
concept bidirectional_iterator = requires /*...*/;

template 
concept randomaccess_iterator = bidirectional_iterator && 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  concept integral        = std::is_integral_v;
template  concept signed_integral = integral && std::is_signed_v;
template  concept integral_4      = integral && 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
the normal form of signed_integral is std::is_integral_v ∧ std::is_signed_v
the normal form integral_4 is std::is_integral_v ∧ 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  concept integral            = std::is_integral_v;
template  concept signed_integral_sad = std::is_integral_v &&
                                                     std::is_signed_v;
template  concept integral_4_sad      = std::is_integral_v && 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
the normal form of signed_integral_sad is std::is_integral_v ∧ std::is_signed_v
the normal form integral_4_sad is std::is_integral_v ∧ 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 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 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

How is the best constrained function template selected with concepts?

1 Answers