Allowing arbitrary literal types for non-type template parameters (original) (raw)

N3413=12-0103
Jens Maurer
2012-09-19

Motivation

With the introduction of constexpr in C++11, the gap between constant expressions and allowable arguments for non-type template parameters has widened. This paper investigates how to allow arbitrary literal types for non-type template parameters with arbitrary constant expressions of the appropriate type as arguments for such template parameters.

Example:

struct C { constexpr C(int v) : v(v) { } int v; };

template struct X { int array[c.v]; };

int main() { X<C(42)> x; }

Design Considerations

"same type" and name mangling

A fundamental concept of C++ is the notion of "same type". Function overloading as well as types constructed by template instantiations require a definite and context-free determination whether two types T1 and T2 are the same or not. Current language rules ensure that this question can be unambiguously answered in most cases, even if thetype-id for the type has lexical differences. Non-template example:

typedef int T1; typedef signed int T2; void f(T1); void f(T2); // redeclaration of f(int)

Template example:

template struct S; void f(S<0>); void f(S<2-2>); // redeclaration of f(S<0>)

The existing expressiveness in this area already allowstype-ids where a compiler cannot practically determine equivalence (see 14.5.6.1 temp.over.link), for example:

template struct S; template void f(S); // #1 template void f(S<n + 0>); // ill-formed, no diagnostic required

Current rules restrict the type of a non-typetemplate-parameter to a built-in simple type, where the compiler can determine the equivalence of template arguments by built-in value equivalence. So, even with an implementation with a sign-magnitude implementation of integers, S<-0> andS<+0> are required to be the same type.

The notion of "same type" reaches beyond a single translation unit. For example, given:

template struct S { static int x; };

the expression S<42>::x must be the same lvalue (i.e. must refer to the same object) in all translation units.

Historically, while requiring elaborate compilers, C++ has always strived to remain implementable with existing linker technology. This implementation approach requires the compiler to devise a scheme so that an elaborate expression such asS<42>::x can be represented to the linker as a simple symbol, satisfying the linker's syntactic constraints on symbols (length, allowable characters, etc.). This is called name mangling.

A fundamental observation about name mangling is that each name can be mangled with no context knowledge: Regardless of the context of use, an lvalue reference to S<42>::x will be mangled the same way.

Restrictions on types for non-type template parameters

When allowing a user-defined type T as the type of a non-typetemplate-parameter, the most natural restriction seems to be to restrict T to literal types. After all, the compiler already has to be able to deal with values of arbitrary literal types to evaluate constexpr expressions.

That is not enough, though, because the notion of "same type" has to be extended. Currently, 14.4 temp.type reads:

Two template-ids refer to the same class or function if [...] their corresponding non-type template arguments of integral or enumeration type have identical values.

What does it mean for values of a literal type to have "identical values"?

Given these declarations, both S<L(2)>::v andS<L(4)>::v would be valid expressions.

When the user can declare his own operator== for values of type L, we must require that always the sameoperator== ends up being used, and we must require thatoperator== establishes an equivalence relation, at least among the values actually used as template arguments. Of course,operator== must be a constant expression to be eligible for compile-time evaluation.

With these restrictions, consider a declaration ofoperator== like the following

constexpr bool operator==(L x, L y) { return true; }

On a conceptual level, S<L(1)> would be the same type as S<L(2)>, and therefore the compile-time constantsS<L(1)>::v and S<L(2)>::v would necessarily have the same value. Which value to pick is for the compiler to choose. In general, this amounts to picking a unique representative member for each of the different equivalence sets established by operator==. However, the compiler cannot determine these unique members in a context-independent way, because that would require analysis of an arbitrarily complex expression in the user-definedoperator==. Traditional name mangling, however, requires a context-free algorithm to determine the mangled symbol for a name, and thus cannot be made to work here.

If you consider an operator== that always returns "true", thus establishing a single equivalence class, not a convincing example, let us consider a more realistic example exhibiting the same issues. A key observation when coming up with examples is that a user-defined operator== that is semantically different from member-wise built-in equality will necessarily establish fewer equivalence classes than member-wise built-in equality does. It cannot establish more, because built-in equality already considers the full value range for its equivalence, so there are no additional bits of information available to base a decision on.

That said, let us consider a literal sign-magnitude integer type:

struct SMI { constexpr SMI(bool n, unsigned long v) : is_negative(n), value(v) { } bool is_negative; unsigned long value; };

Let us further define that -0 == +0, i.e. operator==looks like this:

constexpr bool operator==(const SMI& l, const SMI& r) { if (l.value == 0) return r.value == 0; return l.is_negative == r.is_negative && l.value == r.value; }

The analysis offered above about the difficulties in establishing a "same type" relationship for L and S now apply to SMI when inspecting the actual value of the is_negative member of any SMI instance. There is just one fewer equivalence class than those established by member-wise built-in equality.

Design sub-options:

