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