Coverage Report

Created: 2024-09-23 06:29

/src/abseil-cpp/absl/debugging/internal/demangle.cc
Line
Count
Source (jump to first uncovered line)
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
#include "absl/debugging/internal/demangle.h"
19
20
#include <cstddef>
21
#include <cstdint>
22
#include <cstdio>
23
#include <cstdlib>
24
#include <cstring>
25
#include <limits>
26
#include <string>
27
28
#include "absl/base/config.h"
29
#include "absl/debugging/internal/demangle_rust.h"
30
31
#if ABSL_INTERNAL_HAS_CXA_DEMANGLE
32
#include <cxxabi.h>
33
#endif
34
35
namespace absl {
36
ABSL_NAMESPACE_BEGIN
37
namespace debugging_internal {
38
39
typedef struct {
40
  const char *abbrev;
41
  const char *real_name;
42
  // Number of arguments in <expression> context, or 0 if disallowed.
43
  int arity;
44
} AbbrevPair;
45
46
// List of operators from Itanium C++ ABI.
47
static const AbbrevPair kOperatorList[] = {
48
    // New has special syntax.
49
    {"nw", "new", 0},
50
    {"na", "new[]", 0},
51
52
    // Special-cased elsewhere to support the optional gs prefix.
53
    {"dl", "delete", 1},
54
    {"da", "delete[]", 1},
55
56
    {"aw", "co_await", 1},
57
58
    {"ps", "+", 1},  // "positive"
59
    {"ng", "-", 1},  // "negative"
60
    {"ad", "&", 1},  // "address-of"
61
    {"de", "*", 1},  // "dereference"
62
    {"co", "~", 1},
63
64
    {"pl", "+", 2},
65
    {"mi", "-", 2},
66
    {"ml", "*", 2},
67
    {"dv", "/", 2},
68
    {"rm", "%", 2},
69
    {"an", "&", 2},
70
    {"or", "|", 2},
71
    {"eo", "^", 2},
72
    {"aS", "=", 2},
73
    {"pL", "+=", 2},
74
    {"mI", "-=", 2},
75
    {"mL", "*=", 2},
76
    {"dV", "/=", 2},
77
    {"rM", "%=", 2},
78
    {"aN", "&=", 2},
79
    {"oR", "|=", 2},
80
    {"eO", "^=", 2},
81
    {"ls", "<<", 2},
82
    {"rs", ">>", 2},
83
    {"lS", "<<=", 2},
84
    {"rS", ">>=", 2},
85
    {"ss", "<=>", 2},
86
    {"eq", "==", 2},
87
    {"ne", "!=", 2},
88
    {"lt", "<", 2},
89
    {"gt", ">", 2},
90
    {"le", "<=", 2},
91
    {"ge", ">=", 2},
92
    {"nt", "!", 1},
93
    {"aa", "&&", 2},
94
    {"oo", "||", 2},
95
    {"pp", "++", 1},
96
    {"mm", "--", 1},
97
    {"cm", ",", 2},
98
    {"pm", "->*", 2},
99
    {"pt", "->", 0},  // Special syntax
100
    {"cl", "()", 0},  // Special syntax
101
    {"ix", "[]", 2},
102
    {"qu", "?", 3},
103
    {"st", "sizeof", 0},  // Special syntax
104
    {"sz", "sizeof", 1},  // Not a real operator name, but used in expressions.
105
    {"sZ", "sizeof...", 0},  // Special syntax
106
    {nullptr, nullptr, 0},
107
};
108
109
// List of builtin types from Itanium C++ ABI.
110
//
111
// Invariant: only one- or two-character type abbreviations here.
112
static const AbbrevPair kBuiltinTypeList[] = {
113
    {"v", "void", 0},
114
    {"w", "wchar_t", 0},
115
    {"b", "bool", 0},
116
    {"c", "char", 0},
117
    {"a", "signed char", 0},
118
    {"h", "unsigned char", 0},
119
    {"s", "short", 0},
120
    {"t", "unsigned short", 0},
121
    {"i", "int", 0},
122
    {"j", "unsigned int", 0},
123
    {"l", "long", 0},
124
    {"m", "unsigned long", 0},
125
    {"x", "long long", 0},
126
    {"y", "unsigned long long", 0},
127
    {"n", "__int128", 0},
128
    {"o", "unsigned __int128", 0},
129
    {"f", "float", 0},
130
    {"d", "double", 0},
131
    {"e", "long double", 0},
132
    {"g", "__float128", 0},
133
    {"z", "ellipsis", 0},
134
135
    {"De", "decimal128", 0},      // IEEE 754r decimal floating point (128 bits)
136
    {"Dd", "decimal64", 0},       // IEEE 754r decimal floating point (64 bits)
137
    {"Dc", "decltype(auto)", 0},
138
    {"Da", "auto", 0},
139
    {"Dn", "std::nullptr_t", 0},  // i.e., decltype(nullptr)
140
    {"Df", "decimal32", 0},       // IEEE 754r decimal floating point (32 bits)
141
    {"Di", "char32_t", 0},
142
    {"Du", "char8_t", 0},
143
    {"Ds", "char16_t", 0},
144
    {"Dh", "float16", 0},         // IEEE 754r half-precision float (16 bits)
145
    {nullptr, nullptr, 0},
146
};
147
148
// List of substitutions Itanium C++ ABI.
149
static const AbbrevPair kSubstitutionList[] = {
150
    {"St", "", 0},
151
    {"Sa", "allocator", 0},
152
    {"Sb", "basic_string", 0},
153
    // std::basic_string<char, std::char_traits<char>,std::allocator<char> >
154
    {"Ss", "string", 0},
155
    // std::basic_istream<char, std::char_traits<char> >
156
    {"Si", "istream", 0},
157
    // std::basic_ostream<char, std::char_traits<char> >
158
    {"So", "ostream", 0},
159
    // std::basic_iostream<char, std::char_traits<char> >
160
    {"Sd", "iostream", 0},
161
    {nullptr, nullptr, 0},
162
};
163
164
// State needed for demangling.  This struct is copied in almost every stack
165
// frame, so every byte counts.
166
typedef struct {
167
  int mangled_idx;                     // Cursor of mangled name.
168
  int out_cur_idx;                     // Cursor of output string.
169
  int prev_name_idx;                   // For constructors/destructors.
170
  unsigned int prev_name_length : 16;  // For constructors/destructors.
171
  signed int nest_level : 15;          // For nested names.
172
  unsigned int append : 1;             // Append flag.
173
  // Note: for some reason MSVC can't pack "bool append : 1" into the same int
174
  // with the above two fields, so we use an int instead.  Amusingly it can pack
175
  // "signed bool" as expected, but relying on that to continue to be a legal
176
  // type seems ill-advised (as it's illegal in at least clang).
177
} ParseState;
178
179
static_assert(sizeof(ParseState) == 4 * sizeof(int),
180
              "unexpected size of ParseState");
181
182
// One-off state for demangling that's not subject to backtracking -- either
183
// constant data, data that's intentionally immune to backtracking (steps), or
184
// data that would never be changed by backtracking anyway (recursion_depth).
185
//
186
// Only one copy of this exists for each call to Demangle, so the size of this
187
// struct is nearly inconsequential.
188
typedef struct {
189
  const char *mangled_begin;  // Beginning of input string.
190
  char *out;                  // Beginning of output string.
191
  int out_end_idx;            // One past last allowed output character.
192
  int recursion_depth;        // For stack exhaustion prevention.
193
  int steps;               // Cap how much work we'll do, regardless of depth.
194
  ParseState parse_state;  // Backtrackable state copied for most frames.
195
196
  // Conditionally compiled support for marking the position of the first
197
  // construct Demangle couldn't parse.  This preprocessor symbol is intended
198
  // for use by Abseil demangler maintainers only; its behavior is not part of
199
  // Abseil's public interface.
200
#ifdef ABSL_INTERNAL_DEMANGLE_RECORDS_HIGH_WATER_MARK
201
  int high_water_mark;  // Input position where parsing failed.
202
  bool too_complex;  // True if any guard.IsTooComplex() call returned true.
203
#endif
204
} State;
205
206
namespace {
207
208
#ifdef ABSL_INTERNAL_DEMANGLE_RECORDS_HIGH_WATER_MARK
209
void UpdateHighWaterMark(State *state) {
210
  if (state->high_water_mark < state->parse_state.mangled_idx) {
211
    state->high_water_mark = state->parse_state.mangled_idx;
212
  }
213
}
214
215
void ReportHighWaterMark(State *state) {
216
  // Write out the mangled name with the trouble point marked, provided that the
217
  // output buffer is large enough and the mangled name did not hit a complexity
218
  // limit (in which case the high water mark wouldn't point out an unparsable
219
  // construct, only the point where a budget ran out).
220
  const size_t input_length = std::strlen(state->mangled_begin);
221
  if (input_length + 6 > static_cast<size_t>(state->out_end_idx) ||
222
      state->too_complex) {
223
    if (state->out_end_idx > 0) state->out[0] = '\0';
224
    return;
225
  }
226
  const size_t high_water_mark = static_cast<size_t>(state->high_water_mark);
227
  std::memcpy(state->out, state->mangled_begin, high_water_mark);
228
  std::memcpy(state->out + high_water_mark, "--!--", 5);
229
  std::memcpy(state->out + high_water_mark + 5,
230
              state->mangled_begin + high_water_mark,
231
              input_length - high_water_mark);
232
  state->out[input_length + 5] = '\0';
233
}
234
#else
235
0
void UpdateHighWaterMark(State *) {}
236
0
void ReportHighWaterMark(State *) {}
237
#endif
238
239
// Prevent deep recursion / stack exhaustion.
240
// Also prevent unbounded handling of complex inputs.
241
class ComplexityGuard {
242
 public:
243
0
  explicit ComplexityGuard(State *state) : state_(state) {
244
0
    ++state->recursion_depth;
245
0
    ++state->steps;
246
0
  }
247
0
  ~ComplexityGuard() { --state_->recursion_depth; }
248
249
  // 256 levels of recursion seems like a reasonable upper limit on depth.
250
  // 128 is not enough to demangle synthetic tests from demangle_unittest.txt:
251
  // "_ZaaZZZZ..." and "_ZaaZcvZcvZ..."
252
  static constexpr int kRecursionDepthLimit = 256;
253
254
  // We're trying to pick a charitable upper-limit on how many parse steps are
255
  // necessary to handle something that a human could actually make use of.
256
  // This is mostly in place as a bound on how much work we'll do if we are
257
  // asked to demangle an mangled name from an untrusted source, so it should be
258
  // much larger than the largest expected symbol, but much smaller than the
259
  // amount of work we can do in, e.g., a second.
260
  //
261
  // Some real-world symbols from an arbitrary binary started failing between
262
  // 2^12 and 2^13, so we multiply the latter by an extra factor of 16 to set
263
  // the limit.
264
  //
265
  // Spending one second on 2^17 parse steps would require each step to take
266
  // 7.6us, or ~30000 clock cycles, so it's safe to say this can be done in
267
  // under a second.
268
  static constexpr int kParseStepsLimit = 1 << 17;
269
270
0
  bool IsTooComplex() const {
271
0
    if (state_->recursion_depth > kRecursionDepthLimit ||
272
0
        state_->steps > kParseStepsLimit) {
273
#ifdef ABSL_INTERNAL_DEMANGLE_RECORDS_HIGH_WATER_MARK
274
      state_->too_complex = true;
275
#endif
276
0
      return true;
277
0
    }
278
0
    return false;
279
0
  }
280
281
 private:
282
  State *state_;
283
};
284
}  // namespace
285
286
// We don't use strlen() in libc since it's not guaranteed to be async
287
// signal safe.
288
0
static size_t StrLen(const char *str) {
289
0
  size_t len = 0;
290
0
  while (*str != '\0') {
291
0
    ++str;
292
0
    ++len;
293
0
  }
294
0
  return len;
295
0
}
296
297
// Returns true if "str" has at least "n" characters remaining.
298
0
static bool AtLeastNumCharsRemaining(const char *str, size_t n) {
299
0
  for (size_t i = 0; i < n; ++i) {
300
0
    if (str[i] == '\0') {
301
0
      return false;
302
0
    }
303
0
  }
304
0
  return true;
305
0
}
306
307
// Returns true if "str" has "prefix" as a prefix.
308
0
static bool StrPrefix(const char *str, const char *prefix) {
309
0
  size_t i = 0;
310
0
  while (str[i] != '\0' && prefix[i] != '\0' && str[i] == prefix[i]) {
311
0
    ++i;
312
0
  }
313
0
  return prefix[i] == '\0';  // Consumed everything in "prefix".
314
0
}
315
316
static void InitState(State* state,
317
                      const char* mangled,
318
                      char* out,
319
0
                      size_t out_size) {
320
0
  state->mangled_begin = mangled;
321
0
  state->out = out;
322
0
  state->out_end_idx = static_cast<int>(out_size);
323
0
  state->recursion_depth = 0;
324
0
  state->steps = 0;
325
#ifdef ABSL_INTERNAL_DEMANGLE_RECORDS_HIGH_WATER_MARK
326
  state->high_water_mark = 0;
327
  state->too_complex = false;
328
#endif
329
330
0
  state->parse_state.mangled_idx = 0;
331
0
  state->parse_state.out_cur_idx = 0;
332
0
  state->parse_state.prev_name_idx = 0;
333
0
  state->parse_state.prev_name_length = 0;
334
0
  state->parse_state.nest_level = -1;
335
0
  state->parse_state.append = true;
336
0
}
337
338
0
static inline const char *RemainingInput(State *state) {
339
0
  return &state->mangled_begin[state->parse_state.mangled_idx];
340
0
}
341
342
// Returns true and advances "mangled_idx" if we find "one_char_token"
343
// at "mangled_idx" position.  It is assumed that "one_char_token" does
344
// not contain '\0'.
345
0
static bool ParseOneCharToken(State *state, const char one_char_token) {
346
0
  ComplexityGuard guard(state);
347
0
  if (guard.IsTooComplex()) return false;
348
0
  if (RemainingInput(state)[0] == one_char_token) {
349
0
    ++state->parse_state.mangled_idx;
350
0
    UpdateHighWaterMark(state);
351
0
    return true;
352
0
  }
353
0
  return false;
354
0
}
355
356
// Returns true and advances "mangled_idx" if we find "two_char_token"
357
// at "mangled_idx" position.  It is assumed that "two_char_token" does
358
// not contain '\0'.
359
0
static bool ParseTwoCharToken(State *state, const char *two_char_token) {
360
0
  ComplexityGuard guard(state);
361
0
  if (guard.IsTooComplex()) return false;
362
0
  if (RemainingInput(state)[0] == two_char_token[0] &&
363
0
      RemainingInput(state)[1] == two_char_token[1]) {
364
0
    state->parse_state.mangled_idx += 2;
365
0
    UpdateHighWaterMark(state);
366
0
    return true;
367
0
  }
368
0
  return false;
369
0
}
370
371
// Returns true and advances "mangled_idx" if we find "three_char_token"
372
// at "mangled_idx" position.  It is assumed that "three_char_token" does
373
// not contain '\0'.
374
0
static bool ParseThreeCharToken(State *state, const char *three_char_token) {
375
0
  ComplexityGuard guard(state);
376
0
  if (guard.IsTooComplex()) return false;
377
0
  if (RemainingInput(state)[0] == three_char_token[0] &&
378
0
      RemainingInput(state)[1] == three_char_token[1] &&
379
0
      RemainingInput(state)[2] == three_char_token[2]) {
380
0
    state->parse_state.mangled_idx += 3;
381
0
    UpdateHighWaterMark(state);
382
0
    return true;
383
0
  }
384
0
  return false;
385
0
}
386
387
// Returns true and advances "mangled_idx" if we find a copy of the
388
// NUL-terminated string "long_token" at "mangled_idx" position.
389
0
static bool ParseLongToken(State *state, const char *long_token) {
390
0
  ComplexityGuard guard(state);
391
0
  if (guard.IsTooComplex()) return false;
392
0
  int i = 0;
393
0
  for (; long_token[i] != '\0'; ++i) {
394
    // Note that we cannot run off the end of the NUL-terminated input here.
395
    // Inside the loop body, long_token[i] is known to be different from NUL.
396
    // So if we read the NUL on the end of the input here, we return at once.
397
0
    if (RemainingInput(state)[i] != long_token[i]) return false;
398
0
  }
399
0
  state->parse_state.mangled_idx += i;
400
0
  UpdateHighWaterMark(state);
401
0
  return true;
402
0
}
403
404
// Returns true and advances "mangled_cur" if we find any character in
405
// "char_class" at "mangled_cur" position.
406
0
static bool ParseCharClass(State *state, const char *char_class) {
407
0
  ComplexityGuard guard(state);
408
0
  if (guard.IsTooComplex()) return false;
409
0
  if (RemainingInput(state)[0] == '\0') {
410
0
    return false;
411
0
  }
412
0
  const char *p = char_class;
413
0
  for (; *p != '\0'; ++p) {
414
0
    if (RemainingInput(state)[0] == *p) {
415
0
      ++state->parse_state.mangled_idx;
416
0
      UpdateHighWaterMark(state);
417
0
      return true;
418
0
    }
419
0
  }
420
0
  return false;
421
0
}
422
423
0
static bool ParseDigit(State *state, int *digit) {
424
0
  char c = RemainingInput(state)[0];
425
0
  if (ParseCharClass(state, "0123456789")) {
426
0
    if (digit != nullptr) {
427
0
      *digit = c - '0';
428
0
    }
429
0
    return true;
430
0
  }
431
0
  return false;
432
0
}
433
434
// This function is used for handling an optional non-terminal.
435
0
static bool Optional(bool /*status*/) { return true; }
436
437
// This function is used for handling <non-terminal>+ syntax.
438
typedef bool (*ParseFunc)(State *);
439
0
static bool OneOrMore(ParseFunc parse_func, State *state) {
440
0
  if (parse_func(state)) {
441
0
    while (parse_func(state)) {
442
0
    }
443
0
    return true;
444
0
  }
445
0
  return false;
446
0
}
447
448
// This function is used for handling <non-terminal>* syntax. The function
449
// always returns true and must be followed by a termination token or a
450
// terminating sequence not handled by parse_func (e.g.
451
// ParseOneCharToken(state, 'E')).
452
0
static bool ZeroOrMore(ParseFunc parse_func, State *state) {
453
0
  while (parse_func(state)) {
454
0
  }
455
0
  return true;
456
0
}
457
458
// Append "str" at "out_cur_idx".  If there is an overflow, out_cur_idx is
459
// set to out_end_idx+1.  The output string is ensured to
460
// always terminate with '\0' as long as there is no overflow.
461
0
static void Append(State *state, const char *const str, const size_t length) {
462
0
  for (size_t i = 0; i < length; ++i) {
463
0
    if (state->parse_state.out_cur_idx + 1 <
464
0
        state->out_end_idx) {  // +1 for '\0'
465
0
      state->out[state->parse_state.out_cur_idx++] = str[i];
466
0
    } else {
467
      // signal overflow
468
0
      state->parse_state.out_cur_idx = state->out_end_idx + 1;
469
0
      break;
470
0
    }
471
0
  }
472
0
  if (state->parse_state.out_cur_idx < state->out_end_idx) {
473
0
    state->out[state->parse_state.out_cur_idx] =
474
0
        '\0';  // Terminate it with '\0'
475
0
  }
476
0
}
477
478
// We don't use equivalents in libc to avoid locale issues.
479
0
static bool IsLower(char c) { return c >= 'a' && c <= 'z'; }
480
481
0
static bool IsAlpha(char c) {
482
0
  return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
483
0
}
484
485
0
static bool IsDigit(char c) { return c >= '0' && c <= '9'; }
486
487
// Returns true if "str" is a function clone suffix.  These suffixes are used
488
// by GCC 4.5.x and later versions (and our locally-modified version of GCC
489
// 4.4.x) to indicate functions which have been cloned during optimization.
490
// We treat any sequence (.<alpha>+.<digit>+)+ as a function clone suffix.
491
// Additionally, '_' is allowed along with the alphanumeric sequence.
492
0
static bool IsFunctionCloneSuffix(const char *str) {
493
0
  size_t i = 0;
494
0
  while (str[i] != '\0') {
495
0
    bool parsed = false;
496
    // Consume a single [.<alpha> | _]*[.<digit>]* sequence.
497
0
    if (str[i] == '.' && (IsAlpha(str[i + 1]) || str[i + 1] == '_')) {
498
0
      parsed = true;
499
0
      i += 2;
500
0
      while (IsAlpha(str[i]) || str[i] == '_') {
501
0
        ++i;
502
0
      }
503
0
    }
504
0
    if (str[i] == '.' && IsDigit(str[i + 1])) {
505
0
      parsed = true;
506
0
      i += 2;
507
0
      while (IsDigit(str[i])) {
508
0
        ++i;
509
0
      }
510
0
    }
511
0
    if (!parsed)
512
0
      return false;
513
0
  }
514
0
  return true;  // Consumed everything in "str".
515
0
}
516
517
0
static bool EndsWith(State *state, const char chr) {
518
0
  return state->parse_state.out_cur_idx > 0 &&
519
0
         state->parse_state.out_cur_idx < state->out_end_idx &&
520
0
         chr == state->out[state->parse_state.out_cur_idx - 1];
521
0
}
522
523
// Append "str" with some tweaks, iff "append" state is true.
524
static void MaybeAppendWithLength(State *state, const char *const str,
525
0
                                  const size_t length) {
526
0
  if (state->parse_state.append && length > 0) {
527
    // Append a space if the output buffer ends with '<' and "str"
528
    // starts with '<' to avoid <<<.
529
0
    if (str[0] == '<' && EndsWith(state, '<')) {
530
0
      Append(state, " ", 1);
531
0
    }
532
    // Remember the last identifier name for ctors/dtors,
533
    // but only if we haven't yet overflown the buffer.
534
0
    if (state->parse_state.out_cur_idx < state->out_end_idx &&
535
0
        (IsAlpha(str[0]) || str[0] == '_')) {
536
0
      state->parse_state.prev_name_idx = state->parse_state.out_cur_idx;
537
0
      state->parse_state.prev_name_length = static_cast<unsigned int>(length);
538
0
    }
539
0
    Append(state, str, length);
540
0
  }
541
0
}
542
543
// Appends a positive decimal number to the output if appending is enabled.
544
0
static bool MaybeAppendDecimal(State *state, int val) {
545
  // Max {32-64}-bit unsigned int is 20 digits.
546
0
  constexpr size_t kMaxLength = 20;
547
0
  char buf[kMaxLength];
548
549
  // We can't use itoa or sprintf as neither is specified to be
550
  // async-signal-safe.
551
0
  if (state->parse_state.append) {
552
    // We can't have a one-before-the-beginning pointer, so instead start with
553
    // one-past-the-end and manipulate one character before the pointer.
554
0
    char *p = &buf[kMaxLength];
555
0
    do {  // val=0 is the only input that should write a leading zero digit.
556
0
      *--p = static_cast<char>((val % 10) + '0');
557
0
      val /= 10;
558
0
    } while (p > buf && val != 0);
559
560
    // 'p' landed on the last character we set.  How convenient.
561
0
    Append(state, p, kMaxLength - static_cast<size_t>(p - buf));
562
0
  }
563
564
0
  return true;
565
0
}
566
567
// A convenient wrapper around MaybeAppendWithLength().
568
// Returns true so that it can be placed in "if" conditions.
569
0
static bool MaybeAppend(State *state, const char *const str) {
570
0
  if (state->parse_state.append) {
571
0
    size_t length = StrLen(str);
572
0
    MaybeAppendWithLength(state, str, length);
573
0
  }
574
0
  return true;
575
0
}
576
577
// This function is used for handling nested names.
578
0
static bool EnterNestedName(State *state) {
579
0
  state->parse_state.nest_level = 0;
580
0
  return true;
581
0
}
582
583
// This function is used for handling nested names.
584
0
static bool LeaveNestedName(State *state, int16_t prev_value) {
585
0
  state->parse_state.nest_level = prev_value;
586
0
  return true;
587
0
}
588
589
// Disable the append mode not to print function parameters, etc.
590
0
static bool DisableAppend(State *state) {
591
0
  state->parse_state.append = false;
592
0
  return true;
593
0
}
594
595
// Restore the append mode to the previous state.
596
0
static bool RestoreAppend(State *state, bool prev_value) {
597
0
  state->parse_state.append = prev_value;
598
0
  return true;
599
0
}
600
601
// Increase the nest level for nested names.
602
0
static void MaybeIncreaseNestLevel(State *state) {
603
0
  if (state->parse_state.nest_level > -1) {
604
0
    ++state->parse_state.nest_level;
605
0
  }
606
0
}
607
608
// Appends :: for nested names if necessary.
609
0
static void MaybeAppendSeparator(State *state) {
610
0
  if (state->parse_state.nest_level >= 1) {
611
0
    MaybeAppend(state, "::");
612
0
  }
613
0
}
614
615
// Cancel the last separator if necessary.
616
0
static void MaybeCancelLastSeparator(State *state) {
617
0
  if (state->parse_state.nest_level >= 1 && state->parse_state.append &&
618
0
      state->parse_state.out_cur_idx >= 2) {
619
0
    state->parse_state.out_cur_idx -= 2;
620
0
    state->out[state->parse_state.out_cur_idx] = '\0';
621
0
  }
622
0
}
623
624
// Returns true if the identifier of the given length pointed to by
625
// "mangled_cur" is anonymous namespace.
626
0
static bool IdentifierIsAnonymousNamespace(State *state, size_t length) {
627
  // Returns true if "anon_prefix" is a proper prefix of "mangled_cur".
628
0
  static const char anon_prefix[] = "_GLOBAL__N_";
629
0
  return (length > (sizeof(anon_prefix) - 1) &&
630
0
          StrPrefix(RemainingInput(state), anon_prefix));
631
0
}
632
633
// Forward declarations of our parsing functions.
634
static bool ParseMangledName(State *state);
635
static bool ParseEncoding(State *state);
636
static bool ParseName(State *state);
637
static bool ParseUnscopedName(State *state);
638
static bool ParseNestedName(State *state);
639
static bool ParsePrefix(State *state);
640
static bool ParseUnqualifiedName(State *state);
641
static bool ParseSourceName(State *state);
642
static bool ParseLocalSourceName(State *state);
643
static bool ParseUnnamedTypeName(State *state);
644
static bool ParseNumber(State *state, int *number_out);
645
static bool ParseFloatNumber(State *state);
646
static bool ParseSeqId(State *state);
647
static bool ParseIdentifier(State *state, size_t length);
648
static bool ParseOperatorName(State *state, int *arity);
649
static bool ParseConversionOperatorType(State *state);
650
static bool ParseSpecialName(State *state);
651
static bool ParseCallOffset(State *state);
652
static bool ParseNVOffset(State *state);
653
static bool ParseVOffset(State *state);
654
static bool ParseAbiTags(State *state);
655
static bool ParseCtorDtorName(State *state);
656
static bool ParseDecltype(State *state);
657
static bool ParseType(State *state);
658
static bool ParseCVQualifiers(State *state);
659
static bool ParseExtendedQualifier(State *state);
660
static bool ParseBuiltinType(State *state);
661
static bool ParseVendorExtendedType(State *state);
662
static bool ParseFunctionType(State *state);
663
static bool ParseBareFunctionType(State *state);
664
static bool ParseOverloadAttribute(State *state);
665
static bool ParseClassEnumType(State *state);
666
static bool ParseArrayType(State *state);
667
static bool ParsePointerToMemberType(State *state);
668
static bool ParseTemplateParam(State *state);
669
static bool ParseTemplateParamDecl(State *state);
670
static bool ParseTemplateTemplateParam(State *state);
671
static bool ParseTemplateArgs(State *state);
672
static bool ParseTemplateArg(State *state);
673
static bool ParseBaseUnresolvedName(State *state);
674
static bool ParseUnresolvedName(State *state);
675
static bool ParseUnresolvedQualifierLevel(State *state);
676
static bool ParseUnionSelector(State* state);
677
static bool ParseFunctionParam(State* state);
678
static bool ParseBracedExpression(State *state);
679
static bool ParseExpression(State *state);
680
static bool ParseInitializer(State *state);
681
static bool ParseExprPrimary(State *state);
682
static bool ParseExprCastValueAndTrailingE(State *state);
683
static bool ParseQRequiresClauseExpr(State *state);
684
static bool ParseRequirement(State *state);
685
static bool ParseTypeConstraint(State *state);
686
static bool ParseLocalName(State *state);
687
static bool ParseLocalNameSuffix(State *state);
688
static bool ParseDiscriminator(State *state);
689
static bool ParseSubstitution(State *state, bool accept_std);
690
691
// Implementation note: the following code is a straightforward
692
// translation of the Itanium C++ ABI defined in BNF with a couple of
693
// exceptions.
694
//
695
// - Support GNU extensions not defined in the Itanium C++ ABI
696
// - <prefix> and <template-prefix> are combined to avoid infinite loop
697
// - Reorder patterns to shorten the code
698
// - Reorder patterns to give greedier functions precedence
699
//   We'll mark "Less greedy than" for these cases in the code
700
//
701
// Each parsing function changes the parse state and returns true on
702
// success, or returns false and doesn't change the parse state (note:
703
// the parse-steps counter increases regardless of success or failure).
704
// To ensure that the parse state isn't changed in the latter case, we
705
// save the original state before we call multiple parsing functions
706
// consecutively with &&, and restore it if unsuccessful.  See
707
// ParseEncoding() as an example of this convention.  We follow the
708
// convention throughout the code.
709
//
710
// Originally we tried to do demangling without following the full ABI
711
// syntax but it turned out we needed to follow the full syntax to
712
// parse complicated cases like nested template arguments.  Note that
713
// implementing a full-fledged demangler isn't trivial (libiberty's
714
// cp-demangle.c has +4300 lines).
715
//
716
// Note that (foo) in <(foo) ...> is a modifier to be ignored.
717
//
718
// Reference:
719
// - Itanium C++ ABI
720
//   <https://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling>
721
722
// <mangled-name> ::= _Z <encoding>
723
0
static bool ParseMangledName(State *state) {
724
0
  ComplexityGuard guard(state);
725
0
  if (guard.IsTooComplex()) return false;
726
0
  return ParseTwoCharToken(state, "_Z") && ParseEncoding(state);
727
0
}
728
729
// <encoding> ::= <(function) name> <bare-function-type>
730
//                [`Q` <requires-clause expr>]
731
//            ::= <(data) name>
732
//            ::= <special-name>
733
//
734
// NOTE: Based on http://shortn/_Hoq9qG83rx
735
0
static bool ParseEncoding(State *state) {
736
0
  ComplexityGuard guard(state);
737
0
  if (guard.IsTooComplex()) return false;
738
  // Since the first two productions both start with <name>, attempt
739
  // to parse it only once to avoid exponential blowup of backtracking.
740
  //
741
  // We're careful about exponential blowup because <encoding> recursively
742
  // appears in other productions downstream of its first two productions,
743
  // which means that every call to `ParseName` would possibly indirectly
744
  // result in two calls to `ParseName` etc.
745
0
  if (ParseName(state)) {
746
0
    if (!ParseBareFunctionType(state)) {
747
0
      return true;  // <(data) name>
748
0
    }
749
750
    // Parsed: <(function) name> <bare-function-type>
751
    // Pending: [`Q` <requires-clause expr>]
752
0
    ParseQRequiresClauseExpr(state);  // restores state on failure
753
0
    return true;
754
0
  }
755
756
0
  if (ParseSpecialName(state)) {
757
0
    return true;  // <special-name>
758
0
  }
759
0
  return false;
760
0
}
761
762
// <name> ::= <nested-name>
763
//        ::= <unscoped-template-name> <template-args>
764
//        ::= <unscoped-name>
765
//        ::= <local-name>
766
0
static bool ParseName(State *state) {
767
0
  ComplexityGuard guard(state);
768
0
  if (guard.IsTooComplex()) return false;
769
0
  if (ParseNestedName(state) || ParseLocalName(state)) {
770
0
    return true;
771
0
  }
772
773
  // We reorganize the productions to avoid re-parsing unscoped names.
774
  // - Inline <unscoped-template-name> productions:
775
  //   <name> ::= <substitution> <template-args>
776
  //          ::= <unscoped-name> <template-args>
777
  //          ::= <unscoped-name>
778
  // - Merge the two productions that start with unscoped-name:
779
  //   <name> ::= <unscoped-name> [<template-args>]
780
781
0
  ParseState copy = state->parse_state;
782
  // "std<...>" isn't a valid name.
783
0
  if (ParseSubstitution(state, /*accept_std=*/false) &&
784
0
      ParseTemplateArgs(state)) {
785
0
    return true;
786
0
  }
787
0
  state->parse_state = copy;
788
789
  // Note there's no need to restore state after this since only the first
790
  // subparser can fail.
791
0
  return ParseUnscopedName(state) && Optional(ParseTemplateArgs(state));
792
0
}
793
794
// <unscoped-name> ::= <unqualified-name>
795
//                 ::= St <unqualified-name>
796
0
static bool ParseUnscopedName(State *state) {
797
0
  ComplexityGuard guard(state);
798
0
  if (guard.IsTooComplex()) return false;
799
0
  if (ParseUnqualifiedName(state)) {
800
0
    return true;
801
0
  }
802
803
0
  ParseState copy = state->parse_state;
804
0
  if (ParseTwoCharToken(state, "St") && MaybeAppend(state, "std::") &&
805
0
      ParseUnqualifiedName(state)) {
806
0
    return true;
807
0
  }
808
0
  state->parse_state = copy;
809
0
  return false;
810
0
}
811
812
// <ref-qualifer> ::= R // lvalue method reference qualifier
813
//                ::= O // rvalue method reference qualifier
814
0
static inline bool ParseRefQualifier(State *state) {
815
0
  return ParseCharClass(state, "OR");
816
0
}
817
818
// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
819
//                   <unqualified-name> E
820
//               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
821
//                   <template-args> E
822
0
static bool ParseNestedName(State *state) {
823
0
  ComplexityGuard guard(state);
824
0
  if (guard.IsTooComplex()) return false;
825
0
  ParseState copy = state->parse_state;
826
0
  if (ParseOneCharToken(state, 'N') && EnterNestedName(state) &&
827
0
      Optional(ParseCVQualifiers(state)) &&
828
0
      Optional(ParseRefQualifier(state)) && ParsePrefix(state) &&
829
0
      LeaveNestedName(state, copy.nest_level) &&
830
0
      ParseOneCharToken(state, 'E')) {
831
0
    return true;
832
0
  }
833
0
  state->parse_state = copy;
834
0
  return false;
835
0
}
836
837
// This part is tricky.  If we literally translate them to code, we'll
838
// end up infinite loop.  Hence we merge them to avoid the case.
839
//
840
// <prefix> ::= <prefix> <unqualified-name>
841
//          ::= <template-prefix> <template-args>
842
//          ::= <template-param>
843
//          ::= <decltype>
844
//          ::= <substitution>
845
//          ::= # empty
846
// <template-prefix> ::= <prefix> <(template) unqualified-name>
847
//                   ::= <template-param>
848
//                   ::= <substitution>
849
//                   ::= <vendor-extended-type>
850
0
static bool ParsePrefix(State *state) {
851
0
  ComplexityGuard guard(state);
852
0
  if (guard.IsTooComplex()) return false;
853
0
  bool has_something = false;
854
0
  while (true) {
855
0
    MaybeAppendSeparator(state);
856
0
    if (ParseTemplateParam(state) || ParseDecltype(state) ||
857
0
        ParseSubstitution(state, /*accept_std=*/true) ||
858
        // Although the official grammar does not mention it, nested-names
859
        // shaped like Nu14__some_builtinIiE6memberE occur in practice, and it
860
        // is not clear what else a compiler is supposed to do when a
861
        // vendor-extended type has named members.
862
0
        ParseVendorExtendedType(state) ||
863
0
        ParseUnscopedName(state) ||
864
0
        (ParseOneCharToken(state, 'M') && ParseUnnamedTypeName(state))) {
865
0
      has_something = true;
866
0
      MaybeIncreaseNestLevel(state);
867
0
      continue;
868
0
    }
869
0
    MaybeCancelLastSeparator(state);
870
0
    if (has_something && ParseTemplateArgs(state)) {
871
0
      return ParsePrefix(state);
872
0
    } else {
873
0
      break;
874
0
    }
875
0
  }
876
0
  return true;
877
0
}
878
879
// <unqualified-name> ::= <operator-name> [<abi-tags>]
880
//                    ::= <ctor-dtor-name> [<abi-tags>]
881
//                    ::= <source-name> [<abi-tags>]
882
//                    ::= <local-source-name> [<abi-tags>]
883
//                    ::= <unnamed-type-name> [<abi-tags>]
884
//                    ::= DC <source-name>+ E  # C++17 structured binding
885
//                    ::= F <source-name>  # C++20 constrained friend
886
//                    ::= F <operator-name>  # C++20 constrained friend
887
//
888
// <local-source-name> is a GCC extension; see below.
889
//
890
// For the F notation for constrained friends, see
891
// https://github.com/itanium-cxx-abi/cxx-abi/issues/24#issuecomment-1491130332.
892
0
static bool ParseUnqualifiedName(State *state) {
893
0
  ComplexityGuard guard(state);
894
0
  if (guard.IsTooComplex()) return false;
895
0
  if (ParseOperatorName(state, nullptr) || ParseCtorDtorName(state) ||
896
0
      ParseSourceName(state) || ParseLocalSourceName(state) ||
897
0
      ParseUnnamedTypeName(state)) {
898
0
    return ParseAbiTags(state);
899
0
  }
900
901
  // DC <source-name>+ E
902
0
  ParseState copy = state->parse_state;
903
0
  if (ParseTwoCharToken(state, "DC") && OneOrMore(ParseSourceName, state) &&
904
0
      ParseOneCharToken(state, 'E')) {
905
0
    return true;
906
0
  }
907
0
  state->parse_state = copy;
908
909
  // F <source-name>
910
  // F <operator-name>
911
0
  if (ParseOneCharToken(state, 'F') && MaybeAppend(state, "friend ") &&
912
0
      (ParseSourceName(state) || ParseOperatorName(state, nullptr))) {
913
0
    return true;
914
0
  }
915
0
  state->parse_state = copy;
916
917
0
  return false;
918
0
}
919
920
// <abi-tags> ::= <abi-tag> [<abi-tags>]
921
// <abi-tag>  ::= B <source-name>
922
0
static bool ParseAbiTags(State *state) {
923
0
  ComplexityGuard guard(state);
924
0
  if (guard.IsTooComplex()) return false;
925
926
0
  while (ParseOneCharToken(state, 'B')) {
927
0
    ParseState copy = state->parse_state;
928
0
    MaybeAppend(state, "[abi:");
929
930
0
    if (!ParseSourceName(state)) {
931
0
      state->parse_state = copy;
932
0
      return false;
933
0
    }
934
0
    MaybeAppend(state, "]");
935
0
  }
936
937
0
  return true;
938
0
}
939
940
// <source-name> ::= <positive length number> <identifier>
941
0
static bool ParseSourceName(State *state) {
942
0
  ComplexityGuard guard(state);
943
0
  if (guard.IsTooComplex()) return false;
944
0
  ParseState copy = state->parse_state;
945
0
  int length = -1;
946
0
  if (ParseNumber(state, &length) &&
947
0
      ParseIdentifier(state, static_cast<size_t>(length))) {
948
0
    return true;
949
0
  }
950
0
  state->parse_state = copy;
951
0
  return false;
952
0
}
953
954
// <local-source-name> ::= L <source-name> [<discriminator>]
955
//
956
// References:
957
//   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=31775
958
//   https://gcc.gnu.org/viewcvs?view=rev&revision=124467
959
0
static bool ParseLocalSourceName(State *state) {
960
0
  ComplexityGuard guard(state);
961
0
  if (guard.IsTooComplex()) return false;
962
0
  ParseState copy = state->parse_state;
963
0
  if (ParseOneCharToken(state, 'L') && ParseSourceName(state) &&
964
0
      Optional(ParseDiscriminator(state))) {
965
0
    return true;
966
0
  }
967
0
  state->parse_state = copy;
968
0
  return false;
969
0
}
970
971
// <unnamed-type-name> ::= Ut [<(nonnegative) number>] _
972
//                     ::= <closure-type-name>
973
// <closure-type-name> ::= Ul <lambda-sig> E [<(nonnegative) number>] _
974
// <lambda-sig>        ::= <template-param-decl>* <(parameter) type>+
975
//
976
// For <template-param-decl>* in <lambda-sig> see:
977
//
978
// https://github.com/itanium-cxx-abi/cxx-abi/issues/31
979
0
static bool ParseUnnamedTypeName(State *state) {
980
0
  ComplexityGuard guard(state);
981
0
  if (guard.IsTooComplex()) return false;
982
0
  ParseState copy = state->parse_state;
983
  // Type's 1-based index n is encoded as { "", n == 1; itoa(n-2), otherwise }.
984
  // Optionally parse the encoded value into 'which' and add 2 to get the index.
985
0
  int which = -1;
986
987
  // Unnamed type local to function or class.
988
0
  if (ParseTwoCharToken(state, "Ut") && Optional(ParseNumber(state, &which)) &&
989
0
      which <= std::numeric_limits<int>::max() - 2 &&  // Don't overflow.
990
0
      ParseOneCharToken(state, '_')) {
991
0
    MaybeAppend(state, "{unnamed type#");
992
0
    MaybeAppendDecimal(state, 2 + which);
993
0
    MaybeAppend(state, "}");
994
0
    return true;
995
0
  }
996
0
  state->parse_state = copy;
997
998
  // Closure type.
999
0
  which = -1;
1000
0
  if (ParseTwoCharToken(state, "Ul") && DisableAppend(state) &&
1001
0
      ZeroOrMore(ParseTemplateParamDecl, state) &&
1002
0
      OneOrMore(ParseType, state) && RestoreAppend(state, copy.append) &&
1003
0
      ParseOneCharToken(state, 'E') && Optional(ParseNumber(state, &which)) &&
1004
0
      which <= std::numeric_limits<int>::max() - 2 &&  // Don't overflow.
1005
0
      ParseOneCharToken(state, '_')) {
1006
0
    MaybeAppend(state, "{lambda()#");
1007
0
    MaybeAppendDecimal(state, 2 + which);
1008
0
    MaybeAppend(state, "}");
1009
0
    return true;
1010
0
  }
1011
0
  state->parse_state = copy;
1012
1013
0
  return false;
1014
0
}
1015
1016
// <number> ::= [n] <non-negative decimal integer>
1017
// If "number_out" is non-null, then *number_out is set to the value of the
1018
// parsed number on success.
1019
0
static bool ParseNumber(State *state, int *number_out) {
1020
0
  ComplexityGuard guard(state);
1021
0
  if (guard.IsTooComplex()) return false;
1022
0
  bool negative = false;
1023
0
  if (ParseOneCharToken(state, 'n')) {
1024
0
    negative = true;
1025
0
  }
1026
0
  const char *p = RemainingInput(state);
1027
0
  uint64_t number = 0;
1028
0
  for (; *p != '\0'; ++p) {
1029
0
    if (IsDigit(*p)) {
1030
0
      number = number * 10 + static_cast<uint64_t>(*p - '0');
1031
0
    } else {
1032
0
      break;
1033
0
    }
1034
0
  }
1035
  // Apply the sign with uint64_t arithmetic so overflows aren't UB.  Gives
1036
  // "incorrect" results for out-of-range inputs, but negative values only
1037
  // appear for literals, which aren't printed.
1038
0
  if (negative) {
1039
0
    number = ~number + 1;
1040
0
  }
1041
0
  if (p != RemainingInput(state)) {  // Conversion succeeded.
1042
0
    state->parse_state.mangled_idx += p - RemainingInput(state);
1043
0
    UpdateHighWaterMark(state);
1044
0
    if (number_out != nullptr) {
1045
      // Note: possibly truncate "number".
1046
0
      *number_out = static_cast<int>(number);
1047
0
    }
1048
0
    return true;
1049
0
  }
1050
0
  return false;
1051
0
}
1052
1053
// Floating-point literals are encoded using a fixed-length lowercase
1054
// hexadecimal string.
1055
0
static bool ParseFloatNumber(State *state) {
1056
0
  ComplexityGuard guard(state);
1057
0
  if (guard.IsTooComplex()) return false;
1058
0
  const char *p = RemainingInput(state);
1059
0
  for (; *p != '\0'; ++p) {
1060
0
    if (!IsDigit(*p) && !(*p >= 'a' && *p <= 'f')) {
1061
0
      break;
1062
0
    }
1063
0
  }
1064
0
  if (p != RemainingInput(state)) {  // Conversion succeeded.
1065
0
    state->parse_state.mangled_idx += p - RemainingInput(state);
1066
0
    UpdateHighWaterMark(state);
1067
0
    return true;
1068
0
  }
1069
0
  return false;
1070
0
}
1071
1072
// The <seq-id> is a sequence number in base 36,
1073
// using digits and upper case letters
1074
0
static bool ParseSeqId(State *state) {
1075
0
  ComplexityGuard guard(state);
1076
0
  if (guard.IsTooComplex()) return false;
1077
0
  const char *p = RemainingInput(state);
1078
0
  for (; *p != '\0'; ++p) {
1079
0
    if (!IsDigit(*p) && !(*p >= 'A' && *p <= 'Z')) {
1080
0
      break;
1081
0
    }
1082
0
  }
1083
0
  if (p != RemainingInput(state)) {  // Conversion succeeded.
1084
0
    state->parse_state.mangled_idx += p - RemainingInput(state);
1085
0
    UpdateHighWaterMark(state);
1086
0
    return true;
1087
0
  }
1088
0
  return false;
1089
0
}
1090
1091
// <identifier> ::= <unqualified source code identifier> (of given length)
1092
0
static bool ParseIdentifier(State *state, size_t length) {
1093
0
  ComplexityGuard guard(state);
1094
0
  if (guard.IsTooComplex()) return false;
1095
0
  if (!AtLeastNumCharsRemaining(RemainingInput(state), length)) {
1096
0
    return false;
1097
0
  }
1098
0
  if (IdentifierIsAnonymousNamespace(state, length)) {
1099
0
    MaybeAppend(state, "(anonymous namespace)");
1100
0
  } else {
1101
0
    MaybeAppendWithLength(state, RemainingInput(state), length);
1102
0
  }
1103
0
  state->parse_state.mangled_idx += length;
1104
0
  UpdateHighWaterMark(state);
1105
0
  return true;
1106
0
}
1107
1108
// <operator-name> ::= nw, and other two letters cases
1109
//                 ::= cv <type>  # (cast)
1110
//                 ::= li <source-name>  # C++11 user-defined literal
1111
//                 ::= v  <digit> <source-name> # vendor extended operator
1112
0
static bool ParseOperatorName(State *state, int *arity) {
1113
0
  ComplexityGuard guard(state);
1114
0
  if (guard.IsTooComplex()) return false;
1115
0
  if (!AtLeastNumCharsRemaining(RemainingInput(state), 2)) {
1116
0
    return false;
1117
0
  }
1118
  // First check with "cv" (cast) case.
1119
0
  ParseState copy = state->parse_state;
1120
0
  if (ParseTwoCharToken(state, "cv") && MaybeAppend(state, "operator ") &&
1121
0
      EnterNestedName(state) && ParseConversionOperatorType(state) &&
1122
0
      LeaveNestedName(state, copy.nest_level)) {
1123
0
    if (arity != nullptr) {
1124
0
      *arity = 1;
1125
0
    }
1126
0
    return true;
1127
0
  }
1128
0
  state->parse_state = copy;
1129
1130
  // Then user-defined literals.
1131
0
  if (ParseTwoCharToken(state, "li") && MaybeAppend(state, "operator\"\" ") &&
1132
0
      ParseSourceName(state)) {
1133
0
    return true;
1134
0
  }
1135
0
  state->parse_state = copy;
1136
1137
  // Then vendor extended operators.
1138
0
  if (ParseOneCharToken(state, 'v') && ParseDigit(state, arity) &&
1139
0
      ParseSourceName(state)) {
1140
0
    return true;
1141
0
  }
1142
0
  state->parse_state = copy;
1143
1144
  // Other operator names should start with a lower alphabet followed
1145
  // by a lower/upper alphabet.
1146
0
  if (!(IsLower(RemainingInput(state)[0]) &&
1147
0
        IsAlpha(RemainingInput(state)[1]))) {
1148
0
    return false;
1149
0
  }
1150
  // We may want to perform a binary search if we really need speed.
1151
0
  const AbbrevPair *p;
1152
0
  for (p = kOperatorList; p->abbrev != nullptr; ++p) {
1153
0
    if (RemainingInput(state)[0] == p->abbrev[0] &&
1154
0
        RemainingInput(state)[1] == p->abbrev[1]) {
1155
0
      if (arity != nullptr) {
1156
0
        *arity = p->arity;
1157
0
      }
1158
0
      MaybeAppend(state, "operator");
1159
0
      if (IsLower(*p->real_name)) {  // new, delete, etc.
1160
0
        MaybeAppend(state, " ");
1161
0
      }
1162
0
      MaybeAppend(state, p->real_name);
1163
0
      state->parse_state.mangled_idx += 2;
1164
0
      UpdateHighWaterMark(state);
1165
0
      return true;
1166
0
    }
1167
0
  }
1168
0
  return false;
1169
0
}
1170
1171
// <operator-name> ::= cv <type>  # (cast)
1172
//
1173
// The name of a conversion operator is the one place where cv-qualifiers, *, &,
1174
// and other simple type combinators are expected to appear in our stripped-down
1175
// demangling (elsewhere they appear in function signatures or template
1176
// arguments, which we omit from the output).  We make reasonable efforts to
1177
// render simple cases accurately.
1178
0
static bool ParseConversionOperatorType(State *state) {
1179
0
  ComplexityGuard guard(state);
1180
0
  if (guard.IsTooComplex()) return false;
1181
0
  ParseState copy = state->parse_state;
1182
1183
  // Scan pointers, const, and other easy mangling prefixes with postfix
1184
  // demanglings.  Remember the range of input for later rescanning.
1185
  //
1186
  // See `ParseType` and the `switch` below for the meaning of each char.
1187
0
  const char* begin_simple_prefixes = RemainingInput(state);
1188
0
  while (ParseCharClass(state, "OPRCGrVK")) {}
1189
0
  const char* end_simple_prefixes = RemainingInput(state);
1190
1191
  // Emit the base type first.
1192
0
  if (!ParseType(state)) {
1193
0
    state->parse_state = copy;
1194
0
    return false;
1195
0
  }
1196
1197
  // Then rescan the easy type combinators in reverse order to emit their
1198
  // demanglings in the expected output order.
1199
0
  while (begin_simple_prefixes != end_simple_prefixes) {
1200
0
    switch (*--end_simple_prefixes) {
1201
0
      case 'P':
1202
0
        MaybeAppend(state, "*");
1203
0
        break;
1204
0
      case 'R':
1205
0
        MaybeAppend(state, "&");
1206
0
        break;
1207
0
      case 'O':
1208
0
        MaybeAppend(state, "&&");
1209
0
        break;
1210
0
      case 'C':
1211
0
        MaybeAppend(state, " _Complex");
1212
0
        break;
1213
0
      case 'G':
1214
0
        MaybeAppend(state, " _Imaginary");
1215
0
        break;
1216
0
      case 'r':
1217
0
        MaybeAppend(state, " restrict");
1218
0
        break;
1219
0
      case 'V':
1220
0
        MaybeAppend(state, " volatile");
1221
0
        break;
1222
0
      case 'K':
1223
0
        MaybeAppend(state, " const");
1224
0
        break;
1225
0
    }
1226
0
  }
1227
0
  return true;
1228
0
}
1229
1230
// <special-name> ::= TV <type>
1231
//                ::= TT <type>
1232
//                ::= TI <type>
1233
//                ::= TS <type>
1234
//                ::= TW <name>  # thread-local wrapper
1235
//                ::= TH <name>  # thread-local initialization
1236
//                ::= Tc <call-offset> <call-offset> <(base) encoding>
1237
//                ::= GV <(object) name>
1238
//                ::= GR <(object) name> [<seq-id>] _
1239
//                ::= T <call-offset> <(base) encoding>
1240
//                ::= GTt <encoding>  # transaction-safe entry point
1241
//                ::= TA <template-arg>  # nontype template parameter object
1242
// G++ extensions:
1243
//                ::= TC <type> <(offset) number> _ <(base) type>
1244
//                ::= TF <type>
1245
//                ::= TJ <type>
1246
//                ::= GR <name>  # without final _, perhaps an earlier form?
1247
//                ::= GA <encoding>
1248
//                ::= Th <call-offset> <(base) encoding>
1249
//                ::= Tv <call-offset> <(base) encoding>
1250
//
1251
// Note: Most of these are special data, not functions that occur in stack
1252
// traces.  Exceptions are TW and TH, which denote functions supporting the
1253
// thread_local feature.  For these see:
1254
//
1255
// https://maskray.me/blog/2021-02-14-all-about-thread-local-storage
1256
//
1257
// For TA see https://github.com/itanium-cxx-abi/cxx-abi/issues/63.
1258
0
static bool ParseSpecialName(State *state) {
1259
0
  ComplexityGuard guard(state);
1260
0
  if (guard.IsTooComplex()) return false;
1261
0
  ParseState copy = state->parse_state;
1262
1263
0
  if (ParseTwoCharToken(state, "TW")) {
1264
0
    MaybeAppend(state, "thread-local wrapper routine for ");
1265
0
    if (ParseName(state)) return true;
1266
0
    state->parse_state = copy;
1267
0
    return false;
1268
0
  }
1269
1270
0
  if (ParseTwoCharToken(state, "TH")) {
1271
0
    MaybeAppend(state, "thread-local initialization routine for ");
1272
0
    if (ParseName(state)) return true;
1273
0
    state->parse_state = copy;
1274
0
    return false;
1275
0
  }
1276
1277
0
  if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "VTIS") &&
1278
0
      ParseType(state)) {
1279
0
    return true;
1280
0
  }
1281
0
  state->parse_state = copy;
1282
1283
0
  if (ParseTwoCharToken(state, "Tc") && ParseCallOffset(state) &&
1284
0
      ParseCallOffset(state) && ParseEncoding(state)) {
1285
0
    return true;
1286
0
  }
1287
0
  state->parse_state = copy;
1288
1289
0
  if (ParseTwoCharToken(state, "GV") && ParseName(state)) {
1290
0
    return true;
1291
0
  }
1292
0
  state->parse_state = copy;
1293
1294
0
  if (ParseOneCharToken(state, 'T') && ParseCallOffset(state) &&
1295
0
      ParseEncoding(state)) {
1296
0
    return true;
1297
0
  }
1298
0
  state->parse_state = copy;
1299
1300
  // G++ extensions
1301
0
  if (ParseTwoCharToken(state, "TC") && ParseType(state) &&
1302
0
      ParseNumber(state, nullptr) && ParseOneCharToken(state, '_') &&
1303
0
      DisableAppend(state) && ParseType(state)) {
1304
0
    RestoreAppend(state, copy.append);
1305
0
    return true;
1306
0
  }
1307
0
  state->parse_state = copy;
1308
1309
0
  if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "FJ") &&
