May std::tuple_element double as a universal template argument retriever?

Question

This question got me thinking. Sometimes it's useful to grab an actual argument from a class template specialization, if it fails to define a public typedef of the argument. In C++03 it's a sign of either bad template design, or contrary design intent, and not particularly common. But variadic templates make typedef coverage impossible, so it would be nice to have a tool around to solve the problem without additional work.

C++0x solves the typedef problem for one particular variadic template, tuple.

tuple_element< 2, tuple< char, short, int > >::type my_int; // nth element type

But tuple_element isn't married to tuple; it also works with pair and array. Its declaration doesn't mention tuple.

template< size_t index, typename something_like_a_tuple >
struct tuple_element; // general case is left incomplete, unimplemented

tuple is related by a partial specialization:

template< size_t index, typename ... tuple_elements >
struct tuple_element< index, tuple< tuple_elements ... > > { // impl. in here

But it doesn't need to be. A template template parameter could match tuple, along any other template parameterized only over types.

template< size_t index,
    template< typename ... > class template_over_types,
    typename ... types >
struct tuple_element< index, template_over_types< types ... > > {

This would allow

tuple_element< 1, almost_any_template< char, int > >::type my_int;
tuple_element< 0, pair< int, char > >::type another_int; // same specialization

and yet allow the additional specialization for array

template< size_t index, typename element, size_t extent >
struct tuple_element< index, array< element, extent > > 
    { typedef element type; }

No conflict is possible because array's second argument is a size_t, not a type.

---

Unfortunately, the user is allowed to specialize the tuple_element interface for their own types. The user's precondition and their guarantee is given by C++0x §17.6.3.2.1/1:

A program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

So, not only must the general specialization not conflict with the array specialization, it can't conflict with any specialization that names a user-defined type. That is, if the user declares a specialization, the existence of the general argument getter cannot affect whether it's chosen.

When ambiguity arises in instantiation (that is, two partial specializations match an argument list), the alternatives are compared to determine which is most specialized, in other words least generalized. Call the alternatives A and B. This means that, if A can do B's job, but B cannot do A's job, then B is more specialized. A is the generalist. B will be chosen. The actual arguments instigating the instantiation aren't considered, since they are already known to be a match to both candidates.

Since we want the general template to defer to everything else, we're in good shape.

Generality is checked by replacing the partial specialization parameters in A with unique dummy types, and checking whether B can also implement such a specialization. Repeat with the roles reversed, and if the opposite result is obtained, one candidate is known to be more specialized.

The existence of a user-defined type in the user's specialization guarantees its precedence, because there must be a corresponding unique dummy type in the argument-getter which won't match it.

For example, here is a very general user-declared specialization. It defines tuple_element for any type-parameterized template containing a given user_type.

 template< size_t I,
           template< typename ... > class any_template,
           typename ... T, typename ... U >
 struct tuple_element< I, any_template< T ..., ::user_type, U ... > >;

The sequence ..., user_type, ... can be handled by the general case, but the user's case cannot handle a sequence composed entirely of artificial unique types, because it won't include user_type.

If any user specialization is a candidate, it will be the superior one.

_{(The standard does specify in pseudocode a separate partial specialization for tuple, but it could be omitted under the as-if rule. Anyway, if implemented, it would be covered by the same precedence rule as protects the user.)}

---

I haven't made many forays into the partial ordering rules. Is this analysis correct? Is it OK for the implementation to expose a general template indexer through std::tuple_element?

Answer 1

So, not only must the general specialization not conflict with the array specialization, it can't conflict with any specialization that names a user-defined type. That is, if the user declares a specialization, the existence of the general argument getter cannot affect whether it's chosen.

I don't understand this. What do you mean?

---

Is it OK for the implementation to expose a general template indexer through std::tuple_element?

It's impossible to do so for the general case. Imagine this one

template<int A, char B, long C, class D, int &X, int(*Handler)()>
struct funny_template { };

int x, y();
std::tuple_element<3, funny_template<1, 2, 3, long, x, y> >::type along = 0;

Happy macro meta-programming :)

---

I haven't made many forays into the partial ordering rules. Is this analysis correct?

Partial ordering for two partial specializations

template<class A1, ..., class AN>
class T<Am1, ..., AmM>;

template<class B1, ..., class BL>
class T<Bm1, ..., BmM>;

Works like transforming them to function templates and ordering them

template<class A1, ..., class AN>
void f(T1<Am1, ..., AmM>);

template<class B1, ..., class BL>
void f(T2<Bm1, ..., BmM>);

Partial ordering like your analysis says correctly puts unique types for each template parameter transforming it to an argument for argument deduction, comparing it to the other template

T1A<Uam1, ..., UAmM> -> T2<Bm1, ..., BmM>
T2A<UBm1, ..., UBmM> -> T1<Am1, ..., AmM>

If there is a non-deduced context it's not compared like usual. Like if BmM is typename Foo::X, the first deduction above would consider deduction of the last sub-type as success because there can't be a mismatch for a nondeduced context. The other way around though, Foo::X against AmM can mismatch though if AmM is not a nondeduced context itself.

If deduction succeeds for one round and not the other way around (... leaving off some other rules because they only happen for real function template ordering), the template on the right side above for the round that failed deduction is more specialized. Otherwise, the partial specializations are unordered.