How is constraint overloading resolved by the partial ordering of concept?

Question

Per cppreference, the partial ordering of constraints over subsumption is used to determine "the best match for a template template argument". And in the example section, the option that is "more constrained", i.e. the stronger/tighter, condition is selected. But in practice I've found some confusing behavior when the functions concept constraints are clearly ordered and specific invocation can clearly distinguishes the strongest option.

I'm testing the following on gcc version 10.2.0 (Homebrew GCC 10.2.0): With:

template <typename... Ts>
void foo (Ts... ts) // option 1
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (sizeof...(Ts)<=3)
void foo (Ts... ts) // option 2
{
    (cout << ... << ts) << endl;
}

A call of foo(1,2) would select option 2 since its constraints are clearly stronger than option 1. On the other hand, this would clearly cause ambiguity:

template <typename... Ts>
void foo (Ts... ts) // option 1
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (sizeof...(Ts)<=3)
void foo (Ts... ts) // option 2
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (same_as<Ts, int> && ...)
void foo (Ts... ts) // option 3
{
    (cout << ... << ts) << endl;
}

since a call of foo(1,2) cannot decide whether to choose option 2 or option 3 as they are incomparable. Now, if I understand it correctly, by adding a conjunctive case like:

template <typename... Ts>
void foo (Ts... ts) // option 1
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (sizeof...(Ts)<=3)
void foo (Ts... ts) // option 2
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (same_as<Ts, int> && ...)
void foo (Ts... ts) // option 3
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (sizeof...(Ts)<=3) && (same_as<Ts, int> && ...)
void foo (Ts... ts) // option 4
{
    (cout << ... << ts) << endl;
}

Calling foo(1,2) should resolve with option 4, but my compiler says otherwise:

In function 'int main()':
error: call of overloaded 'foo(int, int)' is ambiguous
      |     foo(1,2);
      |            ^
note: candidate: 'void foo(Ts ...) [with Ts = {int, int}]'
      | void foo (Ts... ts) // option 1
      |      ^~~
note: candidate: 'void foo(Ts ...) [with Ts = {int, int}]'
      | void foo (Ts... ts) // option 2
      |      ^~~
note: candidate: 'void foo(Ts ...) [with Ts = {int, int}]'
      | void foo (Ts... ts) // option 3
      |      ^~~
note: candidate: 'void foo(Ts ...) [with Ts = {int, int}]'
      | void foo (Ts... ts) // option 4

Why is that? And if it is inevitable, is there any way around this?

Shorten

Answer 1

When compiler checks if one set of requirements is more constrained than another one, it recursively expands concepts. It also understands the meaning of &&, ||, ( ) (so the order of conjuncts/disjuncts doesn't matter, the superfluous ( ) don't matter, etc), even inside of concepts.

This part is pretty intuitive. What's not intuitive is that it's not enough for two requirements to be lexically same for them to be considered equivalent. They must literally be the same expression in the same location in the source code, at the point before concepts are expanded. This requires them to originate from the same concept.

Another non-intuitive part is && and || lose their special meaning in a fold expression, so for two fold expressions to be considered equivalent (whether they use && or || or something else) they too have to be in the same location in the source code before concepts are expanded.

Knowing this, the solution is to abstract away sizeof...(Ts) <= 3 and (same_as<Ts, int> && ...) into concepts.

There are numerous ways to do that. You can be as general or as specific as you want:

1. template <typename ...P>
   concept at_most_3 = sizeof...(P) <= 3;
   
   template <typename ...P>
   concept all_ints = (std::same_as<P, int> && ...);
   

   Usage: requires at_most_3<Ts...> && all_ints<Ts...>

2. template <auto A, auto B>
   concept less_eq = A <= B;
   
   template <typename T, typename ...P>
   concept all_same_as = (std::same_as<T, P> && ...);
   

   Usage: requires less_eq<sizeof...(Ts), 3> && all_same_as<int, Ts...>

Even the completely egregious template <bool X> concept boolean = X;, being used as requires boolean<sizeof...(Ts) <= 3> && boolean<(std::same_as<Ts, int> && ...)>, appears to work!

Awaken

Very clearly explained! I can "kind of" understand this like how, in programming languages I've used, functions defined exactly identically lexically can't compare equal. But I'm still curious about the consideration or limitation underneath the hood on this specific case, such as if this is how concepts are supposed to be used. Could you point me some further reading? – Shorten

@Shorten I don't know any good tutorials on concepts. The cppreference article can be useful. Also #58509647 – Awaken

Interesting - that boolean concept apparently makes the compiler use dependent expression equivalence, per [temp.over.link]/5, instead of lexical expression identity. Though I think there's a bit of a hole in the Standard on exactly what happens. – Dynast

Answer 2

If you try to compile :

template <typename... Ts> requires (sizeof...(Ts)<=3)
void foo (Ts... ts) // option 2
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires (sizeof...(Ts)<=3) && (is_same_v<Ts, int> && ...)
void foo (Ts... ts) // option 4
{
    (cout << ... << ts) << endl;
}

With clang 12 you got the message:

note: similar constraint expressions not considered equivalent; 
constraint expressions cannot be considered equivalent unless 
they originate from the same concept

With this hint, you can rewrite your code as:

#include <iostream>
#include <type_traits>

using namespace std;
template <typename... Ts>
void foo (Ts... ts) // option 1
{
    (cout << ... << ts) << endl;
}

template<class ... Ts>
concept LessThan3 =  (sizeof...(Ts)<=3)  ;

template<class ... Ts>
concept AllInt =  (std::same_as<Ts, int> && ...);


template <typename... Ts> requires LessThan3<Ts...>
void foo (Ts... ts) // option 2
{
    (cout << ... << ts) << endl;
}


template <typename... Ts> requires AllInt<Ts...>
void foo (Ts... ts) // option 3
{
    (cout << ... << ts) << endl;
}

template <typename... Ts> requires LessThan3<Ts...> &&  AllInt<Ts...>
void foo (Ts... ts) // option 4
{
    (cout << ... << ts) << endl;
}

int main(){
   
    foo(1,2);
    return 0;
}

Which compile with both gcc and clang: demo

What