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