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