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