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