contrib/llvm/lib/Demangle/ItaniumDemangle.cpp

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