1310
0
      ParseType(state)) {
1311
0
    return true;
1312
0
  }
1313
0
  state->parse_state = copy;
1314
1315
  // <special-name> ::= GR <(object) name> [<seq-id>] _  # modern standard
1316
  //                ::= GR <(object) name>  # also recognized
1317
0
  if (ParseTwoCharToken(state, "GR")) {
1318
0
    MaybeAppend(state, "reference temporary for ");
1319
0
    if (!ParseName(state)) {
1320
0
      state->parse_state = copy;
1321
0
      return false;
1322
0
    }
1323
0
    const bool has_seq_id = ParseSeqId(state);
1324
0
    const bool has_underscore = ParseOneCharToken(state, '_');
1325
0
    if (has_seq_id && !has_underscore) {
1326
0
      state->parse_state = copy;
1327
0
      return false;
1328
0
    }
1329
0
    return true;
1330
0
  }
1331
1332
0
  if (ParseTwoCharToken(state, "GA") && ParseEncoding(state)) {
1333
0
    return true;
1334
0
  }
1335
0
  state->parse_state = copy;
1336
1337
0
  if (ParseThreeCharToken(state, "GTt") &&
1338
0
      MaybeAppend(state, "transaction clone for ") && ParseEncoding(state)) {
1339
0
    return true;
1340
0
  }
