C++ provides a simple syntax for constraining function template arguments. For example, you can constrain a template function foo to take only pointers as arguments using:
template <class T> void foo (T* p);
Unfortunately more complicated constraints (like the ever popular "T inherits from myBase") cannot be expressed in such a simple way.
Previous work on constraining template function arguments in C++ (Bjarne Stroustrup and Jeremy Siek) has focused on generating better error messages when a template is instantiated with an inappropriate type.
For example, using Boost's Concept Checking Library, this code
template <class T>
void foo (T x)
{
function_requires< EqualityComparableConcept<T> >();
// ...
};
will give a (more informative) compile-time error when instantiated
with a type T that doesn't satisfy the requirements.
We focus on a slightly different problem — preventing a function template from being instantiated at all for inappropriate types. Consider what happens if our generic function foo is overloaded. Perhaps there are different implementations of foo for different sets of types. In this case, we want to keep the wrong function templates from being added to the overload set considered during overload resolution, thereby preventing ambiguity errors. Compile-time errors in the body of a function template being instantiated are not helpful in this regard.
Suppose we have a pair of predicates on types and overloads of foo that can handle types satisfying the corresponding predicates.
template <class T> struct Predicate1 { enum { value = ... }; };
template <class T> void foo (T x) { ... }
template <class T> struct Predicate2 { enum { value = ... }; };
template <class T> void foo (T x) { ... }
We want the first foo to accept only types satisfying Predicate1<T>::value and the second to accept only types satisfying Predicate2<T>::value.
We can use the SFINAE ("Substitution Failure Is Not An Error") principle to constrain which overloaded function templates are added to the overload set for any given type. The key to the use of SFINAE is that only the signature of the function is considered while creating the overload set. The signature of a template function includes all the parameters and the return type, but not the body.
Stroustrup and Siek were placing template constraints into the body of the function to generate compile-time errors. What happens if we place our constraints in the parameter list? This seems problematic, since the parameter list is already "busy" — it's being used to pass the arguments!
After meditating on this for a while, we discover that function parameters with default values can be used for this purpose.
template <bool condition> struct Constraint;
template <> struct Constraint<true> { typedef int intAlias; };
// First overload for foo
template <class T>
void foo (T x, typename Constraint<Predicate1<T>::value>::intAlias = 0)
{ ... }
// Second overload for foo
template <class T>
void foo (T x, typename Constraint<Predicate2<T>::value>::intAlias = 0)
{ ... }
Optionally, we could add a macro SATISFYING:
template <class T>
void foo (T x, SATISFYING (Predicate1<T>::value)) { ... }
template <class T>
void foo (T x, SATISFYING (Predicate2<T>::value)) { ... }
This technique works for any functions, including member functions, to which we can add trailing unused parameters with default values.
But not all C++ functions can have trailing parameters with default values added. The signature of many functions are predetermined. For example, overloaded operators:
template <class T> bool operator== (const T& x, const T& y);
It looks like there is no hope for constraining the template parameter T here, since we cannot expand the signature to add additional unused parameters. After some further meditation, we realize that we can make one of the elements of the existing signature do double duty. We can replace the return type bool with a templated expression always identical to bool; then constrain that templated expression to be instantiable only for the types we want.
template <bool condition> struct Constraint;
template <> struct Constraint<true> { typedef bool boolAlias; };
template <class T>
typename Constraint<Predicate1<T>::value>::boolAlias
operator== (const T& x, const T& y) { ... }
template <class T>
typename Constraint<Predicate2<T>::value>::boolAlias
operator== (const T& x, const T& y) { ... }
This works with a standard compliant compiler. Unfortunately, currently not all compilers consider the return types of functions when comparing function template signatures (g++ 3.2 fails; g++ 3.3 is OK).
We can easily generalize our Constraint class so that it can be used to "return" any type:
// Completely general Constraint class
template <bool condition, class type> struct Constraint;
template <class type> struct Constraint<true, type> { typedef type Type; };
template <class T>
typename Constraint<Predicate1<T>::value, bool>::Type
operator== (const T& x, const T& y) { ... }
template <class T>
typename Constraint<Predicate2<T>::value, bool>::Type
operator== (const T& x, const T& y) { ... }
Returning to our first example, one might wonder if we could constrain a template parameter here...
template <class T>
void foo (T x);
by letting the (only) parameter for foo perform double duty:
template <class T>
void foo (typename Constraint<Predicate<T>::value,T>::Type x);
Unfortunately, this technique fails. This function template will never be chosen by the compiler because template argument deduction cannot be done with a type expression containing :: (the compiler might have to explore an infinity of types). A given function parameter can be used for template argument deduction or template argument constraints, but not both simultaneously.
Because only the function parameters of a function template participate in template argument deduction, but the entire function signature (including the return type) is used in constraining instantiations via SFINAE, we can use our technique with any C++ function template specifying a return type, modulo bugs with existing compilers.
Let's return to the example of operator==. If we want to support g++, we can make operator== work by observing that we can use the symmetric function parameters for operator== in an asymmetric way. We can use the first parameter for template argument deduction and the second parameter for template argument constraints.
template <bool condition, class type> struct Constraint;
template <class type> struct Constraint<true, type> { typedef type Type; };
template <class T> bool
operator== (const T& x,
typename Constraint<Predicate1<T>::value, const T&>::Type y);
template <class T> bool
operator== (const T& x,
typename Constraint<Predicate2<T>::value, const T&>::Type y);
But that technique only works when a spare parameter is available, so it's not a general solution.
A more effective bug workaround uses dummy namespaces to avoid tripping g++ 3.2's ambiguity meter:
namespace Dummy1
{
template <class T1, class T2>
typename Constraint<Predicate1<T>::value, bool>::Type
operator== (const T1& x, const T2& y) { ... }
}
namespace Dummy2
{
template <class T1, class T2>
typename Constraint<Predicate2<T>::value, bool>::Type
operator== (const T1& x, const T2& y) { ... }
}
using Dummy1::operator==;
using Dummy2::operator==;
We use this solution in our own code.
Are there any kinds of C++ functions to which we cannot apply our technique at all?
There are C++ functions without any return type. Constructors don't have a return type, but we can use the dummy default parameter trick instead, so these are no problem.
Conversion operators like
class Foo
{
template <class T> operator T ();
};
are the only ones we are aware of for which template parameters cannot
be constrained as we would like — they have no parameters and no
(explicitly specified) return types. Unfortunately, this is a
particularly important template to be able to constrain, since
unfettered conversion is a nightmare.
What are the lessons for the C++ committee? It seems obvious to me that C++ should add a real constraint mechanism to free users from the collection of kludges presented here. We agree with Stroustrup that adding support for limited specific constraints like inheritance from a given base is a mistake — that would not be general enough.
We want a constraint mechanism that allows any kind of compile-time computation to constrain template arguments.
Here's a syntax we like, showing how to implement the standard "inheritance from base" example, using the Boost library:
template <class T>
satisfying (is_base_and_derived<Base,T>::value)
void foo (T x);
The semantics are obvious and intuitive. Compared with other C++ language features, this seems easy to implement. Of course, introducing a new keyword satisfying will cause much dissatisfaction. We leave that problem to the committee.