contrib/llvm/tools/lldb/source/Utility/FastDemangle.cpp

   1 //===-- FastDemangle.cpp ----------------------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "lldb/Utility/FastDemangle.h"
  11
  12 #include "llvm/Support/Compiler.h" // for LLVM_FALLTHROUGH
  13
  14 #include <functional>
  15
  16 #include <stdio.h>
  17 #include <stdlib.h>
  18 #include <string.h>
  19
  20 //#define DEBUG_FAILURES 1
  21 //#define DEBUG_SUBSTITUTIONS 1
  22 //#define DEBUG_TEMPLATE_ARGS 1
  23 //#define DEBUG_HIGHWATER 1
  24 //#define DEBUG_REORDERING 1
  25
  26 namespace {
  27
  28 /// @brief Represents the collection of qualifiers on a type
  29
  30 enum Qualifiers {
  31   QualifierNone = 0,
  32   QualifierConst = 1,
  33   QualifierRestrict = 2,
  34   QualifierVolatile = 4,
  35   QualifierReference = 8,
  36   QualifierRValueReference = 16,
  37   QualifierPointer = 32
  38 };
  39
  40 /// @brief Categorizes the recognized operators
  41
  42 enum class OperatorKind {
  43   Unary,
  44   Postfix,
  45   Binary,
  46   Ternary,
  47   Other,
  48   ConversionOperator,
  49   Vendor,
  50   NoMatch
  51 };
  52
  53 /// @brief Represents one of the recognized two-character operator
  54 /// abbreviations used when parsing operators as names and expressions
  55
  56 struct Operator {
  57   const char *name;
  58   OperatorKind kind;
  59 };
  60
  61 /// @brief Represents a range of characters in the output buffer, typically for
  62 /// use with RewriteRange()
  63
  64 struct BufferRange {
  65   int offset;
  66   int length;
  67 };
  68
  69 /// @brief Transient state required while parsing a name
  70
  71 struct NameState {
  72   bool parse_function_params;
  73   bool is_last_generic;
  74   bool has_no_return_type;
  75   BufferRange last_name_range;
  76 };
  77
  78 /// @brief LLDB's fast C++ demangler
  79 ///
  80 /// This is an incomplete implementation designed to speed up the demangling
  81 /// process that is often a bottleneck when LLDB stops a process for the first
  82 /// time.  Where the implementation doesn't know how to demangle a symbol it
  83 /// fails gracefully to allow the caller to fall back to the existing demangler.
  84 ///
  85 /// Over time the full mangling spec should be supported without compromising
  86 /// performance for the most common cases.
  87
  88 class SymbolDemangler {
  89 public:
  90   //----------------------------------------------------
  91   // Public API
  92   //----------------------------------------------------
  93
  94   /// @brief Create a SymbolDemangler
  95   ///
  96   /// The newly created demangler allocates and owns scratch memory sufficient
  97   /// for demangling typical symbols.  Additional memory will be allocated if
  98   /// needed and managed by the demangler instance.
  99
 100   SymbolDemangler() {
 101     m_buffer = (char *)malloc(8192);
 102     m_buffer_end = m_buffer + 8192;
 103     m_owns_buffer = true;
 104
 105     m_rewrite_ranges = (BufferRange *)malloc(128 * sizeof(BufferRange));
 106     m_rewrite_ranges_size = 128;
 107     m_owns_m_rewrite_ranges = true;
 108   }
 109
 110   /// @brief Create a SymbolDemangler that uses provided scratch memory
 111   ///
 112   /// The provided memory is not owned by the demangler.  It will be
 113   /// overwritten during calls to GetDemangledCopy() but can be used for
 114   /// other purposes between calls.  The provided memory will not be freed
 115   /// when this instance is destroyed.
 116   ///
 117   /// If demangling a symbol requires additional space it will be allocated
 118   /// and managed by the demangler instance.
 119   ///
 120   /// @param storage_ptr Valid pointer to at least storage_size bytes of
 121   /// space that the SymbolDemangler can use during demangling
 122   ///
 123   /// @param storage_size Number of bytes of space available scratch memory
 124   /// referenced by storage_ptr
 125
 126   SymbolDemangler(void *storage_ptr, size_t storage_size,
 127                   std::function<void(const char *)> builtins_hook = nullptr)
 128       : m_builtins_hook(builtins_hook) {
 129     // Use up to 1/8th of the provided space for rewrite ranges
 130     m_rewrite_ranges_size = (storage_size >> 3) / sizeof(BufferRange);
 131     m_rewrite_ranges = (BufferRange *)storage_ptr;
 132     m_owns_m_rewrite_ranges = false;
 133
 134     // Use the rest for the character buffer
 135     m_buffer =
 136         (char *)storage_ptr + m_rewrite_ranges_size * sizeof(BufferRange);
 137     m_buffer_end = (const char *)storage_ptr + storage_size;
 138     m_owns_buffer = false;
 139   }
 140
 141   /// @brief Destroys the SymbolDemangler and deallocates any scratch
 142   /// memory that it owns
 143
 144   ~SymbolDemangler() {
 145     if (m_owns_buffer)
 146       free(m_buffer);
 147     if (m_owns_m_rewrite_ranges)
 148       free(m_rewrite_ranges);
 149   }
 150
 151 #ifdef DEBUG_HIGHWATER
 152   int highwater_store = 0;
 153   int highwater_buffer = 0;
 154 #endif
 155
 156   /// @brief Parses the provided mangled name and returns a newly allocated
 157   /// demangling
 158   ///
 159   /// @param mangled_name Valid null-terminated C++ mangled name following
 160   /// the Itanium C++ ABI mangling specification as implemented by Clang
 161   ///
 162   /// @result Newly allocated null-terminated demangled name when demangling
 163   /// is successful, and nullptr when demangling fails.  The caller is
 164   /// responsible for freeing the allocated memory.
 165
 166   char *GetDemangledCopy(const char *mangled_name,
 167                          long mangled_name_length = 0) {
 168     if (!ParseMangling(mangled_name, mangled_name_length))
 169       return nullptr;
 170
 171 #ifdef DEBUG_HIGHWATER
 172     int rewrite_count = m_next_substitute_index +
 173                         (m_rewrite_ranges_size - 1 - m_next_template_arg_index);
 174     int buffer_size = (int)(m_write_ptr - m_buffer);
 175     if (rewrite_count > highwater_store)
 176       highwater_store = rewrite_count;
 177     if (buffer_size > highwater_buffer)
 178       highwater_buffer = buffer_size;
 179 #endif
 180
 181     int length = (int)(m_write_ptr - m_buffer);
 182     char *copy = (char *)malloc(length + 1);
 183     memcpy(copy, m_buffer, length);
 184     copy[length] = '\0';
 185     return copy;
 186   }
 187
 188 private:
 189   //----------------------------------------------------
 190   // Grow methods
 191   //
 192   // Manage the storage used during demangling
 193   //----------------------------------------------------
 194
 195   void GrowBuffer(long min_growth = 0) {
 196     // By default, double the size of the buffer
 197     long growth = m_buffer_end - m_buffer;
 198
 199     // Avoid growing by more than 1MB at a time
 200     if (growth > 1 << 20)
 201       growth = 1 << 20;
 202
 203     // ... but never grow by less than requested,
 204     // or 1K, whichever is greater
 205     if (min_growth < 1024)
 206       min_growth = 1024;
 207     if (growth < min_growth)
 208       growth = min_growth;
 209
 210     // Allocate the new m_buffer and migrate content
 211     long new_size = (m_buffer_end - m_buffer) + growth;
 212     char *new_buffer = (char *)malloc(new_size);
 213     memcpy(new_buffer, m_buffer, m_write_ptr - m_buffer);
 214     if (m_owns_buffer)
 215       free(m_buffer);
 216     m_owns_buffer = true;
 217
 218     // Update references to the new buffer
 219     m_write_ptr = new_buffer + (m_write_ptr - m_buffer);
 220     m_buffer = new_buffer;
 221     m_buffer_end = m_buffer + new_size;
 222   }
 223
 224   void GrowRewriteRanges() {
 225     // By default, double the size of the array
 226     int growth = m_rewrite_ranges_size;
 227
 228     // Apply reasonable minimum and maximum sizes for growth
 229     if (growth > 128)
 230       growth = 128;
 231     if (growth < 16)
 232       growth = 16;
 233
 234     // Allocate the new array and migrate content
 235     int bytes = (m_rewrite_ranges_size + growth) * sizeof(BufferRange);
 236     BufferRange *new_ranges = (BufferRange *)malloc(bytes);
 237     for (int index = 0; index < m_next_substitute_index; index++) {
 238       new_ranges[index] = m_rewrite_ranges[index];
 239     }
 240     for (int index = m_rewrite_ranges_size - 1;
 241          index > m_next_template_arg_index; index--) {
 242       new_ranges[index + growth] = m_rewrite_ranges[index];
 243     }
 244     if (m_owns_m_rewrite_ranges)
 245       free(m_rewrite_ranges);
 246     m_owns_m_rewrite_ranges = true;
 247
 248     // Update references to the new array
 249     m_rewrite_ranges = new_ranges;
 250     m_rewrite_ranges_size += growth;
 251     m_next_template_arg_index += growth;
 252   }
 253
 254   //----------------------------------------------------
 255   // Range and state management
 256   //----------------------------------------------------
 257
 258   int GetStartCookie() { return (int)(m_write_ptr - m_buffer); }
 259
 260   BufferRange EndRange(int start_cookie) {
 261     return {start_cookie, (int)(m_write_ptr - (m_buffer + start_cookie))};
 262   }
 263
 264   void ReorderRange(BufferRange source_range, int insertion_point_cookie) {
 265     // Ensure there's room the preserve the source range
 266     if (m_write_ptr + source_range.length > m_buffer_end) {
 267       GrowBuffer(m_write_ptr + source_range.length - m_buffer_end);
 268     }
 269
 270     // Reorder the content
 271     memcpy(m_write_ptr, m_buffer + source_range.offset, source_range.length);
 272     memmove(m_buffer + insertion_point_cookie + source_range.length,
 273             m_buffer + insertion_point_cookie,
 274             source_range.offset - insertion_point_cookie);
 275     memcpy(m_buffer + insertion_point_cookie, m_write_ptr, source_range.length);
 276
 277     // Fix up rewritable ranges, covering both substitutions and templates
 278     int index = 0;
 279     while (true) {
 280       if (index == m_next_substitute_index)
 281         index = m_next_template_arg_index + 1;
 282       if (index == m_rewrite_ranges_size)
 283         break;
 284
 285       // Affected ranges are either shuffled forward when after the
 286       // insertion but before the source, or backward when inside the
 287       // source
 288       int candidate_offset = m_rewrite_ranges[index].offset;
 289       if (candidate_offset >= insertion_point_cookie) {
 290         if (candidate_offset < source_range.offset) {
 291           m_rewrite_ranges[index].offset += source_range.length;
 292         } else if (candidate_offset >= source_range.offset) {
 293           m_rewrite_ranges[index].offset -=
 294               (source_range.offset - insertion_point_cookie);
 295         }
 296       }
 297       ++index;
 298     }
 299   }
 300
 301   void EndSubstitution(int start_cookie) {
 302     if (m_next_substitute_index == m_next_template_arg_index)
 303       GrowRewriteRanges();
 304
 305     int index = m_next_substitute_index++;
 306     m_rewrite_ranges[index] = EndRange(start_cookie);
 307 #ifdef DEBUG_SUBSTITUTIONS
 308     printf("Saved substitution # %d = %.*s\n", index,
 309            m_rewrite_ranges[index].length, m_buffer + start_cookie);
 310 #endif
 311   }
 312
 313   void EndTemplateArg(int start_cookie) {
 314     if (m_next_substitute_index == m_next_template_arg_index)
 315       GrowRewriteRanges();
 316
 317     int index = m_next_template_arg_index--;
 318     m_rewrite_ranges[index] = EndRange(start_cookie);
 319 #ifdef DEBUG_TEMPLATE_ARGS
 320     printf("Saved template arg # %d = %.*s\n",
 321            m_rewrite_ranges_size - index - 1, m_rewrite_ranges[index].length,
 322            m_buffer + start_cookie);
 323 #endif
 324   }
 325
 326   void ResetTemplateArgs() {
 327     // TODO: this works, but is it the right thing to do?
 328     // Should we push/pop somehow at the call sites?
 329     m_next_template_arg_index = m_rewrite_ranges_size - 1;
 330   }
 331
 332   //----------------------------------------------------
 333   // Write methods
 334   //
 335   // Appends content to the existing output buffer
 336   //----------------------------------------------------
 337
 338   void Write(char character) {
 339     if (m_write_ptr == m_buffer_end)
 340       GrowBuffer();
 341     *m_write_ptr++ = character;
 342   }
 343
 344   void Write(const char *content) { Write(content, strlen(content)); }
 345
 346   void Write(const char *content, long content_length) {
 347     char *end_m_write_ptr = m_write_ptr + content_length;
 348     if (end_m_write_ptr > m_buffer_end) {
 349       if (content >= m_buffer && content < m_buffer_end) {
 350         long offset = content - m_buffer;
 351         GrowBuffer(end_m_write_ptr - m_buffer_end);
 352         content = m_buffer + offset;
 353       } else {
 354         GrowBuffer(end_m_write_ptr - m_buffer_end);
 355       }
 356       end_m_write_ptr = m_write_ptr + content_length;
 357     }
 358     memcpy(m_write_ptr, content, content_length);
 359     m_write_ptr = end_m_write_ptr;
 360   }
 361 #define WRITE(x) Write(x, sizeof(x) - 1)
 362
 363   void WriteTemplateStart() { Write('<'); }
 364
 365   void WriteTemplateEnd() {
 366     // Put a space between terminal > characters when nesting templates
 367     if (m_write_ptr != m_buffer && *(m_write_ptr - 1) == '>')
 368       WRITE(" >");
 369     else
 370       Write('>');
 371   }
 372
 373   void WriteCommaSpace() { WRITE(", "); }
 374
 375   void WriteNamespaceSeparator() { WRITE("::"); }
 376
 377   void WriteStdPrefix() { WRITE("std::"); }
 378
 379   void WriteQualifiers(int qualifiers, bool space_before_reference = true) {
 380     if (qualifiers & QualifierPointer)
 381       Write('*');
 382     if (qualifiers & QualifierConst)
 383       WRITE(" const");
 384     if (qualifiers & QualifierVolatile)
 385       WRITE(" volatile");
 386     if (qualifiers & QualifierRestrict)
 387       WRITE(" restrict");
 388     if (qualifiers & QualifierReference) {
 389       if (space_before_reference)
 390         WRITE(" &");
 391       else
 392         Write('&');
 393     }
 394     if (qualifiers & QualifierRValueReference) {
 395       if (space_before_reference)
 396         WRITE(" &&");
 397       else
 398         WRITE("&&");
 399     }
 400   }
 401
 402   //----------------------------------------------------
 403   // Rewrite methods
 404   //
 405   // Write another copy of content already present
 406   // earlier in the output buffer
 407   //----------------------------------------------------
 408
 409   void RewriteRange(BufferRange range) {
 410     Write(m_buffer + range.offset, range.length);
 411   }
 412
 413   bool RewriteSubstitution(int index) {
 414     if (index < 0 || index >= m_next_substitute_index) {
 415 #ifdef DEBUG_FAILURES
 416       printf("*** Invalid substitution #%d\n", index);
 417 #endif
 418       return false;
 419     }
 420     RewriteRange(m_rewrite_ranges[index]);
 421     return true;
 422   }
 423
 424   bool RewriteTemplateArg(int template_index) {
 425     int index = m_rewrite_ranges_size - 1 - template_index;
 426     if (template_index < 0 || index <= m_next_template_arg_index) {
 427 #ifdef DEBUG_FAILURES
 428       printf("*** Invalid template arg reference #%d\n", template_index);
 429 #endif
 430       return false;
 431     }
 432     RewriteRange(m_rewrite_ranges[index]);
 433     return true;
 434   }
 435
 436   //----------------------------------------------------
 437   // TryParse methods
 438   //
 439   // Provide information with return values instead of
 440   // writing to the output buffer
 441   //
 442   // Values indicating failure guarantee that the pre-
 443   // call m_read_ptr is unchanged
 444   //----------------------------------------------------
 445
 446   int TryParseNumber() {
 447     unsigned char digit = *m_read_ptr - '0';
 448     if (digit > 9)
 449       return -1;
 450
 451     int count = digit;
 452     while (true) {
 453       digit = *++m_read_ptr - '0';
 454       if (digit > 9)
 455         break;
 456
 457       count = count * 10 + digit;
 458     }
 459     return count;
 460   }
 461
 462   int TryParseBase36Number() {
 463     char digit = *m_read_ptr;
 464     int count;
 465     if (digit >= '0' && digit <= '9')
 466       count = digit -= '0';
 467     else if (digit >= 'A' && digit <= 'Z')
 468       count = digit -= ('A' - 10);
 469     else
 470       return -1;
 471
 472     while (true) {
 473       digit = *++m_read_ptr;
 474       if (digit >= '0' && digit <= '9')
 475         digit -= '0';
 476       else if (digit >= 'A' && digit <= 'Z')
 477         digit -= ('A' - 10);
 478       else
 479         break;
 480
 481       count = count * 36 + digit;
 482     }
 483     return count;
 484   }
 485
 486   // <builtin-type> ::= v    # void
 487   //                ::= w    # wchar_t
 488   //                ::= b    # bool
 489   //                ::= c    # char
 490   //                ::= a    # signed char
 491   //                ::= h    # unsigned char
 492   //                ::= s    # short
 493   //                ::= t    # unsigned short
 494   //                ::= i    # int
 495   //                ::= j    # unsigned int
 496   //                ::= l    # long
 497   //                ::= m    # unsigned long
 498   //                ::= x    # long long, __int64
 499   //                ::= y    # unsigned long long, __int64
 500   //                ::= n    # __int128
 501   //                ::= o    # unsigned __int128
 502   //                ::= f    # float
 503   //                ::= d    # double
 504   //                ::= e    # long double, __float80
 505   //                ::= g    # __float128
 506   //                ::= z    # ellipsis
 507   //                ::= Dd   # IEEE 754r decimal floating point (64 bits)
 508   //                ::= De   # IEEE 754r decimal floating point (128 bits)
 509   //                ::= Df   # IEEE 754r decimal floating point (32 bits)
 510   //                ::= Dh   # IEEE 754r half-precision floating point (16 bits)
 511   //                ::= Di   # char32_t
 512   //                ::= Ds   # char16_t
 513   //                ::= Da   # auto (in dependent new-expressions)
 514   //                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))
 515   //                ::= u <source-name>    # vendor extended type
 516
 517   const char *TryParseBuiltinType() {
 518     if (m_builtins_hook)
 519       m_builtins_hook(m_read_ptr);
 520
 521     switch (*m_read_ptr++) {
 522     case 'v':
 523       return "void";
 524     case 'w':
 525       return "wchar_t";
 526     case 'b':
 527       return "bool";
 528     case 'c':
 529       return "char";
 530     case 'a':
 531       return "signed char";
 532     case 'h':
 533       return "unsigned char";
 534     case 's':
 535       return "short";
 536     case 't':
 537       return "unsigned short";
 538     case 'i':
 539       return "int";
 540     case 'j':
 541       return "unsigned int";
 542     case 'l':
 543       return "long";
 544     case 'm':
 545       return "unsigned long";
 546     case 'x':
 547       return "long long";
 548     case 'y':
 549       return "unsigned long long";
 550     case 'n':
 551       return "__int128";
 552     case 'o':
 553       return "unsigned __int128";
 554     case 'f':
 555       return "float";
 556     case 'd':
 557       return "double";
 558     case 'e':
 559       return "long double";
 560     case 'g':
 561       return "__float128";
 562     case 'z':
 563       return "...";
 564     case 'D': {
 565       switch (*m_read_ptr++) {
 566       case 'd':
 567         return "decimal64";
 568       case 'e':
 569         return "decimal128";
 570       case 'f':
 571         return "decimal32";
 572       case 'h':
 573         return "decimal16";
 574       case 'i':
 575         return "char32_t";
 576       case 's':
 577         return "char16_t";
 578       case 'a':
 579         return "auto";
 580       case 'c':
 581         return "decltype(auto)";
 582       case 'n':
 583         return "std::nullptr_t";
 584       default:
 585         --m_read_ptr;
 586       }
 587     }
 588     }
 589     --m_read_ptr;
 590     return nullptr;
 591   }
 592
 593   //   <operator-name>
 594   //                   ::= aa    # &&
 595   //                   ::= ad    # & (unary)
 596   //                   ::= an    # &
 597   //                   ::= aN    # &=
 598   //                   ::= aS    # =
 599   //                   ::= cl    # ()
 600   //                   ::= cm    # ,
 601   //                   ::= co    # ~
 602   //                   ::= da    # delete[]
 603   //                   ::= de    # * (unary)
 604   //                   ::= dl    # delete
 605   //                   ::= dv    # /
 606   //                   ::= dV    # /=
 607   //                   ::= eo    # ^
 608   //                   ::= eO    # ^=
 609   //                   ::= eq    # ==
 610   //                   ::= ge    # >=
 611   //                   ::= gt    # >
 612   //                   ::= ix    # []
 613   //                   ::= le    # <=
 614   //                   ::= ls    # <<
 615   //                   ::= lS    # <<=
 616   //                   ::= lt    # <
 617   //                   ::= mi    # -
 618   //                   ::= mI    # -=
 619   //                   ::= ml    # *
 620   //                   ::= mL    # *=
 621   //                   ::= mm    # -- (postfix in <expression> context)
 622   //                   ::= na    # new[]
 623   //                   ::= ne    # !=
 624   //                   ::= ng    # - (unary)
 625   //                   ::= nt    # !
 626   //                   ::= nw    # new
 627   //                   ::= oo    # ||
 628   //                   ::= or    # |
 629   //                   ::= oR    # |=
 630   //                   ::= pm    # ->*
 631   //                   ::= pl    # +
 632   //                   ::= pL    # +=
 633   //                   ::= pp    # ++ (postfix in <expression> context)
 634   //                   ::= ps    # + (unary)
 635   //                   ::= pt    # ->
 636   //                   ::= qu    # ?
 637   //                   ::= rm    # %
 638   //                   ::= rM    # %=
 639   //                   ::= rs    # >>
 640   //                   ::= rS    # >>=
 641   //                   ::= cv <type>    # (cast)
 642   //                   ::= v <digit> <source-name>        # vendor extended
 643   //                   operator
 644
 645   Operator TryParseOperator() {
 646     switch (*m_read_ptr++) {
 647     case 'a':
 648       switch (*m_read_ptr++) {
 649       case 'a':
 650         return {"&&", OperatorKind::Binary};
 651       case 'd':
 652         return {"&", OperatorKind::Unary};
 653       case 'n':
 654         return {"&", OperatorKind::Binary};
 655       case 'N':
 656         return {"&=", OperatorKind::Binary};
 657       case 'S':
 658         return {"=", OperatorKind::Binary};
 659       }
 660       --m_read_ptr;
 661       break;
 662     case 'c':
 663       switch (*m_read_ptr++) {
 664       case 'l':
 665         return {"()", OperatorKind::Other};
 666       case 'm':
 667         return {",", OperatorKind::Other};
 668       case 'o':
 669         return {"~", OperatorKind::Unary};
 670       case 'v':
 671         return {nullptr, OperatorKind::ConversionOperator};
 672       }
 673       --m_read_ptr;
 674       break;
 675     case 'd':
 676       switch (*m_read_ptr++) {
 677       case 'a':
 678         return {" delete[]", OperatorKind::Other};
 679       case 'e':
 680         return {"*", OperatorKind::Unary};
 681       case 'l':
 682         return {" delete", OperatorKind::Other};
 683       case 'v':
 684         return {"/", OperatorKind::Binary};
 685       case 'V':
 686         return {"/=", OperatorKind::Binary};
 687       }
 688       --m_read_ptr;
 689       break;
 690     case 'e':
 691       switch (*m_read_ptr++) {
 692       case 'o':
 693         return {"^", OperatorKind::Binary};
 694       case 'O':
 695         return {"^=", OperatorKind::Binary};
 696       case 'q':
 697         return {"==", OperatorKind::Binary};
 698       }
 699       --m_read_ptr;
 700       break;
 701     case 'g':
 702       switch (*m_read_ptr++) {
 703       case 'e':
 704         return {">=", OperatorKind::Binary};
 705       case 't':
 706         return {">", OperatorKind::Binary};
 707       }
 708       --m_read_ptr;
 709       break;
 710     case 'i':
 711       switch (*m_read_ptr++) {
 712       case 'x':
 713         return {"[]", OperatorKind::Other};
 714       }
 715       --m_read_ptr;
 716       break;
 717     case 'l':
 718       switch (*m_read_ptr++) {
 719       case 'e':
 720         return {"<=", OperatorKind::Binary};
 721       case 's':
 722         return {"<<", OperatorKind::Binary};
 723       case 'S':
 724         return {"<<=", OperatorKind::Binary};
 725       case 't':
 726         return {"<", OperatorKind::Binary};
 727         // case 'i': return { "?", OperatorKind::Binary };
 728       }
 729       --m_read_ptr;
 730       break;
 731     case 'm':
 732       switch (*m_read_ptr++) {
 733       case 'i':
 734         return {"-", OperatorKind::Binary};
 735       case 'I':
 736         return {"-=", OperatorKind::Binary};
 737       case 'l':
 738         return {"*", OperatorKind::Binary};
 739       case 'L':
 740         return {"*=", OperatorKind::Binary};
 741       case 'm':
 742         return {"--", OperatorKind::Postfix};
 743       }
 744       --m_read_ptr;
 745       break;
 746     case 'n':
 747       switch (*m_read_ptr++) {
 748       case 'a':
 749         return {" new[]", OperatorKind::Other};
 750       case 'e':
 751         return {"!=", OperatorKind::Binary};
 752       case 'g':
 753         return {"-", OperatorKind::Unary};
 754       case 't':
 755         return {"!", OperatorKind::Unary};
 756       case 'w':
 757         return {" new", OperatorKind::Other};
 758       }
 759       --m_read_ptr;
 760       break;
 761     case 'o':
 762       switch (*m_read_ptr++) {
 763       case 'o':
 764         return {"||", OperatorKind::Binary};
 765       case 'r':
 766         return {"|", OperatorKind::Binary};
 767       case 'R':
 768         return {"|=", OperatorKind::Binary};
 769       }
 770       --m_read_ptr;
 771       break;
 772     case 'p':
 773       switch (*m_read_ptr++) {
 774       case 'm':
 775         return {"->*", OperatorKind::Binary};
 776       case 's':
 777         return {"+", OperatorKind::Unary};
 778       case 'l':
 779         return {"+", OperatorKind::Binary};
 780       case 'L':
 781         return {"+=", OperatorKind::Binary};
 782       case 'p':
 783         return {"++", OperatorKind::Postfix};
 784       case 't':
 785         return {"->", OperatorKind::Binary};
 786       }
 787       --m_read_ptr;
 788       break;
 789     case 'q':
 790       switch (*m_read_ptr++) {
 791       case 'u':
 792         return {"?", OperatorKind::Ternary};
 793       }
 794       --m_read_ptr;
 795       break;
 796     case 'r':
 797       switch (*m_read_ptr++) {
 798       case 'm':
 799         return {"%", OperatorKind::Binary};
 800       case 'M':
 801         return {"%=", OperatorKind::Binary};
 802       case 's':
 803         return {">>", OperatorKind::Binary};
 804       case 'S':
 805         return {">=", OperatorKind::Binary};
 806       }
 807       --m_read_ptr;
 808       break;
 809     case 'v':
 810       char digit = *m_read_ptr;
 811       if (digit >= '0' && digit <= '9') {
 812         m_read_ptr++;
 813         return {nullptr, OperatorKind::Vendor};
 814       }
 815       --m_read_ptr;
 816       break;
 817     }
 818     --m_read_ptr;
 819     return {nullptr, OperatorKind::NoMatch};
 820   }
 821
 822   // <CV-qualifiers> ::= [r] [V] [K]
 823   // <ref-qualifier> ::= R                   # & ref-qualifier
 824   // <ref-qualifier> ::= O                   # && ref-qualifier
 825
 826   int TryParseQualifiers(bool allow_cv, bool allow_ro) {
 827     int qualifiers = QualifierNone;
 828     char next = *m_read_ptr;
 829     if (allow_cv) {
 830       if (next == 'r') // restrict
 831       {
 832         qualifiers |= QualifierRestrict;
 833         next = *++m_read_ptr;
 834       }
 835       if (next == 'V') // volatile
 836       {
 837         qualifiers |= QualifierVolatile;
 838         next = *++m_read_ptr;
 839       }
 840       if (next == 'K') // const
 841       {
 842         qualifiers |= QualifierConst;
 843         next = *++m_read_ptr;
 844       }
 845     }
 846     if (allow_ro) {
 847       if (next == 'R') {
 848         ++m_read_ptr;
 849         qualifiers |= QualifierReference;
 850       } else if (next == 'O') {
 851         ++m_read_ptr;
 852         qualifiers |= QualifierRValueReference;
 853       }
 854     }
 855     return qualifiers;
 856   }
 857
 858   // <discriminator> := _ <non-negative number>      # when number < 10
 859   //                 := __ <non-negative number> _   # when number >= 10
 860   //  extension      := decimal-digit+
 861
 862   int TryParseDiscriminator() {
 863     const char *discriminator_start = m_read_ptr;
 864
 865     // Test the extension first, since it's what Clang uses
 866     int discriminator_value = TryParseNumber();
 867     if (discriminator_value != -1)
 868       return discriminator_value;
 869
 870     char next = *m_read_ptr;
 871     if (next == '_') {
 872       next = *++m_read_ptr;
 873       if (next == '_') {
 874         ++m_read_ptr;
 875         discriminator_value = TryParseNumber();
 876         if (discriminator_value != -1 && *m_read_ptr++ != '_') {
 877           return discriminator_value;
 878         }
 879       } else if (next >= '0' && next <= '9') {
 880         ++m_read_ptr;
 881         return next - '0';
 882       }
 883     }
 884
 885     // Not a valid discriminator
 886     m_read_ptr = discriminator_start;
 887     return -1;
 888   }
 889
 890   //----------------------------------------------------
 891   // Parse methods
 892   //
 893   // Consume input starting from m_read_ptr and produce
 894   // buffered output at m_write_ptr
 895   //
 896   // Failures return false and may leave m_read_ptr in an
 897   // indeterminate state
 898   //----------------------------------------------------
 899
 900   bool Parse(char character) {
 901     if (*m_read_ptr++ == character)
 902       return true;
 903 #ifdef DEBUG_FAILURES
 904     printf("*** Expected '%c'\n", character);
 905 #endif
 906     return false;
 907   }
 908
 909   // <number> ::= [n] <non-negative decimal integer>
 910
 911   bool ParseNumber(bool allow_negative = false) {
 912     if (allow_negative && *m_read_ptr == 'n') {
 913       Write('-');
 914       ++m_read_ptr;
 915     }
 916     const char *before_digits = m_read_ptr;
 917     while (true) {
 918       unsigned char digit = *m_read_ptr - '0';
 919       if (digit > 9)
 920         break;
 921       ++m_read_ptr;
 922     }
 923     if (int digit_count = (int)(m_read_ptr - before_digits)) {
 924       Write(before_digits, digit_count);
 925       return true;
 926     }
 927 #ifdef DEBUG_FAILURES
 928     printf("*** Expected number\n");
 929 #endif
 930     return false;
 931   }
 932
 933   // <substitution> ::= S <seq-id> _
 934   //                ::= S_
 935   // <substitution> ::= Sa # ::std::allocator
 936   // <substitution> ::= Sb # ::std::basic_string
 937   // <substitution> ::= Ss # ::std::basic_string < char,
 938   //                                               ::std::char_traits<char>,
 939   //                                               ::std::allocator<char> >
 940   // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char>
 941   // >
 942   // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char>
 943   // >
 944   // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char>
 945   // >
 946
 947   bool ParseSubstitution() {
 948     const char *substitution;
 949     switch (*m_read_ptr) {
 950     case 'a':
 951       substitution = "std::allocator";
 952       break;
 953     case 'b':
 954       substitution = "std::basic_string";
 955       break;
 956     case 's':
 957       substitution = "std::string";
 958       break;
 959     case 'i':
 960       substitution = "std::istream";
 961       break;
 962     case 'o':
 963       substitution = "std::ostream";
 964       break;
 965     case 'd':
 966       substitution = "std::iostream";
 967       break;
 968     default:
 969       // A failed attempt to parse a number will return -1 which turns out to be
 970       // perfect here as S_ is the first substitution, S0_ the next and so forth
 971       int substitution_index = TryParseBase36Number();
 972       if (*m_read_ptr++ != '_') {
 973 #ifdef DEBUG_FAILURES
 974         printf("*** Expected terminal _ in substitution\n");
 975 #endif
 976         return false;
 977       }
 978       return RewriteSubstitution(substitution_index + 1);
 979     }
 980     Write(substitution);
 981     ++m_read_ptr;
 982     return true;
 983   }
 984
 985   // <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
 986   //
 987   // <bare-function-type> ::= <signature type>+      # types are possible return
 988   // type, then parameter types
 989
 990   bool ParseFunctionType(int inner_qualifiers = QualifierNone) {
 991 #ifdef DEBUG_FAILURES
 992     printf("*** Function types not supported\n");
 993 #endif
 994     // TODO: first steps toward an implementation follow, but they're far
 995     // from complete.  Function types tend to bracket other types eg:
 996     // int (*)() when used as the type for "name" becomes int (*name)().
 997     // This makes substitution et al ... interesting.
 998     return false;
 999
1000 #if 0  // TODO
1001         if (*m_read_ptr == 'Y')
1002             ++m_read_ptr;
1003
1004         int return_type_start_cookie = GetStartCookie();
1005         if (!ParseType())
1006             return false;
1007         Write(' ');
1008
1009         int insert_cookie = GetStartCookie();
1010         Write('(');
1011         bool first_param = true;
1012         int qualifiers = QualifierNone;
1013         while (true)
1014         {
1015             switch (*m_read_ptr)
1016             {
1017                 case 'E':
1018                     ++m_read_ptr;
1019                     Write(')');
1020                     break;
1021                 case 'v':
1022                     ++m_read_ptr;
1023                     continue;
1024                 case 'R':
1025                 case 'O':
1026                     if (*(m_read_ptr + 1) == 'E')
1027                     {
1028                         qualifiers = TryParseQualifiers (false, true);
1029                         Parse('E');
1030                         break;
1031                     }
1032                     // fallthrough
1033                 default:
1034                 {
1035                     if (first_param)
1036                         first_param = false;
1037                     else WriteCommaSpace();
1038
1039                     if (!ParseType())
1040                         return false;
1041                     continue;
1042                 }
1043             }
1044             break;
1045         }
1046
1047         if (qualifiers)
1048         {
1049             WriteQualifiers (qualifiers);
1050             EndSubstitution (return_type_start_cookie);
1051         }
1052
1053         if (inner_qualifiers)
1054         {
1055             int qualifier_start_cookie = GetStartCookie();
1056             Write ('(');
1057             WriteQualifiers (inner_qualifiers);
1058             Write (')');
1059             ReorderRange (EndRange (qualifier_start_cookie), insert_cookie);
1060         }
1061         return true;
1062 #endif // TODO
1063   }
1064
1065   // <array-type> ::= A <positive dimension number> _ <element type>
1066   //              ::= A [<dimension expression>] _ <element type>
1067
1068   bool ParseArrayType(int qualifiers = QualifierNone) {
1069 #ifdef DEBUG_FAILURES
1070     printf("*** Array type unsupported\n");
1071 #endif
1072     // TODO: We fail horribly when recalling these as substitutions or
1073     // templates and trying to constify them eg:
1074     // _ZN4llvm2cl5applyIA28_cNS0_3optIbLb0ENS0_6parserIbEEEEEEvRKT_PT0_
1075     //
1076     // TODO: Chances are we don't do any better with references and pointers
1077     // that should be type (&) [] instead of type & []
1078
1079     return false;
1080
1081 #if 0  // TODO
1082         if (*m_read_ptr == '_')
1083         {
1084             ++m_read_ptr;
1085             if (!ParseType())
1086                 return false;
1087             if (qualifiers)
1088                 WriteQualifiers(qualifiers);
1089             WRITE(" []");
1090             return true;
1091         }
1092         else
1093         {
1094             const char *before_digits = m_read_ptr;
1095             if (TryParseNumber() != -1)
1096             {
1097                 const char *after_digits = m_read_ptr;
1098                 if (!Parse('_'))
1099                     return false;
1100                 if (!ParseType())
1101                     return false;
1102                 if (qualifiers)
1103                     WriteQualifiers(qualifiers);
1104                 Write(' ');
1105                 Write('[');
1106                 Write(before_digits, after_digits - before_digits);
1107             }
1108             else
1109             {
1110                 int type_insertion_cookie = GetStartCookie();
1111                 if (!ParseExpression())
1112                     return false;
1113                 if (!Parse('_'))
1114                     return false;
1115
1116                 int type_start_cookie = GetStartCookie();
1117                 if (!ParseType())
1118                     return false;
1119                 if (qualifiers)
1120                     WriteQualifiers(qualifiers);
1121                 Write(' ');
1122                 Write('[');
1123                 ReorderRange (EndRange (type_start_cookie), type_insertion_cookie);
1124             }
1125             Write(']');
1126             return true;
1127         }
1128 #endif // TODO
1129   }
1130
1131   // <pointer-to-member-type> ::= M <class type> <member type>
1132
1133   // TODO: Determine how to handle pointers to function members correctly,
1134   // currently not an issue because we don't have function types at all...
1135   bool ParsePointerToMemberType() {
1136     int insertion_cookie = GetStartCookie();
1137     Write(' ');
1138     if (!ParseType())
1139       return false;
1140     WRITE("::*");
1141
1142     int type_cookie = GetStartCookie();
1143     if (!ParseType())
1144       return false;
1145     ReorderRange(EndRange(type_cookie), insertion_cookie);
1146     return true;
1147   }
1148
1149   // <template-param> ::= T_    # first template parameter
1150   //                  ::= T <parameter-2 non-negative number> _
1151
1152   bool ParseTemplateParam() {
1153     int count = TryParseNumber();
1154     if (!Parse('_'))
1155       return false;
1156
1157     // When no number is present we get -1, which is convenient since
1158     // T_ is the zeroth element T0_ is element 1, and so on
1159     return RewriteTemplateArg(count + 1);
1160   }
1161
1162   // <vector-type>
1163   // Dv <dimension number> _ <vector type>
1164   bool TryParseVectorType() {
1165     const int dimension = TryParseNumber();
1166     if (dimension == -1)
1167       return false;
1168
1169     if (*m_read_ptr++ != '_')
1170       return false;
1171
1172     char vec_dimens[32] = {'\0'};
1173     ::snprintf(vec_dimens, sizeof vec_dimens - 1, " __vector(%d)", dimension);
1174     ParseType();
1175     Write(vec_dimens);
1176     return true;
1177   }
1178
1179   // <type> ::= <builtin-type>
1180   //        ::= <function-type>
1181   //        ::= <class-enum-type>
1182   //        ::= <array-type>
1183   //        ::= <pointer-to-member-type>
1184   //        ::= <template-param>
1185   //        ::= <template-template-param> <template-args>
1186   //        ::= <decltype>
1187   //        ::= <substitution>
1188   //        ::= <CV-qualifiers> <type>
1189   //        ::= P <type>        # pointer-to
1190   //        ::= R <type>        # reference-to
1191   //        ::= O <type>        # rvalue reference-to (C++0x)
1192   //        ::= C <type>        # complex pair (C 2000)
1193   //        ::= G <type>        # imaginary (C 2000)
1194   //        ::= Dp <type>       # pack expansion (C++0x)
1195   //        ::= U <source-name> <type>  # vendor extended type qualifier
1196   // extension := U <objc-name> <objc-type>  # objc-type<identifier>
1197   // extension := <vector-type> # <vector-type> starts with Dv
1198
1199   // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 +
1200   // <number of digits in k1> + k1
1201   // <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name>
1202   // 11objc_object -> id<source-name>
1203
1204   bool ParseType() {
1205 #ifdef DEBUG_FAILURES
1206     const char *failed_type = m_read_ptr;
1207 #endif
1208     int type_start_cookie = GetStartCookie();
1209     bool suppress_substitution = false;
1210
1211     int qualifiers = TryParseQualifiers(true, false);
1212     switch (*m_read_ptr) {
1213     case 'D':
1214       ++m_read_ptr;
1215       switch (*m_read_ptr++) {
1216       case 'p':
1217         if (!ParseType())
1218           return false;
1219         break;
1220       case 'v':
1221         if (!TryParseVectorType())
1222           return false;
1223         break;
1224       case 'T':
1225       case 't':
1226       default:
1227 #ifdef DEBUG_FAILURES
1228         printf("*** Unsupported type: %.3s\n", failed_type);
1229 #endif
1230         return false;
1231       }
1232       break;
1233     case 'T':
1234       ++m_read_ptr;
1235       if (!ParseTemplateParam())
1236         return false;
1237       break;
1238     case 'M':
1239       ++m_read_ptr;
1240       if (!ParsePointerToMemberType())
1241         return false;
1242       break;
1243     case 'A':
1244       ++m_read_ptr;
1245       if (!ParseArrayType())
1246         return false;
1247       break;
1248     case 'F':
1249       ++m_read_ptr;
1250       if (!ParseFunctionType())
1251         return false;
1252       break;
1253     case 'S':
1254       if (*++m_read_ptr == 't') {
1255         ++m_read_ptr;
1256         WriteStdPrefix();
1257         if (!ParseName())
1258           return false;
1259       } else {
1260         suppress_substitution = true;
1261         if (!ParseSubstitution())
1262           return false;
1263       }
1264       break;
1265     case 'P': {
1266       switch (*++m_read_ptr) {
1267       case 'F':
1268         ++m_read_ptr;
1269         if (!ParseFunctionType(QualifierPointer))
1270           return false;
1271         break;
1272       default:
1273         if (!ParseType())
1274           return false;
1275         Write('*');
1276         break;
1277       }
1278       break;
1279     }
1280     case 'R': {
1281       ++m_read_ptr;
1282       if (!ParseType())
1283         return false;
1284       Write('&');
1285       break;
1286     }
1287     case 'O': {
1288       ++m_read_ptr;
1289       if (!ParseType())
1290         return false;
1291       Write('&');
1292       Write('&');
1293       break;
1294     }
1295     case 'C':
1296     case 'G':
1297     case 'U':
1298 #ifdef DEBUG_FAILURES
1299       printf("*** Unsupported type: %.3s\n", failed_type);
1300 #endif
1301       return false;
1302     // Test for common cases to avoid TryParseBuiltinType() overhead
1303     case 'N':
1304     case 'Z':
1305     case 'L':
1306       if (!ParseName())
1307         return false;
1308       break;
1309     default:
1310       if (const char *builtin = TryParseBuiltinType()) {
1311         Write(builtin);
1312         suppress_substitution = true;
1313       } else {
1314         if (!ParseName())
1315           return false;
1316       }
1317       break;
1318     }
1319
1320     // Allow base substitutions to be suppressed, but always record
1321     // substitutions for the qualified variant
1322     if (!suppress_substitution)
1323       EndSubstitution(type_start_cookie);
1324     if (qualifiers) {
1325       WriteQualifiers(qualifiers, false);
1326       EndSubstitution(type_start_cookie);
1327     }
1328     return true;
1329   }
1330
1331   // <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
1332   //                     ::= <closure-type-name>
1333   //
1334   // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
1335   //
1336   // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda
1337   // has no parameters
1338
1339   bool ParseUnnamedTypeName(NameState &name_state) {
1340     switch (*m_read_ptr++) {
1341     case 't': {
1342       int cookie = GetStartCookie();
1343       WRITE("'unnamed");
1344       const char *before_digits = m_read_ptr;
1345       if (TryParseNumber() != -1)
1346         Write(before_digits, m_read_ptr - before_digits);
1347       if (!Parse('_'))
1348         return false;
1349       Write('\'');
1350       name_state.last_name_range = EndRange(cookie);
1351       return true;
1352     }
1353     case 'b': {
1354       int cookie = GetStartCookie();
1355       WRITE("'block");
1356       const char *before_digits = m_read_ptr;
1357       if (TryParseNumber() != -1)
1358         Write(before_digits, m_read_ptr - before_digits);
1359       if (!Parse('_'))
1360         return false;
1361       Write('\'');
1362       name_state.last_name_range = EndRange(cookie);
1363       return true;
1364     }
1365     case 'l':
1366 #ifdef DEBUG_FAILURES
1367       printf("*** Lambda type names unsupported\n");
1368 #endif
1369       return false;
1370     }
1371 #ifdef DEBUG_FAILURES
1372     printf("*** Unknown unnamed type %.3s\n", m_read_ptr - 2);
1373 #endif
1374     return false;
1375   }
1376
1377   // <ctor-dtor-name> ::= C1      # complete object constructor
1378   //                  ::= C2      # base object constructor
1379   //                  ::= C3      # complete object allocating constructor
1380
1381   bool ParseCtor(NameState &name_state) {
1382     char next = *m_read_ptr;
1383     if (next == '1' || next == '2' || next == '3' || next == '5') {
1384       RewriteRange(name_state.last_name_range);
1385       name_state.has_no_return_type = true;
1386       ++m_read_ptr;
1387       return true;
1388     }
1389 #ifdef DEBUG_FAILURES
1390     printf("*** Broken constructor\n");
1391 #endif
1392     return false;
1393   }
1394
1395   // <ctor-dtor-name> ::= D0      # deleting destructor
1396   //                  ::= D1      # complete object destructor
1397   //                  ::= D2      # base object destructor
1398
1399   bool ParseDtor(NameState &name_state) {
1400     char next = *m_read_ptr;
1401     if (next == '0' || next == '1' || next == '2' || next == '5') {
1402       Write('~');
1403       RewriteRange(name_state.last_name_range);
1404       name_state.has_no_return_type = true;
1405       ++m_read_ptr;
1406       return true;
1407     }
1408 #ifdef DEBUG_FAILURES
1409     printf("*** Broken destructor\n");
1410 #endif
1411     return false;
1412   }
1413
1414   // See TryParseOperator()
1415
1416   bool ParseOperatorName(NameState &name_state) {
1417 #ifdef DEBUG_FAILURES
1418     const char *operator_ptr = m_read_ptr;
1419 #endif
1420     Operator parsed_operator = TryParseOperator();
1421     if (parsed_operator.name) {
1422       WRITE("operator");
1423       Write(parsed_operator.name);
1424       return true;
1425     }
1426
1427     // Handle special operators
1428     switch (parsed_operator.kind) {
1429     case OperatorKind::Vendor:
1430       WRITE("operator ");
1431       return ParseSourceName();
1432     case OperatorKind::ConversionOperator:
1433       ResetTemplateArgs();
1434       name_state.has_no_return_type = true;
1435       WRITE("operator ");
1436       return ParseType();
1437     default:
1438 #ifdef DEBUG_FAILURES
1439       printf("*** Unknown operator: %.2s\n", operator_ptr);
1440 #endif
1441       return false;
1442     }
1443   }
1444
1445   // <source-name> ::= <positive length number> <identifier>
1446
1447   bool ParseSourceName() {
1448     int count = TryParseNumber();
1449     if (count == -1) {
1450 #ifdef DEBUG_FAILURES
1451       printf("*** Malformed source name, missing length count\n");
1452 #endif
1453       return false;
1454     }
1455
1456     const char *next_m_read_ptr = m_read_ptr + count;
1457     if (next_m_read_ptr > m_read_end) {
1458 #ifdef DEBUG_FAILURES
1459       printf("*** Malformed source name, premature termination\n");
1460 #endif
1461       return false;
1462     }
1463
1464     if (count >= 10 && strncmp(m_read_ptr, "_GLOBAL__N", 10) == 0)
1465       WRITE("(anonymous namespace)");
1466     else
1467       Write(m_read_ptr, count);
1468
1469     m_read_ptr = next_m_read_ptr;
1470     return true;
1471   }
1472
1473   // <unqualified-name> ::= <operator-name>
1474   //                    ::= <ctor-dtor-name>
1475   //                    ::= <source-name>
1476   //                    ::= <unnamed-type-name>
1477
1478   bool ParseUnqualifiedName(NameState &name_state) {
1479     // Note that these are detected directly in ParseNestedName for
1480     // performance rather than switching on the same options twice
1481     char next = *m_read_ptr;
1482     switch (next) {
1483     case 'C':
1484       ++m_read_ptr;
1485       return ParseCtor(name_state);
1486     case 'D':
1487       ++m_read_ptr;
1488       return ParseDtor(name_state);
1489     case 'U':
1490       ++m_read_ptr;
1491       return ParseUnnamedTypeName(name_state);
1492     case '0':
1493     case '1':
1494     case '2':
1495     case '3':
1496     case '4':
1497     case '5':
1498     case '6':
1499     case '7':
1500     case '8':
1501     case '9': {
1502       int name_start_cookie = GetStartCookie();
1503       if (!ParseSourceName())
1504         return false;
1505       name_state.last_name_range = EndRange(name_start_cookie);
1506       return true;
1507     }
1508     default:
1509       return ParseOperatorName(name_state);
1510     };
1511   }
1512
1513   // <unscoped-name> ::= <unqualified-name>
1514   //                 ::= St <unqualified-name>   # ::std::
1515   // extension       ::= StL<unqualified-name>
1516
1517   bool ParseUnscopedName(NameState &name_state) {
1518     if (*m_read_ptr == 'S' && *(m_read_ptr + 1) == 't') {
1519       WriteStdPrefix();
1520       if (*(m_read_ptr += 2) == 'L')
1521         ++m_read_ptr;
1522     }
1523     return ParseUnqualifiedName(name_state);
1524   }
1525
1526   bool ParseIntegerLiteral(const char *prefix, const char *suffix,
1527                            bool allow_negative) {
1528     if (prefix)
1529       Write(prefix);
1530     if (!ParseNumber(allow_negative))
1531       return false;
1532     if (suffix)
1533       Write(suffix);
1534     return Parse('E');
1535   }
1536
1537   bool ParseBooleanLiteral() {
1538     switch (*m_read_ptr++) {
1539     case '0':
1540       WRITE("false");
1541       break;
1542     case '1':
1543       WRITE("true");
1544       break;
1545     default:
1546 #ifdef DEBUG_FAILURES
1547       printf("*** Boolean literal not 0 or 1\n");
1548 #endif
1549       return false;
1550     }
1551     return Parse('E');
1552   }
1553
1554   // <expr-primary> ::= L <type> <value number> E                          #
1555   // integer literal
1556   //                ::= L <type> <value float> E                           #
1557   //                floating literal
1558   //                ::= L <string type> E                                  #
1559   //                string literal
1560   //                ::= L <nullptr type> E                                 #
1561   //                nullptr literal (i.e., "LDnE")
1562   //                ::= L <type> <real-part float> _ <imag-part float> E   #
1563   //                complex floating point literal (C 2000)
1564   //                ::= L <mangled-name> E                                 #
1565   //                external name
1566
1567   bool ParseExpressionPrimary() {
1568     switch (*m_read_ptr++) {
1569     case 'b':
1570       return ParseBooleanLiteral();
1571     case 'x':
1572       return ParseIntegerLiteral(nullptr, "ll", true);
1573     case 'l':
1574       return ParseIntegerLiteral(nullptr, "l", true);
1575     case 'i':
1576       return ParseIntegerLiteral(nullptr, nullptr, true);
1577     case 'n':
1578       return ParseIntegerLiteral("(__int128)", nullptr, true);
1579     case 'j':
1580       return ParseIntegerLiteral(nullptr, "u", false);
1581     case 'm':
1582       return ParseIntegerLiteral(nullptr, "ul", false);
1583     case 'y':
1584       return ParseIntegerLiteral(nullptr, "ull", false);
1585     case 'o':
1586       return ParseIntegerLiteral("(unsigned __int128)", nullptr, false);
1587     case '_':
1588       if (*m_read_ptr++ == 'Z') {
1589         if (!ParseEncoding())
1590           return false;
1591         return Parse('E');
1592       }
1593       --m_read_ptr;
1594       LLVM_FALLTHROUGH;
1595     case 'w':
1596     case 'c':
1597     case 'a':
1598     case 'h':
1599     case 's':
1600     case 't':
1601     case 'f':
1602     case 'd':
1603     case 'e':
1604 #ifdef DEBUG_FAILURES
1605       printf("*** Unsupported primary expression %.5s\n", m_read_ptr - 1);
1606 #endif
1607       return false;
1608     case 'T':
1609 // Invalid mangled name per
1610 //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
1611 #ifdef DEBUG_FAILURES
1612       printf("*** Invalid primary expr encoding\n");
1613 #endif
1614       return false;
1615     default:
1616       --m_read_ptr;
1617       Write('(');
1618       if (!ParseType())
1619         return false;
1620       Write(')');
1621       if (!ParseNumber())
1622         return false;
1623       return Parse('E');
1624     }
1625   }
1626
1627   // <unresolved-type> ::= <template-param>
1628   //                   ::= <decltype>
1629   //                   ::= <substitution>
1630
1631   bool ParseUnresolvedType() {
1632     int type_start_cookie = GetStartCookie();
1633     switch (*m_read_ptr++) {
1634     case 'T':
1635       if (!ParseTemplateParam())
1636         return false;
1637       EndSubstitution(type_start_cookie);
1638       return true;
1639     case 'S': {
1640       if (*m_read_ptr != 't')
1641         return ParseSubstitution();
1642
1643       ++m_read_ptr;
1644       WriteStdPrefix();
1645       NameState type_name = {};
1646       if (!ParseUnqualifiedName(type_name))
1647         return false;
1648       EndSubstitution(type_start_cookie);
1649       return true;
1650     }
1651     case 'D':
1652     default:
1653 #ifdef DEBUG_FAILURES
1654       printf("*** Unsupported unqualified type: %3s\n", m_read_ptr - 1);
1655 #endif
1656       return false;
1657     }
1658   }
1659
1660   // <base-unresolved-name> ::= <simple-id>                                #
1661   // unresolved name
1662   //          extension     ::= <operator-name>                            #
1663   //          unresolved operator-function-id
1664   //          extension     ::= <operator-name> <template-args>            #
1665   //          unresolved operator template-id
1666   //                        ::= on <operator-name>                         #
1667   //                        unresolved operator-function-id
1668   //                        ::= on <operator-name> <template-args>         #
1669   //                        unresolved operator template-id
1670   //                        ::= dn <destructor-name>                       #
1671   //                        destructor or pseudo-destructor;
1672   //                                                                         #
1673   //                                                                         e.g.
1674   //                                                                         ~X
1675   //                                                                         or
1676   //                                                                         ~X<N-1>
1677
1678   bool ParseBaseUnresolvedName() {
1679 #ifdef DEBUG_FAILURES
1680     printf("*** Base unresolved name unsupported\n");
1681 #endif
1682     return false;
1683   }
1684
1685   // <unresolved-name>
1686   //  extension        ::= srN <unresolved-type> [<template-args>]
1687   //  <unresolved-qualifier-level>* E <base-unresolved-name>
1688   //                   ::= [gs] <base-unresolved-name>                     # x
1689   //                   or (with "gs") ::x
1690   //                   ::= [gs] sr <unresolved-qualifier-level>+ E
1691   //                   <base-unresolved-name>
1692   //                                                                       #
1693   //                                                                       A::x,
1694   //                                                                       N::y,
1695   //                                                                       A<T>::z;
1696   //                                                                       "gs"
1697   //                                                                       means
1698   //                                                                       leading
1699   //                                                                       "::"
1700   //                   ::= sr <unresolved-type> <base-unresolved-name>     #
1701   //                   T::x / decltype(p)::x
1702   //  extension        ::= sr <unresolved-type> <template-args>
1703   //  <base-unresolved-name>
1704   //                                                                       #
1705   //                                                                       T::N::x
1706   //                                                                       /decltype(p)::N::x
1707   //  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+
1708   //  E <base-unresolved-name>
1709
1710   bool ParseUnresolvedName() {
1711 #ifdef DEBUG_FAILURES
1712     printf("*** Unresolved names not supported\n");
1713 #endif
1714     // TODO: grammar for all of this seems unclear...
1715     return false;
1716
1717 #if 0  // TODO
1718         if (*m_read_ptr == 'g' && *(m_read_ptr + 1) == 's')
1719         {
1720             m_read_ptr += 2;
1721             WriteNamespaceSeparator();
1722         }
1723 #endif // TODO
1724   }
1725
1726   // <expression> ::= <unary operator-name> <expression>
1727   //              ::= <binary operator-name> <expression> <expression>
1728   //              ::= <ternary operator-name> <expression> <expression>
1729   //              <expression>
1730   //              ::= cl <expression>+ E                                   #
1731   //              call
1732   //              ::= cv <type> <expression>                               #
1733   //              conversion with one argument
1734   //              ::= cv <type> _ <expression>* E                          #
1735   //              conversion with a different number of arguments
1736   //              ::= [gs] nw <expression>* _ <type> E                     # new
1737   //              (expr-list) type
1738   //              ::= [gs] nw <expression>* _ <type> <initializer>         # new
1739   //              (expr-list) type (init)
1740   //              ::= [gs] na <expression>* _ <type> E                     #
1741   //              new[] (expr-list) type
1742   //              ::= [gs] na <expression>* _ <type> <initializer>         #
1743   //              new[] (expr-list) type (init)
1744   //              ::= [gs] dl <expression>                                 #
1745   //              delete expression
1746   //              ::= [gs] da <expression>                                 #
1747   //              delete[] expression
1748   //              ::= pp_ <expression>                                     #
1749   //              prefix ++
1750   //              ::= mm_ <expression>                                     #
1751   //              prefix --
1752   //              ::= ti <type>                                            #
1753   //              typeid (type)
1754   //              ::= te <expression>                                      #
1755   //              typeid (expression)
1756   //              ::= dc <type> <expression>                               #
1757   //              dynamic_cast<type> (expression)
1758   //              ::= sc <type> <expression>                               #
1759   //              static_cast<type> (expression)
1760   //              ::= cc <type> <expression>                               #
1761   //              const_cast<type> (expression)
1762   //              ::= rc <type> <expression>                               #
1763   //              reinterpret_cast<type> (expression)
1764   //              ::= st <type>                                            #
1765   //              sizeof (a type)
1766   //              ::= sz <expression>                                      #
1767   //              sizeof (an expression)
1768   //              ::= at <type>                                            #
1769   //              alignof (a type)
1770   //              ::= az <expression>                                      #
1771   //              alignof (an expression)
1772   //              ::= nx <expression>                                      #
1773   //              noexcept (expression)
1774   //              ::= <template-param>
1775   //              ::= <function-param>
1776   //              ::= dt <expression> <unresolved-name>                    #
1777   //              expr.name
1778   //              ::= pt <expression> <unresolved-name>                    #
1779   //              expr->name
1780   //              ::= ds <expression> <expression>                         #
1781   //              expr.*expr
1782   //              ::= sZ <template-param>                                  #
1783   //              size of a parameter pack
1784   //              ::= sZ <function-param>                                  #
1785   //              size of a function parameter pack
1786   //              ::= sp <expression>                                      #
1787   //              pack expansion
1788   //              ::= tw <expression>                                      #
1789   //              throw expression
1790   //              ::= tr                                                   #
1791   //              throw with no operand (rethrow)
1792   //              ::= <unresolved-name>                                    #
1793   //              f(p), N::f(p), ::f(p),
1794   //                                                                       #
1795   //                                                                       freestanding
1796   //                                                                       dependent
1797   //                                                                       name
1798   //                                                                       (e.g.,
1799   //                                                                       T::x),
1800   //                                                                       #
1801   //                                                                       objectless
1802   //                                                                       nonstatic
1803   //                                                                       member
1804   //                                                                       reference
1805   //              ::= <expr-primary>
1806
1807   bool ParseExpression() {
1808     Operator expression_operator = TryParseOperator();
1809     switch (expression_operator.kind) {
1810     case OperatorKind::Unary:
1811       Write(expression_operator.name);
1812       Write('(');
1813       if (!ParseExpression())
1814         return false;
1815       Write(')');
1816       return true;
1817     case OperatorKind::Binary:
1818       if (!ParseExpression())
1819         return false;
1820       Write(expression_operator.name);
1821       return ParseExpression();
1822     case OperatorKind::Ternary:
1823       if (!ParseExpression())
1824         return false;
1825       Write('?');
1826       if (!ParseExpression())
1827         return false;
1828       Write(':');
1829       return ParseExpression();
1830     case OperatorKind::NoMatch:
1831       break;
1832     case OperatorKind::Other:
1833     default:
1834 #ifdef DEBUG_FAILURES
1835       printf("*** Unsupported operator: %s\n", expression_operator.name);
1836 #endif
1837       return false;
1838     }
1839
1840     switch (*m_read_ptr++) {
1841     case 'T':
1842       return ParseTemplateParam();
1843     case 'L':
1844       return ParseExpressionPrimary();
1845     case 's':
1846       if (*m_read_ptr++ == 'r')
1847         return ParseUnresolvedName();
1848       --m_read_ptr;
1849       LLVM_FALLTHROUGH;
1850     default:
1851       return ParseExpressionPrimary();
1852     }
1853   }
1854
1855   // <template-arg> ::= <type>                                             #
1856   // type or template
1857   //                ::= X <expression> E                                   #
1858   //                expression
1859   //                ::= <expr-primary>                                     #
1860   //                simple expressions
1861   //                ::= J <template-arg>* E                                #
1862   //                argument pack
1863   //                ::= LZ <encoding> E                                    #
1864   //                extension
1865
1866   bool ParseTemplateArg() {
1867     switch (*m_read_ptr) {
1868     case 'J':
1869 #ifdef DEBUG_FAILURES
1870       printf("*** Template argument packs unsupported\n");
1871 #endif
1872       return false;
1873     case 'X':
1874       ++m_read_ptr;
1875       if (!ParseExpression())
1876         return false;
1877       return Parse('E');
1878     case 'L':
1879       ++m_read_ptr;
1880       return ParseExpressionPrimary();
1881     default:
1882       return ParseType();
1883     }
1884   }
1885
1886   // <template-args> ::= I <template-arg>* E
1887   //     extension, the abi says <template-arg>+
1888
1889   bool ParseTemplateArgs(bool record_template_args = false) {
1890     if (record_template_args)
1891       ResetTemplateArgs();
1892
1893     bool first_arg = true;
1894     while (*m_read_ptr != 'E') {
1895       if (first_arg)
1896         first_arg = false;
1897       else
1898         WriteCommaSpace();
1899
1900       int template_start_cookie = GetStartCookie();
1901       if (!ParseTemplateArg())
1902         return false;
1903       if (record_template_args)
1904         EndTemplateArg(template_start_cookie);
1905     }
1906     ++m_read_ptr;
1907     return true;
1908   }
1909
1910   // <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
1911   // <unqualified-name> E
1912   //               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
1913   //               <template-args> E
1914   //
1915   // <prefix> ::= <prefix> <unqualified-name>
1916   //          ::= <template-prefix> <template-args>
1917   //          ::= <template-param>
1918   //          ::= <decltype>
1919   //          ::= # empty
1920   //          ::= <substitution>
1921   //          ::= <prefix> <data-member-prefix>
1922   //  extension ::= L
1923   //
1924   // <template-prefix> ::= <prefix> <template unqualified-name>
1925   //                   ::= <template-param>
1926   //                   ::= <substitution>
1927   //
1928   // <unqualified-name> ::= <operator-name>
1929   //                    ::= <ctor-dtor-name>
1930   //                    ::= <source-name>
1931   //                    ::= <unnamed-type-name>
1932
1933   bool ParseNestedName(NameState &name_state,
1934                        bool parse_discriminator = false) {
1935     int qualifiers = TryParseQualifiers(true, true);
1936     bool first_part = true;
1937     bool suppress_substitution = true;
1938     int name_start_cookie = GetStartCookie();
1939     while (true) {
1940       char next = *m_read_ptr;
1941       if (next == 'E') {
1942         ++m_read_ptr;
1943         break;
1944       }
1945
1946       // Record a substitution candidate for all prefixes, but not the full name
1947       if (suppress_substitution)
1948         suppress_substitution = false;
1949       else
1950         EndSubstitution(name_start_cookie);
1951
1952       if (next == 'I') {
1953         ++m_read_ptr;
1954         name_state.is_last_generic = true;
1955         WriteTemplateStart();
1956         if (!ParseTemplateArgs(name_state.parse_function_params))
1957           return false;
1958         WriteTemplateEnd();
1959         continue;
1960       }
1961
1962       if (first_part)
1963         first_part = false;
1964       else
1965         WriteNamespaceSeparator();
1966
1967       name_state.is_last_generic = false;
1968       switch (next) {
1969       case '0':
1970       case '1':
1971       case '2':
1972       case '3':
1973       case '4':
1974       case '5':
1975       case '6':
1976       case '7':
1977       case '8':
1978       case '9': {
1979         int name_start_cookie = GetStartCookie();
1980         if (!ParseSourceName())
1981           return false;
1982         name_state.last_name_range = EndRange(name_start_cookie);
1983         continue;
1984       }
1985       case 'S':
1986         if (*++m_read_ptr == 't') {
1987           WriteStdPrefix();
1988           ++m_read_ptr;
1989           if (!ParseUnqualifiedName(name_state))
1990             return false;
1991         } else {
1992           if (!ParseSubstitution())
1993             return false;
1994           suppress_substitution = true;
1995         }
1996         continue;
1997       case 'T':
1998         ++m_read_ptr;
1999         if (!ParseTemplateParam())
2000           return false;
2001         continue;
2002       case 'C':
2003         ++m_read_ptr;
2004         if (!ParseCtor(name_state))
2005           return false;
2006         continue;
2007       case 'D': {
2008         switch (*(m_read_ptr + 1)) {
2009         case 't':
2010         case 'T':
2011 #ifdef DEBUG_FAILURES
2012           printf("*** Decltype unsupported\n");
2013 #endif
2014           return false;
2015         }
2016         ++m_read_ptr;
2017         if (!ParseDtor(name_state))
2018           return false;
2019         continue;
2020       }
2021       case 'U':
2022         ++m_read_ptr;
2023         if (!ParseUnnamedTypeName(name_state))
2024           return false;
2025         continue;
2026       case 'L':
2027         ++m_read_ptr;
2028         if (!ParseUnqualifiedName(name_state))
2029           return false;
2030         continue;
2031       default:
2032         if (!ParseOperatorName(name_state))
2033           return false;
2034       }
2035     }
2036
2037     if (parse_discriminator)
2038       TryParseDiscriminator();
2039     if (name_state.parse_function_params &&
2040         !ParseFunctionArgs(name_state, name_start_cookie)) {
2041       return false;
2042     }
2043     if (qualifiers)
2044       WriteQualifiers(qualifiers);
2045     return true;
2046   }
2047
2048   // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
2049   //              := Z <function encoding> E s [<discriminator>]
2050   //              := Z <function encoding> Ed [ <parameter number> ] _ <entity
2051   //              name>
2052
2053   bool ParseLocalName(bool parse_function_params) {
2054     if (!ParseEncoding())
2055       return false;
2056     if (!Parse('E'))
2057       return false;
2058
2059     switch (*m_read_ptr) {
2060     case 's':
2061       ++m_read_ptr;
2062       TryParseDiscriminator(); // Optional and ignored
2063       WRITE("::string literal");
2064       break;
2065     case 'd':
2066       ++m_read_ptr;
2067       TryParseNumber(); // Optional and ignored
2068       if (!Parse('_'))
2069         return false;
2070       WriteNamespaceSeparator();
2071       if (!ParseName())
2072         return false;
2073       break;
2074     default:
2075       WriteNamespaceSeparator();
2076       if (!ParseName(parse_function_params, true))
2077         return false;
2078       TryParseDiscriminator(); // Optional and ignored
2079     }
2080     return true;
2081   }
2082
2083   // <name> ::= <nested-name>
2084   //        ::= <local-name>
2085   //        ::= <unscoped-template-name> <template-args>
2086   //        ::= <unscoped-name>
2087
2088   // <unscoped-template-name> ::= <unscoped-name>
2089   //                          ::= <substitution>
2090
2091   bool ParseName(bool parse_function_params = false,
2092                  bool parse_discriminator = false) {
2093     NameState name_state = {parse_function_params, false, false, {0, 0}};
2094     int name_start_cookie = GetStartCookie();
2095
2096     switch (*m_read_ptr) {
2097     case 'N':
2098       ++m_read_ptr;
2099       return ParseNestedName(name_state, parse_discriminator);
2100     case 'Z': {
2101       ++m_read_ptr;
2102       if (!ParseLocalName(parse_function_params))
2103         return false;
2104       break;
2105     }
2106     case 'L':
2107       ++m_read_ptr;
2108       LLVM_FALLTHROUGH;
2109     default: {
2110       if (!ParseUnscopedName(name_state))
2111         return false;
2112
2113       if (*m_read_ptr == 'I') {
2114         EndSubstitution(name_start_cookie);
2115
2116         ++m_read_ptr;
2117         name_state.is_last_generic = true;
2118         WriteTemplateStart();
2119         if (!ParseTemplateArgs(parse_function_params))
2120           return false;
2121         WriteTemplateEnd();
2122       }
2123       break;
2124     }
2125     }
2126     if (parse_discriminator)
2127       TryParseDiscriminator();
2128     if (parse_function_params &&
2129         !ParseFunctionArgs(name_state, name_start_cookie)) {
2130       return false;
2131     }
2132     return true;
2133   }
2134
2135   // <call-offset> ::= h <nv-offset> _
2136   //               ::= v <v-offset> _
2137   //
2138   // <nv-offset> ::= <offset number>
2139   //                 # non-virtual base override
2140   //
2141   // <v-offset>  ::= <offset number> _ <virtual offset number>
2142   //                 # virtual base override, with vcall offset
2143
2144   bool ParseCallOffset() {
2145     switch (*m_read_ptr++) {
2146     case 'h':
2147       if (*m_read_ptr == 'n')
2148         ++m_read_ptr;
2149       if (TryParseNumber() == -1 || *m_read_ptr++ != '_')
2150         break;
2151       return true;
2152     case 'v':
2153       if (*m_read_ptr == 'n')
2154         ++m_read_ptr;
2155       if (TryParseNumber() == -1 || *m_read_ptr++ != '_')
2156         break;
2157       if (*m_read_ptr == 'n')
2158         ++m_read_ptr;
2159       if (TryParseNumber() == -1 || *m_read_ptr++ != '_')
2160         break;
2161       return true;
2162     }
2163 #ifdef DEBUG_FAILURES
2164     printf("*** Malformed call offset\n");
2165 #endif
2166     return false;
2167   }
2168
2169   // <special-name> ::= TV <type>    # virtual table
2170   //                ::= TT <type>    # VTT structure (construction vtable index)
2171   //                ::= TI <type>    # typeinfo structure
2172   //                ::= TS <type>    # typeinfo name (null-terminated byte
2173   //                string)
2174   //                ::= Tc <call-offset> <call-offset> <base encoding>
2175   //                    # base is the nominal target function of thunk
2176   //                    # first call-offset is 'this' adjustment
2177   //                    # second call-offset is result adjustment
2178   //                ::= T <call-offset> <base encoding>
2179   //                    # base is the nominal target function of thunk
2180   //      extension ::= TC <first type> <number> _ <second type> # construction
2181   //      vtable for second-in-first
2182
2183   bool ParseSpecialNameT() {
2184     switch (*m_read_ptr++) {
2185     case 'V':
2186       WRITE("vtable for ");
2187       return ParseType();
2188     case 'T':
2189       WRITE("VTT for ");
2190       return ParseType();
2191     case 'I':
2192       WRITE("typeinfo for ");
2193       return ParseType();
2194     case 'S':
2195       WRITE("typeinfo name for ");
2196       return ParseType();
2197     case 'c':
2198     case 'C':
2199 #ifdef DEBUG_FAILURES
2200       printf("*** Unsupported thunk or construction vtable name: %.3s\n",
2201              m_read_ptr - 1);
2202 #endif
2203       return false;
2204     default:
2205       if (*--m_read_ptr == 'v') {
2206         WRITE("virtual thunk to ");
2207       } else {
2208         WRITE("non-virtual thunk to ");
2209       }
2210       if (!ParseCallOffset())
2211         return false;
2212       return ParseEncoding();
2213     }
2214   }
2215
2216   // <special-name> ::= GV <object name> # Guard variable for one-time
2217   // initialization
2218   //                                     # No <type>
2219   //      extension ::= GR <object name> # reference temporary for object
2220
2221   bool ParseSpecialNameG() {
2222     switch (*m_read_ptr++) {
2223     case 'V':
2224       WRITE("guard variable for ");
2225       if (!ParseName(true))
2226         return false;
2227       break;
2228     case 'R':
2229       WRITE("reference temporary for ");
2230       if (!ParseName(true))
2231         return false;
2232       break;
2233     default:
2234 #ifdef DEBUG_FAILURES
2235       printf("*** Unknown G encoding\n");
2236 #endif
2237       return false;
2238     }
2239     return true;
2240   }
2241
2242   // <bare-function-type> ::= <signature type>+        # types are possible
2243   // return type, then parameter types
2244
2245   bool ParseFunctionArgs(NameState &name_state, int return_insert_cookie) {
2246     char next = *m_read_ptr;
2247     if (next == 'E' || next == '\0' || next == '.')
2248       return true;
2249
2250     // Clang has a bad habit of making unique manglings by just sticking numbers
2251     // on the end of a symbol,
2252     // which is ambiguous with malformed source name manglings
2253     const char *before_clang_uniquing_test = m_read_ptr;
2254     if (TryParseNumber()) {
2255       if (*m_read_ptr == '\0')
2256         return true;
2257       m_read_ptr = before_clang_uniquing_test;
2258     }
2259
2260     if (name_state.is_last_generic && !name_state.has_no_return_type) {
2261       int return_type_start_cookie = GetStartCookie();
2262       if (!ParseType())
2263         return false;
2264       Write(' ');
2265       ReorderRange(EndRange(return_type_start_cookie), return_insert_cookie);
2266     }
2267
2268     Write('(');
2269     bool first_param = true;
2270     while (true) {
2271       switch (*m_read_ptr) {
2272       case '\0':
2273       case 'E':
2274       case '.':
2275         break;
2276       case 'v':
2277         ++m_read_ptr;
2278         continue;
2279       case '_':
2280         // Not a formal part of the mangling specification, but clang emits
2281         // suffixes starting with _block_invoke
2282         if (strncmp(m_read_ptr, "_block_invoke", 13) == 0) {
2283           m_read_ptr += strlen(m_read_ptr);
2284           break;
2285         }
2286         LLVM_FALLTHROUGH;
2287       default:
2288         if (first_param)
2289           first_param = false;
2290         else
2291           WriteCommaSpace();
2292
2293         if (!ParseType())
2294           return false;
2295         continue;
2296       }
2297       break;
2298     }
2299     Write(')');
2300     return true;
2301   }
2302
2303   // <encoding> ::= <function name> <bare-function-type>
2304   //            ::= <data name>
2305   //            ::= <special-name>
2306
2307   bool ParseEncoding() {
2308     switch (*m_read_ptr) {
2309     case 'T':
2310       ++m_read_ptr;
2311       if (!ParseSpecialNameT())
2312         return false;
2313       break;
2314     case 'G':
2315       ++m_read_ptr;
2316       if (!ParseSpecialNameG())
2317         return false;
2318       break;
2319     default:
2320       if (!ParseName(true))
2321         return false;
2322       break;
2323     }
2324     return true;
2325   }
2326
2327   bool ParseMangling(const char *mangled_name, long mangled_name_length = 0) {
2328     if (!mangled_name_length)
2329       mangled_name_length = strlen(mangled_name);
2330     m_read_end = mangled_name + mangled_name_length;
2331     m_read_ptr = mangled_name;
2332     m_write_ptr = m_buffer;
2333     m_next_substitute_index = 0;
2334     m_next_template_arg_index = m_rewrite_ranges_size - 1;
2335
2336     if (*m_read_ptr++ != '_' || *m_read_ptr++ != 'Z') {
2337 #ifdef DEBUG_FAILURES
2338       printf("*** Missing _Z prefix\n");
2339 #endif
2340       return false;
2341     }
2342     if (!ParseEncoding())
2343       return false;
2344     switch (*m_read_ptr) {
2345     case '.':
2346       Write(' ');
2347       Write('(');
2348       Write(m_read_ptr, m_read_end - m_read_ptr);
2349       Write(')');
2350       LLVM_FALLTHROUGH;
2351     case '\0':
2352       return true;
2353     default:
2354 #ifdef DEBUG_FAILURES
2355       printf("*** Unparsed mangled content\n");
2356 #endif
2357       return false;
2358     }
2359   }
2360
2361 private:
2362   // External scratch storage used during demanglings
2363
2364   char *m_buffer;
2365   const char *m_buffer_end;
2366   BufferRange *m_rewrite_ranges;
2367   int m_rewrite_ranges_size;
2368   bool m_owns_buffer;
2369   bool m_owns_m_rewrite_ranges;
2370
2371   // Internal state used during demangling
2372
2373   const char *m_read_ptr;
2374   const char *m_read_end;
2375   char *m_write_ptr;
2376   int m_next_template_arg_index;
2377   int m_next_substitute_index;
2378   std::function<void(const char *s)> m_builtins_hook;
2379 };
2380
2381 } // Anonymous namespace
2382
2383 // Public entry points referenced from Mangled.cpp
2384 namespace lldb_private {
2385 char *FastDemangle(const char *mangled_name) {
2386   char buffer[16384];
2387   SymbolDemangler demangler(buffer, sizeof(buffer));
2388   return demangler.GetDemangledCopy(mangled_name);
2389 }
2390
2391 char *FastDemangle(const char *mangled_name, size_t mangled_name_length,
2392                    std::function<void(const char *s)> builtins_hook) {
2393   char buffer[16384];
2394   SymbolDemangler demangler(buffer, sizeof(buffer), builtins_hook);
2395   return demangler.GetDemangledCopy(mangled_name, mangled_name_length);
2396 }
2397 } // lldb_private namespace