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