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