contrib/llvm/tools/lldb/source/Core/CxaDemangle.cpp

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