P1107R0
Constrained Deduction

1. Problem Statement

Template argument deduction is a basic feature of C++ templates. There are several quite distinct uses of it:

• to instantiate a generic algorithm for a given type (template <typename T> auto min(T, T))

• handle various combinations of cv-ref qualifiers (template <typename T> auto foo(T&&))

• disable a function instantiation using SFINAE or the new requires machinery (template <typename T> auto foo(T) requires predicate<T>)

• combinations of above

For an illustration, humor a contrived example. Consider a get for a simple value container, which is intended to be inherited from:

struct box {
  std::vector<int> value;
};


template <typename Box>
decltype(auto) get(Box&& x)
    requires DerivedFrom<B, box> {
  // borrow forward_like from [[p0847r1]] - like std::forward, but forwards
  // its parameter based on the value-category of the template parameter.
  return std::forward_like<Box>(x.box::value); /* access the *box* value */
}

The intention is to forward the value-category of the box to the accessed value. There are only 8 possible useful instantiations of the get function: box&, box&&, box const&, box const&&, and their volatile versions. Since box is intended to be inherited from, get will get instantiatiations for every derived, however, leading to code bloat.

While the example is contrived for clarity, should get be a more complex function, such code bloat does become serious, and the above has been a concern for library implementers since templates were added to the language. Every time templates become more useful, the problem gets worse; first, when forwarding references were added to the language, because they added an orthogonal reason to overload, and it will get even worse when [p0847r1] or any spiritual successor lands, because it will provide a very powerful vector for addition of functions which exhibit exactly this problem (while solving DRY for member functions).

The main issues with template code bloat are more machine code than necessary, additional exception tables and duplicate work the optimizer has to do to optimize every copy, leading to slower compile times.

There is a separate issue from code bloat, however. When writing templates that are really supposed to operate on a particular base-class type, one has to qualify every member access with the type’s name, because derived classes can shadow those methods. This will become far more prevalent should [p0847r1] land. Deduction expressions are a flexible way to solve a variety of issues such an extension would introduce, in addition to being an extremely powerful way to constrain template instantiation in deduced contexts.

2. Proposed Solution

We are proposing a mechanism to allow a metafunction to compute the final deduction from the first-pass deduction that occurs in C++17.

2.1. Example

template <typename Box : like_t<Box, box>>
decltype(auto) get(Box&& x) {
  return std::forward_like<Box>(x.value);
}

• like_t copies (and overwrites) any cv-ref qualifiers on its second parameter with the ones on its first

• There is no need to use x.box::value anymore, as like_t<Box, box> always results in a cv-qualified box

• the requires clause is no longer necessary, since a reference to a box will always only bind to references to boxes and their derived classes.

3. Syntax

4. Proposed Semantics

This section describes the feature using a few "as if rewritten as" sections, each describing a part of the proposed mechanism.

4.1. Deduction

4.1.1. For a type template parameter

// template <
CONCEPT T = DEFAULT_EXPR : DEDUCTION_EXPR
// > void 

1. The deduction of T proceeds normally until T is deduced as per C++17 rules, with any default initializer expressions executing if necessary. Let us name this result the initial deduction.

2. Immediately after the initial deduction is known, but before executing any requires constraints, execute DEDUCTION_EXPR in the with the same set name bindings available as the DEFAULT_EXPR would have (or has) been run with, with the addition of T being bound to the initial deduction. Let the value of DEDUCTION_EXPR be the final deduction. If DEDUCTION_EXPR does not evaluate to a type, this results in a substitution failure (SFINAE).

3. Any requires expressions that would be run in C++17 are run now, with the name T being bound to the final deduction.

Deduction of following parameters is done with the name T being bound to the constrained deduction.

4.1.2. For a value template parameter

The algorithm is exactly the same, but the the expression after the colon has to result in a a value. Basically, DEDUCTION_EXPR has to result in something that can be bound to the way the template parameter is declared.

4.1.3. For a template-template parameter

See values. Same rules - if it binds, it works, if it doesn’t, SFINAE.

4.2. Function signature construction

Same as now - the deduced parameters are substituted back into the function signature (and the body of the template), with deduced parameters now meaning final deduced parameters. This may result in an invalid signature, which is a SFINAE condition.

4.3. Overload set construction

The construction of the overload set is unchanged, once one takes into account that candidates are generated differently than before. Compared to C++17, the overload set consists of functions instantiated from the very same candidate templates as before, though their signatures may be different. If two templates generate the same function signature, the result is ambiguous, and therefore results in an invalid program (diagnostic required).

5. Examples

6. FAQ

6.1. Can I use a previously deduced parameter in a DEDUCTION_EXPR?

Yes! This should work:

template <
  typename T : like_t<T, box>
  typename U : decltype(declval<T>().value)
> foo(T&&, U) {}

T always deduces to some cv-qualified version of box or box&, and U is coerced to the declval of the box’s value. Note that T is the already fully deduced box in U's deduction-expr.

6.2. Can I use the initial deduction in other template parameters?

In other words, given

template <
  typename T : long /* T will *always* be long */, 
  typename U = T
>
void foo(T) {}

is it possible to have U deduce to int instead of long in the call foo(1)?

The answer is no. There is no way to access the initial deduction outside of the deduction-expr (though I’m sure clever metaprogrammers can find a way to export it somehow).

6.3. What if the final signature doesn’t bind to the given parameters?

The scenario is the following:

template <typename T : int>
void foo(T) {}

foo(nullptr);

The initial deduction for T is nullptr_t, but the deduction-expr for T forces it to be int. The resulting signature is foo(int), which does not match, and is removed from the overload set. In the absence of additional overloads for foo this fails with a compilation error because there were no matching functions to call.

6.4. What happens if two templates generate the same overload

Same as now - if the best match is ambigous, the program ill-formed (diagnostic required). Two templates resulting in the same best-match overload is a special case of this eventuality.

6.5. Could Concepts Solve This?

No. Concepts can only answer the question of whether to admit or remove an overload once it has already been enumerated as a candidate for the overload set, which is almost no better than enable_if, because it happens _after_ template argument deduction has already occurred. In this case, we need to change the template argument deduction rules themselves, so that the template parameter itself is deduced in a programmable fashion, and _then_ perhaps constrained by a concept.

7. Acknowledgements

The authors would like to thank Alisdair Meredith, especially, as he had both the original complaint about the deduction rules, and the first workable suggestion of how to fix it. This solution is far more general, but every proposal needs a spark.

The authors would additionally like to thank everyone (as I don’t think there was anyone who remained silent) who attended the C++Now 2018 talk "My Little *this deduction: Friendship is Uniform", for their helpful comments, commentary, hints, tips, and ideas, whithout which this paper would not have gotten the idelological momentum to be born.