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