Mistake in C++ ABI substitution rules?

Mistake in C++ ABI substitution rules?

[Stan Shebs]

One of our tasks in migrating Darwin / Mac OS X to use GCC 3.x is
to provide a way to load I/O drivers written in C++ and compiled
with GCC 2.95.  (Yeah yeah, bad idea, but the deed is done, and
alternative is to compile the kernel's I/O subsystem with 2.95
forever, I'll work hard to avoid that fate.)

Anyway, to translate the symbols we have a homemade 2.95 compat
demangler (written using a spec I handed to the kernel hacker,
poor guy) feeding into a remangler written using the spec at
http://www.codesourcery.com/cxx-abi/abi.html#mangling.  So far
so good, we have something that actually does the right thing
most of the time.  However, there is a troublesome point in the
substitution rules for the new C++ ABI, where it says 

"Logically, the substitutable components of a mangled name are
considered left-to-right, components before the composite structure
of which they are a part. If a component has been encountered
before, it is substituted as described below. This decision is
independent of whether its components have been substituted,
so an implementation MAY OPTIMIZE by considering large structures
for substitution before their components. If a component has not
been encountered before, its mangling is identified, and it is
added to a dictionary of substitution candidates. No entity is
added to the dictionary twice." (emphasis mine)

This sure sounds like it's allowing different compilers to mangle
names differently, by choosing to substitute in different ways.
And indeed we had to determine 3.x's behavior empirically.  But
this seems like a fatal blow to the goal of an ABI that could
allow object files from different compilers to be linked together,
or to link code from two different 3.x versions of GCC.

Am I missing something here, or is there an unresolved omission
in the name mangling rules of the C++ ABI?

Stan

Re: Mistake in C++ ABI substitution rules?

[Carlo Wood]

In the past I reported a problem with the way g++ 3.x mangles
names, related to substitutions.  It does not handle the substitutions
the way it should (according to the ABI).

The reponse was that the ABI would not be changed when it
didn't break anything the way it was.  So yes, it seems that the
mangling is still compiler specific and the choice is to leave it
that way.

The comment that I wrote in the code of my demangler (I wrote one too
thus), is:

// <type> ::= <builtin-type>                                  # Starts with a lower case character != r.
//        ::= <function-type>                                 # Starts with F
//        ::= <class-enum-type>                               # Starts with N, S, C, D, Z, a digit or a lower case character.
//                                                            #   since a lower case character would be an operator name, that would
//                                                            #   be an error.  The S is a substitution or St (::std::).  A 'C' would
//                                                            #   be a constructor and thus also an error.
//        ::= <template-param>                                # Starts with T
//        ::= <substitution>                                  # Starts with S
//        ::= <template-template-param> <template-args>       # Starts with T or S, equivalent with the above.
//
//        ::= <array-type>                                    # Starts with A
//        ::= <pointer-to-member-type>                        # Starts with M
//        ::= <CV-qualifiers> <type>                          # Starts with r, V or K
//        ::= P <type>   # pointer-to                         # Starts with P
//        ::= R <type>   # reference-to                       # Starts with R
//        ::= C <type>   # complex pair (C 2000)              # Starts with C
//        ::= G <type>   # imaginary (C 2000)                 # Starts with G
//        ::= U <source-name> <type>                          # vendor extended type qualifier, starts with U
//
// <template-template-param> ::= <template-param>
//                           ::= <substitution>
//
// My own analysis of how to decode qualifiers:
//
// F is a <function-type>, <T> is a <builtin-type>, <class-enum-type>, <template-param> or <template-template-param> <template-args>.
// <Q> represents a series of qualifiers (not G or C).
// <C> is an unqualified type.  <R> is a qualified type.
// <B> is the bare-function-type without return type.  <I> is the array index.  //
//                                                            Substitutions:
// <Q>M<Q2><C>F<R><B>E        ==> R (C::*Q)B Q2               "<C>", "<Q2><C>", "F<R><B>E" (<R> and <B> recursive), "M<Q2><C>F<R><B>E".
// <Q>F<R><B>E                ==> R (Q)B                      "<R>", "<B>" (<B> recursive) and "F<R><B>E".
// <Q>G<T>                    ==> imaginary T Q               "<T>", "G<T>" (<T> recursive).
// <Q>C<T>                    ==> complex T Q                 "<T>", "C<T>" (<T> recursive).
// <Q><T>                     ==> T Q                         "<T>" (<T> recursive).
//
// where Q is any of:
//
// <Q>P               ==> *Q                                  "P..."
// <Q>R               ==> &Q                                  "R..."
// <Q>[K|V|r]+        ==> [ const| volatile| restrict]+Q      "KVr..."
// <Q>U<S>            ==>  SQ                                 "U<S>..."
// A<I>               ==>  [I]                                "A<I>..." (<I> recursive).
// <Q>A<I>            ==>  (Q) [I]                            "A<I>..." (<I> recursive).
// <Q>M<C>            ==> C::*Q                               "M<C>..." (<C> recursive).
//
// A <substitution> is handled with an input position switch during which new substitutions are
// turned off.  Because recursive handling of types (and therefore the order in which substitutions
// must be generated) must be done left to right, but the generation of Q needs processing right to left,
// substitutions per <type> are generated by reading the input left to right and marking the starts of
// all substitutions only - implicitly finishing them at the end of the type.  Then the output and real
// substitutions are generated.
//
// The ABI specifies for pointer-to-member function types the format <Q>M<T>F<R><B>E.  In other words,
// the qualifier <Q2> (see above) is implicitely contained in <T> instead of explicitly part of the M
// format.  I am convinced that this is a bug in the ABI.  Unfortunately, this is how we have to
// demangle things as it has a direct impact on the order in which substitutions are stored.
// This ill-formed design results in rather ill-formed demangler code too however :/


On Tue, Feb 19, 2002 at 02:42:02PM -0800, Stan Shebs wrote:
> One of our tasks in migrating Darwin / Mac OS X to use GCC 3.x is
> to provide a way to load I/O drivers written in C++ and compiled
> with GCC 2.95.  (Yeah yeah, bad idea, but the deed is done, and
> alternative is to compile the kernel's I/O subsystem with 2.95
> forever, I'll work hard to avoid that fate.)
> 
> Anyway, to translate the symbols we have a homemade 2.95 compat
> demangler (written using a spec I handed to the kernel hacker,
> poor guy) feeding into a remangler written using the spec at
> http://www.codesourcery.com/cxx-abi/abi.html#mangling.  So far
> so good, we have something that actually does the right thing
> most of the time.  However, there is a troublesome point in the
> substitution rules for the new C++ ABI, where it says 
> 
> "Logically, the substitutable components of a mangled name are
> considered left-to-right, components before the composite structure
> of which they are a part. If a component has been encountered
> before, it is substituted as described below. This decision is
> independent of whether its components have been substituted,
> so an implementation MAY OPTIMIZE by considering large structures
> for substitution before their components. If a component has not
> been encountered before, its mangling is identified, and it is
> added to a dictionary of substitution candidates. No entity is
> added to the dictionary twice." (emphasis mine)
> 
> This sure sounds like it's allowing different compilers to mangle
> names differently, by choosing to substitute in different ways.
> And indeed we had to determine 3.x's behavior empirically.  But
> this seems like a fatal blow to the goal of an ABI that could
> allow object files from different compilers to be linked together,
> or to link code from two different 3.x versions of GCC.
> 
> Am I missing something here, or is there an unresolved omission
> in the name mangling rules of the C++ ABI?
> 
> Stan

-- 
Carlo Wood <carlo@alinoe.com>

Re: Mistake in C++ ABI substitution rules?

[Joe Buck]

> In the past I reported a problem with the way g++ 3.x mangles
> names, related to substitutions.  It does not handle the substitutions
> the way it should (according to the ABI).
> 
> The reponse was that the ABI would not be changed when it
> didn't break anything the way it was.  So yes, it seems that the
> mangling is still compiler specific and the choice is to leave it
> that way.

The possibilility was left open to fix any errors in the ABI for 3.1
(since we have to break compatibility for the standard library anyway),
but we didn't want to break compatibility between 3.0.x releases.

Perhaps the 3.1 release is a good place to fix problems such as the ones
Carlo is pointing out, but I'm not certain.

Does anyone know what other compilers besides gcc purport to implement
the standard ABI, and how they handle the cases Carlo is talking about?

Re: Mistake in C++ ABI substitution rules?

[Mark Mitchell]

Stan --

  I've forwarded your mail to the C++ ABI mailing list:

    cxx-abi-dev@codesourcery.com

--On Tuesday, February 19, 2002 02:42:02 PM -0800 Stan Shebs 
<shebs@apple.com> wrote:

> One of our tasks in migrating Darwin / Mac OS X to use GCC 3.x is
> to provide a way to load I/O drivers written in C++ and compiled
> with GCC 2.95.  (Yeah yeah, bad idea, but the deed is done, and
> alternative is to compile the kernel's I/O subsystem with 2.95
> forever, I'll work hard to avoid that fate.)
>
> Anyway, to translate the symbols we have a homemade 2.95 compat
> demangler (written using a spec I handed to the kernel hacker,
> poor guy) feeding into a remangler written using the spec at
> http://www.codesourcery.com/cxx-abi/abi.html#mangling.  So far
> so good, we have something that actually does the right thing
> most of the time.  However, there is a troublesome point in the
> substitution rules for the new C++ ABI, where it says
>
> "Logically, the substitutable components of a mangled name are
> considered left-to-right, components before the composite structure
> of which they are a part. If a component has been encountered
> before, it is substituted as described below. This decision is
> independent of whether its components have been substituted,
> so an implementation MAY OPTIMIZE by considering large structures
> for substitution before their components. If a component has not
> been encountered before, its mangling is identified, and it is
> added to a dictionary of substitution candidates. No entity is
> added to the dictionary twice." (emphasis mine)

I think that "may" should be "must".

Thoughts?

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

Re: Mistake in C++ ABI substitution rules?

[Joe Buck]

> > "Logically, the substitutable components of a mangled name are
> > considered left-to-right, components before the composite structure
> > of which they are a part. If a component has been encountered
> > before, it is substituted as described below. This decision is
> > independent of whether its components have been substituted,
> > so an implementation MAY OPTIMIZE by considering large structures
> > for substitution before their components. If a component has not
> > been encountered before, its mangling is identified, and it is
> > added to a dictionary of substitution candidates. No entity is
> > added to the dictionary twice." (emphasis mine)

Mark writes:
> I think that "may" should be "must".

If all the folks who implemented the ABI interpreted it that way, we
have no problem with s/may/must/.  But if some did not, then we don't
have a portable ABI, someone will have to make changes.

Re: Mistake in C++ ABI substitution rules?

[Mark Mitchell]

> If all the folks who implemented the ABI interpreted it that way, we
> have no problem with s/may/must/.  But if some did not, then we don't
> have a portable ABI, someone will have to make changes.

I strongly believe that all vendors have implemented the substitution
semantics.  I know that Intel, GCC, and HP have all implemented these
rules.

Like many things about the ABI, the name-mangling rules are not nearly
as clear as I would like.  Whenever I say something like this, Jason
reminds me that I could fix the spec, and then I find myself
insufficiently motivated.

Unfortunately, the little unclarities mean that corner cases do come
up where things are not compatible.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Jim Dehnert]

It was certainly intended as must.  My mistake, probably.  As Joe
points out, it's not portable otherwise, so there's not much choice.

Jim


Joe Buck wrote:
> 
> > > "Logically, the substitutable components of a mangled name are
> > > considered left-to-right, components before the composite structure
> > > of which they are a part. If a component has been encountered
> > > before, it is substituted as described below. This decision is
> > > independent of whether its components have been substituted,
> > > so an implementation MAY OPTIMIZE by considering large structures
> > > for substitution before their components. If a component has not
> > > been encountered before, its mangling is identified, and it is
> > > added to a dictionary of substitution candidates. No entity is
> > > added to the dictionary twice." (emphasis mine)
> 
> Mark writes:
> > I think that "may" should be "must".
> 
> If all the folks who implemented the ABI interpreted it that way, we
> have no problem with s/may/must/.  But if some did not, then we don't
> have a portable ABI, someone will have to make changes.

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Martin von Loewis]

Mark Mitchell <mark@codesourcery.com> writes:

> I think that "may" should be "must".

I think the intention was always that you MUST apply compression if
possible. Without that, there is no chance of interoperable mangling.

Regards,
Martin

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Christophe de Dinechin]

