mangling for constrained templates

[zygoloid]

p0734r0 added new forms of overloadable declaration that we need to mangle. For instance, we now need to distinguish:

template<typename T> concept A = ...
template<typename T> concept B = ...
template<A T> void f(T); // f1
template<B T> void f(T); // f2
template<typename T> requires A<T> void g(T); // g1
template<typename T> requires B<T> void g(T); // g2

It is permissible (but not necessary) for the mangling of f1 and g1 to be the same (other than the name).

(There are also requires-clauses on non-template functions, but I don't believe there is any need to mangle those since at most one such function can have its requires-clause evaluate to true, and the rest are never emitted.)

As a general model, I suggest we include "extra information" about a template-parameter (for a function template -- we don't need this for non-overloadable templates) as a prefix on the template-arg mangling. (We should also consider extending this to the case where the the template parameter is a template template parameter and the template argument does not have an identical template-parameter-list, to handle the case described in http://sourcerytools.com/pipermail/cxx-abi-dev/2014-December/002791.html)

I suggest we affix the constraint expression from the requires-clause (if any) to the template-args, and do not perform any expansion or canonicalization of the as-written form of the template declaration. Strawman mangling suggestion:

<template-arg> ::= C <concept name> <template-arg>
<template-args> ::= I <template-arg>+ Q <requires-clause expr> E

Example:

template<A T, B U> requires C<T, U> void f();
f<int, 3>(); // _Z1fIC1AiC1BLi3EQ1CIT_T0_EEvv

[rjmccall]

Is your statement about non-template functions true in the case that not all such functions are declared in the same translation unit? Or is that impossible because such functions must be defined within templates?

[rjmccall]

Does the standard consider these to be different declarations for the purposes of the ODR?

  template <A T> void foo();
  template <class T> requires A<T> void foo();

Oh, I see you answered that: it's unspecified.

I feel like it would be responsible for us to do some minimal canonicalization here.

[thiagomacieira]

Similarly, does it consider these two to be two different functions, even if both concepts are exactly the same (same requirements, literally)?

  template<typename T> concept A = ...
  template<typename T> concept B = ...
  template<A T> void f(T); // f1
  template<B T> void f(T); // f2

If that is the case, trying to call f with any argument that matches the concepts is an ambiguous overload, correct?

But if I split the two in two different translation units, could I call two different functions and not violate ODR?

And what happens if two different TUs have differing concepts that have the same name? ODR violation?

[daveedvdv]

On Jul 25, 2017, at 11:21 PM, John McCall ***@***.***> wrote: Does the standard consider these to be different declarations for the purposes of the ODR? template void foo(); template requires A void foo();

Yes (the draft standard, that is). Daveed

[daveedvdv]

On Jul 26, 2017, at 12:01 AM, Thiago Macieira ***@***.***> wrote: Similarly, does it consider these two to be two different functions, even if both concepts are exactly the same (same requirements, literally)? template concept A = ... template concept B = ... template void f(T); // f1 template void f(T); // f2

I’m guessing that f1 and f2 meant to be constrained with A and B respectively, and that those two concepts were meant to be defined identically?

If that is the case, trying to call f with any argument that matches the concepts is an ambiguous overload, correct? But if I split the two in two different translation units, could I call two different functions and not violate ODR?

That’s my understanding of the proposal as adopted into the working draft (which incorporates P0717, which is a change in that regard compared to the Concepts TS). Daveed

[thiagomacieira]

Please note that your reply removed everything between the angle brackets, so you removed important information. But to be clear, I'm asking:
a.cpp:

template<typename T> concept A = { something here; };
template<A T> void f(T) {}

b.cpp:

template<typename T> concept B = { something here; };
template<B T> void f(T) {}

Specifically, aside from the change of A to B, the rest is exactly the same, literally so for the concept declaration. In other words: what defines a concept: the name or the requirements?

And as a corollary, in c.cpp:

template<typename T> concept A = { something very different here; };
template<A T> void f(T) {}

If concepts are identified by name, then the above is must be ODR violation (no diagnostic required). Is this understanding correct?

[daveedvdv]

On Jul 26, 2017, at 11:15 AM, Thiago Macieira ***@***.***> wrote: Please note that your reply removed everything between the angle brackets,

Ah, the angle brackets did not show up on my end. Probably some markup gobbling along the way...

so you removed important information. But to be clear, I'm asking: a.cpp: template<typename T> concept A = { something here; }; template<A T> void f(T) {} b.cpp: template<typename T> concept B = { something here; }; template<B T> void f(T) {} Specifically, aside from the change of A to B, the rest is exactly the same, literally so for the concept declaration. In other words: what defines a concept: the name or the requirements?

What defines the concept is the concept definition (including the name and its initializer). I _think_ you meant to ask how equivalence of constraints on function templates is specified: In terms of concept names or the underlying expressions? The answer to that question is that it’s not quite either of those two (and “equivalence” is defined differently depending on context). See: http://wg21.link/p0717 for details. For your example, that means that the two declarations of f declare distinct templates.

And as a corollary, in c.cpp: template<typename T> concept A = { something very different here; }; template<A T> void f(T) {} If concepts are identified by name, then the above is must be ODR violation (no diagnostic required). Is this understanding correct?

I believe concepts have linkage, and therefore, yes, that would be an ODR violation (even without the declaration of f). Daveed

[thiagomacieira]

I believe concepts have linkage, and therefore, yes, that would be an ODR violation (even without the declaration of f).

If they have linkage, we need to mangle that too.

Why do they have to have linkage?

[rjmccall]

It looks like concepts with the same name are required to be defined the same way in different translation units. I don't know if there's a way of giving a concept "linkage" per se.

[thiagomacieira]

Something like IFNDR then.

[rjmccall]

It looks like Daveed's statement is correct: two template-heads (template parameter list + requires clause) are equivalent only if they are written in exactly the same way, but they are functionally equivalent if they accept the same set of template arguments. So we are allowed but not required to treat those as distinct templates. (Exactly like Richard said.)

[rjmccall]

I feel like people would probably be surprised by trivial differences breaking ABI, but on the other that's already true of function templates, and it mostly doesn't matter because:

• depending on function pointer equality is extremely rare (and foolish) and
• depending on the address/uniqueness of a static variable within a function template is rare, albeit less so (and most justifiable) than depending on function pointer equality.

So Richard's idea of not doing any canonicalization is appealing. But if anything about concepts requires us to mangle template-heads for something besides identifying a function template, we'll be in more trouble.

[tahonermann]

(There are also requires-clauses on non-template functions, but I don't believe there is any need to mangle those since at most one such function can have its requires-clause evaluate to true, and the rest are never emitted.)

For tool vendors such as Synopsys/Coverity, having different mangled names for each distinct declaration is useful, even if only one of them can ever be "activated" within a TU. However, this is a niche requirement and we can resort to vendor extensions (as we have in other cases such as "conflicting" inline friend function definitions in different class templates) if including mangling would be at all problematic for other implementors.

[zygoloid]

Is your statement about non-template functions true in the case that not all such functions are declared in the same translation unit?

The wording in this area is unclear, and we have an open issue on it. Example:

// translation unit 1
struct A {};
struct B;
template<typename T> concept bool Complete = requires { sizeof(T); };
inline void f() requires Complete<A> {};
inline void f() requires Complete<B> {};

// translation unit 2
struct A;
struct B {};
template<typename T> concept bool Complete = requires { sizeof(T); };
inline void f() requires Complete<A> {};
inline void f() requires Complete<B> {};

It's not clear whether this program is valid, or (if valid) what it means. And the same situation can arise even within a TU:

struct A;
struct B;
template<typename T> concept bool Complete = requires { sizeof(T); };
inline void f() requires !Complete<A> || Complete<B> {}; // #1
inline void f() requires Complete<A> && !Complete<B> {}; // #2
void g() { f(); } // calls #1
struct A {};
void h() { f(); } // calls #2
struct B {};
void i() { f(); } // calls #1

Or is that impossible because such functions must be defined within templates?

There is no such requirement... yet.

If nothing else, I'd say the underspecification in this area and the likelihood of changes suggests that we shouldn't commit to a mangling for this construct yet.

[rjmccall]

Interesting, alright.

[saarraz]

Hi, trying to bring this back to life now that we have a more final version of the language feature.
@zygoloid were the issues mentioned here addressed since?

Also, we're going to need some way to mangle requires-expressions (which should be less problematic, I believe?).

[rjmccall]

It's not conceptually problematic, but the parameter clause does make it non-trivial to invent a mangling for.

[zygoloid]

See also #47, in which I gave a suggestion for when to include a <template-param-decl> as part of a <template-arg> mangling, and #85, which defines <template-param-decl> for use in <lambda-sig>.

[dfrib]

(There are also requires-clauses on non-template functions, but I don't believe there is any need to mangle those since at most one such function can have its requires-clause evaluate to true, and the rest are never emitted.)

As per US115 of P2103R0 hidden non-template friends may also use requires-clauses:

struct Base {};

template<int N>
struct S : public Base {
    friend int foo(Base&) requires (N == 1) { return 1; }
    friend int foo(Base&) requires (N == 2) { return 3; }
};

int main() {
    S<1> s1{};
    S<2> s2{};  // GCC & MSVC: re-definition error of 'foo'
    auto const foo1 = foo(s1); // #1
    auto const foo2 = foo(s2); // Clang error: definition with same mangled name as another definition
} 

On a tangent: is it well-specified whether such friends are late-instantiated only for the enclosing class template specializations for which its requires-clause is fulfilled? Afaict all three compilers are wrong here, but is the program well-formed or ill-formed due to an ambiguity at #1?

[rjmccall]

Well, that's an exciting special case.

Such a constrained friend function or function template declaration does not declare the same function or function template as a declaration in any other scope.

That's fairly clear: GCC and MSVC are wrong because these are not redeclarations, and Clang is wrong because this is well-formed and we aren't allowed to reject it because of a mangling conflict. The only viable implementation path I can see, given that nothing in the standard prevents these friend declarations from otherwise matching perfectly in signatures and requires-clauses, is to mangle the declaring class for these friends. Note that mangling the requires-clause is not sufficient: we cannot rely on ambiguity to force there to only be a single friend declaration with satisfied constraints because the instantiations could be split between TUs.

Mangling the declaring class shouldn't impose a significant symbol size penalty because in non-perverse code the declaring class will be mentioned in the function signature, so substitution will apply. Unfortunately, I don't think we can turn that into a constraint which would let us avoid including the mangling.

On a tangent: is it well-specified whether such friends are late-instantiated only for the enclosing class template specializations for which its requires-clause is fulfilled?

There doesn't seem to be a concept in the standard of only instantiating functions whose requires-clauses are satisfied; such functions always exist and are weeded out as non-viable during overload resolution. But no, the current wording seems to just not cover what happens when instantiating a friend function:

The type-constraints and requires-clause of a template specialization or member function are not instantiated along with the specialization or function itself, even for a member function of a local class; substitution into the atomic constraints formed from them is instead performed as specified in [temp.constr.decl] and [temp.constr.atomic] when determining whether the constraints are satisfied or as specified in [temp.constr.decl] when comparing declarations.

Non-template friend functions are neither template specializations nor members.

Afaict all three compilers are wrong here, but is the program well-formed or ill-formed due to an ambiguity at #1?

I don't see why there would be an ambiguity.

Do you have any interest in writing this up? We'll need to pick some way to mangle something as a friend from a particular declaring class, and it can't just be the normal member mangling.

CC @zygoloid

[zygoloid]

The only viable implementation path I can see, given that nothing in the standard prevents these friend declarations from otherwise matching perfectly in signatures and requires-clauses, is to mangle the declaring class for these friends.

That's the implementation strategy we had in mind when this was discussed in committee. I agree that we can't use the normal member mangling here, because a friend and a member can have the same signature.

I think the mangling needs the fully-qualified mangled name of the class and only a simple identifier for the function; it's not sufficient to mangle the fully-qualified name of the function and only a simple identifier for the class because the class could be a template specialization or a local class. So modeling the friend as if it were a member, with some disambiguator character(s) added to distinguish the cases, makes sense to me.

Perhaps we could allow a marker for this prior to the final <unqualified-name> in a <nested-name>? The mangling grammar doesn't make that convenient to express, but I think it could be something like:

-    <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
+    <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> [F] <unqualified-name> E

...

     <template-prefix> ::= <template unqualified-name>           # global template
-                      ::= <prefix> <template unqualified-name>  # nested template
+                      ::= <prefix> [F] <template unqualified-name>  # nested template

[rjmccall]

I think that should work, since the namespace of a friend function definition is always derivable from the class. And I like that it maintains a common prefix with true class members.

[dfrib]

Do you have any interest in writing this up? We'll need to pick some way to mangle something as a friend from a particular declaring class, and it can't just be the normal member mangling.

Sorry for the late reply, I forgot about this.

I would be happy to, as an instructive ABI journey, start from @zygoloid's proposal above and submit a PR. If so, should I open an separate issue for this isolated case?

[erichkeane]

Was this ever merged into the ABI? was 'F' chosen as the differentiator here?

Is the solution here to ALWAYS mangle 'friend' functions as a member function? Do we fear that this is an ABI break (since the name is changing?), or is it that the definition is 'inline' to the class, that the name change cannot break ABI?

[Arcoth]

(There are also requires-clauses on non-template functions, but I don't believe there is any need to mangle those since at most one such function can have its requires-clause evaluate to true, and the rest are never emitted.)

Why at most one? What about

    template<int I> concept C = true;

    template <typename T = int> struct A {
        int f() requires C<42> { return 0; }
        long f() requires true {return 0; }
    };
    
    int x = (A<>{}.*((int(A<>::*)())&A<>::f))();
    
    int y = (A<>{}.*((long(A<>::*)())&A<>::f))();

I don't see this being prohibited by current wording. Also, the "at most one" part is contradicted by e.g. https://eel.is/c++draft/temp.spec#temp.inst-example-10. Clearly the idea was that such templated functions would not be distinguishable during overload resolution, so only one could be instantiated per enclosing specialization, but if we distinguish via the return type which is not mangled AFAICS, the problem returns.

[zygoloid]

(There are also requires-clauses on non-template functions, but I don't believe there is any need to mangle those since at most one such function can have its requires-clause evaluate to true, and the rest are never emitted.)

Why at most one?

I'm not sure whether the rules here changed between when I wrote my initial comment and the final C++20 standard, but in any case, I agree; we do need to mangle trailing requires clauses for non-template functions; they are part of the signature.

[zygoloid]

Use of C is unwise due to collisions with complex types. Revised suggestion follows; this is intended to replace prior suggestions on this issue, and augment the rules proposed in #47.

Type constraints are mangled following the source syntax:

• <type-constraint> ::= <name>

A type constraint C or C<> is mangled as the name of the concept C. A type constraint C<Args> with non-empty Args is mangled as the name of the hypothetical template specialization C<Args>, even though it would result in a satisfaction check for C<T, Args> for some T. For example, 12IsBiggerThanIiE or N3Lib11IsContainerIiEE.

• <template-param-decl> ::= Tk <type-constraint> # constrained type parameter

Constrained type template parameters use a new mangling instead of Ty. This applies not only in the cases where we currently mangle template parameters (for example, in the signature of a lambda), but also in #47 step 3: the natural template parameter for any template argument is always unconstrained, so this also applies in every <template-arg> where the parameter is constrained and the template is overloadable:

template<C T> void f() {}
// _Z1fITk1CiEvv
template void f<int>();

• <template-param-decl> ::= Tt <template-param-decl>* [Q <constraint-expression>] E

Template template parameters can have requires-clauses, and function templates can be overloaded on the requires-clauses of their template template parameters, so the requires-clause is included in the mangling of the template template parameter.

When constrained auto is used to declare an abbreviated function template, the language rules permit the function template to be redeclared with an explicit template parameter, so the abbreviated function template is rewritten to the non-abbreviated form prior to mangling:

void f(C auto) {}
// _Z1fITk1CiEvT_
template void f<int>(int);

When a constrained placeholder type appears in contexts where it is not rewritten to a template parameter, it is mangled with its constraint, instead of with the Da / Dc mangling:

• <type> ::= Dk <type-constraint> # constrained auto
• <type> ::= DK <type-constraint> # constrained decltype(auto)

For example:

template<C auto N> void f() {}
// _Z1fITnDk1CLi5EEvv
template void f<5>();

template<typename T> void g(decltype(new C auto(T())) x) {}
// _Z1gIiEvDTnw_Dk1CpicvT__EEE
template void g<int>(int*);

A requires-clause that follows a template-parameter-list is appended to the corresponding <template-args> when mangling an overloadable template, as defined in #47.

• <template-args> ::= I <template-arg>+ [Q <constraint-expression>] E

A trailing requires-clause is mangled as a suffix on the encoding of a function:

• <encoding> ::= <function name> <bare-function-type> [Q <constraint-expression>]

This applies to all cases where a trailing requires-clause is permitted: function template specializations, members of templated classes, and friends of templated classes.

Non-template friend function declarations with trailing requires-clauses and friend function templates whose constraints involve enclosing template parameters have special linkage rules: they are distinct from declarations in other scopes, and instead behave like class members for linkage purposes. We call these member-like constrained friends. Member-like constrained friends are mangled as if they were class member functions, with an F preceding their unqualified name:

• <unqualified-name> ::= F <source-name> # member-like constrained friend
• <unqualified-name> ::= F <operator-name> # member-like constrained friend

Constrained lambdas have two places where requires-clauses can appear: after the template parameter list, and after the function parameter list. Both are mangled, in lexical order:

• <lambda-sig> ::= <template-param-decl>* [Q <early constraint-expression>] <parameter type>+ [Q <late constraint-expression>]

Concept-ids are always mangled as unresolved-names, never as L_Z<encoding>E, even when none of the template arguments is instantiation-dependent. We can't use <encoding> when arguments are instantiation-dependent, because T_ references within an <encoding> never refer to enclosing parameters. (But see #38 for a pre-existing issue with unresolved-names.)

Substitution is never performed into <constraint-expression>s before they are mangled, so they can refer to all levels of enclosing template parameters. In a <constraint-expression>, T[<n>]_ refers to the outermost enclosing template parameter list (even if it belongs to an enclosing class template specialization), TL<n>__ refers to the next innermost level, and so on. A <constraint-expression> is otherwise mangled the same as any other <expression>.

• <constraint-expression> ::= <expression>

[zygoloid]

We also need to mangle requires-expressions. Suggestion:

• <expression> ::= rq <requirement>+ E # requires { ... }
• <expression> ::= rQ <bare-function-type> _ <requirement>+ E # requires (...) { ... }

Within an rQ mangling, an extra depth of <function-param> is in scope, referring to the parameters of the requires-expression. Within an rq mangling, no extra depth of <function-param> is in scope, so fp_ refers to an enclosing function parameter. For consistency, an empty parameter list (requires () { ... } or requires (void) { ... }) is mangled as rQv_ not rQ_.

Requirements are mangled as follows:

• <requirement> ::= X <expression> [N] [R <type-constraint>] # simple-requirement or compound-requirement
• <requirement> ::= T <type> # type-requirement
• <requirement> ::= Q <constraint-expression> # nested-requirement

The requirements expr; and {expr}; are functionally equivalent and have the same mangling. Expression requirements are suffixed with N for a noexcept requirement and with R <type-constraint> for a return-type-requirement.

TODO: requires-expressions can appear outside of constraint-expressions in the signature of a function or function template. It is unclear how to mangle these, as we may have performed substitution into only a subset of the requirements within them, and mangling the original expression can lead to collisions (eg, two friend templates declared in different classes can have requires-expressions in their signatures that look the same prior to substitution but different afterwards). This question is pending committee feedback.

[zygoloid]

@jicama @rjmccall @jhsedg Your thoughts on the above would be appreciated. It seems important that we settle an ABI for the C++20 additions fairly soon, given the increasing levels of adoption.

[jicama]

When constrained auto is used to declare an abbreviated function template, the language rules permit the function template to be redeclared with an explicit template parameter, so the abbreviated function template is rewritten to the non-abbreviated form prior to mangling:

void f(C auto) {}
// _Z1fITk1CiEvT_
template void f<int>(int);

But they're not always equivalent because of the ordering of constraints in https://eel.is/c++draft/temp.constr.decl#3.3 specifying that the constraints from a requires-clause following the template parameters are checked before the constraints from type-constraints in the parameter-type-list. So e.g. here the ordering is important:

#include <type_traits>
template <class T> concept HasFoo = requires { typename T::foo; };
template <class T> concept NotVoid = !std::is_void<T>::value;
template <class T> struct A { T t; };
template <class T> requires NotVoid<T> void f(HasFoo auto);
template <class T, class U> void f(...);
template <class T> struct B { T t; };
template <class T, HasFoo U> requires NotVoid<T> void g(U);
template <class T, class U> void g(...);
int main()
{
  f<void,A<void>>(42); // OK, calls f(...)
  g<void,B<void>>(42); // concept checking causes bad instantiation of B<void>
}

I suppose we could do the rewriting you describe if there is no requires-clause on the template parameter list, but if there is, append the constraint-expressions from the parameter list to the requires-clause with && ?

My inclination would be to always mangle the combined constraint-expression from the above section rather than try to use a shorthand form for constrained type parameters, but I'm willing to go along with the Tk mangling for compactness.

[zygoloid]

When constrained auto is used to declare an abbreviated function template, the language rules permit the function template to be redeclared with an explicit template parameter, so the abbreviated function template is rewritten to the non-abbreviated form prior to mangling:

void f(C auto) {}
// _Z1fITk1CiEvT_
template void f<int>(int);

But they're not always equivalent because of the ordering of constraints in https://eel.is/c++draft/temp.constr.decl#3.3 specifying that the constraints from a requires-clause following the template parameters are checked before the constraints from type-constraints in the parameter-type-list.

The two declarations are always equivalent, per https://eel.is/c++draft/dcl.fct#22.sentence-2, so we are required to mangle them the same way. I agree that they have different behavior, but that's a CWG problem (mailed to the core reflector [edit: now CWG2802]) not an ABI problem. I think probably CWG1321 would specify the behavior here: we would use the associated constraints from the first declaration of the template (though CWG1321 predates concepts, and we seem to have somehow lost the normative changes there, and it's not clear how they'd work with modules...).