Allowing arbitrary literal types for non-type template parameters

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<C c>
struct X {
  int array[c.v];
};

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

Design Considerations

"same type" and name mangling

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

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

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

Current rules restrict the type of a non-type template-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> and S<+0> are required to be the same type.

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

  template<int n>
  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 as S<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-type template-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"?

• Option 1: use operator== on T
• Option 2: use member-wise equivalence

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

  template<L x>
  struct S
  {
    static constexpr int v = x.v;
  };

Given these declarations, both S<L(2)>::v and S<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 same operator== ends up being used, and we must require that operator== 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 of operator== 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 constants S<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-defined operator==. 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;
};

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:

• require the compiler to pick a unique instantiation, consistent across all translation units
• each mention of the type yields an unspecified value
• such use is undefined

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-type template-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

Open Issues

Changes to the Working Draft

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:

• integral or enumeration type,
• pointer to object or pointer to function,
• lvalue reference to object or lvalue reference to function,
• pointer to member,
• std::nullptr_t.

[ 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 the template-parameter are 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 be constexpr, 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 yield true, a == b shall yield the same value as b == a, and if a == b and b == c both yield true, a == c shall yield true; no diagnostic required.

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

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

-- end example ]

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

• for a non-type non-reference template-parameter of integral or enumeration type, a converted constant expression (5.19 expr.const) of the type of the template-parameter; or
• the name of a non-type template-parameter; or
• an address constant expression (5.19 expr.const) a constant expression (5.19) that designates the address of an object with static storage duration external or internal linkage or a function with external or internal linkage, including function templates and function template-ids but excluding non-static class members, expressed (ignoring parentheses) & id-expression, except that the & may be omitted if the name refers to a function or array and shall be omitted if the corresponding template-parameter is a reference; or
• a constant expression that evaluates to a null pointer value (4.10 conv.ptr); or
• for a non-type reference template-parameter, a reference constant expression.
• a constant expression that evaluates to a null member pointer value (4.11 conv.mem); or
• a pointer to member expressed as described in 5.3.1.

[ 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 acceptable template-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 ]

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

Alternative 1: use operator==

An explicitly-defaulted member function operator== of class C shall be a non-volatile const member function and shall have a return type bool 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.

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

• ...
• the values of their corresponding non-type non-reference template arguments of integral or enumeration literal type compare equal (5.10 expr.eq) or operator== (13.5.2 over.binary) returns true (14.1 temp.param) have identical values and
• their corresponding non-type template-arguments of pointer type refer to the same external object or function or are both the null pointer value and
• their corresponding non-type template-arguments of pointer-to-member type refer to the same class member or are both the null member pointer value and
• their corresponding non-type template-arguments of reference type refer to the same external object or function and
• ...

A template type argument T, a template template argument TT or a template non-type argument i whose template-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

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

• for T a scalar type, the built-in equality comparison (5.10 expr.eq) of the promoted values (4.5 conv.prom) yields true, or
• for T a reference type, both references refer to the same object or function, or
• for T an array type, each corresponding element is memberwise equal, or
• for T a class type, each base class and non-variant non-static data member is memberwise equal.

Acknowledgements