Mark,


I believe that the "may" here (and the whole sentence) was intended to 
cover the internal data structures used for mangling, rather than the 
result. In other words, the result must be compressed ("If a component 
has been encountered, it IS substituted as described below"). But the 
spec doesn't force you to recognize the structure internally ahead of 
time.

As I remember it, an ordering problem arose when we discussed 
implementations. For instance, aCC has a unique internal "type token" 
that it builds quite early. We wanted to make it possible for aCC to use 
the type token as the key in the dictionary, which would correspond to 
the optimization of "considering large structures for substitution 
before their components". But we did not want to impose such a "type 
token" on other compilers just for mangling reasons.


Regards,
Christophe

On Wednesday, February 20, 2002, at 06:42 AM, Mark Mitchell wrote:

> Stan --
>
>  I've forwarded your mail to the C++ ABI mailing list:
>
>    cxx-abi-dev@codesourcery.com
>
> --On Tuesday, February 19, 2002 02:42:02 PM -0800 Stan Shebs 
> <shebs@apple.com> wrote:
>
>> One of our tasks in migrating Darwin / Mac OS X to use GCC 3.x is
>> to provide a way to load I/O drivers written in C++ and compiled
>> with GCC 2.95.  (Yeah yeah, bad idea, but the deed is done, and
>> alternative is to compile the kernel's I/O subsystem with 2.95
>> forever, I'll work hard to avoid that fate.)
>>
>> Anyway, to translate the symbols we have a homemade 2.95 compat
>> demangler (written using a spec I handed to the kernel hacker,
>> poor guy) feeding into a remangler written using the spec at
>> http://www.codesourcery.com/cxx-abi/abi.html#mangling.  So far
>> so good, we have something that actually does the right thing
>> most of the time.  However, there is a troublesome point in the
>> substitution rules for the new C++ ABI, where it says
>>
>> "Logically, the substitutable components of a mangled name are
>> considered left-to-right, components before the composite structure
>> of which they are a part. If a component has been encountered
>> before, it is substituted as described below. This decision is
>> independent of whether its components have been substituted,
>> so an implementation MAY OPTIMIZE by considering large structures
>> for substitution before their components. If a component has not
>> been encountered before, its mangling is identified, and it is
>> added to a dictionary of substitution candidates. No entity is
>> added to the dictionary twice." (emphasis mine)
>
> I think that "may" should be "must".
>
> Thoughts?
>
> --
> Mark Mitchell                   mark@codesourcery.com
> CodeSourcery, LLC               http://www.codesourcery.com
>
>

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Stan Shebs]

Thanks all - the "must" interpretation seemed most sensible to me too.

Incidentally, the kernel guy now reports that he has a remangler
capable of converting all the 2.95 mangled symbols in Darwin kernel
and drivers to their 3.1 counterparts.  Next is to try booting a
3.1-compiled kernel and see what happens when the 3.1 base classes
actually load the 2.95-compiled derived classes that make up the
drivers...

Stan

Jim Dehnert wrote:
> 
> It was certainly intended as must.  My mistake, probably.  As Joe
> points out, it's not portable otherwise, so there's not much choice.
> 
> Jim
> 
> Joe Buck wrote:
> >
> > > > "Logically, the substitutable components of a mangled name are
> > > > considered left-to-right, components before the composite structure
> > > > of which they are a part. If a component has been encountered
> > > > before, it is substituted as described below. This decision is
> > > > independent of whether its components have been substituted,
> > > > so an implementation MAY OPTIMIZE by considering large structures
> > > > for substitution before their components. If a component has not
> > > > been encountered before, its mangling is identified, and it is
> > > > added to a dictionary of substitution candidates. No entity is
> > > > added to the dictionary twice." (emphasis mine)
> >
> > Mark writes:
> > > I think that "may" should be "must".
> >
> > If all the folks who implemented the ABI interpreted it that way, we
> > have no problem with s/may/must/.  But if some did not, then we don't
> > have a portable ABI, someone will have to make changes.

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Jim Dehnert]

