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