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