src/demangle.cc

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