LLVM  6.0.0svn
ItaniumDemangle.cpp
Go to the documentation of this file.
1 //===- ItaniumDemangle.cpp ------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/Demangle/Demangle.h"
11 
12 // This file exports a single function: llvm::itanium_demangle.
13 // It also has no dependencies on the rest of llvm. It is implemented this way
14 // so that it can be easily reused in libcxxabi.
15 
16 #include <algorithm>
17 #include <cctype>
18 #include <cstdlib>
19 #include <cstring>
20 #include <numeric>
21 #include <string>
22 #include <vector>
23 
24 #ifdef _MSC_VER
25 // snprintf is implemented in VS 2015
26 #if _MSC_VER < 1900
27 #define snprintf _snprintf_s
28 #endif
29 #endif
30 
31 enum {
37 };
38 
39 enum {
40  CV_const = (1 << 0),
41  CV_volatile = (1 << 1),
42  CV_restrict = (1 << 2),
43 };
44 
45 template <class C>
46 static const char *parse_type(const char *first, const char *last, C &db);
47 template <class C>
48 static const char *parse_encoding(const char *first, const char *last, C &db);
49 template <class C>
50 static const char *parse_name(const char *first, const char *last, C &db,
51  bool *ends_with_template_args = 0);
52 template <class C>
53 static const char *parse_expression(const char *first, const char *last, C &db);
54 template <class C>
55 static const char *parse_template_args(const char *first, const char *last,
56  C &db);
57 template <class C>
58 static const char *parse_operator_name(const char *first, const char *last,
59  C &db);
60 template <class C>
61 static const char *parse_unqualified_name(const char *first, const char *last,
62  C &db);
63 template <class C>
64 static const char *parse_decltype(const char *first, const char *last, C &db);
65 
66 // <number> ::= [n] <non-negative decimal integer>
67 
68 static const char *parse_number(const char *first, const char *last) {
69  if (first != last) {
70  const char *t = first;
71  if (*t == 'n')
72  ++t;
73  if (t != last) {
74  if (*t == '0') {
75  first = t + 1;
76  } else if ('1' <= *t && *t <= '9') {
77  first = t + 1;
78  while (first != last && std::isdigit(*first))
79  ++first;
80  }
81  }
82  }
83  return first;
84 }
85 
86 namespace {
87 template <class Float> struct float_data;
88 
89 template <> struct float_data<float> {
90  static const size_t mangled_size = 8;
91  static const size_t max_demangled_size = 24;
92  static const char *spec;
93 };
94 const char *float_data<float>::spec = "%af";
95 
96 template <> struct float_data<double> {
97  static const size_t mangled_size = 16;
98  static const size_t max_demangled_size = 32;
99  static const char *spec;
100 };
101 
102 const char *float_data<double>::spec = "%a";
103 
104 template <> struct float_data<long double> {
105 #if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) || \
106  defined(__wasm__)
107  static const size_t mangled_size = 32;
108 #elif defined(__arm__) || defined(__mips__) || defined(__hexagon__)
109  static const size_t mangled_size = 16;
110 #else
111  static const size_t mangled_size =
112  20; // May need to be adjusted to 16 or 24 on other platforms
113 #endif
114  static const size_t max_demangled_size = 40;
115  static const char *spec;
116 };
117 
118 const char *float_data<long double>::spec = "%LaL";
119 }
120 
121 template <class Float, class C>
122 static const char *parse_floating_number(const char *first, const char *last,
123  C &db) {
124  const size_t N = float_data<Float>::mangled_size;
125  if (static_cast<std::size_t>(last - first) > N) {
126  last = first + N;
127  union {
128  Float value;
129  char buf[sizeof(Float)];
130  };
131  const char *t = first;
132  char *e = buf;
133  for (; t != last; ++t, ++e) {
134  if (!isxdigit(*t))
135  return first;
136  unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
137  : static_cast<unsigned>(*t - 'a' + 10);
138  ++t;
139  unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
140  : static_cast<unsigned>(*t - 'a' + 10);
141  *e = static_cast<char>((d1 << 4) + d0);
142  }
143  if (*t == 'E') {
144 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
145  std::reverse(buf, e);
146 #endif
147  char num[float_data<Float>::max_demangled_size] = {0};
148  int n = snprintf(num, sizeof(num), float_data<Float>::spec, value);
149  if (static_cast<std::size_t>(n) >= sizeof(num))
150  return first;
151  db.names.push_back(std::string(num, static_cast<std::size_t>(n)));
152  first = t + 1;
153  }
154  }
155  return first;
156 }
157 
158 // <source-name> ::= <positive length number> <identifier>
159 
160 template <class C>
161 static const char *parse_source_name(const char *first, const char *last,
162  C &db) {
163  if (first != last) {
164  char c = *first;
165  if (isdigit(c) && first + 1 != last) {
166  const char *t = first + 1;
167  size_t n = static_cast<size_t>(c - '0');
168  for (c = *t; isdigit(c); c = *t) {
169  n = n * 10 + static_cast<size_t>(c - '0');
170  if (++t == last)
171  return first;
172  }
173  if (static_cast<size_t>(last - t) >= n) {
174  std::string r(t, n);
175  if (r.substr(0, 10) == "_GLOBAL__N")
176  db.names.push_back("(anonymous namespace)");
177  else
178  db.names.push_back(std::move(r));
179  first = t + n;
180  }
181  }
182  }
183  return first;
184 }
185 
186 // <substitution> ::= S <seq-id> _
187 // ::= S_
188 // <substitution> ::= Sa # ::std::allocator
189 // <substitution> ::= Sb # ::std::basic_string
190 // <substitution> ::= Ss # ::std::basic_string < char,
191 // ::std::char_traits<char>,
192 // ::std::allocator<char> >
193 // <substitution> ::= Si # ::std::basic_istream<char, std::char_traits<char> >
194 // <substitution> ::= So # ::std::basic_ostream<char, std::char_traits<char> >
195 // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
196 
197 template <class C>
198 static const char *parse_substitution(const char *first, const char *last,
199  C &db) {
200  if (last - first >= 2) {
201  if (*first == 'S') {
202  switch (first[1]) {
203  case 'a':
204  db.names.push_back("std::allocator");
205  first += 2;
206  break;
207  case 'b':
208  db.names.push_back("std::basic_string");
209  first += 2;
210  break;
211  case 's':
212  db.names.push_back("std::string");
213  first += 2;
214  break;
215  case 'i':
216  db.names.push_back("std::istream");
217  first += 2;
218  break;
219  case 'o':
220  db.names.push_back("std::ostream");
221  first += 2;
222  break;
223  case 'd':
224  db.names.push_back("std::iostream");
225  first += 2;
226  break;
227  case '_':
228  if (!db.subs.empty()) {
229  for (const auto &n : db.subs.front())
230  db.names.push_back(n);
231  first += 2;
232  }
233  break;
234  default:
235  if (std::isdigit(first[1]) || std::isupper(first[1])) {
236  size_t sub = 0;
237  const char *t = first + 1;
238  if (std::isdigit(*t))
239  sub = static_cast<size_t>(*t - '0');
240  else
241  sub = static_cast<size_t>(*t - 'A') + 10;
242  for (++t; t != last && (std::isdigit(*t) || std::isupper(*t)); ++t) {
243  sub *= 36;
244  if (std::isdigit(*t))
245  sub += static_cast<size_t>(*t - '0');
246  else
247  sub += static_cast<size_t>(*t - 'A') + 10;
248  }
249  if (t == last || *t != '_')
250  return first;
251  ++sub;
252  if (sub < db.subs.size()) {
253  for (const auto &n : db.subs[sub])
254  db.names.push_back(n);
255  first = t + 1;
256  }
257  }
258  break;
259  }
260  }
261  }
262  return first;
263 }
264 
265 // <builtin-type> ::= v # void
266 // ::= w # wchar_t
267 // ::= b # bool
268 // ::= c # char
269 // ::= a # signed char
270 // ::= h # unsigned char
271 // ::= s # short
272 // ::= t # unsigned short
273 // ::= i # int
274 // ::= j # unsigned int
275 // ::= l # long
276 // ::= m # unsigned long
277 // ::= x # long long, __int64
278 // ::= y # unsigned long long, __int64
279 // ::= n # __int128
280 // ::= o # unsigned __int128
281 // ::= f # float
282 // ::= d # double
283 // ::= e # long double, __float80
284 // ::= g # __float128
285 // ::= z # ellipsis
286 // ::= Dd # IEEE 754r decimal floating point (64 bits)
287 // ::= De # IEEE 754r decimal floating point (128 bits)
288 // ::= Df # IEEE 754r decimal floating point (32 bits)
289 // ::= Dh # IEEE 754r half-precision floating point (16 bits)
290 // ::= Di # char32_t
291 // ::= Ds # char16_t
292 // ::= Da # auto (in dependent new-expressions)
293 // ::= Dc # decltype(auto)
294 // ::= Dn # std::nullptr_t (i.e., decltype(nullptr))
295 // ::= u <source-name> # vendor extended type
296 
297 template <class C>
298 static const char *parse_builtin_type(const char *first, const char *last,
299  C &db) {
300  if (first != last) {
301  switch (*first) {
302  case 'v':
303  db.names.push_back("void");
304  ++first;
305  break;
306  case 'w':
307  db.names.push_back("wchar_t");
308  ++first;
309  break;
310  case 'b':
311  db.names.push_back("bool");
312  ++first;
313  break;
314  case 'c':
315  db.names.push_back("char");
316  ++first;
317  break;
318  case 'a':
319  db.names.push_back("signed char");
320  ++first;
321  break;
322  case 'h':
323  db.names.push_back("unsigned char");
324  ++first;
325  break;
326  case 's':
327  db.names.push_back("short");
328  ++first;
329  break;
330  case 't':
331  db.names.push_back("unsigned short");
332  ++first;
333  break;
334  case 'i':
335  db.names.push_back("int");
336  ++first;
337  break;
338  case 'j':
339  db.names.push_back("unsigned int");
340  ++first;
341  break;
342  case 'l':
343  db.names.push_back("long");
344  ++first;
345  break;
346  case 'm':
347  db.names.push_back("unsigned long");
348  ++first;
349  break;
350  case 'x':
351  db.names.push_back("long long");
352  ++first;
353  break;
354  case 'y':
355  db.names.push_back("unsigned long long");
356  ++first;
357  break;
358  case 'n':
359  db.names.push_back("__int128");
360  ++first;
361  break;
362  case 'o':
363  db.names.push_back("unsigned __int128");
364  ++first;
365  break;
366  case 'f':
367  db.names.push_back("float");
368  ++first;
369  break;
370  case 'd':
371  db.names.push_back("double");
372  ++first;
373  break;
374  case 'e':
375  db.names.push_back("long double");
376  ++first;
377  break;
378  case 'g':
379  db.names.push_back("__float128");
380  ++first;
381  break;
382  case 'z':
383  db.names.push_back("...");
384  ++first;
385  break;
386  case 'u': {
387  const char *t = parse_source_name(first + 1, last, db);
388  if (t != first + 1)
389  first = t;
390  } break;
391  case 'D':
392  if (first + 1 != last) {
393  switch (first[1]) {
394  case 'd':
395  db.names.push_back("decimal64");
396  first += 2;
397  break;
398  case 'e':
399  db.names.push_back("decimal128");
400  first += 2;
401  break;
402  case 'f':
403  db.names.push_back("decimal32");
404  first += 2;
405  break;
406  case 'h':
407  db.names.push_back("decimal16");
408  first += 2;
409  break;
410  case 'i':
411  db.names.push_back("char32_t");
412  first += 2;
413  break;
414  case 's':
415  db.names.push_back("char16_t");
416  first += 2;
417  break;
418  case 'a':
419  db.names.push_back("auto");
420  first += 2;
421  break;
422  case 'c':
423  db.names.push_back("decltype(auto)");
424  first += 2;
425  break;
426  case 'n':
427  db.names.push_back("std::nullptr_t");
428  first += 2;
429  break;
430  }
431  }
432  break;
433  }
434  }
435  return first;
436 }
437 
438 // <CV-qualifiers> ::= [r] [V] [K]
439 
440 static const char *parse_cv_qualifiers(const char *first, const char *last,
441  unsigned &cv) {
442  cv = 0;
443  if (first != last) {
444  if (*first == 'r') {
445  cv |= CV_restrict;
446  ++first;
447  }
448  if (*first == 'V') {
449  cv |= CV_volatile;
450  ++first;
451  }
452  if (*first == 'K') {
453  cv |= CV_const;
454  ++first;
455  }
456  }
457  return first;
458 }
459 
460 // <template-param> ::= T_ # first template parameter
461 // ::= T <parameter-2 non-negative number> _
462 
463 template <class C>
464 static const char *parse_template_param(const char *first, const char *last,
465  C &db) {
466  if (last - first >= 2) {
467  if (*first == 'T') {
468  if (first[1] == '_') {
469  if (db.template_param.empty())
470  return first;
471  if (!db.template_param.back().empty()) {
472  for (auto &t : db.template_param.back().front())
473  db.names.push_back(t);
474  first += 2;
475  } else {
476  db.names.push_back("T_");
477  first += 2;
478  db.fix_forward_references = true;
479  }
480  } else if (isdigit(first[1])) {
481  const char *t = first + 1;
482  size_t sub = static_cast<size_t>(*t - '0');
483  for (++t; t != last && isdigit(*t); ++t) {
484  sub *= 10;
485  sub += static_cast<size_t>(*t - '0');
486  }
487  if (t == last || *t != '_' || db.template_param.empty())
488  return first;
489  ++sub;
490  if (sub < db.template_param.back().size()) {
491  for (auto &temp : db.template_param.back()[sub])
492  db.names.push_back(temp);
493  first = t + 1;
494  } else {
495  db.names.push_back(std::string(first, t + 1));
496  first = t + 1;
497  db.fix_forward_references = true;
498  }
499  }
500  }
501  }
502  return first;
503 }
504 
505 // cc <type> <expression> # const_cast<type>
506 // (expression)
507 
508 template <class C>
509 static const char *parse_const_cast_expr(const char *first, const char *last,
510  C &db) {
511  if (last - first >= 3 && first[0] == 'c' && first[1] == 'c') {
512  const char *t = parse_type(first + 2, last, db);
513  if (t != first + 2) {
514  const char *t1 = parse_expression(t, last, db);
515  if (t1 != t) {
516  if (db.names.size() < 2)
517  return first;
518  auto expr = db.names.back().move_full();
519  db.names.pop_back();
520  if (db.names.empty())
521  return first;
522  db.names.back() =
523  "const_cast<" + db.names.back().move_full() + ">(" + expr + ")";
524  first = t1;
525  }
526  }
527  }
528  return first;
529 }
530 
531 // dc <type> <expression> # dynamic_cast<type>
532 // (expression)
533 
534 template <class C>
535 static const char *parse_dynamic_cast_expr(const char *first, const char *last,
536  C &db) {
537  if (last - first >= 3 && first[0] == 'd' && first[1] == 'c') {
538  const char *t = parse_type(first + 2, last, db);
539  if (t != first + 2) {
540  const char *t1 = parse_expression(t, last, db);
541  if (t1 != t) {
542  if (db.names.size() < 2)
543  return first;
544  auto expr = db.names.back().move_full();
545  db.names.pop_back();
546  if (db.names.empty())
547  return first;
548  db.names.back() =
549  "dynamic_cast<" + db.names.back().move_full() + ">(" + expr + ")";
550  first = t1;
551  }
552  }
553  }
554  return first;
555 }
556 
557 // rc <type> <expression> # reinterpret_cast<type>
558 // (expression)
559 
560 template <class C>
561 static const char *parse_reinterpret_cast_expr(const char *first,
562  const char *last, C &db) {
563  if (last - first >= 3 && first[0] == 'r' && first[1] == 'c') {
564  const char *t = parse_type(first + 2, last, db);
565  if (t != first + 2) {
566  const char *t1 = parse_expression(t, last, db);
567  if (t1 != t) {
568  if (db.names.size() < 2)
569  return first;
570  auto expr = db.names.back().move_full();
571  db.names.pop_back();
572  if (db.names.empty())
573  return first;
574  db.names.back() = "reinterpret_cast<" + db.names.back().move_full() +
575  ">(" + expr + ")";
576  first = t1;
577  }
578  }
579  }
580  return first;
581 }
582 
583 // sc <type> <expression> # static_cast<type>
584 // (expression)
585 
586 template <class C>
587 static const char *parse_static_cast_expr(const char *first, const char *last,
588  C &db) {
589  if (last - first >= 3 && first[0] == 's' && first[1] == 'c') {
590  const char *t = parse_type(first + 2, last, db);
591  if (t != first + 2) {
592  const char *t1 = parse_expression(t, last, db);
593  if (t1 != t) {
594  if (db.names.size() < 2)
595  return first;
596  auto expr = db.names.back().move_full();
597  db.names.pop_back();
598  db.names.back() =
599  "static_cast<" + db.names.back().move_full() + ">(" + expr + ")";
600  first = t1;
601  }
602  }
603  }
604  return first;
605 }
606 
607 // sp <expression> # pack expansion
608 
609 template <class C>
610 static const char *parse_pack_expansion(const char *first, const char *last,
611  C &db) {
612  if (last - first >= 3 && first[0] == 's' && first[1] == 'p') {
613  const char *t = parse_expression(first + 2, last, db);
614  if (t != first + 2)
615  first = t;
616  }
617  return first;
618 }
619 
620 // st <type> # sizeof (a type)
621 
622 template <class C>
623 static const char *parse_sizeof_type_expr(const char *first, const char *last,
624  C &db) {
625  if (last - first >= 3 && first[0] == 's' && first[1] == 't') {
626  const char *t = parse_type(first + 2, last, db);
627  if (t != first + 2) {
628  if (db.names.empty())
629  return first;
630  db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
631  first = t;
632  }
633  }
634  return first;
635 }
636 
637 // sz <expr> # sizeof (a expression)
638 
639 template <class C>
640 static const char *parse_sizeof_expr_expr(const char *first, const char *last,
641  C &db) {
642  if (last - first >= 3 && first[0] == 's' && first[1] == 'z') {
643  const char *t = parse_expression(first + 2, last, db);
644  if (t != first + 2) {
645  if (db.names.empty())
646  return first;
647  db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
648  first = t;
649  }
650  }
651  return first;
652 }
653 
654 // sZ <template-param> # size of a parameter
655 // pack
656 
657 template <class C>
658 static const char *parse_sizeof_param_pack_expr(const char *first,
659  const char *last, C &db) {
660  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' &&
661  first[2] == 'T') {
662  size_t k0 = db.names.size();
663  const char *t = parse_template_param(first + 2, last, db);
664  size_t k1 = db.names.size();
665  if (t != first + 2) {
666  std::string tmp("sizeof...(");
667  size_t k = k0;
668  if (k != k1) {
669  tmp += db.names[k].move_full();
670  for (++k; k != k1; ++k)
671  tmp += ", " + db.names[k].move_full();
672  }
673  tmp += ")";
674  for (; k1 != k0; --k1)
675  db.names.pop_back();
676  db.names.push_back(std::move(tmp));
677  first = t;
678  }
679  }
680  return first;
681 }
682 
683 // <function-param> ::= fp <top-level CV-qualifiers> _ # L == 0, first parameter
684 // ::= fp <top-level CV-qualifiers> <parameter-2 non-negative
685 // number> _ # L == 0, second and later parameters
686 // ::= fL <L-1 non-negative number> p <top-level CV-qualifiers>
687 // _ # L > 0, first parameter
688 // ::= fL <L-1 non-negative number> p <top-level CV-qualifiers>
689 // <parameter-2 non-negative number> _ # L > 0, second and
690 // later parameters
691 
692 template <class C>
693 static const char *parse_function_param(const char *first, const char *last,
694  C &db) {
695  if (last - first >= 3 && *first == 'f') {
696  if (first[1] == 'p') {
697  unsigned cv;
698  const char *t = parse_cv_qualifiers(first + 2, last, cv);
699  const char *t1 = parse_number(t, last);
700  if (t1 != last && *t1 == '_') {
701  db.names.push_back("fp" + std::string(t, t1));
702  first = t1 + 1;
703  }
704  } else if (first[1] == 'L') {
705  unsigned cv;
706  const char *t0 = parse_number(first + 2, last);
707  if (t0 != last && *t0 == 'p') {
708  ++t0;
709  const char *t = parse_cv_qualifiers(t0, last, cv);
710  const char *t1 = parse_number(t, last);
711  if (t1 != last && *t1 == '_') {
712  db.names.push_back("fp" + std::string(t, t1));
713  first = t1 + 1;
714  }
715  }
716  }
717  }
718  return first;
719 }
720 
721 // sZ <function-param> # size of a function
722 // parameter pack
723 
724 template <class C>
725 static const char *parse_sizeof_function_param_pack_expr(const char *first,
726  const char *last,
727  C &db) {
728  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' &&
729  first[2] == 'f') {
730  const char *t = parse_function_param(first + 2, last, db);
731  if (t != first + 2) {
732  if (db.names.empty())
733  return first;
734  db.names.back() = "sizeof...(" + db.names.back().move_full() + ")";
735  first = t;
736  }
737  }
738  return first;
739 }
740 
741 // te <expression> # typeid (expression)
742 // ti <type> # typeid (type)
743 
744 template <class C>
745 static const char *parse_typeid_expr(const char *first, const char *last,
746  C &db) {
747  if (last - first >= 3 && first[0] == 't' &&
748  (first[1] == 'e' || first[1] == 'i')) {
749  const char *t;
750  if (first[1] == 'e')
751  t = parse_expression(first + 2, last, db);
752  else
753  t = parse_type(first + 2, last, db);
754  if (t != first + 2) {
755  if (db.names.empty())
756  return first;
757  db.names.back() = "typeid(" + db.names.back().move_full() + ")";
758  first = t;
759  }
760  }
761  return first;
762 }
763 
764 // tw <expression> # throw expression
765 
766 template <class C>
767 static const char *parse_throw_expr(const char *first, const char *last,
768  C &db) {
769  if (last - first >= 3 && first[0] == 't' && first[1] == 'w') {
770  const char *t = parse_expression(first + 2, last, db);
771  if (t != first + 2) {
772  if (db.names.empty())
773  return first;
774  db.names.back() = "throw " + db.names.back().move_full();
775  first = t;
776  }
777  }
778  return first;
779 }
780 
781 // ds <expression> <expression> # expr.*expr
782 
783 template <class C>
784 static const char *parse_dot_star_expr(const char *first, const char *last,
785  C &db) {
786  if (last - first >= 3 && first[0] == 'd' && first[1] == 's') {
787  const char *t = parse_expression(first + 2, last, db);
788  if (t != first + 2) {
789  const char *t1 = parse_expression(t, last, db);
790  if (t1 != t) {
791  if (db.names.size() < 2)
792  return first;
793  auto expr = db.names.back().move_full();
794  db.names.pop_back();
795  db.names.back().first += ".*" + expr;
796  first = t1;
797  }
798  }
799  }
800  return first;
801 }
802 
803 // <simple-id> ::= <source-name> [ <template-args> ]
804 
805 template <class C>
806 static const char *parse_simple_id(const char *first, const char *last, C &db) {
807  if (first != last) {
808  const char *t = parse_source_name(first, last, db);
809  if (t != first) {
810  const char *t1 = parse_template_args(t, last, db);
811  if (t1 != t) {
812  if (db.names.size() < 2)
813  return first;
814  auto args = db.names.back().move_full();
815  db.names.pop_back();
816  db.names.back().first += std::move(args);
817  }
818  first = t1;
819  } else
820  first = t;
821  }
822  return first;
823 }
824 
825 // <unresolved-type> ::= <template-param>
826 // ::= <decltype>
827 // ::= <substitution>
828 
829 template <class C>
830 static const char *parse_unresolved_type(const char *first, const char *last,
831  C &db) {
832  if (first != last) {
833  const char *t = first;
834  switch (*first) {
835  case 'T': {
836  size_t k0 = db.names.size();
837  t = parse_template_param(first, last, db);
838  size_t k1 = db.names.size();
839  if (t != first && k1 == k0 + 1) {
840  db.subs.push_back(typename C::sub_type(1, db.names.back()));
841  first = t;
842  } else {
843  for (; k1 != k0; --k1)
844  db.names.pop_back();
845  }
846  break;
847  }
848  case 'D':
849  t = parse_decltype(first, last, db);
850  if (t != first) {
851  if (db.names.empty())
852  return first;
853  db.subs.push_back(typename C::sub_type(1, db.names.back()));
854  first = t;
855  }
856  break;
857  case 'S':
858  t = parse_substitution(first, last, db);
859  if (t != first)
860  first = t;
861  else {
862  if (last - first > 2 && first[1] == 't') {
863  t = parse_unqualified_name(first + 2, last, db);
864  if (t != first + 2) {
865  if (db.names.empty())
866  return first;
867  db.names.back().first.insert(0, "std::");
868  db.subs.push_back(typename C::sub_type(1, db.names.back()));
869  first = t;
870  }
871  }
872  }
873  break;
874  }
875  }
876  return first;
877 }
878 
879 // <destructor-name> ::= <unresolved-type> # e.g.,
880 // ~T or ~decltype(f())
881 // ::= <simple-id> # e.g.,
882 // ~A<2*N>
883 
884 template <class C>
885 static const char *parse_destructor_name(const char *first, const char *last,
886  C &db) {
887  if (first != last) {
888  const char *t = parse_unresolved_type(first, last, db);
889  if (t == first)
890  t = parse_simple_id(first, last, db);
891  if (t != first) {
892  if (db.names.empty())
893  return first;
894  db.names.back().first.insert(0, "~");
895  first = t;
896  }
897  }
898  return first;
899 }
900 
901 // <base-unresolved-name> ::= <simple-id> #
902 // unresolved name
903 // extension ::= <operator-name> #
904 // unresolved operator-function-id
905 // extension ::= <operator-name> <template-args> #
906 // unresolved operator template-id
907 // ::= on <operator-name> #
908 // unresolved operator-function-id
909 // ::= on <operator-name> <template-args> #
910 // unresolved operator template-id
911 // ::= dn <destructor-name> #
912 // destructor or pseudo-destructor;
913 // #
914 // e.g.
915 // ~X or
916 // ~X<N-1>
917 
918 template <class C>
919 static const char *parse_base_unresolved_name(const char *first,
920  const char *last, C &db) {
921  if (last - first >= 2) {
922  if ((first[0] == 'o' || first[0] == 'd') && first[1] == 'n') {
923  if (first[0] == 'o') {
924  const char *t = parse_operator_name(first + 2, last, db);
925  if (t != first + 2) {
926  first = parse_template_args(t, last, db);
927  if (first != t) {
928  if (db.names.size() < 2)
929  return first;
930  auto args = db.names.back().move_full();
931  db.names.pop_back();
932  db.names.back().first += std::move(args);
933  }
934  }
935  } else {
936  const char *t = parse_destructor_name(first + 2, last, db);
937  if (t != first + 2)
938  first = t;
939  }
940  } else {
941  const char *t = parse_simple_id(first, last, db);
942  if (t == first) {
943  t = parse_operator_name(first, last, db);
944  if (t != first) {
945  first = parse_template_args(t, last, db);
946  if (first != t) {
947  if (db.names.size() < 2)
948  return first;
949  auto args = db.names.back().move_full();
950  db.names.pop_back();
951  db.names.back().first += std::move(args);
952  }
953  }
954  } else
955  first = t;
956  }
957  }
958  return first;
959 }
960 
961 // <unresolved-qualifier-level> ::= <simple-id>
962 
963 template <class C>
964 static const char *parse_unresolved_qualifier_level(const char *first,
965  const char *last, C &db) {
966  return parse_simple_id(first, last, db);
967 }
968 
969 // <unresolved-name>
970 // extension ::= srN <unresolved-type> [<template-args>]
971 // <unresolved-qualifier-level>* E <base-unresolved-name>
972 // ::= [gs] <base-unresolved-name> # x or
973 // (with "gs") ::x
974 // ::= [gs] sr <unresolved-qualifier-level>+ E
975 // <base-unresolved-name>
976 // # A::x,
977 // N::y,
978 // A<T>::z;
979 // "gs"
980 // means
981 // leading
982 // "::"
983 // ::= sr <unresolved-type> <base-unresolved-name> # T::x
984 // / decltype(p)::x
985 // extension ::= sr <unresolved-type> <template-args>
986 // <base-unresolved-name>
987 // #
988 // T::N::x
989 // /decltype(p)::N::x
990 // (ignored) ::= srN <unresolved-type> <unresolved-qualifier-level>+ E
991 // <base-unresolved-name>
992 
993 template <class C>
994 static const char *parse_unresolved_name(const char *first, const char *last,
995  C &db) {
996  if (last - first > 2) {
997  const char *t = first;
998  bool global = false;
999  if (t[0] == 'g' && t[1] == 's') {
1000  global = true;
1001  t += 2;
1002  }
1003  const char *t2 = parse_base_unresolved_name(t, last, db);
1004  if (t2 != t) {
1005  if (global) {
1006  if (db.names.empty())
1007  return first;
1008  db.names.back().first.insert(0, "::");
1009  }
1010  first = t2;
1011  } else if (last - t > 2 && t[0] == 's' && t[1] == 'r') {
1012  if (t[2] == 'N') {
1013  t += 3;
1014  const char *t1 = parse_unresolved_type(t, last, db);
1015  if (t1 == t || t1 == last)
1016  return first;
1017  t = t1;
1018  t1 = parse_template_args(t, last, db);
1019  if (t1 != t) {
1020  if (db.names.size() < 2)
1021  return first;
1022  auto args = db.names.back().move_full();
1023  db.names.pop_back();
1024  db.names.back().first += std::move(args);
1025  t = t1;
1026  if (t == last) {
1027  db.names.pop_back();
1028  return first;
1029  }
1030  }
1031  while (*t != 'E') {
1032  t1 = parse_unresolved_qualifier_level(t, last, db);
1033  if (t1 == t || t1 == last || db.names.size() < 2)
1034  return first;
1035  auto s = db.names.back().move_full();
1036  db.names.pop_back();
1037  db.names.back().first += "::" + std::move(s);
1038  t = t1;
1039  }
1040  ++t;
1041  t1 = parse_base_unresolved_name(t, last, db);
1042  if (t1 == t) {
1043  if (!db.names.empty())
1044  db.names.pop_back();
1045  return first;
1046  }
1047  if (db.names.size() < 2)
1048  return first;
1049  auto s = db.names.back().move_full();
1050  db.names.pop_back();
1051  db.names.back().first += "::" + std::move(s);
1052  first = t1;
1053  } else {
1054  t += 2;
1055  const char *t1 = parse_unresolved_type(t, last, db);
1056  if (t1 != t) {
1057  t = t1;
1058  t1 = parse_template_args(t, last, db);
1059  if (t1 != t) {
1060  if (db.names.size() < 2)
1061  return first;
1062  auto args = db.names.back().move_full();
1063  db.names.pop_back();
1064  db.names.back().first += std::move(args);
1065  t = t1;
1066  }
1067  t1 = parse_base_unresolved_name(t, last, db);
1068  if (t1 == t) {
1069  if (!db.names.empty())
1070  db.names.pop_back();
1071  return first;
1072  }
1073  if (db.names.size() < 2)
1074  return first;
1075  auto s = db.names.back().move_full();
1076  db.names.pop_back();
1077  db.names.back().first += "::" + std::move(s);
1078  first = t1;
1079  } else {
1080  t1 = parse_unresolved_qualifier_level(t, last, db);
1081  if (t1 == t || t1 == last)
1082  return first;
1083  t = t1;
1084  if (global) {
1085  if (db.names.empty())
1086  return first;
1087  db.names.back().first.insert(0, "::");
1088  }
1089  while (*t != 'E') {
1090  t1 = parse_unresolved_qualifier_level(t, last, db);
1091  if (t1 == t || t1 == last || db.names.size() < 2)
1092  return first;
1093  auto s = db.names.back().move_full();
1094  db.names.pop_back();
1095  db.names.back().first += "::" + std::move(s);
1096  t = t1;
1097  }
1098  ++t;
1099  t1 = parse_base_unresolved_name(t, last, db);
1100  if (t1 == t) {
1101  if (!db.names.empty())
1102  db.names.pop_back();
1103  return first;
1104  }
1105  if (db.names.size() < 2)
1106  return first;
1107  auto s = db.names.back().move_full();
1108  db.names.pop_back();
1109  db.names.back().first += "::" + std::move(s);
1110  first = t1;
1111  }
1112  }
1113  }
1114  }
1115  return first;
1116 }
1117 
1118 // dt <expression> <unresolved-name> # expr.name
1119 
1120 template <class C>
1121 static const char *parse_dot_expr(const char *first, const char *last, C &db) {
1122  if (last - first >= 3 && first[0] == 'd' && first[1] == 't') {
1123  const char *t = parse_expression(first + 2, last, db);
1124  if (t != first + 2) {
1125  const char *t1 = parse_unresolved_name(t, last, db);
1126  if (t1 != t) {
1127  if (db.names.size() < 2)
1128  return first;
1129  auto name = db.names.back().move_full();
1130  db.names.pop_back();
1131  if (db.names.empty())
1132  return first;
1133  db.names.back().first += "." + name;
1134  first = t1;
1135  }
1136  }
1137  }
1138  return first;
1139 }
1140 
1141 // cl <expression>+ E # call
1142 
1143 template <class C>
1144 static const char *parse_call_expr(const char *first, const char *last, C &db) {
1145  if (last - first >= 4 && first[0] == 'c' && first[1] == 'l') {
1146  const char *t = parse_expression(first + 2, last, db);
1147  if (t != first + 2) {
1148  if (t == last)
1149  return first;
1150  if (db.names.empty())
1151  return first;
1152  db.names.back().first += db.names.back().second;
1153  db.names.back().second = std::string();
1154  db.names.back().first.append("(");
1155  bool first_expr = true;
1156  while (*t != 'E') {
1157  const char *t1 = parse_expression(t, last, db);
1158  if (t1 == t || t1 == last)
1159  return first;
1160  if (db.names.empty())
1161  return first;
1162  auto tmp = db.names.back().move_full();
1163  db.names.pop_back();
1164  if (!tmp.empty()) {
1165  if (db.names.empty())
1166  return first;
1167  if (!first_expr) {
1168  db.names.back().first.append(", ");
1169  first_expr = false;
1170  }
1171  db.names.back().first.append(tmp);
1172  }
1173  t = t1;
1174  }
1175  ++t;
1176  if (db.names.empty())
1177  return first;
1178  db.names.back().first.append(")");
1179  first = t;
1180  }
1181  }
1182  return first;
1183 }
1184 
1185 // [gs] nw <expression>* _ <type> E # new (expr-list) type
1186 // [gs] nw <expression>* _ <type> <initializer> # new (expr-list) type
1187 // (init)
1188 // [gs] na <expression>* _ <type> E # new[] (expr-list) type
1189 // [gs] na <expression>* _ <type> <initializer> # new[] (expr-list) type
1190 // (init)
1191 // <initializer> ::= pi <expression>* E # parenthesized
1192 // initialization
1193 
1194 template <class C>
1195 static const char *parse_new_expr(const char *first, const char *last, C &db) {
1196  if (last - first >= 4) {
1197  const char *t = first;
1198  bool parsed_gs = false;
1199  if (t[0] == 'g' && t[1] == 's') {
1200  t += 2;
1201  parsed_gs = true;
1202  }
1203  if (t[0] == 'n' && (t[1] == 'w' || t[1] == 'a')) {
1204  bool is_array = t[1] == 'a';
1205  t += 2;
1206  if (t == last)
1207  return first;
1208  bool has_expr_list = false;
1209  bool first_expr = true;
1210  while (*t != '_') {
1211  const char *t1 = parse_expression(t, last, db);
1212  if (t1 == t || t1 == last)
1213  return first;
1214  has_expr_list = true;
1215  if (!first_expr) {
1216  if (db.names.empty())
1217  return first;
1218  auto tmp = db.names.back().move_full();
1219  db.names.pop_back();
1220  if (!tmp.empty()) {
1221  if (db.names.empty())
1222  return first;
1223  db.names.back().first.append(", ");
1224  db.names.back().first.append(tmp);
1225  first_expr = false;
1226  }
1227  }
1228  t = t1;
1229  }
1230  ++t;
1231  const char *t1 = parse_type(t, last, db);
1232  if (t1 == t || t1 == last)
1233  return first;
1234  t = t1;
1235  bool has_init = false;
1236  if (last - t >= 3 && t[0] == 'p' && t[1] == 'i') {
1237  t += 2;
1238  has_init = true;
1239  first_expr = true;
1240  while (*t != 'E') {
1241  t1 = parse_expression(t, last, db);
1242  if (t1 == t || t1 == last)
1243  return first;
1244  if (!first_expr) {
1245  if (db.names.empty())
1246  return first;
1247  auto tmp = db.names.back().move_full();
1248  db.names.pop_back();
1249  if (!tmp.empty()) {
1250  if (db.names.empty())
1251  return first;
1252  db.names.back().first.append(", ");
1253  db.names.back().first.append(tmp);
1254  first_expr = false;
1255  }
1256  }
1257  t = t1;
1258  }
1259  }
1260  if (*t != 'E')
1261  return first;
1262  std::string init_list;
1263  if (has_init) {
1264  if (db.names.empty())
1265  return first;
1266  init_list = db.names.back().move_full();
1267  db.names.pop_back();
1268  }
1269  if (db.names.empty())
1270  return first;
1271  auto type = db.names.back().move_full();
1272  db.names.pop_back();
1273  std::string expr_list;
1274  if (has_expr_list) {
1275  if (db.names.empty())
1276  return first;
1277  expr_list = db.names.back().move_full();
1278  db.names.pop_back();
1279  }
1280  std::string r;
1281  if (parsed_gs)
1282  r = "::";
1283  if (is_array)
1284  r += "[] ";
1285  else
1286  r += " ";
1287  if (has_expr_list)
1288  r += "(" + expr_list + ") ";
1289  r += type;
1290  if (has_init)
1291  r += " (" + init_list + ")";
1292  db.names.push_back(std::move(r));
1293  first = t + 1;
1294  }
1295  }
1296  return first;
1297 }
1298 
1299 // cv <type> <expression> # conversion with one
1300 // argument
1301 // cv <type> _ <expression>* E # conversion with a
1302 // different number of arguments
1303 
1304 template <class C>
1305 static const char *parse_conversion_expr(const char *first, const char *last,
1306  C &db) {
1307  if (last - first >= 3 && first[0] == 'c' && first[1] == 'v') {
1308  bool try_to_parse_template_args = db.try_to_parse_template_args;
1309  db.try_to_parse_template_args = false;
1310  const char *t = parse_type(first + 2, last, db);
1311  db.try_to_parse_template_args = try_to_parse_template_args;
1312  if (t != first + 2 && t != last) {
1313  if (*t != '_') {
1314  const char *t1 = parse_expression(t, last, db);
1315  if (t1 == t)
1316  return first;
1317  t = t1;
1318  } else {
1319  ++t;
1320  if (t == last)
1321  return first;
1322  if (*t == 'E')
1323  db.names.emplace_back();
1324  else {
1325  bool first_expr = true;
1326  while (*t != 'E') {
1327  const char *t1 = parse_expression(t, last, db);
1328  if (t1 == t || t1 == last)
1329  return first;
1330  if (!first_expr) {
1331  if (db.names.empty())
1332  return first;
1333  auto tmp = db.names.back().move_full();
1334  db.names.pop_back();
1335  if (!tmp.empty()) {
1336  if (db.names.empty())
1337  return first;
1338  db.names.back().first.append(", ");
1339  db.names.back().first.append(tmp);
1340  first_expr = false;
1341  }
1342  }
1343  t = t1;
1344  }
1345  }
1346  ++t;
1347  }
1348  if (db.names.size() < 2)
1349  return first;
1350  auto tmp = db.names.back().move_full();
1351  db.names.pop_back();
1352  db.names.back() = "(" + db.names.back().move_full() + ")(" + tmp + ")";
1353  first = t;
1354  }
1355  }
1356  return first;
1357 }
1358 
1359 // pt <expression> <expression> # expr->name
1360 
1361 template <class C>
1362 static const char *parse_arrow_expr(const char *first, const char *last,
1363  C &db) {
1364  if (last - first >= 3 && first[0] == 'p' && first[1] == 't') {
1365  const char *t = parse_expression(first + 2, last, db);
1366  if (t != first + 2) {
1367  const char *t1 = parse_expression(t, last, db);
1368  if (t1 != t) {
1369  if (db.names.size() < 2)
1370  return first;
1371  auto tmp = db.names.back().move_full();
1372  db.names.pop_back();
1373  db.names.back().first += "->";
1374  db.names.back().first += tmp;
1375  first = t1;
1376  }
1377  }
1378  }
1379  return first;
1380 }
1381 
1382 // <ref-qualifier> ::= R # & ref-qualifier
1383 // <ref-qualifier> ::= O # && ref-qualifier
1384 
1385 // <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
1386 
1387 template <class C>
1388 static const char *parse_function_type(const char *first, const char *last,
1389  C &db) {
1390  if (first != last && *first == 'F') {
1391  const char *t = first + 1;
1392  if (t != last) {
1393  if (*t == 'Y') {
1394  /* extern "C" */
1395  if (++t == last)
1396  return first;
1397  }
1398  const char *t1 = parse_type(t, last, db);
1399  if (t1 != t) {
1400  t = t1;
1401  std::string sig("(");
1402  int ref_qual = 0;
1403  while (true) {
1404  if (t == last) {
1405  if (!db.names.empty())
1406  db.names.pop_back();
1407  return first;
1408  }
1409  if (*t == 'E') {
1410  ++t;
1411  break;
1412  }
1413  if (*t == 'v') {
1414  ++t;
1415  continue;
1416  }
1417  if (*t == 'R' && t + 1 != last && t[1] == 'E') {
1418  ref_qual = 1;
1419  ++t;
1420  continue;
1421  }
1422  if (*t == 'O' && t + 1 != last && t[1] == 'E') {
1423  ref_qual = 2;
1424  ++t;
1425  continue;
1426  }
1427  size_t k0 = db.names.size();
1428  t1 = parse_type(t, last, db);
1429  size_t k1 = db.names.size();
1430  if (t1 == t || t1 == last)
1431  return first;
1432  for (size_t k = k0; k < k1; ++k) {
1433  if (sig.size() > 1)
1434  sig += ", ";
1435  sig += db.names[k].move_full();
1436  }
1437  for (size_t k = k0; k < k1; ++k)
1438  db.names.pop_back();
1439  t = t1;
1440  }
1441  sig += ")";
1442  switch (ref_qual) {
1443  case 1:
1444  sig += " &";
1445  break;
1446  case 2:
1447  sig += " &&";
1448  break;
1449  }
1450  if (db.names.empty())
1451  return first;
1452  db.names.back().first += " ";
1453  db.names.back().second.insert(0, sig);
1454  first = t;
1455  }
1456  }
1457  }
1458  return first;
1459 }
1460 
1461 // <pointer-to-member-type> ::= M <class type> <member type>
1462 
1463 template <class C>
1464 static const char *parse_pointer_to_member_type(const char *first,
1465  const char *last, C &db) {
1466  if (first != last && *first == 'M') {
1467  const char *t = parse_type(first + 1, last, db);
1468  if (t != first + 1) {
1469  const char *t2 = parse_type(t, last, db);
1470  if (t2 != t) {
1471  if (db.names.size() < 2)
1472  return first;
1473  auto func = std::move(db.names.back());
1474  db.names.pop_back();
1475  auto class_type = std::move(db.names.back());
1476  if (!func.second.empty() && func.second.front() == '(') {
1477  db.names.back().first =
1478  std::move(func.first) + "(" + class_type.move_full() + "::*";
1479  db.names.back().second = ")" + std::move(func.second);
1480  } else {
1481  db.names.back().first =
1482  std::move(func.first) + " " + class_type.move_full() + "::*";
1483  db.names.back().second = std::move(func.second);
1484  }
1485  first = t2;
1486  }
1487  }
1488  }
1489  return first;
1490 }
1491 
1492 // <array-type> ::= A <positive dimension number> _ <element type>
1493 // ::= A [<dimension expression>] _ <element type>
1494 
1495 template <class C>
1496 static const char *parse_array_type(const char *first, const char *last,
1497  C &db) {
1498  if (first != last && *first == 'A' && first + 1 != last) {
1499  if (first[1] == '_') {
1500  const char *t = parse_type(first + 2, last, db);
1501  if (t != first + 2) {
1502  if (db.names.empty())
1503  return first;
1504  if (db.names.back().second.substr(0, 2) == " [")
1505  db.names.back().second.erase(0, 1);
1506  db.names.back().second.insert(0, " []");
1507  first = t;
1508  }
1509  } else if ('1' <= first[1] && first[1] <= '9') {
1510  const char *t = parse_number(first + 1, last);
1511  if (t != last && *t == '_') {
1512  const char *t2 = parse_type(t + 1, last, db);
1513  if (t2 != t + 1) {
1514  if (db.names.empty())
1515  return first;
1516  if (db.names.back().second.substr(0, 2) == " [")
1517  db.names.back().second.erase(0, 1);
1518  db.names.back().second.insert(0,
1519  " [" + std::string(first + 1, t) + "]");
1520  first = t2;
1521  }
1522  }
1523  } else {
1524  const char *t = parse_expression(first + 1, last, db);
1525  if (t != first + 1 && t != last && *t == '_') {
1526  const char *t2 = parse_type(++t, last, db);
1527  if (t2 != t) {
1528  if (db.names.size() < 2)
1529  return first;
1530  auto type = std::move(db.names.back());
1531  db.names.pop_back();
1532  auto expr = std::move(db.names.back());
1533  db.names.back().first = std::move(type.first);
1534  if (type.second.substr(0, 2) == " [")
1535  type.second.erase(0, 1);
1536  db.names.back().second =
1537  " [" + expr.move_full() + "]" + std::move(type.second);
1538  first = t2;
1539  }
1540  }
1541  }
1542  }
1543  return first;
1544 }
1545 
1546 // <decltype> ::= Dt <expression> E # decltype of an id-expression or class
1547 // member access (C++0x)
1548 // ::= DT <expression> E # decltype of an expression (C++0x)
1549 
1550 template <class C>
1551 static const char *parse_decltype(const char *first, const char *last, C &db) {
1552  if (last - first >= 4 && first[0] == 'D') {
1553  switch (first[1]) {
1554  case 't':
1555  case 'T': {
1556  const char *t = parse_expression(first + 2, last, db);
1557  if (t != first + 2 && t != last && *t == 'E') {
1558  if (db.names.empty())
1559  return first;
1560  db.names.back() = "decltype(" + db.names.back().move_full() + ")";
1561  first = t + 1;
1562  }
1563  } break;
1564  }
1565  }
1566  return first;
1567 }
1568 
1569 // extension:
1570 // <vector-type> ::= Dv <positive dimension number> _
1571 // <extended element type>
1572 // ::= Dv [<dimension expression>] _ <element type>
1573 // <extended element type> ::= <element type>
1574 // ::= p # AltiVec vector pixel
1575 
1576 template <class C>
1577 static const char *parse_vector_type(const char *first, const char *last,
1578  C &db) {
1579  if (last - first > 3 && first[0] == 'D' && first[1] == 'v') {
1580  if ('1' <= first[2] && first[2] <= '9') {
1581  const char *t = parse_number(first + 2, last);
1582  if (t == last || *t != '_')
1583  return first;
1584  const char *num = first + 2;
1585  size_t sz = static_cast<size_t>(t - num);
1586  if (++t != last) {
1587  if (*t != 'p') {
1588  const char *t1 = parse_type(t, last, db);
1589  if (t1 != t) {
1590  if (db.names.empty())
1591  return first;
1592  db.names.back().first += " vector[" + std::string(num, sz) + "]";
1593  first = t1;
1594  }
1595  } else {
1596  ++t;
1597  db.names.push_back("pixel vector[" + std::string(num, sz) + "]");
1598  first = t;
1599  }
1600  }
1601  } else {
1602  std::string num;
1603  const char *t1 = first + 2;
1604  if (*t1 != '_') {
1605  const char *t = parse_expression(t1, last, db);
1606  if (t != t1) {
1607  if (db.names.empty())
1608  return first;
1609  num = db.names.back().move_full();
1610  db.names.pop_back();
1611  t1 = t;
1612  }
1613  }
1614  if (t1 != last && *t1 == '_' && ++t1 != last) {
1615  const char *t = parse_type(t1, last, db);
1616  if (t != t1) {
1617  if (db.names.empty())
1618  return first;
1619  db.names.back().first += " vector[" + num + "]";
1620  first = t;
1621  }
1622  }
1623  }
1624  }
1625  return first;
1626 }
1627 
1628 // <type> ::= <builtin-type>
1629 // ::= <function-type>
1630 // ::= <class-enum-type>
1631 // ::= <array-type>
1632 // ::= <pointer-to-member-type>
1633 // ::= <template-param>
1634 // ::= <template-template-param> <template-args>
1635 // ::= <decltype>
1636 // ::= <substitution>
1637 // ::= <CV-qualifiers> <type>
1638 // ::= P <type> # pointer-to
1639 // ::= R <type> # reference-to
1640 // ::= O <type> # rvalue reference-to (C++0x)
1641 // ::= C <type> # complex pair (C 2000)
1642 // ::= G <type> # imaginary (C 2000)
1643 // ::= Dp <type> # pack expansion (C++0x)
1644 // ::= U <source-name> <type> # vendor extended type qualifier
1645 // extension := U <objc-name> <objc-type> # objc-type<identifier>
1646 // extension := <vector-type> # <vector-type> starts with Dv
1647 
1648 // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier> # k0 = 9 +
1649 // <number of digits in k1> + k1
1650 // <objc-type> := <source-name> # PU<11+>objcproto 11objc_object<source-name>
1651 // 11objc_object -> id<source-name>
1652 
1653 template <class C>
1654 static const char *parse_type(const char *first, const char *last, C &db) {
1655  if (first != last) {
1656  switch (*first) {
1657  case 'r':
1658  case 'V':
1659  case 'K': {
1660  unsigned cv = 0;
1661  const char *t = parse_cv_qualifiers(first, last, cv);
1662  if (t != first) {
1663  bool is_function = *t == 'F';
1664  size_t k0 = db.names.size();
1665  const char *t1 = parse_type(t, last, db);
1666  size_t k1 = db.names.size();
1667  if (t1 != t) {
1668  if (is_function)
1669  db.subs.pop_back();
1670  db.subs.emplace_back();
1671  for (size_t k = k0; k < k1; ++k) {
1672  if (is_function) {
1673  auto &name = db.names[k].second;
1674  size_t p = name.size();
1675 
1676  if (name[p - 2] == '&' && name[p - 1] == '&')
1677  p -= 2;
1678  else if (name.back() == '&')
1679  p -= 1;
1680 
1681  if (cv & CV_const) {
1682  name.insert(p, " const");
1683  p += 6;
1684  }
1685  if (cv & CV_volatile) {
1686  name.insert(p, " volatile");
1687  p += 9;
1688  }
1689  if (cv & CV_restrict)
1690  name.insert(p, " restrict");
1691  } else {
1692  if (cv & CV_const)
1693  db.names[k].first.append(" const");
1694  if (cv & CV_volatile)
1695  db.names[k].first.append(" volatile");
1696  if (cv & CV_restrict)
1697  db.names[k].first.append(" restrict");
1698  }
1699  db.subs.back().push_back(db.names[k]);
1700  }
1701  first = t1;
1702  }
1703  }
1704  } break;
1705  default: {
1706  const char *t = parse_builtin_type(first, last, db);
1707  if (t != first) {
1708  first = t;
1709  } else {
1710  switch (*first) {
1711  case 'A':
1712  t = parse_array_type(first, last, db);
1713  if (t != first) {
1714  if (db.names.empty())
1715  return first;
1716  first = t;
1717  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1718  }
1719  break;
1720  case 'C':
1721  t = parse_type(first + 1, last, db);
1722  if (t != first + 1) {
1723  if (db.names.empty())
1724  return first;
1725  db.names.back().first.append(" complex");
1726  first = t;
1727  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1728  }
1729  break;
1730  case 'F':
1731  t = parse_function_type(first, last, db);
1732  if (t != first) {
1733  if (db.names.empty())
1734  return first;
1735  first = t;
1736  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1737  }
1738  break;
1739  case 'G':
1740  t = parse_type(first + 1, last, db);
1741  if (t != first + 1) {
1742  if (db.names.empty())
1743  return first;
1744  db.names.back().first.append(" imaginary");
1745  first = t;
1746  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1747  }
1748  break;
1749  case 'M':
1750  t = parse_pointer_to_member_type(first, last, db);
1751  if (t != first) {
1752  if (db.names.empty())
1753  return first;
1754  first = t;
1755  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1756  }
1757  break;
1758  case 'O': {
1759  size_t k0 = db.names.size();
1760  t = parse_type(first + 1, last, db);
1761  size_t k1 = db.names.size();
1762  if (t != first + 1) {
1763  db.subs.emplace_back();
1764  for (size_t k = k0; k < k1; ++k) {
1765  if (db.names[k].second.substr(0, 2) == " [") {
1766  db.names[k].first += " (";
1767  db.names[k].second.insert(0, ")");
1768  } else if (!db.names[k].second.empty() &&
1769  db.names[k].second.front() == '(') {
1770  db.names[k].first += "(";
1771  db.names[k].second.insert(0, ")");
1772  }
1773  db.names[k].first.append("&&");
1774  db.subs.back().push_back(db.names[k]);
1775  }
1776  first = t;
1777  }
1778  break;
1779  }
1780  case 'P': {
1781  size_t k0 = db.names.size();
1782  t = parse_type(first + 1, last, db);
1783  size_t k1 = db.names.size();
1784  if (t != first + 1) {
1785  db.subs.emplace_back();
1786  for (size_t k = k0; k < k1; ++k) {
1787  if (db.names[k].second.substr(0, 2) == " [") {
1788  db.names[k].first += " (";
1789  db.names[k].second.insert(0, ")");
1790  } else if (!db.names[k].second.empty() &&
1791  db.names[k].second.front() == '(') {
1792  db.names[k].first += "(";
1793  db.names[k].second.insert(0, ")");
1794  }
1795  if (first[1] != 'U' ||
1796  db.names[k].first.substr(0, 12) != "objc_object<") {
1797  db.names[k].first.append("*");
1798  } else {
1799  db.names[k].first.replace(0, 11, "id");
1800  }
1801  db.subs.back().push_back(db.names[k]);
1802  }
1803  first = t;
1804  }
1805  break;
1806  }
1807  case 'R': {
1808  size_t k0 = db.names.size();
1809  t = parse_type(first + 1, last, db);
1810  size_t k1 = db.names.size();
1811  if (t != first + 1) {
1812  db.subs.emplace_back();
1813  for (size_t k = k0; k < k1; ++k) {
1814  if (db.names[k].second.substr(0, 2) == " [") {
1815  db.names[k].first += " (";
1816  db.names[k].second.insert(0, ")");
1817  } else if (!db.names[k].second.empty() &&
1818  db.names[k].second.front() == '(') {
1819  db.names[k].first += "(";
1820  db.names[k].second.insert(0, ")");
1821  }
1822  db.names[k].first.append("&");
1823  db.subs.back().push_back(db.names[k]);
1824  }
1825  first = t;
1826  }
1827  break;
1828  }
1829  case 'T': {
1830  size_t k0 = db.names.size();
1831  t = parse_template_param(first, last, db);
1832  size_t k1 = db.names.size();
1833  if (t != first) {
1834  db.subs.emplace_back();
1835  for (size_t k = k0; k < k1; ++k)
1836  db.subs.back().push_back(db.names[k]);
1837  if (db.try_to_parse_template_args && k1 == k0 + 1) {
1838  const char *t1 = parse_template_args(t, last, db);
1839  if (t1 != t) {
1840  auto args = db.names.back().move_full();
1841  db.names.pop_back();
1842  db.names.back().first += std::move(args);
1843  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1844  t = t1;
1845  }
1846  }
1847  first = t;
1848  }
1849  break;
1850  }
1851  case 'U':
1852  if (first + 1 != last) {
1853  t = parse_source_name(first + 1, last, db);
1854  if (t != first + 1) {
1855  const char *t2 = parse_type(t, last, db);
1856  if (t2 != t) {
1857  if (db.names.size() < 2)
1858  return first;
1859  auto type = db.names.back().move_full();
1860  db.names.pop_back();
1861  if (db.names.back().first.substr(0, 9) != "objcproto") {
1862  db.names.back() = type + " " + db.names.back().move_full();
1863  } else {
1864  auto proto = db.names.back().move_full();
1865  db.names.pop_back();
1866  t = parse_source_name(proto.data() + 9,
1867  proto.data() + proto.size(), db);
1868  if (t != proto.data() + 9) {
1869  db.names.back() =
1870  type + "<" + db.names.back().move_full() + ">";
1871  } else {
1872  db.names.push_back(type + " " + proto);
1873  }
1874  }
1875  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1876  first = t2;
1877  }
1878  }
1879  }
1880  break;
1881  case 'S':
1882  if (first + 1 != last && first[1] == 't') {
1883  t = parse_name(first, last, db);
1884  if (t != first) {
1885  if (db.names.empty())
1886  return first;
1887  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1888  first = t;
1889  }
1890  } else {
1891  t = parse_substitution(first, last, db);
1892  if (t != first) {
1893  first = t;
1894  // Parsed a substitution. If the substitution is a
1895  // <template-param> it might be followed by <template-args>.
1896  t = parse_template_args(first, last, db);
1897  if (t != first) {
1898  if (db.names.size() < 2)
1899  return first;
1900  auto template_args = db.names.back().move_full();
1901  db.names.pop_back();
1902  db.names.back().first += template_args;
1903  // Need to create substitution for <template-template-param>
1904  // <template-args>
1905  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1906  first = t;
1907  }
1908  }
1909  }
1910  break;
1911  case 'D':
1912  if (first + 1 != last) {
1913  switch (first[1]) {
1914  case 'p': {
1915  size_t k0 = db.names.size();
1916  t = parse_type(first + 2, last, db);
1917  size_t k1 = db.names.size();
1918  if (t != first + 2) {
1919  db.subs.emplace_back();
1920  for (size_t k = k0; k < k1; ++k)
1921  db.subs.back().push_back(db.names[k]);
1922  first = t;
1923  return first;
1924  }
1925  break;
1926  }
1927  case 't':
1928  case 'T':
1929  t = parse_decltype(first, last, db);
1930  if (t != first) {
1931  if (db.names.empty())
1932  return first;
1933  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1934  first = t;
1935  return first;
1936  }
1937  break;
1938  case 'v':
1939  t = parse_vector_type(first, last, db);
1940  if (t != first) {
1941  if (db.names.empty())
1942  return first;
1943  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1944  first = t;
1945  return first;
1946  }
1947  break;
1948  }
1949  }
1950  // falls through
1951  default:
1952  // must check for builtin-types before class-enum-types to avoid
1953  // ambiguities with operator-names
1954  t = parse_builtin_type(first, last, db);
1955  if (t != first) {
1956  first = t;
1957  } else {
1958  t = parse_name(first, last, db);
1959  if (t != first) {
1960  if (db.names.empty())
1961  return first;
1962  db.subs.push_back(typename C::sub_type(1, db.names.back()));
1963  first = t;
1964  }
1965  }
1966  break;
1967  }
1968  }
1969  break;
1970  }
1971  }
1972  }
1973  return first;
1974 }
1975 
1976 // <operator-name>
1977 // ::= aa # &&
1978 // ::= ad # & (unary)
1979 // ::= an # &
1980 // ::= aN # &=
1981 // ::= aS # =
1982 // ::= cl # ()
1983 // ::= cm # ,
1984 // ::= co # ~
1985 // ::= cv <type> # (cast)
1986 // ::= da # delete[]
1987 // ::= de # * (unary)
1988 // ::= dl # delete
1989 // ::= dv # /
1990 // ::= dV # /=
1991 // ::= eo # ^
1992 // ::= eO # ^=
1993 // ::= eq # ==
1994 // ::= ge # >=
1995 // ::= gt # >
1996 // ::= ix # []
1997 // ::= le # <=
1998 // ::= li <source-name> # operator ""
1999 // ::= ls # <<
2000 // ::= lS # <<=
2001 // ::= lt # <
2002 // ::= mi # -
2003 // ::= mI # -=
2004 // ::= ml # *
2005 // ::= mL # *=
2006 // ::= mm # -- (postfix in <expression> context)
2007 // ::= na # new[]
2008 // ::= ne # !=
2009 // ::= ng # - (unary)
2010 // ::= nt # !
2011 // ::= nw # new
2012 // ::= oo # ||
2013 // ::= or # |
2014 // ::= oR # |=
2015 // ::= pm # ->*
2016 // ::= pl # +
2017 // ::= pL # +=
2018 // ::= pp # ++ (postfix in <expression> context)
2019 // ::= ps # + (unary)
2020 // ::= pt # ->
2021 // ::= qu # ?
2022 // ::= rm # %
2023 // ::= rM # %=
2024 // ::= rs # >>
2025 // ::= rS # >>=
2026 // ::= v <digit> <source-name> # vendor extended
2027 // operator
2028 
2029 template <class C>
2030 static const char *parse_operator_name(const char *first, const char *last,
2031  C &db) {
2032  if (last - first >= 2) {
2033  switch (first[0]) {
2034  case 'a':
2035  switch (first[1]) {
2036  case 'a':
2037  db.names.push_back("operator&&");
2038  first += 2;
2039  break;
2040  case 'd':
2041  case 'n':
2042  db.names.push_back("operator&");
2043  first += 2;
2044  break;
2045  case 'N':
2046  db.names.push_back("operator&=");
2047  first += 2;
2048  break;
2049  case 'S':
2050  db.names.push_back("operator=");
2051  first += 2;
2052  break;
2053  }
2054  break;
2055  case 'c':
2056  switch (first[1]) {
2057  case 'l':
2058  db.names.push_back("operator()");
2059  first += 2;
2060  break;
2061  case 'm':
2062  db.names.push_back("operator,");
2063  first += 2;
2064  break;
2065  case 'o':
2066  db.names.push_back("operator~");
2067  first += 2;
2068  break;
2069  case 'v': {
2070  bool try_to_parse_template_args = db.try_to_parse_template_args;
2071  db.try_to_parse_template_args = false;
2072  const char *t = parse_type(first + 2, last, db);
2073  db.try_to_parse_template_args = try_to_parse_template_args;
2074  if (t != first + 2) {
2075  if (db.names.empty())
2076  return first;
2077  db.names.back().first.insert(0, "operator ");
2078  db.parsed_ctor_dtor_cv = true;
2079  first = t;
2080  }
2081  } break;
2082  }
2083  break;
2084  case 'd':
2085  switch (first[1]) {
2086  case 'a':
2087  db.names.push_back("operator delete[]");
2088  first += 2;
2089  break;
2090  case 'e':
2091  db.names.push_back("operator*");
2092  first += 2;
2093  break;
2094  case 'l':
2095  db.names.push_back("operator delete");
2096  first += 2;
2097  break;
2098  case 'v':
2099  db.names.push_back("operator/");
2100  first += 2;
2101  break;
2102  case 'V':
2103  db.names.push_back("operator/=");
2104  first += 2;
2105  break;
2106  }
2107  break;
2108  case 'e':
2109  switch (first[1]) {
2110  case 'o':
2111  db.names.push_back("operator^");
2112  first += 2;
2113  break;
2114  case 'O':
2115  db.names.push_back("operator^=");
2116  first += 2;
2117  break;
2118  case 'q':
2119  db.names.push_back("operator==");
2120  first += 2;
2121  break;
2122  }
2123  break;
2124  case 'g':
2125  switch (first[1]) {
2126  case 'e':
2127  db.names.push_back("operator>=");
2128  first += 2;
2129  break;
2130  case 't':
2131  db.names.push_back("operator>");
2132  first += 2;
2133  break;
2134  }
2135  break;
2136  case 'i':
2137  if (first[1] == 'x') {
2138  db.names.push_back("operator[]");
2139  first += 2;
2140  }
2141  break;
2142  case 'l':
2143  switch (first[1]) {
2144  case 'e':
2145  db.names.push_back("operator<=");
2146  first += 2;
2147  break;
2148  case 'i': {
2149  const char *t = parse_source_name(first + 2, last, db);
2150  if (t != first + 2) {
2151  if (db.names.empty())
2152  return first;
2153  db.names.back().first.insert(0, "operator\"\" ");
2154  first = t;
2155  }
2156  } break;
2157  case 's':
2158  db.names.push_back("operator<<");
2159  first += 2;
2160  break;
2161  case 'S':
2162  db.names.push_back("operator<<=");
2163  first += 2;
2164  break;
2165  case 't':
2166  db.names.push_back("operator<");
2167  first += 2;
2168  break;
2169  }
2170  break;
2171  case 'm':
2172  switch (first[1]) {
2173  case 'i':
2174  db.names.push_back("operator-");
2175  first += 2;
2176  break;
2177  case 'I':
2178  db.names.push_back("operator-=");
2179  first += 2;
2180  break;
2181  case 'l':
2182  db.names.push_back("operator*");
2183  first += 2;
2184  break;
2185  case 'L':
2186  db.names.push_back("operator*=");
2187  first += 2;
2188  break;
2189  case 'm':
2190  db.names.push_back("operator--");
2191  first += 2;
2192  break;
2193  }
2194  break;
2195  case 'n':
2196  switch (first[1]) {
2197  case 'a':
2198  db.names.push_back("operator new[]");
2199  first += 2;
2200  break;
2201  case 'e':
2202  db.names.push_back("operator!=");
2203  first += 2;
2204  break;
2205  case 'g':
2206  db.names.push_back("operator-");
2207  first += 2;
2208  break;
2209  case 't':
2210  db.names.push_back("operator!");
2211  first += 2;
2212  break;
2213  case 'w':
2214  db.names.push_back("operator new");
2215  first += 2;
2216  break;
2217  }
2218  break;
2219  case 'o':
2220  switch (first[1]) {
2221  case 'o':
2222  db.names.push_back("operator||");
2223  first += 2;
2224  break;
2225  case 'r':
2226  db.names.push_back("operator|");
2227  first += 2;
2228  break;
2229  case 'R':
2230  db.names.push_back("operator|=");
2231  first += 2;
2232  break;
2233  }
2234  break;
2235  case 'p':
2236  switch (first[1]) {
2237  case 'm':
2238  db.names.push_back("operator->*");
2239  first += 2;
2240  break;
2241  case 'l':
2242  db.names.push_back("operator+");
2243  first += 2;
2244  break;
2245  case 'L':
2246  db.names.push_back("operator+=");
2247  first += 2;
2248  break;
2249  case 'p':
2250  db.names.push_back("operator++");
2251  first += 2;
2252  break;
2253  case 's':
2254  db.names.push_back("operator+");
2255  first += 2;
2256  break;
2257  case 't':
2258  db.names.push_back("operator->");
2259  first += 2;
2260  break;
2261  }
2262  break;
2263  case 'q':
2264  if (first[1] == 'u') {
2265  db.names.push_back("operator?");
2266  first += 2;
2267  }
2268  break;
2269  case 'r':
2270  switch (first[1]) {
2271  case 'm':
2272  db.names.push_back("operator%");
2273  first += 2;
2274  break;
2275  case 'M':
2276  db.names.push_back("operator%=");
2277  first += 2;
2278  break;
2279  case 's':
2280  db.names.push_back("operator>>");
2281  first += 2;
2282  break;
2283  case 'S':
2284  db.names.push_back("operator>>=");
2285  first += 2;
2286  break;
2287  }
2288  break;
2289  case 'v':
2290  if (std::isdigit(first[1])) {
2291  const char *t = parse_source_name(first + 2, last, db);
2292  if (t != first + 2) {
2293  if (db.names.empty())
2294  return first;
2295  db.names.back().first.insert(0, "operator ");
2296  first = t;
2297  }
2298  }
2299  break;
2300  }
2301  }
2302  return first;
2303 }
2304 
2305 template <class C>
2306 static const char *parse_integer_literal(const char *first, const char *last,
2307  const std::string &lit, C &db) {
2308  const char *t = parse_number(first, last);
2309  if (t != first && t != last && *t == 'E') {
2310  if (lit.size() > 3)
2311  db.names.push_back("(" + lit + ")");
2312  else
2313  db.names.emplace_back();
2314  if (*first == 'n') {
2315  db.names.back().first += '-';
2316  ++first;
2317  }
2318  db.names.back().first.append(first, t);
2319  if (lit.size() <= 3)
2320  db.names.back().first += lit;
2321  first = t + 1;
2322  }
2323  return first;
2324 }
2325 
2326 // <expr-primary> ::= L <type> <value number> E #
2327 // integer literal
2328 // ::= L <type> <value float> E #
2329 // floating literal
2330 // ::= L <string type> E #
2331 // string literal
2332 // ::= L <nullptr type> E #
2333 // nullptr literal (i.e., "LDnE")
2334 // ::= L <type> <real-part float> _ <imag-part float> E #
2335 // complex floating point literal (C 2000)
2336 // ::= L <mangled-name> E #
2337 // external name
2338 
2339 template <class C>
2340 static const char *parse_expr_primary(const char *first, const char *last,
2341  C &db) {
2342  if (last - first >= 4 && *first == 'L') {
2343  switch (first[1]) {
2344  case 'w': {
2345  const char *t = parse_integer_literal(first + 2, last, "wchar_t", db);
2346  if (t != first + 2)
2347  first = t;
2348  } break;
2349  case 'b':
2350  if (first[3] == 'E') {
2351  switch (first[2]) {
2352  case '0':
2353  db.names.push_back("false");
2354  first += 4;
2355  break;
2356  case '1':
2357  db.names.push_back("true");
2358  first += 4;
2359  break;
2360  }
2361  }
2362  break;
2363  case 'c': {
2364  const char *t = parse_integer_literal(first + 2, last, "char", db);
2365  if (t != first + 2)
2366  first = t;
2367  } break;
2368  case 'a': {
2369  const char *t = parse_integer_literal(first + 2, last, "signed char", db);
2370  if (t != first + 2)
2371  first = t;
2372  } break;
2373  case 'h': {
2374  const char *t =
2375  parse_integer_literal(first + 2, last, "unsigned char", db);
2376  if (t != first + 2)
2377  first = t;
2378  } break;
2379  case 's': {
2380  const char *t = parse_integer_literal(first + 2, last, "short", db);
2381  if (t != first + 2)
2382  first = t;
2383  } break;
2384  case 't': {
2385  const char *t =
2386  parse_integer_literal(first + 2, last, "unsigned short", db);
2387  if (t != first + 2)
2388  first = t;
2389  } break;
2390  case 'i': {
2391  const char *t = parse_integer_literal(first + 2, last, "", db);
2392  if (t != first + 2)
2393  first = t;
2394  } break;
2395  case 'j': {
2396  const char *t = parse_integer_literal(first + 2, last, "u", db);
2397  if (t != first + 2)
2398  first = t;
2399  } break;
2400  case 'l': {
2401  const char *t = parse_integer_literal(first + 2, last, "l", db);
2402  if (t != first + 2)
2403  first = t;
2404  } break;
2405  case 'm': {
2406  const char *t = parse_integer_literal(first + 2, last, "ul", db);
2407  if (t != first + 2)
2408  first = t;
2409  } break;
2410  case 'x': {
2411  const char *t = parse_integer_literal(first + 2, last, "ll", db);
2412  if (t != first + 2)
2413  first = t;
2414  } break;
2415  case 'y': {
2416  const char *t = parse_integer_literal(first + 2, last, "ull", db);
2417  if (t != first + 2)
2418  first = t;
2419  } break;
2420  case 'n': {
2421  const char *t = parse_integer_literal(first + 2, last, "__int128", db);
2422  if (t != first + 2)
2423  first = t;
2424  } break;
2425  case 'o': {
2426  const char *t =
2427  parse_integer_literal(first + 2, last, "unsigned __int128", db);
2428  if (t != first + 2)
2429  first = t;
2430  } break;
2431  case 'f': {
2432  const char *t = parse_floating_number<float>(first + 2, last, db);
2433  if (t != first + 2)
2434  first = t;
2435  } break;
2436  case 'd': {
2437  const char *t = parse_floating_number<double>(first + 2, last, db);
2438  if (t != first + 2)
2439  first = t;
2440  } break;
2441  case 'e': {
2442  const char *t = parse_floating_number<long double>(first + 2, last, db);
2443  if (t != first + 2)
2444  first = t;
2445  } break;
2446  case '_':
2447  if (first[2] == 'Z') {
2448  const char *t = parse_encoding(first + 3, last, db);
2449  if (t != first + 3 && t != last && *t == 'E')
2450  first = t + 1;
2451  }
2452  break;
2453  case 'T':
2454  // Invalid mangled name per
2455  // http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
2456  break;
2457  default: {
2458  // might be named type
2459  const char *t = parse_type(first + 1, last, db);
2460  if (t != first + 1 && t != last) {
2461  if (*t != 'E') {
2462  const char *n = t;
2463  for (; n != last && isdigit(*n); ++n)
2464  ;
2465  if (n != t && n != last && *n == 'E') {
2466  if (db.names.empty())
2467  return first;
2468  db.names.back() =
2469  "(" + db.names.back().move_full() + ")" + std::string(t, n);
2470  first = n + 1;
2471  break;
2472  }
2473  } else {
2474  first = t + 1;
2475  break;
2476  }
2477  }
2478  }
2479  }
2480  }
2481  return first;
2482 }
2483 
2484 static std::string base_name(std::string &s) {
2485  if (s.empty())
2486  return s;
2487  if (s == "std::string") {
2488  s = "std::basic_string<char, std::char_traits<char>, std::allocator<char> "
2489  ">";
2490  return "basic_string";
2491  }
2492  if (s == "std::istream") {
2493  s = "std::basic_istream<char, std::char_traits<char> >";
2494  return "basic_istream";
2495  }
2496  if (s == "std::ostream") {
2497  s = "std::basic_ostream<char, std::char_traits<char> >";
2498  return "basic_ostream";
2499  }
2500  if (s == "std::iostream") {
2501  s = "std::basic_iostream<char, std::char_traits<char> >";
2502  return "basic_iostream";
2503  }
2504  const char *const pf = s.data();
2505  const char *pe = pf + s.size();
2506  if (pe[-1] == '>') {
2507  unsigned c = 1;
2508  while (true) {
2509  if (--pe == pf)
2510  return std::string();
2511  if (pe[-1] == '<') {
2512  if (--c == 0) {
2513  --pe;
2514  break;
2515  }
2516  } else if (pe[-1] == '>')
2517  ++c;
2518  }
2519  }
2520  if (pe - pf <= 1)
2521  return std::string();
2522  const char *p0 = pe - 1;
2523  for (; p0 != pf; --p0) {
2524  if (*p0 == ':') {
2525  ++p0;
2526  break;
2527  }
2528  if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_') {
2529  return std::string();
2530  }
2531  }
2532  return std::string(p0, pe);
2533 }
2534 
2535 // <ctor-dtor-name> ::= C1 # complete object constructor
2536 // ::= C2 # base object constructor
2537 // ::= C3 # complete object allocating constructor
2538 // extension ::= C5 # ?
2539 // ::= D0 # deleting destructor
2540 // ::= D1 # complete object destructor
2541 // ::= D2 # base object destructor
2542 // extension ::= D5 # ?
2543 
2544 template <class C>
2545 static const char *parse_ctor_dtor_name(const char *first, const char *last,
2546  C &db) {
2547  if (last - first >= 2 && !db.names.empty()) {
2548  switch (first[0]) {
2549  case 'C':
2550  switch (first[1]) {
2551  case '1':
2552  case '2':
2553  case '3':
2554  case '5':
2555  if (db.names.empty())
2556  return first;
2557  db.names.push_back(base_name(db.names.back().first));
2558  first += 2;
2559  db.parsed_ctor_dtor_cv = true;
2560  break;
2561  }
2562  break;
2563  case 'D':
2564  switch (first[1]) {
2565  case '0':
2566  case '1':
2567  case '2':
2568  case '5':
2569  if (db.names.empty())
2570  return first;
2571  db.names.push_back("~" + base_name(db.names.back().first));
2572  first += 2;
2573  db.parsed_ctor_dtor_cv = true;
2574  break;
2575  }
2576  break;
2577  }
2578  }
2579  return first;
2580 }
2581 
2582 // <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
2583 // ::= <closure-type-name>
2584 //
2585 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
2586 //
2587 // <lambda-sig> ::= <parameter type>+ # Parameter types or "v" if the lambda
2588 // has no parameters
2589 
2590 template <class C>
2591 static const char *parse_unnamed_type_name(const char *first, const char *last,
2592  C &db) {
2593  if (last - first > 2 && first[0] == 'U') {
2594  char type = first[1];
2595  switch (type) {
2596  case 't': {
2597  db.names.push_back(std::string("'unnamed"));
2598  const char *t0 = first + 2;
2599  if (t0 == last) {
2600  db.names.pop_back();
2601  return first;
2602  }
2603  if (std::isdigit(*t0)) {
2604  const char *t1 = t0 + 1;
2605  while (t1 != last && std::isdigit(*t1))
2606  ++t1;
2607  db.names.back().first.append(t0, t1);
2608  t0 = t1;
2609  }
2610  db.names.back().first.push_back('\'');
2611  if (t0 == last || *t0 != '_') {
2612  db.names.pop_back();
2613  return first;
2614  }
2615  first = t0 + 1;
2616  } break;
2617  case 'l': {
2618  size_t lambda_pos = db.names.size();
2619  db.names.push_back(std::string("'lambda'("));
2620  const char *t0 = first + 2;
2621  if (first[2] == 'v') {
2622  db.names.back().first += ')';
2623  ++t0;
2624  } else {
2625  bool is_first_it = true;
2626  while (true) {
2627  long k0 = static_cast<long>(db.names.size());
2628  const char *t1 = parse_type(t0, last, db);
2629  long k1 = static_cast<long>(db.names.size());
2630  if (t1 == t0)
2631  break;
2632  if (k0 >= k1)
2633  return first;
2634  // If the call to parse_type above found a pack expansion
2635  // substitution, then multiple names could have been
2636  // inserted into the name table. Walk through the names,
2637  // appending each onto the lambda's parameter list.
2638  std::for_each(db.names.begin() + k0, db.names.begin() + k1,
2639  [&](typename C::sub_type::value_type &pair) {
2640  if (pair.empty())
2641  return;
2642  auto &lambda = db.names[lambda_pos].first;
2643  if (!is_first_it)
2644  lambda.append(", ");
2645  is_first_it = false;
2646  lambda.append(pair.move_full());
2647  });
2648  db.names.erase(db.names.begin() + k0, db.names.end());
2649  t0 = t1;
2650  }
2651  if (is_first_it) {
2652  if (!db.names.empty())
2653  db.names.pop_back();
2654  return first;
2655  }
2656  if (db.names.empty() || db.names.size() - 1 != lambda_pos)
2657  return first;
2658  db.names.back().first.append(")");
2659  }
2660  if (t0 == last || *t0 != 'E') {
2661  if (!db.names.empty())
2662  db.names.pop_back();
2663  return first;
2664  }
2665  ++t0;
2666  if (t0 == last) {
2667  if (!db.names.empty())
2668  db.names.pop_back();
2669  return first;
2670  }
2671  if (std::isdigit(*t0)) {
2672  const char *t1 = t0 + 1;
2673  while (t1 != last && std::isdigit(*t1))
2674  ++t1;
2675  db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1);
2676  t0 = t1;
2677  }
2678  if (t0 == last || *t0 != '_') {
2679  if (!db.names.empty())
2680  db.names.pop_back();
2681  return first;
2682  }
2683  first = t0 + 1;
2684  } break;
2685  }
2686  }
2687  return first;
2688 }
2689 
2690 // <unqualified-name> ::= <operator-name>
2691 // ::= <ctor-dtor-name>
2692 // ::= <source-name>
2693 // ::= <unnamed-type-name>
2694 
2695 template <class C>
2696 static const char *parse_unqualified_name(const char *first, const char *last,
2697  C &db) {
2698  if (first != last) {
2699  const char *t;
2700  switch (*first) {
2701  case 'C':
2702  case 'D':
2703  t = parse_ctor_dtor_name(first, last, db);
2704  if (t != first)
2705  first = t;
2706  break;
2707  case 'U':
2708  t = parse_unnamed_type_name(first, last, db);
2709  if (t != first)
2710  first = t;
2711  break;
2712  case '1':
2713  case '2':
2714  case '3':
2715  case '4':
2716  case '5':
2717  case '6':
2718  case '7':
2719  case '8':
2720  case '9':
2721  t = parse_source_name(first, last, db);
2722  if (t != first)
2723  first = t;
2724  break;
2725  default:
2726  t = parse_operator_name(first, last, db);
2727  if (t != first)
2728  first = t;
2729  break;
2730  };
2731  }
2732  return first;
2733 }
2734 
2735 // <unscoped-name> ::= <unqualified-name>
2736 // ::= St <unqualified-name> # ::std::
2737 // extension ::= StL<unqualified-name>
2738 
2739 template <class C>
2740 static const char *parse_unscoped_name(const char *first, const char *last,
2741  C &db) {
2742  if (last - first >= 2) {
2743  const char *t0 = first;
2744  bool St = false;
2745  if (first[0] == 'S' && first[1] == 't') {
2746  t0 += 2;
2747  St = true;
2748  if (t0 != last && *t0 == 'L')
2749  ++t0;
2750  }
2751  const char *t1 = parse_unqualified_name(t0, last, db);
2752  if (t1 != t0) {
2753  if (St) {
2754  if (db.names.empty())
2755  return first;
2756  db.names.back().first.insert(0, "std::");
2757  }
2758  first = t1;
2759  }
2760  }
2761  return first;
2762 }
2763 
2764 // at <type> # alignof (a type)
2765 
2766 template <class C>
2767 static const char *parse_alignof_type(const char *first, const char *last,
2768  C &db) {
2769  if (last - first >= 3 && first[0] == 'a' && first[1] == 't') {
2770  const char *t = parse_type(first + 2, last, db);
2771  if (t != first + 2) {
2772  if (db.names.empty())
2773  return first;
2774  db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2775  first = t;
2776  }
2777  }
2778  return first;
2779 }
2780 
2781 // az <expression> # alignof (a
2782 // expression)
2783 
2784 template <class C>
2785 static const char *parse_alignof_expr(const char *first, const char *last,
2786  C &db) {
2787  if (last - first >= 3 && first[0] == 'a' && first[1] == 'z') {
2788  const char *t = parse_expression(first + 2, last, db);
2789  if (t != first + 2) {
2790  if (db.names.empty())
2791  return first;
2792  db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2793  first = t;
2794  }
2795  }
2796  return first;
2797 }
2798 
2799 template <class C>
2800 static const char *parse_noexcept_expression(const char *first,
2801  const char *last, C &db) {
2802  const char *t1 = parse_expression(first, last, db);
2803  if (t1 != first) {
2804  if (db.names.empty())
2805  return first;
2806  db.names.back().first = "noexcept (" + db.names.back().move_full() + ")";
2807  first = t1;
2808  }
2809  return first;
2810 }
2811 
2812 template <class C>
2813 static const char *parse_prefix_expression(const char *first, const char *last,
2814  const std::string &op,
2815  C &db) {
2816  const char *t1 = parse_expression(first, last, db);
2817  if (t1 != first) {
2818  if (db.names.empty())
2819  return first;
2820  db.names.back().first = op + "(" + db.names.back().move_full() + ")";
2821  first = t1;
2822  }
2823  return first;
2824 }
2825 
2826 template <class C>
2827 static const char *parse_binary_expression(const char *first, const char *last,
2828  const std::string &op,
2829  C &db) {
2830  const char *t1 = parse_expression(first, last, db);
2831  if (t1 != first) {
2832  const char *t2 = parse_expression(t1, last, db);
2833  if (t2 != t1) {
2834  if (db.names.size() < 2)
2835  return first;
2836  auto op2 = db.names.back().move_full();
2837  db.names.pop_back();
2838  auto op1 = db.names.back().move_full();
2839  auto &nm = db.names.back().first;
2840  nm.clear();
2841  if (op == ">")
2842  nm += '(';
2843  nm += "(" + op1 + ") " + op + " (" + op2 + ")";
2844  if (op == ">")
2845  nm += ')';
2846  first = t2;
2847  } else if (!db.names.empty())
2848  db.names.pop_back();
2849  }
2850  return first;
2851 }
2852 
2853 // <expression> ::= <unary operator-name> <expression>
2854 // ::= <binary operator-name> <expression> <expression>
2855 // ::= <ternary operator-name> <expression> <expression>
2856 // <expression>
2857 // ::= cl <expression>+ E # call
2858 // ::= cv <type> <expression> #
2859 // conversion with one argument
2860 // ::= cv <type> _ <expression>* E #
2861 // conversion with a different number of arguments
2862 // ::= [gs] nw <expression>* _ <type> E # new
2863 // (expr-list) type
2864 // ::= [gs] nw <expression>* _ <type> <initializer> # new
2865 // (expr-list) type (init)
2866 // ::= [gs] na <expression>* _ <type> E # new[]
2867 // (expr-list) type
2868 // ::= [gs] na <expression>* _ <type> <initializer> # new[]
2869 // (expr-list) type (init)
2870 // ::= [gs] dl <expression> #
2871 // delete expression
2872 // ::= [gs] da <expression> #
2873 // delete[] expression
2874 // ::= pp_ <expression> #
2875 // prefix ++
2876 // ::= mm_ <expression> #
2877 // prefix --
2878 // ::= ti <type> #
2879 // typeid (type)
2880 // ::= te <expression> #
2881 // typeid (expression)
2882 // ::= dc <type> <expression> #
2883 // dynamic_cast<type> (expression)
2884 // ::= sc <type> <expression> #
2885 // static_cast<type> (expression)
2886 // ::= cc <type> <expression> #
2887 // const_cast<type> (expression)
2888 // ::= rc <type> <expression> #
2889 // reinterpret_cast<type> (expression)
2890 // ::= st <type> #
2891 // sizeof (a type)
2892 // ::= sz <expression> #
2893 // sizeof (an expression)
2894 // ::= at <type> #
2895 // alignof (a type)
2896 // ::= az <expression> #
2897 // alignof (an expression)
2898 // ::= nx <expression> #
2899 // noexcept (expression)
2900 // ::= <template-param>
2901 // ::= <function-param>
2902 // ::= dt <expression> <unresolved-name> #
2903 // expr.name
2904 // ::= pt <expression> <unresolved-name> #
2905 // expr->name
2906 // ::= ds <expression> <expression> #
2907 // expr.*expr
2908 // ::= sZ <template-param> # size
2909 // of a parameter pack
2910 // ::= sZ <function-param> # size
2911 // of a function parameter pack
2912 // ::= sp <expression> # pack
2913 // expansion
2914 // ::= tw <expression> # throw
2915 // expression
2916 // ::= tr # throw
2917 // with no operand (rethrow)
2918 // ::= <unresolved-name> # f(p),
2919 // N::f(p), ::f(p),
2920 // #
2921 // freestanding
2922 // dependent
2923 // name
2924 // (e.g.,
2925 // T::x),
2926 // #
2927 // objectless
2928 // nonstatic
2929 // member
2930 // reference
2931 // ::= <expr-primary>
2932 
2933 template <class C>
2934 static const char *parse_expression(const char *first, const char *last,
2935  C &db) {
2936  if (last - first >= 2) {
2937  const char *t = first;
2938  bool parsed_gs = false;
2939  if (last - first >= 4 && t[0] == 'g' && t[1] == 's') {
2940  t += 2;
2941  parsed_gs = true;
2942  }
2943  switch (*t) {
2944  case 'L':
2945  first = parse_expr_primary(first, last, db);
2946  break;
2947  case 'T':
2948  first = parse_template_param(first, last, db);
2949  break;
2950  case 'f':
2951  first = parse_function_param(first, last, db);
2952  break;
2953  case 'a':
2954  switch (t[1]) {
2955  case 'a':
2956  t = parse_binary_expression(first + 2, last, "&&", db);
2957  if (t != first + 2)
2958  first = t;
2959  break;
2960  case 'd':
2961  t = parse_prefix_expression(first + 2, last, "&", db);
2962  if (t != first + 2)
2963  first = t;
2964  break;
2965  case 'n':
2966  t = parse_binary_expression(first + 2, last, "&", db);
2967  if (t != first + 2)
2968  first = t;
2969  break;
2970  case 'N':
2971  t = parse_binary_expression(first + 2, last, "&=", db);
2972  if (t != first + 2)
2973  first = t;
2974  break;
2975  case 'S':
2976  t = parse_binary_expression(first + 2, last, "=", db);
2977  if (t != first + 2)
2978  first = t;
2979  break;
2980  case 't':
2981  first = parse_alignof_type(first, last, db);
2982  break;
2983  case 'z':
2984  first = parse_alignof_expr(first, last, db);
2985  break;
2986  }
2987  break;
2988  case 'c':
2989  switch (t[1]) {
2990  case 'c':
2991  first = parse_const_cast_expr(first, last, db);
2992  break;
2993  case 'l':
2994  first = parse_call_expr(first, last, db);
2995  break;
2996  case 'm':
2997  t = parse_binary_expression(first + 2, last, ",", db);
2998  if (t != first + 2)
2999  first = t;
3000  break;
3001  case 'o':
3002  t = parse_prefix_expression(first + 2, last, "~", db);
3003  if (t != first + 2)
3004  first = t;
3005  break;
3006  case 'v':
3007  first = parse_conversion_expr(first, last, db);
3008  break;
3009  }
3010  break;
3011  case 'd':
3012  switch (t[1]) {
3013  case 'a': {
3014  const char *t1 = parse_expression(t + 2, last, db);
3015  if (t1 != t + 2) {
3016  if (db.names.empty())
3017  return first;
3018  db.names.back().first =
3019  (parsed_gs ? std::string("::") : std::string()) + "delete[] " +
3020  db.names.back().move_full();
3021  first = t1;
3022  }
3023  } break;
3024  case 'c':
3025  first = parse_dynamic_cast_expr(first, last, db);
3026  break;
3027  case 'e':
3028  t = parse_prefix_expression(first + 2, last, "*", db);
3029  if (t != first + 2)
3030  first = t;
3031  break;
3032  case 'l': {
3033  const char *t1 = parse_expression(t + 2, last, db);
3034  if (t1 != t + 2) {
3035  if (db.names.empty())
3036  return first;
3037  db.names.back().first =
3038  (parsed_gs ? std::string("::") : std::string()) + "delete " +
3039  db.names.back().move_full();
3040  first = t1;
3041  }
3042  } break;
3043  case 'n':
3044  return parse_unresolved_name(first, last, db);
3045  case 's':
3046  first = parse_dot_star_expr(first, last, db);
3047  break;
3048  case 't':
3049  first = parse_dot_expr(first, last, db);
3050  break;
3051  case 'v':
3052  t = parse_binary_expression(first + 2, last, "/", db);
3053  if (t != first + 2)
3054  first = t;
3055  break;
3056  case 'V':
3057  t = parse_binary_expression(first + 2, last, "/=", db);
3058  if (t != first + 2)
3059  first = t;
3060  break;
3061  }
3062  break;
3063  case 'e':
3064  switch (t[1]) {
3065  case 'o':
3066  t = parse_binary_expression(first + 2, last, "^", db);
3067  if (t != first + 2)
3068  first = t;
3069  break;
3070  case 'O':
3071  t = parse_binary_expression(first + 2, last, "^=", db);
3072  if (t != first + 2)
3073  first = t;
3074  break;
3075  case 'q':
3076  t = parse_binary_expression(first + 2, last, "==", db);
3077  if (t != first + 2)
3078  first = t;
3079  break;
3080  }
3081  break;
3082  case 'g':
3083  switch (t[1]) {
3084  case 'e':
3085  t = parse_binary_expression(first + 2, last, ">=", db);
3086  if (t != first + 2)
3087  first = t;
3088  break;
3089  case 't':
3090  t = parse_binary_expression(first + 2, last, ">", db);
3091  if (t != first + 2)
3092  first = t;
3093  break;
3094  }
3095  break;
3096  case 'i':
3097  if (t[1] == 'x') {
3098  const char *t1 = parse_expression(first + 2, last, db);
3099  if (t1 != first + 2) {
3100  const char *t2 = parse_expression(t1, last, db);
3101  if (t2 != t1) {
3102  if (db.names.size() < 2)
3103  return first;
3104  auto op2 = db.names.back().move_full();
3105  db.names.pop_back();
3106  auto op1 = db.names.back().move_full();
3107  db.names.back() = "(" + op1 + ")[" + op2 + "]";
3108  first = t2;
3109  } else if (!db.names.empty())
3110  db.names.pop_back();
3111  }
3112  }
3113  break;
3114  case 'l':
3115  switch (t[1]) {
3116  case 'e':
3117  t = parse_binary_expression(first + 2, last, "<=", db);
3118  if (t != first + 2)
3119  first = t;
3120  break;
3121  case 's':
3122  t = parse_binary_expression(first + 2, last, "<<", db);
3123  if (t != first + 2)
3124  first = t;
3125  break;
3126  case 'S':
3127  t = parse_binary_expression(first + 2, last, "<<=", db);
3128  if (t != first + 2)
3129  first = t;
3130  break;
3131  case 't':
3132  t = parse_binary_expression(first + 2, last, "<", db);
3133  if (t != first + 2)
3134  first = t;
3135  break;
3136  }
3137  break;
3138  case 'm':
3139  switch (t[1]) {
3140  case 'i':
3141  t = parse_binary_expression(first + 2, last, "-", db);
3142  if (t != first + 2)
3143  first = t;
3144  break;
3145  case 'I':
3146  t = parse_binary_expression(first + 2, last, "-=", db);
3147  if (t != first + 2)
3148  first = t;
3149  break;
3150  case 'l':
3151  t = parse_binary_expression(first + 2, last, "*", db);
3152  if (t != first + 2)
3153  first = t;
3154  break;
3155  case 'L':
3156  t = parse_binary_expression(first + 2, last, "*=", db);
3157  if (t != first + 2)
3158  first = t;
3159  break;
3160  case 'm':
3161  if (first + 2 != last && first[2] == '_') {
3162  t = parse_prefix_expression(first + 3, last, "--", db);
3163  if (t != first + 3)
3164  first = t;
3165  } else {
3166  const char *t1 = parse_expression(first + 2, last, db);
3167  if (t1 != first + 2) {
3168  if (db.names.empty())
3169  return first;
3170  db.names.back() = "(" + db.names.back().move_full() + ")--";
3171  first = t1;
3172  }
3173  }
3174  break;
3175  }
3176  break;
3177  case 'n':
3178  switch (t[1]) {
3179  case 'a':
3180  case 'w':
3181  first = parse_new_expr(first, last, db);
3182  break;
3183  case 'e':
3184  t = parse_binary_expression(first + 2, last, "!=", db);
3185  if (t != first + 2)
3186  first = t;
3187  break;
3188  case 'g':
3189  t = parse_prefix_expression(first + 2, last, "-", db);
3190  if (t != first + 2)
3191  first = t;
3192  break;
3193  case 't':
3194  t = parse_prefix_expression(first + 2, last, "!", db);
3195  if (t != first + 2)
3196  first = t;
3197  break;
3198  case 'x':
3199  t = parse_noexcept_expression(first + 2, last, db);
3200  if (t != first + 2)
3201  first = t;
3202  break;
3203  }
3204  break;
3205  case 'o':
3206  switch (t[1]) {
3207  case 'n':
3208  return parse_unresolved_name(first, last, db);
3209  case 'o':
3210  t = parse_binary_expression(first + 2, last, "||", db);
3211  if (t != first + 2)
3212  first = t;
3213  break;
3214  case 'r':
3215  t = parse_binary_expression(first + 2, last, "|", db);
3216  if (t != first + 2)
3217  first = t;
3218  break;
3219  case 'R':
3220  t = parse_binary_expression(first + 2, last, "|=", db);
3221  if (t != first + 2)
3222  first = t;
3223  break;
3224  }
3225  break;
3226  case 'p':
3227  switch (t[1]) {
3228  case 'm':
3229  t = parse_binary_expression(first + 2, last, "->*", db);
3230  if (t != first + 2)
3231  first = t;
3232  break;
3233  case 'l':
3234  t = parse_binary_expression(first + 2, last, "+", db);
3235  if (t != first + 2)
3236  first = t;
3237  break;
3238  case 'L':
3239  t = parse_binary_expression(first + 2, last, "+=", db);
3240  if (t != first + 2)
3241  first = t;
3242  break;
3243  case 'p':
3244  if (first + 2 != last && first[2] == '_') {
3245  t = parse_prefix_expression(first + 3, last, "++", db);
3246  if (t != first + 3)
3247  first = t;
3248  } else {
3249  const char *t1 = parse_expression(first + 2, last, db);
3250  if (t1 != first + 2) {
3251  if (db.names.empty())
3252  return first;
3253  db.names.back() = "(" + db.names.back().move_full() + ")++";
3254  first = t1;
3255  }
3256  }
3257  break;
3258  case 's':
3259  t = parse_prefix_expression(first + 2, last, "+", db);
3260  if (t != first + 2)
3261  first = t;
3262  break;
3263  case 't':
3264  first = parse_arrow_expr(first, last, db);
3265  break;
3266  }
3267  break;
3268  case 'q':
3269  if (t[1] == 'u') {
3270  const char *t1 = parse_expression(first + 2, last, db);
3271  if (t1 != first + 2) {
3272  const char *t2 = parse_expression(t1, last, db);
3273  if (t2 != t1) {
3274  const char *t3 = parse_expression(t2, last, db);
3275  if (t3 != t2) {
3276  if (db.names.size() < 3)
3277  return first;
3278  auto op3 = db.names.back().move_full();
3279  db.names.pop_back();
3280  auto op2 = db.names.back().move_full();
3281  db.names.pop_back();
3282  auto op1 = db.names.back().move_full();
3283  db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")";
3284  first = t3;
3285  } else {
3286  if (db.names.size() < 2)
3287  return first;
3288  db.names.pop_back();
3289  db.names.pop_back();
3290  }
3291  } else if (!db.names.empty())
3292  db.names.pop_back();
3293  }
3294  }
3295  break;
3296  case 'r':
3297  switch (t[1]) {
3298  case 'c':
3299  first = parse_reinterpret_cast_expr(first, last, db);
3300  break;
3301  case 'm':
3302  t = parse_binary_expression(first + 2, last, "%", db);
3303  if (t != first + 2)
3304  first = t;
3305  break;
3306  case 'M':
3307  t = parse_binary_expression(first + 2, last, "%=", db);
3308  if (t != first + 2)
3309  first = t;
3310  break;
3311  case 's':
3312  t = parse_binary_expression(first + 2, last, ">>", db);
3313  if (t != first + 2)
3314  first = t;
3315  break;
3316  case 'S':
3317  t = parse_binary_expression(first + 2, last, ">>=", db);
3318  if (t != first + 2)
3319  first = t;
3320  break;
3321  }
3322  break;
3323  case 's':
3324  switch (t[1]) {
3325  case 'c':
3326  first = parse_static_cast_expr(first, last, db);
3327  break;
3328  case 'p':
3329  first = parse_pack_expansion(first, last, db);
3330  break;
3331  case 'r':
3332  return parse_unresolved_name(first, last, db);
3333  case 't':
3334  first = parse_sizeof_type_expr(first, last, db);
3335  break;
3336  case 'z':
3337  first = parse_sizeof_expr_expr(first, last, db);
3338  break;
3339  case 'Z':
3340  if (last - t >= 3) {
3341  switch (t[2]) {
3342  case 'T':
3343  first = parse_sizeof_param_pack_expr(first, last, db);
3344  break;
3345  case 'f':
3346  first = parse_sizeof_function_param_pack_expr(first, last, db);
3347  break;
3348  }
3349  }
3350  break;
3351  }
3352  break;
3353  case 't':
3354  switch (t[1]) {
3355  case 'e':
3356  case 'i':
3357  first = parse_typeid_expr(first, last, db);
3358  break;
3359  case 'r':
3360  db.names.push_back("throw");
3361  first += 2;
3362  break;
3363  case 'w':
3364  first = parse_throw_expr(first, last, db);
3365  break;
3366  }
3367  break;
3368  case '1':
3369  case '2':
3370  case '3':
3371  case '4':
3372  case '5':
3373  case '6':
3374  case '7':
3375  case '8':
3376  case '9':
3377  return parse_unresolved_name(first, last, db);
3378  }
3379  }
3380  return first;
3381 }
3382 
3383 // <template-arg> ::= <type> # type
3384 // or template
3385 // ::= X <expression> E #
3386 // expression
3387 // ::= <expr-primary> #
3388 // simple expressions
3389 // ::= J <template-arg>* E #
3390 // argument pack
3391 // ::= LZ <encoding> E #
3392 // extension
3393 
3394 template <class C>
3395 static const char *parse_template_arg(const char *first, const char *last,
3396  C &db) {
3397  if (first != last) {
3398  const char *t;
3399  switch (*first) {
3400  case 'X':
3401  t = parse_expression(first + 1, last, db);
3402  if (t != first + 1) {
3403  if (t != last && *t == 'E')
3404  first = t + 1;
3405  }
3406  break;
3407  case 'J':
3408  t = first + 1;
3409  if (t == last)
3410  return first;
3411  while (*t != 'E') {
3412  const char *t1 = parse_template_arg(t, last, db);
3413  if (t1 == t)
3414  return first;
3415  t = t1;
3416  }
3417  first = t + 1;
3418  break;
3419  case 'L':
3420  // <expr-primary> or LZ <encoding> E
3421  if (first + 1 != last && first[1] == 'Z') {
3422  t = parse_encoding(first + 2, last, db);
3423  if (t != first + 2 && t != last && *t == 'E')
3424  first = t + 1;
3425  } else
3426  first = parse_expr_primary(first, last, db);
3427  break;
3428  default:
3429  // <type>
3430  first = parse_type(first, last, db);
3431  break;
3432  }
3433  }
3434  return first;
3435 }
3436 
3437 // <template-args> ::= I <template-arg>* E
3438 // extension, the abi says <template-arg>+
3439 
3440 template <class C>
3441 static const char *parse_template_args(const char *first, const char *last,
3442  C &db) {
3443  if (last - first >= 2 && *first == 'I') {
3444  if (db.tag_templates)
3445  db.template_param.back().clear();
3446  const char *t = first + 1;
3447  std::string args("<");
3448  while (*t != 'E') {
3449  if (db.tag_templates)
3450  db.template_param.emplace_back();
3451  size_t k0 = db.names.size();
3452  const char *t1 = parse_template_arg(t, last, db);
3453  size_t k1 = db.names.size();
3454  if (db.tag_templates)
3455  db.template_param.pop_back();
3456  if (t1 == t || t1 == last)
3457  return first;
3458  if (db.tag_templates) {
3459  db.template_param.back().emplace_back();
3460  for (size_t k = k0; k < k1; ++k)
3461  db.template_param.back().back().push_back(db.names[k]);
3462  }
3463  for (size_t k = k0; k < k1; ++k) {
3464  if (args.size() > 1)
3465  args += ", ";
3466  args += db.names[k].move_full();
3467  }
3468  for (; k1 > k0; --k1)
3469  if (!db.names.empty())
3470  db.names.pop_back();
3471  t = t1;
3472  }
3473  first = t + 1;
3474  if (args.back() != '>')
3475  args += ">";
3476  else
3477  args += " >";
3478  db.names.push_back(std::move(args));
3479  }
3480  return first;
3481 }
3482 
3483 // <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
3484 // <unqualified-name> E
3485 // ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
3486 // <template-args> E
3487 //
3488 // <prefix> ::= <prefix> <unqualified-name>
3489 // ::= <template-prefix> <template-args>
3490 // ::= <template-param>
3491 // ::= <decltype>
3492 // ::= # empty
3493 // ::= <substitution>
3494 // ::= <prefix> <data-member-prefix>
3495 // extension ::= L
3496 //
3497 // <template-prefix> ::= <prefix> <template unqualified-name>
3498 // ::= <template-param>
3499 // ::= <substitution>
3500 
3501 template <class C>
3502 static const char *parse_nested_name(const char *first, const char *last, C &db,
3503  bool *ends_with_template_args) {
3504  if (first != last && *first == 'N') {
3505  unsigned cv;
3506  const char *t0 = parse_cv_qualifiers(first + 1, last, cv);
3507  if (t0 == last)
3508  return first;
3509  db.ref = 0;
3510  if (*t0 == 'R') {
3511  db.ref = 1;
3512  ++t0;
3513  } else if (*t0 == 'O') {
3514  db.ref = 2;
3515  ++t0;
3516  }
3517  db.names.emplace_back();
3518  if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't') {
3519  t0 += 2;
3520  db.names.back().first = "std";
3521  }
3522  if (t0 == last) {
3523  db.names.pop_back();
3524  return first;
3525  }
3526  bool pop_subs = false;
3527  bool component_ends_with_template_args = false;
3528  while (*t0 != 'E') {
3529  component_ends_with_template_args = false;
3530  const char *t1;
3531  switch (*t0) {
3532  case 'S':
3533  if (t0 + 1 != last && t0[1] == 't')
3534  goto do_parse_unqualified_name;
3535  t1 = parse_substitution(t0, last, db);
3536  if (t1 != t0 && t1 != last) {
3537  auto name = db.names.back().move_full();
3538  db.names.pop_back();
3539  if (db.names.empty())
3540  return first;
3541  if (!db.names.back().first.empty()) {
3542  db.names.back().first += "::" + name;
3543  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3544  } else
3545  db.names.back().first = name;
3546  pop_subs = true;
3547  t0 = t1;
3548  } else
3549  return first;
3550  break;
3551  case 'T':
3552  t1 = parse_template_param(t0, last, db);
3553  if (t1 != t0 && t1 != last) {
3554  auto name = db.names.back().move_full();
3555  db.names.pop_back();
3556  if (db.names.empty())
3557  return first;
3558  if (!db.names.back().first.empty())
3559  db.names.back().first += "::" + name;
3560  else
3561  db.names.back().first = name;
3562  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3563  pop_subs = true;
3564  t0 = t1;
3565  } else
3566  return first;
3567  break;
3568  case 'D':
3569  if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
3570  goto do_parse_unqualified_name;
3571  t1 = parse_decltype(t0, last, db);
3572  if (t1 != t0 && t1 != last) {
3573  auto name = db.names.back().move_full();
3574  db.names.pop_back();
3575  if (db.names.empty())
3576  return first;
3577  if (!db.names.back().first.empty())
3578  db.names.back().first += "::" + name;
3579  else
3580  db.names.back().first = name;
3581  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3582  pop_subs = true;
3583  t0 = t1;
3584  } else
3585  return first;
3586  break;
3587  case 'I':
3588  t1 = parse_template_args(t0, last, db);
3589  if (t1 != t0 && t1 != last) {
3590  auto name = db.names.back().move_full();
3591  db.names.pop_back();
3592  if (db.names.empty())
3593  return first;
3594  db.names.back().first += name;
3595  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3596  t0 = t1;
3597  component_ends_with_template_args = true;
3598  } else
3599  return first;
3600  break;
3601  case 'L':
3602  if (++t0 == last)
3603  return first;
3604  break;
3605  default:
3606  do_parse_unqualified_name:
3607  t1 = parse_unqualified_name(t0, last, db);
3608  if (t1 != t0 && t1 != last) {
3609  auto name = db.names.back().move_full();
3610  db.names.pop_back();
3611  if (db.names.empty())
3612  return first;
3613  if (!db.names.back().first.empty())
3614  db.names.back().first += "::" + name;
3615  else
3616  db.names.back().first = name;
3617  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3618  pop_subs = true;
3619  t0 = t1;
3620  } else
3621  return first;
3622  }
3623  }
3624  first = t0 + 1;
3625  db.cv = cv;
3626  if (pop_subs && !db.subs.empty())
3627  db.subs.pop_back();
3628  if (ends_with_template_args)
3629  *ends_with_template_args = component_ends_with_template_args;
3630  }
3631  return first;
3632 }
3633 
3634 // <discriminator> := _ <non-negative number> # when number < 10
3635 // := __ <non-negative number> _ # when number >= 10
3636 // extension := decimal-digit+ # at the end of string
3637 
3638 static const char *parse_discriminator(const char *first, const char *last) {
3639  // parse but ignore discriminator
3640  if (first != last) {
3641  if (*first == '_') {
3642  const char *t1 = first + 1;
3643  if (t1 != last) {
3644  if (std::isdigit(*t1))
3645  first = t1 + 1;
3646  else if (*t1 == '_') {
3647  for (++t1; t1 != last && std::isdigit(*t1); ++t1)
3648  ;
3649  if (t1 != last && *t1 == '_')
3650  first = t1 + 1;
3651  }
3652  }
3653  } else if (std::isdigit(*first)) {
3654  const char *t1 = first + 1;
3655  for (; t1 != last && std::isdigit(*t1); ++t1)
3656  ;
3657  if (t1 == last)
3658  first = last;
3659  }
3660  }
3661  return first;
3662 }
3663 
3664 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
3665 // := Z <function encoding> E s [<discriminator>]
3666 // := Z <function encoding> Ed [ <parameter number> ] _ <entity
3667 // name>
3668 
3669 template <class C>
3670 static const char *parse_local_name(const char *first, const char *last, C &db,
3671  bool *ends_with_template_args) {
3672  if (first != last && *first == 'Z') {
3673  const char *t = parse_encoding(first + 1, last, db);
3674  if (t != first + 1 && t != last && *t == 'E' && ++t != last) {
3675  switch (*t) {
3676  case 's':
3677  first = parse_discriminator(t + 1, last);
3678  if (db.names.empty())
3679  return first;
3680  db.names.back().first.append("::string literal");
3681  break;
3682  case 'd':
3683  if (++t != last) {
3684  const char *t1 = parse_number(t, last);
3685  if (t1 != last && *t1 == '_') {
3686  t = t1 + 1;
3687  t1 = parse_name(t, last, db, ends_with_template_args);
3688  if (t1 != t) {
3689  if (db.names.size() < 2)
3690  return first;
3691  auto name = db.names.back().move_full();
3692  db.names.pop_back();
3693  if (db.names.empty())
3694  return first;
3695  db.names.back().first.append("::");
3696  db.names.back().first.append(name);
3697  first = t1;
3698  } else if (!db.names.empty())
3699  db.names.pop_back();
3700  }
3701  }
3702  break;
3703  default: {
3704  const char *t1 = parse_name(t, last, db, ends_with_template_args);
3705  if (t1 != t) {
3706  // parse but ignore discriminator
3707  first = parse_discriminator(t1, last);
3708  if (db.names.size() < 2)
3709  return first;
3710  auto name = db.names.back().move_full();
3711  db.names.pop_back();
3712  if (db.names.empty())
3713  return first;
3714  db.names.back().first.append("::");
3715  db.names.back().first.append(name);
3716  } else if (!db.names.empty())
3717  db.names.pop_back();
3718  } break;
3719  }
3720  }
3721  }
3722  return first;
3723 }
3724 
3725 // <name> ::= <nested-name> // N
3726 // ::= <local-name> # See Scope Encoding below // Z
3727 // ::= <unscoped-template-name> <template-args>
3728 // ::= <unscoped-name>
3729 
3730 // <unscoped-template-name> ::= <unscoped-name>
3731 // ::= <substitution>
3732 
3733 template <class C>
3734 static const char *parse_name(const char *first, const char *last, C &db,
3735  bool *ends_with_template_args) {
3736  if (last - first >= 2) {
3737  const char *t0 = first;
3738  // extension: ignore L here
3739  if (*t0 == 'L')
3740  ++t0;
3741  switch (*t0) {
3742  case 'N': {
3743  const char *t1 = parse_nested_name(t0, last, db, ends_with_template_args);
3744  if (t1 != t0)
3745  first = t1;
3746  break;
3747  }
3748  case 'Z': {
3749  const char *t1 = parse_local_name(t0, last, db, ends_with_template_args);
3750  if (t1 != t0)
3751  first = t1;
3752  break;
3753  }
3754  default: {
3755  const char *t1 = parse_unscoped_name(t0, last, db);
3756  if (t1 != t0) {
3757  if (t1 != last &&
3758  *t1 == 'I') // <unscoped-template-name> <template-args>
3759  {
3760  if (db.names.empty())
3761  return first;
3762  db.subs.push_back(typename C::sub_type(1, db.names.back()));
3763  t0 = t1;
3764  t1 = parse_template_args(t0, last, db);
3765  if (t1 != t0) {
3766  if (db.names.size() < 2)
3767  return first;
3768  auto tmp = db.names.back().move_full();
3769  db.names.pop_back();
3770  if (db.names.empty())
3771  return first;
3772  db.names.back().first += tmp;
3773  first = t1;
3774  if (ends_with_template_args)
3775  *ends_with_template_args = true;
3776  }
3777  } else // <unscoped-name>
3778  first = t1;
3779  } else { // try <substitution> <template-args>
3780  t1 = parse_substitution(t0, last, db);
3781  if (t1 != t0 && t1 != last && *t1 == 'I') {
3782  t0 = t1;
3783  t1 = parse_template_args(t0, last, db);
3784  if (t1 != t0) {
3785  if (db.names.size() < 2)
3786  return first;
3787  auto tmp = db.names.back().move_full();
3788  db.names.pop_back();
3789  if (db.names.empty())
3790  return first;
3791  db.names.back().first += tmp;
3792  first = t1;
3793  if (ends_with_template_args)
3794  *ends_with_template_args = true;
3795  }
3796  }
3797  }
3798  break;
3799  }
3800  }
3801  }
3802  return first;
3803 }
3804 
3805 // <call-offset> ::= h <nv-offset> _
3806 // ::= v <v-offset> _
3807 //
3808 // <nv-offset> ::= <offset number>
3809 // # non-virtual base override
3810 //
3811 // <v-offset> ::= <offset number> _ <virtual offset number>
3812 // # virtual base override, with vcall offset
3813 
3814 static const char *parse_call_offset(const char *first, const char *last) {
3815  if (first != last) {
3816  switch (*first) {
3817  case 'h': {
3818  const char *t = parse_number(first + 1, last);
3819  if (t != first + 1 && t != last && *t == '_')
3820  first = t + 1;
3821  } break;
3822  case 'v': {
3823  const char *t = parse_number(first + 1, last);
3824  if (t != first + 1 && t != last && *t == '_') {
3825  const char *t2 = parse_number(++t, last);
3826  if (t2 != t && t2 != last && *t2 == '_')
3827  first = t2 + 1;
3828  }
3829  } break;
3830  }
3831  }
3832  return first;
3833 }
3834 
3835 // <special-name> ::= TV <type> # virtual table
3836 // ::= TT <type> # VTT structure (construction vtable index)
3837 // ::= TI <type> # typeinfo structure
3838 // ::= TS <type> # typeinfo name (null-terminated byte string)
3839 // ::= Tc <call-offset> <call-offset> <base encoding>
3840 // # base is the nominal target function of thunk
3841 // # first call-offset is 'this' adjustment
3842 // # second call-offset is result adjustment
3843 // ::= T <call-offset> <base encoding>
3844 // # base is the nominal target function of thunk
3845 // ::= GV <object name> # Guard variable for one-time
3846 // initialization
3847 // # No <type>
3848 // ::= TW <object name> # Thread-local wrapper
3849 // ::= TH <object name> # Thread-local initialization
3850 // extension ::= TC <first type> <number> _ <second type> # construction
3851 // vtable for second-in-first
3852 // extension ::= GR <object name> # reference temporary for object
3853 
3854 template <class C>
3855 static const char *parse_special_name(const char *first, const char *last,
3856  C &db) {
3857  if (last - first > 2) {
3858  const char *t;
3859  switch (*first) {
3860  case 'T':
3861  switch (first[1]) {
3862  case 'V':
3863  // TV <type> # virtual table
3864  t = parse_type(first + 2, last, db);
3865  if (t != first + 2) {
3866  if (db.names.empty())
3867  return first;
3868  db.names.back().first.insert(0, "vtable for ");
3869  first = t;
3870  }
3871  break;
3872  case 'T':
3873  // TT <type> # VTT structure (construction vtable index)
3874  t = parse_type(first + 2, last, db);
3875  if (t != first + 2) {
3876  if (db.names.empty())
3877  return first;
3878  db.names.back().first.insert(0, "VTT for ");
3879  first = t;
3880  }
3881  break;
3882  case 'I':
3883  // TI <type> # typeinfo structure
3884  t = parse_type(first + 2, last, db);
3885  if (t != first + 2) {
3886  if (db.names.empty())
3887  return first;
3888  db.names.back().first.insert(0, "typeinfo for ");
3889  first = t;
3890  }
3891  break;
3892  case 'S':
3893  // TS <type> # typeinfo name (null-terminated byte string)
3894  t = parse_type(first + 2, last, db);
3895  if (t != first + 2) {
3896  if (db.names.empty())
3897  return first;
3898  db.names.back().first.insert(0, "typeinfo name for ");
3899  first = t;
3900  }
3901  break;
3902  case 'c':
3903  // Tc <call-offset> <call-offset> <base encoding>
3904  {
3905  const char *t0 = parse_call_offset(first + 2, last);
3906  if (t0 == first + 2)
3907  break;
3908  const char *t1 = parse_call_offset(t0, last);
3909  if (t1 == t0)
3910  break;
3911  t = parse_encoding(t1, last, db);
3912  if (t != t1) {
3913  if (db.names.empty())
3914  return first;
3915  db.names.back().first.insert(0, "covariant return thunk to ");
3916  first = t;
3917  }
3918  }
3919  break;
3920  case 'C':
3921  // extension ::= TC <first type> <number> _ <second type> # construction
3922  // vtable for second-in-first
3923  t = parse_type(first + 2, last, db);
3924  if (t != first + 2) {
3925  const char *t0 = parse_number(t, last);
3926  if (t0 != t && t0 != last && *t0 == '_') {
3927  const char *t1 = parse_type(++t0, last, db);
3928  if (t1 != t0) {
3929  if (db.names.size() < 2)
3930  return first;
3931  auto left = db.names.back().move_full();
3932  db.names.pop_back();
3933  if (db.names.empty())
3934  return first;
3935  db.names.back().first = "construction vtable for " +
3936  std::move(left) + "-in-" +
3937  db.names.back().move_full();
3938  first = t1;
3939  }
3940  }
3941  }
3942  break;
3943  case 'W':
3944  // TW <object name> # Thread-local wrapper
3945  t = parse_name(first + 2, last, db);
3946  if (t != first + 2) {
3947  if (db.names.empty())
3948  return first;
3949  db.names.back().first.insert(0, "thread-local wrapper routine for ");
3950  first = t;
3951  }
3952  break;
3953  case 'H':
3954  // TH <object name> # Thread-local initialization
3955  t = parse_name(first + 2, last, db);
3956  if (t != first + 2) {
3957  if (db.names.empty())
3958  return first;
3959  db.names.back().first.insert(
3960  0, "thread-local initialization routine for ");
3961  first = t;
3962  }
3963  break;
3964  default:
3965  // T <call-offset> <base encoding>
3966  {
3967  const char *t0 = parse_call_offset(first + 1, last);
3968  if (t0 == first + 1)
3969  break;
3970  t = parse_encoding(t0, last, db);
3971  if (t != t0) {
3972  if (db.names.empty())
3973  return first;
3974  if (first[1] == 'v') {
3975  db.names.back().first.insert(0, "virtual thunk to ");
3976  first = t;
3977  } else {
3978  db.names.back().first.insert(0, "non-virtual thunk to ");
3979  first = t;
3980  }
3981  }
3982  }
3983  break;
3984  }
3985  break;
3986  case 'G':
3987  switch (first[1]) {
3988  case 'V':
3989  // GV <object name> # Guard variable for one-time initialization
3990  t = parse_name(first + 2, last, db);
3991  if (t != first + 2) {
3992  if (db.names.empty())
3993  return first;
3994  db.names.back().first.insert(0, "guard variable for ");
3995  first = t;
3996  }
3997  break;
3998  case 'R':
3999  // extension ::= GR <object name> # reference temporary for object
4000  t = parse_name(first + 2, last, db);
4001  if (t != first + 2) {
4002  if (db.names.empty())
4003  return first;
4004  db.names.back().first.insert(0, "reference temporary for ");
4005  first = t;
4006  }
4007  break;
4008  }
4009  break;
4010  }
4011  }
4012  return first;
4013 }
4014 
4015 namespace {
4016 template <class T> class save_value {
4017  T &restore_;
4018  T original_value_;
4019 
4020 public:
4021  save_value(T &restore) : restore_(restore), original_value_(restore) {}
4022 
4023  ~save_value() { restore_ = std::move(original_value_); }
4024 
4025  save_value(const save_value &) = delete;
4026  save_value &operator=(const save_value &) = delete;
4027 };
4028 }
4029 
4030 // <encoding> ::= <function name> <bare-function-type>
4031 // ::= <data name>
4032 // ::= <special-name>
4033 
4034 template <class C>
4035 static const char *parse_encoding(const char *first, const char *last, C &db) {
4036  if (first != last) {
4037  save_value<decltype(db.encoding_depth)> su(db.encoding_depth);
4038  ++db.encoding_depth;
4039  save_value<decltype(db.tag_templates)> sb(db.tag_templates);
4040  if (db.encoding_depth > 1)
4041  db.tag_templates = true;
4042  save_value<decltype(db.parsed_ctor_dtor_cv)> sp(db.parsed_ctor_dtor_cv);
4043  db.parsed_ctor_dtor_cv = false;
4044  switch (*first) {
4045  case 'G':
4046  case 'T':
4047  first = parse_special_name(first, last, db);
4048  break;
4049  default: {
4050  bool ends_with_template_args = false;
4051  const char *t = parse_name(first, last, db, &ends_with_template_args);
4052  unsigned cv = db.cv;
4053  unsigned ref = db.ref;
4054  if (t != first) {
4055  if (t != last && *t != 'E' && *t != '.') {
4056  save_value<bool> sb2(db.tag_templates);
4057  db.tag_templates = false;
4058  const char *t2;
4059  std::string ret2;
4060  if (db.names.empty())
4061  return first;
4062  const std::string &nm = db.names.back().first;
4063  if (nm.empty())
4064  return first;
4065  if (!db.parsed_ctor_dtor_cv && ends_with_template_args) {
4066  t2 = parse_type(t, last, db);
4067  if (t2 == t)
4068  return first;
4069  if (db.names.size() < 2)
4070  return first;
4071  auto ret1 = std::move(db.names.back().first);
4072  ret2 = std::move(db.names.back().second);
4073  if (ret2.empty())
4074  ret1 += ' ';
4075  db.names.pop_back();
4076  if (db.names.empty())
4077  return first;
4078 
4079  db.names.back().first.insert(0, ret1);
4080  t = t2;
4081  }
4082  db.names.back().first += '(';
4083  if (t != last && *t == 'v') {
4084  ++t;
4085  } else {
4086  bool first_arg = true;
4087  while (true) {
4088  size_t k0 = db.names.size();
4089  t2 = parse_type(t, last, db);
4090  size_t k1 = db.names.size();
4091  if (t2 == t)
4092  break;
4093  if (k1 > k0) {
4094  std::string tmp;
4095  for (size_t k = k0; k < k1; ++k) {
4096  if (!tmp.empty())
4097  tmp += ", ";
4098  tmp += db.names[k].move_full();
4099  }
4100  for (size_t k = k0; k < k1; ++k) {
4101  if (db.names.empty())
4102  return first;
4103  db.names.pop_back();
4104  }
4105  if (!tmp.empty()) {
4106  if (db.names.empty())
4107  return first;
4108  if (!first_arg)
4109  db.names.back().first += ", ";
4110  else
4111  first_arg = false;
4112  db.names.back().first += tmp;
4113  }
4114  }
4115  t = t2;
4116  }
4117  }
4118  if (db.names.empty())
4119  return first;
4120  db.names.back().first += ')';
4121  if (cv & CV_const)
4122  db.names.back().first.append(" const");
4123  if (cv & CV_volatile)
4124  db.names.back().first.append(" volatile");
4125  if (cv & CV_restrict)
4126  db.names.back().first.append(" restrict");
4127  if (ref == 1)
4128  db.names.back().first.append(" &");
4129  else if (ref == 2)
4130  db.names.back().first.append(" &&");
4131  db.names.back().first += ret2;
4132  first = t;
4133  } else
4134  first = t;
4135  }
4136  break;
4137  }
4138  }
4139  }
4140  return first;
4141 }
4142 
4143 // _block_invoke
4144 // _block_invoke<decimal-digit>+
4145 // _block_invoke_<decimal-digit>+
4146 
4147 template <class C>
4148 static const char *parse_block_invoke(const char *first, const char *last,
4149  C &db) {
4150  if (last - first >= 13) {
4151  const char test[] = "_block_invoke";
4152  const char *t = first;
4153  for (int i = 0; i < 13; ++i, ++t) {
4154  if (*t != test[i])
4155  return first;
4156  }
4157  if (t != last) {
4158  if (*t == '_') {
4159  // must have at least 1 decimal digit
4160  if (++t == last || !std::isdigit(*t))
4161  return first;
4162  ++t;
4163  }
4164  // parse zero or more digits
4165  while (t != last && isdigit(*t))
4166  ++t;
4167  }
4168  if (db.names.empty())
4169  return first;
4170  db.names.back().first.insert(0, "invocation function for block in ");
4171  first = t;
4172  }
4173  return first;
4174 }
4175 
4176 // extension
4177 // <dot-suffix> := .<anything and everything>
4178 
4179 template <class C>
4180 static const char *parse_dot_suffix(const char *first, const char *last,
4181  C &db) {
4182  if (first != last && *first == '.') {
4183  if (db.names.empty())
4184  return first;
4185  db.names.back().first += " (" + std::string(first, last) + ")";
4186  first = last;
4187  }
4188  return first;
4189 }
4190 
4191 // <block-involcaton-function> ___Z<encoding>_block_invoke
4192 // <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+
4193 // <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+
4194 // <mangled-name> ::= _Z<encoding>
4195 // ::= <type>
4196 
4197 template <class C>
4198 static void demangle(const char *first, const char *last, C &db, int &status) {
4199  if (first >= last) {
4200  status = invalid_mangled_name;
4201  return;
4202  }
4203  if (*first == '_') {
4204  if (last - first >= 4) {
4205  if (first[1] == 'Z') {
4206  const char *t = parse_encoding(first + 2, last, db);
4207  if (t != first + 2 && t != last && *t == '.')
4208  t = parse_dot_suffix(t, last, db);
4209  if (t != last)
4210  status = invalid_mangled_name;
4211  } else if (first[1] == '_' && first[2] == '_' && first[3] == 'Z') {
4212  const char *t = parse_encoding(first + 4, last, db);
4213  if (t != first + 4 && t != last) {
4214  const char *t1 = parse_block_invoke(t, last, db);
4215  if (t1 != last)
4216  status = invalid_mangled_name;
4217  } else
4218  status = invalid_mangled_name;
4219  } else
4220  status = invalid_mangled_name;
4221  } else
4222  status = invalid_mangled_name;
4223  } else {
4224  const char *t = parse_type(first, last, db);
4225  if (t != last)
4226  status = invalid_mangled_name;
4227  }
4228  if (status == success && db.names.empty())
4229  status = invalid_mangled_name;
4230 }
4231 
4232 namespace {
4233 template <class StrT> struct string_pair {
4234  StrT first;
4235  StrT second;
4236 
4237  string_pair() = default;
4238  string_pair(StrT f) : first(std::move(f)) {}
4239  string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
4240  template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {}
4241 
4242  size_t size() const { return first.size() + second.size(); }
4243  bool empty() const { return first.empty() && second.empty(); }
4244  StrT full() const { return first + second; }
4245  StrT move_full() { return std::move(first) + std::move(second); }
4246 };
4247 
4248 struct Db {
4249  typedef std::vector<string_pair<std::string>> sub_type;
4250  typedef std::vector<sub_type> template_param_type;
4251  sub_type names;
4252  template_param_type subs;
4253  std::vector<template_param_type> template_param;
4254  unsigned cv = 0;
4255  unsigned ref = 0;
4256  unsigned encoding_depth = 0;
4257  bool parsed_ctor_dtor_cv = false;
4258  bool tag_templates = true;
4259  bool fix_forward_references = false;
4260  bool try_to_parse_template_args = true;
4261 
4262  Db() : subs(0, names), template_param(0, subs) {}
4263 };
4264 }
4265 
4266 char *llvm::itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
4267  int *status) {
4268  if (mangled_name == nullptr || (buf != nullptr && n == nullptr)) {
4269  if (status)
4270  *status = invalid_args;
4271  return nullptr;
4272  }
4273  size_t internal_size = buf != nullptr ? *n : 0;
4274  Db db;
4275  db.template_param.emplace_back();
4276  int internal_status = success;
4277  size_t len = std::strlen(mangled_name);
4278  demangle(mangled_name, mangled_name + len, db, internal_status);
4279  if (internal_status == success && db.fix_forward_references &&
4280  !db.template_param.empty() && !db.template_param.front().empty()) {
4281  db.fix_forward_references = false;
4282  db.tag_templates = false;
4283  db.names.clear();
4284  db.subs.clear();
4285  demangle(mangled_name, mangled_name + len, db, internal_status);
4286  if (db.fix_forward_references)
4287  internal_status = invalid_mangled_name;
4288  }
4289  if (internal_status == success) {
4290  size_t sz = db.names.back().size() + 1;
4291  if (sz > internal_size) {
4292  char *newbuf = static_cast<char *>(std::realloc(buf, sz));
4293  if (newbuf == nullptr) {
4294  internal_status = memory_alloc_failure;
4295  buf = nullptr;
4296  } else {
4297  buf = newbuf;
4298  if (n != nullptr)
4299  *n = sz;
4300  }
4301  }
4302  if (buf != nullptr) {
4303  db.names.back().first += db.names.back().second;
4304  std::memcpy(buf, db.names.back().first.data(), sz - 1);
4305  buf[sz - 1] = char(0);
4306  }
4307  } else
4308  buf = nullptr;
4309  if (status)
4310  *status = internal_status;
4311  return buf;
4312 }
static const char * parse_expression(const char *first, const char *last, C &db)
uint64_t CallInst * C
static const char * parse_sizeof_expr_expr(const char *first, const char *last, C &db)
char * itaniumDemangle(const char *mangled_name, char *buf, size_t *n, int *status)
This is a llvm local version of __cxa_demangle.
static const uint64_t k0
Some primes between 2^63 and 2^64 for various uses.
Definition: Hashing.h:162
static const char * parse_noexcept_expression(const char *first, const char *last, C &db)
static const char * parse_builtin_type(const char *first, const char *last, C &db)
static const char * parse_source_name(const char *first, const char *last, C &db)
static const char * parse_ctor_dtor_name(const char *first, const char *last, C &db)
static const char * parse_template_args(const char *first, const char *last, C &db)
unsigned second
#define op(i)
static const char * parse_unresolved_name(const char *first, const char *last, C &db)
static const char * parse_arrow_expr(const char *first, const char *last, C &db)
static const char * parse_expr_primary(const char *first, const char *last, C &db)
static const char * parse_unscoped_name(const char *first, const char *last, C &db)
static const char * parse_dynamic_cast_expr(const char *first, const char *last, C &db)
static const char * parse_call_offset(const char *first, const char *last)
static const char * parse_throw_expr(const char *first, const char *last, C &db)
static const char * parse_template_arg(const char *first, const char *last, C &db)
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:248
static const char * parse_unnamed_type_name(const char *first, const char *last, C &db)
static const char * parse_static_cast_expr(const char *first, const char *last, C &db)
static const char * parse_special_name(const char *first, const char *last, C &db)
static const char * parse_block_invoke(const char *first, const char *last, C &db)
static const char * parse_operator_name(const char *first, const char *last, C &db)
static const char * parse_nested_name(const char *first, const char *last, C &db, bool *ends_with_template_args)
static const char * parse_dot_expr(const char *first, const char *last, C &db)
static const char * parse_function_type(const char *first, const char *last, C &db)
static const char * parse_dot_star_expr(const char *first, const char *last, C &db)
std::error_code status(const Twine &path, file_status &result, bool follow=true)
Get file status as if by POSIX stat().
static const char * parse_new_expr(const char *first, const char *last, C &db)
static std::string base_name(std::string &s)
static const char * parse_const_cast_expr(const char *first, const char *last, C &db)
static const char * parse_sizeof_function_param_pack_expr(const char *first, const char *last, C &db)
static void demangle(const char *first, const char *last, C &db, int &status)
static const char * parse_conversion_expr(const char *first, const char *last, C &db)
static const char * parse_sizeof_type_expr(const char *first, const char *last, C &db)
static const char * parse_local_name(const char *first, const char *last, C &db, bool *ends_with_template_args)
unsigned first
static const uint64_t k1
Definition: Hashing.h:163
static const char * parse_function_param(const char *first, const char *last, C &db)
static const char * parse_unresolved_qualifier_level(const char *first, const char *last, C &db)
static const char * parse_sizeof_param_pack_expr(const char *first, const char *last, C &db)
static const char * parse_integer_literal(const char *first, const char *last, const std::string &lit, C &db)
static const char * parse_encoding(const char *first, const char *last, C &db)
static const char * parse_cv_qualifiers(const char *first, const char *last, unsigned &cv)
static const char * parse_call_expr(const char *first, const char *last, C &db)
void for_each(Policy policy, IterTy Begin, IterTy End, FuncTy Fn)
Definition: Parallel.h:207
static const char * parse_template_param(const char *first, const char *last, C &db)
static const char * parse_simple_id(const char *first, const char *last, C &db)
static const char * parse_number(const char *first, const char *last)
static const char * parse_unqualified_name(const char *first, const char *last, C &db)
static const char * parse_name(const char *first, const char *last, C &db, bool *ends_with_template_args=0)
static const char * parse_unresolved_type(const char *first, const char *last, C &db)
static const char * parse_type(const char *first, const char *last, C &db)
static const char * parse_dot_suffix(const char *first, const char *last, C &db)
static const char * parse_vector_type(const char *first, const char *last, C &db)
static const char * parse_decltype(const char *first, const char *last, C &db)
static const char * parse_floating_number(const char *first, const char *last, C &db)
static const char * parse_base_unresolved_name(const char *first, const char *last, C &db)
#define N
static const char * parse_substitution(const char *first, const char *last, C &db)
static const char * parse_prefix_expression(const char *first, const char *last, const std::string &op, C &db)
static const char * parse_alignof_type(const char *first, const char *last, C &db)
static const char * parse_pack_expansion(const char *first, const char *last, C &db)
static const char * parse_discriminator(const char *first, const char *last)
static const char * parse_array_type(const char *first, const char *last, C &db)
static const char * name
static const char * parse_pointer_to_member_type(const char *first, const char *last, C &db)
static const char * parse_reinterpret_cast_expr(const char *first, const char *last, C &db)
static const char * parse_alignof_expr(const char *first, const char *last, C &db)
static const char * parse_typeid_expr(const char *first, const char *last, C &db)
static const char * parse_destructor_name(const char *first, const char *last, C &db)
static const char * parse_binary_expression(const char *first, const char *last, const std::string &op, C &db)