Why does the order of template argument substitution matter?
C++TemplatesC++11Language LawyerC++14C++ Problem Overview
C++11
> 14.8.2 - Template Argument Deduction - [temp.deduct]
> > 7 The substitution occurs in all types and expressions that are used in the function type and in template parameter declarations. The expressions include not only constant expressions such as those that appear in array bounds or as nontype template arguments but also general expressions (ie. non-constant expressions) inside sizeof, decltype, and other contexts that allow non-constant expressions.
C++14
> 14.8.2 - Template Argument Deduction - [temp.deduct]
> > 7 The substitution occurs in all types and expressions that are used in the function type and in template parameter declarations. The expressions include not only constant expressions such as those that appear in array bounds or as nontype template arguments but also general expressions (ie. non-constant expressions) inside sizeof, decltype, and other contexts that allow non-constant expressions. The substitution proceeds in lexical order and stops when a condition that causes deduction to fail is encountered.
The added sentence explicitly states the order of substitution when dealing with template parameters in C++14.
The order of substitution is something that most often isn't given a lot of attention. I have yet to find a single paper on why this matters. Maybe this is because C++1y hasn't been fully standardized yet, but I'm assuming such a change must have been introduced for a reason.
The question:
- Why, and when, does the order of template argument substitution matter?
C++ Solutions
Solution 1 - C++
As stated C++14 explicitly says that the order of template argument substitution is well-defined; more specifically it will be guaranteed to proceed in "lexical order and halt whenever a substitution causes the deduction to fail.
Compared to C++11 it will be much easier to write SFINAE-code that consists of one rule depending on another in C++14, we will also move away from cases where undefined ordering of template substitution can make our entire application suffer from undefined-behaviour.
Note: It's important to note that the behavior described in C++14 has always been the intended behavior, even in C++11, just that it hasn't been worded in such an explicit way.
What is the rationale behind such change?
The original reason behind this change can be found in a defect report originally submitted by Daniel Krügler:
FURTHER EXPLANATION
When writing SFINAE we as developers depend on the compiler to find any substitution that would yield an invalid type or expression in our template when used. If such invalid entity is found we'd like to disregard whatever the template is declaring and move on to hopefully find a suitable match.
Substitution Failure Is Not An Error, but a mere.. "aw, this didn't work.. please move on".
The problem is that potential invalid types and expressions are only looked for in the immediate context of the substitution.
> 14.8.2 - Template Argument Deduction - [temp.deduct]
> > 8 If a substitution results in an invalid type or expression, type deduction fails. An invalid type or expression is one that would be ill-formed if written using the substituted arguments.
> >
> > [ Note: Access checking is done as part of the substitution process. --end note ]
> >
> > Only invalid types and expressions in the immediate context of the function type and its template parameter types can result in a deduction failure.
> >
> > [ Note: The evaluation of the substituted types and expressions can result in side effects such as the instantiation of class template specializations and/or function template specializations, the generation of implicitly-defined functions, etc. Such side effects are not in the "immediate context" and can result in the program being ill-formed. --end note]
In other words a substitution that occurs in a non-immediate context will still render the program ill-formed, which is why the order of template substitutions is important; it can change the whole meaning of a certain template.
More specifically it can be the difference between having a template which is usable in SFINAE, and a template which isn't.
SILLY EXAMPLE
template<typename SomeType>
struct inner_type { typedef typename SomeType::type type; };
template<
class T,
class = typename T::type, // (E)
class U = typename inner_type<T>::type // (F)
> void foo (int); // preferred
template<class> void foo (...); // fallback
struct A { };
struct B { using type = A; };
int main () {
foo<A> (0); // (G), should call "fallback "
foo<B> (0); // (H), should call "preferred"
}
On the line marked (G) we want the compiler to first check (E) and if that succeeds evaluate (F), but before the standard change discussed in this post there was no such guarantee.
The immediate context of the substitutions in foo(int) includes;
(E)making sure that the passed inThas::type(F)making sure thatinner_type<T>has::type
If (F) is evaluated even though (E) results in an invalid substitution, or if (F) is evaluated before (E) our short (silly) example won't make use of SFINAE and we will get an diagnostic saying that our application is ill-formed.. even though we intended for foo(...) to be used in such case.
Note: Notice that SomeType::type is not in the immediate context of the template; a failure in the typedef inside inner_type will render the application ill-formed and prevent the template from making use of SFINAE.
What implications will this have on code development in C++14?
The change will dramatically ease the life of language-lawyers trying to implement something which is guaranteed to be evaluated in a certain way (and order), no matter what conforming compiler they are using.
It will also make template argument substitution behave in a more natural way to non-language-lawyers; having the substitution occur from left-to-right is far more intuitive than erhm-like-any-way-the-compiler-wanna-do-it-like-erhm-....
Isn't there any negative implication?
The only thing I can think of is that since the order of substitution will occur from left-to-right a compiler is not permitted to handle multiple substitutions at once using an asynchronous implementation.
I have yet to stumble across such implementation, and I doubt that it would result in any major performance gain, but at least the thought (in theory) kinda fits on the "negative" side of things.
As an example: A compiler will not be able to use two threads that simultaneously does substitutions when instantating a certain template without any mechanism to act like the substitutions that occured after a certain point never happened, if that is required.
The story
Note: An example that could have been taken from real life will be presented in this section to describe when and why the order of template argument substitution matters. Please let me know (using the comment section) if anything is not clear enough, or maybe even wrong.
Imagine that we are working with enumerators and that we'd like a way to easily obtain the underlying value of the specified enumeration.
Basically we are sick and tired of always having to write (A), when we would ideally want something closer to (B).
auto value = static_cast<std::underlying_type<EnumType>::type> (SOME_ENUM_VALUE); // (A)
auto value = underlying_value (SOME_ENUM_VALUE); // (B)
THE ORIGINAL IMPLEMENTATION
Said and done, we decide to write an implementation of underlying_value looking as the below.
template<class T, class U = typename std::underlying_type<T>::type>
U underlying_value (T enum_value) { return static_cast<U> (enum_value); }
This will ease our pain, and seems to do exactly what we want; we pass in an enumerator, and get the underlying value back.
We tell ourselves that this implementation is awesome and ask a colleague of ours (Don Quixote) to sit down and review our implementation before pushing it out into production.
THE CODE REVIEW
Don Quixote is an experienced C++ developer that has a cup of coffee in one hand, and the C++ standard in the other. It's a mystery how he manages to write a single line of code with both hands busy, but that's a different story.
He reviews our code and comes to the conclusion that the implementation is unsafe, we need to guard std::underlying_type from undefined-behaviour since we can pass in a T which is not of enumeration type.
> 20.10.7.6 - Other Transformations - [meta.trans.other]
> > templateT shall be an enumeration type (7.2)
> > Comments: The member typedef type shall name the underlying type of T.
Note: The standard specifies a condition for underlying_type, but it doesn't go any further to specifiy what will happen if it's instantiated with a non-enum. Since we don't know what will happen in such case the usage falls under undefined-behavior; it could be pure UB, make the application ill-formed, or order edible underwear online.
THE KNIGHT IN SHINING ARMOUR
Don yells something about how we always should honor the C++ standard, and that we should feel tremendous shame for what we have done.. it's unacceptable.
After he has calmed down, and had a few more sips of coffee, he suggests that we change the implementation to add protection against instantiating std::underlying_type with something which isn't allowed.
template<
typename T,
typename = typename std::enable_if<std::is_enum<T>::value>::type, // (C)
typename U = typename std::underlying_type<T>::type // (D)
>
U underlying_value (T value) { return static_cast<U> (value); }
THE WINDMILL
We thank Don for his discoveries and are now satisfied with our implementation, but only until we realize that the order of template argument substitution isn't well-defined in C++11 (nor is it stated when the substitution will stop).
Compiled as C++11 our implementation can still cause an instantiation of std::underlying_type with a T that isn't of enumeration type because of two reasons:
-
The compiler is free to evaluate
(D)before(C)since the substitution order isn't well-defined, and; -
even if the compiler evaluates
(C)before(D), it's not guaranteed that it won't evaluate(D), C++11 doesn't have a clause explicitly saying when the substitution chain must stop.
The implementation by Don will be free from undefined-behavior in C++14, but only because C++14 explicitly states that the substitution will proceed in lexical order, and that it will halt whenever a substitution causes deduction to fail.
Don might not be fighting windmills on this one, but he surely missed a very important dragon in the C++11 standard.
A valid implementation in C++11 would need to make sure that no matter the order in which the substitution of template parameters occur the instantation of std::underlying_type won't be with an invalid type.
#include <type_traits>
namespace impl {
template<bool B, typename T>
struct underlying_type { };
template<typename T>
struct underlying_type<true, T>
: std::underlying_type<T>
{ };
}
template<typename T>
struct underlying_type_if_enum
: impl::underlying_type<std::is_enum<T>::value, T>
{ };
template<typename T, typename U = typename underlying_type_if_enum<T>::type>
U get_underlying_value (T value) {
return static_cast<U> (value);
}
Note: underlying_type was used because it's a simple way to use something in the standard against what is in the standard; the important bit is that instantiating it with a non-enum is undefined behavior.
The defect-report previously linked in this post uses a much more complex example which assumes extensive knowledge about the matter. I hope this story is a more suitable explanation for those who are not well read up on the subject.