New demangler bug and HOWTO-demangle (was Re: Demangle THIS)

[Carlo Wood <carlo at alinoe dot com>]

On Thu, Jun 21, 2001 at 11:15:55AM -0400, Daniel Berlin wrote:
> Well, put it in libcw's CVS, and i'll rewrite the libiberty demangler
> to do it.

I *finally* finished the demangler :).
I just commited it to the CVS of libcwd.

The most important part(s) for you to look at are probably the comments,
but I suppose it also will help to look at the code (especially how
'decode_type' works).

Allow me to repeat the most relevant comments from 'demangle3.cc' here:
(17" monitor (1024x768) needed here)

  // 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 :/
  //

Also note that I choose for a special treatment of the G and C qualifiers
and print those on the left side of the type.  This should be correct in
all cases because such a type can't be a pointer (and thus 'TYPE complex'
 == 'complex TYPE').  I think that having the 'complex' qualifier on the
left will be common practise because of this.  This also causes the G and C
qualifiers to always cuddle with the (unqualified) type <T>, hence - we can
treat G an C and not being a part of <Q>.


Note that apart from printing the qualifiers at the wrong place sometimes
I did find only ONE bug in the demangler of libiberty, which is actually
pretty impressive.  This bug is related to the generation of substituation
above S9_ and shows up while demangling this:

_Z3fooiPiPS_PS0_PS1_PS2_PS3_PS4_PS5_PS6_PS7_PS8_PS9_PSA_PSB_PSC_

This really is:

~/c++/libcw/src/libcwd>cat test2.cc
int foo(int,
        int*,
        int**,
        int***,
        int****,
        int*****,
        int******,
        int*******,
        int********,
        int*********,
        int**********,
        int***********,
        int************,
        int*************,
        int**************,
        int***************)
{
}

but is demangled by libiberty as:

SUBSTITUTIONS:
 S_   : int*
 S0_  : int**
 S1_  : int***
 S2_  : int****
 S3_  : int*****
 S4_  : int******
 S5_  : int*******
 S6_  : int********
 S7_  : int*********
 S8_  : int**********
 S9_  : int***********
 S10_  : int************
 S11_  : int************	<-- huh?
 S12_  : int*************
 S13_  : int************	<-- huh?
 S14_  : int*************	<-- huh?
 S15_  : int*************	<-- huh?
 S16_  : int**************
    foo(int,
        int*,
        int**,
	int***,
	int****,
	int*****,
	int******,
	int*******,
	int********,
	int*********,
	int**********,
	int***********,
	int************,
	int*************,
	int*************,
	int**************)