Home | History | Annotate | Download | only in demangle 
      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 (name[-1] == 'K' || name[-1] == 'V') {
    546       // Special case, const/volatile apply as a single entity.
    547       assert(!cur_state_.suffixes.empty());
    548       size_t index = cur_state_.suffixes.size();
    549       cur_state_.suffixes[index-1].insert(0, suffix);
    550     } else {
    551       cur_state_.suffixes.push_back(suffix);
    552     }
    553     return name + 1;
    554   }
    555 
    556   case 'F': {
    557     std::string function_modifier;
    558     std::string function_type;
    559     if (!cur_state_.suffixes.empty()) {
    560       // If the first element starts with a ' ', then this modifies the
    561       // function itself.
    562       if (cur_state_.suffixes.back()[0] == ' ') {
    563         function_modifier = cur_state_.suffixes.back();
    564         cur_state_.suffixes.pop_back();
    565       }
    566       while (!cur_state_.suffixes.empty()) {
    567         function_type += cur_state_.suffixes.back();
    568         cur_state_.suffixes.pop_back();
    569       }
    570     }
    571 
    572     state_stack_.push(cur_state_);
    573 
    574     cur_state_.Clear();
    575 
    576     // The function parameter has this format:
    577     //   First argument is the function modifier.
    578     //   Second argument is the function type.
    579     //   Third argument will be the return function type but has not
    580     //     been parsed yet.
    581     //   Any other parameters are the arguments to the function. There
    582     //     must be at least one or this isn't valid.
    583     cur_state_.args.push_back(function_modifier);
    584     cur_state_.args.push_back(function_type);
    585 
    586     parse_funcs_.push_back(parse_func_);
    587     parse_func_ = &Demangler::ParseFunctionArgument;
    588     return name + 1;
    589   }
    590 
    591   case 'N':
    592     parse_funcs_.push_back(parse_func_);
    593     parse_func_ = &Demangler::ParseComplexArgument;
    594     return name + 1;
    595 
    596   case 'S':
    597     name++;
    598     if (*name == 't') {
    599       cur_state_.str = "std::";
    600       return name + 1;
    601     }
    602     name = ParseS(name);
    603     if (name == nullptr) {
    604       return nullptr;
    605     }
    606     AppendArgument(cur_state_.str);
    607     cur_state_.str.clear();
    608     return name;
    609 
    610   case 'D':
    611     name++;
    612     if (*name >= 'a' && *name <= 'z') {
    613       const char* arg = Demangler::kDTypes[*name - 'a'];
    614       if (arg == nullptr) {
    615         return nullptr;
    616       }
    617       AppendArgument(arg);
    618       return name + 1;
    619     }
    620     return nullptr;
    621 
    622   case 'I':
    623     // Save the current argument state.
    624     state_stack_.push(cur_state_);
    625     cur_state_.Clear();
    626 
    627     parse_funcs_.push_back(parse_func_);
    628     parse_func_ = &Demangler::ParseTemplateArguments;
    629     return name + 1;
    630 
    631   case 'v':
    632     AppendArgument("void");
    633     return name + 1;
    634 
    635   default:
    636     if (*name >= 'a' && *name <= 'z') {
    637       const char* arg = Demangler::kTypes[*name - 'a'];
    638       if (arg == nullptr) {
    639         return nullptr;
    640       }
    641       AppendArgument(arg);
    642       return name + 1;
    643     } else if (std::isdigit(*name)) {
    644       std::string arg = cur_state_.str;
    645       name = GetStringFromLength(name, &arg);
    646       if (name == nullptr) {
    647         return nullptr;
    648       }
    649       Save(arg, true);
    650       if (*name == 'I') {
    651         // There is one case where this argument is not complete, and that's
    652         // where this is a template argument.
    653         cur_state_.str = arg;
    654       } else {
    655         AppendArgument(arg);
    656         cur_state_.str.clear();
    657       }
    658       return name;
    659     }
    660   }
    661   return nullptr;
    662 }
    663 
    664 const char* Demangler::ParseTemplateArgumentsComplex(const char* name) {
    665   if (*name == 'E') {
    666     if (parse_funcs_.empty()) {
    667       return nullptr;
    668     }
    669     parse_func_ = parse_funcs_.back();
    670     parse_funcs_.pop_back();
    671     FinalizeTemplate();
    672     Save(cur_state_.str, false);
    673     return name + 1;
    674   }
    675   return ParseArguments(name);
    676 }
    677 
    678 const char* Demangler::ParseTemplateArguments(const char* name) {
    679   if (*name == 'E') {
    680     if (parse_funcs_.empty()) {
    681       return nullptr;
    682     }
    683     parse_func_ = parse_funcs_.back();
    684     parse_funcs_.pop_back();
    685     FinalizeTemplate();
    686     AppendArgument(cur_state_.str);
    687     cur_state_.str.clear();
    688     return name + 1;
    689   }
    690   return ParseArguments(name);
    691 }
    692 
    693 const char* Demangler::FindFunctionName(const char* name) {
    694   if (*name == 'N') {
    695     parse_funcs_.push_back(&Demangler::ParseArguments);
    696     parse_func_ = &Demangler::ParseFunctionName;
    697     return name + 1;
    698   }
    699 
    700   if (std::isdigit(*name)) {
    701     name = GetStringFromLength(name, &function_name_);
    702   } else {
    703     name = AppendOperatorString(name);
    704     function_name_ = cur_state_.str;
    705   }
    706   parse_func_ = &Demangler::ParseArguments;
    707   cur_state_.Clear();
    708   return name;
    709 }
    710 
    711 std::string Demangler::Parse(const char* name, size_t max_length) {
    712   if (name[0] == '\0' || name[0] != '_' || name[1] == '\0' || name[1] != 'Z') {
    713     // Name is not mangled.
    714     return name;
    715   }
    716 
    717   Clear();
    718 
    719   parse_func_ = &Demangler::FindFunctionName;
    720   parse_funcs_.push_back(&Demangler::Fail);
    721   const char* cur_name = name + 2;
    722   while (cur_name != nullptr && *cur_name != '\0'
    723       && static_cast<size_t>(cur_name - name) < max_length) {
    724     cur_name = (this->*parse_func_)(cur_name);
    725   }
    726   if (cur_name == nullptr || *cur_name != '\0' || function_name_.empty()) {
    727     return name;
    728   }
    729 
    730   std::string arg_str;
    731   if (cur_state_.args.size() == 1 && cur_state_.args[0] == "void") {
    732     // If the only argument is void, then don't print any args.
    733     arg_str = "()";
    734   } else {
    735     arg_str = GetArgumentsString();
    736     if (!arg_str.empty()) {
    737       arg_str = '(' + arg_str + ')';
    738     }
    739   }
    740   return function_name_ + arg_str + function_suffix_;
    741 }
    742 
    743 std::string demangle(const char* name) {
    744   Demangler demangler;
    745   return demangler.Parse(name);
    746 }
    747