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