1341
0
  state->parse_state = copy;
1342
1343
0
  if (ParseOneCharToken(state, 'T') && ParseCharClass(state, "hv") &&
1344
0
      ParseCallOffset(state) && ParseEncoding(state)) {
1345
0
    return true;
1346
0
  }
1347
0
  state->parse_state = copy;
1348
1349
0
  if (ParseTwoCharToken(state, "TA")) {
1350
0
    bool append = state->parse_state.append;
1351
0
    DisableAppend(state);
1352
0
    if (ParseTemplateArg(state)) {
1353
0
      RestoreAppend(state, append);
1354
0
      MaybeAppend(state, "template parameter object");
1355
0
      return true;
1356
0
    }
1357
0
  }
1358
0
  state->parse_state = copy;
1359
1360
0
  return false;
1361
0
}
1362
1363
// <call-offset> ::= h <nv-offset> _
1364
//               ::= v <v-offset> _
1365
0
static bool ParseCallOffset(State *state) {
1366
0
  ComplexityGuard guard(state);
1367
0
  if (guard.IsTooComplex()) return false;
1368
0
  ParseState copy = state->parse_state;
1369
0
  if (ParseOneCharToken(state, 'h') && ParseNVOffset(state) &&
1370
0
      ParseOneCharToken(state, '_')) {
1371
0
    return true;
1372
0
  }
1373
0
  state->parse_state = copy;
1374
1375
0
  if (ParseOneCharToken(state, 'v') && ParseVOffset(state) &&
1376
0
      ParseOneCharToken(state, '_')) {
1377
0
    return true;
1378
0
  }
1379
0
  state->parse_state = copy;
1380
1381
0
  return false;
1382
0
}
1383
1384
// <nv-offset> ::= <(offset) number>
1385
0
static bool ParseNVOffset(State *state) {
1386
0
  ComplexityGuard guard(state);
1387
0
  if (guard.IsTooComplex()) return false;
1388
0
  return ParseNumber(state, nullptr);
1389
0
}
1390
1391
// <v-offset>  ::= <(offset) number> _ <(virtual offset) number>
1392
0
static bool ParseVOffset(State *state) {
1393
0
  ComplexityGuard guard(state);
1394
0
  if (guard.IsTooComplex()) return false;
1395
0
  ParseState copy = state->parse_state;
1396
0
  if (ParseNumber(state, nullptr) && ParseOneCharToken(state, '_') &&
1397
0
      ParseNumber(state, nullptr)) {
1398
0
    return true;
1399
0
  }
1400
0
  state->parse_state = copy;
1401
0
  return false;
1402
0
}
1403
1404
// <ctor-dtor-name> ::= C1 | C2 | C3 | CI1 <base-class-type> | CI2
1405
// <base-class-type>
1406
//                  ::= D0 | D1 | D2
1407
// # GCC extensions: "unified" constructor/destructor.  See
1408
// #
1409
// https://github.com/gcc-mirror/gcc/blob/7ad17b583c3643bd4557f29b8391ca7ef08391f5/gcc/cp/mangle.c#L1847
1410
//                  ::= C4 | D4
1411
0
static bool ParseCtorDtorName(State *state) {
1412
0
  ComplexityGuard guard(state);
1413
0
  if (guard.IsTooComplex()) return false;
1414
0
  ParseState copy = state->parse_state;
1415
0
  if (ParseOneCharToken(state, 'C')) {
1416
0
    if (ParseCharClass(state, "1234")) {
1417
0
      const char *const prev_name =
1418
0
          state->out + state->parse_state.prev_name_idx;
1419
0
      MaybeAppendWithLength(state, prev_name,
1420
0
                            state->parse_state.prev_name_length);
1421
0
      return true;
1422
0
    } else if (ParseOneCharToken(state, 'I') && ParseCharClass(state, "12") &&
1423
0
               ParseClassEnumType(state)) {
1424
0
      return true;
1425
0
    }
1426
0
  }
1427
0
  state->parse_state = copy;
1428
1429
0
  if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "0124")) {
1430
0
    const char *const prev_name = state->out + state->parse_state.prev_name_idx;
1431
0
    MaybeAppend(state, "~");
1432
0
    MaybeAppendWithLength(state, prev_name,
1433
0
                          state->parse_state.prev_name_length);
1434
0
    return true;
1435
0
  }
