C++ concepts placeholder type deduction

Question

In the Ranges spec N4622 the Same concept is defined to take two types T and U, but is sometimes used inside requires with just one like:

{ t } -> Same<T>;

What's the rule that enables the deduction for the 2nd type U? (e.g. from the Concepts spec N4630)

The simplest similar example would be:

template <class T, class U>
concept bool C = (sizeof(T) == sizeof(U)) && (sizeof(U) != 1);

template <class T>
concept bool D = requires(T t){
  // How is U deduced here? 
  {t} -> C<T>; 
};

template <class T>
  requires D<T>
void fn() {}

int main() {
  // Fails with: unable to deduce placeholder type 'C<char>' from 't'
  // That's expected.
  //fn<char>();

  // But how does this work?
  fn<int>();
}

Tested sample using g++ 8.0.0 and -fconcepts.

Answer 1

What's a placeholder?

A quick recap to make sure we’re all on the same page: a placeholder type is almost, but not quite a type. It’s a stand-in for a type that will be effectively be deduced. (Similarly there also are placeholder non-types [resp. templates] which are stand-ins for non-types. To avoid going on a tangent I’ll just mention their existence here and use the all-encompassing placeholder term from now on.)

Before concepts the only placeholders we have are the auto and decltype(auto) specifiers:

// the specifiers are all placeholders for `int`
auto i = 42;
auto& lref = i;
auto&& rref = 0;
decltype(auto) = 2 * i;

With concepts we can use placeholders in more intricate ways:

// two placeholders for `int`
std::pair<auto, auto> p = std::make_pair(1, 4);

// one placeholder
std::pair<auto, int> q = p;

And here’s where it gets tricky: a concept itself can be used as a placeholder:

template<typename Int>
concept bool Integral = …;

// placeholder for `int` constrained by `Integral<int>`
Integral a = 0;

// same as above
Integral<> b = a;

template<typename Lhs, typename Rhs>
concept bool EqualityComparable = …;

// another placeholder for `int`
// this time constrained by `EqualityComparable<int, double>`
EqualityComparable<double> c = a;

Read the binary EqualityComparable example carefully. What makes concepts as placeholders tricky is that the very first concept parameter has special treatment and will not be mentioned in the argument list. Whatever arguments appear in the angle bracket list (if any) correspond to the subsequent parameters.

Placeholders in requirements

Let’s write a concept for something that has a size(). For the sake of demonstration we’ll be expecting that the result of this size() operation should be usable as an Incrementable variable (rather than something sensible like an Integral concept).

template<typename Incr>
concept bool Incrementable = requires(Incr incr) {
    ++incr;
};

template<typename Cont>
concept bool Sizeable = requires(Cont const cont) {
    // requirement #1
    { cont.size() } -> Incrementable
};

Our requirement #1 is a compound requirement of a special kind. Namely, it is one where a placeholder appears in the syntactic trailing-return-type. The effects are as if we had written:

template<Incrementable Incr>
void valid_for_incrementable(Incr incr);

template<typename Cont>
concept bool Sizeable = requires(Cont const cont) {
    cont.size();
    valid_for_incrementable(cont.size());
};

Plainly put the purpose of a compound requirement is to introduce two constraints at once: that the expression in brackets is valid, and that it can be used as the argument to an invented constraint-validating function template.

All together now

Armed with our knowledge of placeholders and of their uses in compound requirements, we can find our answer:

template<typename T>
concept bool Demo = requires(T t) {
    { t } -> C<T>;
};

effectively means that we introduce a C<T, T> constraint on the t expression. Had the placeholder been C<int> instead, then the constraint would have been C<T, int> instead and so on.