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