1436
0
  state->parse_state = copy;
1437
0
  return false;
1438
0
}
1439
1440
// <decltype> ::= Dt <expression> E  # decltype of an id-expression or class
1441
//                                   # member access (C++0x)
1442
//            ::= DT <expression> E  # decltype of an expression (C++0x)
1443
0
static bool ParseDecltype(State *state) {
1444
0
  ComplexityGuard guard(state);
1445
0
  if (guard.IsTooComplex()) return false;
1446
1447
0
  ParseState copy = state->parse_state;
1448
0
  if (ParseOneCharToken(state, 'D') && ParseCharClass(state, "tT") &&
1449
0
      ParseExpression(state) && ParseOneCharToken(state, 'E')) {
1450
0
    return true;
1451
0
  }
1452
0
  state->parse_state = copy;
1453
1454
0
  return false;
1455
0
}
1456
1457
// <type> ::= <CV-qualifiers> <type>
1458
//        ::= P <type>   # pointer-to
1459
//        ::= R <type>   # reference-to
1460
//        ::= O <type>   # rvalue reference-to (C++0x)
1461
//        ::= C <type>   # complex pair (C 2000)
1462
//        ::= G <type>   # imaginary (C 2000)
1463
//        ::= <builtin-type>
1464
//        ::= <function-type>
1465
//        ::= <class-enum-type>  # note: just an alias for <name>
1466
//        ::= <array-type>
1467
//        ::= <pointer-to-member-type>
1468
//        ::= <template-template-param> <template-args>
1469
//        ::= <template-param>
1470
//        ::= <decltype>
1471
//        ::= <substitution>
1472
//        ::= Dp <type>          # pack expansion of (C++0x)
1473
//        ::= Dv <(elements) number> _ <type>  # GNU vector extension
1474
//        ::= Dv <(bytes) expression> _ <type>
1475
//        ::= Dk <type-constraint>  # constrained auto
1476
//
1477
0
static bool ParseType(State *state) {
1478
0
  ComplexityGuard guard(state);
1479
0
  if (guard.IsTooComplex()) return false;
1480
0
  ParseState copy = state->parse_state;
1481
1482
  // We should check CV-qualifers, and PRGC things first.
1483
  //
1484
  // CV-qualifiers overlap with some operator names, but an operator name is not
1485
  // valid as a type.  To avoid an ambiguity that can lead to exponential time
1486
  // complexity, refuse to backtrack the CV-qualifiers.
1487
  //
1488
  // _Z4aoeuIrMvvE
1489
  //  => _Z 4aoeuI        rM  v     v   E
1490
  //         aoeu<operator%=, void, void>
1491
  //  => _Z 4aoeuI r Mv v              E
1492
  //         aoeu<void void::* restrict>
1493
  //
1494
  // By consuming the CV-qualifiers first, the former parse is disabled.
1495
0
  if (ParseCVQualifiers(state)) {
1496
0
    const bool result = ParseType(state);
1497
0
    if (!result) state->parse_state = copy;
1498
0
    return result;
1499
0
  }
1500
0
  state->parse_state = copy;
1501
1502
  // Similarly, these tag characters can overlap with other <name>s resulting in
1503
  // two different parse prefixes that land on <template-args> in the same
1504
  // place, such as "C3r1xI...".  So, disable the "ctor-name = C3" parse by
1505
  // refusing to backtrack the tag characters.
1506
0
  if (ParseCharClass(state, "OPRCG")) {
1507
0
    const bool result = ParseType(state);
1508
0
    if (!result) state->parse_state = copy;
1509
0
    return result;
1510
0
  }
1511
0
  state->parse_state = copy;
1512
1513
0
  if (ParseTwoCharToken(state, "Dp") && ParseType(state)) {
1514
0
    return true;
1515
0
  }
1516
0
  state->parse_state = copy;
1517
1518
0
  if (ParseBuiltinType(state) || ParseFunctionType(state) ||
1519
0
      ParseClassEnumType(state) || ParseArrayType(state) ||
1520
0
      ParsePointerToMemberType(state) || ParseDecltype(state) ||
1521
      // "std" on its own isn't a type.
1522
0
      ParseSubstitution(state, /*accept_std=*/false)) {
1523
0
    return true;
1524
0
  }
1525
1526
0
  if (ParseTemplateTemplateParam(state) && ParseTemplateArgs(state)) {
1527
0
    return true;
1528
0
  }
1529
0
  state->parse_state = copy;
1530
1531
  // Less greedy than <template-template-param> <template-args>.
1532
0
  if (ParseTemplateParam(state)) {
1533
0
    return true;
1534
0
  }
1535
1536
  // GNU vector extension Dv <number> _ <type>
1537
0
  if (ParseTwoCharToken(state, "Dv") && ParseNumber(state, nullptr) &&
1538
0
      ParseOneCharToken(state, '_') && ParseType(state)) {
1539
0
    return true;
1540
0
  }
1541
0
  state->parse_state = copy;
1542
1543
  // GNU vector extension Dv <expression> _ <type>
1544
0
  if (ParseTwoCharToken(state, "Dv") && ParseExpression(state) &&
1545
0
      ParseOneCharToken(state, '_') && ParseType(state)) {
1546
0
    return true;
1547
0
  }
1548
0
  state->parse_state = copy;
1549
1550
0
  if (ParseTwoCharToken(state, "Dk") && ParseTypeConstraint(state)) {
1551
0
    return true;
1552
0
  }
1553
0
  state->parse_state = copy;
1554
1555
  // For this notation see CXXNameMangler::mangleType in Clang's source code.
1556
  // The relevant logic and its comment "not clear how to mangle this!" date
1557
  // from 2011, so it may be with us awhile.
1558
0
  return ParseLongToken(state, "_SUBSTPACK_");
1559
0
}
1560
1561
// <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
1562
// <CV-qualifiers> ::= [r] [V] [K]
1563
//
1564
// We don't allow empty <CV-qualifiers> to avoid infinite loop in
1565
// ParseType().
1566
0
static bool ParseCVQualifiers(State *state) {
1567
0
  ComplexityGuard guard(state);
1568
0
  if (guard.IsTooComplex()) return false;
1569
0
  int num_cv_qualifiers = 0;
1570
0
  while (ParseExtendedQualifier(state)) ++num_cv_qualifiers;
1571
0
  num_cv_qualifiers += ParseOneCharToken(state, 'r');
1572
0
  num_cv_qualifiers += ParseOneCharToken(state, 'V');
1573
0
  num_cv_qualifiers += ParseOneCharToken(state, 'K');
1574
0
  return num_cv_qualifiers > 0;
1575
0
}
1576
1577
// <extended-qualifier> ::= U <source-name> [<template-args>]
1578
0
static bool ParseExtendedQualifier(State *state) {
1579
0
  ComplexityGuard guard(state);
1580
0
  if (guard.IsTooComplex()) return false;
1581
0
  ParseState copy = state->parse_state;
1582
1583
0
  if (!ParseOneCharToken(state, 'U')) return false;
1584
1585
0
  bool append = state->parse_state.append;
1586
0
  DisableAppend(state);
1587
0
  if (!ParseSourceName(state)) {
1588
0
    state->parse_state = copy;
1589
0
    return false;
1590
0
  }
1591
0
  Optional(ParseTemplateArgs(state));
1592
0
  RestoreAppend(state, append);
1593
0
  return true;
1594
0
}
1595
1596
// <builtin-type> ::= v, etc.  # single-character builtin types
1597
//                ::= <vendor-extended-type>
1598
//                ::= Dd, etc.  # two-character builtin types
1599
//                ::= DB (<number> | <expression>) _  # _BitInt(N)
1600
//                ::= DU (<number> | <expression>) _  # unsigned _BitInt(N)
1601
//                ::= DF <number> _  # _FloatN (N bits)
1602
//                ::= DF <number> x  # _FloatNx
1603
//                ::= DF16b  # std::bfloat16_t
1604
//
1605
// Not supported:
1606
//                ::= [DS] DA <fixed-point-size>
1607
//                ::= [DS] DR <fixed-point-size>
1608
// because real implementations of N1169 fixed-point are scant.
1609
0
static bool ParseBuiltinType(State *state) {
1610
0
  ComplexityGuard guard(state);
1611
0
  if (guard.IsTooComplex()) return false;
1612
0
  ParseState copy = state->parse_state;
1613
1614
  // DB (<number> | <expression>) _  # _BitInt(N)
1615
  // DU (<number> | <expression>) _  # unsigned _BitInt(N)
1616
0
  if (ParseTwoCharToken(state, "DB") ||
1617
0
      (ParseTwoCharToken(state, "DU") && MaybeAppend(state, "unsigned "))) {
1618
0
    bool append = state->parse_state.append;
1619
0
    DisableAppend(state);
1620
0
    int number = -1;
1621
0
    if (!ParseNumber(state, &number) && !ParseExpression(state)) {
1622
0
      state->parse_state = copy;
1623
0
      return false;
1624
0
    }
1625
0
    RestoreAppend(state, append);
1626
1627
0
    if (!ParseOneCharToken(state, '_')) {
1628
0
      state->parse_state = copy;
1629
0
      return false;
1630
0
    }
1631
1632
0
    MaybeAppend(state, "_BitInt(");
1633
0
    if (number >= 0) {
1634
0
      MaybeAppendDecimal(state, number);
1635
0
    } else {
1636
0
      MaybeAppend(state, "?");  // the best we can do for dependent sizes
1637
0
    }
1638
0
    MaybeAppend(state, ")");
1639
0
    return true;
1640
0
  }
1641
1642
  // DF <number> _  # _FloatN
1643
  // DF <number> x  # _FloatNx
1644
  // DF16b  # std::bfloat16_t
1645
0
  if (ParseTwoCharToken(state, "DF")) {
1646
0
    if (ParseThreeCharToken(state, "16b")) {
1647
0
      MaybeAppend(state, "std::bfloat16_t");
1648
0
      return true;
1649
0
    }
1650
0
    int number = 0;
1651
0
    if (!ParseNumber(state, &number)) {
1652
0
      state->parse_state = copy;
1653
0
      return false;
1654
0
    }
1655
0
    MaybeAppend(state, "_Float");
1656
0
    MaybeAppendDecimal(state, number);
1657
0
    if (ParseOneCharToken(state, 'x')) {
1658
0
      MaybeAppend(state, "x");
1659
0
      return true;
1660
0
    }
1661
0
    if (ParseOneCharToken(state, '_')) return true;
1662
0
    state->parse_state = copy;
1663
0
    return false;
1664
0
  }
1665
1666
0
  for (const AbbrevPair *p = kBuiltinTypeList; p->abbrev != nullptr; ++p) {
1667
    // Guaranteed only 1- or 2-character strings in kBuiltinTypeList.
1668
0
    if (p->abbrev[1] == '\0') {
1669
0
      if (ParseOneCharToken(state, p->abbrev[0])) {
1670
0
        MaybeAppend(state, p->real_name);
1671
0
        return true;  // ::= v, etc.  # single-character builtin types
1672
0
      }
1673
0
    } else if (p->abbrev[2] == '\0' && ParseTwoCharToken(state, p->abbrev)) {
1674
0
      MaybeAppend(state, p->real_name);
1675
0
      return true;  // ::= Dd, etc.  # two-character builtin types
1676
0
    }
1677
0
  }
1678
1679
0
  return ParseVendorExtendedType(state);
1680
0
}
1681
1682
// <vendor-extended-type> ::= u <source-name> [<template-args>]
1683
0
static bool ParseVendorExtendedType(State *state) {
1684
0
  ComplexityGuard guard(state);
1685
0
  if (guard.IsTooComplex()) return false;
1686
1687
0
  ParseState copy = state->parse_state;
1688
0
  if (ParseOneCharToken(state, 'u') && ParseSourceName(state) &&
1689
0
      Optional(ParseTemplateArgs(state))) {
1690
0
    return true;
1691
0
  }
1692
0
  state->parse_state = copy;
1693
0
  return false;
1694
0
}
1695
1696
//  <exception-spec> ::= Do                # non-throwing
1697
//                                           exception-specification (e.g.,
1698
//                                           noexcept, throw())
1699
//                   ::= DO <expression> E # computed (instantiation-dependent)
1700
//                                           noexcept
1701
//                   ::= Dw <type>+ E      # dynamic exception specification
1702
//                                           with instantiation-dependent types
1703
0
static bool ParseExceptionSpec(State *state) {
1704
0
  ComplexityGuard guard(state);
1705
0
  if (guard.IsTooComplex()) return false;
1706
1707
0
  if (ParseTwoCharToken(state, "Do")) return true;
1708
1709
0
  ParseState copy = state->parse_state;
1710
0
  if (ParseTwoCharToken(state, "DO") && ParseExpression(state) &&
1711
0
      ParseOneCharToken(state, 'E')) {
1712
0
    return true;
1713
0
  }
1714
0
  state->parse_state = copy;
1715
0
  if (ParseTwoCharToken(state, "Dw") && OneOrMore(ParseType, state) &&
1716
0
      ParseOneCharToken(state, 'E')) {
1717
0
    return true;
1718
0
  }
1719
0
  state->parse_state = copy;
1720
1721
0
  return false;
1722
0
}
1723
1724
// <function-type> ::=
1725
//     [exception-spec] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
1726
//
1727
// <ref-qualifier> ::= R | O
1728
0
static bool ParseFunctionType(State *state) {
1729
0
  ComplexityGuard guard(state);
1730
0
  if (guard.IsTooComplex()) return false;
1731
0
  ParseState copy = state->parse_state;
1732
0
  Optional(ParseExceptionSpec(state));
1733
0
  Optional(ParseTwoCharToken(state, "Dx"));
1734
0
  if (!ParseOneCharToken(state, 'F')) {
1735
0
    state->parse_state = copy;
1736
0
    return false;
1737
0
  }
1738
0
  Optional(ParseOneCharToken(state, 'Y'));
1739
0
  if (!ParseBareFunctionType(state)) {
1740
0
    state->parse_state = copy;
1741
0
    return false;
1742
0
  }
1743
0
  Optional(ParseCharClass(state, "RO"));
1744
0
  if (!ParseOneCharToken(state, 'E')) {
1745
0
    state->parse_state = copy;
1746
0
    return false;
1747
0
  }
1748
0
  return true;
1749
0
}
1750
1751
// <bare-function-type> ::= <overload-attribute>* <(signature) type>+
1752
//
1753
// The <overload-attribute>* prefix is nonstandard; see the comment on
1754
// ParseOverloadAttribute.
1755
0
static bool ParseBareFunctionType(State *state) {
1756
0
  ComplexityGuard guard(state);
1757
0
  if (guard.IsTooComplex()) return false;
1758
0
  ParseState copy = state->parse_state;
1759
0
  DisableAppend(state);
1760
0
  if (ZeroOrMore(ParseOverloadAttribute, state) &&
1761
0
      OneOrMore(ParseType, state)) {
1762
0
    RestoreAppend(state, copy.append);
1763
0
    MaybeAppend(state, "()");
1764
0
    return true;
1765
0
  }
1766
0
  state->parse_state = copy;
1767
0
  return false;
1768
0
}
1769
1770
// <overload-attribute> ::= Ua <name>
1771
//
1772
// The nonstandard <overload-attribute> production is sufficient to accept the
1773
// current implementation of __attribute__((enable_if(condition, "message")))
1774
// and future attributes of a similar shape.  See
1775
// https://clang.llvm.org/docs/AttributeReference.html#enable-if and the
1776
// definition of CXXNameMangler::mangleFunctionEncodingBareType in Clang's
1777
// source code.
1778
0
static bool ParseOverloadAttribute(State *state) {
1779
0
  ComplexityGuard guard(state);
1780
0
  if (guard.IsTooComplex()) return false;
1781
0
  ParseState copy = state->parse_state;
1782
0
  if (ParseTwoCharToken(state, "Ua") && ParseName(state)) {
1783
0
    return true;
1784
0
  }
1785
0
  state->parse_state = copy;
1786
0
  return false;
1787
0
}
1788
1789
// <class-enum-type> ::= <name>
1790
//                   ::= Ts <name>  # struct Name or class Name
1791
//                   ::= Tu <name>  # union Name
1792
//                   ::= Te <name>  # enum Name
1793
//
1794
// See http://shortn/_W3YrltiEd0.
1795
0
static bool ParseClassEnumType(State *state) {
1796
0
  ComplexityGuard guard(state);
1797
0
  if (guard.IsTooComplex()) return false;
1798
0
  ParseState copy = state->parse_state;
1799
0
  if (Optional(ParseTwoCharToken(state, "Ts") ||
1800
0
               ParseTwoCharToken(state, "Tu") ||
1801
0
               ParseTwoCharToken(state, "Te")) &&
1802
0
      ParseName(state)) {
1803
0
    return true;
1804
0
  }
1805
0
  state->parse_state = copy;
1806
0
  return false;
1807
0
}
1808
1809
// <array-type> ::= A <(positive dimension) number> _ <(element) type>
1810
//              ::= A [<(dimension) expression>] _ <(element) type>
1811
0
static bool ParseArrayType(State *state) {
1812
0
  ComplexityGuard guard(state);
1813
0
  if (guard.IsTooComplex()) return false;
1814
0
  ParseState copy = state->parse_state;
1815
0
  if (ParseOneCharToken(state, 'A') && ParseNumber(state, nullptr) &&
1816
0
      ParseOneCharToken(state, '_') && ParseType(state)) {
1817
0
    return true;
1818
0
  }
1819
0
  state->parse_state = copy;
1820
1821
0
  if (ParseOneCharToken(state, 'A') && Optional(ParseExpression(state)) &&
1822
0
      ParseOneCharToken(state, '_') && ParseType(state)) {
1823
0
    return true;
1824
0
  }
1825
0
  state->parse_state = copy;
1826
0
  return false;
1827
0
}
1828
1829
// <pointer-to-member-type> ::= M <(class) type> <(member) type>
1830
0
static bool ParsePointerToMemberType(State *state) {
1831
0
  ComplexityGuard guard(state);
1832
0
  if (guard.IsTooComplex()) return false;
1833
0
  ParseState copy = state->parse_state;
1834
0
  if (ParseOneCharToken(state, 'M') && ParseType(state) && ParseType(state)) {
1835
0
    return true;
1836
0
  }
1837
0
  state->parse_state = copy;
1838
0
  return false;
1839
0
}
1840
1841
// <template-param> ::= T_
1842
//                  ::= T <parameter-2 non-negative number> _
1843
//                  ::= TL <level-1> __
1844
//                  ::= TL <level-1> _ <parameter-2 non-negative number> _
1845
0
static bool ParseTemplateParam(State *state) {
1846
0
  ComplexityGuard guard(state);
1847
0
  if (guard.IsTooComplex()) return false;
1848
0
  if (ParseTwoCharToken(state, "T_")) {
1849
0
    MaybeAppend(state, "?");  // We don't support template substitutions.
1850
0
    return true;              // ::= T_
1851
0
  }
1852
1853
0
  ParseState copy = state->parse_state;
1854
0
  if (ParseOneCharToken(state, 'T') && ParseNumber(state, nullptr) &&
1855
0
      ParseOneCharToken(state, '_')) {
1856
0
    MaybeAppend(state, "?");  // We don't support template substitutions.
1857
0
    return true;              // ::= T <parameter-2 non-negative number> _
1858
0
  }
1859
0
  state->parse_state = copy;
1860
1861
0
  if (ParseTwoCharToken(state, "TL") && ParseNumber(state, nullptr)) {
1862
0
    if (ParseTwoCharToken(state, "__")) {
1863
0
      MaybeAppend(state, "?");  // We don't support template substitutions.
1864
0
      return true;              // ::= TL <level-1> __
1865
0
    }
1866
1867
0
    if (ParseOneCharToken(state, '_') && ParseNumber(state, nullptr) &&
1868
0
        ParseOneCharToken(state, '_')) {
1869
0
      MaybeAppend(state, "?");  // We don't support template substitutions.
1870
0
      return true;  // ::= TL <level-1> _ <parameter-2 non-negative number> _
1871
0
    }
1872
0
  }
1873
0
  state->parse_state = copy;
1874
0
  return false;
1875
0
}
1876
1877
// <template-param-decl>
1878
//   ::= Ty                                  # template type parameter
1879
//   ::= Tk <concept name> [<template-args>] # constrained type parameter
1880
//   ::= Tn <type>                           # template non-type parameter
1881
//   ::= Tt <template-param-decl>* E         # template template parameter
1882
//   ::= Tp <template-param-decl>            # template parameter pack
1883
//
1884
// NOTE: <concept name> is just a <name>: http://shortn/_MqJVyr0fc1
1885
// TODO(b/324066279): Implement optional suffix for `Tt`:
1886
// [Q <requires-clause expr>]
1887
0
static bool ParseTemplateParamDecl(State *state) {
1888
0
  ComplexityGuard guard(state);
1889
0
  if (guard.IsTooComplex()) return false;
1890
0
  ParseState copy = state->parse_state;
1891
1892
0
  if (ParseTwoCharToken(state, "Ty")) {
1893
0
    return true;
1894
0
  }
1895
0
  state->parse_state = copy;
1896
1897
0
  if (ParseTwoCharToken(state, "Tk") && ParseName(state) &&
1898
0
      Optional(ParseTemplateArgs(state))) {
1899
0
    return true;
1900
0
  }
1901
0
  state->parse_state = copy;
1902
1903
0
  if (ParseTwoCharToken(state, "Tn") && ParseType(state)) {
1904
0
    return true;
1905
0
  }
1906
0
  state->parse_state = copy;
1907
1908
0
  if (ParseTwoCharToken(state, "Tt") &&
1909
0
      ZeroOrMore(ParseTemplateParamDecl, state) &&
1910
0
      ParseOneCharToken(state, 'E')) {
1911
0
    return true;
1912
0
  }
1913
0
  state->parse_state = copy;
1914
1915
0
  if (ParseTwoCharToken(state, "Tp") && ParseTemplateParamDecl(state)) {
1916
0
    return true;
1917
0
  }
1918
0
  state->parse_state = copy;
1919
1920
0
  return false;
1921
0
}
1922
1923
// <template-template-param> ::= <template-param>
1924
//                           ::= <substitution>
1925
0
static bool ParseTemplateTemplateParam(State *state) {
1926
0
  ComplexityGuard guard(state);
1927
0
  if (guard.IsTooComplex()) return false;
1928
0
  return (ParseTemplateParam(state) ||
1929
          // "std" on its own isn't a template.
1930
0
          ParseSubstitution(state, /*accept_std=*/false));
1931
0
}
1932
1933
// <template-args> ::= I <template-arg>+ [Q <requires-clause expr>] E
1934
0
static bool ParseTemplateArgs(State *state) {
1935
0
  ComplexityGuard guard(state);
1936
0
  if (guard.IsTooComplex()) return false;
1937
0
  ParseState copy = state->parse_state;
1938
0
  DisableAppend(state);
1939
0
  if (ParseOneCharToken(state, 'I') && OneOrMore(ParseTemplateArg, state) &&
1940
0
      Optional(ParseQRequiresClauseExpr(state)) &&
1941
0
      ParseOneCharToken(state, 'E')) {
1942
0
    RestoreAppend(state, copy.append);
1943
0
    MaybeAppend(state, "<>");
1944
0
    return true;
1945
0
  }
1946
0
  state->parse_state = copy;
1947
0
  return false;
1948
0
}
1949
1950
// <template-arg>  ::= <template-param-decl> <template-arg>
1951
//                 ::= <type>
1952
//                 ::= <expr-primary>
1953
//                 ::= J <template-arg>* E        # argument pack
1954
//                 ::= X <expression> E
1955
0
static bool ParseTemplateArg(State *state) {
1956
0
  ComplexityGuard guard(state);
1957
0
  if (guard.IsTooComplex()) return false;
1958
0
  ParseState copy = state->parse_state;
1959
0
  if (ParseOneCharToken(state, 'J') && ZeroOrMore(ParseTemplateArg, state) &&
1960
0
      ParseOneCharToken(state, 'E')) {
1961
0
    return true;
1962
0
  }
1963
0
  state->parse_state = copy;
1964
1965
  // There can be significant overlap between the following leading to
1966
  // exponential backtracking:
1967
  //
1968
  //   <expr-primary> ::= L <type> <expr-cast-value> E
1969
  //                 e.g. L 2xxIvE 1                 E
1970
  //   <type>         ==> <local-source-name> <template-args>
1971
  //                 e.g. L 2xx               IvE
1972
  //
1973
  // This means parsing an entire <type> twice, and <type> can contain
1974
  // <template-arg>, so this can generate exponential backtracking.  There is
1975
  // only overlap when the remaining input starts with "L <source-name>", so
1976
  // parse all cases that can start this way jointly to share the common prefix.
1977
  //
1978
  // We have:
1979
  //
1980
  //   <template-arg> ::= <type>
1981
  //                  ::= <expr-primary>
1982
  //
1983
  // First, drop all the productions of <type> that must start with something
1984
  // other than 'L'.  All that's left is <class-enum-type>; inline it.
1985
  //
1986
  //   <type> ::= <nested-name> # starts with 'N'
1987
  //          ::= <unscoped-name>
1988
  //          ::= <unscoped-template-name> <template-args>
1989
  //          ::= <local-name> # starts with 'Z'
1990
  //
1991
  // Drop and inline again:
1992
  //
1993
  //   <type> ::= <unscoped-name>
1994
  //          ::= <unscoped-name> <template-args>
1995
  //          ::= <substitution> <template-args> # starts with 'S'
1996
  //
1997
  // Merge the first two, inline <unscoped-name>, drop last:
1998
  //
1999
  //   <type> ::= <unqualified-name> [<template-args>]
2000
  //          ::= St <unqualified-name> [<template-args>] # starts with 'S'
2001
  //
2002
  // Drop and inline:
2003
  //
2004
  //   <type> ::= <operator-name> [<template-args>] # starts with lowercase
2005
  //          ::= <ctor-dtor-name> [<template-args>] # starts with 'C' or 'D'
2006
  //          ::= <source-name> [<template-args>] # starts with digit
2007
  //          ::= <local-source-name> [<template-args>]
2008
  //          ::= <unnamed-type-name> [<template-args>] # starts with 'U'
2009
  //
2010
  // One more time:
2011
  //
2012
  //   <type> ::= L <source-name> [<template-args>]
2013
  //
2014
  // Likewise with <expr-primary>:
2015
  //
2016
  //   <expr-primary> ::= L <type> <expr-cast-value> E
2017
  //                  ::= LZ <encoding> E # cannot overlap; drop
2018
  //                  ::= L <mangled_name> E # cannot overlap; drop
2019
  //
2020
  // By similar reasoning as shown above, the only <type>s starting with
2021
  // <source-name> are "<source-name> [<template-args>]".  Inline this.
2022
  //
2023
  //   <expr-primary> ::= L <source-name> [<template-args>] <expr-cast-value> E
2024
  //
2025
  // Now inline both of these into <template-arg>:
2026
  //
2027
  //   <template-arg> ::= L <source-name> [<template-args>]
2028
  //                  ::= L <source-name> [<template-args>] <expr-cast-value> E
2029
  //
2030
  // Merge them and we're done:
2031
  //   <template-arg>
2032
  //     ::= L <source-name> [<template-args>] [<expr-cast-value> E]
2033
0
  if (ParseLocalSourceName(state) && Optional(ParseTemplateArgs(state))) {
2034
0
    copy = state->parse_state;
2035
0
    if (ParseExprCastValueAndTrailingE(state)) {
2036
0
      return true;
2037
0
    }
2038
0
    state->parse_state = copy;
2039
0
    return true;
2040
0
  }
2041
2042
  // Now that the overlapping cases can't reach this code, we can safely call
2043
  // both of these.
2044
0
  if (ParseType(state) || ParseExprPrimary(state)) {
2045
0
    return true;
2046
0
  }
2047
0
  state->parse_state = copy;
2048
2049
0
  if (ParseOneCharToken(state, 'X') && ParseExpression(state) &&
2050
0
      ParseOneCharToken(state, 'E')) {
2051
0
    return true;
2052
0
  }
2053
0
  state->parse_state = copy;
2054
2055
0
  if (ParseTemplateParamDecl(state) && ParseTemplateArg(state)) {
2056
0
    return true;
2057
0
  }
2058
0
  state->parse_state = copy;
2059
2060
0
  return false;
2061
0
}
2062
2063
// <unresolved-type> ::= <template-param> [<template-args>]
2064
//                   ::= <decltype>
2065
//                   ::= <substitution>
2066
0
static inline bool ParseUnresolvedType(State *state) {
2067
  // No ComplexityGuard because we don't copy the state in this stack frame.
2068
0
  return (ParseTemplateParam(state) && Optional(ParseTemplateArgs(state))) ||
2069
0
         ParseDecltype(state) || ParseSubstitution(state, /*accept_std=*/false);
2070
0
}
2071
2072
// <simple-id> ::= <source-name> [<template-args>]
2073
0
static inline bool ParseSimpleId(State *state) {
2074
  // No ComplexityGuard because we don't copy the state in this stack frame.
2075
2076
  // Note: <simple-id> cannot be followed by a parameter pack; see comment in
2077
  // ParseUnresolvedType.
2078
0
  return ParseSourceName(state) && Optional(ParseTemplateArgs(state));
2079
0
}
2080
2081
// <base-unresolved-name> ::= <source-name> [<template-args>]
2082
//                        ::= on <operator-name> [<template-args>]
2083
//                        ::= dn <destructor-name>
2084
0
static bool ParseBaseUnresolvedName(State *state) {
2085
0
  ComplexityGuard guard(state);
2086
0
  if (guard.IsTooComplex()) return false;
2087
2088
0
  if (ParseSimpleId(state)) {
2089
0
    return true;
2090
0
  }
2091
2092
0
  ParseState copy = state->parse_state;
2093
0
  if (ParseTwoCharToken(state, "on") && ParseOperatorName(state, nullptr) &&
2094
0
      Optional(ParseTemplateArgs(state))) {
2095
0
    return true;
2096
0
  }
2097
0
  state->parse_state = copy;
2098
2099
0
  if (ParseTwoCharToken(state, "dn") &&
2100
0
      (ParseUnresolvedType(state) || ParseSimpleId(state))) {
2101
0
    return true;
2102
0
  }
2103
0
  state->parse_state = copy;
2104
2105
0
  return false;
2106
0
}
2107
2108
// <unresolved-name> ::= [gs] <base-unresolved-name>
2109
//                   ::= sr <unresolved-type> <base-unresolved-name>
2110
//                   ::= srN <unresolved-type> <unresolved-qualifier-level>+ E
2111
//                         <base-unresolved-name>
2112
//                   ::= [gs] sr <unresolved-qualifier-level>+ E
2113
//                         <base-unresolved-name>
2114
//                   ::= sr St <simple-id> <simple-id>  # nonstandard
2115
//
2116
// The last case is not part of the official grammar but has been observed in
2117
// real-world examples that the GNU demangler (but not the LLVM demangler) is
2118
// able to decode; see demangle_test.cc for one such symbol name.  The shape
2119
// sr St <simple-id> <simple-id> was inferred by closed-box testing of the GNU
2120
// demangler.
2121
0
static bool ParseUnresolvedName(State *state) {
2122
0
  ComplexityGuard guard(state);
2123
0
  if (guard.IsTooComplex()) return false;
2124
2125
0
  ParseState copy = state->parse_state;
2126
0
  if (Optional(ParseTwoCharToken(state, "gs")) &&
2127
0
      ParseBaseUnresolvedName(state)) {
2128
0
    return true;
2129
0
  }
2130
0
  state->parse_state = copy;
2131
2132
0
  if (ParseTwoCharToken(state, "sr") && ParseUnresolvedType(state) &&
2133
0
      ParseBaseUnresolvedName(state)) {
2134
0
    return true;
2135
0
  }
2136
0
  state->parse_state = copy;
2137
2138
0
  if (ParseTwoCharToken(state, "sr") && ParseOneCharToken(state, 'N') &&
2139
0
      ParseUnresolvedType(state) &&
2140
0
      OneOrMore(ParseUnresolvedQualifierLevel, state) &&
2141
0
      ParseOneCharToken(state, 'E') && ParseBaseUnresolvedName(state)) {
2142
0
    return true;
2143
0
  }
2144
0
  state->parse_state = copy;
2145
2146
0
  if (Optional(ParseTwoCharToken(state, "gs")) &&
2147
0
      ParseTwoCharToken(state, "sr") &&
2148
0
      OneOrMore(ParseUnresolvedQualifierLevel, state) &&
2149
0
      ParseOneCharToken(state, 'E') && ParseBaseUnresolvedName(state)) {
2150
0
    return true;
2151
0
  }
2152
0
  state->parse_state = copy;
2153
2154
0
  if (ParseTwoCharToken(state, "sr") && ParseTwoCharToken(state, "St") &&
2155
0
      ParseSimpleId(state) && ParseSimpleId(state)) {
2156
0
    return true;
2157
0
  }
2158
0
  state->parse_state = copy;
2159
2160
0
  return false;
2161
0
}
2162
2163
// <unresolved-qualifier-level> ::= <simple-id>
2164
//                              ::= <substitution> <template-args>
2165
//
2166
// The production <substitution> <template-args> is nonstandard but is observed
2167
// in practice.  An upstream discussion on the best shape of <unresolved-name>
2168
// has not converged:
2169
//
2170
// https://github.com/itanium-cxx-abi/cxx-abi/issues/38
2171
0
static bool ParseUnresolvedQualifierLevel(State *state) {
2172
0
  ComplexityGuard guard(state);
2173
0
  if (guard.IsTooComplex()) return false;
2174
2175
0
  if (ParseSimpleId(state)) return true;
2176
2177
0
  ParseState copy = state->parse_state;
2178
0
  if (ParseSubstitution(state, /*accept_std=*/false) &&
2179
0
      ParseTemplateArgs(state)) {
2180
0
    return true;
2181
0
  }
2182
0
  state->parse_state = copy;
2183
0
  return false;
2184
0
}
2185
2186
// <union-selector> ::= _ [<number>]
2187
//
2188
// https://github.com/itanium-cxx-abi/cxx-abi/issues/47
2189
0
static bool ParseUnionSelector(State *state) {
2190
0
  return ParseOneCharToken(state, '_') && Optional(ParseNumber(state, nullptr));
2191
0
}
2192
2193
// <function-param> ::= fp <(top-level) CV-qualifiers> _
2194
//                  ::= fp <(top-level) CV-qualifiers> <number> _
2195
//                  ::= fL <number> p <(top-level) CV-qualifiers> _
2196
//                  ::= fL <number> p <(top-level) CV-qualifiers> <number> _
2197
//                  ::= fpT  # this
2198
0
static bool ParseFunctionParam(State *state) {
2199
0
  ComplexityGuard guard(state);
2200
0
  if (guard.IsTooComplex()) return false;
2201
2202
0
  ParseState copy = state->parse_state;
2203
2204
  // Function-param expression (level 0).
2205
0
  if (ParseTwoCharToken(state, "fp") && Optional(ParseCVQualifiers(state)) &&
2206
0
      Optional(ParseNumber(state, nullptr)) && ParseOneCharToken(state, '_')) {
2207
0
    return true;
2208
0
  }
2209
0
  state->parse_state = copy;
2210
2211
  // Function-param expression (level 1+).
2212
0
  if (ParseTwoCharToken(state, "fL") && Optional(ParseNumber(state, nullptr)) &&
2213
0
      ParseOneCharToken(state, 'p') && Optional(ParseCVQualifiers(state)) &&
2214
0
      Optional(ParseNumber(state, nullptr)) && ParseOneCharToken(state, '_')) {
2215
0
    return true;
2216
0
  }
2217
0
  state->parse_state = copy;
2218
2219
0
  return ParseThreeCharToken(state, "fpT");
2220
0
}
2221
2222
// <braced-expression> ::= <expression>
2223
//                     ::= di <field source-name> <braced-expression>
2224
//                     ::= dx <index expression> <braced-expression>
2225
//                     ::= dX <expression> <expression> <braced-expression>
2226
0
static bool ParseBracedExpression(State *state) {
2227
0
  ComplexityGuard guard(state);
2228
0
  if (guard.IsTooComplex()) return false;
2229
2230
0
  ParseState copy = state->parse_state;
2231
2232
0
  if (ParseTwoCharToken(state, "di") && ParseSourceName(state) &&
2233
0
      ParseBracedExpression(state)) {
2234
0
    return true;
2235
0
  }
2236
0
  state->parse_state = copy;
2237
2238
0
  if (ParseTwoCharToken(state, "dx") && ParseExpression(state) &&
2239
0
      ParseBracedExpression(state)) {
2240
0
    return true;
2241
0
  }
2242
0
  state->parse_state = copy;
2243
2244
0
  if (ParseTwoCharToken(state, "dX") &&
2245
0
      ParseExpression(state) && ParseExpression(state) &&
2246
0
      ParseBracedExpression(state)) {
2247
0
    return true;
2248
0
  }
2249
0
  state->parse_state = copy;
2250
2251
0
  return ParseExpression(state);
2252
0
}
2253
2254
// <expression> ::= <1-ary operator-name> <expression>
2255
//              ::= <2-ary operator-name> <expression> <expression>
2256
//              ::= <3-ary operator-name> <expression> <expression> <expression>
2257
//              ::= pp_ <expression>  # ++e; pp <expression> is e++
2258
//              ::= mm_ <expression>  # --e; mm <expression> is e--
2259
//              ::= cl <expression>+ E
2260
//              ::= cp <simple-id> <expression>* E # Clang-specific.
2261
//              ::= so <type> <expression> [<number>] <union-selector>* [p] E
2262
//              ::= cv <type> <expression>      # type (expression)
2263
//              ::= cv <type> _ <expression>* E # type (expr-list)
2264
//              ::= tl <type> <braced-expression>* E
2265
//              ::= il <braced-expression>* E
2266
//              ::= [gs] nw <expression>* _ <type> E
2267
//              ::= [gs] nw <expression>* _ <type> <initializer>
2268
//              ::= [gs] na <expression>* _ <type> E
2269
//              ::= [gs] na <expression>* _ <type> <initializer>
2270
//              ::= [gs] dl <expression>
2271
//              ::= [gs] da <expression>
2272
//              ::= dc <type> <expression>
2273
//              ::= sc <type> <expression>
2274
//              ::= cc <type> <expression>
2275
//              ::= rc <type> <expression>
2276
//              ::= ti <type>
2277
//              ::= te <expression>
2278
//              ::= st <type>
2279
//              ::= at <type>
2280
//              ::= az <expression>
2281
//              ::= nx <expression>
2282
//              ::= <template-param>
2283
//              ::= <function-param>
2284
//              ::= sZ <template-param>
2285
//              ::= sZ <function-param>
2286
//              ::= sP <template-arg>* E
2287
//              ::= <expr-primary>
2288
//              ::= dt <expression> <unresolved-name> # expr.name
2289
//              ::= pt <expression> <unresolved-name> # expr->name
2290
//              ::= sp <expression>         # argument pack expansion
2291
//              ::= fl <binary operator-name> <expression>
2292
//              ::= fr <binary operator-name> <expression>
2293
//              ::= fL <binary operator-name> <expression> <expression>
2294
//              ::= fR <binary operator-name> <expression> <expression>
2295
//              ::= tw <expression>
2296
//              ::= tr
2297
//              ::= sr <type> <unqualified-name> <template-args>
2298
//              ::= sr <type> <unqualified-name>
2299
//              ::= u <source-name> <template-arg>* E  # vendor extension
2300
//              ::= rq <requirement>+ E
2301
//              ::= rQ <bare-function-type> _ <requirement>+ E
2302
0
static bool ParseExpression(State *state) {
2303
0
  ComplexityGuard guard(state);
2304
0
  if (guard.IsTooComplex()) return false;
2305
0
  if (ParseTemplateParam(state) || ParseExprPrimary(state)) {
2306
0
    return true;
2307
0
  }
2308
2309
0
  ParseState copy = state->parse_state;
2310
2311
  // Object/function call expression.
2312
0
  if (ParseTwoCharToken(state, "cl") && OneOrMore(ParseExpression, state) &&
2313
0
      ParseOneCharToken(state, 'E')) {
2314
0
    return true;
2315
0
  }
2316
0
  state->parse_state = copy;
2317
2318
  // Preincrement and predecrement.  Postincrement and postdecrement are handled
2319
  // by the operator-name logic later on.
2320
0
  if ((ParseThreeCharToken(state, "pp_") ||
2321
0
       ParseThreeCharToken(state, "mm_")) &&
2322
0
      ParseExpression(state)) {
2323
0
    return true;
2324
0
  }
2325
0
  state->parse_state = copy;
2326
2327
  // Clang-specific "cp <simple-id> <expression>* E"
2328
  //   https://clang.llvm.org/doxygen/ItaniumMangle_8cpp_source.html#l04338
2329
0
  if (ParseTwoCharToken(state, "cp") && ParseSimpleId(state) &&
2330
0
      ZeroOrMore(ParseExpression, state) && ParseOneCharToken(state, 'E')) {
2331
0
    return true;
2332
0
  }
2333
0
  state->parse_state = copy;
2334
2335
  // <expression> ::= so <type> <expression> [<number>] <union-selector>* [p] E
2336
  //
2337
  // https://github.com/itanium-cxx-abi/cxx-abi/issues/47
2338
0
  if (ParseTwoCharToken(state, "so") && ParseType(state) &&
2339
0
      ParseExpression(state) && Optional(ParseNumber(state, nullptr)) &&
2340
0
      ZeroOrMore(ParseUnionSelector, state) &&
2341
0
      Optional(ParseOneCharToken(state, 'p')) &&
2342
0
      ParseOneCharToken(state, 'E')) {
2343
0
    return true;
2344
0
  }
2345
0
  state->parse_state = copy;
2346
2347
  // <expression> ::= <function-param>
2348
0
  if (ParseFunctionParam(state)) return true;
2349
0
  state->parse_state = copy;
2350
2351
  // <expression> ::= tl <type> <braced-expression>* E
2352
0
  if (ParseTwoCharToken(state, "tl") && ParseType(state) &&
2353
0
      ZeroOrMore(ParseBracedExpression, state) &&
2354
0
      ParseOneCharToken(state, 'E')) {
2355
0
    return true;
2356
0
  }
2357
0
  state->parse_state = copy;
2358
2359
  // <expression> ::= il <braced-expression>* E
2360
0
  if (ParseTwoCharToken(state, "il") &&
2361
0
      ZeroOrMore(ParseBracedExpression, state) &&
2362
0
      ParseOneCharToken(state, 'E')) {
2363
0
    return true;
2364
0
  }
2365
0
  state->parse_state = copy;
2366
2367
  // <expression> ::= [gs] nw <expression>* _ <type> E
2368
  //              ::= [gs] nw <expression>* _ <type> <initializer>
2369
  //              ::= [gs] na <expression>* _ <type> E
2370
  //              ::= [gs] na <expression>* _ <type> <initializer>
2371
0
  if (Optional(ParseTwoCharToken(state, "gs")) &&
2372
0
      (ParseTwoCharToken(state, "nw") || ParseTwoCharToken(state, "na")) &&
2373
0
      ZeroOrMore(ParseExpression, state) && ParseOneCharToken(state, '_') &&
2374
0
      ParseType(state) &&
2375
0
      (ParseOneCharToken(state, 'E') || ParseInitializer(state))) {
2376
0
    return true;
2377
0
  }
2378
0
  state->parse_state = copy;
2379
2380
  // <expression> ::= [gs] dl <expression>
2381
  //              ::= [gs] da <expression>
2382
0
  if (Optional(ParseTwoCharToken(state, "gs")) &&
2383
0
      (ParseTwoCharToken(state, "dl") || ParseTwoCharToken(state, "da")) &&
2384
0
      ParseExpression(state)) {
2385
0
    return true;
2386
0
  }
2387
0
  state->parse_state = copy;
2388
2389
  // dynamic_cast, static_cast, const_cast, reinterpret_cast.
2390
  //
2391
  // <expression> ::= (dc | sc | cc | rc) <type> <expression>
2392
0
  if (ParseCharClass(state, "dscr") && ParseOneCharToken(state, 'c') &&
2393
0
      ParseType(state) && ParseExpression(state)) {
2394
0
    return true;
2395
0
  }
2396
0
  state->parse_state = copy;
2397
2398
  // Parse the conversion expressions jointly to avoid re-parsing the <type> in
2399
  // their common prefix.  Parsed as:
2400
  // <expression> ::= cv <type> <conversion-args>
2401
  // <conversion-args> ::= _ <expression>* E
2402
  //                   ::= <expression>
2403
  //
2404
  // Also don't try ParseOperatorName after seeing "cv", since ParseOperatorName
2405
  // also needs to accept "cv <type>" in other contexts.
2406
0
  if (ParseTwoCharToken(state, "cv")) {
2407
0
    if (ParseType(state)) {
2408
0
      ParseState copy2 = state->parse_state;
2409
0
      if (ParseOneCharToken(state, '_') && ZeroOrMore(ParseExpression, state) &&
2410
0
          ParseOneCharToken(state, 'E')) {
2411
0
        return true;
2412
0
      }
2413
0
      state->parse_state = copy2;
2414
0
      if (ParseExpression(state)) {
2415
0
        return true;
2416
0
      }
2417
0
    }
2418
0
  } else {
2419
    // Parse unary, binary, and ternary operator expressions jointly, taking
2420
    // care not to re-parse subexpressions repeatedly. Parse like:
2421
    //   <expression> ::= <operator-name> <expression>
2422
    //                    [<one-to-two-expressions>]
2423
    //   <one-to-two-expressions> ::= <expression> [<expression>]
2424
0
    int arity = -1;
2425
0
    if (ParseOperatorName(state, &arity) &&
2426
0
        arity > 0 &&  // 0 arity => disabled.
2427
0
        (arity < 3 || ParseExpression(state)) &&
2428
0
        (arity < 2 || ParseExpression(state)) &&
2429
0
        (arity < 1 || ParseExpression(state))) {
2430
0
      return true;
2431
0
    }
2432
0
  }
2433
0
  state->parse_state = copy;
2434
2435
  // typeid(type)
2436
0
  if (ParseTwoCharToken(state, "ti") && ParseType(state)) {
2437
0
    return true;
2438
0
  }
2439
0
  state->parse_state = copy;
2440
2441
  // typeid(expression)
2442
0
  if (ParseTwoCharToken(state, "te") && ParseExpression(state)) {
2443
0
    return true;
2444
0
  }
2445
0
  state->parse_state = copy;
2446
2447
  // sizeof type
2448
0
  if (ParseTwoCharToken(state, "st") && ParseType(state)) {
2449
0
    return true;
2450
0
  }
2451
0
  state->parse_state = copy;
2452
2453
  // alignof(type)
2454
0
  if (ParseTwoCharToken(state, "at") && ParseType(state)) {
2455
0
    return true;
2456
0
  }
2457
0
  state->parse_state = copy;
2458
2459
  // alignof(expression), a GNU extension
2460
0
  if (ParseTwoCharToken(state, "az") && ParseExpression(state)) {
2461
0
    return true;
2462
0
  }
2463
0
  state->parse_state = copy;
2464
2465
  // noexcept(expression) appearing as an expression in a dependent signature
2466
0
  if (ParseTwoCharToken(state, "nx") && ParseExpression(state)) {
2467
0
    return true;
2468
0
  }
2469
0
  state->parse_state = copy;
2470
2471
  // sizeof...(pack)
2472
  //
2473
  // <expression> ::= sZ <template-param>
2474
  //              ::= sZ <function-param>
2475
0
  if (ParseTwoCharToken(state, "sZ") &&
2476
0
      (ParseFunctionParam(state) || ParseTemplateParam(state))) {
2477
0
    return true;
2478
0
  }
2479
0
  state->parse_state = copy;
2480
2481
  // sizeof...(pack) captured from an alias template
2482
  //
2483
  // <expression> ::= sP <template-arg>* E
2484
0
  if (ParseTwoCharToken(state, "sP") && ZeroOrMore(ParseTemplateArg, state) &&
2485
0
      ParseOneCharToken(state, 'E')) {
2486
0
    return true;
2487
0
  }
2488
0
  state->parse_state = copy;
2489
2490
  // Unary folds (... op pack) and (pack op ...).
2491
  //
2492
  // <expression> ::= fl <binary operator-name> <expression>
2493
  //              ::= fr <binary operator-name> <expression>
2494
0
  if ((ParseTwoCharToken(state, "fl") || ParseTwoCharToken(state, "fr")) &&
2495
0
      ParseOperatorName(state, nullptr) && ParseExpression(state)) {
2496
0
    return true;
2497
0
  }
2498
0
  state->parse_state = copy;
2499
2500
  // Binary folds (init op ... op pack) and (pack op ... op init).
2501
  //
2502
  // <expression> ::= fL <binary operator-name> <expression> <expression>
2503
  //              ::= fR <binary operator-name> <expression> <expression>
2504
0
  if ((ParseTwoCharToken(state, "fL") || ParseTwoCharToken(state, "fR")) &&
2505
0
      ParseOperatorName(state, nullptr) && ParseExpression(state) &&
2506
0
      ParseExpression(state)) {
2507
0
    return true;
2508
0
  }
2509
0
  state->parse_state = copy;
2510
2511
  // tw <expression>: throw e
2512
0
  if (ParseTwoCharToken(state, "tw") && ParseExpression(state)) {
2513
0
    return true;
2514
0
  }
2515
0
  state->parse_state = copy;
2516
2517
  // tr: throw (rethrows an exception from the handler that caught it)
2518
0
  if (ParseTwoCharToken(state, "tr")) return true;
2519
2520
  // Object and pointer member access expressions.
2521
  //
2522
  // <expression> ::= (dt | pt) <expression> <unresolved-name>
2523
0
  if ((ParseTwoCharToken(state, "dt") || ParseTwoCharToken(state, "pt")) &&
2524
0
      ParseExpression(state) && ParseUnresolvedName(state)) {
2525
0
    return true;
2526
0
  }
2527
0
  state->parse_state = copy;
2528
2529
  // Pointer-to-member access expressions.  This parses the same as a binary
2530
  // operator, but it's implemented separately because "ds" shouldn't be
2531
  // accepted in other contexts that parse an operator name.
2532
0
  if (ParseTwoCharToken(state, "ds") && ParseExpression(state) &&
2533
0
      ParseExpression(state)) {
2534
0
    return true;
2535
0
  }
2536
0
  state->parse_state = copy;
2537
2538
  // Parameter pack expansion
2539
0
  if (ParseTwoCharToken(state, "sp") && ParseExpression(state)) {
2540
0
    return true;
2541
0
  }
2542
0
  state->parse_state = copy;
2543
2544
  // Vendor extended expressions
2545
0
  if (ParseOneCharToken(state, 'u') && ParseSourceName(state) &&
2546
0
      ZeroOrMore(ParseTemplateArg, state) && ParseOneCharToken(state, 'E')) {
2547
0
    return true;
2548
0
  }
2549
0
  state->parse_state = copy;
2550
2551
  // <expression> ::= rq <requirement>+ E
2552
  //
2553
  // https://github.com/itanium-cxx-abi/cxx-abi/issues/24
2554
0
  if (ParseTwoCharToken(state, "rq") && OneOrMore(ParseRequirement, state) &&
2555
0
      ParseOneCharToken(state, 'E')) {
2556
0
    return true;
2557
0
  }
2558
0
  state->parse_state = copy;
2559
2560
  // <expression> ::= rQ <bare-function-type> _ <requirement>+ E
2561
  //
2562
  // https://github.com/itanium-cxx-abi/cxx-abi/issues/24
2563
0
  if (ParseTwoCharToken(state, "rQ") && ParseBareFunctionType(state) &&
2564
0
      ParseOneCharToken(state, '_') && OneOrMore(ParseRequirement, state) &&
2565
0
      ParseOneCharToken(state, 'E')) {
2566
0
    return true;
2567
0
  }
2568
0
  state->parse_state = copy;
2569
2570
0
  return ParseUnresolvedName(state);
2571
0
}
2572
2573
// <initializer> ::= pi <expression>* E
2574
//               ::= il <braced-expression>* E
2575
//
2576
// The il ... E form is not in the ABI spec but is seen in practice for
2577
// braced-init-lists in new-expressions, which are standard syntax from C++11
2578
// on.
2579
0
static bool ParseInitializer(State *state) {
2580
0
  ComplexityGuard guard(state);
2581
0
  if (guard.IsTooComplex()) return false;
2582
0
  ParseState copy = state->parse_state;
2583
2584
0
  if (ParseTwoCharToken(state, "pi") && ZeroOrMore(ParseExpression, state) &&
2585
0
      ParseOneCharToken(state, 'E')) {
2586
0
    return true;
2587
0
  }
2588
0
  state->parse_state = copy;
2589
2590
0
  if (ParseTwoCharToken(state, "il") &&
2591
0
      ZeroOrMore(ParseBracedExpression, state) &&
2592
0
      ParseOneCharToken(state, 'E')) {
2593
0
    return true;
2594
0
  }
2595
0
  state->parse_state = copy;
2596
0
  return false;
2597
0
}
2598
2599
// <expr-primary> ::= L <type> <(value) number> E
2600
//                ::= L <type> <(value) float> E
2601
//                ::= L <mangled-name> E
2602
//                // A bug in g++'s C++ ABI version 2 (-fabi-version=2).
2603
//                ::= LZ <encoding> E
2604
//
2605
// Warning, subtle: the "bug" LZ production above is ambiguous with the first
2606
// production where <type> starts with <local-name>, which can lead to
2607
// exponential backtracking in two scenarios:
2608
//
2609
// - When whatever follows the E in the <local-name> in the first production is
2610
//   not a name, we backtrack the whole <encoding> and re-parse the whole thing.
2611
//
2612
// - When whatever follows the <local-name> in the first production is not a
2613
//   number and this <expr-primary> may be followed by a name, we backtrack the
2614
//   <name> and re-parse it.
2615
//
2616
// Moreover this ambiguity isn't always resolved -- for example, the following
2617
// has two different parses:
2618
//
2619
//   _ZaaILZ4aoeuE1x1EvE
2620
//   => operator&&<aoeu, x, E, void>
2621
//   => operator&&<(aoeu::x)(1), void>
2622
//
2623
// To resolve this, we just do what GCC's demangler does, and refuse to parse
2624
// casts to <local-name> types.
2625
0
static bool ParseExprPrimary(State *state) {
2626
0
  ComplexityGuard guard(state);
2627
0
  if (guard.IsTooComplex()) return false;
2628
0
  ParseState copy = state->parse_state;
2629
2630
  // The "LZ" special case: if we see LZ, we commit to accept "LZ <encoding> E"
2631
  // or fail, no backtracking.
2632
0
  if (ParseTwoCharToken(state, "LZ")) {
2633
0
    if (ParseEncoding(state) && ParseOneCharToken(state, 'E')) {
2634
0
      return true;
2635
0
    }
2636
2637
0
    state->parse_state = copy;
2638
0
    return false;
2639
0
  }
2640
2641
0
  if (ParseOneCharToken(state, 'L')) {
2642
    // There are two special cases in which a literal may or must contain a type
2643
    // without a value.  The first is that both LDnE and LDn0E are valid
2644
    // encodings of nullptr, used in different situations.  Recognize LDnE here,
2645
    // leaving LDn0E to be recognized by the general logic afterward.
2646
0
    if (ParseThreeCharToken(state, "DnE")) return true;
2647
2648
    // The second special case is a string literal, currently mangled in C++98
2649
    // style as LA<length + 1>_KcE.  This is inadequate to support C++11 and
2650
    // later versions, and the discussion of this problem has not converged.
2651
    //
2652
    // https://github.com/itanium-cxx-abi/cxx-abi/issues/64
2653
    //
2654
    // For now the bare-type mangling is what's used in practice, so we
2655
    // recognize this form and only this form if an array type appears here.
2656
    // Someday we'll probably have to accept a new form of value mangling in
2657
    // LA...E constructs.  (Note also that C++20 allows a wide range of
2658
    // class-type objects as template arguments, so someday their values will be
2659
    // mangled and we'll have to recognize them here too.)
2660
0
    if (RemainingInput(state)[0] == 'A' /* an array type follows */) {
2661
0
      if (ParseType(state) && ParseOneCharToken(state, 'E')) return true;
2662
0
      state->parse_state = copy;
2663
0
      return false;
2664
0
    }
2665
2666
    // The merged cast production.
2667
0
    if (ParseType(state) && ParseExprCastValueAndTrailingE(state)) {
2668
0
      return true;
2669
0
    }
2670
0
  }
2671
0
  state->parse_state = copy;
2672
2673
0
  if (ParseOneCharToken(state, 'L') && ParseMangledName(state) &&
2674
0
      ParseOneCharToken(state, 'E')) {
2675
0
    return true;
2676
0
  }
2677
0
  state->parse_state = copy;
2678
2679
0
  return false;
2680
0
}
2681
2682
// <number> or <float>, followed by 'E', as described above ParseExprPrimary.
2683
0
static bool ParseExprCastValueAndTrailingE(State *state) {
2684
0
  ComplexityGuard guard(state);
2685
0
  if (guard.IsTooComplex()) return false;
2686
  // We have to be able to backtrack after accepting a number because we could
2687
  // have e.g. "7fffE", which will accept "7" as a number but then fail to find
2688
  // the 'E'.
2689
0
  ParseState copy = state->parse_state;
2690
0
  if (ParseNumber(state, nullptr) && ParseOneCharToken(state, 'E')) {
2691
0
    return true;
2692
0
  }
2693
0
  state->parse_state = copy;
2694
2695
0
  if (ParseFloatNumber(state)) {
2696
    // <float> for ordinary floating-point types
2697
0
    if (ParseOneCharToken(state, 'E')) return true;
2698
2699
    // <float> _ <float> for complex floating-point types
2700
0
    if (ParseOneCharToken(state, '_') && ParseFloatNumber(state) &&
2701
0
        ParseOneCharToken(state, 'E')) {
2702
0
      return true;
2703
0
    }
2704
0
  }
2705
0
  state->parse_state = copy;
2706
2707
0
  return false;
2708
0
}
2709
2710
// Parses `Q <requires-clause expr>`.
2711
// If parsing fails, applies backtracking to `state`.
2712
//
2713
// This function covers two symbols instead of one for convenience,
2714
// because in LLVM's Itanium ABI mangling grammar, <requires-clause expr>
2715
// always appears after Q.
2716
//
2717
// Does not emit the parsed `requires` clause to simplify the implementation.
2718
// In other words, these two functions' mangled names will demangle identically:
2719
//
2720
// template <typename T>
2721
// int foo(T) requires IsIntegral<T>;
2722
//
2723
// vs.
2724
//
2725
// template <typename T>
2726
// int foo(T);
2727
0
static bool ParseQRequiresClauseExpr(State *state) {
2728
0
  ComplexityGuard guard(state);
2729
0
  if (guard.IsTooComplex()) return false;
2730
0
  ParseState copy = state->parse_state;
2731
0
  DisableAppend(state);
2732
2733
  // <requires-clause expr> is just an <expression>: http://shortn/_9E1Ul0rIM8
2734
0
  if (ParseOneCharToken(state, 'Q') && ParseExpression(state)) {
2735
0
    RestoreAppend(state, copy.append);
2736
0
    return true;
2737
0
  }
2738
2739
  // also restores append
2740
0
  state->parse_state = copy;
2741
0
  return false;
2742
0
}
2743
2744
// <requirement> ::= X <expression> [N] [R <type-constraint>]
2745
// <requirement> ::= T <type>
2746
// <requirement> ::= Q <constraint-expression>
2747
//
2748
// <constraint-expression> ::= <expression>
2749
//
2750
// https://github.com/itanium-cxx-abi/cxx-abi/issues/24
2751
0
static bool ParseRequirement(State *state) {
2752
0
  ComplexityGuard guard(state);
2753
0
  if (guard.IsTooComplex()) return false;
2754
2755
0
  ParseState copy = state->parse_state;
2756
2757
0
  if (ParseOneCharToken(state, 'X') && ParseExpression(state) &&
2758
0
      Optional(ParseOneCharToken(state, 'N')) &&
2759
      // This logic backtracks cleanly if we eat an R but a valid type doesn't
2760
      // follow it.
2761
0
      (!ParseOneCharToken(state, 'R') || ParseTypeConstraint(state))) {
2762
0
    return true;
2763
0
  }
2764
0
  state->parse_state = copy;
2765
2766
0
  if (ParseOneCharToken(state, 'T') && ParseType(state)) return true;
2767
0
  state->parse_state = copy;
2768
2769
0
  if (ParseOneCharToken(state, 'Q') && ParseExpression(state)) return true;
2770
0
  state->parse_state = copy;
2771
2772
0
  return false;
2773
0
}
2774
2775
// <type-constraint> ::= <name>
2776
0
static bool ParseTypeConstraint(State *state) {
2777
0
  return ParseName(state);
2778
0
}
2779
2780
// <local-name> ::= Z <(function) encoding> E <(entity) name> [<discriminator>]
2781
//              ::= Z <(function) encoding> E s [<discriminator>]
2782
//              ::= Z <(function) encoding> E d [<(parameter) number>] _ <name>
2783
//
2784
// Parsing a common prefix of these two productions together avoids an
2785
// exponential blowup of backtracking.  Parse like:
2786
//   <local-name> := Z <encoding> E <local-name-suffix>
2787
//   <local-name-suffix> ::= s [<discriminator>]
2788
//                       ::= d [<(parameter) number>] _ <name>
2789
//                       ::= <name> [<discriminator>]
2790
2791
0
static bool ParseLocalNameSuffix(State *state) {
2792
0
  ComplexityGuard guard(state);
2793
0
  if (guard.IsTooComplex()) return false;
2794
0
  ParseState copy = state->parse_state;
2795
2796
  // <local-name-suffix> ::= d [<(parameter) number>] _ <name>
2797
0
  if (ParseOneCharToken(state, 'd') &&
2798
0
      (IsDigit(RemainingInput(state)[0]) || RemainingInput(state)[0] == '_')) {
2799
0
    int number = -1;
2800
0
    Optional(ParseNumber(state, &number));
2801
0
    if (number < -1 || number > 2147483645) {
2802
      // Work around overflow cases.  We do not expect these outside of a fuzzer
2803
      // or other source of adversarial input.  If we do detect overflow here,
2804
      // we'll print {default arg#1}.
2805
0
      number = -1;
2806
0
    }
2807
0
    number += 2;
2808
2809
    // The ::{default arg#1}:: infix must be rendered before the lambda itself,
2810
    // so print this before parsing the rest of the <local-name-suffix>.
2811
0
    MaybeAppend(state, "::{default arg#");
2812
0
    MaybeAppendDecimal(state, number);
2813
0
    MaybeAppend(state, "}::");
2814
0
    if (ParseOneCharToken(state, '_') && ParseName(state)) return true;
2815
2816
    // On late parse failure, roll back not only the input but also the output,
2817
    // whose trailing NUL was overwritten.
2818
0
    state->parse_state = copy;
2819
0
    if (state->parse_state.append) {
2820
0
      state->out[state->parse_state.out_cur_idx] = '\0';
2821
0
    }
2822
0
    return false;
2823
0
  }
2824
0
  state->parse_state = copy;
2825
2826
  // <local-name-suffix> ::= <name> [<discriminator>]
2827
0
  if (MaybeAppend(state, "::") && ParseName(state) &&
2828
0
      Optional(ParseDiscriminator(state))) {
2829
0
    return true;
2830
0
  }
2831
0
  state->parse_state = copy;
2832
0
  if (state->parse_state.append) {
2833
0
    state->out[state->parse_state.out_cur_idx] = '\0';
2834
0
  }
2835
2836
  // <local-name-suffix> ::= s [<discriminator>]
2837
0
  return ParseOneCharToken(state, 's') && Optional(ParseDiscriminator(state));
2838
0
}
2839
2840
0
static bool ParseLocalName(State *state) {
2841
0
  ComplexityGuard guard(state);
2842
0
  if (guard.IsTooComplex()) return false;
2843
0
  ParseState copy = state->parse_state;
2844
0
  if (ParseOneCharToken(state, 'Z') && ParseEncoding(state) &&
2845
0
      ParseOneCharToken(state, 'E') && ParseLocalNameSuffix(state)) {
2846
0
    return true;
2847
0
  }
2848
0
  state->parse_state = copy;
2849
0
  return false;
2850
0
}
2851
2852
// <discriminator> := _ <digit>
2853
//                 := __ <number (>= 10)> _
2854
0
static bool ParseDiscriminator(State *state) {
2855
0
  ComplexityGuard guard(state);
2856
0
  if (guard.IsTooComplex()) return false;
2857
0
  ParseState copy = state->parse_state;
2858
2859
  // Both forms start with _ so parse that first.
2860
0
  if (!ParseOneCharToken(state, '_')) return false;
2861
2862
  // <digit>
2863
0
  if (ParseDigit(state, nullptr)) return true;
2864
2865
  // _ <number> _
2866
0
  if (ParseOneCharToken(state, '_') && ParseNumber(state, nullptr) &&
2867
0
      ParseOneCharToken(state, '_')) {
2868
0
    return true;
2869
0
  }
2870
0
  state->parse_state = copy;
2871
0
  return false;
2872
0
}
2873
2874
// <substitution> ::= S_
2875
//                ::= S <seq-id> _
2876
//                ::= St, etc.
2877
//
2878
// "St" is special in that it's not valid as a standalone name, and it *is*
2879
// allowed to precede a name without being wrapped in "N...E".  This means that
2880
// if we accept it on its own, we can accept "St1a" and try to parse
2881
// template-args, then fail and backtrack, accept "St" on its own, then "1a" as
2882
// an unqualified name and re-parse the same template-args.  To block this
2883
// exponential backtracking, we disable it with 'accept_std=false' in
2884
// problematic contexts.
2885
0
static bool ParseSubstitution(State *state, bool accept_std) {
2886
0
  ComplexityGuard guard(state);
2887
0
  if (guard.IsTooComplex()) return false;
2888
0
  if (ParseTwoCharToken(state, "S_")) {
2889
0
    MaybeAppend(state, "?");  // We don't support substitutions.
2890
0
    return true;
2891
0
  }
2892
2893
0
  ParseState copy = state->parse_state;
2894
0
  if (ParseOneCharToken(state, 'S') && ParseSeqId(state) &&
2895
0
      ParseOneCharToken(state, '_')) {
2896
0
    MaybeAppend(state, "?");  // We don't support substitutions.
2897
0
    return true;
2898
0
  }
2899
0
  state->parse_state = copy;
2900
2901
  // Expand abbreviations like "St" => "std".
2902
0
  if (ParseOneCharToken(state, 'S')) {
2903
0
    const AbbrevPair *p;
2904
0
    for (p = kSubstitutionList; p->abbrev != nullptr; ++p) {
2905
0
      if (RemainingInput(state)[0] == p->abbrev[1] &&
2906
0
          (accept_std || p->abbrev[1] != 't')) {
2907
0
        MaybeAppend(state, "std");
2908
0
        if (p->real_name[0] != '\0') {
2909
0
          MaybeAppend(state, "::");
2910
0
          MaybeAppend(state, p->real_name);
2911
0
        }
2912
0
        ++state->parse_state.mangled_idx;
2913
0
        UpdateHighWaterMark(state);
2914
0
        return true;
2915
0
      }
2916
0
    }
2917
0
  }
2918
0
  state->parse_state = copy;
2919
0
  return false;
2920
0
}
2921
2922
// Parse <mangled-name>, optionally followed by either a function-clone suffix
2923
// or version suffix.  Returns true only if all of "mangled_cur" was consumed.
2924
0
static bool ParseTopLevelMangledName(State *state) {
2925
0
  ComplexityGuard guard(state);
2926
0
  if (guard.IsTooComplex()) return false;
2927
0
  if (ParseMangledName(state)) {
2928
0
    if (RemainingInput(state)[0] != '\0') {
2929
      // Drop trailing function clone suffix, if any.
2930
0
      if (IsFunctionCloneSuffix(RemainingInput(state))) {
2931
0
        return true;
2932
0
      }
2933
      // Append trailing version suffix if any.
2934
      // ex. _Z3foo@@GLIBCXX_3.4
2935
0
      if (RemainingInput(state)[0] == '@') {
2936
0
        MaybeAppend(state, RemainingInput(state));
2937
0
        return true;
2938
0
      }
2939
0
      ReportHighWaterMark(state);
2940
0
      return false;  // Unconsumed suffix.
2941
0
    }
2942
0
    return true;
2943
0
  }
2944
2945
0
  ReportHighWaterMark(state);
2946
0
  return false;
2947
0
}
2948
2949
0
static bool Overflowed(const State *state) {
2950
0
  return state->parse_state.out_cur_idx >= state->out_end_idx;
2951
0
}
2952
2953
// The demangler entry point.
2954
0
bool Demangle(const char* mangled, char* out, size_t out_size) {
2955
0
  if (mangled[0] == '_' && mangled[1] == 'R') {
2956
0
    return DemangleRustSymbolEncoding(mangled, out, out_size);
2957
0
  }
2958
2959
0
  State state;
2960
0
  InitState(&state, mangled, out, out_size);
2961
0
  return ParseTopLevelMangledName(&state) && !Overflowed(&state) &&
2962
0
         state.parse_state.out_cur_idx > 0;
2963
0
}
2964
2965
0
std::string DemangleString(const char* mangled) {
2966
0
  std::string out;
2967
0
  int status = 0;
2968
0
  char* demangled = nullptr;
2969
0
#if ABSL_INTERNAL_HAS_CXA_DEMANGLE
2970
0
  demangled = abi::__cxa_demangle(mangled, nullptr, nullptr, &status);
2971
0
#endif
2972
0
  if (status == 0 && demangled != nullptr) {
2973
0
    out.append(demangled);
2974
0
    free(demangled);
2975
0
  } else {
2976
0
    out.append(mangled);
2977
0
  }
2978
0
  return out;
2979
0
}
2980
2981
}  // namespace debugging_internal
2982
ABSL_NAMESPACE_END
2983
}  // namespace absl