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             if (!db.names.empty())
1406               db.names.pop_back();
1407             return first;
1408           }
1409           if (*t == 'E') {
1410             ++t;
1411             break;
1412           }
1413           if (*t == 'v') {
1414             ++t;
1415             continue;
1416           }
1417           if (*t == 'R' && t + 1 != last && t[1] == 'E') {
1418             ref_qual = 1;
1419             ++t;
1420             continue;
1421           }
1422           if (*t == 'O' && t + 1 != last && t[1] == 'E') {
1423             ref_qual = 2;
1424             ++t;
1425             continue;
1426           }
1427           size_t k0 = db.names.size();
1428           t1 = parse_type(t, last, db);
1429           size_t k1 = db.names.size();
1430           if (t1 == t || t1 == last)
1431             return first;
1432           for (size_t k = k0; k < k1; ++k) {
1433             if (sig.size() > 1)
1434               sig += ", ";
1435             sig += db.names[k].move_full();
1436           }
1437           for (size_t k = k0; k < k1; ++k)
1438             db.names.pop_back();
1439           t = t1;
1440         }
1441         sig += ")";
1442         switch (ref_qual) {
1443         case 1:
1444           sig += " &";
1445           break;
1446         case 2:
1447           sig += " &&";
1448           break;
1449         }
1450         if (db.names.empty())
1451           return first;
1452         db.names.back().first += " ";
1453         db.names.back().second.insert(0, sig);
1454         first = t;
1455       }
1456     }
1457   }
1458   return first;
1459 }
1460 
1461 // <pointer-to-member-type> ::= M <class type> <member type>
1462 
1463 template <class C>
1464 static const char *parse_pointer_to_member_type(const char *first,
1465                                                 const char *last, C &db) {
1466   if (first != last && *first == 'M') {
1467     const char *t = parse_type(first + 1, last, db);
1468     if (t != first + 1) {
1469       const char *t2 = parse_type(t, last, db);
1470       if (t2 != t) {
1471         if (db.names.size() < 2)
1472           return first;
1473         auto func = std::move(db.names.back());
1474         db.names.pop_back();
1475         auto class_type = std::move(db.names.back());
1476         if (!func.second.empty() && func.second.front() == '(') {
1477           db.names.back().first =
1478               std::move(func.first) + "(" + class_type.move_full() + "::*";
1479           db.names.back().second = ")" + std::move(func.second);
1480         } else {
1481           db.names.back().first =
1482               std::move(func.first) + " " + class_type.move_full() + "::*";
1483           db.names.back().second = std::move(func.second);
1484         }
1485         first = t2;
1486       }
1487     }
1488   }
1489   return first;
1490 }
1491 
1492 // <array-type> ::= A <positive dimension number> _ <element type>
1493 //              ::= A [<dimension expression>] _ <element type>
1494 
1495 template <class C>
1496 static const char *parse_array_type(const char *first, const char *last,
1497                                     C &db) {
1498   if (first != last && *first == 'A' && first + 1 != last) {
1499     if (first[1] == '_') {
1500       const char *t = parse_type(first + 2, last, db);
1501       if (t != first + 2) {
1502         if (db.names.empty())
1503           return first;
1504         if (db.names.back().second.substr(0, 2) == " [")
1505           db.names.back().second.erase(0, 1);
1506         db.names.back().second.insert(0, " []");
1507         first = t;
1508       }
1509     } else if ('1' <= first[1] && first[1] <= '9') {
1510       const char *t = parse_number(first + 1, last);
1511       if (t != last && *t == '_') {
1512         const char *t2 = parse_type(t + 1, last, db);
1513         if (t2 != t + 1) {
1514           if (db.names.empty())
1515             return first;
1516           if (db.names.back().second.substr(0, 2) == " [")
1517             db.names.back().second.erase(0, 1);
1518           db.names.back().second.insert(0,
1519                                         " [" + std::string(first + 1, t) + "]");
1520           first = t2;
1521         }
1522       }
1523     } else {
1524       const char *t = parse_expression(first + 1, last, db);
1525       if (t != first + 1 && t != last && *t == '_') {
1526         const char *t2 = parse_type(++t, last, db);
1527         if (t2 != t) {
1528           if (db.names.size() < 2)
1529             return first;
1530           auto type = std::move(db.names.back());
1531           db.names.pop_back();
1532           auto expr = std::move(db.names.back());
1533           db.names.back().first = std::move(type.first);
1534           if (type.second.substr(0, 2) == " [")
1535             type.second.erase(0, 1);
1536           db.names.back().second =
1537               " [" + expr.move_full() + "]" + std::move(type.second);
1538           first = t2;
1539         }
1540       }
1541     }
1542   }
1543   return first;
1544 }
1545 
1546 // <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class
1547 // member access (C++0x)
1548 //             ::= DT <expression> E  # decltype of an expression (C++0x)
1549 
1550 template <class C>
1551 static const char *parse_decltype(const char *first, const char *last, C &db) {
1552   if (last - first >= 4 && first[0] == 'D') {
1553     switch (first[1]) {
1554     case 't':
1555     case 'T': {
1556       const char *t = parse_expression(first + 2, last, db);
1557       if (t != first + 2 && t != last && *t == 'E') {
1558         if (db.names.empty())
1559           return first;
1560         db.names.back() = "decltype(" + db.names.back().move_full() + ")";
1561         first = t + 1;
1562       }
1563     } break;
1564     }
1565   }
1566   return first;
1567 }
1568 
1569 // extension:
1570 // <vector-type>           ::= Dv <positive dimension number> _
1571 //                                    <extended element type>
1572 //                         ::= Dv [<dimension expression>] _ <element type>
1573 // <extended element type> ::= <element type>
1574 //                         ::= p # AltiVec vector pixel
1575 
1576 template <class C>
1577 static const char *parse_vector_type(const char *first, const char *last,
1578                                      C &db) {
1579   if (last - first > 3 && first[0] == 'D' && first[1] == 'v') {
1580     if ('1' <= first[2] && first[2] <= '9') {
1581       const char *t = parse_number(first + 2, last);
1582       if (t == last || *t != '_')
1583         return first;
1584       const char *num = first + 2;
1585       size_t sz = static_cast<size_t>(t - num);
1586       if (++t != last) {
1587         if (*t != 'p') {
1588           const char *t1 = parse_type(t, last, db);
1589           if (t1 != t) {
1590             if (db.names.empty())
1591               return first;
1592             db.names.back().first += " vector[" + std::string(num, sz) + "]";
1593             first = t1;
1594           }
1595         } else {
1596           ++t;
1597           db.names.push_back("pixel vector[" + std::string(num, sz) + "]");
1598           first = t;
1599         }
1600       }
1601     } else {
1602       std::string num;
1603       const char *t1 = first + 2;
1604       if (*t1 != '_') {
1605         const char *t = parse_expression(t1, last, db);
1606         if (t != t1) {
1607           if (db.names.empty())
1608             return first;
1609           num = db.names.back().move_full();
1610           db.names.pop_back();
1611           t1 = t;
1612         }
1613       }
1614       if (t1 != last && *t1 == '_' && ++t1 != last) {
1615         const char *t = parse_type(t1, last, db);
1616         if (t != t1) {
1617           if (db.names.empty())
1618             return first;
1619           db.names.back().first += " vector[" + num + "]";
1620           first = t;
1621         }
1622       }
1623     }
1624   }
1625   return first;
1626 }
1627 
1628 // <type> ::= <builtin-type>
1629 //        ::= <function-type>
1630 //        ::= <class-enum-type>
1631 //        ::= <array-type>
1632 //        ::= <pointer-to-member-type>
1633 //        ::= <template-param>
1634 //        ::= <template-template-param> <template-args>
1635 //        ::= <decltype>
1636 //        ::= <substitution>
1637 //        ::= <CV-qualifiers> <type>
1638 //        ::= P <type>        # pointer-to
1639 //        ::= R <type>        # reference-to
1640 //        ::= O <type>        # rvalue reference-to (C++0x)
1641 //        ::= C <type>        # complex pair (C 2000)
1642 //        ::= G <type>        # imaginary (C 2000)
1643 //        ::= Dp <type>       # pack expansion (C++0x)
1644 //        ::= U <source-name> <type>  # vendor extended type qualifier
1645 // extension := U <objc-name> <objc-type>  # objc-type<identifier>
1646 // extension := <vector-type> # <vector-type> starts with Dv
1647 
1648 // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 +
1649 // <number of digits in k1> + k1
1650 // <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name>
1651 // 11objc_object -> id<source-name>
1652 
1653 template <class C>
1654 static const char *parse_type(const char *first, const char *last, C &db) {
1655   if (first != last) {
1656     switch (*first) {
1657     case 'r':
1658     case 'V':
1659     case 'K': {
1660       unsigned cv = 0;
1661       const char *t = parse_cv_qualifiers(first, last, cv);
1662       if (t != first) {
1663         bool is_function = *t == 'F';
1664         size_t k0 = db.names.size();
1665         const char *t1 = parse_type(t, last, db);
1666         size_t k1 = db.names.size();
1667         if (t1 != t) {
1668           if (is_function)
1669             db.subs.pop_back();
1670           db.subs.emplace_back();
1671           for (size_t k = k0; k < k1; ++k) {
1672             if (is_function) {
1673               auto &name = db.names[k].second;
1674               size_t p = name.size();
1675 
1676               if (name[p - 2] == '&' && name[p - 1] == '&')
1677                 p -= 2;
1678               else if (name.back() == '&')
1679                 p -= 1;
1680 
1681               if (cv & CV_const) {
1682                 name.insert(p, " const");
1683                 p += 6;
1684               }
1685               if (cv & CV_volatile) {
1686                 name.insert(p, " volatile");
1687                 p += 9;
1688               }
1689               if (cv & CV_restrict)
1690                 name.insert(p, " restrict");
1691             } else {
1692               if (cv & CV_const)
1693                 db.names[k].first.append(" const");
1694               if (cv & CV_volatile)
1695                 db.names[k].first.append(" volatile");
1696               if (cv & CV_restrict)
1697                 db.names[k].first.append(" restrict");
1698             }
1699             db.subs.back().push_back(db.names[k]);
1700           }
1701           first = t1;
1702         }
1703       }
1704     } break;
1705     default: {
1706       const char *t = parse_builtin_type(first, last, db);
1707       if (t != first) {
1708         first = t;
1709       } else {
1710         switch (*first) {
1711         case 'A':
1712           t = parse_array_type(first, last, db);
1713           if (t != first) {
1714             if (db.names.empty())
1715               return first;
1716             first = t;
1717             db.subs.push_back(typename C::sub_type(1, db.names.back()));
1718           }
1719           break;
1720         case 'C':
1721           t = parse_type(first + 1, last, db);
1722           if (t != first + 1) {
1723             if (db.names.empty())
1724               return first;
1725             db.names.back().first.append(" complex");
1726             first = t;
1727             db.subs.push_back(typename C::sub_type(1, db.names.back()));
1728           }
1729           break;
1730         case 'F':
1731           t = parse_function_type(first, last, db);
1732           if (t != first) {
1733             if (db.names.empty())
1734               return first;
1735             first = t;
1736             db.subs.push_back(typename C::sub_type(1, db.names.back()));
1737           }
1738           break;
1739         case 'G':
1740           t = parse_type(first + 1, last, db);
1741           if (t != first + 1) {
1742             if (db.names.empty())
1743               return first;
1744             db.names.back().first.append(" imaginary");
1745             first = t;
1746             db.subs.push_back(typename C::sub_type(1, db.names.back()));
1747           }
1748           break;
1749         case 'M':
1750           t = parse_pointer_to_member_type(first, last, db);
1751           if (t != first) {
1752             if (db.names.empty())
1753               return first;
1754             first = t;
1755             db.subs.push_back(typename C::sub_type(1, db.names.back()));
1756           }
1757           break;
1758         case 'O': {
1759           size_t k0 = db.names.size();
1760           t = parse_type(first + 1, last, db);
1761           size_t k1 = db.names.size();
1762           if (t != first + 1) {
1763             db.subs.emplace_back();
1764             for (size_t k = k0; k < k1; ++k) {
1765               if (db.names[k].second.substr(0, 2) == " [") {
1766                 db.names[k].first += " (";
1767                 db.names[k].second.insert(0, ")");
1768               } else if (!db.names[k].second.empty() &&
1769                          db.names[k].second.front() == '(') {
1770                 db.names[k].first += "(";
1771                 db.names[k].second.insert(0, ")");
1772               }
1773               db.names[k].first.append("&&");
1774               db.subs.back().push_back(db.names[k]);
1775             }
1776             first = t;
1777           }
1778           break;
1779         }
1780         case 'P': {
1781           size_t k0 = db.names.size();
1782           t = parse_type(first + 1, last, db);
1783           size_t k1 = db.names.size();
1784           if (t != first + 1) {
1785             db.subs.emplace_back();
1786             for (size_t k = k0; k < k1; ++k) {
1787               if (db.names[k].second.substr(0, 2) == " [") {
1788                 db.names[k].first += " (";
1789                 db.names[k].second.insert(0, ")");
1790               } else if (!db.names[k].second.empty() &&
1791                          db.names[k].second.front() == '(') {
1792                 db.names[k].first += "(";
1793                 db.names[k].second.insert(0, ")");
1794               }
1795               if (first[1] != 'U' ||
1796                   db.names[k].first.substr(0, 12) != "objc_object<") {
1797                 db.names[k].first.append("*");
1798               } else {
1799                 db.names[k].first.replace(0, 11, "id");
1800               }
1801               db.subs.back().push_back(db.names[k]);
1802             }
1803             first = t;
1804           }
1805           break;
1806         }
1807         case 'R': {
1808           size_t k0 = db.names.size();
1809           t = parse_type(first + 1, last, db);
1810           size_t k1 = db.names.size();
1811           if (t != first + 1) {
1812             db.subs.emplace_back();
1813             for (size_t k = k0; k < k1; ++k) {
1814               if (db.names[k].second.substr(0, 2) == " [") {
1815                 db.names[k].first += " (";
1816                 db.names[k].second.insert(0, ")");
1817               } else if (!db.names[k].second.empty() &&
1818                          db.names[k].second.front() == '(') {
1819                 db.names[k].first += "(";
1820                 db.names[k].second.insert(0, ")");
1821               }
1822               db.names[k].first.append("&");
1823               db.subs.back().push_back(db.names[k]);
1824             }
1825             first = t;
1826           }
1827           break;
1828         }
1829         case 'T': {
1830           size_t k0 = db.names.size();
1831           t = parse_template_param(first, last, db);
1832           size_t k1 = db.names.size();
1833           if (t != first) {
1834             db.subs.emplace_back();
1835             for (size_t k = k0; k < k1; ++k)
1836               db.subs.back().push_back(db.names[k]);
1837             if (db.try_to_parse_template_args && k1 == k0 + 1) {
1838               const char *t1 = parse_template_args(t, last, db);
1839               if (t1 != t) {
1840                 auto args = db.names.back().move_full();
1841                 db.names.pop_back();
1842                 db.names.back().first += std::move(args);
1843                 db.subs.push_back(typename C::sub_type(1, db.names.back()));
1844                 t = t1;
1845               }
1846             }
1847             first = t;
1848           }
1849           break;
1850         }
1851         case 'U':
1852           if (first + 1 != last) {
1853             t = parse_source_name(first + 1, last, db);
1854             if (t != first + 1) {
1855               const char *t2 = parse_type(t, last, db);
1856               if (t2 != t) {
1857                 if (db.names.size() < 2)
1858                   return first;
1859                 auto type = db.names.back().move_full();
1860                 db.names.pop_back();
1861                 if (db.names.back().first.substr(0, 9) != "objcproto") {
1862                   db.names.back() = type + " " + db.names.back().move_full();
1863                 } else {
1864                   auto proto = db.names.back().move_full();
1865                   db.names.pop_back();
1866                   t = parse_source_name(proto.data() + 9,
1867                                         proto.data() + proto.size(), db);
1868                   if (t != proto.data() + 9) {
1869                     db.names.back() =
1870                         type + "<" + db.names.back().move_full() + ">";
1871                   } else {
1872                     db.names.push_back(type + " " + proto);
1873                   }
1874                 }
1875                 db.subs.push_back(typename C::sub_type(1, db.names.back()));
1876                 first = t2;
1877               }
1878             }
1879           }
1880           break;
1881         case 'S':
1882           if (first + 1 != last && first[1] == 't') {
1883             t = parse_name(first, last, db);
1884             if (t != first) {
1885               if (db.names.empty())
1886                 return first;
1887               db.subs.push_back(typename C::sub_type(1, db.names.back()));
1888               first = t;
1889             }
1890           } else {
1891             t = parse_substitution(first, last, db);
1892             if (t != first) {
1893               first = t;
1894               // Parsed a substitution.  If the substitution is a
1895               //  <template-param> it might be followed by <template-args>.
1896               t = parse_template_args(first, last, db);
1897               if (t != first) {
1898                 if (db.names.size() < 2)
1899                   return first;
1900                 auto template_args = db.names.back().move_full();
1901                 db.names.pop_back();
1902                 db.names.back().first += template_args;
1903                 // Need to create substitution for <template-template-param>
1904                 // <template-args>
1905                 db.subs.push_back(typename C::sub_type(1, db.names.back()));
1906                 first = t;
1907               }
1908             }
1909           }
1910           break;
1911         case 'D':
1912           if (first + 1 != last) {
1913             switch (first[1]) {
1914             case 'p': {
1915               size_t k0 = db.names.size();
1916               t = parse_type(first + 2, last, db);
1917               size_t k1 = db.names.size();
1918               if (t != first + 2) {
1919                 db.subs.emplace_back();
1920                 for (size_t k = k0; k < k1; ++k)
1921                   db.subs.back().push_back(db.names[k]);
1922                 first = t;
1923                 return first;
1924               }
1925               break;
1926             }
1927             case 't':
1928             case 'T':
1929               t = parse_decltype(first, last, db);
1930               if (t != first) {
1931                 if (db.names.empty())
1932                   return first;
1933                 db.subs.push_back(typename C::sub_type(1, db.names.back()));
1934                 first = t;
1935                 return first;
1936               }
1937               break;
1938             case 'v':
1939               t = parse_vector_type(first, last, db);
1940               if (t != first) {
1941                 if (db.names.empty())
1942                   return first;
1943                 db.subs.push_back(typename C::sub_type(1, db.names.back()));
1944                 first = t;
1945                 return first;
1946               }
1947               break;
1948             }
1949           }
1950         // falls through
1951         default:
1952           // must check for builtin-types before class-enum-types to avoid
1953           // ambiguities with operator-names
1954           t = parse_builtin_type(first, last, db);
1955           if (t != first) {
1956             first = t;
1957           } else {
1958             t = parse_name(first, last, db);
1959             if (t != first) {
1960               if (db.names.empty())
1961                 return first;
1962               db.subs.push_back(typename C::sub_type(1, db.names.back()));
1963               first = t;
1964             }
1965           }
1966           break;
1967         }
1968       }
1969       break;
1970     }
1971     }
1972   }
1973   return first;
1974 }
1975 
1976 //   <operator-name>
1977 //                   ::= aa    # &&
1978 //                   ::= ad    # & (unary)
1979 //                   ::= an    # &
1980 //                   ::= aN    # &=
1981 //                   ::= aS    # =
1982 //                   ::= cl    # ()
1983 //                   ::= cm    # ,
1984 //                   ::= co    # ~
1985 //                   ::= cv <type>    # (cast)
1986 //                   ::= da    # delete[]
1987 //                   ::= de    # * (unary)
1988 //                   ::= dl    # delete
1989 //                   ::= dv    # /
1990 //                   ::= dV    # /=
1991 //                   ::= eo    # ^
1992 //                   ::= eO    # ^=
1993 //                   ::= eq    # ==
1994 //                   ::= ge    # >=
1995 //                   ::= gt    # >
1996 //                   ::= ix    # []
1997 //                   ::= le    # <=
1998 //                   ::= li <source-name>  # operator ""
1999 //                   ::= ls    # <<
2000 //                   ::= lS    # <<=
2001 //                   ::= lt    # <
2002 //                   ::= mi    # -
2003 //                   ::= mI    # -=
2004 //                   ::= ml    # *
2005 //                   ::= mL    # *=
2006 //                   ::= mm    # -- (postfix in <expression> context)
2007 //                   ::= na    # new[]
2008 //                   ::= ne    # !=
2009 //                   ::= ng    # - (unary)
2010 //                   ::= nt    # !
2011 //                   ::= nw    # new
2012 //                   ::= oo    # ||
2013 //                   ::= or    # |
2014 //                   ::= oR    # |=
2015 //                   ::= pm    # ->*
2016 //                   ::= pl    # +
2017 //                   ::= pL    # +=
2018 //                   ::= pp    # ++ (postfix in <expression> context)
2019 //                   ::= ps    # + (unary)
2020 //                   ::= pt    # ->
2021 //                   ::= qu    # ?
2022 //                   ::= rm    # %
2023 //                   ::= rM    # %=
2024 //                   ::= rs    # >>
2025 //                   ::= rS    # >>=
2026 //                   ::= v <digit> <source-name>        # vendor extended
2027 //                   operator
2028 
2029 template <class C>
2030 static const char *parse_operator_name(const char *first, const char *last,
2031                                        C &db) {
2032   if (last - first >= 2) {
2033     switch (first[0]) {
2034     case 'a':
2035       switch (first[1]) {
2036       case 'a':
2037         db.names.push_back("operator&&");
2038         first += 2;
2039         break;
2040       case 'd':
2041       case 'n':
2042         db.names.push_back("operator&");
2043         first += 2;
2044         break;
2045       case 'N':
2046         db.names.push_back("operator&=");
2047         first += 2;
2048         break;
2049       case 'S':
2050         db.names.push_back("operator=");
2051         first += 2;
2052         break;
2053       }
2054       break;
2055     case 'c':
2056       switch (first[1]) {
2057       case 'l':
2058         db.names.push_back("operator()");
2059         first += 2;
2060         break;
2061       case 'm':
2062         db.names.push_back("operator,");
2063         first += 2;
2064         break;
2065       case 'o':
2066         db.names.push_back("operator~");
2067         first += 2;
2068         break;
2069       case 'v': {
2070         bool try_to_parse_template_args = db.try_to_parse_template_args;
2071         db.try_to_parse_template_args = false;
2072         const char *t = parse_type(first + 2, last, db);
2073         db.try_to_parse_template_args = try_to_parse_template_args;
2074         if (t != first + 2) {
2075           if (db.names.empty())
2076             return first;
2077           db.names.back().first.insert(0, "operator ");
2078           db.parsed_ctor_dtor_cv = true;
2079           first = t;
2080         }
2081       } break;
2082       }
2083       break;
2084     case 'd':
2085       switch (first[1]) {
2086       case 'a':
2087         db.names.push_back("operator delete[]");
2088         first += 2;
2089         break;
2090       case 'e':
2091         db.names.push_back("operator*");
2092         first += 2;
2093         break;
2094       case 'l':
2095         db.names.push_back("operator delete");
2096         first += 2;
2097         break;
2098       case 'v':
2099         db.names.push_back("operator/");
2100         first += 2;
2101         break;
2102       case 'V':
2103         db.names.push_back("operator/=");
2104         first += 2;
2105         break;
2106       }
2107       break;
2108     case 'e':
2109       switch (first[1]) {
2110       case 'o':
2111         db.names.push_back("operator^");
2112         first += 2;
2113         break;
2114       case 'O':
2115         db.names.push_back("operator^=");
2116         first += 2;
2117         break;
2118       case 'q':
2119         db.names.push_back("operator==");
2120         first += 2;
2121         break;
2122       }
2123       break;
2124     case 'g':
2125       switch (first[1]) {
2126       case 'e':
2127         db.names.push_back("operator>=");
2128         first += 2;
2129         break;
2130       case 't':
2131         db.names.push_back("operator>");
2132         first += 2;
2133         break;
2134       }
2135       break;
2136     case 'i':
2137       if (first[1] == 'x') {
2138         db.names.push_back("operator[]");
2139         first += 2;
2140       }
2141       break;
2142     case 'l':
2143       switch (first[1]) {
2144       case 'e':
2145         db.names.push_back("operator<=");
2146         first += 2;
2147         break;
2148       case 'i': {
2149         const char *t = parse_source_name(first + 2, last, db);
2150         if (t != first + 2) {
2151           if (db.names.empty())
2152             return first;
2153           db.names.back().first.insert(0, "operator\"\" ");
2154           first = t;
2155         }
2156       } break;
2157       case 's':
2158         db.names.push_back("operator<<");
2159         first += 2;
2160         break;
2161       case 'S':
2162         db.names.push_back("operator<<=");
2163         first += 2;
2164         break;
2165       case 't':
2166         db.names.push_back("operator<");
2167         first += 2;
2168         break;
2169       }
2170       break;
2171     case 'm':
2172       switch (first[1]) {
2173       case 'i':
2174         db.names.push_back("operator-");
2175         first += 2;
2176         break;
2177       case 'I':
2178         db.names.push_back("operator-=");
2179         first += 2;
2180         break;
2181       case 'l':
2182         db.names.push_back("operator*");
2183         first += 2;
2184         break;
2185       case 'L':
2186         db.names.push_back("operator*=");
2187         first += 2;
2188         break;
2189       case 'm':
2190         db.names.push_back("operator--");
2191         first += 2;
2192         break;
2193       }
2194       break;
2195     case 'n':
2196       switch (first[1]) {
2197       case 'a':
2198         db.names.push_back("operator new[]");
2199         first += 2;
2200         break;
2201       case 'e':
2202         db.names.push_back("operator!=");
2203         first += 2;
2204         break;
2205       case 'g':
2206         db.names.push_back("operator-");
2207         first += 2;
2208         break;
2209       case 't':
2210         db.names.push_back("operator!");
2211         first += 2;
2212         break;
2213       case 'w':
2214         db.names.push_back("operator new");
2215         first += 2;
2216         break;
2217       }
2218       break;
2219     case 'o':
2220       switch (first[1]) {
2221       case 'o':
2222         db.names.push_back("operator||");
2223         first += 2;
2224         break;
2225       case 'r':
2226         db.names.push_back("operator|");
2227         first += 2;
2228         break;
2229       case 'R':
2230         db.names.push_back("operator|=");
2231         first += 2;
2232         break;
2233       }
2234       break;
2235     case 'p':
2236       switch (first[1]) {
2237       case 'm':
2238         db.names.push_back("operator->*");
2239         first += 2;
2240         break;
2241       case 'l':
2242         db.names.push_back("operator+");
2243         first += 2;
2244         break;
2245       case 'L':
2246         db.names.push_back("operator+=");
2247         first += 2;
2248         break;
2249       case 'p':
2250         db.names.push_back("operator++");
2251         first += 2;
2252         break;
2253       case 's':
2254         db.names.push_back("operator+");
2255         first += 2;
2256         break;
2257       case 't':
2258         db.names.push_back("operator->");
2259         first += 2;
2260         break;
2261       }
2262       break;
2263     case 'q':
2264       if (first[1] == 'u') {
2265         db.names.push_back("operator?");
2266         first += 2;
2267       }
2268       break;
2269     case 'r':
2270       switch (first[1]) {
2271       case 'm':
2272         db.names.push_back("operator%");
2273         first += 2;
2274         break;
2275       case 'M':
2276         db.names.push_back("operator%=");
2277         first += 2;
2278         break;
2279       case 's':
2280         db.names.push_back("operator>>");
2281         first += 2;
2282         break;
2283       case 'S':
2284         db.names.push_back("operator>>=");
2285         first += 2;
2286         break;
2287       }
2288       break;
2289     case 'v':
2290       if (std::isdigit(first[1])) {
2291         const char *t = parse_source_name(first + 2, last, db);
2292         if (t != first + 2) {
2293           if (db.names.empty())
2294             return first;
2295           db.names.back().first.insert(0, "operator ");
2296           first = t;
2297         }
2298       }
2299       break;
2300     }
2301   }
2302   return first;
2303 }
2304 
2305 template <class C>
2306 static const char *parse_integer_literal(const char *first, const char *last,
2307                                          const std::string &lit, C &db) {
2308   const char *t = parse_number(first, last);
2309   if (t != first && t != last && *t == 'E') {
2310     if (lit.size() > 3)
2311       db.names.push_back("(" + lit + ")");
2312     else
2313       db.names.emplace_back();
2314     if (*first == 'n') {
2315       db.names.back().first += '-';
2316       ++first;
2317     }
2318     db.names.back().first.append(first, t);
2319     if (lit.size() <= 3)
2320       db.names.back().first += lit;
2321     first = t + 1;
2322   }
2323   return first;
2324 }
2325 
2326 // <expr-primary> ::= L <type> <value number> E                          #
2327 // integer literal
2328 //                ::= L <type> <value float> E                           #
2329 //                floating literal
2330 //                ::= L <string type> E                                  #
2331 //                string literal
2332 //                ::= L <nullptr type> E                                 #
2333 //                nullptr literal (i.e., "LDnE")
2334 //                ::= L <type> <real-part float> _ <imag-part float> E   #
2335 //                complex floating point literal (C 2000)
2336 //                ::= L <mangled-name> E                                 #
2337 //                external name
2338 
2339 template <class C>
2340 static const char *parse_expr_primary(const char *first, const char *last,
2341                                       C &db) {
2342   if (last - first >= 4 && *first == 'L') {
2343     switch (first[1]) {
2344     case 'w': {
2345       const char *t = parse_integer_literal(first + 2, last, "wchar_t", db);
2346       if (t != first + 2)
2347         first = t;
2348     } break;
2349     case 'b':
2350       if (first[3] == 'E') {
2351         switch (first[2]) {
2352         case '0':
2353           db.names.push_back("false");
2354           first += 4;
2355           break;
2356         case '1':
2357           db.names.push_back("true");
2358           first += 4;
2359           break;
2360         }
2361       }
2362       break;
2363     case 'c': {
2364       const char *t = parse_integer_literal(first + 2, last, "char", db);
2365       if (t != first + 2)
2366         first = t;
2367     } break;
2368     case 'a': {
2369       const char *t = parse_integer_literal(first + 2, last, "signed char", db);
2370       if (t != first + 2)
2371         first = t;
2372     } break;
2373     case 'h': {
2374       const char *t =
2375           parse_integer_literal(first + 2, last, "unsigned char", db);
2376       if (t != first + 2)
2377         first = t;
2378     } break;
2379     case 's': {
2380       const char *t = parse_integer_literal(first + 2, last, "short", db);
2381       if (t != first + 2)
2382         first = t;
2383     } break;
2384     case 't': {
2385       const char *t =
2386           parse_integer_literal(first + 2, last, "unsigned short", db);
2387       if (t != first + 2)
2388         first = t;
2389     } break;
2390     case 'i': {
2391       const char *t = parse_integer_literal(first + 2, last, "", db);
2392       if (t != first + 2)
2393         first = t;
2394     } break;
2395     case 'j': {
2396       const char *t = parse_integer_literal(first + 2, last, "u", db);
2397       if (t != first + 2)
2398         first = t;
2399     } break;
2400     case 'l': {
2401       const char *t = parse_integer_literal(first + 2, last, "l", db);
2402       if (t != first + 2)
2403         first = t;
2404     } break;
2405     case 'm': {
2406       const char *t = parse_integer_literal(first + 2, last, "ul", db);
2407       if (t != first + 2)
2408         first = t;
2409     } break;
2410     case 'x': {
2411       const char *t = parse_integer_literal(first + 2, last, "ll", db);
2412       if (t != first + 2)
2413         first = t;
2414     } break;
2415     case 'y': {
2416       const char *t = parse_integer_literal(first + 2, last, "ull", db);
2417       if (t != first + 2)
2418         first = t;
2419     } break;
2420     case 'n': {
2421       const char *t = parse_integer_literal(first + 2, last, "__int128", db);
2422       if (t != first + 2)
2423         first = t;
2424     } break;
2425     case 'o': {
2426       const char *t =
2427           parse_integer_literal(first + 2, last, "unsigned __int128", db);
2428       if (t != first + 2)
2429         first = t;
2430     } break;
2431     case 'f': {
2432       const char *t = parse_floating_number<float>(first + 2, last, db);
2433       if (t != first + 2)
2434         first = t;
2435     } break;
2436     case 'd': {
2437       const char *t = parse_floating_number<double>(first + 2, last, db);
2438       if (t != first + 2)
2439         first = t;
2440     } break;
2441     case 'e': {
2442       const char *t = parse_floating_number<long double>(first + 2, last, db);
2443       if (t != first + 2)
2444         first = t;
2445     } break;
2446     case '_':
2447       if (first[2] == 'Z') {
2448         const char *t = parse_encoding(first + 3, last, db);
2449         if (t != first + 3 && t != last && *t == 'E')
2450           first = t + 1;
2451       }
2452       break;
2453     case 'T':
2454       // Invalid mangled name per
2455       //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
2456       break;
2457     default: {
2458       // might be named type
2459       const char *t = parse_type(first + 1, last, db);
2460       if (t != first + 1 && t != last) {
2461         if (*t != 'E') {
2462           const char *n = t;
2463           for (; n != last && isdigit(*n); ++n)
2464             ;
2465           if (n != t && n != last && *n == 'E') {
2466             if (db.names.empty())
2467               return first;
2468             db.names.back() =
2469                 "(" + db.names.back().move_full() + ")" + std::string(t, n);
2470             first = n + 1;
2471             break;
2472           }
2473         } else {
2474           first = t + 1;
2475           break;
2476         }
2477       }
2478     }
2479     }
2480   }
2481   return first;
2482 }
2483 
2484 static std::string base_name(std::string &s) {
2485   if (s.empty())
2486     return s;
2487   if (s == "std::string") {
2488     s = "std::basic_string<char, std::char_traits<char>, std::allocator<char> "
2489         ">";
2490     return "basic_string";
2491   }
2492   if (s == "std::istream") {
2493     s = "std::basic_istream<char, std::char_traits<char> >";
2494     return "basic_istream";
2495   }
2496   if (s == "std::ostream") {
2497     s = "std::basic_ostream<char, std::char_traits<char> >";
2498     return "basic_ostream";
2499   }
2500   if (s == "std::iostream") {
2501     s = "std::basic_iostream<char, std::char_traits<char> >";
2502     return "basic_iostream";
2503   }
2504   const char *const pf = s.data();
2505   const char *pe = pf + s.size();
2506   if (pe[-1] == '>') {
2507     unsigned c = 1;
2508     while (true) {
2509       if (--pe == pf)
2510         return std::string();
2511       if (pe[-1] == '<') {
2512         if (--c == 0) {
2513           --pe;
2514           break;
2515         }
2516       } else if (pe[-1] == '>')
2517         ++c;
2518     }
2519   }
2520   if (pe - pf <= 1)
2521     return std::string();
2522   const char *p0 = pe - 1;
2523   for (; p0 != pf; --p0) {
2524     if (*p0 == ':') {
2525       ++p0;
2526       break;
2527     }
2528   }
2529   return std::string(p0, pe);
2530 }
2531 
2532 // <ctor-dtor-name> ::= C1    # complete object constructor
2533 //                  ::= C2    # base object constructor
2534 //                  ::= C3    # complete object allocating constructor
2535 //   extension      ::= C5    # ?
2536 //                  ::= D0    # deleting destructor
2537 //                  ::= D1    # complete object destructor
2538 //                  ::= D2    # base object destructor
2539 //   extension      ::= D5    # ?
2540 
2541 template <class C>
2542 static const char *parse_ctor_dtor_name(const char *first, const char *last,
2543                                         C &db) {
2544   if (last - first >= 2 && !db.names.empty()) {
2545     switch (first[0]) {
2546     case 'C':
2547       switch (first[1]) {
2548       case '1':
2549       case '2':
2550       case '3':
2551       case '5':
2552         if (db.names.empty())
2553           return first;
2554         db.names.push_back(base_name(db.names.back().first));
2555         first += 2;
2556         db.parsed_ctor_dtor_cv = true;
2557         break;
2558       }
2559       break;
2560     case 'D':
2561       switch (first[1]) {
2562       case '0':
2563       case '1':
2564       case '2':
2565       case '5':
2566         if (db.names.empty())
2567           return first;
2568         db.names.push_back("~" + base_name(db.names.back().first));
2569         first += 2;
2570         db.parsed_ctor_dtor_cv = true;
2571         break;
2572       }
2573       break;
2574     }
2575   }
2576   return first;
2577 }
2578 
2579 // <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
2580 //                     ::= <closure-type-name>
2581 //
2582 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
2583 //
2584 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda
2585 // has no parameters
2586 
2587 template <class C>
2588 static const char *parse_unnamed_type_name(const char *first, const char *last,
2589                                            C &db) {
2590   if (last - first > 2 && first[0] == 'U') {
2591     char type = first[1];
2592     switch (type) {
2593     case 't': {
2594       db.names.push_back(std::string("'unnamed"));
2595       const char *t0 = first + 2;
2596       if (t0 == last) {
2597         db.names.pop_back();
2598         return first;
2599       }
2600       if (std::isdigit(*t0)) {
2601         const char *t1 = t0 + 1;
2602         while (t1 != last && std::isdigit(*t1))
2603           ++t1;
2604         db.names.back().first.append(t0, t1);
2605         t0 = t1;
2606       }
2607       db.names.back().first.push_back('\'');
2608       if (t0 == last || *t0 != '_') {
2609         db.names.pop_back();
2610         return first;
2611       }
2612       first = t0 + 1;
2613     } break;
2614     case 'l': {
2615       size_t lambda_pos = db.names.size();
2616       db.names.push_back(std::string("'lambda'("));
2617       const char *t0 = first + 2;
2618       if (first[2] == 'v') {
2619         db.names.back().first += ')';
2620         ++t0;
2621       } else {
2622         bool is_first_it = true;
2623         while (true) {
2624           long k0 = static_cast<long>(db.names.size());
2625           const char *t1 = parse_type(t0, last, db);
2626           long k1 = static_cast<long>(db.names.size());
2627           if (t1 == t0)
2628             break;
2629           if (k0 >= k1)
2630             return first;
2631           // If the call to parse_type above found a pack expansion
2632           // substitution, then multiple names could have been
2633           // inserted into the name table. Walk through the names,
2634           // appending each onto the lambda's parameter list.
2635           std::for_each(db.names.begin() + k0, db.names.begin() + k1,
2636                         [&](typename C::sub_type::value_type &pair) {
2637                           if (pair.empty())
2638                             return;
2639                           auto &lambda = db.names[lambda_pos].first;
2640                           if (!is_first_it)
2641                             lambda.append(", ");
2642                           is_first_it = false;
2643                           lambda.append(pair.move_full());
2644                         });
2645           db.names.erase(db.names.begin() + k0, db.names.end());
2646           t0 = t1;
2647         }
2648         if (is_first_it) {
2649           if (!db.names.empty())
2650             db.names.pop_back();
2651           return first;
2652         }
2653         if (db.names.empty() || db.names.size() - 1 != lambda_pos)
2654           return first;
2655         db.names.back().first.append(")");
2656       }
2657       if (t0 == last || *t0 != 'E') {
2658         if (!db.names.empty())
2659           db.names.pop_back();
2660         return first;
2661       }
2662       ++t0;
2663       if (t0 == last) {
2664         if (!db.names.empty())
2665           db.names.pop_back();
2666         return first;
2667       }
2668       if (std::isdigit(*t0)) {
2669         const char *t1 = t0 + 1;
2670         while (t1 != last && std::isdigit(*t1))
2671           ++t1;
2672         db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1);
2673         t0 = t1;
2674       }
2675       if (t0 == last || *t0 != '_') {
2676         if (!db.names.empty())
2677           db.names.pop_back();
2678         return first;
2679       }
2680       first = t0 + 1;
2681     } break;
2682     }
2683   }
2684   return first;
2685 }
2686 
2687 // <unqualified-name> ::= <operator-name>
2688 //                    ::= <ctor-dtor-name>
2689 //                    ::= <source-name>
2690 //                    ::= <unnamed-type-name>
2691 
2692 template <class C>
2693 static const char *parse_unqualified_name(const char *first, const char *last,
2694                                           C &db) {
2695   if (first != last) {
2696     const char *t;
2697     switch (*first) {
2698     case 'C':
2699     case 'D':
2700       t = parse_ctor_dtor_name(first, last, db);
2701       if (t != first)
2702         first = t;
2703       break;
2704     case 'U':
2705       t = parse_unnamed_type_name(first, last, db);
2706       if (t != first)
2707         first = t;
2708       break;
2709     case '1':
2710     case '2':
2711     case '3':
2712     case '4':
2713     case '5':
2714     case '6':
2715     case '7':
2716     case '8':
2717     case '9':
2718       t = parse_source_name(first, last, db);
2719       if (t != first)
2720         first = t;
2721       break;
2722     default:
2723       t = parse_operator_name(first, last, db);
2724       if (t != first)
2725         first = t;
2726       break;
2727     };
2728   }
2729   return first;
2730 }
2731 
2732 // <unscoped-name> ::= <unqualified-name>
2733 //                 ::= St <unqualified-name>   # ::std::
2734 // extension       ::= StL<unqualified-name>
2735 
2736 template <class C>
2737 static const char *parse_unscoped_name(const char *first, const char *last,
2738                                        C &db) {
2739   if (last - first >= 2) {
2740     const char *t0 = first;
2741     bool St = false;
2742     if (first[0] == 'S' && first[1] == 't') {
2743       t0 += 2;
2744       St = true;
2745       if (t0 != last && *t0 == 'L')
2746         ++t0;
2747     }
2748     const char *t1 = parse_unqualified_name(t0, last, db);
2749     if (t1 != t0) {
2750       if (St) {
2751         if (db.names.empty())
2752           return first;
2753         db.names.back().first.insert(0, "std::");
2754       }
2755       first = t1;
2756     }
2757   }
2758   return first;
2759 }
2760 
2761 // at <type>                                            # alignof (a type)
2762 
2763 template <class C>
2764 static const char *parse_alignof_type(const char *first, const char *last,
2765                                       C &db) {
2766   if (last - first >= 3 && first[0] == 'a' && first[1] == 't') {
2767     const char *t = parse_type(first + 2, last, db);
2768     if (t != first + 2) {
2769       if (db.names.empty())
2770         return first;
2771       db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2772       first = t;
2773     }
2774   }
2775   return first;
2776 }
2777 
2778 // az <expression>                                            # alignof (a
2779 // expression)
2780 
2781 template <class C>
2782 static const char *parse_alignof_expr(const char *first, const char *last,
2783                                       C &db) {
2784   if (last - first >= 3 && first[0] == 'a' && first[1] == 'z') {
2785     const char *t = parse_expression(first + 2, last, db);
2786     if (t != first + 2) {
2787       if (db.names.empty())
2788         return first;
2789       db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2790       first = t;
2791     }
2792   }
2793   return first;
2794 }
2795 
2796 template <class C>
2797 static const char *parse_noexcept_expression(const char *first,
2798                                              const char *last, C &db) {
2799   const char *t1 = parse_expression(first, last, db);
2800   if (t1 != first) {
2801     if (db.names.empty())
2802       return first;
2803     db.names.back().first = "noexcept (" + db.names.back().move_full() + ")";
2804     first = t1;
2805   }
2806   return first;
2807 }
2808 
2809 template <class C>
2810 static const char *parse_prefix_expression(const char *first, const char *last,
2811                                            const std::string &op,
2812                                            C &db) {
2813   const char *t1 = parse_expression(first, last, db);
2814   if (t1 != first) {
2815     if (db.names.empty())
2816       return first;
2817     db.names.back().first = op + "(" + db.names.back().move_full() + ")";
2818     first = t1;
2819   }
2820   return first;
2821 }
2822 
2823 template <class C>
2824 static const char *parse_binary_expression(const char *first, const char *last,
2825                                            const std::string &op,
2826                                            C &db) {
2827   const char *t1 = parse_expression(first, last, db);
2828   if (t1 != first) {
2829     const char *t2 = parse_expression(t1, last, db);
2830     if (t2 != t1) {
2831       if (db.names.size() < 2)
2832         return first;
2833       auto op2 = db.names.back().move_full();
2834       db.names.pop_back();
2835       auto op1 = db.names.back().move_full();
2836       auto &nm = db.names.back().first;
2837       nm.clear();
2838       if (op == ">")
2839         nm += '(';
2840       nm += "(" + op1 + ") " + op + " (" + op2 + ")";
2841       if (op == ">")
2842         nm += ')';
2843       first = t2;
2844     } else if (!db.names.empty())
2845       db.names.pop_back();
2846   }
2847   return first;
2848 }
2849 
2850 // <expression> ::= <unary operator-name> <expression>
2851 //              ::= <binary operator-name> <expression> <expression>
2852 //              ::= <ternary operator-name> <expression> <expression>
2853 //              <expression>
2854 //              ::= cl <expression>+ E                                   # call
2855 //              ::= cv <type> <expression>                               #
2856 //              conversion with one argument
2857 //              ::= cv <type> _ <expression>* E                          #
2858 //              conversion with a different number of arguments
2859 //              ::= [gs] nw <expression>* _ <type> E                     # new
2860 //              (expr-list) type
2861 //              ::= [gs] nw <expression>* _ <type> <initializer>         # new
2862 //              (expr-list) type (init)
2863 //              ::= [gs] na <expression>* _ <type> E                     # new[]
2864 //              (expr-list) type
2865 //              ::= [gs] na <expression>* _ <type> <initializer>         # new[]
2866 //              (expr-list) type (init)
2867 //              ::= [gs] dl <expression>                                 #
2868 //              delete expression
2869 //              ::= [gs] da <expression>                                 #
2870 //              delete[] expression
2871 //              ::= pp_ <expression>                                     #
2872 //              prefix ++
2873 //              ::= mm_ <expression>                                     #
2874 //              prefix --
2875 //              ::= ti <type>                                            #
2876 //              typeid (type)
2877 //              ::= te <expression>                                      #
2878 //              typeid (expression)
2879 //              ::= dc <type> <expression>                               #
2880 //              dynamic_cast<type> (expression)
2881 //              ::= sc <type> <expression>                               #
2882 //              static_cast<type> (expression)
2883 //              ::= cc <type> <expression>                               #
2884 //              const_cast<type> (expression)
2885 //              ::= rc <type> <expression>                               #
2886 //              reinterpret_cast<type> (expression)
2887 //              ::= st <type>                                            #
2888 //              sizeof (a type)
2889 //              ::= sz <expression>                                      #
2890 //              sizeof (an expression)
2891 //              ::= at <type>                                            #
2892 //              alignof (a type)
2893 //              ::= az <expression>                                      #
2894 //              alignof (an expression)
2895 //              ::= nx <expression>                                      #
2896 //              noexcept (expression)
2897 //              ::= <template-param>
2898 //              ::= <function-param>
2899 //              ::= dt <expression> <unresolved-name>                    #
2900 //              expr.name
2901 //              ::= pt <expression> <unresolved-name>                    #
2902 //              expr->name
2903 //              ::= ds <expression> <expression>                         #
2904 //              expr.*expr
2905 //              ::= sZ <template-param>                                  # size
2906 //              of a parameter pack
2907 //              ::= sZ <function-param>                                  # size
2908 //              of a function parameter pack
2909 //              ::= sp <expression>                                      # pack
2910 //              expansion
2911 //              ::= tw <expression>                                      # throw
2912 //              expression
2913 //              ::= tr                                                   # throw
2914 //              with no operand (rethrow)
2915 //              ::= <unresolved-name>                                    # f(p),
2916 //              N::f(p), ::f(p),
2917 //                                                                       #
2918 //                                                                       freestanding
2919 //                                                                       dependent
2920 //                                                                       name
2921 //                                                                       (e.g.,
2922 //                                                                       T::x),
2923 //                                                                       #
2924 //                                                                       objectless
2925 //                                                                       nonstatic
2926 //                                                                       member
2927 //                                                                       reference
2928 //              ::= <expr-primary>
2929 
2930 template <class C>
2931 static const char *parse_expression(const char *first, const char *last,
2932                                     C &db) {
2933   if (last - first >= 2) {
2934     const char *t = first;
2935     bool parsed_gs = false;
2936     if (last - first >= 4 && t[0] == 'g' && t[1] == 's') {
2937       t += 2;
2938       parsed_gs = true;
2939     }
2940     switch (*t) {
2941     case 'L':
2942       first = parse_expr_primary(first, last, db);
2943       break;
2944     case 'T':
2945       first = parse_template_param(first, last, db);
2946       break;
2947     case 'f':
2948       first = parse_function_param(first, last, db);
2949       break;
2950     case 'a':
2951       switch (t[1]) {
2952       case 'a':
2953         t = parse_binary_expression(first + 2, last, "&&", db);
2954         if (t != first + 2)
2955           first = t;
2956         break;
2957       case 'd':
2958         t = parse_prefix_expression(first + 2, last, "&", db);
2959         if (t != first + 2)
2960           first = t;
2961         break;
2962       case 'n':
2963         t = parse_binary_expression(first + 2, last, "&", db);
2964         if (t != first + 2)
2965           first = t;
2966         break;
2967       case 'N':
2968         t = parse_binary_expression(first + 2, last, "&=", db);
2969         if (t != first + 2)
2970           first = t;
2971         break;
2972       case 'S':
2973         t = parse_binary_expression(first + 2, last, "=", db);
2974         if (t != first + 2)
2975           first = t;
2976         break;
2977       case 't':
2978         first = parse_alignof_type(first, last, db);
2979         break;
2980       case 'z':
2981         first = parse_alignof_expr(first, last, db);
2982         break;
2983       }
2984       break;
2985     case 'c':
2986       switch (t[1]) {
2987       case 'c':
2988         first = parse_const_cast_expr(first, last, db);
2989         break;
2990       case 'l':
2991         first = parse_call_expr(first, last, db);
2992         break;
2993       case 'm':
2994         t = parse_binary_expression(first + 2, last, ",", db);
2995         if (t != first + 2)
2996           first = t;
2997         break;
2998       case 'o':
2999         t = parse_prefix_expression(first + 2, last, "~", db);
3000         if (t != first + 2)
3001           first = t;
3002         break;
3003       case 'v':
3004         first = parse_conversion_expr(first, last, db);
3005         break;
3006       }
3007       break;
3008     case 'd':
3009       switch (t[1]) {
3010       case 'a': {
3011         const char *t1 = parse_expression(t + 2, last, db);
3012         if (t1 != t + 2) {
3013           if (db.names.empty())
3014             return first;
3015           db.names.back().first =
3016               (parsed_gs ? std::string("::") : std::string()) + "delete[] " +
3017               db.names.back().move_full();
3018           first = t1;
3019         }
3020       } break;
3021       case 'c':
3022         first = parse_dynamic_cast_expr(first, last, db);
3023         break;
3024       case 'e':
3025         t = parse_prefix_expression(first + 2, last, "*", db);
3026         if (t != first + 2)
3027           first = t;
3028         break;
3029       case 'l': {
3030         const char *t1 = parse_expression(t + 2, last, db);
3031         if (t1 != t + 2) {
3032           if (db.names.empty())
3033             return first;
3034           db.names.back().first =
3035               (parsed_gs ? std::string("::") : std::string()) + "delete " +
3036               db.names.back().move_full();
3037           first = t1;
3038         }
3039       } break;
3040       case 'n':
3041         return parse_unresolved_name(first, last, db);
3042       case 's':
3043         first = parse_dot_star_expr(first, last, db);
3044         break;
3045       case 't':
3046         first = parse_dot_expr(first, last, db);
3047         break;
3048       case 'v':
3049         t = parse_binary_expression(first + 2, last, "/", db);
3050         if (t != first + 2)
3051           first = t;
3052         break;
3053       case 'V':
3054         t = parse_binary_expression(first + 2, last, "/=", db);
3055         if (t != first + 2)
3056           first = t;
3057         break;
3058       }
3059       break;
3060     case 'e':
3061       switch (t[1]) {
3062       case 'o':
3063         t = parse_binary_expression(first + 2, last, "^", db);
3064         if (t != first + 2)
3065           first = t;
3066         break;
3067       case 'O':
3068         t = parse_binary_expression(first + 2, last, "^=", db);
3069         if (t != first + 2)
3070           first = t;
3071         break;
3072       case 'q':
3073         t = parse_binary_expression(first + 2, last, "==", db);
3074         if (t != first + 2)
3075           first = t;
3076         break;
3077       }
3078       break;
3079     case 'g':
3080       switch (t[1]) {
3081       case 'e':
3082         t = parse_binary_expression(first + 2, last, ">=", db);
3083         if (t != first + 2)
3084           first = t;
3085         break;
3086       case 't':
3087         t = parse_binary_expression(first + 2, last, ">", db);
3088         if (t != first + 2)
3089           first = t;
3090         break;
3091       }
3092       break;
3093     case 'i':
3094       if (t[1] == 'x') {
3095         const char *t1 = parse_expression(first + 2, last, db);
3096         if (t1 != first + 2) {
3097           const char *t2 = parse_expression(t1, last, db);
3098           if (t2 != t1) {
3099             if (db.names.size() < 2)
3100               return first;
3101             auto op2 = db.names.back().move_full();
3102             db.names.pop_back();
3103             auto op1 = db.names.back().move_full();
3104             db.names.back() = "(" + op1 + ")[" + op2 + "]";
3105             first = t2;
3106           } else if (!db.names.empty())
3107             db.names.pop_back();
3108         }
3109       }
3110       break;
3111     case 'l':
3112       switch (t[1]) {
3113       case 'e':
3114         t = parse_binary_expression(first + 2, last, "<=", db);
3115         if (t != first + 2)
3116           first = t;
3117         break;
3118       case 's':
3119         t = parse_binary_expression(first + 2, last, "<<", db);
3120         if (t != first + 2)
3121           first = t;
3122         break;
3123       case 'S':
3124         t = parse_binary_expression(first + 2, last, "<<=", db);
3125         if (t != first + 2)
3126           first = t;
3127         break;
3128       case 't':
3129         t = parse_binary_expression(first + 2, last, "<", db);
3130         if (t != first + 2)
3131           first = t;
3132         break;
3133       }
3134       break;
3135     case 'm':
3136       switch (t[1]) {
3137       case 'i':
3138         t = parse_binary_expression(first + 2, last, "-", db);
3139         if (t != first + 2)
3140           first = t;
3141         break;
3142       case 'I':
3143         t = parse_binary_expression(first + 2, last, "-=", db);
3144         if (t != first + 2)
3145           first = t;
3146         break;
3147       case 'l':
3148         t = parse_binary_expression(first + 2, last, "*", db);
3149         if (t != first + 2)
3150           first = t;
3151         break;
3152       case 'L':
3153         t = parse_binary_expression(first + 2, last, "*=", db);
3154         if (t != first + 2)
3155           first = t;
3156         break;
3157       case 'm':
3158         if (first + 2 != last && first[2] == '_') {
3159           t = parse_prefix_expression(first + 3, last, "--", db);
3160           if (t != first + 3)
3161             first = t;
3162         } else {
3163           const char *t1 = parse_expression(first + 2, last, db);
3164           if (t1 != first + 2) {
3165             if (db.names.empty())
3166               return first;
3167             db.names.back() = "(" + db.names.back().move_full() + ")--";
3168             first = t1;
3169           }
3170         }
3171         break;
3172       }
3173       break;
3174     case 'n':
3175       switch (t[1]) {
3176       case 'a':
3177       case 'w':
3178         first = parse_new_expr(first, last, db);
3179         break;
3180       case 'e':
3181         t = parse_binary_expression(first + 2, last, "!=", db);
3182         if (t != first + 2)
3183           first = t;
3184         break;
3185       case 'g':
3186         t = parse_prefix_expression(first + 2, last, "-", db);
3187         if (t != first + 2)
3188           first = t;
3189         break;
3190       case 't':
3191         t = parse_prefix_expression(first + 2, last, "!", db);
3192         if (t != first + 2)
3193           first = t;
3194         break;
3195       case 'x':
3196         t = parse_noexcept_expression(first + 2, last, db);
3197         if (t != first + 2)
3198           first = t;
3199         break;
3200       }
3201       break;
3202     case 'o':
3203       switch (t[1]) {
3204       case 'n':
3205         return parse_unresolved_name(first, last, db);
3206       case 'o':
3207         t = parse_binary_expression(first + 2, last, "||", db);
3208         if (t != first + 2)
3209           first = t;
3210         break;
3211       case 'r':
3212         t = parse_binary_expression(first + 2, last, "|", db);
3213         if (t != first + 2)
3214           first = t;
3215         break;
3216       case 'R':
3217         t = parse_binary_expression(first + 2, last, "|=", db);
3218         if (t != first + 2)
3219           first = t;
3220         break;
3221       }
3222       break;
3223     case 'p':
3224       switch (t[1]) {
3225       case 'm':
3226         t = parse_binary_expression(first + 2, last, "->*", db);
3227         if (t != first + 2)
3228           first = t;
3229         break;
3230       case 'l':
3231         t = parse_binary_expression(first + 2, last, "+", db);
3232         if (t != first + 2)
3233           first = t;
3234         break;
3235       case 'L':
3236         t = parse_binary_expression(first + 2, last, "+=", db);
3237         if (t != first + 2)
3238           first = t;
3239         break;
3240       case 'p':
3241         if (first + 2 != last && first[2] == '_') {
3242           t = parse_prefix_expression(first + 3, last, "++", db);
3243           if (t != first + 3)
3244             first = t;
3245         } else {
3246           const char *t1 = parse_expression(first + 2, last, db);
3247           if (t1 != first + 2) {
3248             if (db.names.empty())
3249               return first;
3250             db.names.back() = "(" + db.names.back().move_full() + ")++";
3251             first = t1;
3252           }
3253         }
3254         break;
3255       case 's':
3256         t = parse_prefix_expression(first + 2, last, "+", db);
3257         if (t != first + 2)
3258           first = t;
3259         break;
3260       case 't':
3261         first = parse_arrow_expr(first, last, db);
3262         break;
3263       }
3264       break;
3265     case 'q':
3266       if (t[1] == 'u') {
3267         const char *t1 = parse_expression(first + 2, last, db);
3268         if (t1 != first + 2) {
3269           const char *t2 = parse_expression(t1, last, db);
3270           if (t2 != t1) {
3271             const char *t3 = parse_expression(t2, last, db);
3272             if (t3 != t2) {
3273               if (db.names.size() < 3)
3274                 return first;
3275               auto op3 = db.names.back().move_full();
3276               db.names.pop_back();
3277               auto op2 = db.names.back().move_full();
3278               db.names.pop_back();
3279               auto op1 = db.names.back().move_full();
3280               db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")";
3281               first = t3;
3282             } else {
3283               if (db.names.size() < 2)
3284                 return first;
3285               db.names.pop_back();
3286               db.names.pop_back();
3287             }
3288           } else if (!db.names.empty())
3289             db.names.pop_back();
3290         }
3291       }
3292       break;
3293     case 'r':
3294       switch (t[1]) {
3295       case 'c':
3296         first = parse_reinterpret_cast_expr(first, last, db);
3297         break;
3298       case 'm':
3299         t = parse_binary_expression(first + 2, last, "%", db);
3300         if (t != first + 2)
3301           first = t;
3302         break;
3303       case 'M':
3304         t = parse_binary_expression(first + 2, last, "%=", db);
3305         if (t != first + 2)
3306           first = t;
3307         break;
3308       case 's':
3309         t = parse_binary_expression(first + 2, last, ">>", db);
3310         if (t != first + 2)
3311           first = t;
3312         break;
3313       case 'S':
3314         t = parse_binary_expression(first + 2, last, ">>=", db);
3315         if (t != first + 2)
3316           first = t;
3317         break;
3318       }
3319       break;
3320     case 's':
3321       switch (t[1]) {
3322       case 'c':
3323         first = parse_static_cast_expr(first, last, db);
3324         break;
3325       case 'p':
3326         first = parse_pack_expansion(first, last, db);
3327         break;
3328       case 'r':
3329         return parse_unresolved_name(first, last, db);
3330       case 't':
3331         first = parse_sizeof_type_expr(first, last, db);
3332         break;
3333       case 'z':
3334         first = parse_sizeof_expr_expr(first, last, db);
3335         break;
3336       case 'Z':
3337         if (last - t >= 3) {
3338           switch (t[2]) {
3339           case 'T':
3340             first = parse_sizeof_param_pack_expr(first, last, db);
3341             break;
3342           case 'f':
3343             first = parse_sizeof_function_param_pack_expr(first, last, db);
3344             break;
3345           }
3346         }
3347         break;
3348       }
3349       break;
3350     case 't':
3351       switch (t[1]) {
3352       case 'e':
3353       case 'i':
3354         first = parse_typeid_expr(first, last, db);
3355         break;
3356       case 'r':
3357         db.names.push_back("throw");
3358         first += 2;
3359         break;
3360       case 'w':
3361         first = parse_throw_expr(first, last, db);
3362         break;
3363       }
3364       break;
3365     case '1':
3366     case '2':
3367     case '3':
3368     case '4':
3369     case '5':
3370     case '6':
3371     case '7':
3372     case '8':
3373     case '9':
3374       return parse_unresolved_name(first, last, db);
3375     }
3376   }
3377   return first;
3378 }
3379 
3380 // <template-arg> ::= <type>                                             # type
3381 // or template
3382 //                ::= X <expression> E                                   #
3383 //                expression
3384 //                ::= <expr-primary>                                     #
3385 //                simple expressions
3386 //                ::= J <template-arg>* E                                #
3387 //                argument pack
3388 //                ::= LZ <encoding> E                                    #
3389 //                extension
3390 
3391 template <class C>
3392 static const char *parse_template_arg(const char *first, const char *last,
3393                                       C &db) {
3394   if (first != last) {
3395     const char *t;
3396     switch (*first) {
3397     case 'X':
3398       t = parse_expression(first + 1, last, db);
3399       if (t != first + 1) {
3400         if (t != last && *t == 'E')
3401           first = t + 1;
3402       }
3403       break;
3404     case 'J':
3405       t = first + 1;
3406       if (t == last)
3407         return first;
3408       while (*t != 'E') {
3409         const char *t1 = parse_template_arg(t, last, db);
3410         if (t1 == t)
3411           return first;
3412         t = t1;
3413       }
3414       first = t + 1;
3415       break;
3416     case 'L':
3417       // <expr-primary> or LZ <encoding> E
3418       if (first + 1 != last && first[1] == 'Z') {
3419         t = parse_encoding(first + 2, last, db);
3420         if (t != first + 2 && t != last && *t == 'E')
3421           first = t + 1;
3422       } else
3423         first = parse_expr_primary(first, last, db);
3424       break;
3425     default:
3426       // <type>
3427       first = parse_type(first, last, db);
3428       break;
3429     }
3430   }
3431   return first;
3432 }
3433 
3434 // <template-args> ::= I <template-arg>* E
3435 //     extension, the abi says <template-arg>+
3436 
3437 template <class C>
3438 static const char *parse_template_args(const char *first, const char *last,
3439                                        C &db) {
3440   if (last - first >= 2 && *first == 'I') {
3441     if (db.tag_templates)
3442       db.template_param.back().clear();
3443     const char *t = first + 1;
3444     std::string args("<");
3445     while (*t != 'E') {
3446       if (db.tag_templates)
3447         db.template_param.emplace_back();
3448       size_t k0 = db.names.size();
3449       const char *t1 = parse_template_arg(t, last, db);
3450       size_t k1 = db.names.size();
3451       if (db.tag_templates)
3452         db.template_param.pop_back();
3453       if (t1 == t || t1 == last)
3454         return first;
3455       if (db.tag_templates) {
3456         db.template_param.back().emplace_back();
3457         for (size_t k = k0; k < k1; ++k)
3458           db.template_param.back().back().push_back(db.names[k]);
3459       }
3460       for (size_t k = k0; k < k1; ++k) {
3461         if (args.size() > 1)
3462           args += ", ";
3463         args += db.names[k].move_full();
3464       }
3465       for (; k1 > k0; --k1)
3466         if (!db.names.empty())
3467           db.names.pop_back();
3468       t = t1;
3469     }
3470     first = t + 1;
3471     if (args.back() != '>')
3472       args += ">";
3473     else
3474       args += " >";
3475     db.names.push_back(std::move(args));
3476   }
3477   return first;
3478 }
3479 
3480 // <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
3481 // <unqualified-name> E
3482 //               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
3483 //               <template-args> E
3484 //
3485 // <prefix> ::= <prefix> <unqualified-name>
3486 //          ::= <template-prefix> <template-args>
3487 //          ::= <template-param>
3488 //          ::= <decltype>
3489 //          ::= # empty
3490 //          ::= <substitution>
3491 //          ::= <prefix> <data-member-prefix>
3492 //  extension ::= L
3493 //
3494 // <template-prefix> ::= <prefix> <template unqualified-name>
3495 //                   ::= <template-param>
3496 //                   ::= <substitution>
3497 
3498 template <class C>
3499 static const char *parse_nested_name(const char *first, const char *last, C &db,
3500                                      bool *ends_with_template_args) {
3501   if (first != last && *first == 'N') {
3502     unsigned cv;
3503     const char *t0 = parse_cv_qualifiers(first + 1, last, cv);
3504     if (t0 == last)
3505       return first;
3506     db.ref = 0;
3507     if (*t0 == 'R') {
3508       db.ref = 1;
3509       ++t0;
3510     } else if (*t0 == 'O') {
3511       db.ref = 2;
3512       ++t0;
3513     }
3514     db.names.emplace_back();
3515     if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't') {
3516       t0 += 2;
3517       db.names.back().first = "std";
3518     }
3519     if (t0 == last) {
3520       db.names.pop_back();
3521       return first;
3522     }
3523     bool pop_subs = false;
3524     bool component_ends_with_template_args = false;
3525     while (*t0 != 'E') {
3526       component_ends_with_template_args = false;
3527       const char *t1;
3528       switch (*t0) {
3529       case 'S':
3530         if (t0 + 1 != last && t0[1] == 't')
3531           goto do_parse_unqualified_name;
3532         t1 = parse_substitution(t0, last, db);
3533         if (t1 != t0 && t1 != last) {
3534           auto name = db.names.back().move_full();
3535           db.names.pop_back();
3536           if (db.names.empty())
3537             return first;
3538           if (!db.names.back().first.empty()) {
3539             db.names.back().first += "::" + name;
3540             db.subs.push_back(typename C::sub_type(1, db.names.back()));
3541           } else
3542             db.names.back().first = name;
3543           pop_subs = true;
3544           t0 = t1;
3545         } else
3546           return first;
3547         break;
3548       case 'T':
3549         t1 = parse_template_param(t0, last, db);
3550         if (t1 != t0 && t1 != last) {
3551           auto name = db.names.back().move_full();
3552           db.names.pop_back();
3553           if (db.names.empty())
3554             return first;
3555           if (!db.names.back().first.empty())
3556             db.names.back().first += "::" + name;
3557           else
3558             db.names.back().first = name;
3559           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3560           pop_subs = true;
3561           t0 = t1;
3562         } else
3563           return first;
3564         break;
3565       case 'D':
3566         if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
3567           goto do_parse_unqualified_name;
3568         t1 = parse_decltype(t0, last, db);
3569         if (t1 != t0 && t1 != last) {
3570           auto name = db.names.back().move_full();
3571           db.names.pop_back();
3572           if (db.names.empty())
3573             return first;
3574           if (!db.names.back().first.empty())
3575             db.names.back().first += "::" + name;
3576           else
3577             db.names.back().first = name;
3578           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3579           pop_subs = true;
3580           t0 = t1;
3581         } else
3582           return first;
3583         break;
3584       case 'I':
3585         t1 = parse_template_args(t0, last, db);
3586         if (t1 != t0 && t1 != last) {
3587           auto name = db.names.back().move_full();
3588           db.names.pop_back();
3589           if (db.names.empty())
3590             return first;
3591           db.names.back().first += name;
3592           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3593           t0 = t1;
3594           component_ends_with_template_args = true;
3595         } else
3596           return first;
3597         break;
3598       case 'L':
3599         if (++t0 == last)
3600           return first;
3601         break;
3602       default:
3603       do_parse_unqualified_name:
3604         t1 = parse_unqualified_name(t0, last, db);
3605         if (t1 != t0 && t1 != last) {
3606           auto name = db.names.back().move_full();
3607           db.names.pop_back();
3608           if (db.names.empty())
3609             return first;
3610           if (!db.names.back().first.empty())
3611             db.names.back().first += "::" + name;
3612           else
3613             db.names.back().first = name;
3614           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3615           pop_subs = true;
3616           t0 = t1;
3617         } else
3618           return first;
3619       }
3620     }
3621     first = t0 + 1;
3622     db.cv = cv;
3623     if (pop_subs && !db.subs.empty())
3624       db.subs.pop_back();
3625     if (ends_with_template_args)
3626       *ends_with_template_args = component_ends_with_template_args;
3627   }
3628   return first;
3629 }
3630 
3631 // <discriminator> := _ <non-negative number>      # when number < 10
3632 //                 := __ <non-negative number> _   # when number >= 10
3633 //  extension      := decimal-digit+               # at the end of string
3634 
3635 static const char *parse_discriminator(const char *first, const char *last) {
3636   // parse but ignore discriminator
3637   if (first != last) {
3638     if (*first == '_') {
3639       const char *t1 = first + 1;
3640       if (t1 != last) {
3641         if (std::isdigit(*t1))
3642           first = t1 + 1;
3643         else if (*t1 == '_') {
3644           for (++t1; t1 != last && std::isdigit(*t1); ++t1)
3645             ;
3646           if (t1 != last && *t1 == '_')
3647             first = t1 + 1;
3648         }
3649       }
3650     } else if (std::isdigit(*first)) {
3651       const char *t1 = first + 1;
3652       for (; t1 != last && std::isdigit(*t1); ++t1)
3653         ;
3654       if (t1 == last)
3655         first = last;
3656     }
3657   }
3658   return first;
3659 }
3660 
3661 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
3662 //              := Z <function encoding> E s [<discriminator>]
3663 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity
3664 //              name>
3665 
3666 template <class C>
3667 static const char *parse_local_name(const char *first, const char *last, C &db,
3668                                     bool *ends_with_template_args) {
3669   if (first != last && *first == 'Z') {
3670     const char *t = parse_encoding(first + 1, last, db);
3671     if (t != first + 1 && t != last && *t == 'E' && ++t != last) {
3672       switch (*t) {
3673       case 's':
3674         first = parse_discriminator(t + 1, last);
3675         if (db.names.empty())
3676           return first;
3677         db.names.back().first.append("::string literal");
3678         break;
3679       case 'd':
3680         if (++t != last) {
3681           const char *t1 = parse_number(t, last);
3682           if (t1 != last && *t1 == '_') {
3683             t = t1 + 1;
3684             t1 = parse_name(t, last, db, ends_with_template_args);
3685             if (t1 != t) {
3686               if (db.names.size() < 2)
3687                 return first;
3688               auto name = db.names.back().move_full();
3689               db.names.pop_back();
3690               if (db.names.empty())
3691                 return first;
3692               db.names.back().first.append("::");
3693               db.names.back().first.append(name);
3694               first = t1;
3695             } else if (!db.names.empty())
3696               db.names.pop_back();
3697           }
3698         }
3699         break;
3700       default: {
3701         const char *t1 = parse_name(t, last, db, ends_with_template_args);
3702         if (t1 != t) {
3703           // parse but ignore discriminator
3704           first = parse_discriminator(t1, last);
3705           if (db.names.size() < 2)
3706             return first;
3707           auto name = db.names.back().move_full();
3708           db.names.pop_back();
3709           if (db.names.empty())
3710             return first;
3711           db.names.back().first.append("::");
3712           db.names.back().first.append(name);
3713         } else if (!db.names.empty())
3714           db.names.pop_back();
3715       } break;
3716       }
3717     }
3718   }
3719   return first;
3720 }
3721 
3722 // <name> ::= <nested-name> // N
3723 //        ::= <local-name> # See Scope Encoding below  // Z
3724 //        ::= <unscoped-template-name> <template-args>
3725 //        ::= <unscoped-name>
3726 
3727 // <unscoped-template-name> ::= <unscoped-name>
3728 //                          ::= <substitution>
3729 
3730 template <class C>
3731 static const char *parse_name(const char *first, const char *last, C &db,
3732                               bool *ends_with_template_args) {
3733   if (last - first >= 2) {
3734     const char *t0 = first;
3735     // extension: ignore L here
3736     if (*t0 == 'L')
3737       ++t0;
3738     switch (*t0) {
3739     case 'N': {
3740       const char *t1 = parse_nested_name(t0, last, db, ends_with_template_args);
3741       if (t1 != t0)
3742         first = t1;
3743       break;
3744     }
3745     case 'Z': {
3746       const char *t1 = parse_local_name(t0, last, db, ends_with_template_args);
3747       if (t1 != t0)
3748         first = t1;
3749       break;
3750     }
3751     default: {
3752       const char *t1 = parse_unscoped_name(t0, last, db);
3753       if (t1 != t0) {
3754         if (t1 != last &&
3755             *t1 == 'I') // <unscoped-template-name> <template-args>
3756         {
3757           if (db.names.empty())
3758             return first;
3759           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3760           t0 = t1;
3761           t1 = parse_template_args(t0, last, db);
3762           if (t1 != t0) {
3763             if (db.names.size() < 2)
3764               return first;
3765             auto tmp = db.names.back().move_full();
3766             db.names.pop_back();
3767             if (db.names.empty())
3768               return first;
3769             db.names.back().first += tmp;
3770             first = t1;
3771             if (ends_with_template_args)
3772               *ends_with_template_args = true;
3773           }
3774         } else // <unscoped-name>
3775           first = t1;
3776       } else { // try <substitution> <template-args>
3777         t1 = parse_substitution(t0, last, db);
3778         if (t1 != t0 && t1 != last && *t1 == 'I') {
3779           t0 = t1;
3780           t1 = parse_template_args(t0, last, db);
3781           if (t1 != t0) {
3782             if (db.names.size() < 2)
3783               return first;
3784             auto tmp = db.names.back().move_full();
3785             db.names.pop_back();
3786             if (db.names.empty())
3787               return first;
3788             db.names.back().first += tmp;
3789             first = t1;
3790             if (ends_with_template_args)
3791               *ends_with_template_args = true;
3792           }
3793         }
3794       }
3795       break;
3796     }
3797     }
3798   }
3799   return first;
3800 }
3801 
3802 // <call-offset> ::= h <nv-offset> _
3803 //               ::= v <v-offset> _
3804 //
3805 // <nv-offset> ::= <offset number>
3806 //               # non-virtual base override
3807 //
3808 // <v-offset>  ::= <offset number> _ <virtual offset number>
3809 //               # virtual base override, with vcall offset
3810 
3811 static const char *parse_call_offset(const char *first, const char *last) {
3812   if (first != last) {
3813     switch (*first) {
3814     case 'h': {
3815       const char *t = parse_number(first + 1, last);
3816       if (t != first + 1 && t != last && *t == '_')
3817         first = t + 1;
3818     } break;
3819     case 'v': {
3820       const char *t = parse_number(first + 1, last);
3821       if (t != first + 1 && t != last && *t == '_') {
3822         const char *t2 = parse_number(++t, last);
3823         if (t2 != t && t2 != last && *t2 == '_')
3824           first = t2 + 1;
3825       }
3826     } break;
3827     }
3828   }
3829   return first;
3830 }
3831 
3832 // <special-name> ::= TV <type>    # virtual table
3833 //                ::= TT <type>    # VTT structure (construction vtable index)
3834 //                ::= TI <type>    # typeinfo structure
3835 //                ::= TS <type>    # typeinfo name (null-terminated byte string)
3836 //                ::= Tc <call-offset> <call-offset> <base encoding>
3837 //                    # base is the nominal target function of thunk
3838 //                    # first call-offset is 'this' adjustment
3839 //                    # second call-offset is result adjustment
3840 //                ::= T <call-offset> <base encoding>
3841 //                    # base is the nominal target function of thunk
3842 //                ::= GV <object name> # Guard variable for one-time
3843 //                initialization
3844 //                                     # No <type>
3845 //                ::= TW <object name> # Thread-local wrapper
3846 //                ::= TH <object name> # Thread-local initialization
3847 //      extension ::= TC <first type> <number> _ <second type> # construction
3848 //      vtable for second-in-first
3849 //      extension ::= GR <object name> # reference temporary for object
3850 
3851 template <class C>
3852 static const char *parse_special_name(const char *first, const char *last,
3853                                       C &db) {
3854   if (last - first > 2) {
3855     const char *t;
3856     switch (*first) {
3857     case 'T':
3858       switch (first[1]) {
3859       case 'V':
3860         // TV <type>    # virtual table
3861         t = parse_type(first + 2, last, db);
3862         if (t != first + 2) {
3863           if (db.names.empty())
3864             return first;
3865           db.names.back().first.insert(0, "vtable for ");
3866           first = t;
3867         }
3868         break;
3869       case 'T':
3870         // TT <type>    # VTT structure (construction vtable index)
3871         t = parse_type(first + 2, last, db);
3872         if (t != first + 2) {
3873           if (db.names.empty())
3874             return first;
3875           db.names.back().first.insert(0, "VTT for ");
3876           first = t;
3877         }
3878         break;
3879       case 'I':
3880         // TI <type>    # typeinfo structure
3881         t = parse_type(first + 2, last, db);
3882         if (t != first + 2) {
3883           if (db.names.empty())
3884             return first;
3885           db.names.back().first.insert(0, "typeinfo for ");
3886           first = t;
3887         }
3888         break;
3889       case 'S':
3890         // TS <type>    # typeinfo name (null-terminated byte string)
3891         t = parse_type(first + 2, last, db);
3892         if (t != first + 2) {
3893           if (db.names.empty())
3894             return first;
3895           db.names.back().first.insert(0, "typeinfo name for ");
3896           first = t;
3897         }
3898         break;
3899       case 'c':
3900         // Tc <call-offset> <call-offset> <base encoding>
3901         {
3902           const char *t0 = parse_call_offset(first + 2, last);
3903           if (t0 == first + 2)
3904             break;
3905           const char *t1 = parse_call_offset(t0, last);
3906           if (t1 == t0)
3907             break;
3908           t = parse_encoding(t1, last, db);
3909           if (t != t1) {
3910             if (db.names.empty())
3911               return first;
3912             db.names.back().first.insert(0, "covariant return thunk to ");
3913             first = t;
3914           }
3915         }
3916         break;
3917       case 'C':
3918         // extension ::= TC <first type> <number> _ <second type> # construction
3919         // vtable for second-in-first
3920         t = parse_type(first + 2, last, db);
3921         if (t != first + 2) {
3922           const char *t0 = parse_number(t, last);
3923           if (t0 != t && t0 != last && *t0 == '_') {
3924             const char *t1 = parse_type(++t0, last, db);
3925             if (t1 != t0) {
3926               if (db.names.size() < 2)
3927                 return first;
3928               auto left = db.names.back().move_full();
3929               db.names.pop_back();
3930               if (db.names.empty())
3931                 return first;
3932               db.names.back().first = "construction vtable for " +
3933                                       std::move(left) + "-in-" +
3934                                       db.names.back().move_full();
3935               first = t1;
3936             }
3937           }
3938         }
3939         break;
3940       case 'W':
3941         // TW <object name> # Thread-local wrapper
3942         t = parse_name(first + 2, last, db);
3943         if (t != first + 2) {
3944           if (db.names.empty())
3945             return first;
3946           db.names.back().first.insert(0, "thread-local wrapper routine for ");
3947           first = t;
3948         }
3949         break;
3950       case 'H':
3951         // TH <object name> # Thread-local initialization
3952         t = parse_name(first + 2, last, db);
3953         if (t != first + 2) {
3954           if (db.names.empty())
3955             return first;
3956           db.names.back().first.insert(
3957               0, "thread-local initialization routine for ");
3958           first = t;
3959         }
3960         break;
3961       default:
3962         // T <call-offset> <base encoding>
3963         {
3964           const char *t0 = parse_call_offset(first + 1, last);
3965           if (t0 == first + 1)
3966             break;
3967           t = parse_encoding(t0, last, db);
3968           if (t != t0) {
3969             if (db.names.empty())
3970               return first;
3971             if (first[1] == 'v') {
3972               db.names.back().first.insert(0, "virtual thunk to ");
3973               first = t;
3974             } else {
3975               db.names.back().first.insert(0, "non-virtual thunk to ");
3976               first = t;
3977             }
3978           }
3979         }
3980         break;
3981       }
3982       break;
3983     case 'G':
3984       switch (first[1]) {
3985       case 'V':
3986         // GV <object name> # Guard variable for one-time initialization
3987         t = parse_name(first + 2, last, db);
3988         if (t != first + 2) {
3989           if (db.names.empty())
3990             return first;
3991           db.names.back().first.insert(0, "guard variable for ");
3992           first = t;
3993         }
3994         break;
3995       case 'R':
3996         // extension ::= GR <object name> # reference temporary for object
3997         t = parse_name(first + 2, last, db);
3998         if (t != first + 2) {
3999           if (db.names.empty())
4000             return first;
4001           db.names.back().first.insert(0, "reference temporary for ");
4002           first = t;
4003         }
4004         break;
4005       }
4006       break;
4007     }
4008   }
4009   return first;
4010 }
4011 
4012 namespace {
4013 template <class T> class save_value {
4014   T &restore_;
4015   T original_value_;
4016 
4017 public:
4018   save_value(T &restore) : restore_(restore), original_value_(restore) {}
4019 
4020   ~save_value() { restore_ = std::move(original_value_); }
4021 
4022   save_value(const save_value &) = delete;
4023   save_value &operator=(const save_value &) = delete;
4024 };
4025 }
4026 
4027 // <encoding> ::= <function name> <bare-function-type>
4028 //            ::= <data name>
4029 //            ::= <special-name>
4030 
4031 template <class C>
4032 static const char *parse_encoding(const char *first, const char *last, C &db) {
4033   if (first != last) {
4034     save_value<decltype(db.encoding_depth)> su(db.encoding_depth);
4035     ++db.encoding_depth;
4036     save_value<decltype(db.tag_templates)> sb(db.tag_templates);
4037     if (db.encoding_depth > 1)
4038       db.tag_templates = true;
4039     save_value<decltype(db.parsed_ctor_dtor_cv)> sp(db.parsed_ctor_dtor_cv);
4040     db.parsed_ctor_dtor_cv = false;
4041     switch (*first) {
4042     case 'G':
4043     case 'T':
4044       first = parse_special_name(first, last, db);
4045       break;
4046     default: {
4047       bool ends_with_template_args = false;
4048       const char *t = parse_name(first, last, db, &ends_with_template_args);
4049       unsigned cv = db.cv;
4050       unsigned ref = db.ref;
4051       if (t != first) {
4052         if (t != last && *t != 'E' && *t != '.') {
4053           save_value<bool> sb2(db.tag_templates);
4054           db.tag_templates = false;
4055           const char *t2;
4056           std::string ret2;
4057           if (db.names.empty())
4058             return first;
4059           const std::string &nm = db.names.back().first;
4060           if (nm.empty())
4061             return first;
4062           if (!db.parsed_ctor_dtor_cv && ends_with_template_args) {
4063             t2 = parse_type(t, last, db);
4064             if (t2 == t)
4065               return first;
4066             if (db.names.size() < 2)
4067               return first;
4068             auto ret1 = std::move(db.names.back().first);
4069             ret2 = std::move(db.names.back().second);
4070             if (ret2.empty())
4071               ret1 += ' ';
4072             db.names.pop_back();
4073             if (db.names.empty())
4074               return first;
4075 
4076             db.names.back().first.insert(0, ret1);
4077             t = t2;
4078           }
4079           db.names.back().first += '(';
4080           if (t != last && *t == 'v') {
4081             ++t;
4082           } else {
4083             bool first_arg = true;
4084             while (true) {
4085               size_t k0 = db.names.size();
4086               t2 = parse_type(t, last, db);
4087               size_t k1 = db.names.size();
4088               if (t2 == t)
4089                 break;
4090               if (k1 > k0) {
4091                 std::string tmp;
4092                 for (size_t k = k0; k < k1; ++k) {
4093                   if (!tmp.empty())
4094                     tmp += ", ";
4095                   tmp += db.names[k].move_full();
4096                 }
4097                 for (size_t k = k0; k < k1; ++k) {
4098                   if (db.names.empty())
4099                     return first;
4100                   db.names.pop_back();
4101                 }
4102                 if (!tmp.empty()) {
4103                   if (db.names.empty())
4104                     return first;
4105                   if (!first_arg)
4106                     db.names.back().first += ", ";
4107                   else
4108                     first_arg = false;
4109                   db.names.back().first += tmp;
4110                 }
4111               }
4112               t = t2;
4113             }
4114           }
4115           if (db.names.empty())
4116             return first;
4117           db.names.back().first += ')';
4118           if (cv & CV_const)
4119             db.names.back().first.append(" const");
4120           if (cv & CV_volatile)
4121             db.names.back().first.append(" volatile");
4122           if (cv & CV_restrict)
4123             db.names.back().first.append(" restrict");
4124           if (ref == 1)
4125             db.names.back().first.append(" &");
4126           else if (ref == 2)
4127             db.names.back().first.append(" &&");
4128           db.names.back().first += ret2;
4129           first = t;
4130         } else
4131           first = t;
4132       }
4133       break;
4134     }
4135     }
4136   }
4137   return first;
4138 }
4139 
4140 // _block_invoke
4141 // _block_invoke<decimal-digit>+
4142 // _block_invoke_<decimal-digit>+
4143 
4144 template <class C>
4145 static const char *parse_block_invoke(const char *first, const char *last,
4146                                       C &db) {
4147   if (last - first >= 13) {
4148     const char test[] = "_block_invoke";
4149     const char *t = first;
4150     for (int i = 0; i < 13; ++i, ++t) {
4151       if (*t != test[i])
4152         return first;
4153     }
4154     if (t != last) {
4155       if (*t == '_') {
4156         // must have at least 1 decimal digit
4157         if (++t == last || !std::isdigit(*t))
4158           return first;
4159         ++t;
4160       }
4161       // parse zero or more digits
4162       while (t != last && isdigit(*t))
4163         ++t;
4164     }
4165     if (db.names.empty())
4166       return first;
4167     db.names.back().first.insert(0, "invocation function for block in ");
4168     first = t;
4169   }
4170   return first;
4171 }
4172 
4173 // extension
4174 // <dot-suffix> := .<anything and everything>
4175 
4176 template <class C>
4177 static const char *parse_dot_suffix(const char *first, const char *last,
4178                                     C &db) {
4179   if (first != last && *first == '.') {
4180     if (db.names.empty())
4181       return first;
4182     db.names.back().first += " (" + std::string(first, last) + ")";
4183     first = last;
4184   }
4185   return first;
4186 }
4187 
4188 // <block-involcaton-function> ___Z<encoding>_block_invoke
4189 // <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+
4190 // <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+
4191 // <mangled-name> ::= _Z<encoding>
4192 //                ::= <type>
4193 
4194 template <class C>
4195 static void demangle(const char *first, const char *last, C &db, int &status) {
4196   if (first >= last) {
4197     status = invalid_mangled_name;
4198     return;
4199   }
4200   if (*first == '_') {
4201     if (last - first >= 4) {
4202       if (first[1] == 'Z') {
4203         const char *t = parse_encoding(first + 2, last, db);
4204         if (t != first + 2 && t != last && *t == '.')
4205           t = parse_dot_suffix(t, last, db);
4206         if (t != last)
4207           status = invalid_mangled_name;
4208       } else if (first[1] == '_' && first[2] == '_' && first[3] == 'Z') {
4209         const char *t = parse_encoding(first + 4, last, db);
4210         if (t != first + 4 && t != last) {
4211           const char *t1 = parse_block_invoke(t, last, db);
4212           if (t1 != last)
4213             status = invalid_mangled_name;
4214         } else
4215           status = invalid_mangled_name;
4216       } else
4217         status = invalid_mangled_name;
4218     } else
4219       status = invalid_mangled_name;
4220   } else {
4221     const char *t = parse_type(first, last, db);
4222     if (t != last)
4223       status = invalid_mangled_name;
4224   }
4225   if (status == success && db.names.empty())
4226     status = invalid_mangled_name;
4227 }
4228 
4229 namespace {
4230 template <class StrT> struct string_pair {
4231   StrT first;
4232   StrT second;
4233 
4234   string_pair() = default;
4235   string_pair(StrT f) : first(std::move(f)) {}
4236   string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
4237   template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {}
4238 
4239   size_t size() const { return first.size() + second.size(); }
4240   bool empty() const { return first.empty() && second.empty(); }
4241   StrT full() const { return first + second; }
4242   StrT move_full() { return std::move(first) + std::move(second); }
4243 };
4244 
4245 struct Db {
4246   typedef std::vector<string_pair<std::string>> sub_type;
4247   typedef std::vector<sub_type> template_param_type;
4248   sub_type names;
4249   template_param_type subs;
4250   std::vector<template_param_type> template_param;
4251   unsigned cv = 0;
4252   unsigned ref = 0;
4253   unsigned encoding_depth = 0;
4254   bool parsed_ctor_dtor_cv = false;
4255   bool tag_templates = true;
4256   bool fix_forward_references = false;
4257   bool try_to_parse_template_args = true;
4258 
4259   Db() : subs(0, names), template_param(0, subs) {}
4260 };
4261 }
4262 
4263 char *llvm::itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
4264                             int *status) {
4265   if (mangled_name == nullptr || (buf != nullptr && n == nullptr)) {
4266     if (status)
4267       *status = invalid_args;
4268     return nullptr;
4269   }
4270   size_t internal_size = buf != nullptr ? *n : 0;
4271   Db db;
4272   db.template_param.emplace_back();
4273   int internal_status = success;
4274   size_t len = std::strlen(mangled_name);
4275   demangle(mangled_name, mangled_name + len, db, internal_status);
4276   if (internal_status == success && db.fix_forward_references &&
4277       !db.template_param.empty() && !db.template_param.front().empty()) {
4278     db.fix_forward_references = false;
4279     db.tag_templates = false;
4280     db.names.clear();
4281     db.subs.clear();
4282     demangle(mangled_name, mangled_name + len, db, internal_status);
4283     if (db.fix_forward_references)
4284       internal_status = invalid_mangled_name;
4285   }
4286   if (internal_status == success) {
4287     size_t sz = db.names.back().size() + 1;
4288     if (sz > internal_size) {
4289       char *newbuf = static_cast<char *>(std::realloc(buf, sz));
4290       if (newbuf == nullptr) {
4291         internal_status = memory_alloc_failure;
4292         buf = nullptr;
4293       } else {
4294         buf = newbuf;
4295         if (n != nullptr)
4296           *n = sz;
4297       }
4298     }
4299     if (buf != nullptr) {
4300       db.names.back().first += db.names.back().second;
4301       std::memcpy(buf, db.names.back().first.data(), sz - 1);
4302       buf[sz - 1] = char(0);
4303     }
4304   } else
4305     buf = nullptr;
4306   if (status)
4307     *status = internal_status;
4308   return buf;
4309 }
4310