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