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