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