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