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