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