Stan Shebs wrote:
> 
> Thanks all - the "must" interpretation seemed most sensible to me too.

I assume you've also seen Christophe's explanation, which, based on my
flaky memory, is probably correct.  Re-reading this carefully, note that
the result that one gets is actually independent of whether the described
optimization has taken place -- whether or not you have taken the effort
of substituting for the components before considering a containing structure,
the decision to substitute is based on the structure having been encoded
earlier, not on whether the (partially-substituted or not) manglings are
the same.  So the current wording is correct.  The optimization MAY be
applied to the implementation, but will not change the mangling.

Jim

> Jim Dehnert wrote:
> >
> > It was certainly intended as must.  My mistake, probably.  As Joe
> > points out, it's not portable otherwise, so there's not much choice.
> >
> > Jim
> >
> > Joe Buck wrote:
> > >
> > > > > "Logically, the substitutable components of a mangled name are
> > > > > considered left-to-right, components before the composite structure
> > > > > of which they are a part. If a component has been encountered
> > > > > before, it is substituted as described below. This decision is
> > > > > independent of whether its components have been substituted,
> > > > > so an implementation MAY OPTIMIZE by considering large structures
> > > > > for substitution before their components. If a component has not
> > > > > been encountered before, its mangling is identified, and it is
> > > > > added to a dictionary of substitution candidates. No entity is
> > > > > added to the dictionary twice." (emphasis mine)
> > >
> > > Mark writes:
> > > > I think that "may" should be "must".
> > >
> > > If all the folks who implemented the ABI interpreted it that way, we
> > > have no problem with s/may/must/.  But if some did not, then we don't
> > > have a portable ABI, someone will have to make changes.

