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