src/demangle.cc

   1 // Copyright (c) 2006, Google Inc.
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are
   6 // met:
   7 //
   8 //     * Redistributions of source code must retain the above copyright
   9 // notice, this list of conditions and the following disclaimer.
  10 //     * Redistributions in binary form must reproduce the above
  11 // copyright notice, this list of conditions and the following disclaimer
  12 // in the documentation and/or other materials provided with the
  13 // distribution.
  14 //     * Neither the name of Google Inc. nor the names of its
  15 // contributors may be used to endorse or promote products derived from
  16 // this software without specific prior written permission.
  17 //
  18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 //
  30 // Author: Satoru Takabayashi
  31 //
  32 // For reference check out:
  33 // http://www.codesourcery.com/public/cxx-abi/abi.html#mangling
  34 //
  35 // Note that we only have partial C++0x support yet.
  36
  37 #include <stdio.h>  // for NULL
  38 #include "demangle.h"
  39
  40 _START_GOOGLE_NAMESPACE_
  41
  42 typedef struct {
  43   const char *abbrev;
  44   const char *real_name;
  45 } AbbrevPair;
  46
  47 // List of operators from Itanium C++ ABI.
  48 static const AbbrevPair kOperatorList[] = {
  49   { "nw", "new" },
  50   { "na", "new[]" },
  51   { "dl", "delete" },
  52   { "da", "delete[]" },
  53   { "ps", "+" },
  54   { "ng", "-" },
  55   { "ad", "&" },
  56   { "de", "*" },
  57   { "co", "~" },
  58   { "pl", "+" },
  59   { "mi", "-" },
  60   { "ml", "*" },
  61   { "dv", "/" },
  62   { "rm", "%" },
  63   { "an", "&" },
  64   { "or", "|" },
  65   { "eo", "^" },
  66   { "aS", "=" },
  67   { "pL", "+=" },
  68   { "mI", "-=" },
  69   { "mL", "*=" },
  70   { "dV", "/=" },
  71   { "rM", "%=" },
  72   { "aN", "&=" },
  73   { "oR", "|=" },
  74   { "eO", "^=" },
  75   { "ls", "<<" },
  76   { "rs", ">>" },
  77   { "lS", "<<=" },
  78   { "rS", ">>=" },
  79   { "eq", "==" },
  80   { "ne", "!=" },
  81   { "lt", "<" },
  82   { "gt", ">" },
  83   { "le", "<=" },
  84   { "ge", ">=" },
  85   { "nt", "!" },
  86   { "aa", "&&" },
  87   { "oo", "||" },
  88   { "pp", "++" },
  89   { "mm", "--" },
  90   { "cm", "," },
  91   { "pm", "->*" },
  92   { "pt", "->" },
  93   { "cl", "()" },
  94   { "ix", "[]" },
  95   { "qu", "?" },
  96   { "st", "sizeof" },
  97   { "sz", "sizeof" },
  98   { NULL, NULL },
  99 };
 100
 101 // List of builtin types from Itanium C++ ABI.
 102 static const AbbrevPair kBuiltinTypeList[] = {
 103   { "v", "void" },
 104   { "w", "wchar_t" },
 105   { "b", "bool" },
 106   { "c", "char" },
 107   { "a", "signed char" },
 108   { "h", "unsigned char" },
 109   { "s", "short" },
 110   { "t", "unsigned short" },
 111   { "i", "int" },
 112   { "j", "unsigned int" },
 113   { "l", "long" },
 114   { "m", "unsigned long" },
 115   { "x", "long long" },
 116   { "y", "unsigned long long" },
 117   { "n", "__int128" },
 118   { "o", "unsigned __int128" },
 119   { "f", "float" },
 120   { "d", "double" },
 121   { "e", "long double" },
 122   { "g", "__float128" },
 123   { "z", "ellipsis" },
 124   { NULL, NULL }
 125 };
 126
 127 // List of substitutions Itanium C++ ABI.
 128 static const AbbrevPair kSubstitutionList[] = {
 129   { "St", "" },
 130   { "Sa", "allocator" },
 131   { "Sb", "basic_string" },
 132   // std::basic_string<char, std::char_traits<char>,std::allocator<char> >
 133   { "Ss", "string"},
 134   // std::basic_istream<char, std::char_traits<char> >
 135   { "Si", "istream" },
 136   // std::basic_ostream<char, std::char_traits<char> >
 137   { "So", "ostream" },
 138   // std::basic_iostream<char, std::char_traits<char> >
 139   { "Sd", "iostream" },
 140   { NULL, NULL }
 141 };
 142
 143 // State needed for demangling.
 144 typedef struct {
 145   const char *mangled_cur;  // Cursor of mangled name.
 146   char *out_cur;            // Cursor of output string.
 147   const char *out_begin;    // Beginning of output string.
 148   const char *out_end;      // End of output string.
 149   const char *prev_name;    // For constructors/destructors.
 150   int prev_name_length;     // For constructors/destructors.
 151   short nest_level;         // For nested names.
 152   bool append;              // Append flag.
 153   bool overflowed;          // True if output gets overflowed.
 154 } State;
 155
 156 // We don't use strlen() in libc since it's not guaranteed to be async
 157 // signal safe.
 158 static size_t StrLen(const char *str) {
 159   size_t len = 0;
 160   while (*str != '\0') {
 161     ++str;
 162     ++len;
 163   }
 164   return len;
 165 }
 166
 167 // Returns true if "str" has at least "n" characters remaining.
 168 static bool AtLeastNumCharsRemaining(const char *str, int n) {
 169   for (int i = 0; i < n; ++i) {
 170     if (str == '\0') {
 171       return false;
 172     }
 173   }
 174   return true;
 175 }
 176
 177 // Returns true if "str" has "prefix" as a prefix.
 178 static bool StrPrefix(const char *str, const char *prefix) {
 179   size_t i = 0;
 180   while (str[i] != '\0' && prefix[i] != '\0' &&
 181          str[i] == prefix[i]) {
 182     ++i;
 183   }
 184   return prefix[i] == '\0';  // Consumed everything in "prefix".
 185 }
 186
 187 static void InitState(State *state, const char *mangled,
 188                       char *out, int out_size) {
 189   state->mangled_cur = mangled;
 190   state->out_cur = out;
 191   state->out_begin = out;
 192   state->out_end = out + out_size;
 193   state->prev_name  = NULL;
 194   state->prev_name_length = -1;
 195   state->nest_level = -1;
 196   state->append = true;
 197   state->overflowed = false;
 198 }
 199
 200 // Returns true and advances "mangled_cur" if we find "one_char_token"
 201 // at "mangled_cur" position.  It is assumed that "one_char_token" does
 202 // not contain '\0'.
 203 static bool ParseOneCharToken(State *state, const char one_char_token) {
 204   if (state->mangled_cur[0] == one_char_token) {
 205     ++state->mangled_cur;
 206     return true;
 207   }
 208   return false;
 209 }
 210
 211 // Returns true and advances "mangled_cur" if we find "two_char_token"
 212 // at "mangled_cur" position.  It is assumed that "two_char_token" does
 213 // not contain '\0'.
 214 static bool ParseTwoCharToken(State *state, const char *two_char_token) {
 215   if (state->mangled_cur[0] == two_char_token[0] &&
 216       state->mangled_cur[1] == two_char_token[1]) {
 217     state->mangled_cur += 2;
 218     return true;
 219   }
 220   return false;
 221 }
 222
 223 // Returns true and advances "mangled_cur" if we find any character in
 224 // "char_class" at "mangled_cur" position.
 225 static bool ParseCharClass(State *state, const char *char_class) {
 226   if (state->mangled_cur == '\0') {
 227     return false;
 228   }
 229   const char *p = char_class;
 230   for (; *p != '\0'; ++p) {
 231     if (state->mangled_cur[0] == *p) {
 232       ++state->mangled_cur;
 233       return true;
 234     }
 235   }
 236   return false;
 237 }
 238
 239 // This function is used for handling an optional non-terminal.
 240 static bool Optional(bool) {
 241   return true;
 242 }
 243
 244 // This function is used for handling <non-terminal>+ syntax.
 245 typedef bool (*ParseFunc)(State *);
 246 static bool OneOrMore(ParseFunc parse_func, State *state) {
 247   if (parse_func(state)) {
 248     while (parse_func(state)) {
 249     }
 250     return true;
 251   }
 252   return false;
 253 }
 254
 255 // This function is used for handling <non-terminal>* syntax. The function
 256 // always returns true and must be followed by a termination token or a
 257 // terminating sequence not handled by parse_func (e.g.
 258 // ParseOneCharToken(state, 'E')).
 259 static bool ZeroOrMore(ParseFunc parse_func, State *state) {
 260   while (parse_func(state)) {
 261   }
 262   return true;
 263 }
 264
 265 // Append "str" at "out_cur".  If there is an overflow, "overflowed"
 266 // is set to true for later use.  The output string is ensured to
 267 // always terminate with '\0' as long as there is no overflow.
 268 static void Append(State *state, const char * const str, const int length) {
 269   int i;
 270   for (i = 0; i < length; ++i) {
 271     if (state->out_cur + 1 < state->out_end) {  // +1 for '\0'
 272       *state->out_cur = str[i];
 273       ++state->out_cur;
 274     } else {
 275       state->overflowed = true;
 276       break;
 277     }
 278   }
 279   if (!state->overflowed) {
 280     *state->out_cur = '\0';  // Terminate it with '\0'
 281   }
 282 }
 283
 284 // We don't use equivalents in libc to avoid locale issues.
 285 static bool IsLower(char c) {
 286   return c >= 'a' && c <= 'z';
 287 }
 288
 289 static bool IsAlpha(char c) {
 290   return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
 291 }
 292
 293 static bool IsDigit(char c) {
 294   return c >= '0' && c <= '9';
 295 }
 296
 297 // Returns true if "str" is a function clone suffix.  These suffixes are used
 298 // by GCC 4.5.x and later versions to indicate functions which have been
 299 // cloned during optimization.  We treat any sequence (.<alpha>+.<digit>+)+ as
 300 // a function clone suffix.
 301 static bool IsFunctionCloneSuffix(const char *str) {
 302   size_t i = 0;
 303   while (str[i] != '\0') {
 304     // Consume a single .<alpha>+.<digit>+ sequence.
 305     if (str[i] != '.' || !IsAlpha(str[i + 1])) {
 306       return false;
 307     }
 308     i += 2;
 309     while (IsAlpha(str[i])) {
 310       ++i;
 311     }
 312     if (str[i] != '.' || !IsDigit(str[i + 1])) {
 313       return false;
 314     }
 315     i += 2;
 316     while (IsDigit(str[i])) {
 317       ++i;
 318     }
 319   }
 320   return true;  // Consumed everything in "str".
 321 }
 322
 323 // Append "str" with some tweaks, iff "append" state is true.
 324 // Returns true so that it can be placed in "if" conditions.
 325 static void MaybeAppendWithLength(State *state, const char * const str,
 326                                   const int length) {
 327   if (state->append && length > 0) {
 328     // Append a space if the output buffer ends with '<' and "str"
 329     // starts with '<' to avoid <<<.
 330     if (str[0] == '<' && state->out_begin < state->out_cur  &&
 331         state->out_cur[-1] == '<') {
 332       Append(state, " ", 1);
 333     }
 334     // Remember the last identifier name for ctors/dtors.
 335     if (IsAlpha(str[0]) || str[0] == '_') {
 336       state->prev_name = state->out_cur;
 337       state->prev_name_length = length;
 338     }
 339     Append(state, str, length);
 340   }
 341 }
 342
 343 // A convenient wrapper arount MaybeAppendWithLength().
 344 static bool MaybeAppend(State *state, const char * const str) {
 345   if (state->append) {
 346     int length = StrLen(str);
 347     MaybeAppendWithLength(state, str, length);
 348   }
 349   return true;
 350 }
 351
 352 // This function is used for handling nested names.
 353 static bool EnterNestedName(State *state) {
 354   state->nest_level = 0;
 355   return true;
 356 }
 357
 358 // This function is used for handling nested names.
 359 static bool LeaveNestedName(State *state, short prev_value) {
 360   state->nest_level = prev_value;
 361   return true;
 362 }
 363
 364 // Disable the append mode not to print function parameters, etc.
 365 static bool DisableAppend(State *state) {
 366   state->append = false;
 367   return true;
 368 }
 369
 370 // Restore the append mode to the previous state.
 371 static bool RestoreAppend(State *state, bool prev_value) {
 372   state->append = prev_value;
 373   return true;
 374 }
 375
 376 // Increase the nest level for nested names.
 377 static void MaybeIncreaseNestLevel(State *state) {
 378   if (state->nest_level > -1) {
 379     ++state->nest_level;
 380   }
 381 }
 382
 383 // Appends :: for nested names if necessary.
 384 static void MaybeAppendSeparator(State *state) {
 385   if (state->nest_level >= 1) {
 386     MaybeAppend(state, "::");
 387   }
 388 }
 389
 390 // Cancel the last separator if necessary.
 391 static void MaybeCancelLastSeparator(State *state) {
 392   if (state->nest_level >= 1 && state->append &&
 393       state->out_begin <= state->out_cur - 2) {
 394     state->out_cur -= 2;
 395     *state->out_cur = '\0';
 396   }
 397 }
 398
 399 // Returns true if the identifier of the given length pointed to by
 400 // "mangled_cur" is anonymous namespace.
 401 static bool IdentifierIsAnonymousNamespace(State *state, int length) {
 402   static const char anon_prefix[] = "_GLOBAL__N_";
 403   return (length > (int)sizeof(anon_prefix) - 1 &&  // Should be longer.
 404           StrPrefix(state->mangled_cur, anon_prefix));
 405 }
 406
 407 // Forward declarations of our parsing functions.
 408 static bool ParseMangledName(State *state);
 409 static bool ParseEncoding(State *state);
 410 static bool ParseName(State *state);
 411 static bool ParseUnscopedName(State *state);
 412 static bool ParseUnscopedTemplateName(State *state);
 413 static bool ParseNestedName(State *state);
 414 static bool ParsePrefix(State *state);
 415 static bool ParseUnqualifiedName(State *state);
 416 static bool ParseSourceName(State *state);
 417 static bool ParseLocalSourceName(State *state);
 418 static bool ParseNumber(State *state, int *number_out);
 419 static bool ParseFloatNumber(State *state);
 420 static bool ParseSeqId(State *state);
 421 static bool ParseIdentifier(State *state, int length);
 422 static bool ParseOperatorName(State *state);
 423 static bool ParseSpecialName(State *state);
 424 static bool ParseCallOffset(State *state);
 425 static bool ParseNVOffset(State *state);
 426 static bool ParseVOffset(State *state);
 427 static bool ParseCtorDtorName(State *state);
 428 static bool ParseType(State *state);
 429 static bool ParseCVQualifiers(State *state);
 430 static bool ParseBuiltinType(State *state);
 431 static bool ParseFunctionType(State *state);
 432 static bool ParseBareFunctionType(State *state);
 433 static bool ParseClassEnumType(State *state);
 434 static bool ParseArrayType(State *state);
 435 static bool ParsePointerToMemberType(State *state);
 436 static bool ParseTemplateParam(State *state);
 437 static bool ParseTemplateTemplateParam(State *state);
 438 static bool ParseTemplateArgs(State *state);
 439 static bool ParseTemplateArg(State *state);
 440 static bool ParseExpression(State *state);
 441 static bool ParseExprPrimary(State *state);
 442 static bool ParseLocalName(State *state);
 443 static bool ParseDiscriminator(State *state);
 444 static bool ParseSubstitution(State *state);
 445
 446 // Implementation note: the following code is a straightforward
 447 // translation of the Itanium C++ ABI defined in BNF with a couple of
 448 // exceptions.
 449 //
 450 // - Support GNU extensions not defined in the Itanium C++ ABI
 451 // - <prefix> and <template-prefix> are combined to avoid infinite loop
 452 // - Reorder patterns to shorten the code
 453 // - Reorder patterns to give greedier functions precedence
 454 //   We'll mark "Less greedy than" for these cases in the code
 455 //
 456 // Each parsing function changes the state and returns true on
 457 // success.  Otherwise, don't change the state and returns false.  To
 458 // ensure that the state isn't changed in the latter case, we save the
 459 // original state before we call more than one parsing functions
 460 // consecutively with &&, and restore the state if unsuccessful.  See
 461 // ParseEncoding() as an example of this convention.  We follow the
 462 // convention throughout the code.
 463 //
 464 // Originally we tried to do demangling without following the full ABI
 465 // syntax but it turned out we needed to follow the full syntax to
 466 // parse complicated cases like nested template arguments.  Note that
 467 // implementing a full-fledged demangler isn't trivial (libiberty's
 468 // cp-demangle.c has +4300 lines).
 469 //
 470 // Note that (foo) in <(foo) ...> is a modifier to be ignored.
 471 //
 472 // Reference:
 473 // - Itanium C++ ABI
 474 //   <http://www.codesourcery.com/cxx-abi/abi.html#mangling>
 475
 476 // <mangled-name> ::= _Z <encoding>
 477 static bool ParseMangledName(State *state) {
 478   return ParseTwoCharToken(state, "_Z") && ParseEncoding(state);
 479 }
 480
 481 // <encoding> ::= <(function) name> <bare-function-type>
 482 //            ::= <(data) name>
 483 //            ::= <special-name>
 484 static bool ParseEncoding(State *state) {
 485   State copy = *state;
 486   if (ParseName(state) && ParseBareFunctionType(state)) {
 487     return true;
 488   }
 489   *state = copy;
 490
 491   if (ParseName(state) || ParseSpecialName(state)) {
 492     return true;
 493   }
 494   return false;
 495 }
 496
 497 // <name> ::= <nested-name>
 498 //        ::= <unscoped-template-name> <template-args>
 499 //        ::= <unscoped-name>
 500 //        ::= <local-name>
 501 static bool ParseName(State *state) {
 502   if (ParseNestedName(state) || ParseLocalName(state)) {
 503     return true;
 504   }
 505
 506   State copy = *state;
 507   if (ParseUnscopedTemplateName(state) &&
 508       ParseTemplateArgs(state)) {
 509     return true;
 510   }
 511   *state = copy;
 512
 513   // Less greedy than <unscoped-template-name> <template-args>.
 514   if (ParseUnscopedName(state)) {
 515     return true;
 516   }
 517   return false;
 518 }
 519
 520 // <unscoped-name> ::= <unqualified-name>
 521 //                 ::= St <unqualified-name>
 522 static bool ParseUnscopedName(State *state) {
 523   if (ParseUnqualifiedName(state)) {
 524     return true;
 525   }
 526
 527   State copy = *state;
 528   if (ParseTwoCharToken(state, "St") &&
 529       MaybeAppend(state, "std::") &&
 530       ParseUnqualifiedName(state)) {
 531     return true;
 532   }
 533   *state = copy;
 534   return false;
 535 }
 536
 537 // <unscoped-template-name> ::= <unscoped-name>
 538 //                          ::= <substitution>
 539 static bool ParseUnscopedTemplateName(State *state) {
 540   return ParseUnscopedName(state) || ParseSubstitution(state);
 541 }
 542
 543 // <nested-name> ::= N [<CV-qualifiers>] <prefix> <unqualified-name> E
 544 //               ::= N [<CV-qualifiers>] <template-prefix> <template-args> E
 545 static bool ParseNestedName(State *state) {
 546   State copy = *state;
 547   if (ParseOneCharToken(state, 'N') &&
 548       EnterNestedName(state) &&
 549       Optional(ParseCVQualifiers(state)) &&
 550       ParsePrefix(state) &&
 551       LeaveNestedName(state, copy.nest_level) &&
 552       ParseOneCharToken(state, 'E')) {
 553     return true;
 554   }
 555   *state = copy;
 556   return false;
 557 }
 558
 559 // This part is tricky.  If we literally translate them to code, we'll
 560 // end up infinite loop.  Hence we merge them to avoid the case.
 561 //
 562 // <prefix> ::= <prefix> <unqualified-name>
 563 //          ::= <template-prefix> <template-args>
 564 //          ::= <template-param>
 565 //          ::= <substitution>
 566 //          ::= # empty
 567 // <template-prefix> ::= <prefix> <(template) unqualified-name>
 568 //                   ::= <template-param>
 569 //                   ::= <substitution>
 570 static bool ParsePrefix(State *state) {
 571   bool has_something = false;
 572   while (true) {
 573     MaybeAppendSeparator(state);
 574     if (ParseTemplateParam(state) ||
 575         ParseSubstitution(state) ||
 576         ParseUnscopedName(state)) {
 577       has_something = true;
 578       MaybeIncreaseNestLevel(state);
 579       continue;
 580     }
 581     MaybeCancelLastSeparator(state);
 582     if (has_something && ParseTemplateArgs(state)) {
 583       return ParsePrefix(state);
 584     } else {
 585       break;
 586     }
 587   }
 588   return true;
 589 }
 590
 591 // <unqualified-name> ::= <operator-name>
 592 //                    ::= <ctor-dtor-name>
 593 //                    ::= <source-name>
 594 //                    ::= <local-source-name>
 595 static bool ParseUnqualifiedName(State *state) {
 596   return (ParseOperatorName(state) ||
 597           ParseCtorDtorName(state) ||
 598           ParseSourceName(state) ||
 599           ParseLocalSourceName(state));
 600 }
 601
 602 // <source-name> ::= <positive length number> <identifier>
 603 static bool ParseSourceName(State *state) {
 604   State copy = *state;
 605   int length = -1;
 606   if (ParseNumber(state, &length) && ParseIdentifier(state, length)) {
 607     return true;
 608   }
 609   *state = copy;
 610   return false;
 611 }
 612
 613 // <local-source-name> ::= L <source-name> [<discriminator>]
 614 //
 615 // References:
 616 //   http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31775
 617 //   http://gcc.gnu.org/viewcvs?view=rev&revision=124467
 618 static bool ParseLocalSourceName(State *state) {
 619   State copy = *state;
 620   if (ParseOneCharToken(state, 'L') && ParseSourceName(state) &&
 621       Optional(ParseDiscriminator(state))) {
 622     return true;
 623   }
 624   *state = copy;
 625   return false;
 626 }
 627
 628 // <number> ::= [n] <non-negative decimal integer>
 629 // If "number_out" is non-null, then *number_out is set to the value of the
 630 // parsed number on success.
 631 static bool ParseNumber(State *state, int *number_out) {
 632   int sign = 1;
 633   if (ParseOneCharToken(state, 'n')) {
 634     sign = -1;
 635   }
 636   const char *p = state->mangled_cur;
 637   int number = 0;
 638   for (;*p != '\0'; ++p) {
 639     if (IsDigit(*p)) {
 640       number = number * 10 + (*p - '0');
 641     } else {
 642       break;
 643     }
 644   }
 645   if (p != state->mangled_cur) {  // Conversion succeeded.
 646     state->mangled_cur = p;
 647     if (number_out != NULL) {
 648       *number_out = number * sign;
 649     }
 650     return true;
 651   }
 652   return false;
 653 }
 654
 655 // Floating-point literals are encoded using a fixed-length lowercase
 656 // hexadecimal string.
 657 static bool ParseFloatNumber(State *state) {
 658   const char *p = state->mangled_cur;
 659   for (;*p != '\0'; ++p) {
 660     if (!IsDigit(*p) && !(*p >= 'a' && *p <= 'f')) {
 661       break;
 662     }
 663   }
 664   if (p != state->mangled_cur) {  // Conversion succeeded.
 665     state->mangled_cur = p;
 666     return true;
 667   }
 668   return false;
 669 }
 670
 671 // The <seq-id> is a sequence number in base 36,
 672 // using digits and upper case letters
 673 static bool ParseSeqId(State *state) {
 674   const char *p = state->mangled_cur;
 675   for (;*p != '\0'; ++p) {
 676     if (!IsDigit(*p) && !(*p >= 'A' && *p <= 'Z')) {
 677       break;
 678     }
 679   }
 680   if (p != state->mangled_cur) {  // Conversion succeeded.
 681     state->mangled_cur = p;
 682     return true;
 683   }
 684   return false;
 685 }
 686
 687 // <identifier> ::= <unqualified source code identifier> (of given length)
 688 static bool ParseIdentifier(State *state, int length) {
 689   if (length == -1 ||
 690       !AtLeastNumCharsRemaining(state->mangled_cur, length)) {
 691     return false;
 692   }
 693   if (IdentifierIsAnonymousNamespace(state, length)) {
 694     MaybeAppend(state, "(anonymous namespace)");
 695   } else {
 696     MaybeAppendWithLength(state, state->mangled_cur, length);
 697   }
 698   state->mangled_cur += length;
 699   return true;
 700 }
 701
 702 // <operator-name> ::= nw, and other two letters cases
 703 //                 ::= cv <type>  # (cast)
 704 //                 ::= v  <digit> <source-name> # vendor extended operator
 705 static bool ParseOperatorName(State *state) {
 706   if (!AtLeastNumCharsRemaining(state->mangled_cur, 2)) {
 707     return false;
 708   }
 709   // First check with "cv" (cast) case.
 710   State copy = *state;
 711   if (ParseTwoCharToken(state, "cv") &&
 712       MaybeAppend(state, "operator ") &&
 713       EnterNestedName(state) &&
 714       ParseType(state) &&
 715       LeaveNestedName(state, copy.nest_level)) {
 716     return true;
 717   }
 718   *state = copy;
 719
 720   // Then vendor extended operators.
 721   if (ParseOneCharToken(state, 'v') && ParseCharClass(state, "0123456789") &&
 722       ParseSourceName(state)) {
 723     return true;
 724   }
 725   *state = copy;
 726
 727   // Other operator names should start with a lower alphabet followed
 728   // by a lower/upper alphabet.
 729   if (!(IsLower(state->mangled_cur[0]) &&
 730         IsAlpha(state->mangled_cur[1]))) {
 731     return false;
 732   }
 733   // We may want to perform a binary search if we really need speed.
 734   const AbbrevPair *p;
 735   for (p = kOperatorList; p->abbrev != NULL; ++p) {
 736     if (state->mangled_cur[0] == p->abbrev[0] &&
 737         state->mangled_cur[1] == p->abbrev[1]) {
 738       MaybeAppend(state, "operator");
 739       if (IsLower(*p->real_name)) {  // new, delete, etc.
 740         MaybeAppend(state, " ");
 741       }
 742       MaybeAppend(state, p->real_name);
 743       state->mangled_cur += 2;
 744       return true;
 745     }
 746   }
 747   return false;
 748 }
 749
 750 // <special-name> ::= TV <type>
 751 //                ::= TT <type>
 752 //                ::= TI <type>
 753 //                ::= TS <type>
 754 //                ::= Tc <call-offset> <call-offset> <(base) encoding>
 755 //                ::= GV <(object) name>
 756 //                ::= T <call-offset> <(base) encoding>
 757 // G++ extensions:
 758 //                ::= TC <type> <(offset) number> _ <(base) type>
 759 //                ::= TF <type>
 760 //                ::= TJ <type>
 761 //                ::= GR <name>
 762 //                ::= GA <encoding>
 763 //                ::= Th <call-offset> <(base) encoding>
 764 //                ::= Tv <call-offset> <(base) encoding>
 765 //
 766 // Note: we don't care much about them since they don't appear in
 767 // stack traces.  The are special data.
 768 static bool ParseSpecialName(State *state) {
 769   State copy = *state;
 770   if (ParseOneCharToken(state, 'T') &&
 771       ParseCharClass(state, "VTIS") &&
 772       ParseType(state)) {
 773     return true;
 774   }
 775   *state = copy;
 776
 777   if (ParseTwoCharToken(state, "Tc") && ParseCallOffset(state) &&
 778       ParseCallOffset(state) && ParseEncoding(state)) {
 779     return true;
 780   }
 781   *state = copy;
 782
 783   if (ParseTwoCharToken(state, "GV") &&
 784       ParseName(state)) {
 785     return true;
 786   }
 787   *state = copy;
 788
 789   if (ParseOneCharToken(state, 'T') && ParseCallOffset(state) &&
 790       ParseEncoding(state)) {
 791     return true;
 792   }
 793   *state = copy;
 794
 795   // G++ extensions
 796   if (ParseTwoCharToken(state, "TC") && ParseType(state) &&
 797       ParseNumber(state, NULL) && ParseOneCharToken(state, '_') &&
 798       DisableAppend(state) &&
 799       ParseType(state)) {
 800     RestoreAppend(state, copy.append);
 801     return true;
 802   }
 803   *state = copy;
 804
 805   if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "FJ") &&
 806       ParseType(state)) {
 807     return true;
 808   }
 809   *state = copy;
 810
 811   if (ParseTwoCharToken(state, "GR") && ParseName(state)) {
 812     return true;
 813   }
 814   *state = copy;
 815
 816   if (ParseTwoCharToken(state, "GA") && ParseEncoding(state)) {
 817     return true;
 818   }
 819   *state = copy;
 820
 821   if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "hv") &&
 822       ParseCallOffset(state) && ParseEncoding(state)) {
 823     return true;
 824   }
 825   *state = copy;
 826   return false;
 827 }
 828
 829 // <call-offset> ::= h <nv-offset> _
 830 //               ::= v <v-offset> _
 831 static bool ParseCallOffset(State *state) {
 832   State copy = *state;
 833   if (ParseOneCharToken(state, 'h') &&
 834       ParseNVOffset(state) && ParseOneCharToken(state, '_')) {
 835     return true;
 836   }
 837   *state = copy;
 838
 839   if (ParseOneCharToken(state, 'v') &&
 840       ParseVOffset(state) && ParseOneCharToken(state, '_')) {
 841     return true;
 842   }
 843   *state = copy;
 844
 845   return false;
 846 }
 847
 848 // <nv-offset> ::= <(offset) number>
 849 static bool ParseNVOffset(State *state) {
 850   return ParseNumber(state, NULL);
 851 }
 852
 853 // <v-offset>  ::= <(offset) number> _ <(virtual offset) number>
 854 static bool ParseVOffset(State *state) {
 855   State copy = *state;
 856   if (ParseNumber(state, NULL) && ParseOneCharToken(state, '_') &&
 857       ParseNumber(state, NULL)) {
 858     return true;
 859   }
 860   *state = copy;
 861   return false;
 862 }
 863
 864 // <ctor-dtor-name> ::= C1 | C2 | C3
 865 //                  ::= D0 | D1 | D2
 866 static bool ParseCtorDtorName(State *state) {
 867   State copy = *state;
 868   if (ParseOneCharToken(state, 'C') &&
 869       ParseCharClass(state, "123")) {
 870     const char * const prev_name = state->prev_name;
 871     const int prev_name_length = state->prev_name_length;
 872     MaybeAppendWithLength(state, prev_name, prev_name_length);
 873     return true;
 874   }
 875   *state = copy;
 876
 877   if (ParseOneCharToken(state, 'D') &&
 878       ParseCharClass(state, "012")) {
 879     const char * const prev_name = state->prev_name;
 880     const int prev_name_length = state->prev_name_length;
 881     MaybeAppend(state, "~");
 882     MaybeAppendWithLength(state, prev_name, prev_name_length);
 883     return true;
 884   }
 885   *state = copy;
 886   return false;
 887 }
 888
 889 // <type> ::= <CV-qualifiers> <type>
 890 //        ::= P <type>   # pointer-to
 891 //        ::= R <type>   # reference-to
 892 //        ::= O <type>   # rvalue reference-to (C++0x)
 893 //        ::= C <type>   # complex pair (C 2000)
 894 //        ::= G <type>   # imaginary (C 2000)
 895 //        ::= U <source-name> <type>  # vendor extended type qualifier
 896 //        ::= <builtin-type>
 897 //        ::= <function-type>
 898 //        ::= <class-enum-type>
 899 //        ::= <array-type>
 900 //        ::= <pointer-to-member-type>
 901 //        ::= <template-template-param> <template-args>
 902 //        ::= <template-param>
 903 //        ::= <substitution>
 904 //        ::= Dp <type>          # pack expansion of (C++0x)
 905 //        ::= Dt <expression> E  # decltype of an id-expression or class
 906 //                               # member access (C++0x)
 907 //        ::= DT <expression> E  # decltype of an expression (C++0x)
 908 //
 909 static bool ParseType(State *state) {
 910   // We should check CV-qualifers, and PRGC things first.
 911   State copy = *state;
 912   if (ParseCVQualifiers(state) && ParseType(state)) {
 913     return true;
 914   }
 915   *state = copy;
 916
 917   if (ParseCharClass(state, "OPRCG") && ParseType(state)) {
 918     return true;
 919   }
 920   *state = copy;
 921
 922   if (ParseTwoCharToken(state, "Dp") && ParseType(state)) {
 923     return true;
 924   }
 925   *state = copy;
 926
 927   if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "tT") &&
 928       ParseExpression(state) && ParseOneCharToken(state, 'E')) {
 929     return true;
 930   }
 931   *state = copy;
 932
 933   if (ParseOneCharToken(state, 'U') && ParseSourceName(state) &&
 934       ParseType(state)) {
 935     return true;
 936   }
 937   *state = copy;
 938
 939   if (ParseBuiltinType(state) ||
 940       ParseFunctionType(state) ||
 941       ParseClassEnumType(state) ||
 942       ParseArrayType(state) ||
 943       ParsePointerToMemberType(state) ||
 944       ParseSubstitution(state)) {
 945     return true;
 946   }
 947
 948   if (ParseTemplateTemplateParam(state) &&
 949       ParseTemplateArgs(state)) {
 950     return true;
 951   }
 952   *state = copy;
 953
 954   // Less greedy than <template-template-param> <template-args>.
 955   if (ParseTemplateParam(state)) {
 956     return true;
 957   }
 958
 959   return false;
 960 }
 961
 962 // <CV-qualifiers> ::= [r] [V] [K]
 963 // We don't allow empty <CV-qualifiers> to avoid infinite loop in
 964 // ParseType().
 965 static bool ParseCVQualifiers(State *state) {
 966   int num_cv_qualifiers = 0;
 967   num_cv_qualifiers += ParseOneCharToken(state, 'r');
 968   num_cv_qualifiers += ParseOneCharToken(state, 'V');
 969   num_cv_qualifiers += ParseOneCharToken(state, 'K');
 970   return num_cv_qualifiers > 0;
 971 }
 972
 973 // <builtin-type> ::= v, etc.
 974 //                ::= u <source-name>
 975 static bool ParseBuiltinType(State *state) {
 976   const AbbrevPair *p;
 977   for (p = kBuiltinTypeList; p->abbrev != NULL; ++p) {
 978     if (state->mangled_cur[0] == p->abbrev[0]) {
 979       MaybeAppend(state, p->real_name);
 980       ++state->mangled_cur;
 981       return true;
 982     }
 983   }
 984
 985   State copy = *state;
 986   if (ParseOneCharToken(state, 'u') && ParseSourceName(state)) {
 987     return true;
 988   }
 989   *state = copy;
 990   return false;
 991 }
 992
 993 // <function-type> ::= F [Y] <bare-function-type> E
 994 static bool ParseFunctionType(State *state) {
 995   State copy = *state;
 996   if (ParseOneCharToken(state, 'F') &&
 997       Optional(ParseOneCharToken(state, 'Y')) &&
 998       ParseBareFunctionType(state) && ParseOneCharToken(state, 'E')) {
 999     return true;
1000   }
1001   *state = copy;
1002   return false;
1003 }
1004
1005 // <bare-function-type> ::= <(signature) type>+
1006 static bool ParseBareFunctionType(State *state) {
1007   State copy = *state;
1008   DisableAppend(state);
1009   if (OneOrMore(ParseType, state)) {
1010     RestoreAppend(state, copy.append);
1011     MaybeAppend(state, "()");
1012     return true;
1013   }
1014   *state = copy;
1015   return false;
1016 }
1017
1018 // <class-enum-type> ::= <name>
1019 static bool ParseClassEnumType(State *state) {
1020   return ParseName(state);
1021 }
1022
1023 // <array-type> ::= A <(positive dimension) number> _ <(element) type>
1024 //              ::= A [<(dimension) expression>] _ <(element) type>
1025 static bool ParseArrayType(State *state) {
1026   State copy = *state;
1027   if (ParseOneCharToken(state, 'A') && ParseNumber(state, NULL) &&
1028       ParseOneCharToken(state, '_') && ParseType(state)) {
1029     return true;
1030   }
1031   *state = copy;
1032
1033   if (ParseOneCharToken(state, 'A') && Optional(ParseExpression(state)) &&
1034       ParseOneCharToken(state, '_') && ParseType(state)) {
1035     return true;
1036   }
1037   *state = copy;
1038   return false;
1039 }
1040
1041 // <pointer-to-member-type> ::= M <(class) type> <(member) type>
1042 static bool ParsePointerToMemberType(State *state) {
1043   State copy = *state;
1044   if (ParseOneCharToken(state, 'M') && ParseType(state) &&
1045       ParseType(state)) {
1046     return true;
1047   }
1048   *state = copy;
1049   return false;
1050 }
1051
1052 // <template-param> ::= T_
1053 //                  ::= T <parameter-2 non-negative number> _
1054 static bool ParseTemplateParam(State *state) {
1055   if (ParseTwoCharToken(state, "T_")) {
1056     MaybeAppend(state, "?");  // We don't support template substitutions.
1057     return true;
1058   }
1059
1060   State copy = *state;
1061   if (ParseOneCharToken(state, 'T') && ParseNumber(state, NULL) &&
1062       ParseOneCharToken(state, '_')) {
1063     MaybeAppend(state, "?");  // We don't support template substitutions.
1064     return true;
1065   }
1066   *state = copy;
1067   return false;
1068 }
1069
1070
1071 // <template-template-param> ::= <template-param>
1072 //                           ::= <substitution>
1073 static bool ParseTemplateTemplateParam(State *state) {
1074   return (ParseTemplateParam(state) ||
1075           ParseSubstitution(state));
1076 }
1077
1078 // <template-args> ::= I <template-arg>+ E
1079 static bool ParseTemplateArgs(State *state) {
1080   State copy = *state;
1081   DisableAppend(state);
1082   if (ParseOneCharToken(state, 'I') &&
1083       OneOrMore(ParseTemplateArg, state) &&
1084       ParseOneCharToken(state, 'E')) {
1085     RestoreAppend(state, copy.append);
1086     MaybeAppend(state, "<>");
1087     return true;
1088   }
1089   *state = copy;
1090   return false;
1091 }
1092
1093 // <template-arg>  ::= <type>
1094 //                 ::= <expr-primary>
1095 //                 ::= I <template-arg>* E        # argument pack
1096 //                 ::= X <expression> E
1097 static bool ParseTemplateArg(State *state) {
1098   State copy = *state;
1099   if (ParseOneCharToken(state, 'I') &&
1100       ZeroOrMore(ParseTemplateArg, state) &&
1101       ParseOneCharToken(state, 'E')) {
1102     return true;
1103   }
1104   *state = copy;
1105
1106   if (ParseType(state) ||
1107       ParseExprPrimary(state)) {
1108     return true;
1109   }
1110   *state = copy;
1111
1112   if (ParseOneCharToken(state, 'X') && ParseExpression(state) &&
1113       ParseOneCharToken(state, 'E')) {
1114     return true;
1115   }
1116   *state = copy;
1117   return false;
1118 }
1119
1120 // <expression> ::= <template-param>
1121 //              ::= <expr-primary>
1122 //              ::= <unary operator-name> <expression>
1123 //              ::= <binary operator-name> <expression> <expression>
1124 //              ::= <trinary operator-name> <expression> <expression>
1125 //                  <expression>
1126 //              ::= st <type>
1127 //              ::= sr <type> <unqualified-name> <template-args>
1128 //              ::= sr <type> <unqualified-name>
1129 static bool ParseExpression(State *state) {
1130   if (ParseTemplateParam(state) || ParseExprPrimary(state)) {
1131     return true;
1132   }
1133
1134   State copy = *state;
1135   if (ParseOperatorName(state) &&
1136       ParseExpression(state) &&
1137       ParseExpression(state) &&
1138       ParseExpression(state)) {
1139     return true;
1140   }
1141   *state = copy;
1142
1143   if (ParseOperatorName(state) &&
1144       ParseExpression(state) &&
1145       ParseExpression(state)) {
1146     return true;
1147   }
1148   *state = copy;
1149
1150   if (ParseOperatorName(state) &&
1151       ParseExpression(state)) {
1152     return true;
1153   }
1154   *state = copy;
1155
1156   if (ParseTwoCharToken(state, "st") && ParseType(state)) {
1157     return true;
1158   }
1159   *state = copy;
1160
1161   if (ParseTwoCharToken(state, "sr") && ParseType(state) &&
1162       ParseUnqualifiedName(state) &&
1163       ParseTemplateArgs(state)) {
1164     return true;
1165   }
1166   *state = copy;
1167
1168   if (ParseTwoCharToken(state, "sr") && ParseType(state) &&
1169       ParseUnqualifiedName(state)) {
1170     return true;
1171   }
1172   *state = copy;
1173   return false;
1174 }
1175
1176 // <expr-primary> ::= L <type> <(value) number> E
1177 //                ::= L <type> <(value) float> E
1178 //                ::= L <mangled-name> E
1179 //                // A bug in g++'s C++ ABI version 2 (-fabi-version=2).
1180 //                ::= LZ <encoding> E
1181 static bool ParseExprPrimary(State *state) {
1182   State copy = *state;
1183   if (ParseOneCharToken(state, 'L') && ParseType(state) &&
1184       ParseNumber(state, NULL) &&
1185       ParseOneCharToken(state, 'E')) {
1186     return true;
1187   }
1188   *state = copy;
1189
1190   if (ParseOneCharToken(state, 'L') && ParseType(state) &&
1191       ParseFloatNumber(state) &&
1192       ParseOneCharToken(state, 'E')) {
1193     return true;
1194   }
1195   *state = copy;
1196
1197   if (ParseOneCharToken(state, 'L') && ParseMangledName(state) &&
1198       ParseOneCharToken(state, 'E')) {
1199     return true;
1200   }
1201   *state = copy;
1202
1203   if (ParseTwoCharToken(state, "LZ") && ParseEncoding(state) &&
1204       ParseOneCharToken(state, 'E')) {
1205     return true;
1206   }
1207   *state = copy;
1208
1209   return false;
1210 }
1211
1212 // <local-name> := Z <(function) encoding> E <(entity) name>
1213 //                 [<discriminator>]
1214 //              := Z <(function) encoding> E s [<discriminator>]
1215 static bool ParseLocalName(State *state) {
1216   State copy = *state;
1217   if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
1218       ParseOneCharToken(state, 'E') && MaybeAppend(state, "::") &&
1219       ParseName(state) && Optional(ParseDiscriminator(state))) {
1220     return true;
1221   }
1222   *state = copy;
1223
1224   if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
1225       ParseTwoCharToken(state, "Es") && Optional(ParseDiscriminator(state))) {
1226     return true;
1227   }
1228   *state = copy;
1229   return false;
1230 }
1231
1232 // <discriminator> := _ <(non-negative) number>
1233 static bool ParseDiscriminator(State *state) {
1234   State copy = *state;
1235   if (ParseOneCharToken(state, '_') && ParseNumber(state, NULL)) {
1236     return true;
1237   }
1238   *state = copy;
1239   return false;
1240 }
1241
1242 // <substitution> ::= S_
1243 //                ::= S <seq-id> _
1244 //                ::= St, etc.
1245 static bool ParseSubstitution(State *state) {
1246   if (ParseTwoCharToken(state, "S_")) {
1247     MaybeAppend(state, "?");  // We don't support substitutions.
1248     return true;
1249   }
1250
1251   State copy = *state;
1252   if (ParseOneCharToken(state, 'S') && ParseSeqId(state) &&
1253       ParseOneCharToken(state, '_')) {
1254     MaybeAppend(state, "?");  // We don't support substitutions.
1255     return true;
1256   }
1257   *state = copy;
1258
1259   // Expand abbreviations like "St" => "std".
1260   if (ParseOneCharToken(state, 'S')) {
1261     const AbbrevPair *p;
1262     for (p = kSubstitutionList; p->abbrev != NULL; ++p) {
1263       if (state->mangled_cur[0] == p->abbrev[1]) {
1264         MaybeAppend(state, "std");
1265         if (p->real_name[0] != '\0') {
1266           MaybeAppend(state, "::");
1267           MaybeAppend(state, p->real_name);
1268         }
1269         ++state->mangled_cur;
1270         return true;
1271       }
1272     }
1273   }
1274   *state = copy;
1275   return false;
1276 }
1277
1278 // Parse <mangled-name>, optionally followed by either a function-clone suffix
1279 // or version suffix.  Returns true only if all of "mangled_cur" was consumed.
1280 static bool ParseTopLevelMangledName(State *state) {
1281   if (ParseMangledName(state)) {
1282     if (state->mangled_cur[0] != '\0') {
1283       // Drop trailing function clone suffix, if any.
1284       if (IsFunctionCloneSuffix(state->mangled_cur)) {
1285         return true;
1286       }
1287       // Append trailing version suffix if any.
1288       // ex. _Z3foo@@GLIBCXX_3.4
1289       if (state->mangled_cur[0] == '@') {
1290         MaybeAppend(state, state->mangled_cur);
1291         return true;
1292       }
1293       return false;  // Unconsumed suffix.
1294     }
1295     return true;
1296   }
1297   return false;
1298 }
1299
1300 // The demangler entry point.
1301 bool Demangle(const char *mangled, char *out, int out_size) {
1302   State state;
1303   InitState(&state, mangled, out, out_size);
1304   return ParseTopLevelMangledName(&state) && !state.overflowed;
1305 }
1306
1307 _END_GOOGLE_NAMESPACE_