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         // falls 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     if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_') {
2529       return std::string();
2530     }
2531   }
2532   return std::string(p0, pe);
2533 }
2534
2535 // <ctor-dtor-name> ::= C1    # complete object constructor
2536 //                  ::= C2    # base object constructor
2537 //                  ::= C3    # complete object allocating constructor
2538 //   extension      ::= C5    # ?
2539 //                  ::= D0    # deleting destructor
2540 //                  ::= D1    # complete object destructor
2541 //                  ::= D2    # base object destructor
2542 //   extension      ::= D5    # ?
2543
2544 template <class C>
2545 static const char *parse_ctor_dtor_name(const char *first, const char *last,
2546                                         C &db) {
2547   if (last - first >= 2 && !db.names.empty()) {
2548     switch (first[0]) {
2549     case 'C':
2550       switch (first[1]) {
2551       case '1':
2552       case '2':
2553       case '3':
2554       case '5':
2555         if (db.names.empty())
2556           return first;
2557         db.names.push_back(base_name(db.names.back().first));
2558         first += 2;
2559         db.parsed_ctor_dtor_cv = true;
2560         break;
2561       }
2562       break;
2563     case 'D':
2564       switch (first[1]) {
2565       case '0':
2566       case '1':
2567       case '2':
2568       case '5':
2569         if (db.names.empty())
2570           return first;
2571         db.names.push_back("~" + base_name(db.names.back().first));
2572         first += 2;
2573         db.parsed_ctor_dtor_cv = true;
2574         break;
2575       }
2576       break;
2577     }
2578   }
2579   return first;
2580 }
2581
2582 // <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
2583 //                     ::= <closure-type-name>
2584 //
2585 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
2586 //
2587 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda
2588 // has no parameters
2589
2590 template <class C>
2591 static const char *parse_unnamed_type_name(const char *first, const char *last,
2592                                            C &db) {
2593   if (last - first > 2 && first[0] == 'U') {
2594     char type = first[1];
2595     switch (type) {
2596     case 't': {
2597       db.names.push_back(std::string("'unnamed"));
2598       const char *t0 = first + 2;
2599       if (t0 == last) {
2600         db.names.pop_back();
2601         return first;
2602       }
2603       if (std::isdigit(*t0)) {
2604         const char *t1 = t0 + 1;
2605         while (t1 != last && std::isdigit(*t1))
2606           ++t1;
2607         db.names.back().first.append(t0, t1);
2608         t0 = t1;
2609       }
2610       db.names.back().first.push_back('\'');
2611       if (t0 == last || *t0 != '_') {
2612         db.names.pop_back();
2613         return first;
2614       }
2615       first = t0 + 1;
2616     } break;
2617     case 'l': {
2618       size_t lambda_pos = db.names.size();
2619       db.names.push_back(std::string("'lambda'("));
2620       const char *t0 = first + 2;
2621       if (first[2] == 'v') {
2622         db.names.back().first += ')';
2623         ++t0;
2624       } else {
2625         bool is_first_it = true;
2626         while (true) {
2627           long k0 = static_cast<long>(db.names.size());
2628           const char *t1 = parse_type(t0, last, db);
2629           long k1 = static_cast<long>(db.names.size());
2630           if (t1 == t0)
2631             break;
2632           if (k0 >= k1)
2633             return first;
2634           // If the call to parse_type above found a pack expansion
2635           // substitution, then multiple names could have been
2636           // inserted into the name table. Walk through the names,
2637           // appending each onto the lambda's parameter list.
2638           std::for_each(db.names.begin() + k0, db.names.begin() + k1,
2639                         [&](typename C::sub_type::value_type &pair) {
2640                           if (pair.empty())
2641                             return;
2642                           auto &lambda = db.names[lambda_pos].first;
2643                           if (!is_first_it)
2644                             lambda.append(", ");
2645                           is_first_it = false;
2646                           lambda.append(pair.move_full());
2647                         });
2648           db.names.erase(db.names.begin() + k0, db.names.end());
2649           t0 = t1;
2650         }
2651         if (is_first_it) {
2652           if (!db.names.empty())
2653             db.names.pop_back();
2654           return first;
2655         }
2656         if (db.names.empty() || db.names.size() - 1 != lambda_pos)
2657           return first;
2658         db.names.back().first.append(")");
2659       }
2660       if (t0 == last || *t0 != 'E') {
2661         if (!db.names.empty())
2662           db.names.pop_back();
2663         return first;
2664       }
2665       ++t0;
2666       if (t0 == last) {
2667         if (!db.names.empty())
2668           db.names.pop_back();
2669         return first;
2670       }
2671       if (std::isdigit(*t0)) {
2672         const char *t1 = t0 + 1;
2673         while (t1 != last && std::isdigit(*t1))
2674           ++t1;
2675         db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1);
2676         t0 = t1;
2677       }
2678       if (t0 == last || *t0 != '_') {
2679         if (!db.names.empty())
2680           db.names.pop_back();
2681         return first;
2682       }
2683       first = t0 + 1;
2684     } break;
2685     }
2686   }
2687   return first;
2688 }
2689
2690 // <unqualified-name> ::= <operator-name>
2691 //                    ::= <ctor-dtor-name>
2692 //                    ::= <source-name>
2693 //                    ::= <unnamed-type-name>
2694
2695 template <class C>
2696 static const char *parse_unqualified_name(const char *first, const char *last,
2697                                           C &db) {
2698   if (first != last) {
2699     const char *t;
2700     switch (*first) {
2701     case 'C':
2702     case 'D':
2703       t = parse_ctor_dtor_name(first, last, db);
2704       if (t != first)
2705         first = t;
2706       break;
2707     case 'U':
2708       t = parse_unnamed_type_name(first, last, db);
2709       if (t != first)
2710         first = t;
2711       break;
2712     case '1':
2713     case '2':
2714     case '3':
2715     case '4':
2716     case '5':
2717     case '6':
2718     case '7':
2719     case '8':
2720     case '9':
2721       t = parse_source_name(first, last, db);
2722       if (t != first)
2723         first = t;
2724       break;
2725     default:
2726       t = parse_operator_name(first, last, db);
2727       if (t != first)
2728         first = t;
2729       break;
2730     };
2731   }
2732   return first;
2733 }
2734
2735 // <unscoped-name> ::= <unqualified-name>
2736 //                 ::= St <unqualified-name>   # ::std::
2737 // extension       ::= StL<unqualified-name>
2738
2739 template <class C>
2740 static const char *parse_unscoped_name(const char *first, const char *last,
2741                                        C &db) {
2742   if (last - first >= 2) {
2743     const char *t0 = first;
2744     bool St = false;
2745     if (first[0] == 'S' && first[1] == 't') {
2746       t0 += 2;
2747       St = true;
2748       if (t0 != last && *t0 == 'L')
2749         ++t0;
2750     }
2751     const char *t1 = parse_unqualified_name(t0, last, db);
2752     if (t1 != t0) {
2753       if (St) {
2754         if (db.names.empty())
2755           return first;
2756         db.names.back().first.insert(0, "std::");
2757       }
2758       first = t1;
2759     }
2760   }
2761   return first;
2762 }
2763
2764 // at <type>                                            # alignof (a type)
2765
2766 template <class C>
2767 static const char *parse_alignof_type(const char *first, const char *last,
2768                                       C &db) {
2769   if (last - first >= 3 && first[0] == 'a' && first[1] == 't') {
2770     const char *t = parse_type(first + 2, last, db);
2771     if (t != first + 2) {
2772       if (db.names.empty())
2773         return first;
2774       db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2775       first = t;
2776     }
2777   }
2778   return first;
2779 }
2780
2781 // az <expression>                                            # alignof (a
2782 // expression)
2783
2784 template <class C>
2785 static const char *parse_alignof_expr(const char *first, const char *last,
2786                                       C &db) {
2787   if (last - first >= 3 && first[0] == 'a' && first[1] == 'z') {
2788     const char *t = parse_expression(first + 2, last, db);
2789     if (t != first + 2) {
2790       if (db.names.empty())
2791         return first;
2792       db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
2793       first = t;
2794     }
2795   }
2796   return first;
2797 }
2798
2799 template <class C>
2800 static const char *parse_noexcept_expression(const char *first,
2801                                              const char *last, C &db) {
2802   const char *t1 = parse_expression(first, last, db);
2803   if (t1 != first) {
2804     if (db.names.empty())
2805       return first;
2806     db.names.back().first = "noexcept (" + db.names.back().move_full() + ")";
2807     first = t1;
2808   }
2809   return first;
2810 }
2811
2812 template <class C>
2813 static const char *parse_prefix_expression(const char *first, const char *last,
2814                                            const std::string &op,
2815                                            C &db) {
2816   const char *t1 = parse_expression(first, last, db);
2817   if (t1 != first) {
2818     if (db.names.empty())
2819       return first;
2820     db.names.back().first = op + "(" + db.names.back().move_full() + ")";
2821     first = t1;
2822   }
2823   return first;
2824 }
2825
2826 template <class C>
2827 static const char *parse_binary_expression(const char *first, const char *last,
2828                                            const std::string &op,
2829                                            C &db) {
2830   const char *t1 = parse_expression(first, last, db);
2831   if (t1 != first) {
2832     const char *t2 = parse_expression(t1, last, db);
2833     if (t2 != t1) {
2834       if (db.names.size() < 2)
2835         return first;
2836       auto op2 = db.names.back().move_full();
2837       db.names.pop_back();
2838       auto op1 = db.names.back().move_full();
2839       auto &nm = db.names.back().first;
2840       nm.clear();
2841       if (op == ">")
2842         nm += '(';
2843       nm += "(" + op1 + ") " + op + " (" + op2 + ")";
2844       if (op == ">")
2845         nm += ')';
2846       first = t2;
2847     } else if (!db.names.empty())
2848       db.names.pop_back();
2849   }
2850   return first;
2851 }
2852
2853 // <expression> ::= <unary operator-name> <expression>
2854 //              ::= <binary operator-name> <expression> <expression>
2855 //              ::= <ternary operator-name> <expression> <expression>
2856 //              <expression>
2857 //              ::= cl <expression>+ E                                   # call
2858 //              ::= cv <type> <expression>                               #
2859 //              conversion with one argument
2860 //              ::= cv <type> _ <expression>* E                          #
2861 //              conversion with a different number of arguments
2862 //              ::= [gs] nw <expression>* _ <type> E                     # new
2863 //              (expr-list) type
2864 //              ::= [gs] nw <expression>* _ <type> <initializer>         # new
2865 //              (expr-list) type (init)
2866 //              ::= [gs] na <expression>* _ <type> E                     # new[]
2867 //              (expr-list) type
2868 //              ::= [gs] na <expression>* _ <type> <initializer>         # new[]
2869 //              (expr-list) type (init)
2870 //              ::= [gs] dl <expression>                                 #
2871 //              delete expression
2872 //              ::= [gs] da <expression>                                 #
2873 //              delete[] expression
2874 //              ::= pp_ <expression>                                     #
2875 //              prefix ++
2876 //              ::= mm_ <expression>                                     #
2877 //              prefix --
2878 //              ::= ti <type>                                            #
2879 //              typeid (type)
2880 //              ::= te <expression>                                      #
2881 //              typeid (expression)
2882 //              ::= dc <type> <expression>                               #
2883 //              dynamic_cast<type> (expression)
2884 //              ::= sc <type> <expression>                               #
2885 //              static_cast<type> (expression)
2886 //              ::= cc <type> <expression>                               #
2887 //              const_cast<type> (expression)
2888 //              ::= rc <type> <expression>                               #
2889 //              reinterpret_cast<type> (expression)
2890 //              ::= st <type>                                            #
2891 //              sizeof (a type)
2892 //              ::= sz <expression>                                      #
2893 //              sizeof (an expression)
2894 //              ::= at <type>                                            #
2895 //              alignof (a type)
2896 //              ::= az <expression>                                      #
2897 //              alignof (an expression)
2898 //              ::= nx <expression>                                      #
2899 //              noexcept (expression)
2900 //              ::= <template-param>
2901 //              ::= <function-param>
2902 //              ::= dt <expression> <unresolved-name>                    #
2903 //              expr.name
2904 //              ::= pt <expression> <unresolved-name>                    #
2905 //              expr->name
2906 //              ::= ds <expression> <expression>                         #
2907 //              expr.*expr
2908 //              ::= sZ <template-param>                                  # size
2909 //              of a parameter pack
2910 //              ::= sZ <function-param>                                  # size
2911 //              of a function parameter pack
2912 //              ::= sp <expression>                                      # pack
2913 //              expansion
2914 //              ::= tw <expression>                                      # throw
2915 //              expression
2916 //              ::= tr                                                   # throw
2917 //              with no operand (rethrow)
2918 //              ::= <unresolved-name>                                    # f(p),
2919 //              N::f(p), ::f(p),
2920 //                                                                       #
2921 //                                                                       freestanding
2922 //                                                                       dependent
2923 //                                                                       name
2924 //                                                                       (e.g.,
2925 //                                                                       T::x),
2926 //                                                                       #
2927 //                                                                       objectless
2928 //                                                                       nonstatic
2929 //                                                                       member
2930 //                                                                       reference
2931 //              ::= <expr-primary>
2932
2933 template <class C>
2934 static const char *parse_expression(const char *first, const char *last,
2935                                     C &db) {
2936   if (last - first >= 2) {
2937     const char *t = first;
2938     bool parsed_gs = false;
2939     if (last - first >= 4 && t[0] == 'g' && t[1] == 's') {
2940       t += 2;
2941       parsed_gs = true;
2942     }
2943     switch (*t) {
2944     case 'L':
2945       first = parse_expr_primary(first, last, db);
2946       break;
2947     case 'T':
2948       first = parse_template_param(first, last, db);
2949       break;
2950     case 'f':
2951       first = parse_function_param(first, last, db);
2952       break;
2953     case 'a':
2954       switch (t[1]) {
2955       case 'a':
2956         t = parse_binary_expression(first + 2, last, "&&", db);
2957         if (t != first + 2)
2958           first = t;
2959         break;
2960       case 'd':
2961         t = parse_prefix_expression(first + 2, last, "&", db);
2962         if (t != first + 2)
2963           first = t;
2964         break;
2965       case 'n':
2966         t = parse_binary_expression(first + 2, last, "&", db);
2967         if (t != first + 2)
2968           first = t;
2969         break;
2970       case 'N':
2971         t = parse_binary_expression(first + 2, last, "&=", db);
2972         if (t != first + 2)
2973           first = t;
2974         break;
2975       case 'S':
2976         t = parse_binary_expression(first + 2, last, "=", db);
2977         if (t != first + 2)
2978           first = t;
2979         break;
2980       case 't':
2981         first = parse_alignof_type(first, last, db);
2982         break;
2983       case 'z':
2984         first = parse_alignof_expr(first, last, db);
2985         break;
2986       }
2987       break;
2988     case 'c':
2989       switch (t[1]) {
2990       case 'c':
2991         first = parse_const_cast_expr(first, last, db);
2992         break;
2993       case 'l':
2994         first = parse_call_expr(first, last, db);
2995         break;
2996       case 'm':
2997         t = parse_binary_expression(first + 2, last, ",", db);
2998         if (t != first + 2)
2999           first = t;
3000         break;
3001       case 'o':
3002         t = parse_prefix_expression(first + 2, last, "~", db);
3003         if (t != first + 2)
3004           first = t;
3005         break;
3006       case 'v':
3007         first = parse_conversion_expr(first, last, db);
3008         break;
3009       }
3010       break;
3011     case 'd':
3012       switch (t[1]) {
3013       case 'a': {
3014         const char *t1 = parse_expression(t + 2, last, db);
3015         if (t1 != t + 2) {
3016           if (db.names.empty())
3017             return first;
3018           db.names.back().first =
3019               (parsed_gs ? std::string("::") : std::string()) + "delete[] " +
3020               db.names.back().move_full();
3021           first = t1;
3022         }
3023       } break;
3024       case 'c':
3025         first = parse_dynamic_cast_expr(first, last, db);
3026         break;
3027       case 'e':
3028         t = parse_prefix_expression(first + 2, last, "*", db);
3029         if (t != first + 2)
3030           first = t;
3031         break;
3032       case 'l': {
3033         const char *t1 = parse_expression(t + 2, last, db);
3034         if (t1 != t + 2) {
3035           if (db.names.empty())
3036             return first;
3037           db.names.back().first =
3038               (parsed_gs ? std::string("::") : std::string()) + "delete " +
3039               db.names.back().move_full();
3040           first = t1;
3041         }
3042       } break;
3043       case 'n':
3044         return parse_unresolved_name(first, last, db);
3045       case 's':
3046         first = parse_dot_star_expr(first, last, db);
3047         break;
3048       case 't':
3049         first = parse_dot_expr(first, last, db);
3050         break;
3051       case 'v':
3052         t = parse_binary_expression(first + 2, last, "/", db);
3053         if (t != first + 2)
3054           first = t;
3055         break;
3056       case 'V':
3057         t = parse_binary_expression(first + 2, last, "/=", db);
3058         if (t != first + 2)
3059           first = t;
3060         break;
3061       }
3062       break;
3063     case 'e':
3064       switch (t[1]) {
3065       case 'o':
3066         t = parse_binary_expression(first + 2, last, "^", db);
3067         if (t != first + 2)
3068           first = t;
3069         break;
3070       case 'O':
3071         t = parse_binary_expression(first + 2, last, "^=", db);
3072         if (t != first + 2)
3073           first = t;
3074         break;
3075       case 'q':
3076         t = parse_binary_expression(first + 2, last, "==", db);
3077         if (t != first + 2)
3078           first = t;
3079         break;
3080       }
3081       break;
3082     case 'g':
3083       switch (t[1]) {
3084       case 'e':
3085         t = parse_binary_expression(first + 2, last, ">=", db);
3086         if (t != first + 2)
3087           first = t;
3088         break;
3089       case 't':
3090         t = parse_binary_expression(first + 2, last, ">", db);
3091         if (t != first + 2)
3092           first = t;
3093         break;
3094       }
3095       break;
3096     case 'i':
3097       if (t[1] == 'x') {
3098         const char *t1 = parse_expression(first + 2, last, db);
3099         if (t1 != first + 2) {
3100           const char *t2 = parse_expression(t1, last, db);
3101           if (t2 != t1) {
3102             if (db.names.size() < 2)
3103               return first;
3104             auto op2 = db.names.back().move_full();
3105             db.names.pop_back();
3106             auto op1 = db.names.back().move_full();
3107             db.names.back() = "(" + op1 + ")[" + op2 + "]";
3108             first = t2;
3109           } else if (!db.names.empty())
3110             db.names.pop_back();
3111         }
3112       }
3113       break;
3114     case 'l':
3115       switch (t[1]) {
3116       case 'e':
3117         t = parse_binary_expression(first + 2, last, "<=", db);
3118         if (t != first + 2)
3119           first = t;
3120         break;
3121       case 's':
3122         t = parse_binary_expression(first + 2, last, "<<", db);
3123         if (t != first + 2)
3124           first = t;
3125         break;
3126       case 'S':
3127         t = parse_binary_expression(first + 2, last, "<<=", db);
3128         if (t != first + 2)
3129           first = t;
3130         break;
3131       case 't':
3132         t = parse_binary_expression(first + 2, last, "<", db);
3133         if (t != first + 2)
3134           first = t;
3135         break;
3136       }
3137       break;
3138     case 'm':
3139       switch (t[1]) {
3140       case 'i':
3141         t = parse_binary_expression(first + 2, last, "-", db);
3142         if (t != first + 2)
3143           first = t;
3144         break;
3145       case 'I':
3146         t = parse_binary_expression(first + 2, last, "-=", db);
3147         if (t != first + 2)
3148           first = t;
3149         break;
3150       case 'l':
3151         t = parse_binary_expression(first + 2, last, "*", db);
3152         if (t != first + 2)
3153           first = t;
3154         break;
3155       case 'L':
3156         t = parse_binary_expression(first + 2, last, "*=", db);
3157         if (t != first + 2)
3158           first = t;
3159         break;
3160       case 'm':
3161         if (first + 2 != last && first[2] == '_') {
3162           t = parse_prefix_expression(first + 3, last, "--", db);
3163           if (t != first + 3)
3164             first = t;
3165         } else {
3166           const char *t1 = parse_expression(first + 2, last, db);
3167           if (t1 != first + 2) {
3168             if (db.names.empty())
3169               return first;
3170             db.names.back() = "(" + db.names.back().move_full() + ")--";
3171             first = t1;
3172           }
3173         }
3174         break;
3175       }
3176       break;
3177     case 'n':
3178       switch (t[1]) {
3179       case 'a':
3180       case 'w':
3181         first = parse_new_expr(first, last, db);
3182         break;
3183       case 'e':
3184         t = parse_binary_expression(first + 2, last, "!=", db);
3185         if (t != first + 2)
3186           first = t;
3187         break;
3188       case 'g':
3189         t = parse_prefix_expression(first + 2, last, "-", db);
3190         if (t != first + 2)
3191           first = t;
3192         break;
3193       case 't':
3194         t = parse_prefix_expression(first + 2, last, "!", db);
3195         if (t != first + 2)
3196           first = t;
3197         break;
3198       case 'x':
3199         t = parse_noexcept_expression(first + 2, last, db);
3200         if (t != first + 2)
3201           first = t;
3202         break;
3203       }
3204       break;
3205     case 'o':
3206       switch (t[1]) {
3207       case 'n':
3208         return parse_unresolved_name(first, last, db);
3209       case 'o':
3210         t = parse_binary_expression(first + 2, last, "||", db);
3211         if (t != first + 2)
3212           first = t;
3213         break;
3214       case 'r':
3215         t = parse_binary_expression(first + 2, last, "|", db);
3216         if (t != first + 2)
3217           first = t;
3218         break;
3219       case 'R':
3220         t = parse_binary_expression(first + 2, last, "|=", db);
3221         if (t != first + 2)
3222           first = t;
3223         break;
3224       }
3225       break;
3226     case 'p':
3227       switch (t[1]) {
3228       case 'm':
3229         t = parse_binary_expression(first + 2, last, "->*", db);
3230         if (t != first + 2)
3231           first = t;
3232         break;
3233       case 'l':
3234         t = parse_binary_expression(first + 2, last, "+", db);
3235         if (t != first + 2)
3236           first = t;
3237         break;
3238       case 'L':
3239         t = parse_binary_expression(first + 2, last, "+=", db);
3240         if (t != first + 2)
3241           first = t;
3242         break;
3243       case 'p':
3244         if (first + 2 != last && first[2] == '_') {
3245           t = parse_prefix_expression(first + 3, last, "++", db);
3246           if (t != first + 3)
3247             first = t;
3248         } else {
3249           const char *t1 = parse_expression(first + 2, last, db);
3250           if (t1 != first + 2) {
3251             if (db.names.empty())
3252               return first;
3253             db.names.back() = "(" + db.names.back().move_full() + ")++";
3254             first = t1;
3255           }
3256         }
3257         break;
3258       case 's':
3259         t = parse_prefix_expression(first + 2, last, "+", db);
3260         if (t != first + 2)
3261           first = t;
3262         break;
3263       case 't':
3264         first = parse_arrow_expr(first, last, db);
3265         break;
3266       }
3267       break;
3268     case 'q':
3269       if (t[1] == 'u') {
3270         const char *t1 = parse_expression(first + 2, last, db);
3271         if (t1 != first + 2) {
3272           const char *t2 = parse_expression(t1, last, db);
3273           if (t2 != t1) {
3274             const char *t3 = parse_expression(t2, last, db);
3275             if (t3 != t2) {
3276               if (db.names.size() < 3)
3277                 return first;
3278               auto op3 = db.names.back().move_full();
3279               db.names.pop_back();
3280               auto op2 = db.names.back().move_full();
3281               db.names.pop_back();
3282               auto op1 = db.names.back().move_full();
3283               db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")";
3284               first = t3;
3285             } else {
3286               if (db.names.size() < 2)
3287                 return first;
3288               db.names.pop_back();
3289               db.names.pop_back();
3290             }
3291           } else if (!db.names.empty())
3292             db.names.pop_back();
3293         }
3294       }
3295       break;
3296     case 'r':
3297       switch (t[1]) {
3298       case 'c':
3299         first = parse_reinterpret_cast_expr(first, last, db);
3300         break;
3301       case 'm':
3302         t = parse_binary_expression(first + 2, last, "%", db);
3303         if (t != first + 2)
3304           first = t;
3305         break;
3306       case 'M':
3307         t = parse_binary_expression(first + 2, last, "%=", db);
3308         if (t != first + 2)
3309           first = t;
3310         break;
3311       case 's':
3312         t = parse_binary_expression(first + 2, last, ">>", db);
3313         if (t != first + 2)
3314           first = t;
3315         break;
3316       case 'S':
3317         t = parse_binary_expression(first + 2, last, ">>=", db);
3318         if (t != first + 2)
3319           first = t;
3320         break;
3321       }
3322       break;
3323     case 's':
3324       switch (t[1]) {
3325       case 'c':
3326         first = parse_static_cast_expr(first, last, db);
3327         break;
3328       case 'p':
3329         first = parse_pack_expansion(first, last, db);
3330         break;
3331       case 'r':
3332         return parse_unresolved_name(first, last, db);
3333       case 't':
3334         first = parse_sizeof_type_expr(first, last, db);
3335         break;
3336       case 'z':
3337         first = parse_sizeof_expr_expr(first, last, db);
3338         break;
3339       case 'Z':
3340         if (last - t >= 3) {
3341           switch (t[2]) {
3342           case 'T':
3343             first = parse_sizeof_param_pack_expr(first, last, db);
3344             break;
3345           case 'f':
3346             first = parse_sizeof_function_param_pack_expr(first, last, db);
3347             break;
3348           }
3349         }
3350         break;
3351       }
3352       break;
3353     case 't':
3354       switch (t[1]) {
3355       case 'e':
3356       case 'i':
3357         first = parse_typeid_expr(first, last, db);
3358         break;
3359       case 'r':
3360         db.names.push_back("throw");
3361         first += 2;
3362         break;
3363       case 'w':
3364         first = parse_throw_expr(first, last, db);
3365         break;
3366       }
3367       break;
3368     case '1':
3369     case '2':
3370     case '3':
3371     case '4':
3372     case '5':
3373     case '6':
3374     case '7':
3375     case '8':
3376     case '9':
3377       return parse_unresolved_name(first, last, db);
3378     }
3379   }
3380   return first;
3381 }
3382
3383 // <template-arg> ::= <type>                                             # type
3384 // or template
3385 //                ::= X <expression> E                                   #
3386 //                expression
3387 //                ::= <expr-primary>                                     #
3388 //                simple expressions
3389 //                ::= J <template-arg>* E                                #
3390 //                argument pack
3391 //                ::= LZ <encoding> E                                    #
3392 //                extension
3393
3394 template <class C>
3395 static const char *parse_template_arg(const char *first, const char *last,
3396                                       C &db) {
3397   if (first != last) {
3398     const char *t;
3399     switch (*first) {
3400     case 'X':
3401       t = parse_expression(first + 1, last, db);
3402       if (t != first + 1) {
3403         if (t != last && *t == 'E')
3404           first = t + 1;
3405       }
3406       break;
3407     case 'J':
3408       t = first + 1;
3409       if (t == last)
3410         return first;
3411       while (*t != 'E') {
3412         const char *t1 = parse_template_arg(t, last, db);
3413         if (t1 == t)
3414           return first;
3415         t = t1;
3416       }
3417       first = t + 1;
3418       break;
3419     case 'L':
3420       // <expr-primary> or LZ <encoding> E
3421       if (first + 1 != last && first[1] == 'Z') {
3422         t = parse_encoding(first + 2, last, db);
3423         if (t != first + 2 && t != last && *t == 'E')
3424           first = t + 1;
3425       } else
3426         first = parse_expr_primary(first, last, db);
3427       break;
3428     default:
3429       // <type>
3430       first = parse_type(first, last, db);
3431       break;
3432     }
3433   }
3434   return first;
3435 }
3436
3437 // <template-args> ::= I <template-arg>* E
3438 //     extension, the abi says <template-arg>+
3439
3440 template <class C>
3441 static const char *parse_template_args(const char *first, const char *last,
3442                                        C &db) {
3443   if (last - first >= 2 && *first == 'I') {
3444     if (db.tag_templates)
3445       db.template_param.back().clear();
3446     const char *t = first + 1;
3447     std::string args("<");
3448     while (*t != 'E') {
3449       if (db.tag_templates)
3450         db.template_param.emplace_back();
3451       size_t k0 = db.names.size();
3452       const char *t1 = parse_template_arg(t, last, db);
3453       size_t k1 = db.names.size();
3454       if (db.tag_templates)
3455         db.template_param.pop_back();
3456       if (t1 == t || t1 == last)
3457         return first;
3458       if (db.tag_templates) {
3459         db.template_param.back().emplace_back();
3460         for (size_t k = k0; k < k1; ++k)
3461           db.template_param.back().back().push_back(db.names[k]);
3462       }
3463       for (size_t k = k0; k < k1; ++k) {
3464         if (args.size() > 1)
3465           args += ", ";
3466         args += db.names[k].move_full();
3467       }
3468       for (; k1 > k0; --k1)
3469         if (!db.names.empty())
3470           db.names.pop_back();
3471       t = t1;
3472     }
3473     first = t + 1;
3474     if (args.back() != '>')
3475       args += ">";
3476     else
3477       args += " >";
3478     db.names.push_back(std::move(args));
3479   }
3480   return first;
3481 }
3482
3483 // <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
3484 // <unqualified-name> E
3485 //               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
3486 //               <template-args> E
3487 //
3488 // <prefix> ::= <prefix> <unqualified-name>
3489 //          ::= <template-prefix> <template-args>
3490 //          ::= <template-param>
3491 //          ::= <decltype>
3492 //          ::= # empty
3493 //          ::= <substitution>
3494 //          ::= <prefix> <data-member-prefix>
3495 //  extension ::= L
3496 //
3497 // <template-prefix> ::= <prefix> <template unqualified-name>
3498 //                   ::= <template-param>
3499 //                   ::= <substitution>
3500
3501 template <class C>
3502 static const char *parse_nested_name(const char *first, const char *last, C &db,
3503                                      bool *ends_with_template_args) {
3504   if (first != last && *first == 'N') {
3505     unsigned cv;
3506     const char *t0 = parse_cv_qualifiers(first + 1, last, cv);
3507     if (t0 == last)
3508       return first;
3509     db.ref = 0;
3510     if (*t0 == 'R') {
3511       db.ref = 1;
3512       ++t0;
3513     } else if (*t0 == 'O') {
3514       db.ref = 2;
3515       ++t0;
3516     }
3517     db.names.emplace_back();
3518     if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't') {
3519       t0 += 2;
3520       db.names.back().first = "std";
3521     }
3522     if (t0 == last) {
3523       db.names.pop_back();
3524       return first;
3525     }
3526     bool pop_subs = false;
3527     bool component_ends_with_template_args = false;
3528     while (*t0 != 'E') {
3529       component_ends_with_template_args = false;
3530       const char *t1;
3531       switch (*t0) {
3532       case 'S':
3533         if (t0 + 1 != last && t0[1] == 't')
3534           goto do_parse_unqualified_name;
3535         t1 = parse_substitution(t0, last, db);
3536         if (t1 != t0 && t1 != last) {
3537           auto name = db.names.back().move_full();
3538           db.names.pop_back();
3539           if (db.names.empty())
3540             return first;
3541           if (!db.names.back().first.empty()) {
3542             db.names.back().first += "::" + name;
3543             db.subs.push_back(typename C::sub_type(1, db.names.back()));
3544           } else
3545             db.names.back().first = name;
3546           pop_subs = true;
3547           t0 = t1;
3548         } else
3549           return first;
3550         break;
3551       case 'T':
3552         t1 = parse_template_param(t0, last, db);
3553         if (t1 != t0 && t1 != last) {
3554           auto name = db.names.back().move_full();
3555           db.names.pop_back();
3556           if (db.names.empty())
3557             return first;
3558           if (!db.names.back().first.empty())
3559             db.names.back().first += "::" + name;
3560           else
3561             db.names.back().first = name;
3562           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3563           pop_subs = true;
3564           t0 = t1;
3565         } else
3566           return first;
3567         break;
3568       case 'D':
3569         if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
3570           goto do_parse_unqualified_name;
3571         t1 = parse_decltype(t0, last, db);
3572         if (t1 != t0 && t1 != last) {
3573           auto name = db.names.back().move_full();
3574           db.names.pop_back();
3575           if (db.names.empty())
3576             return first;
3577           if (!db.names.back().first.empty())
3578             db.names.back().first += "::" + name;
3579           else
3580             db.names.back().first = name;
3581           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3582           pop_subs = true;
3583           t0 = t1;
3584         } else
3585           return first;
3586         break;
3587       case 'I':
3588         t1 = parse_template_args(t0, last, db);
3589         if (t1 != t0 && t1 != last) {
3590           auto name = db.names.back().move_full();
3591           db.names.pop_back();
3592           if (db.names.empty())
3593             return first;
3594           db.names.back().first += name;
3595           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3596           t0 = t1;
3597           component_ends_with_template_args = true;
3598         } else
3599           return first;
3600         break;
3601       case 'L':
3602         if (++t0 == last)
3603           return first;
3604         break;
3605       default:
3606       do_parse_unqualified_name:
3607         t1 = parse_unqualified_name(t0, last, db);
3608         if (t1 != t0 && t1 != last) {
3609           auto name = db.names.back().move_full();
3610           db.names.pop_back();
3611           if (db.names.empty())
3612             return first;
3613           if (!db.names.back().first.empty())
3614             db.names.back().first += "::" + name;
3615           else
3616             db.names.back().first = name;
3617           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3618           pop_subs = true;
3619           t0 = t1;
3620         } else
3621           return first;
3622       }
3623     }
3624     first = t0 + 1;
3625     db.cv = cv;
3626     if (pop_subs && !db.subs.empty())
3627       db.subs.pop_back();
3628     if (ends_with_template_args)
3629       *ends_with_template_args = component_ends_with_template_args;
3630   }
3631   return first;
3632 }
3633
3634 // <discriminator> := _ <non-negative number>      # when number < 10
3635 //                 := __ <non-negative number> _   # when number >= 10
3636 //  extension      := decimal-digit+               # at the end of string
3637
3638 static const char *parse_discriminator(const char *first, const char *last) {
3639   // parse but ignore discriminator
3640   if (first != last) {
3641     if (*first == '_') {
3642       const char *t1 = first + 1;
3643       if (t1 != last) {
3644         if (std::isdigit(*t1))
3645           first = t1 + 1;
3646         else if (*t1 == '_') {
3647           for (++t1; t1 != last && std::isdigit(*t1); ++t1)
3648             ;
3649           if (t1 != last && *t1 == '_')
3650             first = t1 + 1;
3651         }
3652       }
3653     } else if (std::isdigit(*first)) {
3654       const char *t1 = first + 1;
3655       for (; t1 != last && std::isdigit(*t1); ++t1)
3656         ;
3657       if (t1 == last)
3658         first = last;
3659     }
3660   }
3661   return first;
3662 }
3663
3664 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
3665 //              := Z <function encoding> E s [<discriminator>]
3666 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity
3667 //              name>
3668
3669 template <class C>
3670 static const char *parse_local_name(const char *first, const char *last, C &db,
3671                                     bool *ends_with_template_args) {
3672   if (first != last && *first == 'Z') {
3673     const char *t = parse_encoding(first + 1, last, db);
3674     if (t != first + 1 && t != last && *t == 'E' && ++t != last) {
3675       switch (*t) {
3676       case 's':
3677         first = parse_discriminator(t + 1, last);
3678         if (db.names.empty())
3679           return first;
3680         db.names.back().first.append("::string literal");
3681         break;
3682       case 'd':
3683         if (++t != last) {
3684           const char *t1 = parse_number(t, last);
3685           if (t1 != last && *t1 == '_') {
3686             t = t1 + 1;
3687             t1 = parse_name(t, last, db, ends_with_template_args);
3688             if (t1 != t) {
3689               if (db.names.size() < 2)
3690                 return first;
3691               auto name = db.names.back().move_full();
3692               db.names.pop_back();
3693               if (db.names.empty())
3694                 return first;
3695               db.names.back().first.append("::");
3696               db.names.back().first.append(name);
3697               first = t1;
3698             } else if (!db.names.empty())
3699               db.names.pop_back();
3700           }
3701         }
3702         break;
3703       default: {
3704         const char *t1 = parse_name(t, last, db, ends_with_template_args);
3705         if (t1 != t) {
3706           // parse but ignore discriminator
3707           first = parse_discriminator(t1, last);
3708           if (db.names.size() < 2)
3709             return first;
3710           auto name = db.names.back().move_full();
3711           db.names.pop_back();
3712           if (db.names.empty())
3713             return first;
3714           db.names.back().first.append("::");
3715           db.names.back().first.append(name);
3716         } else if (!db.names.empty())
3717           db.names.pop_back();
3718       } break;
3719       }
3720     }
3721   }
3722   return first;
3723 }
3724
3725 // <name> ::= <nested-name> // N
3726 //        ::= <local-name> # See Scope Encoding below  // Z
3727 //        ::= <unscoped-template-name> <template-args>
3728 //        ::= <unscoped-name>
3729
3730 // <unscoped-template-name> ::= <unscoped-name>
3731 //                          ::= <substitution>
3732
3733 template <class C>
3734 static const char *parse_name(const char *first, const char *last, C &db,
3735                               bool *ends_with_template_args) {
3736   if (last - first >= 2) {
3737     const char *t0 = first;
3738     // extension: ignore L here
3739     if (*t0 == 'L')
3740       ++t0;
3741     switch (*t0) {
3742     case 'N': {
3743       const char *t1 = parse_nested_name(t0, last, db, ends_with_template_args);
3744       if (t1 != t0)
3745         first = t1;
3746       break;
3747     }
3748     case 'Z': {
3749       const char *t1 = parse_local_name(t0, last, db, ends_with_template_args);
3750       if (t1 != t0)
3751         first = t1;
3752       break;
3753     }
3754     default: {
3755       const char *t1 = parse_unscoped_name(t0, last, db);
3756       if (t1 != t0) {
3757         if (t1 != last &&
3758             *t1 == 'I') // <unscoped-template-name> <template-args>
3759         {
3760           if (db.names.empty())
3761             return first;
3762           db.subs.push_back(typename C::sub_type(1, db.names.back()));
3763           t0 = t1;
3764           t1 = parse_template_args(t0, last, db);
3765           if (t1 != t0) {
3766             if (db.names.size() < 2)
3767               return first;
3768             auto tmp = db.names.back().move_full();
3769             db.names.pop_back();
3770             if (db.names.empty())
3771               return first;
3772             db.names.back().first += tmp;
3773             first = t1;
3774             if (ends_with_template_args)
3775               *ends_with_template_args = true;
3776           }
3777         } else // <unscoped-name>
3778           first = t1;
3779       } else { // try <substitution> <template-args>
3780         t1 = parse_substitution(t0, last, db);
3781         if (t1 != t0 && t1 != last && *t1 == 'I') {
3782           t0 = t1;
3783           t1 = parse_template_args(t0, last, db);
3784           if (t1 != t0) {
3785             if (db.names.size() < 2)
3786               return first;
3787             auto tmp = db.names.back().move_full();
3788             db.names.pop_back();
3789             if (db.names.empty())
3790               return first;
3791             db.names.back().first += tmp;
3792             first = t1;
3793             if (ends_with_template_args)
3794               *ends_with_template_args = true;
3795           }
3796         }
3797       }
3798       break;
3799     }
3800     }
3801   }
3802   return first;
3803 }
3804
3805 // <call-offset> ::= h <nv-offset> _
3806 //               ::= v <v-offset> _
3807 //
3808 // <nv-offset> ::= <offset number>
3809 //               # non-virtual base override
3810 //
3811 // <v-offset>  ::= <offset number> _ <virtual offset number>
3812 //               # virtual base override, with vcall offset
3813
3814 static const char *parse_call_offset(const char *first, const char *last) {
3815   if (first != last) {
3816     switch (*first) {
3817     case 'h': {
3818       const char *t = parse_number(first + 1, last);
3819       if (t != first + 1 && t != last && *t == '_')
3820         first = t + 1;
3821     } break;
3822     case 'v': {
3823       const char *t = parse_number(first + 1, last);
3824       if (t != first + 1 && t != last && *t == '_') {
3825         const char *t2 = parse_number(++t, last);
3826         if (t2 != t && t2 != last && *t2 == '_')
3827           first = t2 + 1;
3828       }
3829     } break;
3830     }
3831   }
3832   return first;
3833 }
3834
3835 // <special-name> ::= TV <type>    # virtual table
3836 //                ::= TT <type>    # VTT structure (construction vtable index)
3837 //                ::= TI <type>    # typeinfo structure
3838 //                ::= TS <type>    # typeinfo name (null-terminated byte string)
3839 //                ::= Tc <call-offset> <call-offset> <base encoding>
3840 //                    # base is the nominal target function of thunk
3841 //                    # first call-offset is 'this' adjustment
3842 //                    # second call-offset is result adjustment
3843 //                ::= T <call-offset> <base encoding>
3844 //                    # base is the nominal target function of thunk
3845 //                ::= GV <object name> # Guard variable for one-time
3846 //                initialization
3847 //                                     # No <type>
3848 //                ::= TW <object name> # Thread-local wrapper
3849 //                ::= TH <object name> # Thread-local initialization
3850 //      extension ::= TC <first type> <number> _ <second type> # construction
3851 //      vtable for second-in-first
3852 //      extension ::= GR <object name> # reference temporary for object
3853
3854 template <class C>
3855 static const char *parse_special_name(const char *first, const char *last,
3856                                       C &db) {
3857   if (last - first > 2) {
3858     const char *t;
3859     switch (*first) {
3860     case 'T':
3861       switch (first[1]) {
3862       case 'V':
3863         // TV <type>    # virtual table
3864         t = parse_type(first + 2, last, db);
3865         if (t != first + 2) {
3866           if (db.names.empty())
3867             return first;
3868           db.names.back().first.insert(0, "vtable for ");
3869           first = t;
3870         }
3871         break;
3872       case 'T':
3873         // TT <type>    # VTT structure (construction vtable index)
3874         t = parse_type(first + 2, last, db);
3875         if (t != first + 2) {
3876           if (db.names.empty())
3877             return first;
3878           db.names.back().first.insert(0, "VTT for ");
3879           first = t;
3880         }
3881         break;
3882       case 'I':
3883         // TI <type>    # typeinfo structure
3884         t = parse_type(first + 2, last, db);
3885         if (t != first + 2) {
3886           if (db.names.empty())
3887             return first;
3888           db.names.back().first.insert(0, "typeinfo for ");
3889           first = t;
3890         }
3891         break;
3892       case 'S':
3893         // TS <type>    # typeinfo name (null-terminated byte string)
3894         t = parse_type(first + 2, last, db);
3895         if (t != first + 2) {
3896           if (db.names.empty())
3897             return first;
3898           db.names.back().first.insert(0, "typeinfo name for ");
3899           first = t;
3900         }
3901         break;
3902       case 'c':
3903         // Tc <call-offset> <call-offset> <base encoding>
3904         {
3905           const char *t0 = parse_call_offset(first + 2, last);
3906           if (t0 == first + 2)
3907             break;
3908           const char *t1 = parse_call_offset(t0, last);
3909           if (t1 == t0)
3910             break;
3911           t = parse_encoding(t1, last, db);
3912           if (t != t1) {
3913             if (db.names.empty())
3914               return first;
3915             db.names.back().first.insert(0, "covariant return thunk to ");
3916             first = t;
3917           }
3918         }
3919         break;
3920       case 'C':
3921         // extension ::= TC <first type> <number> _ <second type> # construction
3922         // vtable for second-in-first
3923         t = parse_type(first + 2, last, db);
3924         if (t != first + 2) {
3925           const char *t0 = parse_number(t, last);
3926           if (t0 != t && t0 != last && *t0 == '_') {
3927             const char *t1 = parse_type(++t0, last, db);
3928             if (t1 != t0) {
3929               if (db.names.size() < 2)
3930                 return first;
3931               auto left = db.names.back().move_full();
3932               db.names.pop_back();
3933               if (db.names.empty())
3934                 return first;
3935               db.names.back().first = "construction vtable for " +
3936                                       std::move(left) + "-in-" +
3937                                       db.names.back().move_full();
3938               first = t1;
3939             }
3940           }
3941         }
3942         break;
3943       case 'W':
3944         // TW <object name> # Thread-local wrapper
3945         t = parse_name(first + 2, last, db);
3946         if (t != first + 2) {
3947           if (db.names.empty())
3948             return first;
3949           db.names.back().first.insert(0, "thread-local wrapper routine for ");
3950           first = t;
3951         }
3952         break;
3953       case 'H':
3954         // TH <object name> # Thread-local initialization
3955         t = parse_name(first + 2, last, db);
3956         if (t != first + 2) {
3957           if (db.names.empty())
3958             return first;
3959           db.names.back().first.insert(
3960               0, "thread-local initialization routine for ");
3961           first = t;
3962         }
3963         break;
3964       default:
3965         // T <call-offset> <base encoding>
3966         {
3967           const char *t0 = parse_call_offset(first + 1, last);
3968           if (t0 == first + 1)
3969             break;
3970           t = parse_encoding(t0, last, db);
3971           if (t != t0) {
3972             if (db.names.empty())
3973               return first;
3974             if (first[1] == 'v') {
3975               db.names.back().first.insert(0, "virtual thunk to ");
3976               first = t;
3977             } else {
3978               db.names.back().first.insert(0, "non-virtual thunk to ");
3979               first = t;
3980             }
3981           }
3982         }
3983         break;
3984       }
3985       break;
3986     case 'G':
3987       switch (first[1]) {
3988       case 'V':
3989         // GV <object name> # Guard variable for one-time initialization
3990         t = parse_name(first + 2, last, db);
3991         if (t != first + 2) {
3992           if (db.names.empty())
3993             return first;
3994           db.names.back().first.insert(0, "guard variable for ");
3995           first = t;
3996         }
3997         break;
3998       case 'R':
3999         // extension ::= GR <object name> # reference temporary for object
4000         t = parse_name(first + 2, last, db);
4001         if (t != first + 2) {
4002           if (db.names.empty())
4003             return first;
4004           db.names.back().first.insert(0, "reference temporary for ");
4005           first = t;
4006         }
4007         break;
4008       }
4009       break;
4010     }
4011   }
4012   return first;
4013 }
4014
4015 namespace {
4016 template <class T> class save_value {
4017   T &restore_;
4018   T original_value_;
4019
4020 public:
4021   save_value(T &restore) : restore_(restore), original_value_(restore) {}
4022
4023   ~save_value() { restore_ = std::move(original_value_); }
4024
4025   save_value(const save_value &) = delete;
4026   save_value &operator=(const save_value &) = delete;
4027 };
4028 }
4029
4030 // <encoding> ::= <function name> <bare-function-type>
4031 //            ::= <data name>
4032 //            ::= <special-name>
4033
4034 template <class C>
4035 static const char *parse_encoding(const char *first, const char *last, C &db) {
4036   if (first != last) {
4037     save_value<decltype(db.encoding_depth)> su(db.encoding_depth);
4038     ++db.encoding_depth;
4039     save_value<decltype(db.tag_templates)> sb(db.tag_templates);
4040     if (db.encoding_depth > 1)
4041       db.tag_templates = true;
4042     save_value<decltype(db.parsed_ctor_dtor_cv)> sp(db.parsed_ctor_dtor_cv);
4043     db.parsed_ctor_dtor_cv = false;
4044     switch (*first) {
4045     case 'G':
4046     case 'T':
4047       first = parse_special_name(first, last, db);
4048       break;
4049     default: {
4050       bool ends_with_template_args = false;
4051       const char *t = parse_name(first, last, db, &ends_with_template_args);
4052       unsigned cv = db.cv;
4053       unsigned ref = db.ref;
4054       if (t != first) {
4055         if (t != last && *t != 'E' && *t != '.') {
4056           save_value<bool> sb2(db.tag_templates);
4057           db.tag_templates = false;
4058           const char *t2;
4059           std::string ret2;
4060           if (db.names.empty())
4061             return first;
4062           const std::string &nm = db.names.back().first;
4063           if (nm.empty())
4064             return first;
4065           if (!db.parsed_ctor_dtor_cv && ends_with_template_args) {
4066             t2 = parse_type(t, last, db);
4067             if (t2 == t)
4068               return first;
4069             if (db.names.size() < 2)
4070               return first;
4071             auto ret1 = std::move(db.names.back().first);
4072             ret2 = std::move(db.names.back().second);
4073             if (ret2.empty())
4074               ret1 += ' ';
4075             db.names.pop_back();
4076             if (db.names.empty())
4077               return first;
4078
4079             db.names.back().first.insert(0, ret1);
4080             t = t2;
4081           }
4082           db.names.back().first += '(';
4083           if (t != last && *t == 'v') {
4084             ++t;
4085           } else {
4086             bool first_arg = true;
4087             while (true) {
4088               size_t k0 = db.names.size();
4089               t2 = parse_type(t, last, db);
4090               size_t k1 = db.names.size();
4091               if (t2 == t)
4092                 break;
4093               if (k1 > k0) {
4094                 std::string tmp;
4095                 for (size_t k = k0; k < k1; ++k) {
4096                   if (!tmp.empty())
4097                     tmp += ", ";
4098                   tmp += db.names[k].move_full();
4099                 }
4100                 for (size_t k = k0; k < k1; ++k) {
4101                   if (db.names.empty())
4102                     return first;
4103                   db.names.pop_back();
4104                 }
4105                 if (!tmp.empty()) {
4106                   if (db.names.empty())
4107                     return first;
4108                   if (!first_arg)
4109                     db.names.back().first += ", ";
4110                   else
4111                     first_arg = false;
4112                   db.names.back().first += tmp;
4113                 }
4114               }
4115               t = t2;
4116             }
4117           }
4118           if (db.names.empty())
4119             return first;
4120           db.names.back().first += ')';
4121           if (cv & CV_const)
4122             db.names.back().first.append(" const");
4123           if (cv & CV_volatile)
4124             db.names.back().first.append(" volatile");
4125           if (cv & CV_restrict)
4126             db.names.back().first.append(" restrict");
4127           if (ref == 1)
4128             db.names.back().first.append(" &");
4129           else if (ref == 2)
4130             db.names.back().first.append(" &&");
4131           db.names.back().first += ret2;
4132           first = t;
4133         } else
4134           first = t;
4135       }
4136       break;
4137     }
4138     }
4139   }
4140   return first;
4141 }
4142
4143 // _block_invoke
4144 // _block_invoke<decimal-digit>+
4145 // _block_invoke_<decimal-digit>+
4146
4147 template <class C>
4148 static const char *parse_block_invoke(const char *first, const char *last,
4149                                       C &db) {
4150   if (last - first >= 13) {
4151     const char test[] = "_block_invoke";
4152     const char *t = first;
4153     for (int i = 0; i < 13; ++i, ++t) {
4154       if (*t != test[i])
4155         return first;
4156     }
4157     if (t != last) {
4158       if (*t == '_') {
4159         // must have at least 1 decimal digit
4160         if (++t == last || !std::isdigit(*t))
4161           return first;
4162         ++t;
4163       }
4164       // parse zero or more digits
4165       while (t != last && isdigit(*t))
4166         ++t;
4167     }
4168     if (db.names.empty())
4169       return first;
4170     db.names.back().first.insert(0, "invocation function for block in ");
4171     first = t;
4172   }
4173   return first;
4174 }
4175
4176 // extension
4177 // <dot-suffix> := .<anything and everything>
4178
4179 template <class C>
4180 static const char *parse_dot_suffix(const char *first, const char *last,
4181                                     C &db) {
4182   if (first != last && *first == '.') {
4183     if (db.names.empty())
4184       return first;
4185     db.names.back().first += " (" + std::string(first, last) + ")";
4186     first = last;
4187   }
4188   return first;
4189 }
4190
4191 // <block-involcaton-function> ___Z<encoding>_block_invoke
4192 // <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+
4193 // <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+
4194 // <mangled-name> ::= _Z<encoding>
4195 //                ::= <type>
4196
4197 template <class C>
4198 static void demangle(const char *first, const char *last, C &db, int &status) {
4199   if (first >= last) {
4200     status = invalid_mangled_name;
4201     return;
4202   }
4203   if (*first == '_') {
4204     if (last - first >= 4) {
4205       if (first[1] == 'Z') {
4206         const char *t = parse_encoding(first + 2, last, db);
4207         if (t != first + 2 && t != last && *t == '.')
4208           t = parse_dot_suffix(t, last, db);
4209         if (t != last)
4210           status = invalid_mangled_name;
4211       } else if (first[1] == '_' && first[2] == '_' && first[3] == 'Z') {
4212         const char *t = parse_encoding(first + 4, last, db);
4213         if (t != first + 4 && t != last) {
4214           const char *t1 = parse_block_invoke(t, last, db);
4215           if (t1 != last)
4216             status = invalid_mangled_name;
4217         } else
4218           status = invalid_mangled_name;
4219       } else
4220         status = invalid_mangled_name;
4221     } else
4222       status = invalid_mangled_name;
4223   } else {
4224     const char *t = parse_type(first, last, db);
4225     if (t != last)
4226       status = invalid_mangled_name;
4227   }
4228   if (status == success && db.names.empty())
4229     status = invalid_mangled_name;
4230 }
4231
4232 namespace {
4233 template <class StrT> struct string_pair {
4234   StrT first;
4235   StrT second;
4236
4237   string_pair() = default;
4238   string_pair(StrT f) : first(std::move(f)) {}
4239   string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
4240   template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {}
4241
4242   size_t size() const { return first.size() + second.size(); }
4243   bool empty() const { return first.empty() && second.empty(); }
4244   StrT full() const { return first + second; }
4245   StrT move_full() { return std::move(first) + std::move(second); }
4246 };
4247
4248 struct Db {
4249   typedef std::vector<string_pair<std::string>> sub_type;
4250   typedef std::vector<sub_type> template_param_type;
4251   sub_type names;
4252   template_param_type subs;
4253   std::vector<template_param_type> template_param;
4254   unsigned cv = 0;
4255   unsigned ref = 0;
4256   unsigned encoding_depth = 0;
4257   bool parsed_ctor_dtor_cv = false;
4258   bool tag_templates = true;
4259   bool fix_forward_references = false;
4260   bool try_to_parse_template_args = true;
4261
4262   Db() : subs(0, names), template_param(0, subs) {}
4263 };
4264 }
4265
4266 char *llvm::itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
4267                             int *status) {
4268   if (mangled_name == nullptr || (buf != nullptr && n == nullptr)) {
4269     if (status)
4270       *status = invalid_args;
4271     return nullptr;
4272   }
4273   size_t internal_size = buf != nullptr ? *n : 0;
4274   Db db;
4275   db.template_param.emplace_back();
4276   int internal_status = success;
4277   size_t len = std::strlen(mangled_name);
4278   demangle(mangled_name, mangled_name + len, db, internal_status);
4279   if (internal_status == success && db.fix_forward_references &&
4280       !db.template_param.empty() && !db.template_param.front().empty()) {
4281     db.fix_forward_references = false;
4282     db.tag_templates = false;
4283     db.names.clear();
4284     db.subs.clear();
4285     demangle(mangled_name, mangled_name + len, db, internal_status);
4286     if (db.fix_forward_references)
4287       internal_status = invalid_mangled_name;
4288   }
4289   if (internal_status == success) {
4290     size_t sz = db.names.back().size() + 1;
4291     if (sz > internal_size) {
4292       char *newbuf = static_cast<char *>(std::realloc(buf, sz));
4293       if (newbuf == nullptr) {
4294         internal_status = memory_alloc_failure;
4295         buf = nullptr;
4296       } else {
4297         buf = newbuf;
4298         if (n != nullptr)
4299           *n = sz;
4300       }
4301     }
4302     if (buf != nullptr) {
4303       db.names.back().first += db.names.back().second;
4304       std::memcpy(buf, db.names.back().first.data(), sz - 1);
4305       buf[sz - 1] = char(0);
4306     }
4307   } else
4308     buf = nullptr;
4309   if (status)
4310     *status = internal_status;
4311   return buf;
4312 }