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
Save(const std::string & str,bool is_name)30 void Demangler::Save(const std::string& str, bool is_name) {
31 saves_.push_back(str);
32 last_save_name_ = is_name;
33 }
34
GetArgumentsString()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
AppendOperatorString(const char * name)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
GetStringFromLength(const char * name,std::string * str)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
AppendCurrent(const std::string & str)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
AppendCurrent(const char * str)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
ParseS(const char * name)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
ParseFunctionName(const char * name)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
ParseComplexArgument(const char * name)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
FinalizeTemplate()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
ParseComplexString(const char * name)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
AppendArgument(const std::string & str)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
ParseFunctionArgument(const char * name)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
ParseArguments(const char * name)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
ParseTemplateArgumentsComplex(const char * name)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
ParseTemplateArguments(const char * name)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
FindFunctionName(const char * name)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
Parse(const char * name,size_t max_length)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
demangle(const char * name)743 std::string demangle(const char* name) {
744 Demangler demangler;
745 return demangler.Parse(name);
746 }
747