1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include <assert.h> 18 19 #include <cctype> 20 #include <stack> 21 #include <string> 22 #include <vector> 23 24 #include "Demangler.h" 25 26 constexpr const char* Demangler::kTypes[]; 27 constexpr const char* Demangler::kDTypes[]; 28 constexpr const char* Demangler::kSTypes[]; 29 30 void Demangler::Save(const std::string& str, bool is_name) { 31 saves_.push_back(str); 32 last_save_name_ = is_name; 33 } 34 35 std::string Demangler::GetArgumentsString() { 36 size_t num_args = cur_state_.args.size(); 37 std::string arg_str; 38 if (num_args > 0) { 39 arg_str = cur_state_.args[0]; 40 for (size_t i = 1; i < num_args; i++) { 41 arg_str += ", " + cur_state_.args[i]; 42 } 43 } 44 return arg_str; 45 } 46 47 const char* Demangler::AppendOperatorString(const char* name) { 48 const char* oper = nullptr; 49 switch (*name) { 50 case 'a': 51 name++; 52 switch (*name) { 53 case 'a': 54 oper = "operator&&"; 55 break; 56 case 'd': 57 case 'n': 58 oper = "operator&"; 59 break; 60 case 'N': 61 oper = "operator&="; 62 break; 63 case 'S': 64 oper = "operator="; 65 break; 66 } 67 break; 68 case 'c': 69 name++; 70 switch (*name) { 71 case 'l': 72 oper = "operator()"; 73 break; 74 case 'm': 75 oper = "operator,"; 76 break; 77 case 'o': 78 oper = "operator~"; 79 break; 80 } 81 break; 82 case 'd': 83 name++; 84 switch (*name) { 85 case 'a': 86 oper = "operator delete[]"; 87 break; 88 case 'e': 89 oper = "operator*"; 90 break; 91 case 'l': 92 oper = "operator delete"; 93 break; 94 case 'v': 95 oper = "operator/"; 96 break; 97 case 'V': 98 oper = "operator/="; 99 break; 100 } 101 break; 102 case 'e': 103 name++; 104 switch (*name) { 105 case 'o': 106 oper = "operator^"; 107 break; 108 case 'O': 109 oper = "operator^="; 110 break; 111 case 'q': 112 oper = "operator=="; 113 break; 114 } 115 break; 116 case 'g': 117 name++; 118 switch (*name) { 119 case 'e': 120 oper = "operator>="; 121 break; 122 case 't': 123 oper = "operator>"; 124 break; 125 } 126 break; 127 case 'i': 128 name++; 129 switch (*name) { 130 case 'x': 131 oper = "operator[]"; 132 break; 133 } 134 break; 135 case 'l': 136 name++; 137 switch (*name) { 138 case 'e': 139 oper = "operator<="; 140 break; 141 case 's': 142 oper = "operator<<"; 143 break; 144 case 'S': 145 oper = "operator<<="; 146 break; 147 case 't': 148 oper = "operator<"; 149 break; 150 } 151 break; 152 case 'm': 153 name++; 154 switch (*name) { 155 case 'i': 156 oper = "operator-"; 157 break; 158 case 'I': 159 oper = "operator-="; 160 break; 161 case 'l': 162 oper = "operator*"; 163 break; 164 case 'L': 165 oper = "operator*="; 166 break; 167 case 'm': 168 oper = "operator--"; 169 break; 170 } 171 break; 172 case 'n': 173 name++; 174 switch (*name) { 175 case 'a': 176 oper = "operator new[]"; 177 break; 178 case 'e': 179 oper = "operator!="; 180 break; 181 case 'g': 182 oper = "operator-"; 183 break; 184 case 't': 185 oper = "operator!"; 186 break; 187 case 'w': 188 oper = "operator new"; 189 break; 190 } 191 break; 192 case 'o': 193 name++; 194 switch (*name) { 195 case 'o': 196 oper = "operator||"; 197 break; 198 case 'r': 199 oper = "operator|"; 200 break; 201 case 'R': 202 oper = "operator|="; 203 break; 204 } 205 break; 206 case 'p': 207 name++; 208 switch (*name) { 209 case 'm': 210 oper = "operator->*"; 211 break; 212 case 'l': 213 oper = "operator+"; 214 break; 215 case 'L': 216 oper = "operator+="; 217 break; 218 case 'p': 219 oper = "operator++"; 220 break; 221 case 's': 222 oper = "operator+"; 223 break; 224 case 't': 225 oper = "operator->"; 226 break; 227 } 228 break; 229 case 'q': 230 name++; 231 switch (*name) { 232 case 'u': 233 oper = "operator?"; 234 break; 235 } 236 break; 237 case 'r': 238 name++; 239 switch (*name) { 240 case 'm': 241 oper = "operator%"; 242 break; 243 case 'M': 244 oper = "operator%="; 245 break; 246 case 's': 247 oper = "operator>>"; 248 break; 249 case 'S': 250 oper = "operator>>="; 251 break; 252 } 253 break; 254 } 255 if (oper == nullptr) { 256 return nullptr; 257 } 258 AppendCurrent(oper); 259 cur_state_.last_save = oper; 260 return name + 1; 261 } 262 263 const char* Demangler::GetStringFromLength(const char* name, std::string* str) { 264 assert(std::isdigit(*name)); 265 266 size_t length = *name - '0'; 267 name++; 268 while (*name != '\0' && std::isdigit(*name)) { 269 length = length * 10 + *name - '0'; 270 name++; 271 } 272 273 std::string read_str; 274 while (*name != '\0' && length != 0) { 275 read_str += *name; 276 name++; 277 length--; 278 } 279 if (length != 0) { 280 return nullptr; 281 } 282 // Special replacement of _GLOBAL__N_1 to (anonymous namespace). 283 if (read_str == "_GLOBAL__N_1") { 284 *str += "(anonymous namespace)"; 285 } else { 286 *str += read_str; 287 } 288 return name; 289 } 290 291 void Demangler::AppendCurrent(const std::string& str) { 292 if (!cur_state_.str.empty()) { 293 cur_state_.str += "::"; 294 } 295 cur_state_.str += str; 296 } 297 298 void Demangler::AppendCurrent(const char* str) { 299 if (!cur_state_.str.empty()) { 300 cur_state_.str += "::"; 301 } 302 cur_state_.str += str; 303 } 304 305 const char* Demangler::ParseS(const char* name) { 306 if (std::islower(*name)) { 307 const char* type = kSTypes[*name - 'a']; 308 if (type == nullptr) { 309 return nullptr; 310 } 311 AppendCurrent(type); 312 return name + 1; 313 } 314 315 if (saves_.empty()) { 316 return nullptr; 317 } 318 319 if (*name == '_') { 320 last_save_name_ = false; 321 AppendCurrent(saves_[0]); 322 return name + 1; 323 } 324 325 bool isdigit = std::isdigit(*name); 326 if (!isdigit && !std::isupper(*name)) { 327 return nullptr; 328 } 329 330 size_t index; 331 if (isdigit) { 332 index = *name - '0' + 1; 333 } else { 334 index = *name - 'A' + 11; 335 } 336 name++; 337 if (*name != '_') { 338 return nullptr; 339 } 340 341 if (index >= saves_.size()) { 342 return nullptr; 343 } 344 345 last_save_name_ = false; 346 AppendCurrent(saves_[index]); 347 return name + 1; 348 } 349 350 const char* Demangler::ParseFunctionName(const char* name) { 351 if (*name == 'E') { 352 if (parse_funcs_.empty()) { 353 return nullptr; 354 } 355 parse_func_ = parse_funcs_.back(); 356 parse_funcs_.pop_back(); 357 358 // Remove the last saved part so that the full function name is not saved. 359 // But only if the last save was not something like a substitution. 360 if (!saves_.empty() && last_save_name_) { 361 saves_.pop_back(); 362 } 363 364 function_name_ = cur_state_.str; 365 while (!cur_state_.suffixes.empty()) { 366 function_suffix_ += cur_state_.suffixes.back(); 367 cur_state_.suffixes.pop_back(); 368 } 369 cur_state_.Clear(); 370 371 return name + 1; 372 } 373 374 return ParseComplexString(name); 375 } 376 377 const char* Demangler::ParseComplexArgument(const char* name) { 378 if (*name == 'E') { 379 if (parse_funcs_.empty()) { 380 return nullptr; 381 } 382 parse_func_ = parse_funcs_.back(); 383 parse_funcs_.pop_back(); 384 385 AppendArgument(cur_state_.str); 386 cur_state_.str.clear(); 387 388 return name + 1; 389 } 390 391 return ParseComplexString(name); 392 } 393 394 void Demangler::FinalizeTemplate() { 395 std::string arg_str(GetArgumentsString()); 396 cur_state_ = state_stack_.top(); 397 state_stack_.pop(); 398 cur_state_.str += '<' + arg_str + '>'; 399 } 400 401 const char* Demangler::ParseComplexString(const char* name) { 402 if (*name == 'S') { 403 name++; 404 if (*name == 't') { 405 AppendCurrent("std"); 406 return name + 1; 407 } 408 return ParseS(name); 409 } 410 if (*name == 'L') { 411 name++; 412 if (!std::isdigit(*name)) { 413 return nullptr; 414 } 415 } 416 if (std::isdigit(*name)) { 417 std::string str; 418 name = GetStringFromLength(name, &str); 419 if (name == nullptr) { 420 return name; 421 } 422 AppendCurrent(str); 423 Save(cur_state_.str, true); 424 cur_state_.last_save = std::move(str); 425 return name; 426 } 427 if (*name == 'D') { 428 name++; 429 if (saves_.empty() || (*name != '0' && *name != '1' && *name != '2' 430 && *name != '5')) { 431 return nullptr; 432 } 433 last_save_name_ = false; 434 AppendCurrent("~" + cur_state_.last_save); 435 return name + 1; 436 } 437 if (*name == 'C') { 438 name++; 439 if (saves_.empty() || (*name != '1' && *name != '2' && *name != '3' 440 && *name != '5')) { 441 return nullptr; 442 } 443 last_save_name_ = false; 444 AppendCurrent(cur_state_.last_save); 445 return name + 1; 446 } 447 if (*name == 'K') { 448 cur_state_.suffixes.push_back(" const"); 449 return name + 1; 450 } 451 if (*name == 'V') { 452 cur_state_.suffixes.push_back(" volatile"); 453 return name + 1; 454 } 455 if (*name == 'I') { 456 // Save the current argument state. 457 state_stack_.push(cur_state_); 458 cur_state_.Clear(); 459 460 parse_funcs_.push_back(parse_func_); 461 parse_func_ = &Demangler::ParseTemplateArgumentsComplex; 462 return name + 1; 463 } 464 name = AppendOperatorString(name); 465 if (name != nullptr) { 466 Save(cur_state_.str, true); 467 } 468 return name; 469 } 470 471 void Demangler::AppendArgument(const std::string& str) { 472 std::string arg(str); 473 while (!cur_state_.suffixes.empty()) { 474 arg += cur_state_.suffixes.back(); 475 cur_state_.suffixes.pop_back(); 476 Save(arg, false); 477 } 478 cur_state_.args.push_back(arg); 479 } 480 481 const char* Demangler::ParseFunctionArgument(const char* name) { 482 if (*name == 'E') { 483 // The first argument is the function modifier. 484 // The second argument is the function type. 485 // The third argument is the return type of the function. 486 // The rest of the arguments are the function arguments. 487 size_t num_args = cur_state_.args.size(); 488 if (num_args < 4) { 489 return nullptr; 490 } 491 std::string function_modifier = cur_state_.args[0]; 492 std::string function_type = cur_state_.args[1]; 493 494 std::string str = cur_state_.args[2] + ' '; 495 if (!cur_state_.args[1].empty()) { 496 str += '(' + cur_state_.args[1] + ')'; 497 } 498 499 if (num_args == 4 && cur_state_.args[3] == "void") { 500 str += "()"; 501 } else { 502 str += '(' + cur_state_.args[3]; 503 for (size_t i = 4; i < num_args; i++) { 504 str += ", " + cur_state_.args[i]; 505 } 506 str += ')'; 507 } 508 str += cur_state_.args[0]; 509 510 cur_state_ = state_stack_.top(); 511 state_stack_.pop(); 512 cur_state_.args.emplace_back(std::move(str)); 513 514 parse_func_ = parse_funcs_.back(); 515 parse_funcs_.pop_back(); 516 return name + 1; 517 } 518 return ParseArguments(name); 519 } 520 521 const char* Demangler::ParseArguments(const char* name) { 522 switch (*name) { 523 case 'P': 524 cur_state_.suffixes.push_back("*"); 525 return name + 1; 526 527 case 'R': 528 // This should always be okay because the string is guaranteed to have 529 // at least two characters before this. A mangled string always starts 530 // with _Z. 531 if (name[-1] != 'R') { 532 // Multiple 'R's in a row only add a single &. 533 cur_state_.suffixes.push_back("&"); 534 } 535 return name + 1; 536 537 case 'K': 538 case 'V': { 539 const char* suffix; 540 if (*name == 'K') { 541 suffix = " const"; 542 } else { 543 suffix = " volatile"; 544 } 545 if (!cur_state_.suffixes.empty() && (name[-1] == 'K' || name[-1] == 'V')) { 546 // Special case, const/volatile apply as a single entity. 547 size_t index = cur_state_.suffixes.size(); 548 cur_state_.suffixes[index-1].insert(0, suffix); 549 } else { 550 cur_state_.suffixes.push_back(suffix); 551 } 552 return name + 1; 553 } 554 555 case 'F': { 556 std::string function_modifier; 557 std::string function_type; 558 if (!cur_state_.suffixes.empty()) { 559 // If the first element starts with a ' ', then this modifies the 560 // function itself. 561 if (cur_state_.suffixes.back()[0] == ' ') { 562 function_modifier = cur_state_.suffixes.back(); 563 cur_state_.suffixes.pop_back(); 564 } 565 while (!cur_state_.suffixes.empty()) { 566 function_type += cur_state_.suffixes.back(); 567 cur_state_.suffixes.pop_back(); 568 } 569 } 570 571 state_stack_.push(cur_state_); 572 573 cur_state_.Clear(); 574 575 // The function parameter has this format: 576 // First argument is the function modifier. 577 // Second argument is the function type. 578 // Third argument will be the return function type but has not 579 // been parsed yet. 580 // Any other parameters are the arguments to the function. There 581 // must be at least one or this isn't valid. 582 cur_state_.args.push_back(function_modifier); 583 cur_state_.args.push_back(function_type); 584 585 parse_funcs_.push_back(parse_func_); 586 parse_func_ = &Demangler::ParseFunctionArgument; 587 return name + 1; 588 } 589 590 case 'N': 591 parse_funcs_.push_back(parse_func_); 592 parse_func_ = &Demangler::ParseComplexArgument; 593 return name + 1; 594 595 case 'S': 596 name++; 597 if (*name == 't') { 598 cur_state_.str = "std::"; 599 return name + 1; 600 } 601 name = ParseS(name); 602 if (name == nullptr) { 603 return nullptr; 604 } 605 AppendArgument(cur_state_.str); 606 cur_state_.str.clear(); 607 return name; 608 609 case 'D': 610 name++; 611 if (*name >= 'a' && *name <= 'z') { 612 const char* arg = Demangler::kDTypes[*name - 'a']; 613 if (arg == nullptr) { 614 return nullptr; 615 } 616 AppendArgument(arg); 617 return name + 1; 618 } 619 return nullptr; 620 621 case 'I': 622 // Save the current argument state. 623 state_stack_.push(cur_state_); 624 cur_state_.Clear(); 625 626 parse_funcs_.push_back(parse_func_); 627 parse_func_ = &Demangler::ParseTemplateArguments; 628 return name + 1; 629 630 case 'v': 631 AppendArgument("void"); 632 return name + 1; 633 634 default: 635 if (*name >= 'a' && *name <= 'z') { 636 const char* arg = Demangler::kTypes[*name - 'a']; 637 if (arg == nullptr) { 638 return nullptr; 639 } 640 AppendArgument(arg); 641 return name + 1; 642 } else if (std::isdigit(*name)) { 643 std::string arg = cur_state_.str; 644 name = GetStringFromLength(name, &arg); 645 if (name == nullptr) { 646 return nullptr; 647 } 648 Save(arg, true); 649 if (*name == 'I') { 650 // There is one case where this argument is not complete, and that's 651 // where this is a template argument. 652 cur_state_.str = arg; 653 } else { 654 AppendArgument(arg); 655 cur_state_.str.clear(); 656 } 657 return name; 658 } 659 } 660 return nullptr; 661 } 662 663 const char* Demangler::ParseTemplateArgumentsComplex(const char* name) { 664 if (*name == 'E') { 665 if (parse_funcs_.empty()) { 666 return nullptr; 667 } 668 parse_func_ = parse_funcs_.back(); 669 parse_funcs_.pop_back(); 670 FinalizeTemplate(); 671 Save(cur_state_.str, false); 672 return name + 1; 673 } 674 return ParseArguments(name); 675 } 676 677 const char* Demangler::ParseTemplateArguments(const char* name) { 678 if (*name == 'E') { 679 if (parse_funcs_.empty()) { 680 return nullptr; 681 } 682 parse_func_ = parse_funcs_.back(); 683 parse_funcs_.pop_back(); 684 FinalizeTemplate(); 685 AppendArgument(cur_state_.str); 686 cur_state_.str.clear(); 687 return name + 1; 688 } 689 return ParseArguments(name); 690 } 691 692 const char* Demangler::FindFunctionName(const char* name) { 693 if (*name == 'N') { 694 parse_funcs_.push_back(&Demangler::ParseArguments); 695 parse_func_ = &Demangler::ParseFunctionName; 696 return name + 1; 697 } 698 699 if (std::isdigit(*name)) { 700 name = GetStringFromLength(name, &function_name_); 701 } else if (*name == 'L' && std::isdigit(name[1])) { 702 name = GetStringFromLength(name + 1, &function_name_); 703 } else { 704 name = AppendOperatorString(name); 705 function_name_ = cur_state_.str; 706 } 707 parse_func_ = &Demangler::ParseArguments; 708 cur_state_.Clear(); 709 return name; 710 } 711 712 std::string Demangler::Parse(const char* name, size_t max_length) { 713 if (name[0] == '\0' || name[0] != '_' || name[1] == '\0' || name[1] != 'Z') { 714 // Name is not mangled. 715 return name; 716 } 717 718 Clear(); 719 720 parse_func_ = &Demangler::FindFunctionName; 721 parse_funcs_.push_back(&Demangler::Fail); 722 const char* cur_name = name + 2; 723 while (cur_name != nullptr && *cur_name != '\0' 724 && static_cast<size_t>(cur_name - name) < max_length) { 725 cur_name = (this->*parse_func_)(cur_name); 726 } 727 if (cur_name == nullptr || *cur_name != '\0' || function_name_.empty() || 728 !cur_state_.suffixes.empty()) { 729 return name; 730 } 731 732 std::string arg_str; 733 if (cur_state_.args.size() == 1 && cur_state_.args[0] == "void") { 734 // If the only argument is void, then don't print any args. 735 arg_str = "()"; 736 } else { 737 arg_str = GetArgumentsString(); 738 if (!arg_str.empty()) { 739 arg_str = '(' + arg_str + ')'; 740 } 741 } 742 return function_name_ + arg_str + function_suffix_; 743 } 744 745 std::string demangle(const char* name) { 746 Demangler demangler; 747 return demangler.Parse(name); 748 } 749