1// Copyright 2018 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// For reference check out:
16// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling
17//
18// Note that we only have partial C++11 support yet.
19
20#include "absl/debugging/internal/demangle.h"
21
22#include <cstdint>
23#include <cstdio>
24#include <limits>
25
26namespace absl {
27namespace debugging_internal {
28
29typedef struct {
30 const char *abbrev;
31 const char *real_name;
32 // Number of arguments in <expression> context, or 0 if disallowed.
33 int arity;
34} AbbrevPair;
35
36// List of operators from Itanium C++ ABI.
37static const AbbrevPair kOperatorList[] = {
38 // New has special syntax (not currently supported).
39 {"nw", "new", 0},
40 {"na", "new[]", 0},
41
42 // Works except that the 'gs' prefix is not supported.
43 {"dl", "delete", 1},
44 {"da", "delete[]", 1},
45
46 {"ps", "+", 1}, // "positive"
47 {"ng", "-", 1}, // "negative"
48 {"ad", "&", 1}, // "address-of"
49 {"de", "*", 1}, // "dereference"
50 {"co", "~", 1},
51
52 {"pl", "+", 2},
53 {"mi", "-", 2},
54 {"ml", "*", 2},
55 {"dv", "/", 2},
56 {"rm", "%", 2},
57 {"an", "&", 2},
58 {"or", "|", 2},
59 {"eo", "^", 2},
60 {"aS", "=", 2},
61 {"pL", "+=", 2},
62 {"mI", "-=", 2},
63 {"mL", "*=", 2},
64 {"dV", "/=", 2},
65 {"rM", "%=", 2},
66 {"aN", "&=", 2},
67 {"oR", "|=", 2},
68 {"eO", "^=", 2},
69 {"ls", "<<", 2},
70 {"rs", ">>", 2},
71 {"lS", "<<=", 2},
72 {"rS", ">>=", 2},
73 {"eq", "==", 2},
74 {"ne", "!=", 2},
75 {"lt", "<", 2},
76 {"gt", ">", 2},
77 {"le", "<=", 2},
78 {"ge", ">=", 2},
79 {"nt", "!", 1},
80 {"aa", "&&", 2},
81 {"oo", "||", 2},
82 {"pp", "++", 1},
83 {"mm", "--", 1},
84 {"cm", ",", 2},
85 {"pm", "->*", 2},
86 {"pt", "->", 0}, // Special syntax
87 {"cl", "()", 0}, // Special syntax
88 {"ix", "[]", 2},
89 {"qu", "?", 3},
90 {"st", "sizeof", 0}, // Special syntax
91 {"sz", "sizeof", 1}, // Not a real operator name, but used in expressions.
92 {nullptr, nullptr, 0},
93};
94
95// List of builtin types from Itanium C++ ABI.
96static const AbbrevPair kBuiltinTypeList[] = {
97 {"v", "void", 0},
98 {"w", "wchar_t", 0},
99 {"b", "bool", 0},
100 {"c", "char", 0},
101 {"a", "signed char", 0},
102 {"h", "unsigned char", 0},
103 {"s", "short", 0},
104 {"t", "unsigned short", 0},
105 {"i", "int", 0},
106 {"j", "unsigned int", 0},
107 {"l", "long", 0},
108 {"m", "unsigned long", 0},
109 {"x", "long long", 0},
110 {"y", "unsigned long long", 0},
111 {"n", "__int128", 0},
112 {"o", "unsigned __int128", 0},
113 {"f", "float", 0},
114 {"d", "double", 0},
115 {"e", "long double", 0},
116 {"g", "__float128", 0},
117 {"z", "ellipsis", 0},
118 {nullptr, nullptr, 0},
119};
120
121// List of substitutions Itanium C++ ABI.
122static const AbbrevPair kSubstitutionList[] = {
123 {"St", "", 0},
124 {"Sa", "allocator", 0},
125 {"Sb", "basic_string", 0},
126 // std::basic_string<char, std::char_traits<char>,std::allocator<char> >
127 {"Ss", "string", 0},
128 // std::basic_istream<char, std::char_traits<char> >
129 {"Si", "istream", 0},
130 // std::basic_ostream<char, std::char_traits<char> >
131 {"So", "ostream", 0},
132 // std::basic_iostream<char, std::char_traits<char> >
133 {"Sd", "iostream", 0},
134 {nullptr, nullptr, 0},
135};
136
137// State needed for demangling. This struct is copied in almost every stack
138// frame, so every byte counts.
139typedef struct {
140 int mangled_idx; // Cursor of mangled name.
141 int out_cur_idx; // Cursor of output std::string.
142 int prev_name_idx; // For constructors/destructors.
143 signed int prev_name_length : 16; // For constructors/destructors.
144 signed int nest_level : 15; // For nested names.
145 unsigned int append : 1; // Append flag.
146 // Note: for some reason MSVC can't pack "bool append : 1" into the same int
147 // with the above two fields, so we use an int instead. Amusingly it can pack
148 // "signed bool" as expected, but relying on that to continue to be a legal
149 // type seems ill-advised (as it's illegal in at least clang).
150} ParseState;
151
152static_assert(sizeof(ParseState) == 4 * sizeof(int),
153 "unexpected size of ParseState");
154
155// One-off state for demangling that's not subject to backtracking -- either
156// constant data, data that's intentionally immune to backtracking (steps), or
157// data that would never be changed by backtracking anyway (recursion_depth).
158//
159// Only one copy of this exists for each call to Demangle, so the size of this
160// struct is nearly inconsequential.
161typedef struct {
162 const char *mangled_begin; // Beginning of input std::string.
163 char *out; // Beginning of output std::string.
164 int out_end_idx; // One past last allowed output character.
165 int recursion_depth; // For stack exhaustion prevention.
166 int steps; // Cap how much work we'll do, regardless of depth.
167 ParseState parse_state; // Backtrackable state copied for most frames.
168} State;
169
170namespace {
171// Prevent deep recursion / stack exhaustion.
172// Also prevent unbounded handling of complex inputs.
173class ComplexityGuard {
174 public:
175 explicit ComplexityGuard(State *state) : state_(state) {
176 ++state->recursion_depth;
177 ++state->steps;
178 }
179 ~ComplexityGuard() { --state_->recursion_depth; }
180
181 // 256 levels of recursion seems like a reasonable upper limit on depth.
182 // 128 is not enough to demagle synthetic tests from demangle_unittest.txt:
183 // "_ZaaZZZZ..." and "_ZaaZcvZcvZ..."
184 static constexpr int kRecursionDepthLimit = 256;
185
186 // We're trying to pick a charitable upper-limit on how many parse steps are
187 // necessary to handle something that a human could actually make use of.
188 // This is mostly in place as a bound on how much work we'll do if we are
189 // asked to demangle an mangled name from an untrusted source, so it should be
190 // much larger than the largest expected symbol, but much smaller than the
191 // amount of work we can do in, e.g., a second.
192 //
193 // Some real-world symbols from an arbitrary binary started failing between
194 // 2^12 and 2^13, so we multiply the latter by an extra factor of 16 to set
195 // the limit.
196 //
197 // Spending one second on 2^17 parse steps would require each step to take
198 // 7.6us, or ~30000 clock cycles, so it's safe to say this can be done in
199 // under a second.
200 static constexpr int kParseStepsLimit = 1 << 17;
201
202 bool IsTooComplex() const {
203 return state_->recursion_depth > kRecursionDepthLimit ||
204 state_->steps > kParseStepsLimit;
205 }
206
207 private:
208 State *state_;
209};
210} // namespace
211
212// We don't use strlen() in libc since it's not guaranteed to be async
213// signal safe.
214static size_t StrLen(const char *str) {
215 size_t len = 0;
216 while (*str != '\0') {
217 ++str;
218 ++len;
219 }
220 return len;
221}
222
223// Returns true if "str" has at least "n" characters remaining.
224static bool AtLeastNumCharsRemaining(const char *str, int n) {
225 for (int i = 0; i < n; ++i) {
226 if (str[i] == '\0') {
227 return false;
228 }
229 }
230 return true;
231}
232
233// Returns true if "str" has "prefix" as a prefix.
234static bool StrPrefix(const char *str, const char *prefix) {
235 size_t i = 0;
236 while (str[i] != '\0' && prefix[i] != '\0' && str[i] == prefix[i]) {
237 ++i;
238 }
239 return prefix[i] == '\0'; // Consumed everything in "prefix".
240}
241
242static void InitState(State *state, const char *mangled, char *out,
243 int out_size) {
244 state->mangled_begin = mangled;
245 state->out = out;
246 state->out_end_idx = out_size;
247 state->recursion_depth = 0;
248 state->steps = 0;
249
250 state->parse_state.mangled_idx = 0;
251 state->parse_state.out_cur_idx = 0;
252 state->parse_state.prev_name_idx = 0;
253 state->parse_state.prev_name_length = -1;
254 state->parse_state.nest_level = -1;
255 state->parse_state.append = true;
256}
257
258static inline const char *RemainingInput(State *state) {
259 return &state->mangled_begin[state->parse_state.mangled_idx];
260}
261
262// Returns true and advances "mangled_idx" if we find "one_char_token"
263// at "mangled_idx" position. It is assumed that "one_char_token" does
264// not contain '\0'.
265static bool ParseOneCharToken(State *state, const char one_char_token) {
266 ComplexityGuard guard(state);
267 if (guard.IsTooComplex()) return false;
268 if (RemainingInput(state)[0] == one_char_token) {
269 ++state->parse_state.mangled_idx;
270 return true;
271 }
272 return false;
273}
274
275// Returns true and advances "mangled_cur" if we find "two_char_token"
276// at "mangled_cur" position. It is assumed that "two_char_token" does
277// not contain '\0'.
278static bool ParseTwoCharToken(State *state, const char *two_char_token) {
279 ComplexityGuard guard(state);
280 if (guard.IsTooComplex()) return false;
281 if (RemainingInput(state)[0] == two_char_token[0] &&
282 RemainingInput(state)[1] == two_char_token[1]) {
283 state->parse_state.mangled_idx += 2;
284 return true;
285 }
286 return false;
287}
288
289// Returns true and advances "mangled_cur" if we find any character in
290// "char_class" at "mangled_cur" position.
291static bool ParseCharClass(State *state, const char *char_class) {
292 ComplexityGuard guard(state);
293 if (guard.IsTooComplex()) return false;
294 if (RemainingInput(state)[0] == '\0') {
295 return false;
296 }
297 const char *p = char_class;
298 for (; *p != '\0'; ++p) {
299 if (RemainingInput(state)[0] == *p) {
300 ++state->parse_state.mangled_idx;
301 return true;
302 }
303 }
304 return false;
305}
306
307static bool ParseDigit(State *state, int *digit) {
308 char c = RemainingInput(state)[0];
309 if (ParseCharClass(state, "0123456789")) {
310 if (digit != nullptr) {
311 *digit = c - '0';
312 }
313 return true;
314 }
315 return false;
316}
317
318// This function is used for handling an optional non-terminal.
319static bool Optional(bool /*status*/) { return true; }
320
321// This function is used for handling <non-terminal>+ syntax.
322typedef bool (*ParseFunc)(State *);
323static bool OneOrMore(ParseFunc parse_func, State *state) {
324 if (parse_func(state)) {
325 while (parse_func(state)) {
326 }
327 return true;
328 }
329 return false;
330}
331
332// This function is used for handling <non-terminal>* syntax. The function
333// always returns true and must be followed by a termination token or a
334// terminating sequence not handled by parse_func (e.g.
335// ParseOneCharToken(state, 'E')).
336static bool ZeroOrMore(ParseFunc parse_func, State *state) {
337 while (parse_func(state)) {
338 }
339 return true;
340}
341
342// Append "str" at "out_cur_idx". If there is an overflow, out_cur_idx is
343// set to out_end_idx+1. The output string is ensured to
344// always terminate with '\0' as long as there is no overflow.
345static void Append(State *state, const char *const str, const int length) {
346 for (int i = 0; i < length; ++i) {
347 if (state->parse_state.out_cur_idx + 1 <
348 state->out_end_idx) { // +1 for '\0'
349 state->out[state->parse_state.out_cur_idx++] = str[i];
350 } else {
351 // signal overflow
352 state->parse_state.out_cur_idx = state->out_end_idx + 1;
353 break;
354 }
355 }
356 if (state->parse_state.out_cur_idx < state->out_end_idx) {
357 state->out[state->parse_state.out_cur_idx] =
358 '\0'; // Terminate it with '\0'
359 }
360}
361
362// We don't use equivalents in libc to avoid locale issues.
363static bool IsLower(char c) { return c >= 'a' && c <= 'z'; }
364
365static bool IsAlpha(char c) {
366 return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
367}
368
369static bool IsDigit(char c) { return c >= '0' && c <= '9'; }
370
371// Returns true if "str" is a function clone suffix. These suffixes are used
372// by GCC 4.5.x and later versions (and our locally-modified version of GCC
373// 4.4.x) to indicate functions which have been cloned during optimization.
374// We treat any sequence (.<alpha>+.<digit>+)+ as a function clone suffix.
375static bool IsFunctionCloneSuffix(const char *str) {
376 size_t i = 0;
377 while (str[i] != '\0') {
378 // Consume a single .<alpha>+.<digit>+ sequence.
379 if (str[i] != '.' || !IsAlpha(str[i + 1])) {
380 return false;
381 }
382 i += 2;
383 while (IsAlpha(str[i])) {
384 ++i;
385 }
386 if (str[i] != '.' || !IsDigit(str[i + 1])) {
387 return false;
388 }
389 i += 2;
390 while (IsDigit(str[i])) {
391 ++i;
392 }
393 }
394 return true; // Consumed everything in "str".
395}
396
397static bool EndsWith(State *state, const char chr) {
398 return state->parse_state.out_cur_idx > 0 &&
399 chr == state->out[state->parse_state.out_cur_idx - 1];
400}
401
402// Append "str" with some tweaks, iff "append" state is true.
403static void MaybeAppendWithLength(State *state, const char *const str,
404 const int length) {
405 if (state->parse_state.append && length > 0) {
406 // Append a space if the output buffer ends with '<' and "str"
407 // starts with '<' to avoid <<<.
408 if (str[0] == '<' && EndsWith(state, '<')) {
409 Append(state, " ", 1);
410 }
411 // Remember the last identifier name for ctors/dtors.
412 if (IsAlpha(str[0]) || str[0] == '_') {
413 state->parse_state.prev_name_idx = state->parse_state.out_cur_idx;
414 state->parse_state.prev_name_length = length;
415 }
416 Append(state, str, length);
417 }
418}
419
420// Appends a positive decimal number to the output if appending is enabled.
421static bool MaybeAppendDecimal(State *state, unsigned int val) {
422 // Max {32-64}-bit unsigned int is 20 digits.
423 constexpr size_t kMaxLength = 20;
424 char buf[kMaxLength];
425
426 // We can't use itoa or sprintf as neither is specified to be
427 // async-signal-safe.
428 if (state->parse_state.append) {
429 // We can't have a one-before-the-beginning pointer, so instead start with
430 // one-past-the-end and manipulate one character before the pointer.
431 char *p = &buf[kMaxLength];
432 do { // val=0 is the only input that should write a leading zero digit.
433 *--p = (val % 10) + '0';
434 val /= 10;
435 } while (p > buf && val != 0);
436
437 // 'p' landed on the last character we set. How convenient.
438 Append(state, p, kMaxLength - (p - buf));
439 }
440
441 return true;
442}
443
444// A convenient wrapper around MaybeAppendWithLength().
445// Returns true so that it can be placed in "if" conditions.
446static bool MaybeAppend(State *state, const char *const str) {
447 if (state->parse_state.append) {
448 int length = StrLen(str);
449 MaybeAppendWithLength(state, str, length);
450 }
451 return true;
452}
453
454// This function is used for handling nested names.
455static bool EnterNestedName(State *state) {
456 state->parse_state.nest_level = 0;
457 return true;
458}
459
460// This function is used for handling nested names.
461static bool LeaveNestedName(State *state, int16_t prev_value) {
462 state->parse_state.nest_level = prev_value;
463 return true;
464}
465
466// Disable the append mode not to print function parameters, etc.
467static bool DisableAppend(State *state) {
468 state->parse_state.append = false;
469 return true;
470}
471
472// Restore the append mode to the previous state.
473static bool RestoreAppend(State *state, bool prev_value) {
474 state->parse_state.append = prev_value;
475 return true;
476}
477
478// Increase the nest level for nested names.
479static void MaybeIncreaseNestLevel(State *state) {
480 if (state->parse_state.nest_level > -1) {
481 ++state->parse_state.nest_level;
482 }
483}
484
485// Appends :: for nested names if necessary.
486static void MaybeAppendSeparator(State *state) {
487 if (state->parse_state.nest_level >= 1) {
488 MaybeAppend(state, "::");
489 }
490}
491
492// Cancel the last separator if necessary.
493static void MaybeCancelLastSeparator(State *state) {
494 if (state->parse_state.nest_level >= 1 && state->parse_state.append &&
495 state->parse_state.out_cur_idx >= 2) {
496 state->parse_state.out_cur_idx -= 2;
497 state->out[state->parse_state.out_cur_idx] = '\0';
498 }
499}
500
501// Returns true if the identifier of the given length pointed to by
502// "mangled_cur" is anonymous namespace.
503static bool IdentifierIsAnonymousNamespace(State *state, int length) {
504 // Returns true if "anon_prefix" is a proper prefix of "mangled_cur".
505 static const char anon_prefix[] = "_GLOBAL__N_";
506 return (length > static_cast<int>(sizeof(anon_prefix) - 1) &&
507 StrPrefix(RemainingInput(state), anon_prefix));
508}
509
510// Forward declarations of our parsing functions.
511static bool ParseMangledName(State *state);
512static bool ParseEncoding(State *state);
513static bool ParseName(State *state);
514static bool ParseUnscopedName(State *state);
515static bool ParseNestedName(State *state);
516static bool ParsePrefix(State *state);
517static bool ParseUnqualifiedName(State *state);
518static bool ParseSourceName(State *state);
519static bool ParseLocalSourceName(State *state);
520static bool ParseUnnamedTypeName(State *state);
521static bool ParseNumber(State *state, int *number_out);
522static bool ParseFloatNumber(State *state);
523static bool ParseSeqId(State *state);
524static bool ParseIdentifier(State *state, int length);
525static bool ParseOperatorName(State *state, int *arity);
526static bool ParseSpecialName(State *state);
527static bool ParseCallOffset(State *state);
528static bool ParseNVOffset(State *state);
529static bool ParseVOffset(State *state);
530static bool ParseCtorDtorName(State *state);
531static bool ParseDecltype(State *state);
532static bool ParseType(State *state);
533static bool ParseCVQualifiers(State *state);
534static bool ParseBuiltinType(State *state);
535static bool ParseFunctionType(State *state);
536static bool ParseBareFunctionType(State *state);
537static bool ParseClassEnumType(State *state);
538static bool ParseArrayType(State *state);
539static bool ParsePointerToMemberType(State *state);
540static bool ParseTemplateParam(State *state);
541static bool ParseTemplateTemplateParam(State *state);
542static bool ParseTemplateArgs(State *state);
543static bool ParseTemplateArg(State *state);
544static bool ParseBaseUnresolvedName(State *state);
545static bool ParseUnresolvedName(State *state);
546static bool ParseExpression(State *state);
547static bool ParseExprPrimary(State *state);
548static bool ParseExprCastValue(State *state);
549static bool ParseLocalName(State *state);
550static bool ParseLocalNameSuffix(State *state);
551static bool ParseDiscriminator(State *state);
552static bool ParseSubstitution(State *state, bool accept_std);
553
554// Implementation note: the following code is a straightforward
555// translation of the Itanium C++ ABI defined in BNF with a couple of
556// exceptions.
557//
558// - Support GNU extensions not defined in the Itanium C++ ABI
559// - <prefix> and <template-prefix> are combined to avoid infinite loop
560// - Reorder patterns to shorten the code
561// - Reorder patterns to give greedier functions precedence
562// We'll mark "Less greedy than" for these cases in the code
563//
564// Each parsing function changes the parse state and returns true on
565// success, or returns false and doesn't change the parse state (note:
566// the parse-steps counter increases regardless of success or failure).
567// To ensure that the parse state isn't changed in the latter case, we
568// save the original state before we call multiple parsing functions
569// consecutively with &&, and restore it if unsuccessful. See
570// ParseEncoding() as an example of this convention. We follow the
571// convention throughout the code.
572//
573// Originally we tried to do demangling without following the full ABI
574// syntax but it turned out we needed to follow the full syntax to
575// parse complicated cases like nested template arguments. Note that
576// implementing a full-fledged demangler isn't trivial (libiberty's
577// cp-demangle.c has +4300 lines).
578//
579// Note that (foo) in <(foo) ...> is a modifier to be ignored.
580//
581// Reference:
582// - Itanium C++ ABI
583// <https://mentorembedded.github.io/cxx-abi/abi.html#mangling>
584
585// <mangled-name> ::= _Z <encoding>
586static bool ParseMangledName(State *state) {
587 ComplexityGuard guard(state);
588 if (guard.IsTooComplex()) return false;
589 return ParseTwoCharToken(state, "_Z") && ParseEncoding(state);
590}
591
592// <encoding> ::= <(function) name> <bare-function-type>
593// ::= <(data) name>
594// ::= <special-name>
595static bool ParseEncoding(State *state) {
596 ComplexityGuard guard(state);
597 if (guard.IsTooComplex()) return false;
598 // Implementing the first two productions together as <name>
599 // [<bare-function-type>] avoids exponential blowup of backtracking.
600 //
601 // Since Optional(...) can't fail, there's no need to copy the state for
602 // backtracking.
603 if (ParseName(state) && Optional(ParseBareFunctionType(state))) {
604 return true;
605 }
606
607 if (ParseSpecialName(state)) {
608 return true;
609 }
610 return false;
611}
612
613// <name> ::= <nested-name>
614// ::= <unscoped-template-name> <template-args>
615// ::= <unscoped-name>
616// ::= <local-name>
617static bool ParseName(State *state) {
618 ComplexityGuard guard(state);
619 if (guard.IsTooComplex()) return false;
620 if (ParseNestedName(state) || ParseLocalName(state)) {
621 return true;
622 }
623
624 // We reorganize the productions to avoid re-parsing unscoped names.
625 // - Inline <unscoped-template-name> productions:
626 // <name> ::= <substitution> <template-args>
627 // ::= <unscoped-name> <template-args>
628 // ::= <unscoped-name>
629 // - Merge the two productions that start with unscoped-name:
630 // <name> ::= <unscoped-name> [<template-args>]
631
632 ParseState copy = state->parse_state;
633 // "std<...>" isn't a valid name.
634 if (ParseSubstitution(state, /*accept_std=*/false) &&
635 ParseTemplateArgs(state)) {
636 return true;
637 }
638 state->parse_state = copy;
639
640 // Note there's no need to restore state after this since only the first
641 // subparser can fail.
642 return ParseUnscopedName(state) && Optional(ParseTemplateArgs(state));
643}
644
645// <unscoped-name> ::= <unqualified-name>
646// ::= St <unqualified-name>
647static bool ParseUnscopedName(State *state) {
648 ComplexityGuard guard(state);
649 if (guard.IsTooComplex()) return false;
650 if (ParseUnqualifiedName(state)) {
651 return true;
652 }
653
654 ParseState copy = state->parse_state;
655 if (ParseTwoCharToken(state, "St") && MaybeAppend(state, "std::") &&
656 ParseUnqualifiedName(state)) {
657 return true;
658 }
659 state->parse_state = copy;
660 return false;
661}
662
663// <ref-qualifer> ::= R // lvalue method reference qualifier
664// ::= O // rvalue method reference qualifier
665static inline bool ParseRefQualifier(State *state) {
666 return ParseCharClass(state, "OR");
667}
668
669// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
670// <unqualified-name> E
671// ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
672// <template-args> E
673static bool ParseNestedName(State *state) {
674 ComplexityGuard guard(state);
675 if (guard.IsTooComplex()) return false;
676 ParseState copy = state->parse_state;
677 if (ParseOneCharToken(state, 'N') && EnterNestedName(state) &&
678 Optional(ParseCVQualifiers(state)) &&
679 Optional(ParseRefQualifier(state)) && ParsePrefix(state) &&
680 LeaveNestedName(state, copy.nest_level) &&
681 ParseOneCharToken(state, 'E')) {
682 return true;
683 }
684 state->parse_state = copy;
685 return false;
686}
687
688// This part is tricky. If we literally translate them to code, we'll
689// end up infinite loop. Hence we merge them to avoid the case.
690//
691// <prefix> ::= <prefix> <unqualified-name>
692// ::= <template-prefix> <template-args>
693// ::= <template-param>
694// ::= <substitution>
695// ::= # empty
696// <template-prefix> ::= <prefix> <(template) unqualified-name>
697// ::= <template-param>
698// ::= <substitution>
699static bool ParsePrefix(State *state) {
700 ComplexityGuard guard(state);
701 if (guard.IsTooComplex()) return false;
702 bool has_something = false;
703 while (true) {
704 MaybeAppendSeparator(state);
705 if (ParseTemplateParam(state) ||
706 ParseSubstitution(state, /*accept_std=*/true) ||
707 ParseUnscopedName(state) ||
708 (ParseOneCharToken(state, 'M') && ParseUnnamedTypeName(state))) {
709 has_something = true;
710 MaybeIncreaseNestLevel(state);
711 continue;
712 }
713 MaybeCancelLastSeparator(state);
714 if (has_something && ParseTemplateArgs(state)) {
715 return ParsePrefix(state);
716 } else {
717 break;
718 }
719 }
720 return true;
721}
722
723// <unqualified-name> ::= <operator-name>
724// ::= <ctor-dtor-name>
725// ::= <source-name>
726// ::= <local-source-name> // GCC extension; see below.
727// ::= <unnamed-type-name>
728static bool ParseUnqualifiedName(State *state) {
729 ComplexityGuard guard(state);
730 if (guard.IsTooComplex()) return false;
731 return (ParseOperatorName(state, nullptr) || ParseCtorDtorName(state) ||
732 ParseSourceName(state) || ParseLocalSourceName(state) ||
733 ParseUnnamedTypeName(state));
734}
735
736// <source-name> ::= <positive length number> <identifier>
737static bool ParseSourceName(State *state) {
738 ComplexityGuard guard(state);
739 if (guard.IsTooComplex()) return false;
740 ParseState copy = state->parse_state;
741 int length = -1;
742 if (ParseNumber(state, &length) && ParseIdentifier(state, length)) {
743 return true;
744 }
745 state->parse_state = copy;
746 return false;
747}
748
749// <local-source-name> ::= L <source-name> [<discriminator>]
750//
751// References:
752// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=31775
753// https://gcc.gnu.org/viewcvs?view=rev&revision=124467
754static bool ParseLocalSourceName(State *state) {
755 ComplexityGuard guard(state);
756 if (guard.IsTooComplex()) return false;
757 ParseState copy = state->parse_state;
758 if (ParseOneCharToken(state, 'L') && ParseSourceName(state) &&
759 Optional(ParseDiscriminator(state))) {
760 return true;
761 }
762 state->parse_state = copy;
763 return false;
764}
765
766// <unnamed-type-name> ::= Ut [<(nonnegative) number>] _
767// ::= <closure-type-name>
768// <closure-type-name> ::= Ul <lambda-sig> E [<(nonnegative) number>] _
769// <lambda-sig> ::= <(parameter) type>+
770static bool ParseUnnamedTypeName(State *state) {
771 ComplexityGuard guard(state);
772 if (guard.IsTooComplex()) return false;
773 ParseState copy = state->parse_state;
774 // Type's 1-based index n is encoded as { "", n == 1; itoa(n-2), otherwise }.
775 // Optionally parse the encoded value into 'which' and add 2 to get the index.
776 int which = -1;
777
778 // Unnamed type local to function or class.
779 if (ParseTwoCharToken(state, "Ut") && Optional(ParseNumber(state, &which)) &&
780 which <= std::numeric_limits<int>::max() - 2 && // Don't overflow.
781 ParseOneCharToken(state, '_')) {
782 MaybeAppend(state, "{unnamed type#");
783 MaybeAppendDecimal(state, 2 + which);
784 MaybeAppend(state, "}");
785 return true;
786 }
787 state->parse_state = copy;
788
789 // Closure type.
790 which = -1;
791 if (ParseTwoCharToken(state, "Ul") && DisableAppend(state) &&
792 OneOrMore(ParseType, state) && RestoreAppend(state, copy.append) &&
793 ParseOneCharToken(state, 'E') && Optional(ParseNumber(state, &which)) &&
794 which <= std::numeric_limits<int>::max() - 2 && // Don't overflow.
795 ParseOneCharToken(state, '_')) {
796 MaybeAppend(state, "{lambda()#");
797 MaybeAppendDecimal(state, 2 + which);
798 MaybeAppend(state, "}");
799 return true;
800 }
801 state->parse_state = copy;
802
803 return false;
804}
805
806// <number> ::= [n] <non-negative decimal integer>
807// If "number_out" is non-null, then *number_out is set to the value of the
808// parsed number on success.
809static bool ParseNumber(State *state, int *number_out) {
810 ComplexityGuard guard(state);
811 if (guard.IsTooComplex()) return false;
812 bool negative = false;
813 if (ParseOneCharToken(state, 'n')) {
814 negative = true;
815 }
816 const char *p = RemainingInput(state);
817 uint64_t number = 0;
818 for (; *p != '\0'; ++p) {
819 if (IsDigit(*p)) {
820 number = number * 10 + (*p - '0');
821 } else {
822 break;
823 }
824 }
825 // Apply the sign with uint64_t arithmetic so overflows aren't UB. Gives
826 // "incorrect" results for out-of-range inputs, but negative values only
827 // appear for literals, which aren't printed.
828 if (negative) {
829 number = ~number + 1;
830 }
831 if (p != RemainingInput(state)) { // Conversion succeeded.
832 state->parse_state.mangled_idx += p - RemainingInput(state);
833 if (number_out != nullptr) {
834 // Note: possibly truncate "number".
835 *number_out = number;
836 }
837 return true;
838 }
839 return false;
840}
841
842// Floating-point literals are encoded using a fixed-length lowercase
843// hexadecimal string.
844static bool ParseFloatNumber(State *state) {
845 ComplexityGuard guard(state);
846 if (guard.IsTooComplex()) return false;
847 const char *p = RemainingInput(state);
848 for (; *p != '\0'; ++p) {
849 if (!IsDigit(*p) && !(*p >= 'a' && *p <= 'f')) {
850 break;
851 }
852 }
853 if (p != RemainingInput(state)) { // Conversion succeeded.
854 state->parse_state.mangled_idx += p - RemainingInput(state);
855 return true;
856 }
857 return false;
858}
859
860// The <seq-id> is a sequence number in base 36,
861// using digits and upper case letters
862static bool ParseSeqId(State *state) {
863 ComplexityGuard guard(state);
864 if (guard.IsTooComplex()) return false;
865 const char *p = RemainingInput(state);
866 for (; *p != '\0'; ++p) {
867 if (!IsDigit(*p) && !(*p >= 'A' && *p <= 'Z')) {
868 break;
869 }
870 }
871 if (p != RemainingInput(state)) { // Conversion succeeded.
872 state->parse_state.mangled_idx += p - RemainingInput(state);
873 return true;
874 }
875 return false;
876}
877
878// <identifier> ::= <unqualified source code identifier> (of given length)
879static bool ParseIdentifier(State *state, int length) {
880 ComplexityGuard guard(state);
881 if (guard.IsTooComplex()) return false;
882 if (length < 0 || !AtLeastNumCharsRemaining(RemainingInput(state), length)) {
883 return false;
884 }
885 if (IdentifierIsAnonymousNamespace(state, length)) {
886 MaybeAppend(state, "(anonymous namespace)");
887 } else {
888 MaybeAppendWithLength(state, RemainingInput(state), length);
889 }
890 state->parse_state.mangled_idx += length;
891 return true;
892}
893
894// <operator-name> ::= nw, and other two letters cases
895// ::= cv <type> # (cast)
896// ::= v <digit> <source-name> # vendor extended operator
897static bool ParseOperatorName(State *state, int *arity) {
898 ComplexityGuard guard(state);
899 if (guard.IsTooComplex()) return false;
900 if (!AtLeastNumCharsRemaining(RemainingInput(state), 2)) {
901 return false;
902 }
903 // First check with "cv" (cast) case.
904 ParseState copy = state->parse_state;
905 if (ParseTwoCharToken(state, "cv") && MaybeAppend(state, "operator ") &&
906 EnterNestedName(state) && ParseType(state) &&
907 LeaveNestedName(state, copy.nest_level)) {
908 if (arity != nullptr) {
909 *arity = 1;
910 }
911 return true;
912 }
913 state->parse_state = copy;
914
915 // Then vendor extended operators.
916 if (ParseOneCharToken(state, 'v') && ParseDigit(state, arity) &&
917 ParseSourceName(state)) {
918 return true;
919 }
920 state->parse_state = copy;
921
922 // Other operator names should start with a lower alphabet followed
923 // by a lower/upper alphabet.
924 if (!(IsLower(RemainingInput(state)[0]) &&
925 IsAlpha(RemainingInput(state)[1]))) {
926 return false;
927 }
928 // We may want to perform a binary search if we really need speed.
929 const AbbrevPair *p;
930 for (p = kOperatorList; p->abbrev != nullptr; ++p) {
931 if (RemainingInput(state)[0] == p->abbrev[0] &&
932 RemainingInput(state)[1] == p->abbrev[1]) {
933 if (arity != nullptr) {
934 *arity = p->arity;
935 }
936 MaybeAppend(state, "operator");
937 if (IsLower(*p->real_name)) { // new, delete, etc.
938 MaybeAppend(state, " ");
939 }
940 MaybeAppend(state, p->real_name);
941 state->parse_state.mangled_idx += 2;
942 return true;
943 }
944 }
945 return false;
946}
947
948// <special-name> ::= TV <type>
949// ::= TT <type>
950// ::= TI <type>
951// ::= TS <type>
952// ::= Tc <call-offset> <call-offset> <(base) encoding>
953// ::= GV <(object) name>
954// ::= T <call-offset> <(base) encoding>
955// G++ extensions:
956// ::= TC <type> <(offset) number> _ <(base) type>
957// ::= TF <type>
958// ::= TJ <type>
959// ::= GR <name>
960// ::= GA <encoding>
961// ::= Th <call-offset> <(base) encoding>
962// ::= Tv <call-offset> <(base) encoding>
963//
964// Note: we don't care much about them since they don't appear in
965// stack traces. The are special data.
966static bool ParseSpecialName(State *state) {
967 ComplexityGuard guard(state);
968 if (guard.IsTooComplex()) return false;
969 ParseState copy = state->parse_state;
970 if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "VTIS") &&
971 ParseType(state)) {
972 return true;
973 }
974 state->parse_state = copy;
975
976 if (ParseTwoCharToken(state, "Tc") && ParseCallOffset(state) &&
977 ParseCallOffset(state) && ParseEncoding(state)) {
978 return true;
979 }
980 state->parse_state = copy;
981
982 if (ParseTwoCharToken(state, "GV") && ParseName(state)) {
983 return true;
984 }
985 state->parse_state = copy;
986
987 if (ParseOneCharToken(state, 'T') && ParseCallOffset(state) &&
988 ParseEncoding(state)) {
989 return true;
990 }
991 state->parse_state = copy;
992
993 // G++ extensions
994 if (ParseTwoCharToken(state, "TC") && ParseType(state) &&
995 ParseNumber(state, nullptr) && ParseOneCharToken(state, '_') &&
996 DisableAppend(state) && ParseType(state)) {
997 RestoreAppend(state, copy.append);
998 return true;
999 }
1000 state->parse_state = copy;
1001
1002 if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "FJ") &&
1003 ParseType(state)) {
1004 return true;
1005 }
1006 state->parse_state = copy;
1007
1008 if (ParseTwoCharToken(state, "GR") && ParseName(state)) {
1009 return true;
1010 }
1011 state->parse_state = copy;
1012
1013 if (ParseTwoCharToken(state, "GA") && ParseEncoding(state)) {
1014 return true;
1015 }
1016 state->parse_state = copy;
1017
1018 if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "hv") &&
1019 ParseCallOffset(state) && ParseEncoding(state)) {
1020 return true;
1021 }
1022 state->parse_state = copy;
1023 return false;
1024}
1025
1026// <call-offset> ::= h <nv-offset> _
1027// ::= v <v-offset> _
1028static bool ParseCallOffset(State *state) {
1029 ComplexityGuard guard(state);
1030 if (guard.IsTooComplex()) return false;
1031 ParseState copy = state->parse_state;
1032 if (ParseOneCharToken(state, 'h') && ParseNVOffset(state) &&
1033 ParseOneCharToken(state, '_')) {
1034 return true;
1035 }
1036 state->parse_state = copy;
1037
1038 if (ParseOneCharToken(state, 'v') && ParseVOffset(state) &&
1039 ParseOneCharToken(state, '_')) {
1040 return true;
1041 }
1042 state->parse_state = copy;
1043
1044 return false;
1045}
1046
1047// <nv-offset> ::= <(offset) number>
1048static bool ParseNVOffset(State *state) {
1049 ComplexityGuard guard(state);
1050 if (guard.IsTooComplex()) return false;
1051 return ParseNumber(state, nullptr);
1052}
1053
1054// <v-offset> ::= <(offset) number> _ <(virtual offset) number>
1055static bool ParseVOffset(State *state) {
1056 ComplexityGuard guard(state);
1057 if (guard.IsTooComplex()) return false;
1058 ParseState copy = state->parse_state;
1059 if (ParseNumber(state, nullptr) && ParseOneCharToken(state, '_') &&
1060 ParseNumber(state, nullptr)) {
1061 return true;
1062 }
1063 state->parse_state = copy;
1064 return false;
1065}
1066
1067// <ctor-dtor-name> ::= C1 | C2 | C3
1068// ::= D0 | D1 | D2
1069// # GCC extensions: "unified" constructor/destructor. See
1070// # https://github.com/gcc-mirror/gcc/blob/7ad17b583c3643bd4557f29b8391ca7ef08391f5/gcc/cp/mangle.c#L1847
1071// ::= C4 | D4
1072static bool ParseCtorDtorName(State *state) {
1073 ComplexityGuard guard(state);
1074 if (guard.IsTooComplex()) return false;
1075 ParseState copy = state->parse_state;
1076 if (ParseOneCharToken(state, 'C') && ParseCharClass(state, "1234")) {
1077 const char *const prev_name = state->out + state->parse_state.prev_name_idx;
1078 MaybeAppendWithLength(state, prev_name,
1079 state->parse_state.prev_name_length);
1080 return true;
1081 }
1082 state->parse_state = copy;
1083
1084 if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "0124")) {
1085 const char *const prev_name = state->out + state->parse_state.prev_name_idx;
1086 MaybeAppend(state, "~");
1087 MaybeAppendWithLength(state, prev_name,
1088 state->parse_state.prev_name_length);
1089 return true;
1090 }
1091 state->parse_state = copy;
1092 return false;
1093}
1094
1095// <decltype> ::= Dt <expression> E # decltype of an id-expression or class
1096// # member access (C++0x)
1097// ::= DT <expression> E # decltype of an expression (C++0x)
1098static bool ParseDecltype(State *state) {
1099 ComplexityGuard guard(state);
1100 if (guard.IsTooComplex()) return false;
1101
1102 ParseState copy = state->parse_state;
1103 if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "tT") &&
1104 ParseExpression(state) && ParseOneCharToken(state, 'E')) {
1105 return true;
1106 }
1107 state->parse_state = copy;
1108
1109 return false;
1110}
1111
1112// <type> ::= <CV-qualifiers> <type>
1113// ::= P <type> # pointer-to
1114// ::= R <type> # reference-to
1115// ::= O <type> # rvalue reference-to (C++0x)
1116// ::= C <type> # complex pair (C 2000)
1117// ::= G <type> # imaginary (C 2000)
1118// ::= U <source-name> <type> # vendor extended type qualifier
1119// ::= <builtin-type>
1120// ::= <function-type>
1121// ::= <class-enum-type> # note: just an alias for <name>
1122// ::= <array-type>
1123// ::= <pointer-to-member-type>
1124// ::= <template-template-param> <template-args>
1125// ::= <template-param>
1126// ::= <decltype>
1127// ::= <substitution>
1128// ::= Dp <type> # pack expansion of (C++0x)
1129//
1130static bool ParseType(State *state) {
1131 ComplexityGuard guard(state);
1132 if (guard.IsTooComplex()) return false;
1133 ParseState copy = state->parse_state;
1134
1135 // We should check CV-qualifers, and PRGC things first.
1136 //
1137 // CV-qualifiers overlap with some operator names, but an operator name is not
1138 // valid as a type. To avoid an ambiguity that can lead to exponential time
1139 // complexity, refuse to backtrack the CV-qualifiers.
1140 //
1141 // _Z4aoeuIrMvvE
1142 // => _Z 4aoeuI rM v v E
1143 // aoeu<operator%=, void, void>
1144 // => _Z 4aoeuI r Mv v E
1145 // aoeu<void void::* restrict>
1146 //
1147 // By consuming the CV-qualifiers first, the former parse is disabled.
1148 if (ParseCVQualifiers(state)) {
1149 const bool result = ParseType(state);
1150 if (!result) state->parse_state = copy;
1151 return result;
1152 }
1153 state->parse_state = copy;
1154
1155 // Similarly, these tag characters can overlap with other <name>s resulting in
1156 // two different parse prefixes that land on <template-args> in the same
1157 // place, such as "C3r1xI...". So, disable the "ctor-name = C3" parse by
1158 // refusing to backtrack the tag characters.
1159 if (ParseCharClass(state, "OPRCG")) {
1160 const bool result = ParseType(state);
1161 if (!result) state->parse_state = copy;
1162 return result;
1163 }
1164 state->parse_state = copy;
1165
1166 if (ParseTwoCharToken(state, "Dp") && ParseType(state)) {
1167 return true;
1168 }
1169 state->parse_state = copy;
1170
1171 // nullptr_t, i.e. decltype(nullptr).
1172 if (ParseTwoCharToken(state, "Dn")) {
1173 return true;
1174 }
1175 state->parse_state = copy;
1176
1177 if (ParseOneCharToken(state, 'U') && ParseSourceName(state) &&
1178 ParseType(state)) {
1179 return true;
1180 }
1181 state->parse_state = copy;
1182
1183 if (ParseBuiltinType(state) || ParseFunctionType(state) ||
1184 ParseClassEnumType(state) || ParseArrayType(state) ||
1185 ParsePointerToMemberType(state) || ParseDecltype(state) ||
1186 // "std" on its own isn't a type.
1187 ParseSubstitution(state, /*accept_std=*/false)) {
1188 return true;
1189 }
1190
1191 if (ParseTemplateTemplateParam(state) && ParseTemplateArgs(state)) {
1192 return true;
1193 }
1194 state->parse_state = copy;
1195
1196 // Less greedy than <template-template-param> <template-args>.
1197 if (ParseTemplateParam(state)) {
1198 return true;
1199 }
1200
1201 return false;
1202}
1203
1204// <CV-qualifiers> ::= [r] [V] [K]
1205// We don't allow empty <CV-qualifiers> to avoid infinite loop in
1206// ParseType().
1207static bool ParseCVQualifiers(State *state) {
1208 ComplexityGuard guard(state);
1209 if (guard.IsTooComplex()) return false;
1210 int num_cv_qualifiers = 0;
1211 num_cv_qualifiers += ParseOneCharToken(state, 'r');
1212 num_cv_qualifiers += ParseOneCharToken(state, 'V');
1213 num_cv_qualifiers += ParseOneCharToken(state, 'K');
1214 return num_cv_qualifiers > 0;
1215}
1216
1217// <builtin-type> ::= v, etc.
1218// ::= u <source-name>
1219static bool ParseBuiltinType(State *state) {
1220 ComplexityGuard guard(state);
1221 if (guard.IsTooComplex()) return false;
1222 const AbbrevPair *p;
1223 for (p = kBuiltinTypeList; p->abbrev != nullptr; ++p) {
1224 if (RemainingInput(state)[0] == p->abbrev[0]) {
1225 MaybeAppend(state, p->real_name);
1226 ++state->parse_state.mangled_idx;
1227 return true;
1228 }
1229 }
1230
1231 ParseState copy = state->parse_state;
1232 if (ParseOneCharToken(state, 'u') && ParseSourceName(state)) {
1233 return true;
1234 }
1235 state->parse_state = copy;
1236 return false;
1237}
1238
1239// <function-type> ::= F [Y] <bare-function-type> E
1240static bool ParseFunctionType(State *state) {
1241 ComplexityGuard guard(state);
1242 if (guard.IsTooComplex()) return false;
1243 ParseState copy = state->parse_state;
1244 if (ParseOneCharToken(state, 'F') &&
1245 Optional(ParseOneCharToken(state, 'Y')) && ParseBareFunctionType(state) &&
1246 ParseOneCharToken(state, 'E')) {
1247 return true;
1248 }
1249 state->parse_state = copy;
1250 return false;
1251}
1252
1253// <bare-function-type> ::= <(signature) type>+
1254static bool ParseBareFunctionType(State *state) {
1255 ComplexityGuard guard(state);
1256 if (guard.IsTooComplex()) return false;
1257 ParseState copy = state->parse_state;
1258 DisableAppend(state);
1259 if (OneOrMore(ParseType, state)) {
1260 RestoreAppend(state, copy.append);
1261 MaybeAppend(state, "()");
1262 return true;
1263 }
1264 state->parse_state = copy;
1265 return false;
1266}
1267
1268// <class-enum-type> ::= <name>
1269static bool ParseClassEnumType(State *state) {
1270 ComplexityGuard guard(state);
1271 if (guard.IsTooComplex()) return false;
1272 return ParseName(state);
1273}
1274
1275// <array-type> ::= A <(positive dimension) number> _ <(element) type>
1276// ::= A [<(dimension) expression>] _ <(element) type>
1277static bool ParseArrayType(State *state) {
1278 ComplexityGuard guard(state);
1279 if (guard.IsTooComplex()) return false;
1280 ParseState copy = state->parse_state;
1281 if (ParseOneCharToken(state, 'A') && ParseNumber(state, nullptr) &&
1282 ParseOneCharToken(state, '_') && ParseType(state)) {
1283 return true;
1284 }
1285 state->parse_state = copy;
1286
1287 if (ParseOneCharToken(state, 'A') && Optional(ParseExpression(state)) &&
1288 ParseOneCharToken(state, '_') && ParseType(state)) {
1289 return true;
1290 }
1291 state->parse_state = copy;
1292 return false;
1293}
1294
1295// <pointer-to-member-type> ::= M <(class) type> <(member) type>
1296static bool ParsePointerToMemberType(State *state) {
1297 ComplexityGuard guard(state);
1298 if (guard.IsTooComplex()) return false;
1299 ParseState copy = state->parse_state;
1300 if (ParseOneCharToken(state, 'M') && ParseType(state) && ParseType(state)) {
1301 return true;
1302 }
1303 state->parse_state = copy;
1304 return false;
1305}
1306
1307// <template-param> ::= T_
1308// ::= T <parameter-2 non-negative number> _
1309static bool ParseTemplateParam(State *state) {
1310 ComplexityGuard guard(state);
1311 if (guard.IsTooComplex()) return false;
1312 if (ParseTwoCharToken(state, "T_")) {
1313 MaybeAppend(state, "?"); // We don't support template substitutions.
1314 return true;
1315 }
1316
1317 ParseState copy = state->parse_state;
1318 if (ParseOneCharToken(state, 'T') && ParseNumber(state, nullptr) &&
1319 ParseOneCharToken(state, '_')) {
1320 MaybeAppend(state, "?"); // We don't support template substitutions.
1321 return true;
1322 }
1323 state->parse_state = copy;
1324 return false;
1325}
1326
1327// <template-template-param> ::= <template-param>
1328// ::= <substitution>
1329static bool ParseTemplateTemplateParam(State *state) {
1330 ComplexityGuard guard(state);
1331 if (guard.IsTooComplex()) return false;
1332 return (ParseTemplateParam(state) ||
1333 // "std" on its own isn't a template.
1334 ParseSubstitution(state, /*accept_std=*/false));
1335}
1336
1337// <template-args> ::= I <template-arg>+ E
1338static bool ParseTemplateArgs(State *state) {
1339 ComplexityGuard guard(state);
1340 if (guard.IsTooComplex()) return false;
1341 ParseState copy = state->parse_state;
1342 DisableAppend(state);
1343 if (ParseOneCharToken(state, 'I') && OneOrMore(ParseTemplateArg, state) &&
1344 ParseOneCharToken(state, 'E')) {
1345 RestoreAppend(state, copy.append);
1346 MaybeAppend(state, "<>");
1347 return true;
1348 }
1349 state->parse_state = copy;
1350 return false;
1351}
1352
1353// <template-arg> ::= <type>
1354// ::= <expr-primary>
1355// ::= J <template-arg>* E # argument pack
1356// ::= X <expression> E
1357static bool ParseTemplateArg(State *state) {
1358 ComplexityGuard guard(state);
1359 if (guard.IsTooComplex()) return false;
1360 ParseState copy = state->parse_state;
1361 if (ParseOneCharToken(state, 'J') && ZeroOrMore(ParseTemplateArg, state) &&
1362 ParseOneCharToken(state, 'E')) {
1363 return true;
1364 }
1365 state->parse_state = copy;
1366
1367 // There can be significant overlap between the following leading to
1368 // exponential backtracking:
1369 //
1370 // <expr-primary> ::= L <type> <expr-cast-value> E
1371 // e.g. L 2xxIvE 1 E
1372 // <type> ==> <local-source-name> <template-args>
1373 // e.g. L 2xx IvE
1374 //
1375 // This means parsing an entire <type> twice, and <type> can contain
1376 // <template-arg>, so this can generate exponential backtracking. There is
1377 // only overlap when the remaining input starts with "L <source-name>", so
1378 // parse all cases that can start this way jointly to share the common prefix.
1379 //
1380 // We have:
1381 //
1382 // <template-arg> ::= <type>
1383 // ::= <expr-primary>
1384 //
1385 // First, drop all the productions of <type> that must start with something
1386 // other than 'L'. All that's left is <class-enum-type>; inline it.
1387 //
1388 // <type> ::= <nested-name> # starts with 'N'
1389 // ::= <unscoped-name>
1390 // ::= <unscoped-template-name> <template-args>
1391 // ::= <local-name> # starts with 'Z'
1392 //
1393 // Drop and inline again:
1394 //
1395 // <type> ::= <unscoped-name>
1396 // ::= <unscoped-name> <template-args>
1397 // ::= <substitution> <template-args> # starts with 'S'
1398 //
1399 // Merge the first two, inline <unscoped-name>, drop last:
1400 //
1401 // <type> ::= <unqualified-name> [<template-args>]
1402 // ::= St <unqualified-name> [<template-args>] # starts with 'S'
1403 //
1404 // Drop and inline:
1405 //
1406 // <type> ::= <operator-name> [<template-args>] # starts with lowercase
1407 // ::= <ctor-dtor-name> [<template-args>] # starts with 'C' or 'D'
1408 // ::= <source-name> [<template-args>] # starts with digit
1409 // ::= <local-source-name> [<template-args>]
1410 // ::= <unnamed-type-name> [<template-args>] # starts with 'U'
1411 //
1412 // One more time:
1413 //
1414 // <type> ::= L <source-name> [<template-args>]
1415 //
1416 // Likewise with <expr-primary>:
1417 //
1418 // <expr-primary> ::= L <type> <expr-cast-value> E
1419 // ::= LZ <encoding> E # cannot overlap; drop
1420 // ::= L <mangled_name> E # cannot overlap; drop
1421 //
1422 // By similar reasoning as shown above, the only <type>s starting with
1423 // <source-name> are "<source-name> [<template-args>]". Inline this.
1424 //
1425 // <expr-primary> ::= L <source-name> [<template-args>] <expr-cast-value> E
1426 //
1427 // Now inline both of these into <template-arg>:
1428 //
1429 // <template-arg> ::= L <source-name> [<template-args>]
1430 // ::= L <source-name> [<template-args>] <expr-cast-value> E
1431 //
1432 // Merge them and we're done:
1433 // <template-arg>
1434 // ::= L <source-name> [<template-args>] [<expr-cast-value> E]
1435 if (ParseLocalSourceName(state) && Optional(ParseTemplateArgs(state))) {
1436 copy = state->parse_state;
1437 if (ParseExprCastValue(state) && ParseOneCharToken(state, 'E')) {
1438 return true;
1439 }
1440 state->parse_state = copy;
1441 return true;
1442 }
1443
1444 // Now that the overlapping cases can't reach this code, we can safely call
1445 // both of these.
1446 if (ParseType(state) || ParseExprPrimary(state)) {
1447 return true;
1448 }
1449 state->parse_state = copy;
1450
1451 if (ParseOneCharToken(state, 'X') && ParseExpression(state) &&
1452 ParseOneCharToken(state, 'E')) {
1453 return true;
1454 }
1455 state->parse_state = copy;
1456 return false;
1457}
1458
1459// <unresolved-type> ::= <template-param> [<template-args>]
1460// ::= <decltype>
1461// ::= <substitution>
1462static inline bool ParseUnresolvedType(State *state) {
1463 // No ComplexityGuard because we don't copy the state in this stack frame.
1464 return (ParseTemplateParam(state) && Optional(ParseTemplateArgs(state))) ||
1465 ParseDecltype(state) || ParseSubstitution(state, /*accept_std=*/false);
1466}
1467
1468// <simple-id> ::= <source-name> [<template-args>]
1469static inline bool ParseSimpleId(State *state) {
1470 // No ComplexityGuard because we don't copy the state in this stack frame.
1471
1472 // Note: <simple-id> cannot be followed by a parameter pack; see comment in
1473 // ParseUnresolvedType.
1474 return ParseSourceName(state) && Optional(ParseTemplateArgs(state));
1475}
1476
1477// <base-unresolved-name> ::= <source-name> [<template-args>]
1478// ::= on <operator-name> [<template-args>]
1479// ::= dn <destructor-name>
1480static bool ParseBaseUnresolvedName(State *state) {
1481 ComplexityGuard guard(state);
1482 if (guard.IsTooComplex()) return false;
1483
1484 if (ParseSimpleId(state)) {
1485 return true;
1486 }
1487
1488 ParseState copy = state->parse_state;
1489 if (ParseTwoCharToken(state, "on") && ParseOperatorName(state, nullptr) &&
1490 Optional(ParseTemplateArgs(state))) {
1491 return true;
1492 }
1493 state->parse_state = copy;
1494
1495 if (ParseTwoCharToken(state, "dn") &&
1496 (ParseUnresolvedType(state) || ParseSimpleId(state))) {
1497 return true;
1498 }
1499 state->parse_state = copy;
1500
1501 return false;
1502}
1503
1504// <unresolved-name> ::= [gs] <base-unresolved-name>
1505// ::= sr <unresolved-type> <base-unresolved-name>
1506// ::= srN <unresolved-type> <unresolved-qualifier-level>+ E
1507// <base-unresolved-name>
1508// ::= [gs] sr <unresolved-qualifier-level>+ E
1509// <base-unresolved-name>
1510static bool ParseUnresolvedName(State *state) {
1511 ComplexityGuard guard(state);
1512 if (guard.IsTooComplex()) return false;
1513
1514 ParseState copy = state->parse_state;
1515 if (Optional(ParseTwoCharToken(state, "gs")) &&
1516 ParseBaseUnresolvedName(state)) {
1517 return true;
1518 }
1519 state->parse_state = copy;
1520
1521 if (ParseTwoCharToken(state, "sr") && ParseUnresolvedType(state) &&
1522 ParseBaseUnresolvedName(state)) {
1523 return true;
1524 }
1525 state->parse_state = copy;
1526
1527 if (ParseTwoCharToken(state, "sr") && ParseOneCharToken(state, 'N') &&
1528 ParseUnresolvedType(state) &&
1529 OneOrMore(/* <unresolved-qualifier-level> ::= */ ParseSimpleId, state) &&
1530 ParseOneCharToken(state, 'E') && ParseBaseUnresolvedName(state)) {
1531 return true;
1532 }
1533 state->parse_state = copy;
1534
1535 if (Optional(ParseTwoCharToken(state, "gs")) &&
1536 ParseTwoCharToken(state, "sr") &&
1537 OneOrMore(/* <unresolved-qualifier-level> ::= */ ParseSimpleId, state) &&
1538 ParseOneCharToken(state, 'E') && ParseBaseUnresolvedName(state)) {
1539 return true;
1540 }
1541 state->parse_state = copy;
1542
1543 return false;
1544}
1545
1546// <expression> ::= <1-ary operator-name> <expression>
1547// ::= <2-ary operator-name> <expression> <expression>
1548// ::= <3-ary operator-name> <expression> <expression> <expression>
1549// ::= cl <expression>+ E
1550// ::= cv <type> <expression> # type (expression)
1551// ::= cv <type> _ <expression>* E # type (expr-list)
1552// ::= st <type>
1553// ::= <template-param>
1554// ::= <function-param>
1555// ::= <expr-primary>
1556// ::= dt <expression> <unresolved-name> # expr.name
1557// ::= pt <expression> <unresolved-name> # expr->name
1558// ::= sp <expression> # argument pack expansion
1559// ::= sr <type> <unqualified-name> <template-args>
1560// ::= sr <type> <unqualified-name>
1561// <function-param> ::= fp <(top-level) CV-qualifiers> _
1562// ::= fp <(top-level) CV-qualifiers> <number> _
1563// ::= fL <number> p <(top-level) CV-qualifiers> _
1564// ::= fL <number> p <(top-level) CV-qualifiers> <number> _
1565static bool ParseExpression(State *state) {
1566 ComplexityGuard guard(state);
1567 if (guard.IsTooComplex()) return false;
1568 if (ParseTemplateParam(state) || ParseExprPrimary(state)) {
1569 return true;
1570 }
1571
1572 // Object/function call expression.
1573 ParseState copy = state->parse_state;
1574 if (ParseTwoCharToken(state, "cl") && OneOrMore(ParseExpression, state) &&
1575 ParseOneCharToken(state, 'E')) {
1576 return true;
1577 }
1578 state->parse_state = copy;
1579
1580 // Function-param expression (level 0).
1581 if (ParseTwoCharToken(state, "fp") && Optional(ParseCVQualifiers(state)) &&
1582 Optional(ParseNumber(state, nullptr)) && ParseOneCharToken(state, '_')) {
1583 return true;
1584 }
1585 state->parse_state = copy;
1586
1587 // Function-param expression (level 1+).
1588 if (ParseTwoCharToken(state, "fL") && Optional(ParseNumber(state, nullptr)) &&
1589 ParseOneCharToken(state, 'p') && Optional(ParseCVQualifiers(state)) &&
1590 Optional(ParseNumber(state, nullptr)) && ParseOneCharToken(state, '_')) {
1591 return true;
1592 }
1593 state->parse_state = copy;
1594
1595 // Parse the conversion expressions jointly to avoid re-parsing the <type> in
1596 // their common prefix. Parsed as:
1597 // <expression> ::= cv <type> <conversion-args>
1598 // <conversion-args> ::= _ <expression>* E
1599 // ::= <expression>
1600 //
1601 // Also don't try ParseOperatorName after seeing "cv", since ParseOperatorName
1602 // also needs to accept "cv <type>" in other contexts.
1603 if (ParseTwoCharToken(state, "cv")) {
1604 if (ParseType(state)) {
1605 ParseState copy2 = state->parse_state;
1606 if (ParseOneCharToken(state, '_') && ZeroOrMore(ParseExpression, state) &&
1607 ParseOneCharToken(state, 'E')) {
1608 return true;
1609 }
1610 state->parse_state = copy2;
1611 if (ParseExpression(state)) {
1612 return true;
1613 }
1614 }
1615 } else {
1616 // Parse unary, binary, and ternary operator expressions jointly, taking
1617 // care not to re-parse subexpressions repeatedly. Parse like:
1618 // <expression> ::= <operator-name> <expression>
1619 // [<one-to-two-expressions>]
1620 // <one-to-two-expressions> ::= <expression> [<expression>]
1621 int arity = -1;
1622 if (ParseOperatorName(state, &arity) &&
1623 arity > 0 && // 0 arity => disabled.
1624 (arity < 3 || ParseExpression(state)) &&
1625 (arity < 2 || ParseExpression(state)) &&
1626 (arity < 1 || ParseExpression(state))) {
1627 return true;
1628 }
1629 }
1630 state->parse_state = copy;
1631
1632 // sizeof type
1633 if (ParseTwoCharToken(state, "st") && ParseType(state)) {
1634 return true;
1635 }
1636 state->parse_state = copy;
1637
1638 // Object and pointer member access expressions.
1639 if ((ParseTwoCharToken(state, "dt") || ParseTwoCharToken(state, "pt")) &&
1640 ParseExpression(state) && ParseType(state)) {
1641 return true;
1642 }
1643 state->parse_state = copy;
1644
1645 // Pointer-to-member access expressions. This parses the same as a binary
1646 // operator, but it's implemented separately because "ds" shouldn't be
1647 // accepted in other contexts that parse an operator name.
1648 if (ParseTwoCharToken(state, "ds") && ParseExpression(state) &&
1649 ParseExpression(state)) {
1650 return true;
1651 }
1652 state->parse_state = copy;
1653
1654 // Parameter pack expansion
1655 if (ParseTwoCharToken(state, "sp") && ParseExpression(state)) {
1656 return true;
1657 }
1658 state->parse_state = copy;
1659
1660 return ParseUnresolvedName(state);
1661}
1662
1663// <expr-primary> ::= L <type> <(value) number> E
1664// ::= L <type> <(value) float> E
1665// ::= L <mangled-name> E
1666// // A bug in g++'s C++ ABI version 2 (-fabi-version=2).
1667// ::= LZ <encoding> E
1668//
1669// Warning, subtle: the "bug" LZ production above is ambiguous with the first
1670// production where <type> starts with <local-name>, which can lead to
1671// exponential backtracking in two scenarios:
1672//
1673// - When whatever follows the E in the <local-name> in the first production is
1674// not a name, we backtrack the whole <encoding> and re-parse the whole thing.
1675//
1676// - When whatever follows the <local-name> in the first production is not a
1677// number and this <expr-primary> may be followed by a name, we backtrack the
1678// <name> and re-parse it.
1679//
1680// Moreover this ambiguity isn't always resolved -- for example, the following
1681// has two different parses:
1682//
1683// _ZaaILZ4aoeuE1x1EvE
1684// => operator&&<aoeu, x, E, void>
1685// => operator&&<(aoeu::x)(1), void>
1686//
1687// To resolve this, we just do what GCC's demangler does, and refuse to parse
1688// casts to <local-name> types.
1689static bool ParseExprPrimary(State *state) {
1690 ComplexityGuard guard(state);
1691 if (guard.IsTooComplex()) return false;
1692 ParseState copy = state->parse_state;
1693
1694 // The "LZ" special case: if we see LZ, we commit to accept "LZ <encoding> E"
1695 // or fail, no backtracking.
1696 if (ParseTwoCharToken(state, "LZ")) {
1697 if (ParseEncoding(state) && ParseOneCharToken(state, 'E')) {
1698 return true;
1699 }
1700
1701 state->parse_state = copy;
1702 return false;
1703 }
1704
1705 // The merged cast production.
1706 if (ParseOneCharToken(state, 'L') && ParseType(state) &&
1707 ParseExprCastValue(state)) {
1708 return true;
1709 }
1710 state->parse_state = copy;
1711
1712 if (ParseOneCharToken(state, 'L') && ParseMangledName(state) &&
1713 ParseOneCharToken(state, 'E')) {
1714 return true;
1715 }
1716 state->parse_state = copy;
1717
1718 return false;
1719}
1720
1721// <number> or <float>, followed by 'E', as described above ParseExprPrimary.
1722static bool ParseExprCastValue(State *state) {
1723 ComplexityGuard guard(state);
1724 if (guard.IsTooComplex()) return false;
1725 // We have to be able to backtrack after accepting a number because we could
1726 // have e.g. "7fffE", which will accept "7" as a number but then fail to find
1727 // the 'E'.
1728 ParseState copy = state->parse_state;
1729 if (ParseNumber(state, nullptr) && ParseOneCharToken(state, 'E')) {
1730 return true;
1731 }
1732 state->parse_state = copy;
1733
1734 if (ParseFloatNumber(state) && ParseOneCharToken(state, 'E')) {
1735 return true;
1736 }
1737 state->parse_state = copy;
1738
1739 return false;
1740}
1741
1742// <local-name> ::= Z <(function) encoding> E <(entity) name> [<discriminator>]
1743// ::= Z <(function) encoding> E s [<discriminator>]
1744//
1745// Parsing a common prefix of these two productions together avoids an
1746// exponential blowup of backtracking. Parse like:
1747// <local-name> := Z <encoding> E <local-name-suffix>
1748// <local-name-suffix> ::= s [<discriminator>]
1749// ::= <name> [<discriminator>]
1750
1751static bool ParseLocalNameSuffix(State *state) {
1752 ComplexityGuard guard(state);
1753 if (guard.IsTooComplex()) return false;
1754
1755 if (MaybeAppend(state, "::") && ParseName(state) &&
1756 Optional(ParseDiscriminator(state))) {
1757 return true;
1758 }
1759
1760 // Since we're not going to overwrite the above "::" by re-parsing the
1761 // <encoding> (whose trailing '\0' byte was in the byte now holding the
1762 // first ':'), we have to rollback the "::" if the <name> parse failed.
1763 if (state->parse_state.append) {
1764 state->out[state->parse_state.out_cur_idx - 2] = '\0';
1765 }
1766
1767 return ParseOneCharToken(state, 's') && Optional(ParseDiscriminator(state));
1768}
1769
1770static bool ParseLocalName(State *state) {
1771 ComplexityGuard guard(state);
1772 if (guard.IsTooComplex()) return false;
1773 ParseState copy = state->parse_state;
1774 if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
1775 ParseOneCharToken(state, 'E') && ParseLocalNameSuffix(state)) {
1776 return true;
1777 }
1778 state->parse_state = copy;
1779 return false;
1780}
1781
1782// <discriminator> := _ <(non-negative) number>
1783static bool ParseDiscriminator(State *state) {
1784 ComplexityGuard guard(state);
1785 if (guard.IsTooComplex()) return false;
1786 ParseState copy = state->parse_state;
1787 if (ParseOneCharToken(state, '_') && ParseNumber(state, nullptr)) {
1788 return true;
1789 }
1790 state->parse_state = copy;
1791 return false;
1792}
1793
1794// <substitution> ::= S_
1795// ::= S <seq-id> _
1796// ::= St, etc.
1797//
1798// "St" is special in that it's not valid as a standalone name, and it *is*
1799// allowed to precede a name without being wrapped in "N...E". This means that
1800// if we accept it on its own, we can accept "St1a" and try to parse
1801// template-args, then fail and backtrack, accept "St" on its own, then "1a" as
1802// an unqualified name and re-parse the same template-args. To block this
1803// exponential backtracking, we disable it with 'accept_std=false' in
1804// problematic contexts.
1805static bool ParseSubstitution(State *state, bool accept_std) {
1806 ComplexityGuard guard(state);
1807 if (guard.IsTooComplex()) return false;
1808 if (ParseTwoCharToken(state, "S_")) {
1809 MaybeAppend(state, "?"); // We don't support substitutions.
1810 return true;
1811 }
1812
1813 ParseState copy = state->parse_state;
1814 if (ParseOneCharToken(state, 'S') && ParseSeqId(state) &&
1815 ParseOneCharToken(state, '_')) {
1816 MaybeAppend(state, "?"); // We don't support substitutions.
1817 return true;
1818 }
1819 state->parse_state = copy;
1820
1821 // Expand abbreviations like "St" => "std".
1822 if (ParseOneCharToken(state, 'S')) {
1823 const AbbrevPair *p;
1824 for (p = kSubstitutionList; p->abbrev != nullptr; ++p) {
1825 if (RemainingInput(state)[0] == p->abbrev[1] &&
1826 (accept_std || p->abbrev[1] != 't')) {
1827 MaybeAppend(state, "std");
1828 if (p->real_name[0] != '\0') {
1829 MaybeAppend(state, "::");
1830 MaybeAppend(state, p->real_name);
1831 }
1832 ++state->parse_state.mangled_idx;
1833 return true;
1834 }
1835 }
1836 }
1837 state->parse_state = copy;
1838 return false;
1839}
1840
1841// Parse <mangled-name>, optionally followed by either a function-clone suffix
1842// or version suffix. Returns true only if all of "mangled_cur" was consumed.
1843static bool ParseTopLevelMangledName(State *state) {
1844 ComplexityGuard guard(state);
1845 if (guard.IsTooComplex()) return false;
1846 if (ParseMangledName(state)) {
1847 if (RemainingInput(state)[0] != '\0') {
1848 // Drop trailing function clone suffix, if any.
1849 if (IsFunctionCloneSuffix(RemainingInput(state))) {
1850 return true;
1851 }
1852 // Append trailing version suffix if any.
1853 // ex. _Z3foo@@GLIBCXX_3.4
1854 if (RemainingInput(state)[0] == '@') {
1855 MaybeAppend(state, RemainingInput(state));
1856 return true;
1857 }
1858 return false; // Unconsumed suffix.
1859 }
1860 return true;
1861 }
1862 return false;
1863}
1864
1865static bool Overflowed(const State *state) {
1866 return state->parse_state.out_cur_idx >= state->out_end_idx;
1867}
1868
1869// The demangler entry point.
1870bool Demangle(const char *mangled, char *out, int out_size) {
1871 State state;
1872 InitState(&state, mangled, out, out_size);
1873 return ParseTopLevelMangledName(&state) && !Overflowed(&state);
1874}
1875
1876} // namespace debugging_internal
1877} // namespace absl
1878