-- 
-	    Jim Dehnert		dehnert@transmeta.com
	    (408)919-6984	dehnertj@acm.org

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Martin von Loewis]

Stan Shebs <shebs@apple.com> writes:

> Incidentally, the kernel guy now reports that he has a remangler
> capable of converting all the 2.95 mangled symbols in Darwin kernel
> and drivers to their 3.1 counterparts.  Next is to try booting a
> 3.1-compiled kernel and see what happens when the 3.1 base classes
> actually load the 2.95-compiled derived classes that make up the
> drivers...

Not that this is relevant for the ABI discussions: but won't there be
issues with changes to object layout as well?

Regards,
Martin

Re: [cxx-abi-dev] Re: Mistake in C++ ABI substitution rules?

[Joe Buck]

Stan Shebs <shebs@apple.com> writes:
> 
> > Incidentally, the kernel guy now reports that he has a remangler
> > capable of converting all the 2.95 mangled symbols in Darwin kernel
> > and drivers to their 3.1 counterparts.  Next is to try booting a
> > 3.1-compiled kernel and see what happens when the 3.1 base classes
> > actually load the 2.95-compiled derived classes that make up the
> > drivers...

Martin von Loewis writes:
> Not that this is relevant for the ABI discussions: but won't there be
> issues with changes to object layout as well?

Yes, in particular 2.95 always reserved at least 1 byte for all
sub-objects (members or base classes of a class or struct), but 3.x
will not allocate any space in most cases for classes with no data
members and no vtable.

Re: Mistake in C++ ABI substitution rules?

[Jason Merrill]

>>>>> "Carlo" == Carlo Wood <carlo@alinoe.com> writes:

> // The ABI specifies for pointer-to-member function types the format <Q>M<T>F<R><B>E.  In other words,
> // the qualifier <Q2> (see above) is implicitely contained in <T> instead of explicitly part of the M
> // format.  I am convinced that this is a bug in the ABI.

No, it was just a bug in g++, which I fixed a couple of weeks ago.  Now Q2
modifies the function type, rather than the class type.

Jason