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