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