The first option needs cross-translation unit analysis capabilities way beyond the features of today's linkers, and beyond a simple call to a user-defined operator== at link time.

The second option seems fragile in that it invites ODR violations down the road, for example when these compile-time constants are used as a non-type template argument in another (unrelated) template.

The third option severely limits the use of literal types with user-defined operator== as types of non-typetemplate-parameters, to an extend that makes option 2 (member-wise equivalence) attractive.

With option 2 "member-wise equivalence", name mangling is feasible, because values of user-defined compound types can be mangled as the values of the subobjects, recursively applied until a built-in type is reached. This procedure is context-free.

Restriction on template argument deduction

Template argument deduction involving non-type template parameters of literal type can only be made to work in a few cases and thus should probably not be attempted at all.

Implementation Experience

None, as far as I know.

Open Issues

(none at this time)

Changes to the Working Draft

These changes are sketches to record the incomplete discussion on arbitrary literal types as non-type template parameters.

Change in 14.1 temp.param paragraphs 4 and 5:

A non-type template-parameter shall have literal type (3.9 basic.types). one of the following (optionally cv-qualified) types:

[ Note: Other types are disallowed either explicitly below or implicitly by the rules governing the form of template-arguments (14.3 tmep.arg). -- end note ]The top-level cv-qualifiers on thetemplate-parameterare ignored when determining its type.For non-type non-reference template-parameters, at each point of instantiation of the template (14.6.4.1 temp.point), overload resolution (13.3.1.2 over.match.oper) is applied to an equality comparison (5.10 expr.eq) of two values of the template-parameter's type T, and the built-in operator or operator function selected shall be the same; no diagnostic required. The operator function selected (if any) shall beconstexpr, and for all values a, b, c of type T used in instantiations of the template, a == b shall be a constant expression (5.19 expr.const), a == a shall yieldtrue, a == b shall yield the same value asb == a, and if a == b and b == c both yield true, a == c shall yieldtrue; no diagnostic required.

Delete 14.1 temp.param paragraph 7:

A non-type template-parameter shall not be declared to have floating point, class, or void type. [ Example:

template class X; // error template<double* pd> class Y; // OK template<double& rd> class Z; // OK

-- end example ]

Change in 14.3.2 temp.arg.nontype paragraph 1:

A template-argument for a non-type, non-templatetemplate-parameter shall be one of:

Delete 14.3.2 temp.arg.nontype paragraphs 2 and 3:

[ Note: A string literal (2.14.5 lex.string) does not satisfy the requirements of any of these categories and thus is not an acceptable template-argument. [ Example:

template<class T, const char* p> class X { / ... / }; X<int, "Studebaker"> x1; // error: string literal as template-argument const char p[] = "Vivisectionist"; X<int,p> x2; // OK

-- end example ] -- end note ]

[ Note: Addresses of array elements and names or addresses of non-static class members are not acceptabletemplate-arguments. [ Example:

template<int* p> class X { }; int a[10]; struct S { int m; static int s; } s; X<&a[2]> x3; // error: address of array element X<&s.m> x4; // error: address of non-static member X<&s.s> x5; // error: &S::s must be used X<&S::s> x6; // OK: address of static member

-- end example ] -- end note ]

Delete 14.3.2 temp.arg.nontype paragraph 5:

The following conversions are performed on each expression used as a non-type template-argument. ...

Alternative 1: use operator==

Add in 8.4.2 dcl.fct.def.default: (warning: rough change)

An explicitly-defaulted member function operator== of class C shall be a non-volatile const member function and shall have a return typebool and a single parameter of type C or of type "reference to const C". The operator function is defined as deleted if C has a variant member. Otherwise, an explicitly-defaulted member operator==is defined to compare for equality (5.10 expr.eq, 13.5.2 over.binary) the corresponding values of each base class and non-static data member in the lexical order of appearance in the class definition; it returns true if each subobject comparison yields true, and false otherwise.

An explicity-defaulted non-member function operator== shall have a return type bool and two parameters of the same type T where T is a class or enumeration type or a reference to const such a type. If the parameters have enumeration type or reference to const enumeration type, the explicity-defaulted operator== returns true if the built-in equality comparison of the promoted type yields true, and false otherwise. If the parameters have class type or reference to const class type, the explicitly-defaulted operator== has the same definition as-if it were a member operator of the class type.

Change in 14.4 temp.type paragraph 1:

Two template-ids refer to the same class or function if

Change in 14.8.2.5 temp.deduct.type paragraph 8:

A template type argument T, a template template argument TT or a template non-type argument i whosetemplate-parameter's type uses the built-in equality operator (14.1 temp.param) can be deduced if P and A have one of the following forms:

Alternative 2: use memberwise equality

Add in 8.4.2 dcl.fct.def.default:

Two values of the same non-union type T are memberwise equal if

Acknowledgements

Thanks to Richard Smith for some of the more annoying issues with allowing a user-defined operator==.