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

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