diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2018-07-28 10:51:19 +0000 | 
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2018-07-28 10:51:19 +0000 | 
| commit | eb11fae6d08f479c0799db45860a98af528fa6e7 (patch) | |
| tree | 44d492a50c8c1a7eb8e2d17ea3360ec4d066f042 /lib/Demangle/ItaniumDemangle.cpp | |
| parent | b8a2042aa938069e862750553db0e4d82d25822c (diff) | |
Notes
Diffstat (limited to 'lib/Demangle/ItaniumDemangle.cpp')
| -rw-r--r-- | lib/Demangle/ItaniumDemangle.cpp | 8767 | 
1 files changed, 4827 insertions, 3940 deletions
| diff --git a/lib/Demangle/ItaniumDemangle.cpp b/lib/Demangle/ItaniumDemangle.cpp index 9c2258f5b933..5bfd2e6ff87e 100644 --- a/lib/Demangle/ItaniumDemangle.cpp +++ b/lib/Demangle/ItaniumDemangle.cpp @@ -1,4 +1,4 @@ -//===- ItaniumDemangle.cpp ------------------------------------------------===// +//===------------------------- ItaniumDemangle.cpp ------------------------===//  //  //                     The LLVM Compiler Infrastructure  // @@ -7,1975 +7,2280 @@  //  //===----------------------------------------------------------------------===// -#include "llvm/Demangle/Demangle.h" -#include "llvm/Support/Compiler.h" +// FIXME: (possibly) incomplete list of features that clang mangles that this +// file does not yet support: +//   - C++ modules TS -// This file exports a single function: llvm::itanium_demangle. -// It also has no dependencies on the rest of llvm. It is implemented this way -// so that it can be easily reused in libcxxabi. +#include "Compiler.h" +#include "StringView.h" +#include "Utility.h" +#include "llvm/Demangle/Demangle.h" -#include <algorithm> +#include <cassert>  #include <cctype> +#include <cstdio>  #include <cstdlib>  #include <cstring>  #include <numeric> -#include <string> +#include <utility>  #include <vector> -#ifdef _MSC_VER -// snprintf is implemented in VS 2015 -#if _MSC_VER < 1900 -#define snprintf _snprintf_s -#endif +namespace { +// Base class of all AST nodes. The AST is built by the parser, then is +// traversed by the printLeft/Right functions to produce a demangled string. +class Node { +public: +  enum Kind : unsigned char { +    KNodeArrayNode, +    KDotSuffix, +    KVendorExtQualType, +    KQualType, +    KConversionOperatorType, +    KPostfixQualifiedType, +    KElaboratedTypeSpefType, +    KNameType, +    KAbiTagAttr, +    KEnableIfAttr, +    KObjCProtoName, +    KPointerType, +    KReferenceType, +    KPointerToMemberType, +    KArrayType, +    KFunctionType, +    KNoexceptSpec, +    KDynamicExceptionSpec, +    KFunctionEncoding, +    KLiteralOperator, +    KSpecialName, +    KCtorVtableSpecialName, +    KQualifiedName, +    KNestedName, +    KLocalName, +    KVectorType, +    KParameterPack, +    KTemplateArgumentPack, +    KParameterPackExpansion, +    KTemplateArgs, +    KForwardTemplateReference, +    KNameWithTemplateArgs, +    KGlobalQualifiedName, +    KStdQualifiedName, +    KExpandedSpecialSubstitution, +    KSpecialSubstitution, +    KCtorDtorName, +    KDtorName, +    KUnnamedTypeName, +    KClosureTypeName, +    KStructuredBindingName, +    KExpr, +    KBracedExpr, +    KBracedRangeExpr, +  }; + +  Kind K; + +  /// Three-way bool to track a cached value. Unknown is possible if this node +  /// has an unexpanded parameter pack below it that may affect this cache. +  enum class Cache : unsigned char { Yes, No, Unknown, }; + +  /// Tracks if this node has a component on its right side, in which case we +  /// need to call printRight. +  Cache RHSComponentCache; + +  /// Track if this node is a (possibly qualified) array type. This can affect +  /// how we format the output string. +  Cache ArrayCache; + +  /// Track if this node is a (possibly qualified) function type. This can +  /// affect how we format the output string. +  Cache FunctionCache; + +  Node(Kind K_, Cache RHSComponentCache_ = Cache::No, +       Cache ArrayCache_ = Cache::No, Cache FunctionCache_ = Cache::No) +      : K(K_), RHSComponentCache(RHSComponentCache_), ArrayCache(ArrayCache_), +        FunctionCache(FunctionCache_) {} + +  bool hasRHSComponent(OutputStream &S) const { +    if (RHSComponentCache != Cache::Unknown) +      return RHSComponentCache == Cache::Yes; +    return hasRHSComponentSlow(S); +  } + +  bool hasArray(OutputStream &S) const { +    if (ArrayCache != Cache::Unknown) +      return ArrayCache == Cache::Yes; +    return hasArraySlow(S); +  } + +  bool hasFunction(OutputStream &S) const { +    if (FunctionCache != Cache::Unknown) +      return FunctionCache == Cache::Yes; +    return hasFunctionSlow(S); +  } + +  Kind getKind() const { return K; } + +  virtual bool hasRHSComponentSlow(OutputStream &) const { return false; } +  virtual bool hasArraySlow(OutputStream &) const { return false; } +  virtual bool hasFunctionSlow(OutputStream &) const { return false; } + +  // Dig through "glue" nodes like ParameterPack and ForwardTemplateReference to +  // get at a node that actually represents some concrete syntax. +  virtual const Node *getSyntaxNode(OutputStream &) const { +    return this; +  } + +  void print(OutputStream &S) const { +    printLeft(S); +    if (RHSComponentCache != Cache::No) +      printRight(S); +  } + +  // Print the "left" side of this Node into OutputStream. +  virtual void printLeft(OutputStream &) const = 0; + +  // Print the "right". This distinction is necessary to represent C++ types +  // that appear on the RHS of their subtype, such as arrays or functions. +  // Since most types don't have such a component, provide a default +  // implementation. +  virtual void printRight(OutputStream &) const {} + +  virtual StringView getBaseName() const { return StringView(); } + +  // Silence compiler warnings, this dtor will never be called. +  virtual ~Node() = default; + +#ifndef NDEBUG +  LLVM_DUMP_METHOD void dump() const { +    char *Buffer = static_cast<char*>(std::malloc(1024)); +    OutputStream S(Buffer, 1024); +    print(S); +    S += '\0'; +    printf("Symbol dump for %p: %s\n", (const void*)this, S.getBuffer()); +    std::free(S.getBuffer()); +  }  #endif +}; + +class NodeArray { +  Node **Elements; +  size_t NumElements; + +public: +  NodeArray() : Elements(nullptr), NumElements(0) {} +  NodeArray(Node **Elements_, size_t NumElements_) +      : Elements(Elements_), NumElements(NumElements_) {} + +  bool empty() const { return NumElements == 0; } +  size_t size() const { return NumElements; } + +  Node **begin() const { return Elements; } +  Node **end() const { return Elements + NumElements; } + +  Node *operator[](size_t Idx) const { return Elements[Idx]; } + +  void printWithComma(OutputStream &S) const { +    bool FirstElement = true; +    for (size_t Idx = 0; Idx != NumElements; ++Idx) { +      size_t BeforeComma = S.getCurrentPosition(); +      if (!FirstElement) +        S += ", "; +      size_t AfterComma = S.getCurrentPosition(); +      Elements[Idx]->print(S); + +      // Elements[Idx] is an empty parameter pack expansion, we should erase the +      // comma we just printed. +      if (AfterComma == S.getCurrentPosition()) { +        S.setCurrentPosition(BeforeComma); +        continue; +      } -enum { -  unknown_error = -4, -  invalid_args = -3, -  invalid_mangled_name, -  memory_alloc_failure, -  success +      FirstElement = false; +    } +  }  }; -enum { -  CV_const = (1 << 0), -  CV_volatile = (1 << 1), -  CV_restrict = (1 << 2), +struct NodeArrayNode : Node { +  NodeArray Array; +  NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {} +  void printLeft(OutputStream &S) const override { +    Array.printWithComma(S); +  }  }; -template <class C> -static const char *parse_type(const char *first, const char *last, C &db); -template <class C> -static const char *parse_encoding(const char *first, const char *last, C &db); -template <class C> -static const char *parse_name(const char *first, const char *last, C &db, -                              bool *ends_with_template_args = 0); -template <class C> -static const char *parse_expression(const char *first, const char *last, C &db); -template <class C> -static const char *parse_template_args(const char *first, const char *last, -                                       C &db); -template <class C> -static const char *parse_operator_name(const char *first, const char *last, -                                       C &db); -template <class C> -static const char *parse_unqualified_name(const char *first, const char *last, -                                          C &db); -template <class C> -static const char *parse_decltype(const char *first, const char *last, C &db); +class DotSuffix final : public Node { +  const Node *Prefix; +  const StringView Suffix; -// <number> ::= [n] <non-negative decimal integer> +public: +  DotSuffix(Node *Prefix_, StringView Suffix_) +      : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {} + +  void printLeft(OutputStream &s) const override { +    Prefix->print(s); +    s += " ("; +    s += Suffix; +    s += ")"; +  } +}; -static const char *parse_number(const char *first, const char *last) { -  if (first != last) { -    const char *t = first; -    if (*t == 'n') -      ++t; -    if (t != last) { -      if (*t == '0') { -        first = t + 1; -      } else if ('1' <= *t && *t <= '9') { -        first = t + 1; -        while (first != last && std::isdigit(*first)) -          ++first; -      } -    } +class VendorExtQualType final : public Node { +  const Node *Ty; +  StringView Ext; + +public: +  VendorExtQualType(Node *Ty_, StringView Ext_) +      : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_) {} + +  void printLeft(OutputStream &S) const override { +    Ty->print(S); +    S += " "; +    S += Ext;    } -  return first; +}; + +enum FunctionRefQual : unsigned char { +  FrefQualNone, +  FrefQualLValue, +  FrefQualRValue, +}; + +enum Qualifiers { +  QualNone = 0, +  QualConst = 0x1, +  QualVolatile = 0x2, +  QualRestrict = 0x4, +}; + +void addQualifiers(Qualifiers &Q1, Qualifiers Q2) { +  Q1 = static_cast<Qualifiers>(Q1 | Q2);  } -namespace { -template <class Float> struct float_data; +class QualType : public Node { +protected: +  const Qualifiers Quals; +  const Node *Child; + +  void printQuals(OutputStream &S) const { +    if (Quals & QualConst) +      S += " const"; +    if (Quals & QualVolatile) +      S += " volatile"; +    if (Quals & QualRestrict) +      S += " restrict"; +  } + +public: +  QualType(Node *Child_, Qualifiers Quals_) +      : Node(KQualType, Child_->RHSComponentCache, +             Child_->ArrayCache, Child_->FunctionCache), +        Quals(Quals_), Child(Child_) {} + +  bool hasRHSComponentSlow(OutputStream &S) const override { +    return Child->hasRHSComponent(S); +  } +  bool hasArraySlow(OutputStream &S) const override { +    return Child->hasArray(S); +  } +  bool hasFunctionSlow(OutputStream &S) const override { +    return Child->hasFunction(S); +  } + +  void printLeft(OutputStream &S) const override { +    Child->printLeft(S); +    printQuals(S); +  } -template <> struct float_data<float> { -  static const size_t mangled_size = 8; -  static const size_t max_demangled_size = 24; -  static const char *spec; +  void printRight(OutputStream &S) const override { Child->printRight(S); }  }; -const char *float_data<float>::spec = "%af"; -template <> struct float_data<double> { -  static const size_t mangled_size = 16; -  static const size_t max_demangled_size = 32; -  static const char *spec; +class ConversionOperatorType final : public Node { +  const Node *Ty; + +public: +  ConversionOperatorType(Node *Ty_) +      : Node(KConversionOperatorType), Ty(Ty_) {} + +  void printLeft(OutputStream &S) const override { +    S += "operator "; +    Ty->print(S); +  }  }; -const char *float_data<double>::spec = "%a"; +class PostfixQualifiedType final : public Node { +  const Node *Ty; +  const StringView Postfix; -template <> struct float_data<long double> { -#if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) ||        \ -    defined(__wasm__) -  static const size_t mangled_size = 32; -#elif defined(__arm__) || defined(__mips__) || defined(__hexagon__) -  static const size_t mangled_size = 16; -#else -  static const size_t mangled_size = -      20; // May need to be adjusted to 16 or 24 on other platforms -#endif -  static const size_t max_demangled_size = 40; -  static const char *spec; +public: +  PostfixQualifiedType(Node *Ty_, StringView Postfix_) +      : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {} + +  void printLeft(OutputStream &s) const override { +    Ty->printLeft(s); +    s += Postfix; +  }  }; -const char *float_data<long double>::spec = "%LaL"; -} +class NameType final : public Node { +  const StringView Name; -template <class Float, class C> -static const char *parse_floating_number(const char *first, const char *last, -                                         C &db) { -  const size_t N = float_data<Float>::mangled_size; -  if (static_cast<std::size_t>(last - first) > N) { -    last = first + N; -    union { -      Float value; -      char buf[sizeof(Float)]; -    }; -    const char *t = first; -    char *e = buf; -    for (; t != last; ++t, ++e) { -      if (!isxdigit(*t)) -        return first; -      unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0') -                                : static_cast<unsigned>(*t - 'a' + 10); -      ++t; -      unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0') -                                : static_cast<unsigned>(*t - 'a' + 10); -      *e = static_cast<char>((d1 << 4) + d0); -    } -    if (*t == 'E') { -#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ -      std::reverse(buf, e); -#endif -      char num[float_data<Float>::max_demangled_size] = {0}; -      int n = snprintf(num, sizeof(num), float_data<Float>::spec, value); -      if (static_cast<std::size_t>(n) >= sizeof(num)) -        return first; -      db.names.push_back(std::string(num, static_cast<std::size_t>(n))); -      first = t + 1; +public: +  NameType(StringView Name_) : Node(KNameType), Name(Name_) {} + +  StringView getName() const { return Name; } +  StringView getBaseName() const override { return Name; } + +  void printLeft(OutputStream &s) const override { s += Name; } +}; + +class ElaboratedTypeSpefType : public Node { +  StringView Kind; +  Node *Child; +public: +  ElaboratedTypeSpefType(StringView Kind_, Node *Child_) +      : Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {} + +  void printLeft(OutputStream &S) const override { +    S += Kind; +    S += ' '; +    Child->print(S); +  } +}; + +struct AbiTagAttr : Node { +  Node *Base; +  StringView Tag; + +  AbiTagAttr(Node* Base_, StringView Tag_) +      : Node(KAbiTagAttr, Base_->RHSComponentCache, +             Base_->ArrayCache, Base_->FunctionCache), +        Base(Base_), Tag(Tag_) {} + +  void printLeft(OutputStream &S) const override { +    Base->printLeft(S); +    S += "[abi:"; +    S += Tag; +    S += "]"; +  } +}; + +class EnableIfAttr : public Node { +  NodeArray Conditions; +public: +  EnableIfAttr(NodeArray Conditions_) +      : Node(KEnableIfAttr), Conditions(Conditions_) {} + +  void printLeft(OutputStream &S) const override { +    S += " [enable_if:"; +    Conditions.printWithComma(S); +    S += ']'; +  } +}; + +class ObjCProtoName : public Node { +  Node *Ty; +  StringView Protocol; + +  friend class PointerType; + +public: +  ObjCProtoName(Node *Ty_, StringView Protocol_) +      : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {} + +  bool isObjCObject() const { +    return Ty->getKind() == KNameType && +           static_cast<NameType *>(Ty)->getName() == "objc_object"; +  } + +  void printLeft(OutputStream &S) const override { +    Ty->print(S); +    S += "<"; +    S += Protocol; +    S += ">"; +  } +}; + +class PointerType final : public Node { +  const Node *Pointee; + +public: +  PointerType(Node *Pointee_) +      : Node(KPointerType, Pointee_->RHSComponentCache), +        Pointee(Pointee_) {} + +  bool hasRHSComponentSlow(OutputStream &S) const override { +    return Pointee->hasRHSComponent(S); +  } + +  void printLeft(OutputStream &s) const override { +    // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>. +    if (Pointee->getKind() != KObjCProtoName || +        !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) { +      Pointee->printLeft(s); +      if (Pointee->hasArray(s)) +        s += " "; +      if (Pointee->hasArray(s) || Pointee->hasFunction(s)) +        s += "("; +      s += "*"; +    } else { +      const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee); +      s += "id<"; +      s += objcProto->Protocol; +      s += ">";      }    } -  return first; -} -// <source-name> ::= <positive length number> <identifier> +  void printRight(OutputStream &s) const override { +    if (Pointee->getKind() != KObjCProtoName || +        !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) { +      if (Pointee->hasArray(s) || Pointee->hasFunction(s)) +        s += ")"; +      Pointee->printRight(s); +    } +  } +}; -template <class C> -static const char *parse_source_name(const char *first, const char *last, -                                     C &db) { -  if (first != last) { -    char c = *first; -    if (isdigit(c) && first + 1 != last) { -      const char *t = first + 1; -      size_t n = static_cast<size_t>(c - '0'); -      for (c = *t; isdigit(c); c = *t) { -        n = n * 10 + static_cast<size_t>(c - '0'); -        if (++t == last) -          return first; -      } -      if (static_cast<size_t>(last - t) >= n) { -        std::string r(t, n); -        if (r.substr(0, 10) == "_GLOBAL__N") -          db.names.push_back("(anonymous namespace)"); -        else -          db.names.push_back(std::move(r)); -        first = t + n; -      } +enum class ReferenceKind { +  LValue, +  RValue, +}; + +// Represents either a LValue or an RValue reference type. +class ReferenceType : public Node { +  const Node *Pointee; +  ReferenceKind RK; + +  // Dig through any refs to refs, collapsing the ReferenceTypes as we go. The +  // rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any +  // other combination collapses to a lvalue ref. +  std::pair<ReferenceKind, const Node *> collapse(OutputStream &S) const { +    auto SoFar = std::make_pair(RK, Pointee); +    for (;;) { +      const Node *SN = SoFar.second->getSyntaxNode(S); +      if (SN->getKind() != KReferenceType) +        break; +      auto *RT = static_cast<const ReferenceType *>(SN); +      SoFar.second = RT->Pointee; +      SoFar.first = std::min(SoFar.first, RT->RK);      } +    return SoFar;    } -  return first; -} -// <substitution> ::= S <seq-id> _ -//                ::= S_ -// <substitution> ::= Sa # ::std::allocator -// <substitution> ::= Sb # ::std::basic_string -// <substitution> ::= Ss # ::std::basic_string < char, -//                                               ::std::char_traits<char>, -//                                               ::std::allocator<char> > -// <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> > -// <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> > -// <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> > +public: +  ReferenceType(Node *Pointee_, ReferenceKind RK_) +      : Node(KReferenceType, Pointee_->RHSComponentCache), +        Pointee(Pointee_), RK(RK_) {} -template <class C> -static const char *parse_substitution(const char *first, const char *last, -                                      C &db) { -  if (last - first >= 2) { -    if (*first == 'S') { -      switch (first[1]) { -      case 'a': -        db.names.push_back("std::allocator"); -        first += 2; -        break; -      case 'b': -        db.names.push_back("std::basic_string"); -        first += 2; -        break; -      case 's': -        db.names.push_back("std::string"); -        first += 2; -        break; -      case 'i': -        db.names.push_back("std::istream"); -        first += 2; -        break; -      case 'o': -        db.names.push_back("std::ostream"); -        first += 2; -        break; -      case 'd': -        db.names.push_back("std::iostream"); -        first += 2; -        break; -      case '_': -        if (!db.subs.empty()) { -          for (const auto &n : db.subs.front()) -            db.names.push_back(n); -          first += 2; -        } -        break; -      default: -        if (std::isdigit(first[1]) || std::isupper(first[1])) { -          size_t sub = 0; -          const char *t = first + 1; -          if (std::isdigit(*t)) -            sub = static_cast<size_t>(*t - '0'); -          else -            sub = static_cast<size_t>(*t - 'A') + 10; -          for (++t; t != last && (std::isdigit(*t) || std::isupper(*t)); ++t) { -            sub *= 36; -            if (std::isdigit(*t)) -              sub += static_cast<size_t>(*t - '0'); -            else -              sub += static_cast<size_t>(*t - 'A') + 10; -          } -          if (t == last || *t != '_') -            return first; -          ++sub; -          if (sub < db.subs.size()) { -            for (const auto &n : db.subs[sub]) -              db.names.push_back(n); -            first = t + 1; -          } -        } -        break; -      } +  bool hasRHSComponentSlow(OutputStream &S) const override { +    return Pointee->hasRHSComponent(S); +  } + +  void printLeft(OutputStream &s) const override { +    std::pair<ReferenceKind, const Node *> Collapsed = collapse(s); +    Collapsed.second->printLeft(s); +    if (Collapsed.second->hasArray(s)) +      s += " "; +    if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) +      s += "("; + +    s += (Collapsed.first == ReferenceKind::LValue ? "&" : "&&"); +  } +  void printRight(OutputStream &s) const override { +    std::pair<ReferenceKind, const Node *> Collapsed = collapse(s); +    if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) +      s += ")"; +    Collapsed.second->printRight(s); +  } +}; + +class PointerToMemberType final : public Node { +  const Node *ClassType; +  const Node *MemberType; + +public: +  PointerToMemberType(Node *ClassType_, Node *MemberType_) +      : Node(KPointerToMemberType, MemberType_->RHSComponentCache), +        ClassType(ClassType_), MemberType(MemberType_) {} + +  bool hasRHSComponentSlow(OutputStream &S) const override { +    return MemberType->hasRHSComponent(S); +  } + +  void printLeft(OutputStream &s) const override { +    MemberType->printLeft(s); +    if (MemberType->hasArray(s) || MemberType->hasFunction(s)) +      s += "("; +    else +      s += " "; +    ClassType->print(s); +    s += "::*"; +  } + +  void printRight(OutputStream &s) const override { +    if (MemberType->hasArray(s) || MemberType->hasFunction(s)) +      s += ")"; +    MemberType->printRight(s); +  } +}; + +class NodeOrString { +  const void *First; +  const void *Second; + +public: +  /* implicit */ NodeOrString(StringView Str) { +    const char *FirstChar = Str.begin(); +    const char *SecondChar = Str.end(); +    if (SecondChar == nullptr) { +      assert(FirstChar == SecondChar); +      ++FirstChar, ++SecondChar;      } +    First = static_cast<const void *>(FirstChar); +    Second = static_cast<const void *>(SecondChar);    } -  return first; -} -// <builtin-type> ::= v    # void -//                ::= w    # wchar_t -//                ::= b    # bool -//                ::= c    # char -//                ::= a    # signed char -//                ::= h    # unsigned char -//                ::= s    # short -//                ::= t    # unsigned short -//                ::= i    # int -//                ::= j    # unsigned int -//                ::= l    # long -//                ::= m    # unsigned long -//                ::= x    # long long, __int64 -//                ::= y    # unsigned long long, __int64 -//                ::= n    # __int128 -//                ::= o    # unsigned __int128 -//                ::= f    # float -//                ::= d    # double -//                ::= e    # long double, __float80 -//                ::= g    # __float128 -//                ::= z    # ellipsis -//                ::= Dd   # IEEE 754r decimal floating point (64 bits) -//                ::= De   # IEEE 754r decimal floating point (128 bits) -//                ::= Df   # IEEE 754r decimal floating point (32 bits) -//                ::= Dh   # IEEE 754r half-precision floating point (16 bits) -//                ::= Di   # char32_t -//                ::= Ds   # char16_t -//                ::= Da   # auto (in dependent new-expressions) -//                ::= Dc   # decltype(auto) -//                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr)) -//                ::= u <source-name>    # vendor extended type - -template <class C> -static const char *parse_builtin_type(const char *first, const char *last, -                                      C &db) { -  if (first != last) { -    switch (*first) { -    case 'v': -      db.names.push_back("void"); -      ++first; -      break; -    case 'w': -      db.names.push_back("wchar_t"); -      ++first; -      break; -    case 'b': -      db.names.push_back("bool"); -      ++first; -      break; -    case 'c': -      db.names.push_back("char"); -      ++first; -      break; -    case 'a': -      db.names.push_back("signed char"); -      ++first; -      break; -    case 'h': -      db.names.push_back("unsigned char"); -      ++first; -      break; -    case 's': -      db.names.push_back("short"); -      ++first; -      break; -    case 't': -      db.names.push_back("unsigned short"); -      ++first; -      break; -    case 'i': -      db.names.push_back("int"); -      ++first; -      break; -    case 'j': -      db.names.push_back("unsigned int"); -      ++first; -      break; -    case 'l': -      db.names.push_back("long"); -      ++first; -      break; -    case 'm': -      db.names.push_back("unsigned long"); -      ++first; +  /* implicit */ NodeOrString(Node *N) +      : First(static_cast<const void *>(N)), Second(nullptr) {} +  NodeOrString() : First(nullptr), Second(nullptr) {} + +  bool isString() const { return Second && First; } +  bool isNode() const { return First && !Second; } +  bool isEmpty() const { return !First && !Second; } + +  StringView asString() const { +    assert(isString()); +    return StringView(static_cast<const char *>(First), +                      static_cast<const char *>(Second)); +  } + +  const Node *asNode() const { +    assert(isNode()); +    return static_cast<const Node *>(First); +  } +}; + +class ArrayType final : public Node { +  Node *Base; +  NodeOrString Dimension; + +public: +  ArrayType(Node *Base_, NodeOrString Dimension_) +      : Node(KArrayType, +             /*RHSComponentCache=*/Cache::Yes, +             /*ArrayCache=*/Cache::Yes), +        Base(Base_), Dimension(Dimension_) {} + +  // Incomplete array type. +  ArrayType(Node *Base_) +      : Node(KArrayType, +             /*RHSComponentCache=*/Cache::Yes, +             /*ArrayCache=*/Cache::Yes), +        Base(Base_) {} + +  bool hasRHSComponentSlow(OutputStream &) const override { return true; } +  bool hasArraySlow(OutputStream &) const override { return true; } + +  void printLeft(OutputStream &S) const override { Base->printLeft(S); } + +  void printRight(OutputStream &S) const override { +    if (S.back() != ']') +      S += " "; +    S += "["; +    if (Dimension.isString()) +      S += Dimension.asString(); +    else if (Dimension.isNode()) +      Dimension.asNode()->print(S); +    S += "]"; +    Base->printRight(S); +  } +}; + +class FunctionType final : public Node { +  Node *Ret; +  NodeArray Params; +  Qualifiers CVQuals; +  FunctionRefQual RefQual; +  Node *ExceptionSpec; + +public: +  FunctionType(Node *Ret_, NodeArray Params_, Qualifiers CVQuals_, +               FunctionRefQual RefQual_, Node *ExceptionSpec_) +      : Node(KFunctionType, +             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No, +             /*FunctionCache=*/Cache::Yes), +        Ret(Ret_), Params(Params_), CVQuals(CVQuals_), RefQual(RefQual_), +        ExceptionSpec(ExceptionSpec_) {} + +  bool hasRHSComponentSlow(OutputStream &) const override { return true; } +  bool hasFunctionSlow(OutputStream &) const override { return true; } + +  // Handle C++'s ... quirky decl grammar by using the left & right +  // distinction. Consider: +  //   int (*f(float))(char) {} +  // f is a function that takes a float and returns a pointer to a function +  // that takes a char and returns an int. If we're trying to print f, start +  // by printing out the return types's left, then print our parameters, then +  // finally print right of the return type. +  void printLeft(OutputStream &S) const override { +    Ret->printLeft(S); +    S += " "; +  } + +  void printRight(OutputStream &S) const override { +    S += "("; +    Params.printWithComma(S); +    S += ")"; +    Ret->printRight(S); + +    if (CVQuals & QualConst) +      S += " const"; +    if (CVQuals & QualVolatile) +      S += " volatile"; +    if (CVQuals & QualRestrict) +      S += " restrict"; + +    if (RefQual == FrefQualLValue) +      S += " &"; +    else if (RefQual == FrefQualRValue) +      S += " &&"; + +    if (ExceptionSpec != nullptr) { +      S += ' '; +      ExceptionSpec->print(S); +    } +  } +}; + +class NoexceptSpec : public Node { +  Node *E; +public: +  NoexceptSpec(Node *E_) : Node(KNoexceptSpec), E(E_) {} + +  void printLeft(OutputStream &S) const override { +    S += "noexcept("; +    E->print(S); +    S += ")"; +  } +}; + +class DynamicExceptionSpec : public Node { +  NodeArray Types; +public: +  DynamicExceptionSpec(NodeArray Types_) +      : Node(KDynamicExceptionSpec), Types(Types_) {} + +  void printLeft(OutputStream &S) const override { +    S += "throw("; +    Types.printWithComma(S); +    S += ')'; +  } +}; + +class FunctionEncoding final : public Node { +  Node *Ret; +  Node *Name; +  NodeArray Params; +  Node *Attrs; +  Qualifiers CVQuals; +  FunctionRefQual RefQual; + +public: +  FunctionEncoding(Node *Ret_, Node *Name_, NodeArray Params_, +                   Node *Attrs_, Qualifiers CVQuals_, FunctionRefQual RefQual_) +      : Node(KFunctionEncoding, +             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No, +             /*FunctionCache=*/Cache::Yes), +        Ret(Ret_), Name(Name_), Params(Params_), Attrs(Attrs_), +        CVQuals(CVQuals_), RefQual(RefQual_) {} + +  Qualifiers getCVQuals() const { return CVQuals; } +  FunctionRefQual getRefQual() const { return RefQual; } +  NodeArray getParams() const { return Params; } +  Node *getReturnType() const { return Ret; } + +  bool hasRHSComponentSlow(OutputStream &) const override { return true; } +  bool hasFunctionSlow(OutputStream &) const override { return true; } + +  Node *getName() { return const_cast<Node *>(Name); } + +  void printLeft(OutputStream &S) const override { +    if (Ret) { +      Ret->printLeft(S); +      if (!Ret->hasRHSComponent(S)) +        S += " "; +    } +    Name->print(S); +  } + +  void printRight(OutputStream &S) const override { +    S += "("; +    Params.printWithComma(S); +    S += ")"; +    if (Ret) +      Ret->printRight(S); + +    if (CVQuals & QualConst) +      S += " const"; +    if (CVQuals & QualVolatile) +      S += " volatile"; +    if (CVQuals & QualRestrict) +      S += " restrict"; + +    if (RefQual == FrefQualLValue) +      S += " &"; +    else if (RefQual == FrefQualRValue) +      S += " &&"; + +    if (Attrs != nullptr) +      Attrs->print(S); +  } +}; + +class LiteralOperator : public Node { +  const Node *OpName; + +public: +  LiteralOperator(Node *OpName_) : Node(KLiteralOperator), OpName(OpName_) {} + +  void printLeft(OutputStream &S) const override { +    S += "operator\"\" "; +    OpName->print(S); +  } +}; + +class SpecialName final : public Node { +  const StringView Special; +  const Node *Child; + +public: +  SpecialName(StringView Special_, Node* Child_) +      : Node(KSpecialName), Special(Special_), Child(Child_) {} + +  void printLeft(OutputStream &S) const override { +    S += Special; +    Child->print(S); +  } +}; + +class CtorVtableSpecialName final : public Node { +  const Node *FirstType; +  const Node *SecondType; + +public: +  CtorVtableSpecialName(Node *FirstType_, Node *SecondType_) +      : Node(KCtorVtableSpecialName), +        FirstType(FirstType_), SecondType(SecondType_) {} + +  void printLeft(OutputStream &S) const override { +    S += "construction vtable for "; +    FirstType->print(S); +    S += "-in-"; +    SecondType->print(S); +  } +}; + +struct NestedName : Node { +  Node *Qual; +  Node *Name; + +  NestedName(Node *Qual_, Node *Name_) +      : Node(KNestedName), Qual(Qual_), Name(Name_) {} + +  StringView getBaseName() const override { return Name->getBaseName(); } + +  void printLeft(OutputStream &S) const override { +    Qual->print(S); +    S += "::"; +    Name->print(S); +  } +}; + +struct LocalName : Node { +  Node *Encoding; +  Node *Entity; + +  LocalName(Node *Encoding_, Node *Entity_) +      : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {} + +  void printLeft(OutputStream &S) const override { +    Encoding->print(S); +    S += "::"; +    Entity->print(S); +  } +}; + +class QualifiedName final : public Node { +  // qualifier::name +  const Node *Qualifier; +  const Node *Name; + +public: +  QualifiedName(Node* Qualifier_, Node* Name_) +      : Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {} + +  StringView getBaseName() const override { return Name->getBaseName(); } + +  void printLeft(OutputStream &S) const override { +    Qualifier->print(S); +    S += "::"; +    Name->print(S); +  } +}; + +class VectorType final : public Node { +  const Node *BaseType; +  const NodeOrString Dimension; +  const bool IsPixel; + +public: +  VectorType(NodeOrString Dimension_) +      : Node(KVectorType), BaseType(nullptr), Dimension(Dimension_), +        IsPixel(true) {} +  VectorType(Node *BaseType_, NodeOrString Dimension_) +      : Node(KVectorType), BaseType(BaseType_), +        Dimension(Dimension_), IsPixel(false) {} + +  void printLeft(OutputStream &S) const override { +    if (IsPixel) { +      S += "pixel vector["; +      S += Dimension.asString(); +      S += "]"; +    } else { +      BaseType->print(S); +      S += " vector["; +      if (Dimension.isNode()) +        Dimension.asNode()->print(S); +      else if (Dimension.isString()) +        S += Dimension.asString(); +      S += "]"; +    } +  } +}; + +/// An unexpanded parameter pack (either in the expression or type context). If +/// this AST is correct, this node will have a ParameterPackExpansion node above +/// it. +/// +/// This node is created when some <template-args> are found that apply to an +/// <encoding>, and is stored in the TemplateParams table. In order for this to +/// appear in the final AST, it has to referenced via a <template-param> (ie, +/// T_). +class ParameterPack final : public Node { +  NodeArray Data; + +  // Setup OutputStream for a pack expansion unless we're already expanding one. +  void initializePackExpansion(OutputStream &S) const { +    if (S.CurrentPackMax == std::numeric_limits<unsigned>::max()) { +      S.CurrentPackMax = static_cast<unsigned>(Data.size()); +      S.CurrentPackIndex = 0; +    } +  } + +public: +  ParameterPack(NodeArray Data_) : Node(KParameterPack), Data(Data_) { +    ArrayCache = FunctionCache = RHSComponentCache = Cache::Unknown; +    if (std::all_of(Data.begin(), Data.end(), [](Node* P) { +          return P->ArrayCache == Cache::No; +        })) +      ArrayCache = Cache::No; +    if (std::all_of(Data.begin(), Data.end(), [](Node* P) { +          return P->FunctionCache == Cache::No; +        })) +      FunctionCache = Cache::No; +    if (std::all_of(Data.begin(), Data.end(), [](Node* P) { +          return P->RHSComponentCache == Cache::No; +        })) +      RHSComponentCache = Cache::No; +  } + +  bool hasRHSComponentSlow(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    return Idx < Data.size() && Data[Idx]->hasRHSComponent(S); +  } +  bool hasArraySlow(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    return Idx < Data.size() && Data[Idx]->hasArray(S); +  } +  bool hasFunctionSlow(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    return Idx < Data.size() && Data[Idx]->hasFunction(S); +  } +  const Node *getSyntaxNode(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    return Idx < Data.size() ? Data[Idx]->getSyntaxNode(S) : this; +  } + +  void printLeft(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    if (Idx < Data.size()) +      Data[Idx]->printLeft(S); +  } +  void printRight(OutputStream &S) const override { +    initializePackExpansion(S); +    size_t Idx = S.CurrentPackIndex; +    if (Idx < Data.size()) +      Data[Idx]->printRight(S); +  } +}; + +/// A variadic template argument. This node represents an occurrence of +/// J<something>E in some <template-args>. It isn't itself unexpanded, unless +/// one of it's Elements is. The parser inserts a ParameterPack into the +/// TemplateParams table if the <template-args> this pack belongs to apply to an +/// <encoding>. +class TemplateArgumentPack final : public Node { +  NodeArray Elements; +public: +  TemplateArgumentPack(NodeArray Elements_) +      : Node(KTemplateArgumentPack), Elements(Elements_) {} + +  NodeArray getElements() const { return Elements; } + +  void printLeft(OutputStream &S) const override { +    Elements.printWithComma(S); +  } +}; + +/// A pack expansion. Below this node, there are some unexpanded ParameterPacks +/// which each have Child->ParameterPackSize elements. +class ParameterPackExpansion final : public Node { +  const Node *Child; + +public: +  ParameterPackExpansion(Node* Child_) +      : Node(KParameterPackExpansion), Child(Child_) {} + +  const Node *getChild() const { return Child; } + +  void printLeft(OutputStream &S) const override { +    constexpr unsigned Max = std::numeric_limits<unsigned>::max(); +    SwapAndRestore<unsigned> SavePackIdx(S.CurrentPackIndex, Max); +    SwapAndRestore<unsigned> SavePackMax(S.CurrentPackMax, Max); +    size_t StreamPos = S.getCurrentPosition(); + +    // Print the first element in the pack. If Child contains a ParameterPack, +    // it will set up S.CurrentPackMax and print the first element. +    Child->print(S); + +    // No ParameterPack was found in Child. This can occur if we've found a pack +    // expansion on a <function-param>. +    if (S.CurrentPackMax == Max) { +      S += "..."; +      return; +    } + +    // We found a ParameterPack, but it has no elements. Erase whatever we may +    // of printed. +    if (S.CurrentPackMax == 0) { +      S.setCurrentPosition(StreamPos); +      return; +    } + +    // Else, iterate through the rest of the elements in the pack. +    for (unsigned I = 1, E = S.CurrentPackMax; I < E; ++I) { +      S += ", "; +      S.CurrentPackIndex = I; +      Child->print(S); +    } +  } +}; + +class TemplateArgs final : public Node { +  NodeArray Params; + +public: +  TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {} + +  NodeArray getParams() { return Params; } + +  void printLeft(OutputStream &S) const override { +    S += "<"; +    Params.printWithComma(S); +    if (S.back() == '>') +      S += " "; +    S += ">"; +  } +}; + +struct ForwardTemplateReference : Node { +  size_t Index; +  Node *Ref = nullptr; + +  // If we're currently printing this node. It is possible (though invalid) for +  // a forward template reference to refer to itself via a substitution. This +  // creates a cyclic AST, which will stack overflow printing. To fix this, bail +  // out if more than one print* function is active. +  mutable bool Printing = false; + +  ForwardTemplateReference(size_t Index_) +      : Node(KForwardTemplateReference, Cache::Unknown, Cache::Unknown, +             Cache::Unknown), +        Index(Index_) {} + +  bool hasRHSComponentSlow(OutputStream &S) const override { +    if (Printing) +      return false; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    return Ref->hasRHSComponent(S); +  } +  bool hasArraySlow(OutputStream &S) const override { +    if (Printing) +      return false; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    return Ref->hasArray(S); +  } +  bool hasFunctionSlow(OutputStream &S) const override { +    if (Printing) +      return false; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    return Ref->hasFunction(S); +  } +  const Node *getSyntaxNode(OutputStream &S) const override { +    if (Printing) +      return this; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    return Ref->getSyntaxNode(S); +  } + +  void printLeft(OutputStream &S) const override { +    if (Printing) +      return; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    Ref->printLeft(S); +  } +  void printRight(OutputStream &S) const override { +    if (Printing) +      return; +    SwapAndRestore<bool> SavePrinting(Printing, true); +    Ref->printRight(S); +  } +}; + +struct NameWithTemplateArgs : Node { +  // name<template_args> +  Node *Name; +  Node *TemplateArgs; + +  NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_) +      : Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {} + +  StringView getBaseName() const override { return Name->getBaseName(); } + +  void printLeft(OutputStream &S) const override { +    Name->print(S); +    TemplateArgs->print(S); +  } +}; + +class GlobalQualifiedName final : public Node { +  Node *Child; + +public: +  GlobalQualifiedName(Node* Child_) +      : Node(KGlobalQualifiedName), Child(Child_) {} + +  StringView getBaseName() const override { return Child->getBaseName(); } + +  void printLeft(OutputStream &S) const override { +    S += "::"; +    Child->print(S); +  } +}; + +struct StdQualifiedName : Node { +  Node *Child; + +  StdQualifiedName(Node *Child_) : Node(KStdQualifiedName), Child(Child_) {} + +  StringView getBaseName() const override { return Child->getBaseName(); } + +  void printLeft(OutputStream &S) const override { +    S += "std::"; +    Child->print(S); +  } +}; + +enum class SpecialSubKind { +  allocator, +  basic_string, +  string, +  istream, +  ostream, +  iostream, +}; + +class ExpandedSpecialSubstitution final : public Node { +  SpecialSubKind SSK; + +public: +  ExpandedSpecialSubstitution(SpecialSubKind SSK_) +      : Node(KExpandedSpecialSubstitution), SSK(SSK_) {} + +  StringView getBaseName() const override { +    switch (SSK) { +    case SpecialSubKind::allocator: +      return StringView("allocator"); +    case SpecialSubKind::basic_string: +      return StringView("basic_string"); +    case SpecialSubKind::string: +      return StringView("basic_string"); +    case SpecialSubKind::istream: +      return StringView("basic_istream"); +    case SpecialSubKind::ostream: +      return StringView("basic_ostream"); +    case SpecialSubKind::iostream: +      return StringView("basic_iostream"); +    } +    LLVM_BUILTIN_UNREACHABLE; +  } + +  void printLeft(OutputStream &S) const override { +    switch (SSK) { +    case SpecialSubKind::allocator: +      S += "std::basic_string<char, std::char_traits<char>, " +           "std::allocator<char> >";        break; -    case 'x': -      db.names.push_back("long long"); -      ++first; +    case SpecialSubKind::basic_string: +    case SpecialSubKind::string: +      S += "std::basic_string<char, std::char_traits<char>, " +           "std::allocator<char> >";        break; -    case 'y': -      db.names.push_back("unsigned long long"); -      ++first; +    case SpecialSubKind::istream: +      S += "std::basic_istream<char, std::char_traits<char> >";        break; -    case 'n': -      db.names.push_back("__int128"); -      ++first; +    case SpecialSubKind::ostream: +      S += "std::basic_ostream<char, std::char_traits<char> >";        break; -    case 'o': -      db.names.push_back("unsigned __int128"); -      ++first; +    case SpecialSubKind::iostream: +      S += "std::basic_iostream<char, std::char_traits<char> >";        break; -    case 'f': -      db.names.push_back("float"); -      ++first; +    } +  } +}; + +class SpecialSubstitution final : public Node { +public: +  SpecialSubKind SSK; + +  SpecialSubstitution(SpecialSubKind SSK_) +      : Node(KSpecialSubstitution), SSK(SSK_) {} + +  StringView getBaseName() const override { +    switch (SSK) { +    case SpecialSubKind::allocator: +      return StringView("allocator"); +    case SpecialSubKind::basic_string: +      return StringView("basic_string"); +    case SpecialSubKind::string: +      return StringView("string"); +    case SpecialSubKind::istream: +      return StringView("istream"); +    case SpecialSubKind::ostream: +      return StringView("ostream"); +    case SpecialSubKind::iostream: +      return StringView("iostream"); +    } +    LLVM_BUILTIN_UNREACHABLE; +  } + +  void printLeft(OutputStream &S) const override { +    switch (SSK) { +    case SpecialSubKind::allocator: +      S += "std::allocator";        break; -    case 'd': -      db.names.push_back("double"); -      ++first; +    case SpecialSubKind::basic_string: +      S += "std::basic_string";        break; -    case 'e': -      db.names.push_back("long double"); -      ++first; +    case SpecialSubKind::string: +      S += "std::string";        break; -    case 'g': -      db.names.push_back("__float128"); -      ++first; +    case SpecialSubKind::istream: +      S += "std::istream";        break; -    case 'z': -      db.names.push_back("..."); -      ++first; +    case SpecialSubKind::ostream: +      S += "std::ostream";        break; -    case 'u': { -      const char *t = parse_source_name(first + 1, last, db); -      if (t != first + 1) -        first = t; -    } break; -    case 'D': -      if (first + 1 != last) { -        switch (first[1]) { -        case 'd': -          db.names.push_back("decimal64"); -          first += 2; -          break; -        case 'e': -          db.names.push_back("decimal128"); -          first += 2; -          break; -        case 'f': -          db.names.push_back("decimal32"); -          first += 2; -          break; -        case 'h': -          db.names.push_back("decimal16"); -          first += 2; -          break; -        case 'i': -          db.names.push_back("char32_t"); -          first += 2; -          break; -        case 's': -          db.names.push_back("char16_t"); -          first += 2; -          break; -        case 'a': -          db.names.push_back("auto"); -          first += 2; -          break; -        case 'c': -          db.names.push_back("decltype(auto)"); -          first += 2; -          break; -        case 'n': -          db.names.push_back("std::nullptr_t"); -          first += 2; -          break; -        } -      } +    case SpecialSubKind::iostream: +      S += "std::iostream";        break;      }    } -  return first; -} +}; -// <CV-qualifiers> ::= [r] [V] [K] +class CtorDtorName final : public Node { +  const Node *Basename; +  const bool IsDtor; -static const char *parse_cv_qualifiers(const char *first, const char *last, -                                       unsigned &cv) { -  cv = 0; -  if (first != last) { -    if (*first == 'r') { -      cv |= CV_restrict; -      ++first; -    } -    if (*first == 'V') { -      cv |= CV_volatile; -      ++first; -    } -    if (*first == 'K') { -      cv |= CV_const; -      ++first; -    } +public: +  CtorDtorName(Node *Basename_, bool IsDtor_) +      : Node(KCtorDtorName), Basename(Basename_), IsDtor(IsDtor_) {} + +  void printLeft(OutputStream &S) const override { +    if (IsDtor) +      S += "~"; +    S += Basename->getBaseName();    } -  return first; -} +}; -// <template-param> ::= T_    # first template parameter -//                  ::= T <parameter-2 non-negative number> _ +class DtorName : public Node { +  const Node *Base; -template <class C> -static const char *parse_template_param(const char *first, const char *last, -                                        C &db) { -  if (last - first >= 2) { -    if (*first == 'T') { -      if (first[1] == '_') { -        if (db.template_param.empty()) -          return first; -        if (!db.template_param.back().empty()) { -          for (auto &t : db.template_param.back().front()) -            db.names.push_back(t); -          first += 2; -        } else { -          db.names.push_back("T_"); -          first += 2; -          db.fix_forward_references = true; -        } -      } else if (isdigit(first[1])) { -        const char *t = first + 1; -        size_t sub = static_cast<size_t>(*t - '0'); -        for (++t; t != last && isdigit(*t); ++t) { -          sub *= 10; -          sub += static_cast<size_t>(*t - '0'); -        } -        if (t == last || *t != '_' || db.template_param.empty()) -          return first; -        ++sub; -        if (sub < db.template_param.back().size()) { -          for (auto &temp : db.template_param.back()[sub]) -            db.names.push_back(temp); -          first = t + 1; -        } else { -          db.names.push_back(std::string(first, t + 1)); -          first = t + 1; -          db.fix_forward_references = true; -        } -      } -    } +public: +  DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {} + +  void printLeft(OutputStream &S) const override { +    S += "~"; +    Base->printLeft(S);    } -  return first; -} +}; -// cc <type> <expression>                               # const_cast<type> -// (expression) - -template <class C> -static const char *parse_const_cast_expr(const char *first, const char *last, -                                         C &db) { -  if (last - first >= 3 && first[0] == 'c' && first[1] == 'c') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto expr = db.names.back().move_full(); -        db.names.pop_back(); -        if (db.names.empty()) -          return first; -        db.names.back() = -            "const_cast<" + db.names.back().move_full() + ">(" + expr + ")"; -        first = t1; -      } -    } +class UnnamedTypeName : public Node { +  const StringView Count; + +public: +  UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {} + +  void printLeft(OutputStream &S) const override { +    S += "'unnamed"; +    S += Count; +    S += "\'";    } -  return first; -} +}; -// dc <type> <expression>                               # dynamic_cast<type> -// (expression) - -template <class C> -static const char *parse_dynamic_cast_expr(const char *first, const char *last, -                                           C &db) { -  if (last - first >= 3 && first[0] == 'd' && first[1] == 'c') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto expr = db.names.back().move_full(); -        db.names.pop_back(); -        if (db.names.empty()) -          return first; -        db.names.back() = -            "dynamic_cast<" + db.names.back().move_full() + ">(" + expr + ")"; -        first = t1; -      } -    } +class ClosureTypeName : public Node { +  NodeArray Params; +  StringView Count; + +public: +  ClosureTypeName(NodeArray Params_, StringView Count_) +      : Node(KClosureTypeName), Params(Params_), Count(Count_) {} + +  void printLeft(OutputStream &S) const override { +    S += "\'lambda"; +    S += Count; +    S += "\'("; +    Params.printWithComma(S); +    S += ")";    } -  return first; -} +}; -// rc <type> <expression>                               # reinterpret_cast<type> -// (expression) - -template <class C> -static const char *parse_reinterpret_cast_expr(const char *first, -                                               const char *last, C &db) { -  if (last - first >= 3 && first[0] == 'r' && first[1] == 'c') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto expr = db.names.back().move_full(); -        db.names.pop_back(); -        if (db.names.empty()) -          return first; -        db.names.back() = "reinterpret_cast<" + db.names.back().move_full() + -                          ">(" + expr + ")"; -        first = t1; -      } -    } +class StructuredBindingName : public Node { +  NodeArray Bindings; +public: +  StructuredBindingName(NodeArray Bindings_) +      : Node(KStructuredBindingName), Bindings(Bindings_) {} + +  void printLeft(OutputStream &S) const override { +    S += '['; +    Bindings.printWithComma(S); +    S += ']';    } -  return first; -} +}; -// sc <type> <expression>                               # static_cast<type> -// (expression) - -template <class C> -static const char *parse_static_cast_expr(const char *first, const char *last, -                                          C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 'c') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto expr = db.names.back().move_full(); -        db.names.pop_back(); -        db.names.back() = -            "static_cast<" + db.names.back().move_full() + ">(" + expr + ")"; -        first = t1; -      } -    } +// -- Expression Nodes -- + +struct Expr : public Node { +  Expr(Kind K = KExpr) : Node(K) {} +}; + +class BinaryExpr : public Expr { +  const Node *LHS; +  const StringView InfixOperator; +  const Node *RHS; + +public: +  BinaryExpr(Node *LHS_, StringView InfixOperator_, Node *RHS_) +      : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {} + +  void printLeft(OutputStream &S) const override { +    // might be a template argument expression, then we need to disambiguate +    // with parens. +    if (InfixOperator == ">") +      S += "("; + +    S += "("; +    LHS->print(S); +    S += ") "; +    S += InfixOperator; +    S += " ("; +    RHS->print(S); +    S += ")"; + +    if (InfixOperator == ">") +      S += ")";    } -  return first; -} +}; -// sp <expression>                                  # pack expansion +class ArraySubscriptExpr : public Expr { +  const Node *Op1; +  const Node *Op2; -template <class C> -static const char *parse_pack_expansion(const char *first, const char *last, -                                        C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 'p') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) -      first = t; +public: +  ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {} + +  void printLeft(OutputStream &S) const override { +    S += "("; +    Op1->print(S); +    S += ")["; +    Op2->print(S); +    S += "]";    } -  return first; -} +}; -// st <type>                                            # sizeof (a type) +class PostfixExpr : public Expr { +  const Node *Child; +  const StringView Operand; -template <class C> -static const char *parse_sizeof_type_expr(const char *first, const char *last, -                                          C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 't') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back() = "sizeof (" + db.names.back().move_full() + ")"; -      first = t; -    } +public: +  PostfixExpr(Node *Child_, StringView Operand_) +      : Child(Child_), Operand(Operand_) {} + +  void printLeft(OutputStream &S) const override { +    S += "("; +    Child->print(S); +    S += ")"; +    S += Operand;    } -  return first; -} +}; + +class ConditionalExpr : public Expr { +  const Node *Cond; +  const Node *Then; +  const Node *Else; + +public: +  ConditionalExpr(Node *Cond_, Node *Then_, Node *Else_) +      : Cond(Cond_), Then(Then_), Else(Else_) {} + +  void printLeft(OutputStream &S) const override { +    S += "("; +    Cond->print(S); +    S += ") ? ("; +    Then->print(S); +    S += ") : ("; +    Else->print(S); +    S += ")"; +  } +}; + +class MemberExpr : public Expr { +  const Node *LHS; +  const StringView Kind; +  const Node *RHS; + +public: +  MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_) +      : LHS(LHS_), Kind(Kind_), RHS(RHS_) {} -// sz <expr>                                            # sizeof (a expression) +  void printLeft(OutputStream &S) const override { +    LHS->print(S); +    S += Kind; +    RHS->print(S); +  } +}; + +class EnclosingExpr : public Expr { +  const StringView Prefix; +  const Node *Infix; +  const StringView Postfix; + +public: +  EnclosingExpr(StringView Prefix_, Node *Infix_, StringView Postfix_) +      : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {} + +  void printLeft(OutputStream &S) const override { +    S += Prefix; +    Infix->print(S); +    S += Postfix; +  } +}; + +class CastExpr : public Expr { +  // cast_kind<to>(from) +  const StringView CastKind; +  const Node *To; +  const Node *From; + +public: +  CastExpr(StringView CastKind_, Node *To_, Node *From_) +      : CastKind(CastKind_), To(To_), From(From_) {} + +  void printLeft(OutputStream &S) const override { +    S += CastKind; +    S += "<"; +    To->printLeft(S); +    S += ">("; +    From->printLeft(S); +    S += ")"; +  } +}; -template <class C> -static const char *parse_sizeof_expr_expr(const char *first, const char *last, -                                          C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 'z') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back() = "sizeof (" + db.names.back().move_full() + ")"; -      first = t; +class SizeofParamPackExpr : public Expr { +  Node *Pack; + +public: +  SizeofParamPackExpr(Node *Pack_) : Pack(Pack_) {} + +  void printLeft(OutputStream &S) const override { +    S += "sizeof...("; +    ParameterPackExpansion PPE(Pack); +    PPE.printLeft(S); +    S += ")"; +  } +}; + +class CallExpr : public Expr { +  const Node *Callee; +  NodeArray Args; + +public: +  CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {} + +  void printLeft(OutputStream &S) const override { +    Callee->print(S); +    S += "("; +    Args.printWithComma(S); +    S += ")"; +  } +}; + +class NewExpr : public Expr { +  // new (expr_list) type(init_list) +  NodeArray ExprList; +  Node *Type; +  NodeArray InitList; +  bool IsGlobal; // ::operator new ? +  bool IsArray;  // new[] ? +public: +  NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_, +          bool IsArray_) +      : ExprList(ExprList_), Type(Type_), InitList(InitList_), +        IsGlobal(IsGlobal_), IsArray(IsArray_) {} + +  void printLeft(OutputStream &S) const override { +    if (IsGlobal) +      S += "::operator "; +    S += "new"; +    if (IsArray) +      S += "[]"; +    S += ' '; +    if (!ExprList.empty()) { +      S += "("; +      ExprList.printWithComma(S); +      S += ")";      } +    Type->print(S); +    if (!InitList.empty()) { +      S += "("; +      InitList.printWithComma(S); +      S += ")"; +    } +    } -  return first; -} +}; -// sZ <template-param>                                  # size of a parameter -// pack - -template <class C> -static const char *parse_sizeof_param_pack_expr(const char *first, -                                                const char *last, C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' && -      first[2] == 'T') { -    size_t k0 = db.names.size(); -    const char *t = parse_template_param(first + 2, last, db); -    size_t k1 = db.names.size(); -    if (t != first + 2) { -      std::string tmp("sizeof...("); -      size_t k = k0; -      if (k != k1) { -        tmp += db.names[k].move_full(); -        for (++k; k != k1; ++k) -          tmp += ", " + db.names[k].move_full(); -      } -      tmp += ")"; -      for (; k1 != k0; --k1) -        db.names.pop_back(); -      db.names.push_back(std::move(tmp)); -      first = t; +class DeleteExpr : public Expr { +  Node *Op; +  bool IsGlobal; +  bool IsArray; + +public: +  DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_) +      : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {} + +  void printLeft(OutputStream &S) const override { +    if (IsGlobal) +      S += "::"; +    S += "delete"; +    if (IsArray) +      S += "[] "; +    Op->print(S); +  } +}; + +class PrefixExpr : public Expr { +  StringView Prefix; +  Node *Child; + +public: +  PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {} + +  void printLeft(OutputStream &S) const override { +    S += Prefix; +    S += "("; +    Child->print(S); +    S += ")"; +  } +}; + +class FunctionParam : public Expr { +  StringView Number; + +public: +  FunctionParam(StringView Number_) : Number(Number_) {} + +  void printLeft(OutputStream &S) const override { +    S += "fp"; +    S += Number; +  } +}; + +class ConversionExpr : public Expr { +  const Node *Type; +  NodeArray Expressions; + +public: +  ConversionExpr(const Node *Type_, NodeArray Expressions_) +      : Type(Type_), Expressions(Expressions_) {} + +  void printLeft(OutputStream &S) const override { +    S += "("; +    Type->print(S); +    S += ")("; +    Expressions.printWithComma(S); +    S += ")"; +  } +}; + +class InitListExpr : public Expr { +  Node *Ty; +  NodeArray Inits; +public: +  InitListExpr(Node *Ty_, NodeArray Inits_) : Ty(Ty_), Inits(Inits_) {} + +  void printLeft(OutputStream &S) const override { +    if (Ty) +      Ty->print(S); +    S += '{'; +    Inits.printWithComma(S); +    S += '}'; +  } +}; + +class BracedExpr : public Expr { +  Node *Elem; +  Node *Init; +  bool IsArray; +public: +  BracedExpr(Node *Elem_, Node *Init_, bool IsArray_) +      : Expr(KBracedExpr), Elem(Elem_), Init(Init_), IsArray(IsArray_) {} + +  void printLeft(OutputStream &S) const override { +    if (IsArray) { +      S += '['; +      Elem->print(S); +      S += ']'; +    } else { +      S += '.'; +      Elem->print(S);      } +    if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr) +      S += " = "; +    Init->print(S);    } -  return first; -} +}; + +class BracedRangeExpr : public Expr { +  Node *First; +  Node *Last; +  Node *Init; +public: +  BracedRangeExpr(Node *First_, Node *Last_, Node *Init_) +      : Expr(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {} + +  void printLeft(OutputStream &S) const override { +    S += '['; +    First->print(S); +    S += " ... "; +    Last->print(S); +    S += ']'; +    if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr) +      S += " = "; +    Init->print(S); +  } +}; -// <function-param> ::= fp <top-level CV-qualifiers> _ # L == 0, first parameter -//                  ::= fp <top-level CV-qualifiers> <parameter-2 non-negative -//                  number> _   # L == 0, second and later parameters -//                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> -//                  _         # L > 0, first parameter -//                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers> -//                  <parameter-2 non-negative number> _   # L > 0, second and -//                  later parameters - -template <class C> -static const char *parse_function_param(const char *first, const char *last, -                                        C &db) { -  if (last - first >= 3 && *first == 'f') { -    if (first[1] == 'p') { -      unsigned cv; -      const char *t = parse_cv_qualifiers(first + 2, last, cv); -      const char *t1 = parse_number(t, last); -      if (t1 != last && *t1 == '_') { -        db.names.push_back("fp" + std::string(t, t1)); -        first = t1 + 1; +struct FoldExpr : Expr { +  Node *Pack, *Init; +  StringView OperatorName; +  bool IsLeftFold; + +  FoldExpr(bool IsLeftFold_, StringView OperatorName_, Node *Pack_, Node *Init_) +      : Pack(Pack_), Init(Init_), OperatorName(OperatorName_), +        IsLeftFold(IsLeftFold_) {} + +  void printLeft(OutputStream &S) const override { +    auto PrintPack = [&] { +      S += '('; +      ParameterPackExpansion(Pack).print(S); +      S += ')'; +    }; + +    S += '('; + +    if (IsLeftFold) { +      // init op ... op pack +      if (Init != nullptr) { +        Init->print(S); +        S += ' '; +        S += OperatorName; +        S += ' ';        } -    } else if (first[1] == 'L') { -      unsigned cv; -      const char *t0 = parse_number(first + 2, last); -      if (t0 != last && *t0 == 'p') { -        ++t0; -        const char *t = parse_cv_qualifiers(t0, last, cv); -        const char *t1 = parse_number(t, last); -        if (t1 != last && *t1 == '_') { -          db.names.push_back("fp" + std::string(t, t1)); -          first = t1 + 1; -        } +      // ... op pack +      S += "... "; +      S += OperatorName; +      S += ' '; +      PrintPack(); +    } else { // !IsLeftFold +      // pack op ... +      PrintPack(); +      S += ' '; +      S += OperatorName; +      S += " ..."; +      // pack op ... op init +      if (Init != nullptr) { +        S += ' '; +        S += OperatorName; +        S += ' '; +        Init->print(S);        }      } +    S += ')';    } -  return first; -} +}; -// sZ <function-param>                                  # size of a function -// parameter pack +class ThrowExpr : public Expr { +  const Node *Op; -template <class C> -static const char *parse_sizeof_function_param_pack_expr(const char *first, -                                                         const char *last, -                                                         C &db) { -  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' && -      first[2] == 'f') { -    const char *t = parse_function_param(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back() = "sizeof...(" + db.names.back().move_full() + ")"; -      first = t; -    } +public: +  ThrowExpr(Node *Op_) : Op(Op_) {} + +  void printLeft(OutputStream &S) const override { +    S += "throw "; +    Op->print(S);    } -  return first; -} +}; -// te <expression>                                      # typeid (expression) -// ti <type>                                            # typeid (type) - -template <class C> -static const char *parse_typeid_expr(const char *first, const char *last, -                                     C &db) { -  if (last - first >= 3 && first[0] == 't' && -      (first[1] == 'e' || first[1] == 'i')) { -    const char *t; -    if (first[1] == 'e') -      t = parse_expression(first + 2, last, db); -    else -      t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back() = "typeid(" + db.names.back().move_full() + ")"; -      first = t; -    } +class BoolExpr : public Expr { +  bool Value; + +public: +  BoolExpr(bool Value_) : Value(Value_) {} + +  void printLeft(OutputStream &S) const override { +    S += Value ? StringView("true") : StringView("false");    } -  return first; -} +}; + +class IntegerCastExpr : public Expr { +  // ty(integer) +  Node *Ty; +  StringView Integer; + +public: +  IntegerCastExpr(Node *Ty_, StringView Integer_) +      : Ty(Ty_), Integer(Integer_) {} + +  void printLeft(OutputStream &S) const override { +    S += "("; +    Ty->print(S); +    S += ")"; +    S += Integer; +  } +}; + +class IntegerExpr : public Expr { +  StringView Type; +  StringView Value; -// tw <expression>                                      # throw expression +public: +  IntegerExpr(StringView Type_, StringView Value_) : Type(Type_), Value(Value_) {} -template <class C> -static const char *parse_throw_expr(const char *first, const char *last, -                                    C &db) { -  if (last - first >= 3 && first[0] == 't' && first[1] == 'w') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back() = "throw " + db.names.back().move_full(); -      first = t; +  void printLeft(OutputStream &S) const override { +    if (Type.size() > 3) { +      S += "("; +      S += Type; +      S += ")";      } + +    if (Value[0] == 'n') { +      S += "-"; +      S += Value.dropFront(1); +    } else +      S += Value; + +    if (Type.size() <= 3) +      S += Type;    } -  return first; -} +}; + +template <class Float> struct FloatData; -// ds <expression> <expression>                         # expr.*expr - -template <class C> -static const char *parse_dot_star_expr(const char *first, const char *last, -                                       C &db) { -  if (last - first >= 3 && first[0] == 'd' && first[1] == 's') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto expr = db.names.back().move_full(); -        db.names.pop_back(); -        db.names.back().first += ".*" + expr; -        first = t1; +template <class Float> class FloatExpr : public Expr { +  const StringView Contents; + +public: +  FloatExpr(StringView Contents_) : Contents(Contents_) {} + +  void printLeft(OutputStream &s) const override { +    const char *first = Contents.begin(); +    const char *last = Contents.end() + 1; + +    const size_t N = FloatData<Float>::mangled_size; +    if (static_cast<std::size_t>(last - first) > N) { +      last = first + N; +      union { +        Float value; +        char buf[sizeof(Float)]; +      }; +      const char *t = first; +      char *e = buf; +      for (; t != last; ++t, ++e) { +        unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0') +                                  : static_cast<unsigned>(*t - 'a' + 10); +        ++t; +        unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0') +                                  : static_cast<unsigned>(*t - 'a' + 10); +        *e = static_cast<char>((d1 << 4) + d0);        } +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ +      std::reverse(buf, e); +#endif +      char num[FloatData<Float>::max_demangled_size] = {0}; +      int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value); +      s += StringView(num, num + n);      }    } -  return first; -} +}; -// <simple-id> ::= <source-name> [ <template-args> ] +class BumpPointerAllocator { +  struct BlockMeta { +    BlockMeta* Next; +    size_t Current; +  }; -template <class C> -static const char *parse_simple_id(const char *first, const char *last, C &db) { -  if (first != last) { -    const char *t = parse_source_name(first, last, db); -    if (t != first) { -      const char *t1 = parse_template_args(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto args = db.names.back().move_full(); -        db.names.pop_back(); -        db.names.back().first += std::move(args); -      } -      first = t1; -    } else -      first = t; +  static constexpr size_t AllocSize = 4096; +  static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta); + +  alignas(long double) char InitialBuffer[AllocSize]; +  BlockMeta* BlockList = nullptr; + +  void grow() { +    char* NewMeta = static_cast<char *>(std::malloc(AllocSize)); +    if (NewMeta == nullptr) +      std::terminate(); +    BlockList = new (NewMeta) BlockMeta{BlockList, 0};    } -  return first; -} -// <unresolved-type> ::= <template-param> -//                   ::= <decltype> -//                   ::= <substitution> +  void* allocateMassive(size_t NBytes) { +    NBytes += sizeof(BlockMeta); +    BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(std::malloc(NBytes)); +    if (NewMeta == nullptr) +      std::terminate(); +    BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0}; +    return static_cast<void*>(NewMeta + 1); +  } -template <class C> -static const char *parse_unresolved_type(const char *first, const char *last, -                                         C &db) { -  if (first != last) { -    const char *t = first; -    switch (*first) { -    case 'T': { -      size_t k0 = db.names.size(); -      t = parse_template_param(first, last, db); -      size_t k1 = db.names.size(); -      if (t != first && k1 == k0 + 1) { -        db.subs.push_back(typename C::sub_type(1, db.names.back())); -        first = t; -      } else { -        for (; k1 != k0; --k1) -          db.names.pop_back(); -      } -      break; +public: +  BumpPointerAllocator() +      : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {} + +  void* allocate(size_t N) { +    N = (N + 15u) & ~15u; +    if (N + BlockList->Current >= UsableAllocSize) { +      if (N > UsableAllocSize) +        return allocateMassive(N); +      grow();      } -    case 'D': -      t = parse_decltype(first, last, db); -      if (t != first) { -        if (db.names.empty()) -          return first; -        db.subs.push_back(typename C::sub_type(1, db.names.back())); -        first = t; -      } -      break; -    case 'S': -      t = parse_substitution(first, last, db); -      if (t != first) -        first = t; -      else { -        if (last - first > 2 && first[1] == 't') { -          t = parse_unqualified_name(first + 2, last, db); -          if (t != first + 2) { -            if (db.names.empty()) -              return first; -            db.names.back().first.insert(0, "std::"); -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -            first = t; -          } -        } -      } -      break; +    BlockList->Current += N; +    return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) + +                              BlockList->Current - N); +  } + +  void reset() { +    while (BlockList) { +      BlockMeta* Tmp = BlockList; +      BlockList = BlockList->Next; +      if (reinterpret_cast<char*>(Tmp) != InitialBuffer) +        std::free(Tmp);      } +    BlockList = new (InitialBuffer) BlockMeta{nullptr, 0};    } -  return first; -} -// <destructor-name> ::= <unresolved-type>                               # e.g., -// ~T or ~decltype(f()) -//                   ::= <simple-id>                                     # e.g., -//                   ~A<2*N> - -template <class C> -static const char *parse_destructor_name(const char *first, const char *last, -                                         C &db) { -  if (first != last) { -    const char *t = parse_unresolved_type(first, last, db); -    if (t == first) -      t = parse_simple_id(first, last, db); -    if (t != first) { -      if (db.names.empty()) -        return first; -      db.names.back().first.insert(0, "~"); -      first = t; -    } -  } -  return first; -} +  ~BumpPointerAllocator() { reset(); } +}; -// <base-unresolved-name> ::= <simple-id>                                # -// unresolved name -//          extension     ::= <operator-name>                            # -//          unresolved operator-function-id -//          extension     ::= <operator-name> <template-args>            # -//          unresolved operator template-id -//                        ::= on <operator-name>                         # -//                        unresolved operator-function-id -//                        ::= on <operator-name> <template-args>         # -//                        unresolved operator template-id -//                        ::= dn <destructor-name>                       # -//                        destructor or pseudo-destructor; -//                                                                         # -//                                                                         e.g. -//                                                                         ~X or -//                                                                         ~X<N-1> - -template <class C> -static const char *parse_base_unresolved_name(const char *first, -                                              const char *last, C &db) { -  if (last - first >= 2) { -    if ((first[0] == 'o' || first[0] == 'd') && first[1] == 'n') { -      if (first[0] == 'o') { -        const char *t = parse_operator_name(first + 2, last, db); -        if (t != first + 2) { -          first = parse_template_args(t, last, db); -          if (first != t) { -            if (db.names.size() < 2) -              return first; -            auto args = db.names.back().move_full(); -            db.names.pop_back(); -            db.names.back().first += std::move(args); -          } -        } -      } else { -        const char *t = parse_destructor_name(first + 2, last, db); -        if (t != first + 2) -          first = t; -      } +template <class T, size_t N> +class PODSmallVector { +  static_assert(std::is_pod<T>::value, +                "T is required to be a plain old data type"); + +  T* First; +  T* Last; +  T* Cap; +  T Inline[N]; + +  bool isInline() const { return First == Inline; } + +  void clearInline() { +    First = Inline; +    Last = Inline; +    Cap = Inline + N; +  } + +  void reserve(size_t NewCap) { +    size_t S = size(); +    if (isInline()) { +      auto* Tmp = static_cast<T*>(std::malloc(NewCap * sizeof(T))); +      if (Tmp == nullptr) +        std::terminate(); +      std::copy(First, Last, Tmp); +      First = Tmp;      } else { -      const char *t = parse_simple_id(first, last, db); -      if (t == first) { -        t = parse_operator_name(first, last, db); -        if (t != first) { -          first = parse_template_args(t, last, db); -          if (first != t) { -            if (db.names.size() < 2) -              return first; -            auto args = db.names.back().move_full(); -            db.names.pop_back(); -            db.names.back().first += std::move(args); -          } -        } -      } else -        first = t; +      First = static_cast<T*>(std::realloc(First, NewCap * sizeof(T))); +      if (First == nullptr) +        std::terminate();      } +    Last = First + S; +    Cap = First + NewCap;    } -  return first; -} -// <unresolved-qualifier-level> ::= <simple-id> +public: +  PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {} -template <class C> -static const char *parse_unresolved_qualifier_level(const char *first, -                                                    const char *last, C &db) { -  return parse_simple_id(first, last, db); -} +  PODSmallVector(const PODSmallVector&) = delete; +  PODSmallVector& operator=(const PODSmallVector&) = delete; -// <unresolved-name> -//  extension        ::= srN <unresolved-type> [<template-args>] -//  <unresolved-qualifier-level>* E <base-unresolved-name> -//                   ::= [gs] <base-unresolved-name>                     # x or -//                   (with "gs") ::x -//                   ::= [gs] sr <unresolved-qualifier-level>+ E -//                   <base-unresolved-name> -//                                                                       # A::x, -//                                                                       N::y, -//                                                                       A<T>::z; -//                                                                       "gs" -//                                                                       means -//                                                                       leading -//                                                                       "::" -//                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x -//                   / decltype(p)::x -//  extension        ::= sr <unresolved-type> <template-args> -//  <base-unresolved-name> -//                                                                       # -//                                                                       T::N::x -//                                                                       /decltype(p)::N::x -//  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E -//  <base-unresolved-name> - -template <class C> -static const char *parse_unresolved_name(const char *first, const char *last, -                                         C &db) { -  if (last - first > 2) { -    const char *t = first; -    bool global = false; -    if (t[0] == 'g' && t[1] == 's') { -      global = true; -      t += 2; -    } -    const char *t2 = parse_base_unresolved_name(t, last, db); -    if (t2 != t) { -      if (global) { -        if (db.names.empty()) -          return first; -        db.names.back().first.insert(0, "::"); -      } -      first = t2; -    } else if (last - t > 2 && t[0] == 's' && t[1] == 'r') { -      if (t[2] == 'N') { -        t += 3; -        const char *t1 = parse_unresolved_type(t, last, db); -        if (t1 == t || t1 == last) -          return first; -        t = t1; -        t1 = parse_template_args(t, last, db); -        if (t1 != t) { -          if (db.names.size() < 2) -            return first; -          auto args = db.names.back().move_full(); -          db.names.pop_back(); -          db.names.back().first += std::move(args); -          t = t1; -          if (t == last) { -            db.names.pop_back(); -            return first; -          } -        } -        while (*t != 'E') { -          t1 = parse_unresolved_qualifier_level(t, last, db); -          if (t1 == t || t1 == last || db.names.size() < 2) -            return first; -          auto s = db.names.back().move_full(); -          db.names.pop_back(); -          db.names.back().first += "::" + std::move(s); -          t = t1; -        } -        ++t; -        t1 = parse_base_unresolved_name(t, last, db); -        if (t1 == t) { -          if (!db.names.empty()) -            db.names.pop_back(); -          return first; -        } -        if (db.names.size() < 2) -          return first; -        auto s = db.names.back().move_full(); -        db.names.pop_back(); -        db.names.back().first += "::" + std::move(s); -        first = t1; -      } else { -        t += 2; -        const char *t1 = parse_unresolved_type(t, last, db); -        if (t1 != t) { -          t = t1; -          t1 = parse_template_args(t, last, db); -          if (t1 != t) { -            if (db.names.size() < 2) -              return first; -            auto args = db.names.back().move_full(); -            db.names.pop_back(); -            db.names.back().first += std::move(args); -            t = t1; -          } -          t1 = parse_base_unresolved_name(t, last, db); -          if (t1 == t) { -            if (!db.names.empty()) -              db.names.pop_back(); -            return first; -          } -          if (db.names.size() < 2) -            return first; -          auto s = db.names.back().move_full(); -          db.names.pop_back(); -          db.names.back().first += "::" + std::move(s); -          first = t1; -        } else { -          t1 = parse_unresolved_qualifier_level(t, last, db); -          if (t1 == t || t1 == last) -            return first; -          t = t1; -          if (global) { -            if (db.names.empty()) -              return first; -            db.names.back().first.insert(0, "::"); -          } -          while (*t != 'E') { -            t1 = parse_unresolved_qualifier_level(t, last, db); -            if (t1 == t || t1 == last || db.names.size() < 2) -              return first; -            auto s = db.names.back().move_full(); -            db.names.pop_back(); -            db.names.back().first += "::" + std::move(s); -            t = t1; -          } -          ++t; -          t1 = parse_base_unresolved_name(t, last, db); -          if (t1 == t) { -            if (!db.names.empty()) -              db.names.pop_back(); -            return first; -          } -          if (db.names.size() < 2) -            return first; -          auto s = db.names.back().move_full(); -          db.names.pop_back(); -          db.names.back().first += "::" + std::move(s); -          first = t1; -        } -      } +  PODSmallVector(PODSmallVector&& Other) : PODSmallVector() { +    if (Other.isInline()) { +      std::copy(Other.begin(), Other.end(), First); +      Last = First + Other.size(); +      Other.clear(); +      return;      } + +    First = Other.First; +    Last = Other.Last; +    Cap = Other.Cap; +    Other.clearInline();    } -  return first; -} -// dt <expression> <unresolved-name>                    # expr.name - -template <class C> -static const char *parse_dot_expr(const char *first, const char *last, C &db) { -  if (last - first >= 3 && first[0] == 'd' && first[1] == 't') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_unresolved_name(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto name = db.names.back().move_full(); -        db.names.pop_back(); -        if (db.names.empty()) -          return first; -        db.names.back().first += "." + name; -        first = t1; +  PODSmallVector& operator=(PODSmallVector&& Other) { +    if (Other.isInline()) { +      if (!isInline()) { +        std::free(First); +        clearInline();        } +      std::copy(Other.begin(), Other.end(), First); +      Last = First + Other.size(); +      Other.clear(); +      return *this;      } -  } -  return first; -} -// cl <expression>+ E                                   # call - -template <class C> -static const char *parse_call_expr(const char *first, const char *last, C &db) { -  if (last - first >= 4 && first[0] == 'c' && first[1] == 'l') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      if (t == last) -        return first; -      if (db.names.empty()) -        return first; -      db.names.back().first += db.names.back().second; -      db.names.back().second = std::string(); -      db.names.back().first.append("("); -      bool first_expr = true; -      while (*t != 'E') { -        const char *t1 = parse_expression(t, last, db); -        if (t1 == t || t1 == last) -          return first; -        if (db.names.empty()) -          return first; -        auto tmp = db.names.back().move_full(); -        db.names.pop_back(); -        if (!tmp.empty()) { -          if (db.names.empty()) -            return first; -          if (!first_expr) { -            db.names.back().first.append(", "); -            first_expr = false; -          } -          db.names.back().first.append(tmp); -        } -        t = t1; -      } -      ++t; -      if (db.names.empty()) -        return first; -      db.names.back().first.append(")"); -      first = t; +    if (isInline()) { +      First = Other.First; +      Last = Other.Last; +      Cap = Other.Cap; +      Other.clearInline(); +      return *this;      } + +    std::swap(First, Other.First); +    std::swap(Last, Other.Last); +    std::swap(Cap, Other.Cap); +    Other.clear(); +    return *this;    } -  return first; -} -// [gs] nw <expression>* _ <type> E                     # new (expr-list) type -// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type -// (init) -// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type -// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type -// (init) -// <initializer> ::= pi <expression>* E                 # parenthesized -// initialization - -template <class C> -static const char *parse_new_expr(const char *first, const char *last, C &db) { -  if (last - first >= 4) { -    const char *t = first; -    bool parsed_gs = false; -    if (t[0] == 'g' && t[1] == 's') { -      t += 2; -      parsed_gs = true; -    } -    if (t[0] == 'n' && (t[1] == 'w' || t[1] == 'a')) { -      bool is_array = t[1] == 'a'; -      t += 2; -      if (t == last) -        return first; -      bool has_expr_list = false; -      bool first_expr = true; -      while (*t != '_') { -        const char *t1 = parse_expression(t, last, db); -        if (t1 == t || t1 == last) -          return first; -        has_expr_list = true; -        if (!first_expr) { -          if (db.names.empty()) -            return first; -          auto tmp = db.names.back().move_full(); -          db.names.pop_back(); -          if (!tmp.empty()) { -            if (db.names.empty()) -              return first; -            db.names.back().first.append(", "); -            db.names.back().first.append(tmp); -            first_expr = false; -          } -        } -        t = t1; -      } -      ++t; -      const char *t1 = parse_type(t, last, db); -      if (t1 == t || t1 == last) -        return first; -      t = t1; -      bool has_init = false; -      if (last - t >= 3 && t[0] == 'p' && t[1] == 'i') { -        t += 2; -        has_init = true; -        first_expr = true; -        while (*t != 'E') { -          t1 = parse_expression(t, last, db); -          if (t1 == t || t1 == last) -            return first; -          if (!first_expr) { -            if (db.names.empty()) -              return first; -            auto tmp = db.names.back().move_full(); -            db.names.pop_back(); -            if (!tmp.empty()) { -              if (db.names.empty()) -                return first; -              db.names.back().first.append(", "); -              db.names.back().first.append(tmp); -              first_expr = false; -            } -          } -          t = t1; -        } -      } -      if (*t != 'E') -        return first; -      std::string init_list; -      if (has_init) { -        if (db.names.empty()) -          return first; -        init_list = db.names.back().move_full(); -        db.names.pop_back(); -      } -      if (db.names.empty()) -        return first; -      auto type = db.names.back().move_full(); -      db.names.pop_back(); -      std::string expr_list; -      if (has_expr_list) { -        if (db.names.empty()) -          return first; -        expr_list = db.names.back().move_full(); -        db.names.pop_back(); -      } -      std::string r; -      if (parsed_gs) -        r = "::"; -      if (is_array) -        r += "[] "; -      else -        r += " "; -      if (has_expr_list) -        r += "(" + expr_list + ") "; -      r += type; -      if (has_init) -        r += " (" + init_list + ")"; -      db.names.push_back(std::move(r)); -      first = t + 1; -    } +  void push_back(const T& Elem) { +    if (Last == Cap) +      reserve(size() * 2); +    *Last++ = Elem;    } -  return first; -} -// cv <type> <expression>                               # conversion with one -// argument -// cv <type> _ <expression>* E                          # conversion with a -// different number of arguments - -template <class C> -static const char *parse_conversion_expr(const char *first, const char *last, -                                         C &db) { -  if (last - first >= 3 && first[0] == 'c' && first[1] == 'v') { -    bool try_to_parse_template_args = db.try_to_parse_template_args; -    db.try_to_parse_template_args = false; -    const char *t = parse_type(first + 2, last, db); -    db.try_to_parse_template_args = try_to_parse_template_args; -    if (t != first + 2 && t != last) { -      if (*t != '_') { -        const char *t1 = parse_expression(t, last, db); -        if (t1 == t) -          return first; -        t = t1; -      } else { -        ++t; -        if (t == last) -          return first; -        if (*t == 'E') -          db.names.emplace_back(); -        else { -          bool first_expr = true; -          while (*t != 'E') { -            const char *t1 = parse_expression(t, last, db); -            if (t1 == t || t1 == last) -              return first; -            if (!first_expr) { -              if (db.names.empty()) -                return first; -              auto tmp = db.names.back().move_full(); -              db.names.pop_back(); -              if (!tmp.empty()) { -                if (db.names.empty()) -                  return first; -                db.names.back().first.append(", "); -                db.names.back().first.append(tmp); -                first_expr = false; -              } -            } -            t = t1; -          } -        } -        ++t; -      } -      if (db.names.size() < 2) -        return first; -      auto tmp = db.names.back().move_full(); -      db.names.pop_back(); -      db.names.back() = "(" + db.names.back().move_full() + ")(" + tmp + ")"; -      first = t; -    } +  void pop_back() { +    assert(Last != First && "Popping empty vector!"); +    --Last;    } -  return first; -} -// pt <expression> <expression>                    # expr->name - -template <class C> -static const char *parse_arrow_expr(const char *first, const char *last, -                                    C &db) { -  if (last - first >= 3 && first[0] == 'p' && first[1] == 't') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      const char *t1 = parse_expression(t, last, db); -      if (t1 != t) { -        if (db.names.size() < 2) -          return first; -        auto tmp = db.names.back().move_full(); -        db.names.pop_back(); -        db.names.back().first += "->"; -        db.names.back().first += tmp; -        first = t1; -      } +  void dropBack(size_t Index) { +    assert(Index <= size() && "dropBack() can't expand!"); +    Last = First + Index; +  } + +  T* begin() { return First; } +  T* end() { return Last; } + +  bool empty() const { return First == Last; } +  size_t size() const { return static_cast<size_t>(Last - First); } +  T& back() { +    assert(Last != First && "Calling back() on empty vector!"); +    return *(Last - 1); +  } +  T& operator[](size_t Index) { +    assert(Index < size() && "Invalid access!"); +    return *(begin() + Index); +  } +  void clear() { Last = First; } + +  ~PODSmallVector() { +    if (!isInline()) +      std::free(First); +  } +}; + +struct Db { +  const char *First; +  const char *Last; + +  // Name stack, this is used by the parser to hold temporary names that were +  // parsed. The parser collapses multiple names into new nodes to construct +  // the AST. Once the parser is finished, names.size() == 1. +  PODSmallVector<Node *, 32> Names; + +  // Substitution table. Itanium supports name substitutions as a means of +  // compression. The string "S42_" refers to the 44nd entry (base-36) in this +  // table. +  PODSmallVector<Node *, 32> Subs; + +  // Template parameter table. Like the above, but referenced like "T42_". +  // This has a smaller size compared to Subs and Names because it can be +  // stored on the stack. +  PODSmallVector<Node *, 8> TemplateParams; + +  // Set of unresolved forward <template-param> references. These can occur in a +  // conversion operator's type, and are resolved in the enclosing <encoding>. +  PODSmallVector<ForwardTemplateReference *, 4> ForwardTemplateRefs; + +  bool TryToParseTemplateArgs = true; +  bool PermitForwardTemplateReferences = false; +  bool ParsingLambdaParams = false; + +  BumpPointerAllocator ASTAllocator; + +  Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {} + +  void reset(const char *First_, const char *Last_) { +    First = First_; +    Last = Last_; +    Names.clear(); +    Subs.clear(); +    TemplateParams.clear(); +    ParsingLambdaParams = false; +    TryToParseTemplateArgs = true; +    PermitForwardTemplateReferences = false; +    ASTAllocator.reset(); +  } + +  template <class T, class... Args> T *make(Args &&... args) { +    return new (ASTAllocator.allocate(sizeof(T))) +        T(std::forward<Args>(args)...); +  } + +  template <class It> NodeArray makeNodeArray(It begin, It end) { +    size_t sz = static_cast<size_t>(end - begin); +    void *mem = ASTAllocator.allocate(sizeof(Node *) * sz); +    Node **data = new (mem) Node *[sz]; +    std::copy(begin, end, data); +    return NodeArray(data, sz); +  } + +  NodeArray popTrailingNodeArray(size_t FromPosition) { +    assert(FromPosition <= Names.size()); +    NodeArray res = +        makeNodeArray(Names.begin() + (long)FromPosition, Names.end()); +    Names.dropBack(FromPosition); +    return res; +  } + +  bool consumeIf(StringView S) { +    if (StringView(First, Last).startsWith(S)) { +      First += S.size(); +      return true;      } +    return false;    } -  return first; -} -//  <ref-qualifier> ::= R                   # & ref-qualifier -//  <ref-qualifier> ::= O                   # && ref-qualifier - -// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E - -template <class C> -static const char *parse_function_type(const char *first, const char *last, -                                       C &db) { -  if (first != last && *first == 'F') { -    const char *t = first + 1; -    if (t != last) { -      if (*t == 'Y') { -        /* extern "C" */ -        if (++t == last) -          return first; -      } -      const char *t1 = parse_type(t, last, db); -      if (t1 != t) { -        t = t1; -        std::string sig("("); -        int ref_qual = 0; -        while (true) { -          if (t == last) { -            if (!db.names.empty()) -              db.names.pop_back(); -            return first; -          } -          if (*t == 'E') { -            ++t; -            break; -          } -          if (*t == 'v') { -            ++t; -            continue; -          } -          if (*t == 'R' && t + 1 != last && t[1] == 'E') { -            ref_qual = 1; -            ++t; -            continue; -          } -          if (*t == 'O' && t + 1 != last && t[1] == 'E') { -            ref_qual = 2; -            ++t; -            continue; -          } -          size_t k0 = db.names.size(); -          t1 = parse_type(t, last, db); -          size_t k1 = db.names.size(); -          if (t1 == t || t1 == last) -            return first; -          for (size_t k = k0; k < k1; ++k) { -            if (sig.size() > 1) -              sig += ", "; -            sig += db.names[k].move_full(); -          } -          for (size_t k = k0; k < k1; ++k) -            db.names.pop_back(); -          t = t1; -        } -        sig += ")"; -        switch (ref_qual) { -        case 1: -          sig += " &"; -          break; -        case 2: -          sig += " &&"; -          break; -        } -        if (db.names.empty()) -          return first; -        db.names.back().first += " "; -        db.names.back().second.insert(0, sig); -        first = t; -      } +  bool consumeIf(char C) { +    if (First != Last && *First == C) { +      ++First; +      return true;      } +    return false;    } -  return first; -} -// <pointer-to-member-type> ::= M <class type> <member type> +  char consume() { return First != Last ? *First++ : '\0'; } -template <class C> -static const char *parse_pointer_to_member_type(const char *first, -                                                const char *last, C &db) { -  if (first != last && *first == 'M') { -    const char *t = parse_type(first + 1, last, db); -    if (t != first + 1) { -      const char *t2 = parse_type(t, last, db); -      if (t2 != t) { -        if (db.names.size() < 2) -          return first; -        auto func = std::move(db.names.back()); -        db.names.pop_back(); -        auto class_type = std::move(db.names.back()); -        if (!func.second.empty() && func.second.front() == '(') { -          db.names.back().first = -              std::move(func.first) + "(" + class_type.move_full() + "::*"; -          db.names.back().second = ")" + std::move(func.second); -        } else { -          db.names.back().first = -              std::move(func.first) + " " + class_type.move_full() + "::*"; -          db.names.back().second = std::move(func.second); -        } -        first = t2; -      } +  char look(unsigned Lookahead = 0) { +    if (static_cast<size_t>(Last - First) <= Lookahead) +      return '\0'; +    return First[Lookahead]; +  } + +  size_t numLeft() const { return static_cast<size_t>(Last - First); } + +  StringView parseNumber(bool AllowNegative = false); +  Qualifiers parseCVQualifiers(); +  bool parsePositiveInteger(size_t *Out); +  StringView parseBareSourceName(); + +  bool parseSeqId(size_t *Out); +  Node *parseSubstitution(); +  Node *parseTemplateParam(); +  Node *parseTemplateArgs(bool TagTemplates = false); +  Node *parseTemplateArg(); + +  /// Parse the <expr> production. +  Node *parseExpr(); +  Node *parsePrefixExpr(StringView Kind); +  Node *parseBinaryExpr(StringView Kind); +  Node *parseIntegerLiteral(StringView Lit); +  Node *parseExprPrimary(); +  template <class Float> Node *parseFloatingLiteral(); +  Node *parseFunctionParam(); +  Node *parseNewExpr(); +  Node *parseConversionExpr(); +  Node *parseBracedExpr(); +  Node *parseFoldExpr(); + +  /// Parse the <type> production. +  Node *parseType(); +  Node *parseFunctionType(); +  Node *parseVectorType(); +  Node *parseDecltype(); +  Node *parseArrayType(); +  Node *parsePointerToMemberType(); +  Node *parseClassEnumType(); +  Node *parseQualifiedType(); + +  Node *parseEncoding(); +  bool parseCallOffset(); +  Node *parseSpecialName(); + +  /// Holds some extra information about a <name> that is being parsed. This +  /// information is only pertinent if the <name> refers to an <encoding>. +  struct NameState { +    bool CtorDtorConversion = false; +    bool EndsWithTemplateArgs = false; +    Qualifiers CVQualifiers = QualNone; +    FunctionRefQual ReferenceQualifier = FrefQualNone; +    size_t ForwardTemplateRefsBegin; + +    NameState(Db *Enclosing) +        : ForwardTemplateRefsBegin(Enclosing->ForwardTemplateRefs.size()) {} +  }; + +  bool resolveForwardTemplateRefs(NameState &State) { +    size_t I = State.ForwardTemplateRefsBegin; +    size_t E = ForwardTemplateRefs.size(); +    for (; I < E; ++I) { +      size_t Idx = ForwardTemplateRefs[I]->Index; +      if (Idx >= TemplateParams.size()) +        return true; +      ForwardTemplateRefs[I]->Ref = TemplateParams[Idx];      } +    ForwardTemplateRefs.dropBack(State.ForwardTemplateRefsBegin); +    return false;    } -  return first; -} -// <array-type> ::= A <positive dimension number> _ <element type> -//              ::= A [<dimension expression>] _ <element type> +  /// Parse the <name> production> +  Node *parseName(NameState *State = nullptr); +  Node *parseLocalName(NameState *State); +  Node *parseOperatorName(NameState *State); +  Node *parseUnqualifiedName(NameState *State); +  Node *parseUnnamedTypeName(NameState *State); +  Node *parseSourceName(NameState *State); +  Node *parseUnscopedName(NameState *State); +  Node *parseNestedName(NameState *State); +  Node *parseCtorDtorName(Node *&SoFar, NameState *State); + +  Node *parseAbiTags(Node *N); + +  /// Parse the <unresolved-name> production. +  Node *parseUnresolvedName(); +  Node *parseSimpleId(); +  Node *parseBaseUnresolvedName(); +  Node *parseUnresolvedType(); +  Node *parseDestructorName(); + +  /// Top-level entry point into the parser. +  Node *parse(); +}; -template <class C> -static const char *parse_array_type(const char *first, const char *last, -                                    C &db) { -  if (first != last && *first == 'A' && first + 1 != last) { -    if (first[1] == '_') { -      const char *t = parse_type(first + 2, last, db); -      if (t != first + 2) { -        if (db.names.empty()) -          return first; -        if (db.names.back().second.substr(0, 2) == " [") -          db.names.back().second.erase(0, 1); -        db.names.back().second.insert(0, " []"); -        first = t; -      } -    } else if ('1' <= first[1] && first[1] <= '9') { -      const char *t = parse_number(first + 1, last); -      if (t != last && *t == '_') { -        const char *t2 = parse_type(t + 1, last, db); -        if (t2 != t + 1) { -          if (db.names.empty()) -            return first; -          if (db.names.back().second.substr(0, 2) == " [") -            db.names.back().second.erase(0, 1); -          db.names.back().second.insert(0, -                                        " [" + std::string(first + 1, t) + "]"); -          first = t2; -        } -      } -    } else { -      const char *t = parse_expression(first + 1, last, db); -      if (t != first + 1 && t != last && *t == '_') { -        const char *t2 = parse_type(++t, last, db); -        if (t2 != t) { -          if (db.names.size() < 2) -            return first; -          auto type = std::move(db.names.back()); -          db.names.pop_back(); -          auto expr = std::move(db.names.back()); -          db.names.back().first = std::move(type.first); -          if (type.second.substr(0, 2) == " [") -            type.second.erase(0, 1); -          db.names.back().second = -              " [" + expr.move_full() + "]" + std::move(type.second); -          first = t2; -        } -      } -    } +const char* parse_discriminator(const char* first, const char* last); + +// <name> ::= <nested-name> // N +//        ::= <local-name> # See Scope Encoding below  // Z +//        ::= <unscoped-template-name> <template-args> +//        ::= <unscoped-name> +// +// <unscoped-template-name> ::= <unscoped-name> +//                          ::= <substitution> +Node *Db::parseName(NameState *State) { +  consumeIf('L'); // extension + +  if (look() == 'N') +    return parseNestedName(State); +  if (look() == 'Z') +    return parseLocalName(State); + +  //        ::= <unscoped-template-name> <template-args> +  if (look() == 'S' && look(1) != 't') { +    Node *S = parseSubstitution(); +    if (S == nullptr) +      return nullptr; +    if (look() != 'I') +      return nullptr; +    Node *TA = parseTemplateArgs(State != nullptr); +    if (TA == nullptr) +      return nullptr; +    if (State) State->EndsWithTemplateArgs = true; +    return make<NameWithTemplateArgs>(S, TA);    } -  return first; + +  Node *N = parseUnscopedName(State); +  if (N == nullptr) +    return nullptr; +  //        ::= <unscoped-template-name> <template-args> +  if (look() == 'I') { +    Subs.push_back(N); +    Node *TA = parseTemplateArgs(State != nullptr); +    if (TA == nullptr) +      return nullptr; +    if (State) State->EndsWithTemplateArgs = true; +    return make<NameWithTemplateArgs>(N, TA); +  } +  //        ::= <unscoped-name> +  return N;  } -// <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class -// member access (C++0x) -//             ::= DT <expression> E  # decltype of an expression (C++0x) +// <local-name> := Z <function encoding> E <entity name> [<discriminator>] +//              := Z <function encoding> E s [<discriminator>] +//              := Z <function encoding> Ed [ <parameter number> ] _ <entity name> +Node *Db::parseLocalName(NameState *State) { +  if (!consumeIf('Z')) +    return nullptr; +  Node *Encoding = parseEncoding(); +  if (Encoding == nullptr || !consumeIf('E')) +    return nullptr; -template <class C> -static const char *parse_decltype(const char *first, const char *last, C &db) { -  if (last - first >= 4 && first[0] == 'D') { -    switch (first[1]) { -    case 't': -    case 'T': { -      const char *t = parse_expression(first + 2, last, db); -      if (t != first + 2 && t != last && *t == 'E') { -        if (db.names.empty()) -          return first; -        db.names.back() = "decltype(" + db.names.back().move_full() + ")"; -        first = t + 1; -      } -    } break; -    } +  if (consumeIf('s')) { +    First = parse_discriminator(First, Last); +    return make<LocalName>(Encoding, make<NameType>("string literal"));    } -  return first; + +  if (consumeIf('d')) { +    parseNumber(true); +    if (!consumeIf('_')) +      return nullptr; +    Node *N = parseName(State); +    if (N == nullptr) +      return nullptr; +    return make<LocalName>(Encoding, N); +  } + +  Node *Entity = parseName(State); +  if (Entity == nullptr) +    return nullptr; +  First = parse_discriminator(First, Last); +  return make<LocalName>(Encoding, Entity);  } -// extension: -// <vector-type>           ::= Dv <positive dimension number> _ -//                                    <extended element type> -//                         ::= Dv [<dimension expression>] _ <element type> -// <extended element type> ::= <element type> -//                         ::= p # AltiVec vector pixel +// <unscoped-name> ::= <unqualified-name> +//                 ::= St <unqualified-name>   # ::std:: +// extension       ::= StL<unqualified-name> +Node *Db::parseUnscopedName(NameState *State) { + if (consumeIf("StL") || consumeIf("St")) { +   Node *R = parseUnqualifiedName(State); +   if (R == nullptr) +     return nullptr; +   return make<StdQualifiedName>(R); + } + return parseUnqualifiedName(State); +} -template <class C> -static const char *parse_vector_type(const char *first, const char *last, -                                     C &db) { -  if (last - first > 3 && first[0] == 'D' && first[1] == 'v') { -    if ('1' <= first[2] && first[2] <= '9') { -      const char *t = parse_number(first + 2, last); -      if (t == last || *t != '_') -        return first; -      const char *num = first + 2; -      size_t sz = static_cast<size_t>(t - num); -      if (++t != last) { -        if (*t != 'p') { -          const char *t1 = parse_type(t, last, db); -          if (t1 != t) { -            if (db.names.empty()) -              return first; -            db.names.back().first += " vector[" + std::string(num, sz) + "]"; -            first = t1; -          } -        } else { -          ++t; -          db.names.push_back("pixel vector[" + std::string(num, sz) + "]"); -          first = t; -        } -      } -    } else { -      std::string num; -      const char *t1 = first + 2; -      if (*t1 != '_') { -        const char *t = parse_expression(t1, last, db); -        if (t != t1) { -          if (db.names.empty()) -            return first; -          num = db.names.back().move_full(); -          db.names.pop_back(); -          t1 = t; -        } -      } -      if (t1 != last && *t1 == '_' && ++t1 != last) { -        const char *t = parse_type(t1, last, db); -        if (t != t1) { -          if (db.names.empty()) -            return first; -          db.names.back().first += " vector[" + num + "]"; -          first = t; -        } -      } -    } -  } -  return first; +// <unqualified-name> ::= <operator-name> [abi-tags] +//                    ::= <ctor-dtor-name> +//                    ::= <source-name> +//                    ::= <unnamed-type-name> +//                    ::= DC <source-name>+ E      # structured binding declaration +Node *Db::parseUnqualifiedName(NameState *State) { + // <ctor-dtor-name>s are special-cased in parseNestedName(). + Node *Result; + if (look() == 'U') +   Result = parseUnnamedTypeName(State); + else if (look() >= '1' && look() <= '9') +   Result = parseSourceName(State); + else if (consumeIf("DC")) { +   size_t BindingsBegin = Names.size(); +   do { +     Node *Binding = parseSourceName(State); +     if (Binding == nullptr) +       return nullptr; +     Names.push_back(Binding); +   } while (!consumeIf('E')); +   Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin)); + } else +   Result = parseOperatorName(State); + if (Result != nullptr) +   Result = parseAbiTags(Result); + return Result;  } -// <type> ::= <builtin-type> -//        ::= <function-type> -//        ::= <class-enum-type> -//        ::= <array-type> -//        ::= <pointer-to-member-type> -//        ::= <template-param> -//        ::= <template-template-param> <template-args> -//        ::= <decltype> -//        ::= <substitution> -//        ::= <CV-qualifiers> <type> -//        ::= P <type>        # pointer-to -//        ::= R <type>        # reference-to -//        ::= O <type>        # rvalue reference-to (C++0x) -//        ::= C <type>        # complex pair (C 2000) -//        ::= G <type>        # imaginary (C 2000) -//        ::= Dp <type>       # pack expansion (C++0x) -//        ::= U <source-name> <type>  # vendor extended type qualifier -// extension := U <objc-name> <objc-type>  # objc-type<identifier> -// extension := <vector-type> # <vector-type> starts with Dv - -// <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + -// <number of digits in k1> + k1 -// <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name> -// 11objc_object -> id<source-name> - -template <class C> -static const char *parse_type(const char *first, const char *last, C &db) { -  if (first != last) { -    switch (*first) { -    case 'r': -    case 'V': -    case 'K': { -      unsigned cv = 0; -      const char *t = parse_cv_qualifiers(first, last, cv); -      if (t != first) { -        bool is_function = *t == 'F'; -        size_t k0 = db.names.size(); -        const char *t1 = parse_type(t, last, db); -        size_t k1 = db.names.size(); -        if (t1 != t) { -          if (is_function) -            db.subs.pop_back(); -          db.subs.emplace_back(); -          for (size_t k = k0; k < k1; ++k) { -            if (is_function) { -              auto &name = db.names[k].second; -              size_t p = name.size(); - -              if (name[p - 2] == '&' && name[p - 1] == '&') -                p -= 2; -              else if (name.back() == '&') -                p -= 1; - -              if (cv & CV_const) { -                name.insert(p, " const"); -                p += 6; -              } -              if (cv & CV_volatile) { -                name.insert(p, " volatile"); -                p += 9; -              } -              if (cv & CV_restrict) -                name.insert(p, " restrict"); -            } else { -              if (cv & CV_const) -                db.names[k].first.append(" const"); -              if (cv & CV_volatile) -                db.names[k].first.append(" volatile"); -              if (cv & CV_restrict) -                db.names[k].first.append(" restrict"); -            } -            db.subs.back().push_back(db.names[k]); -          } -          first = t1; -        } -      } -    } break; -    default: { -      const char *t = parse_builtin_type(first, last, db); -      if (t != first) { -        first = t; -      } else { -        switch (*first) { -        case 'A': -          t = parse_array_type(first, last, db); -          if (t != first) { -            if (db.names.empty()) -              return first; -            first = t; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } -          break; -        case 'C': -          t = parse_type(first + 1, last, db); -          if (t != first + 1) { -            if (db.names.empty()) -              return first; -            db.names.back().first.append(" complex"); -            first = t; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } -          break; -        case 'F': -          t = parse_function_type(first, last, db); -          if (t != first) { -            if (db.names.empty()) -              return first; -            first = t; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } -          break; -        case 'G': -          t = parse_type(first + 1, last, db); -          if (t != first + 1) { -            if (db.names.empty()) -              return first; -            db.names.back().first.append(" imaginary"); -            first = t; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } -          break; -        case 'M': -          t = parse_pointer_to_member_type(first, last, db); -          if (t != first) { -            if (db.names.empty()) -              return first; -            first = t; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } -          break; -        case 'O': { -          size_t k0 = db.names.size(); -          t = parse_type(first + 1, last, db); -          size_t k1 = db.names.size(); -          if (t != first + 1) { -            db.subs.emplace_back(); -            for (size_t k = k0; k < k1; ++k) { -              if (db.names[k].second.substr(0, 2) == " [") { -                db.names[k].first += " ("; -                db.names[k].second.insert(0, ")"); -              } else if (!db.names[k].second.empty() && -                         db.names[k].second.front() == '(') { -                db.names[k].first += "("; -                db.names[k].second.insert(0, ")"); -              } -              db.names[k].first.append("&&"); -              db.subs.back().push_back(db.names[k]); -            } -            first = t; -          } -          break; -        } -        case 'P': { -          size_t k0 = db.names.size(); -          t = parse_type(first + 1, last, db); -          size_t k1 = db.names.size(); -          if (t != first + 1) { -            db.subs.emplace_back(); -            for (size_t k = k0; k < k1; ++k) { -              if (db.names[k].second.substr(0, 2) == " [") { -                db.names[k].first += " ("; -                db.names[k].second.insert(0, ")"); -              } else if (!db.names[k].second.empty() && -                         db.names[k].second.front() == '(') { -                db.names[k].first += "("; -                db.names[k].second.insert(0, ")"); -              } -              if (first[1] != 'U' || -                  db.names[k].first.substr(0, 12) != "objc_object<") { -                db.names[k].first.append("*"); -              } else { -                db.names[k].first.replace(0, 11, "id"); -              } -              db.subs.back().push_back(db.names[k]); -            } -            first = t; -          } -          break; -        } -        case 'R': { -          size_t k0 = db.names.size(); -          t = parse_type(first + 1, last, db); -          size_t k1 = db.names.size(); -          if (t != first + 1) { -            db.subs.emplace_back(); -            for (size_t k = k0; k < k1; ++k) { -              if (db.names[k].second.substr(0, 2) == " [") { -                db.names[k].first += " ("; -                db.names[k].second.insert(0, ")"); -              } else if (!db.names[k].second.empty() && -                         db.names[k].second.front() == '(') { -                db.names[k].first += "("; -                db.names[k].second.insert(0, ")"); -              } -              db.names[k].first.append("&"); -              db.subs.back().push_back(db.names[k]); -            } -            first = t; -          } -          break; -        } -        case 'T': { -          size_t k0 = db.names.size(); -          t = parse_template_param(first, last, db); -          size_t k1 = db.names.size(); -          if (t != first) { -            db.subs.emplace_back(); -            for (size_t k = k0; k < k1; ++k) -              db.subs.back().push_back(db.names[k]); -            if (db.try_to_parse_template_args && k1 == k0 + 1) { -              const char *t1 = parse_template_args(t, last, db); -              if (t1 != t) { -                auto args = db.names.back().move_full(); -                db.names.pop_back(); -                db.names.back().first += std::move(args); -                db.subs.push_back(typename C::sub_type(1, db.names.back())); -                t = t1; -              } -            } -            first = t; -          } -          break; -        } -        case 'U': -          if (first + 1 != last) { -            t = parse_source_name(first + 1, last, db); -            if (t != first + 1) { -              const char *t2 = parse_type(t, last, db); -              if (t2 != t) { -                if (db.names.size() < 2) -                  return first; -                auto type = db.names.back().move_full(); -                db.names.pop_back(); -                if (db.names.back().first.substr(0, 9) != "objcproto") { -                  db.names.back() = type + " " + db.names.back().move_full(); -                } else { -                  auto proto = db.names.back().move_full(); -                  db.names.pop_back(); -                  t = parse_source_name(proto.data() + 9, -                                        proto.data() + proto.size(), db); -                  if (t != proto.data() + 9) { -                    db.names.back() = -                        type + "<" + db.names.back().move_full() + ">"; -                  } else { -                    db.names.push_back(type + " " + proto); -                  } -                } -                db.subs.push_back(typename C::sub_type(1, db.names.back())); -                first = t2; -              } -            } -          } -          break; -        case 'S': -          if (first + 1 != last && first[1] == 't') { -            t = parse_name(first, last, db); -            if (t != first) { -              if (db.names.empty()) -                return first; -              db.subs.push_back(typename C::sub_type(1, db.names.back())); -              first = t; -            } -          } else { -            t = parse_substitution(first, last, db); -            if (t != first) { -              first = t; -              // Parsed a substitution.  If the substitution is a -              //  <template-param> it might be followed by <template-args>. -              t = parse_template_args(first, last, db); -              if (t != first) { -                if (db.names.size() < 2) -                  return first; -                auto template_args = db.names.back().move_full(); -                db.names.pop_back(); -                db.names.back().first += template_args; -                // Need to create substitution for <template-template-param> -                // <template-args> -                db.subs.push_back(typename C::sub_type(1, db.names.back())); -                first = t; -              } -            } -          } -          break; -        case 'D': -          if (first + 1 != last) { -            switch (first[1]) { -            case 'p': { -              size_t k0 = db.names.size(); -              t = parse_type(first + 2, last, db); -              size_t k1 = db.names.size(); -              if (t != first + 2) { -                db.subs.emplace_back(); -                for (size_t k = k0; k < k1; ++k) -                  db.subs.back().push_back(db.names[k]); -                first = t; -                return first; -              } -              break; -            } -            case 't': -            case 'T': -              t = parse_decltype(first, last, db); -              if (t != first) { -                if (db.names.empty()) -                  return first; -                db.subs.push_back(typename C::sub_type(1, db.names.back())); -                first = t; -                return first; -              } -              break; -            case 'v': -              t = parse_vector_type(first, last, db); -              if (t != first) { -                if (db.names.empty()) -                  return first; -                db.subs.push_back(typename C::sub_type(1, db.names.back())); -                first = t; -                return first; -              } -              break; -            } -          } -          LLVM_FALLTHROUGH; -        default: -          // must check for builtin-types before class-enum-types to avoid -          // ambiguities with operator-names -          t = parse_builtin_type(first, last, db); -          if (t != first) { -            first = t; -          } else { -            t = parse_name(first, last, db); -            if (t != first) { -              if (db.names.empty()) -                return first; -              db.subs.push_back(typename C::sub_type(1, db.names.back())); -              first = t; -            } -          } -          break; -        } -      } -      break; -    } +// <unnamed-type-name> ::= Ut [<nonnegative number>] _ +//                     ::= <closure-type-name> +// +// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _ +// +// <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters +Node *Db::parseUnnamedTypeName(NameState *) { +  if (consumeIf("Ut")) { +    StringView Count = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    return make<UnnamedTypeName>(Count); +  } +  if (consumeIf("Ul")) { +    NodeArray Params; +    SwapAndRestore<bool> SwapParams(ParsingLambdaParams, true); +    if (!consumeIf("vE")) { +      size_t ParamsBegin = Names.size(); +      do { +        Node *P = parseType(); +        if (P == nullptr) +          return nullptr; +        Names.push_back(P); +      } while (!consumeIf('E')); +      Params = popTrailingNodeArray(ParamsBegin);      } +    StringView Count = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    return make<ClosureTypeName>(Params, Count);    } -  return first; +  return nullptr; +} + +// <source-name> ::= <positive length number> <identifier> +Node *Db::parseSourceName(NameState *) { +  size_t Length = 0; +  if (parsePositiveInteger(&Length)) +    return nullptr; +  if (numLeft() < Length || Length == 0) +    return nullptr; +  StringView Name(First, First + Length); +  First += Length; +  if (Name.startsWith("_GLOBAL__N")) +    return make<NameType>("(anonymous namespace)"); +  return make<NameType>(Name);  } -//   <operator-name> -//                   ::= aa    # && +//   <operator-name> ::= aa    # &&  //                   ::= ad    # & (unary)  //                   ::= an    # &  //                   ::= aN    # &= @@ -2024,1783 +2329,2047 @@ static const char *parse_type(const char *first, const char *last, C &db) {  //                   ::= rM    # %=  //                   ::= rs    # >>  //                   ::= rS    # >>= -//                   ::= v <digit> <source-name>        # vendor extended -//                   operator - -template <class C> -static const char *parse_operator_name(const char *first, const char *last, -                                       C &db) { -  if (last - first >= 2) { -    switch (first[0]) { +//                   ::= ss    # <=> C++2a +//                   ::= v <digit> <source-name>        # vendor extended operator +Node *Db::parseOperatorName(NameState *State) { +  switch (look()) { +  case 'a': +    switch (look(1)) {      case 'a': -      switch (first[1]) { -      case 'a': -        db.names.push_back("operator&&"); -        first += 2; -        break; -      case 'd': -      case 'n': -        db.names.push_back("operator&"); -        first += 2; -        break; -      case 'N': -        db.names.push_back("operator&="); -        first += 2; -        break; -      case 'S': -        db.names.push_back("operator="); -        first += 2; -        break; -      } -      break; -    case 'c': -      switch (first[1]) { -      case 'l': -        db.names.push_back("operator()"); -        first += 2; -        break; -      case 'm': -        db.names.push_back("operator,"); -        first += 2; -        break; -      case 'o': -        db.names.push_back("operator~"); -        first += 2; -        break; -      case 'v': { -        bool try_to_parse_template_args = db.try_to_parse_template_args; -        db.try_to_parse_template_args = false; -        const char *t = parse_type(first + 2, last, db); -        db.try_to_parse_template_args = try_to_parse_template_args; -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "operator "); -          db.parsed_ctor_dtor_cv = true; -          first = t; -        } -      } break; -      } -      break; +      First += 2; +      return make<NameType>("operator&&");      case 'd': -      switch (first[1]) { -      case 'a': -        db.names.push_back("operator delete[]"); -        first += 2; -        break; -      case 'e': -        db.names.push_back("operator*"); -        first += 2; -        break; -      case 'l': -        db.names.push_back("operator delete"); -        first += 2; -        break; -      case 'v': -        db.names.push_back("operator/"); -        first += 2; -        break; -      case 'V': -        db.names.push_back("operator/="); -        first += 2; -        break; -      } -      break; +    case 'n': +      First += 2; +      return make<NameType>("operator&"); +    case 'N': +      First += 2; +      return make<NameType>("operator&="); +    case 'S': +      First += 2; +      return make<NameType>("operator="); +    } +    return nullptr; +  case 'c': +    switch (look(1)) { +    case 'l': +      First += 2; +      return make<NameType>("operator()"); +    case 'm': +      First += 2; +      return make<NameType>("operator,"); +    case 'o': +      First += 2; +      return make<NameType>("operator~"); +    //                   ::= cv <type>    # (cast) +    case 'v': { +      First += 2; +      SwapAndRestore<bool> SaveTemplate(TryToParseTemplateArgs, false); +      // If we're parsing an encoding, State != nullptr and the conversion +      // operators' <type> could have a <template-param> that refers to some +      // <template-arg>s further ahead in the mangled name. +      SwapAndRestore<bool> SavePermit(PermitForwardTemplateReferences, +                                      PermitForwardTemplateReferences || +                                          State != nullptr); +      Node* Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      if (State) State->CtorDtorConversion = true; +      return make<ConversionOperatorType>(Ty); +    } +    } +    return nullptr; +  case 'd': +    switch (look(1)) { +    case 'a': +      First += 2; +      return make<NameType>("operator delete[]");      case 'e': -      switch (first[1]) { -      case 'o': -        db.names.push_back("operator^"); -        first += 2; -        break; -      case 'O': -        db.names.push_back("operator^="); -        first += 2; -        break; -      case 'q': -        db.names.push_back("operator=="); -        first += 2; -        break; -      } -      break; -    case 'g': -      switch (first[1]) { -      case 'e': -        db.names.push_back("operator>="); -        first += 2; -        break; -      case 't': -        db.names.push_back("operator>"); -        first += 2; -        break; -      } -      break; +      First += 2; +      return make<NameType>("operator*"); +    case 'l': +      First += 2; +      return make<NameType>("operator delete"); +    case 'v': +      First += 2; +      return make<NameType>("operator/"); +    case 'V': +      First += 2; +      return make<NameType>("operator/="); +    } +    return nullptr; +  case 'e': +    switch (look(1)) { +    case 'o': +      First += 2; +      return make<NameType>("operator^"); +    case 'O': +      First += 2; +      return make<NameType>("operator^="); +    case 'q': +      First += 2; +      return make<NameType>("operator=="); +    } +    return nullptr; +  case 'g': +    switch (look(1)) { +    case 'e': +      First += 2; +      return make<NameType>("operator>="); +    case 't': +      First += 2; +      return make<NameType>("operator>"); +    } +    return nullptr; +  case 'i': +    if (look(1) == 'x') { +      First += 2; +      return make<NameType>("operator[]"); +    } +    return nullptr; +  case 'l': +    switch (look(1)) { +    case 'e': +      First += 2; +      return make<NameType>("operator<="); +    //                   ::= li <source-name>  # operator "" +    case 'i': { +      First += 2; +      Node *SN = parseSourceName(State); +      if (SN == nullptr) +        return nullptr; +      return make<LiteralOperator>(SN); +    } +    case 's': +      First += 2; +      return make<NameType>("operator<<"); +    case 'S': +      First += 2; +      return make<NameType>("operator<<="); +    case 't': +      First += 2; +      return make<NameType>("operator<"); +    } +    return nullptr; +  case 'm': +    switch (look(1)) {      case 'i': -      if (first[1] == 'x') { -        db.names.push_back("operator[]"); -        first += 2; -      } -      break; +      First += 2; +      return make<NameType>("operator-"); +    case 'I': +      First += 2; +      return make<NameType>("operator-=");      case 'l': -      switch (first[1]) { -      case 'e': -        db.names.push_back("operator<="); -        first += 2; -        break; -      case 'i': { -        const char *t = parse_source_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "operator\"\" "); -          first = t; -        } -      } break; -      case 's': -        db.names.push_back("operator<<"); -        first += 2; -        break; -      case 'S': -        db.names.push_back("operator<<="); -        first += 2; -        break; -      case 't': -        db.names.push_back("operator<"); -        first += 2; -        break; -      } -      break; +      First += 2; +      return make<NameType>("operator*"); +    case 'L': +      First += 2; +      return make<NameType>("operator*=");      case 'm': -      switch (first[1]) { -      case 'i': -        db.names.push_back("operator-"); -        first += 2; -        break; -      case 'I': -        db.names.push_back("operator-="); -        first += 2; -        break; -      case 'l': -        db.names.push_back("operator*"); -        first += 2; -        break; -      case 'L': -        db.names.push_back("operator*="); -        first += 2; -        break; -      case 'm': -        db.names.push_back("operator--"); -        first += 2; -        break; -      } -      break; -    case 'n': -      switch (first[1]) { -      case 'a': -        db.names.push_back("operator new[]"); -        first += 2; -        break; -      case 'e': -        db.names.push_back("operator!="); -        first += 2; -        break; -      case 'g': -        db.names.push_back("operator-"); -        first += 2; -        break; -      case 't': -        db.names.push_back("operator!"); -        first += 2; -        break; -      case 'w': -        db.names.push_back("operator new"); -        first += 2; -        break; -      } -      break; +      First += 2; +      return make<NameType>("operator--"); +    } +    return nullptr; +  case 'n': +    switch (look(1)) { +    case 'a': +      First += 2; +      return make<NameType>("operator new[]"); +    case 'e': +      First += 2; +      return make<NameType>("operator!="); +    case 'g': +      First += 2; +      return make<NameType>("operator-"); +    case 't': +      First += 2; +      return make<NameType>("operator!"); +    case 'w': +      First += 2; +      return make<NameType>("operator new"); +    } +    return nullptr; +  case 'o': +    switch (look(1)) {      case 'o': -      switch (first[1]) { -      case 'o': -        db.names.push_back("operator||"); -        first += 2; -        break; -      case 'r': -        db.names.push_back("operator|"); -        first += 2; -        break; -      case 'R': -        db.names.push_back("operator|="); -        first += 2; -        break; -      } -      break; -    case 'p': -      switch (first[1]) { -      case 'm': -        db.names.push_back("operator->*"); -        first += 2; -        break; -      case 'l': -        db.names.push_back("operator+"); -        first += 2; -        break; -      case 'L': -        db.names.push_back("operator+="); -        first += 2; -        break; -      case 'p': -        db.names.push_back("operator++"); -        first += 2; -        break; -      case 's': -        db.names.push_back("operator+"); -        first += 2; -        break; -      case 't': -        db.names.push_back("operator->"); -        first += 2; -        break; -      } -      break; -    case 'q': -      if (first[1] == 'u') { -        db.names.push_back("operator?"); -        first += 2; -      } -      break; +      First += 2; +      return make<NameType>("operator||");      case 'r': -      switch (first[1]) { -      case 'm': -        db.names.push_back("operator%"); -        first += 2; -        break; -      case 'M': -        db.names.push_back("operator%="); -        first += 2; -        break; -      case 's': -        db.names.push_back("operator>>"); -        first += 2; -        break; -      case 'S': -        db.names.push_back("operator>>="); -        first += 2; -        break; -      } -      break; -    case 'v': -      if (std::isdigit(first[1])) { -        const char *t = parse_source_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "operator "); -          first = t; -        } -      } -      break; +      First += 2; +      return make<NameType>("operator|"); +    case 'R': +      First += 2; +      return make<NameType>("operator|=");      } -  } -  return first; -} - -template <class C> -static const char *parse_integer_literal(const char *first, const char *last, -                                         const std::string &lit, C &db) { -  const char *t = parse_number(first, last); -  if (t != first && t != last && *t == 'E') { -    if (lit.size() > 3) -      db.names.push_back("(" + lit + ")"); -    else -      db.names.emplace_back(); -    if (*first == 'n') { -      db.names.back().first += '-'; -      ++first; +    return nullptr; +  case 'p': +    switch (look(1)) { +    case 'm': +      First += 2; +      return make<NameType>("operator->*"); +    case 'l': +      First += 2; +      return make<NameType>("operator+"); +    case 'L': +      First += 2; +      return make<NameType>("operator+="); +    case 'p': +      First += 2; +      return make<NameType>("operator++"); +    case 's': +      First += 2; +      return make<NameType>("operator+"); +    case 't': +      First += 2; +      return make<NameType>("operator->"); +    } +    return nullptr; +  case 'q': +    if (look(1) == 'u') { +      First += 2; +      return make<NameType>("operator?"); +    } +    return nullptr; +  case 'r': +    switch (look(1)) { +    case 'm': +      First += 2; +      return make<NameType>("operator%"); +    case 'M': +      First += 2; +      return make<NameType>("operator%="); +    case 's': +      First += 2; +      return make<NameType>("operator>>"); +    case 'S': +      First += 2; +      return make<NameType>("operator>>="); +    } +    return nullptr; +  case 's': +    if (look(1) == 's') { +      First += 2; +      return make<NameType>("operator<=>");      } -    db.names.back().first.append(first, t); -    if (lit.size() <= 3) -      db.names.back().first += lit; -    first = t + 1; +    return nullptr; +  // ::= v <digit> <source-name>        # vendor extended operator +  case 'v': +    if (std::isdigit(look(1))) { +      First += 2; +      Node *SN = parseSourceName(State); +      if (SN == nullptr) +        return nullptr; +      return make<ConversionOperatorType>(SN); +    } +    return nullptr;    } -  return first; +  return nullptr;  } -// <expr-primary> ::= L <type> <value number> E                          # -// integer literal -//                ::= L <type> <value float> E                           # -//                floating literal -//                ::= L <string type> E                                  # -//                string literal -//                ::= L <nullptr type> E                                 # -//                nullptr literal (i.e., "LDnE") -//                ::= L <type> <real-part float> _ <imag-part float> E   # -//                complex floating point literal (C 2000) -//                ::= L <mangled-name> E                                 # -//                external name - -template <class C> -static const char *parse_expr_primary(const char *first, const char *last, -                                      C &db) { -  if (last - first >= 4 && *first == 'L') { -    switch (first[1]) { -    case 'w': { -      const char *t = parse_integer_literal(first + 2, last, "wchar_t", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'b': -      if (first[3] == 'E') { -        switch (first[2]) { -        case '0': -          db.names.push_back("false"); -          first += 4; -          break; -        case '1': -          db.names.push_back("true"); -          first += 4; -          break; -        } -      } -      break; -    case 'c': { -      const char *t = parse_integer_literal(first + 2, last, "char", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'a': { -      const char *t = parse_integer_literal(first + 2, last, "signed char", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'h': { -      const char *t = -          parse_integer_literal(first + 2, last, "unsigned char", db); -      if (t != first + 2) -        first = t; -    } break; -    case 's': { -      const char *t = parse_integer_literal(first + 2, last, "short", db); -      if (t != first + 2) -        first = t; -    } break; -    case 't': { -      const char *t = -          parse_integer_literal(first + 2, last, "unsigned short", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'i': { -      const char *t = parse_integer_literal(first + 2, last, "", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'j': { -      const char *t = parse_integer_literal(first + 2, last, "u", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'l': { -      const char *t = parse_integer_literal(first + 2, last, "l", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'm': { -      const char *t = parse_integer_literal(first + 2, last, "ul", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'x': { -      const char *t = parse_integer_literal(first + 2, last, "ll", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'y': { -      const char *t = parse_integer_literal(first + 2, last, "ull", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'n': { -      const char *t = parse_integer_literal(first + 2, last, "__int128", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'o': { -      const char *t = -          parse_integer_literal(first + 2, last, "unsigned __int128", db); -      if (t != first + 2) -        first = t; -    } break; -    case 'f': { -      const char *t = parse_floating_number<float>(first + 2, last, db); -      if (t != first + 2) -        first = t; -    } break; -    case 'd': { -      const char *t = parse_floating_number<double>(first + 2, last, db); -      if (t != first + 2) -        first = t; -    } break; -    case 'e': { -      const char *t = parse_floating_number<long double>(first + 2, last, db); -      if (t != first + 2) -        first = t; -    } break; -    case '_': -      if (first[2] == 'Z') { -        const char *t = parse_encoding(first + 3, last, db); -        if (t != first + 3 && t != last && *t == 'E') -          first = t + 1; -      } -      break; -    case 'T': -      // Invalid mangled name per -      //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html +// <ctor-dtor-name> ::= C1  # complete object constructor +//                  ::= C2  # base object constructor +//                  ::= C3  # complete object allocating constructor +//   extension      ::= C5    # ? +//                  ::= D0  # deleting destructor +//                  ::= D1  # complete object destructor +//                  ::= D2  # base object destructor +//   extension      ::= D5    # ? +Node *Db::parseCtorDtorName(Node *&SoFar, NameState *State) { +  if (SoFar->K == Node::KSpecialSubstitution) { +    auto SSK = static_cast<SpecialSubstitution *>(SoFar)->SSK; +    switch (SSK) { +    case SpecialSubKind::string: +    case SpecialSubKind::istream: +    case SpecialSubKind::ostream: +    case SpecialSubKind::iostream: +      SoFar = make<ExpandedSpecialSubstitution>(SSK); +    default:        break; -    default: { -      // might be named type -      const char *t = parse_type(first + 1, last, db); -      if (t != first + 1 && t != last) { -        if (*t != 'E') { -          const char *n = t; -          for (; n != last && isdigit(*n); ++n) -            ; -          if (n != t && n != last && *n == 'E') { -            if (db.names.empty()) -              return first; -            db.names.back() = -                "(" + db.names.back().move_full() + ")" + std::string(t, n); -            first = n + 1; -            break; -          } -        } else { -          first = t + 1; -          break; -        } -      }      } +  } + +  if (consumeIf('C')) { +    bool IsInherited = consumeIf('I'); +    if (look() != '1' && look() != '2' && look() != '3' && look() != '5') +      return nullptr; +    ++First; +    if (State) State->CtorDtorConversion = true; +    if (IsInherited) { +      if (parseName(State) == nullptr) +        return nullptr;      } +    return make<CtorDtorName>(SoFar, false);    } -  return first; + +  if (look() == 'D' && +      (look(1) == '0' || look(1) == '1' || look(1) == '2' || look(1) == '5')) { +    First += 2; +    if (State) State->CtorDtorConversion = true; +    return make<CtorDtorName>(SoFar, true); +  } + +  return nullptr;  } -static std::string base_name(std::string &s) { -  if (s.empty()) -    return s; -  if (s == "std::string") { -    s = "std::basic_string<char, std::char_traits<char>, std::allocator<char> " -        ">"; -    return "basic_string"; -  } -  if (s == "std::istream") { -    s = "std::basic_istream<char, std::char_traits<char> >"; -    return "basic_istream"; -  } -  if (s == "std::ostream") { -    s = "std::basic_ostream<char, std::char_traits<char> >"; -    return "basic_ostream"; -  } -  if (s == "std::iostream") { -    s = "std::basic_iostream<char, std::char_traits<char> >"; -    return "basic_iostream"; -  } -  const char *const pf = s.data(); -  const char *pe = pf + s.size(); -  if (pe[-1] == '>') { -    unsigned c = 1; -    while (true) { -      if (--pe == pf) -        return std::string(); -      if (pe[-1] == '<') { -        if (--c == 0) { -          --pe; -          break; -        } -      } else if (pe[-1] == '>') -        ++c; +// <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E +//               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E +// +// <prefix> ::= <prefix> <unqualified-name> +//          ::= <template-prefix> <template-args> +//          ::= <template-param> +//          ::= <decltype> +//          ::= # empty +//          ::= <substitution> +//          ::= <prefix> <data-member-prefix> +//  extension ::= L +// +// <data-member-prefix> := <member source-name> [<template-args>] M +// +// <template-prefix> ::= <prefix> <template unqualified-name> +//                   ::= <template-param> +//                   ::= <substitution> +Node *Db::parseNestedName(NameState *State) { +  if (!consumeIf('N')) +    return nullptr; + +  Qualifiers CVTmp = parseCVQualifiers(); +  if (State) State->CVQualifiers = CVTmp; + +  if (consumeIf('O')) { +    if (State) State->ReferenceQualifier = FrefQualRValue; +  } else if (consumeIf('R')) { +    if (State) State->ReferenceQualifier = FrefQualLValue; +  } else +    if (State) State->ReferenceQualifier = FrefQualNone; + +  Node *SoFar = nullptr; +  auto PushComponent = [&](Node *Comp) { +    if (SoFar) SoFar = make<NestedName>(SoFar, Comp); +    else       SoFar = Comp; +    if (State) State->EndsWithTemplateArgs = false; +  }; + +  if (consumeIf("St")) +    SoFar = make<NameType>("std"); + +  while (!consumeIf('E')) { +    consumeIf('L'); // extension + +    // <data-member-prefix> := <member source-name> [<template-args>] M +    if (consumeIf('M')) { +      if (SoFar == nullptr) +        return nullptr; +      continue;      } -  } -  if (pe - pf <= 1) -    return std::string(); -  const char *p0 = pe - 1; -  for (; p0 != pf; --p0) { -    if (*p0 == ':') { -      ++p0; -      break; + +    //          ::= <template-param> +    if (look() == 'T') { +      Node *TP = parseTemplateParam(); +      if (TP == nullptr) +        return nullptr; +      PushComponent(TP); +      Subs.push_back(SoFar); +      continue;      } -    if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_') { -      return std::string(); + +    //          ::= <template-prefix> <template-args> +    if (look() == 'I') { +      Node *TA = parseTemplateArgs(State != nullptr); +      if (TA == nullptr || SoFar == nullptr) +        return nullptr; +      SoFar = make<NameWithTemplateArgs>(SoFar, TA); +      if (State) State->EndsWithTemplateArgs = true; +      Subs.push_back(SoFar); +      continue;      } -  } -  return std::string(p0, pe); -} -// <ctor-dtor-name> ::= C1    # complete object constructor -//                  ::= C2    # base object constructor -//                  ::= C3    # complete object allocating constructor -//   extension      ::= C5    # ? -//                  ::= D0    # deleting destructor -//                  ::= D1    # complete object destructor -//                  ::= D2    # base object destructor -//   extension      ::= D5    # ? +    //          ::= <decltype> +    if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) { +      Node *DT = parseDecltype(); +      if (DT == nullptr) +        return nullptr; +      PushComponent(DT); +      Subs.push_back(SoFar); +      continue; +    } -template <class C> -static const char *parse_ctor_dtor_name(const char *first, const char *last, -                                        C &db) { -  if (last - first >= 2 && !db.names.empty()) { -    switch (first[0]) { -    case 'C': -      switch (first[1]) { -      case '1': -      case '2': -      case '3': -      case '5': -        if (db.names.empty()) -          return first; -        db.names.push_back(base_name(db.names.back().first)); -        first += 2; -        db.parsed_ctor_dtor_cv = true; -        break; -      } -      break; -    case 'D': -      switch (first[1]) { -      case '0': -      case '1': -      case '2': -      case '5': -        if (db.names.empty()) -          return first; -        db.names.push_back("~" + base_name(db.names.back().first)); -        first += 2; -        db.parsed_ctor_dtor_cv = true; -        break; -      } -      break; +    //          ::= <substitution> +    if (look() == 'S' && look(1) != 't') { +      Node *S = parseSubstitution(); +      if (S == nullptr) +        return nullptr; +      PushComponent(S); +      if (SoFar != S) +        Subs.push_back(S); +      continue; +    } + +    // Parse an <unqualified-name> thats actually a <ctor-dtor-name>. +    if (look() == 'C' || (look() == 'D' && look(1) != 'C')) { +      if (SoFar == nullptr) +        return nullptr; +      Node *CtorDtor = parseCtorDtorName(SoFar, State); +      if (CtorDtor == nullptr) +        return nullptr; +      PushComponent(CtorDtor); +      SoFar = parseAbiTags(SoFar); +      if (SoFar == nullptr) +        return nullptr; +      Subs.push_back(SoFar); +      continue;      } + +    //          ::= <prefix> <unqualified-name> +    Node *N = parseUnqualifiedName(State); +    if (N == nullptr) +      return nullptr; +    PushComponent(N); +    Subs.push_back(SoFar);    } -  return first; + +  if (SoFar == nullptr || Subs.empty()) +    return nullptr; + +  Subs.pop_back(); +  return SoFar;  } -// <unnamed-type-name> ::= Ut [ <nonnegative number> ] _ -//                     ::= <closure-type-name> -// -// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _ -// -// <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda -// has no parameters - -template <class C> -static const char *parse_unnamed_type_name(const char *first, const char *last, -                                           C &db) { -  if (last - first > 2 && first[0] == 'U') { -    char type = first[1]; -    switch (type) { -    case 't': { -      db.names.push_back(std::string("'unnamed")); -      const char *t0 = first + 2; -      if (t0 == last) { -        db.names.pop_back(); -        return first; -      } -      if (std::isdigit(*t0)) { -        const char *t1 = t0 + 1; -        while (t1 != last && std::isdigit(*t1)) -          ++t1; -        db.names.back().first.append(t0, t1); -        t0 = t1; -      } -      db.names.back().first.push_back('\''); -      if (t0 == last || *t0 != '_') { -        db.names.pop_back(); -        return first; -      } -      first = t0 + 1; -    } break; -    case 'l': { -      size_t lambda_pos = db.names.size(); -      db.names.push_back(std::string("'lambda'(")); -      const char *t0 = first + 2; -      if (first[2] == 'v') { -        db.names.back().first += ')'; -        ++t0; -      } else { -        bool is_first_it = true; -        while (true) { -          long k0 = static_cast<long>(db.names.size()); -          const char *t1 = parse_type(t0, last, db); -          long k1 = static_cast<long>(db.names.size()); -          if (t1 == t0) -            break; -          if (k0 >= k1) -            return first; -          // If the call to parse_type above found a pack expansion -          // substitution, then multiple names could have been -          // inserted into the name table. Walk through the names, -          // appending each onto the lambda's parameter list. -          std::for_each(db.names.begin() + k0, db.names.begin() + k1, -                        [&](typename C::sub_type::value_type &pair) { -                          if (pair.empty()) -                            return; -                          auto &lambda = db.names[lambda_pos].first; -                          if (!is_first_it) -                            lambda.append(", "); -                          is_first_it = false; -                          lambda.append(pair.move_full()); -                        }); -          db.names.erase(db.names.begin() + k0, db.names.end()); -          t0 = t1; -        } -        if (is_first_it) { -          if (!db.names.empty()) -            db.names.pop_back(); -          return first; -        } -        if (db.names.empty() || db.names.size() - 1 != lambda_pos) -          return first; -        db.names.back().first.append(")"); -      } -      if (t0 == last || *t0 != 'E') { -        if (!db.names.empty()) -          db.names.pop_back(); -        return first; -      } -      ++t0; -      if (t0 == last) { -        if (!db.names.empty()) -          db.names.pop_back(); -        return first; -      } -      if (std::isdigit(*t0)) { -        const char *t1 = t0 + 1; -        while (t1 != last && std::isdigit(*t1)) -          ++t1; -        db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1); -        t0 = t1; -      } -      if (t0 == last || *t0 != '_') { -        if (!db.names.empty()) -          db.names.pop_back(); -        return first; -      } -      first = t0 + 1; -    } break; -    } +// <simple-id> ::= <source-name> [ <template-args> ] +Node *Db::parseSimpleId() { +  Node *SN = parseSourceName(/*NameState=*/nullptr); +  if (SN == nullptr) +    return nullptr; +  if (look() == 'I') { +    Node *TA = parseTemplateArgs(); +    if (TA == nullptr) +      return nullptr; +    return make<NameWithTemplateArgs>(SN, TA);    } -  return first; +  return SN;  } -// <unqualified-name> ::= <operator-name> -//                    ::= <ctor-dtor-name> -//                    ::= <source-name> -//                    ::= <unnamed-type-name> +// <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f()) +//                   ::= <simple-id>        # e.g., ~A<2*N> +Node *Db::parseDestructorName() { +  Node *Result; +  if (std::isdigit(look())) +    Result = parseSimpleId(); +  else +    Result = parseUnresolvedType(); +  if (Result == nullptr) +    return nullptr; +  return make<DtorName>(Result); +} -template <class C> -static const char *parse_unqualified_name(const char *first, const char *last, -                                          C &db) { -  if (first != last) { -    const char *t; -    switch (*first) { -    case 'C': -    case 'D': -      t = parse_ctor_dtor_name(first, last, db); -      if (t != first) -        first = t; -      break; -    case 'U': -      t = parse_unnamed_type_name(first, last, db); -      if (t != first) -        first = t; -      break; -    case '1': -    case '2': -    case '3': -    case '4': -    case '5': -    case '6': -    case '7': -    case '8': -    case '9': -      t = parse_source_name(first, last, db); -      if (t != first) -        first = t; -      break; -    default: -      t = parse_operator_name(first, last, db); -      if (t != first) -        first = t; -      break; -    }; +// <unresolved-type> ::= <template-param> +//                   ::= <decltype> +//                   ::= <substitution> +Node *Db::parseUnresolvedType() { +  if (look() == 'T') { +    Node *TP = parseTemplateParam(); +    if (TP == nullptr) +      return nullptr; +    Subs.push_back(TP); +    return TP;    } -  return first; +  if (look() == 'D') { +    Node *DT = parseDecltype(); +    if (DT == nullptr) +      return nullptr; +    Subs.push_back(DT); +    return DT; +  } +  return parseSubstitution();  } -// <unscoped-name> ::= <unqualified-name> -//                 ::= St <unqualified-name>   # ::std:: -// extension       ::= StL<unqualified-name> +// <base-unresolved-name> ::= <simple-id>                                # unresolved name +//          extension     ::= <operator-name>                            # unresolved operator-function-id +//          extension     ::= <operator-name> <template-args>            # unresolved operator template-id +//                        ::= on <operator-name>                         # unresolved operator-function-id +//                        ::= on <operator-name> <template-args>         # unresolved operator template-id +//                        ::= dn <destructor-name>                       # destructor or pseudo-destructor; +//                                                                         # e.g. ~X or ~X<N-1> +Node *Db::parseBaseUnresolvedName() { +  if (std::isdigit(look())) +    return parseSimpleId(); -template <class C> -static const char *parse_unscoped_name(const char *first, const char *last, -                                       C &db) { -  if (last - first >= 2) { -    const char *t0 = first; -    bool St = false; -    if (first[0] == 'S' && first[1] == 't') { -      t0 += 2; -      St = true; -      if (t0 != last && *t0 == 'L') -        ++t0; -    } -    const char *t1 = parse_unqualified_name(t0, last, db); -    if (t1 != t0) { -      if (St) { -        if (db.names.empty()) -          return first; -        db.names.back().first.insert(0, "std::"); -      } -      first = t1; -    } +  if (consumeIf("dn")) +    return parseDestructorName(); + +  consumeIf("on"); + +  Node *Oper = parseOperatorName(/*NameState=*/nullptr); +  if (Oper == nullptr) +    return nullptr; +  if (look() == 'I') { +    Node *TA = parseTemplateArgs(); +    if (TA == nullptr) +      return nullptr; +    return make<NameWithTemplateArgs>(Oper, TA);    } -  return first; +  return Oper;  } -// at <type>                                            # alignof (a type) +// <unresolved-name> +//  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name> +//                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x +//                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name> +//                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::" +//                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x +//  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name> +//                                                                       # T::N::x /decltype(p)::N::x +//  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name> +// +// <unresolved-qualifier-level> ::= <simple-id> +Node *Db::parseUnresolvedName() { +  Node *SoFar = nullptr; + +  // srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name> +  // srN <unresolved-type>                   <unresolved-qualifier-level>+ E <base-unresolved-name> +  if (consumeIf("srN")) { +    SoFar = parseUnresolvedType(); +    if (SoFar == nullptr) +      return nullptr; + +    if (look() == 'I') { +      Node *TA = parseTemplateArgs(); +      if (TA == nullptr) +        return nullptr; +      SoFar = make<NameWithTemplateArgs>(SoFar, TA); +    } -template <class C> -static const char *parse_alignof_type(const char *first, const char *last, -                                      C &db) { -  if (last - first >= 3 && first[0] == 'a' && first[1] == 't') { -    const char *t = parse_type(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back().first = "alignof (" + db.names.back().move_full() + ")"; -      first = t; +    while (!consumeIf('E')) { +      Node *Qual = parseSimpleId(); +      if (Qual == nullptr) +        return nullptr; +      SoFar = make<QualifiedName>(SoFar, Qual);      } + +    Node *Base = parseBaseUnresolvedName(); +    if (Base == nullptr) +      return nullptr; +    return make<QualifiedName>(SoFar, Base);    } -  return first; -} -// az <expression>                                            # alignof (a -// expression) +  bool Global = consumeIf("gs"); -template <class C> -static const char *parse_alignof_expr(const char *first, const char *last, -                                      C &db) { -  if (last - first >= 3 && first[0] == 'a' && first[1] == 'z') { -    const char *t = parse_expression(first + 2, last, db); -    if (t != first + 2) { -      if (db.names.empty()) -        return first; -      db.names.back().first = "alignof (" + db.names.back().move_full() + ")"; -      first = t; +  // [gs] <base-unresolved-name>                     # x or (with "gs") ::x +  if (!consumeIf("sr")) { +    SoFar = parseBaseUnresolvedName(); +    if (SoFar == nullptr) +      return nullptr; +    if (Global) +      SoFar = make<GlobalQualifiedName>(SoFar); +    return SoFar; +  } + +  // [gs] sr <unresolved-qualifier-level>+ E   <base-unresolved-name> +  if (std::isdigit(look())) { +    do { +      Node *Qual = parseSimpleId(); +      if (Qual == nullptr) +        return nullptr; +      if (SoFar) +        SoFar = make<QualifiedName>(SoFar, Qual); +      else if (Global) +        SoFar = make<GlobalQualifiedName>(Qual); +      else +        SoFar = Qual; +    } while (!consumeIf('E')); +  } +  //      sr <unresolved-type>                 <base-unresolved-name> +  //      sr <unresolved-type> <template-args> <base-unresolved-name> +  else { +    SoFar = parseUnresolvedType(); +    if (SoFar == nullptr) +      return nullptr; + +    if (look() == 'I') { +      Node *TA = parseTemplateArgs(); +      if (TA == nullptr) +        return nullptr; +      SoFar = make<NameWithTemplateArgs>(SoFar, TA);      }    } -  return first; + +  assert(SoFar != nullptr); + +  Node *Base = parseBaseUnresolvedName(); +  if (Base == nullptr) +    return nullptr; +  return make<QualifiedName>(SoFar, Base);  } -template <class C> -static const char *parse_noexcept_expression(const char *first, -                                             const char *last, C &db) { -  const char *t1 = parse_expression(first, last, db); -  if (t1 != first) { -    if (db.names.empty()) -      return first; -    db.names.back().first = "noexcept (" + db.names.back().move_full() + ")"; -    first = t1; -  } -  return first; +// <abi-tags> ::= <abi-tag> [<abi-tags>] +// <abi-tag> ::= B <source-name> +Node *Db::parseAbiTags(Node *N) { +  while (consumeIf('B')) { +    StringView SN = parseBareSourceName(); +    if (SN.empty()) +      return nullptr; +    N = make<AbiTagAttr>(N, SN); +  } +  return N;  } -template <class C> -static const char *parse_prefix_expression(const char *first, const char *last, -                                           const std::string &op, -                                           C &db) { -  const char *t1 = parse_expression(first, last, db); -  if (t1 != first) { -    if (db.names.empty()) -      return first; -    db.names.back().first = op + "(" + db.names.back().move_full() + ")"; -    first = t1; -  } -  return first; +// <number> ::= [n] <non-negative decimal integer> +StringView Db::parseNumber(bool AllowNegative) { +  const char *Tmp = First; +  if (AllowNegative) +    consumeIf('n'); +  if (numLeft() == 0 || !std::isdigit(*First)) +    return StringView(); +  while (numLeft() != 0 && std::isdigit(*First)) +    ++First; +  return StringView(Tmp, First);  } -template <class C> -static const char *parse_binary_expression(const char *first, const char *last, -                                           const std::string &op, -                                           C &db) { -  const char *t1 = parse_expression(first, last, db); -  if (t1 != first) { -    const char *t2 = parse_expression(t1, last, db); -    if (t2 != t1) { -      if (db.names.size() < 2) -        return first; -      auto op2 = db.names.back().move_full(); -      db.names.pop_back(); -      auto op1 = db.names.back().move_full(); -      auto &nm = db.names.back().first; -      nm.clear(); -      if (op == ">") -        nm += '('; -      nm += "(" + op1 + ") " + op + " (" + op2 + ")"; -      if (op == ">") -        nm += ')'; -      first = t2; -    } else if (!db.names.empty()) -      db.names.pop_back(); -  } -  return first; +// <positive length number> ::= [0-9]* +bool Db::parsePositiveInteger(size_t *Out) { +  *Out = 0; +  if (look() < '0' || look() > '9') +    return true; +  while (look() >= '0' && look() <= '9') { +    *Out *= 10; +    *Out += static_cast<size_t>(consume() - '0'); +  } +  return false;  } -// <expression> ::= <unary operator-name> <expression> -//              ::= <binary operator-name> <expression> <expression> -//              ::= <ternary operator-name> <expression> <expression> -//              <expression> -//              ::= cl <expression>+ E                                   # call -//              ::= cv <type> <expression>                               # -//              conversion with one argument -//              ::= cv <type> _ <expression>* E                          # -//              conversion with a different number of arguments -//              ::= [gs] nw <expression>* _ <type> E                     # new -//              (expr-list) type -//              ::= [gs] nw <expression>* _ <type> <initializer>         # new -//              (expr-list) type (init) -//              ::= [gs] na <expression>* _ <type> E                     # new[] -//              (expr-list) type -//              ::= [gs] na <expression>* _ <type> <initializer>         # new[] -//              (expr-list) type (init) -//              ::= [gs] dl <expression>                                 # -//              delete expression -//              ::= [gs] da <expression>                                 # -//              delete[] expression -//              ::= pp_ <expression>                                     # -//              prefix ++ -//              ::= mm_ <expression>                                     # -//              prefix -- -//              ::= ti <type>                                            # -//              typeid (type) -//              ::= te <expression>                                      # -//              typeid (expression) -//              ::= dc <type> <expression>                               # -//              dynamic_cast<type> (expression) -//              ::= sc <type> <expression>                               # -//              static_cast<type> (expression) -//              ::= cc <type> <expression>                               # -//              const_cast<type> (expression) -//              ::= rc <type> <expression>                               # -//              reinterpret_cast<type> (expression) -//              ::= st <type>                                            # -//              sizeof (a type) -//              ::= sz <expression>                                      # -//              sizeof (an expression) -//              ::= at <type>                                            # -//              alignof (a type) -//              ::= az <expression>                                      # -//              alignof (an expression) -//              ::= nx <expression>                                      # -//              noexcept (expression) -//              ::= <template-param> -//              ::= <function-param> -//              ::= dt <expression> <unresolved-name>                    # -//              expr.name -//              ::= pt <expression> <unresolved-name>                    # -//              expr->name -//              ::= ds <expression> <expression>                         # -//              expr.*expr -//              ::= sZ <template-param>                                  # size -//              of a parameter pack -//              ::= sZ <function-param>                                  # size -//              of a function parameter pack -//              ::= sp <expression>                                      # pack -//              expansion -//              ::= tw <expression>                                      # throw -//              expression -//              ::= tr                                                   # throw -//              with no operand (rethrow) -//              ::= <unresolved-name>                                    # f(p), -//              N::f(p), ::f(p), -//                                                                       # -//                                                                       freestanding -//                                                                       dependent -//                                                                       name -//                                                                       (e.g., -//                                                                       T::x), -//                                                                       # -//                                                                       objectless -//                                                                       nonstatic -//                                                                       member -//                                                                       reference -//              ::= <expr-primary> +StringView Db::parseBareSourceName() { +  size_t Int = 0; +  if (parsePositiveInteger(&Int) || numLeft() < Int) +    return StringView(); +  StringView R(First, First + Int); +  First += Int; +  return R; +} -template <class C> -static const char *parse_expression(const char *first, const char *last, -                                    C &db) { -  if (last - first >= 2) { -    const char *t = first; -    bool parsed_gs = false; -    if (last - first >= 4 && t[0] == 'g' && t[1] == 's') { -      t += 2; -      parsed_gs = true; -    } -    switch (*t) { -    case 'L': -      first = parse_expr_primary(first, last, db); -      break; -    case 'T': -      first = parse_template_param(first, last, db); +// <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E +// +// <exception-spec> ::= Do                # non-throwing exception-specification (e.g., noexcept, throw()) +//                  ::= DO <expression> E # computed (instantiation-dependent) noexcept +//                  ::= Dw <type>+ E      # dynamic exception specification with instantiation-dependent types +// +// <ref-qualifier> ::= R                   # & ref-qualifier +// <ref-qualifier> ::= O                   # && ref-qualifier +Node *Db::parseFunctionType() { +  Qualifiers CVQuals = parseCVQualifiers(); + +  Node *ExceptionSpec = nullptr; +  if (consumeIf("Do")) { +    ExceptionSpec = make<NameType>("noexcept"); +  } else if (consumeIf("DO")) { +    Node *E = parseExpr(); +    if (E == nullptr || !consumeIf('E')) +      return nullptr; +    ExceptionSpec = make<NoexceptSpec>(E); +  } else if (consumeIf("Dw")) { +    size_t SpecsBegin = Names.size(); +    while (!consumeIf('E')) { +      Node *T = parseType(); +      if (T == nullptr) +        return nullptr; +      Names.push_back(T); +    } +    ExceptionSpec = +      make<DynamicExceptionSpec>(popTrailingNodeArray(SpecsBegin)); +  } + +  consumeIf("Dx"); // transaction safe + +  if (!consumeIf('F')) +    return nullptr; +  consumeIf('Y'); // extern "C" +  Node *ReturnType = parseType(); +  if (ReturnType == nullptr) +    return nullptr; + +  FunctionRefQual ReferenceQualifier = FrefQualNone; +  size_t ParamsBegin = Names.size(); +  while (true) { +    if (consumeIf('E'))        break; -    case 'f': -      first = parse_function_param(first, last, db); +    if (consumeIf('v')) +      continue; +    if (consumeIf("RE")) { +      ReferenceQualifier = FrefQualLValue;        break; -    case 'a': -      switch (t[1]) { -      case 'a': -        t = parse_binary_expression(first + 2, last, "&&", db); -        if (t != first + 2) -          first = t; -        break; -      case 'd': -        t = parse_prefix_expression(first + 2, last, "&", db); -        if (t != first + 2) -          first = t; -        break; -      case 'n': -        t = parse_binary_expression(first + 2, last, "&", db); -        if (t != first + 2) -          first = t; -        break; -      case 'N': -        t = parse_binary_expression(first + 2, last, "&=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'S': -        t = parse_binary_expression(first + 2, last, "=", db); -        if (t != first + 2) -          first = t; -        break; -      case 't': -        first = parse_alignof_type(first, last, db); -        break; -      case 'z': -        first = parse_alignof_expr(first, last, db); -        break; -      } +    } +    if (consumeIf("OE")) { +      ReferenceQualifier = FrefQualRValue;        break; -    case 'c': -      switch (t[1]) { -      case 'c': -        first = parse_const_cast_expr(first, last, db); -        break; -      case 'l': -        first = parse_call_expr(first, last, db); -        break; -      case 'm': -        t = parse_binary_expression(first + 2, last, ",", db); -        if (t != first + 2) -          first = t; -        break; -      case 'o': -        t = parse_prefix_expression(first + 2, last, "~", db); -        if (t != first + 2) -          first = t; -        break; -      case 'v': -        first = parse_conversion_expr(first, last, db); -        break; +    } +    Node *T = parseType(); +    if (T == nullptr) +      return nullptr; +    Names.push_back(T); +  } + +  NodeArray Params = popTrailingNodeArray(ParamsBegin); +  return make<FunctionType>(ReturnType, Params, CVQuals, +                            ReferenceQualifier, ExceptionSpec); +} + +// extension: +// <vector-type>           ::= Dv <positive dimension number> _ <extended element type> +//                         ::= Dv [<dimension expression>] _ <element type> +// <extended element type> ::= <element type> +//                         ::= p # AltiVec vector pixel +Node *Db::parseVectorType() { +  if (!consumeIf("Dv")) +    return nullptr; +  if (look() >= '1' && look() <= '9') { +    StringView DimensionNumber = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    if (consumeIf('p')) +      return make<VectorType>(DimensionNumber); +    Node *ElemType = parseType(); +    if (ElemType == nullptr) +      return nullptr; +    return make<VectorType>(ElemType, DimensionNumber); +  } + +  if (!consumeIf('_')) { +    Node *DimExpr = parseExpr(); +    if (!DimExpr) +      return nullptr; +    if (!consumeIf('_')) +      return nullptr; +    Node *ElemType = parseType(); +    if (!ElemType) +      return nullptr; +    return make<VectorType>(ElemType, DimExpr); +  } +  Node *ElemType = parseType(); +  if (!ElemType) +    return nullptr; +  return make<VectorType>(ElemType, StringView()); +} + +// <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x) +//             ::= DT <expression> E  # decltype of an expression (C++0x) +Node *Db::parseDecltype() { +  if (!consumeIf('D')) +    return nullptr; +  if (!consumeIf('t') && !consumeIf('T')) +    return nullptr; +  Node *E = parseExpr(); +  if (E == nullptr) +    return nullptr; +  if (!consumeIf('E')) +    return nullptr; +  return make<EnclosingExpr>("decltype(", E, ")"); +} + +// <array-type> ::= A <positive dimension number> _ <element type> +//              ::= A [<dimension expression>] _ <element type> +Node *Db::parseArrayType() { +  if (!consumeIf('A')) +    return nullptr; + +  if (std::isdigit(look())) { +    StringView Dimension = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    Node *Ty = parseType(); +    if (Ty == nullptr) +      return nullptr; +    return make<ArrayType>(Ty, Dimension); +  } + +  if (!consumeIf('_')) { +    Node *DimExpr = parseExpr(); +    if (DimExpr == nullptr) +      return nullptr; +    if (!consumeIf('_')) +      return nullptr; +    Node *ElementType = parseType(); +    if (ElementType == nullptr) +      return nullptr; +    return make<ArrayType>(ElementType, DimExpr); +  } + +  Node *Ty = parseType(); +  if (Ty == nullptr) +    return nullptr; +  return make<ArrayType>(Ty); +} + +// <pointer-to-member-type> ::= M <class type> <member type> +Node *Db::parsePointerToMemberType() { +  if (!consumeIf('M')) +    return nullptr; +  Node *ClassType = parseType(); +  if (ClassType == nullptr) +    return nullptr; +  Node *MemberType = parseType(); +  if (MemberType == nullptr) +    return nullptr; +  return make<PointerToMemberType>(ClassType, MemberType); +} + +// <class-enum-type> ::= <name>     # non-dependent type name, dependent type name, or dependent typename-specifier +//                   ::= Ts <name>  # dependent elaborated type specifier using 'struct' or 'class' +//                   ::= Tu <name>  # dependent elaborated type specifier using 'union' +//                   ::= Te <name>  # dependent elaborated type specifier using 'enum' +Node *Db::parseClassEnumType() { +  StringView ElabSpef; +  if (consumeIf("Ts")) +    ElabSpef = "struct"; +  else if (consumeIf("Tu")) +    ElabSpef = "union"; +  else if (consumeIf("Te")) +    ElabSpef = "enum"; + +  Node *Name = parseName(); +  if (Name == nullptr) +    return nullptr; + +  if (!ElabSpef.empty()) +    return make<ElaboratedTypeSpefType>(ElabSpef, Name); + +  return Name; +} + +// <qualified-type>     ::= <qualifiers> <type> +// <qualifiers> ::= <extended-qualifier>* <CV-qualifiers> +// <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier +Node *Db::parseQualifiedType() { +  if (consumeIf('U')) { +    StringView Qual = parseBareSourceName(); +    if (Qual.empty()) +      return nullptr; + +    // FIXME parse the optional <template-args> here! + +    // extension            ::= U <objc-name> <objc-type>  # objc-type<identifier> +    if (Qual.startsWith("objcproto")) { +      StringView ProtoSourceName = Qual.dropFront(std::strlen("objcproto")); +      StringView Proto; +      { +        SwapAndRestore<const char *> SaveFirst(First, ProtoSourceName.begin()), +                                     SaveLast(Last, ProtoSourceName.end()); +        Proto = parseBareSourceName();        } +      if (Proto.empty()) +        return nullptr; +      Node *Child = parseQualifiedType(); +      if (Child == nullptr) +        return nullptr; +      return make<ObjCProtoName>(Child, Proto); +    } + +    Node *Child = parseQualifiedType(); +    if (Child == nullptr) +      return nullptr; +    return make<VendorExtQualType>(Child, Qual); +  } + +  Qualifiers Quals = parseCVQualifiers(); +  Node *Ty = parseType(); +  if (Ty == nullptr) +    return nullptr; +  if (Quals != QualNone) +    Ty = make<QualType>(Ty, Quals); +  return Ty; +} + +// <type>      ::= <builtin-type> +//             ::= <qualified-type> +//             ::= <function-type> +//             ::= <class-enum-type> +//             ::= <array-type> +//             ::= <pointer-to-member-type> +//             ::= <template-param> +//             ::= <template-template-param> <template-args> +//             ::= <decltype> +//             ::= P <type>        # pointer +//             ::= R <type>        # l-value reference +//             ::= O <type>        # r-value reference (C++11) +//             ::= C <type>        # complex pair (C99) +//             ::= G <type>        # imaginary (C99) +//             ::= <substitution>  # See Compression below +// extension   ::= U <objc-name> <objc-type>  # objc-type<identifier> +// extension   ::= <vector-type> # <vector-type> starts with Dv +// +// <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1 +// <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name> +Node *Db::parseType() { +  Node *Result = nullptr; + +  switch (look()) { +  //             ::= <qualified-type> +  case 'r': +  case 'V': +  case 'K': { +    unsigned AfterQuals = 0; +    if (look(AfterQuals) == 'r') ++AfterQuals; +    if (look(AfterQuals) == 'V') ++AfterQuals; +    if (look(AfterQuals) == 'K') ++AfterQuals; + +    if (look(AfterQuals) == 'F' || +        (look(AfterQuals) == 'D' && +         (look(AfterQuals + 1) == 'o' || look(AfterQuals + 1) == 'O' || +          look(AfterQuals + 1) == 'w' || look(AfterQuals + 1) == 'x'))) { +      Result = parseFunctionType();        break; +    } +    LLVM_FALLTHROUGH; +  } +  case 'U': { +    Result = parseQualifiedType(); +    break; +  } +  // <builtin-type> ::= v    # void +  case 'v': +    ++First; +    return make<NameType>("void"); +  //                ::= w    # wchar_t +  case 'w': +    ++First; +    return make<NameType>("wchar_t"); +  //                ::= b    # bool +  case 'b': +    ++First; +    return make<NameType>("bool"); +  //                ::= c    # char +  case 'c': +    ++First; +    return make<NameType>("char"); +  //                ::= a    # signed char +  case 'a': +    ++First; +    return make<NameType>("signed char"); +  //                ::= h    # unsigned char +  case 'h': +    ++First; +    return make<NameType>("unsigned char"); +  //                ::= s    # short +  case 's': +    ++First; +    return make<NameType>("short"); +  //                ::= t    # unsigned short +  case 't': +    ++First; +    return make<NameType>("unsigned short"); +  //                ::= i    # int +  case 'i': +    ++First; +    return make<NameType>("int"); +  //                ::= j    # unsigned int +  case 'j': +    ++First; +    return make<NameType>("unsigned int"); +  //                ::= l    # long +  case 'l': +    ++First; +    return make<NameType>("long"); +  //                ::= m    # unsigned long +  case 'm': +    ++First; +    return make<NameType>("unsigned long"); +  //                ::= x    # long long, __int64 +  case 'x': +    ++First; +    return make<NameType>("long long"); +  //                ::= y    # unsigned long long, __int64 +  case 'y': +    ++First; +    return make<NameType>("unsigned long long"); +  //                ::= n    # __int128 +  case 'n': +    ++First; +    return make<NameType>("__int128"); +  //                ::= o    # unsigned __int128 +  case 'o': +    ++First; +    return make<NameType>("unsigned __int128"); +  //                ::= f    # float +  case 'f': +    ++First; +    return make<NameType>("float"); +  //                ::= d    # double +  case 'd': +    ++First; +    return make<NameType>("double"); +  //                ::= e    # long double, __float80 +  case 'e': +    ++First; +    return make<NameType>("long double"); +  //                ::= g    # __float128 +  case 'g': +    ++First; +    return make<NameType>("__float128"); +  //                ::= z    # ellipsis +  case 'z': +    ++First; +    return make<NameType>("..."); + +  // <builtin-type> ::= u <source-name>    # vendor extended type +  case 'u': { +    ++First; +    StringView Res = parseBareSourceName(); +    if (Res.empty()) +      return nullptr; +    return make<NameType>(Res); +  } +  case 'D': +    switch (look(1)) { +    //                ::= Dd   # IEEE 754r decimal floating point (64 bits)      case 'd': -      switch (t[1]) { -      case 'a': { -        const char *t1 = parse_expression(t + 2, last, db); -        if (t1 != t + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first = -              (parsed_gs ? std::string("::") : std::string()) + "delete[] " + -              db.names.back().move_full(); -          first = t1; -        } -      } break; -      case 'c': -        first = parse_dynamic_cast_expr(first, last, db); -        break; -      case 'e': -        t = parse_prefix_expression(first + 2, last, "*", db); -        if (t != first + 2) -          first = t; -        break; -      case 'l': { -        const char *t1 = parse_expression(t + 2, last, db); -        if (t1 != t + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first = -              (parsed_gs ? std::string("::") : std::string()) + "delete " + -              db.names.back().move_full(); -          first = t1; -        } -      } break; -      case 'n': -        return parse_unresolved_name(first, last, db); -      case 's': -        first = parse_dot_star_expr(first, last, db); -        break; -      case 't': -        first = parse_dot_expr(first, last, db); -        break; -      case 'v': -        t = parse_binary_expression(first + 2, last, "/", db); -        if (t != first + 2) -          first = t; -        break; -      case 'V': -        t = parse_binary_expression(first + 2, last, "/=", db); -        if (t != first + 2) -          first = t; -        break; -      } -      break; +      First += 2; +      return make<NameType>("decimal64"); +    //                ::= De   # IEEE 754r decimal floating point (128 bits)      case 'e': -      switch (t[1]) { -      case 'o': -        t = parse_binary_expression(first + 2, last, "^", db); -        if (t != first + 2) -          first = t; -        break; -      case 'O': -        t = parse_binary_expression(first + 2, last, "^=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'q': -        t = parse_binary_expression(first + 2, last, "==", db); -        if (t != first + 2) -          first = t; -        break; -      } -      break; -    case 'g': -      switch (t[1]) { -      case 'e': -        t = parse_binary_expression(first + 2, last, ">=", db); -        if (t != first + 2) -          first = t; -        break; -      case 't': -        t = parse_binary_expression(first + 2, last, ">", db); -        if (t != first + 2) -          first = t; -        break; -      } -      break; +      First += 2; +      return make<NameType>("decimal128"); +    //                ::= Df   # IEEE 754r decimal floating point (32 bits) +    case 'f': +      First += 2; +      return make<NameType>("decimal32"); +    //                ::= Dh   # IEEE 754r half-precision floating point (16 bits) +    case 'h': +      First += 2; +      return make<NameType>("decimal16"); +    //                ::= Di   # char32_t      case 'i': -      if (t[1] == 'x') { -        const char *t1 = parse_expression(first + 2, last, db); -        if (t1 != first + 2) { -          const char *t2 = parse_expression(t1, last, db); -          if (t2 != t1) { -            if (db.names.size() < 2) -              return first; -            auto op2 = db.names.back().move_full(); -            db.names.pop_back(); -            auto op1 = db.names.back().move_full(); -            db.names.back() = "(" + op1 + ")[" + op2 + "]"; -            first = t2; -          } else if (!db.names.empty()) -            db.names.pop_back(); -        } -      } -      break; -    case 'l': -      switch (t[1]) { -      case 'e': -        t = parse_binary_expression(first + 2, last, "<=", db); -        if (t != first + 2) -          first = t; -        break; -      case 's': -        t = parse_binary_expression(first + 2, last, "<<", db); -        if (t != first + 2) -          first = t; -        break; -      case 'S': -        t = parse_binary_expression(first + 2, last, "<<=", db); -        if (t != first + 2) -          first = t; -        break; -      case 't': -        t = parse_binary_expression(first + 2, last, "<", db); -        if (t != first + 2) -          first = t; -        break; -      } -      break; -    case 'm': -      switch (t[1]) { -      case 'i': -        t = parse_binary_expression(first + 2, last, "-", db); -        if (t != first + 2) -          first = t; -        break; -      case 'I': -        t = parse_binary_expression(first + 2, last, "-=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'l': -        t = parse_binary_expression(first + 2, last, "*", db); -        if (t != first + 2) -          first = t; -        break; -      case 'L': -        t = parse_binary_expression(first + 2, last, "*=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'm': -        if (first + 2 != last && first[2] == '_') { -          t = parse_prefix_expression(first + 3, last, "--", db); -          if (t != first + 3) -            first = t; -        } else { -          const char *t1 = parse_expression(first + 2, last, db); -          if (t1 != first + 2) { -            if (db.names.empty()) -              return first; -            db.names.back() = "(" + db.names.back().move_full() + ")--"; -            first = t1; -          } -        } -        break; -      } -      break; +      First += 2; +      return make<NameType>("char32_t"); +    //                ::= Ds   # char16_t +    case 's': +      First += 2; +      return make<NameType>("char16_t"); +    //                ::= Da   # auto (in dependent new-expressions) +    case 'a': +      First += 2; +      return make<NameType>("auto"); +    //                ::= Dc   # decltype(auto) +    case 'c': +      First += 2; +      return make<NameType>("decltype(auto)"); +    //                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))      case 'n': -      switch (t[1]) { -      case 'a': -      case 'w': -        first = parse_new_expr(first, last, db); -        break; -      case 'e': -        t = parse_binary_expression(first + 2, last, "!=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'g': -        t = parse_prefix_expression(first + 2, last, "-", db); -        if (t != first + 2) -          first = t; -        break; -      case 't': -        t = parse_prefix_expression(first + 2, last, "!", db); -        if (t != first + 2) -          first = t; -        break; -      case 'x': -        t = parse_noexcept_expression(first + 2, last, db); -        if (t != first + 2) -          first = t; -        break; -      } -      break; -    case 'o': -      switch (t[1]) { -      case 'n': -        return parse_unresolved_name(first, last, db); -      case 'o': -        t = parse_binary_expression(first + 2, last, "||", db); -        if (t != first + 2) -          first = t; -        break; -      case 'r': -        t = parse_binary_expression(first + 2, last, "|", db); -        if (t != first + 2) -          first = t; -        break; -      case 'R': -        t = parse_binary_expression(first + 2, last, "|=", db); -        if (t != first + 2) -          first = t; -        break; -      } +      First += 2; +      return make<NameType>("std::nullptr_t"); + +    //             ::= <decltype> +    case 't': +    case 'T': { +      Result = parseDecltype();        break; -    case 'p': -      switch (t[1]) { -      case 'm': -        t = parse_binary_expression(first + 2, last, "->*", db); -        if (t != first + 2) -          first = t; -        break; -      case 'l': -        t = parse_binary_expression(first + 2, last, "+", db); -        if (t != first + 2) -          first = t; -        break; -      case 'L': -        t = parse_binary_expression(first + 2, last, "+=", db); -        if (t != first + 2) -          first = t; -        break; -      case 'p': -        if (first + 2 != last && first[2] == '_') { -          t = parse_prefix_expression(first + 3, last, "++", db); -          if (t != first + 3) -            first = t; -        } else { -          const char *t1 = parse_expression(first + 2, last, db); -          if (t1 != first + 2) { -            if (db.names.empty()) -              return first; -            db.names.back() = "(" + db.names.back().move_full() + ")++"; -            first = t1; -          } -        } -        break; -      case 's': -        t = parse_prefix_expression(first + 2, last, "+", db); -        if (t != first + 2) -          first = t; -        break; -      case 't': -        first = parse_arrow_expr(first, last, db); -        break; -      } +    } +    // extension   ::= <vector-type> # <vector-type> starts with Dv +    case 'v': { +      Result = parseVectorType();        break; -    case 'q': -      if (t[1] == 'u') { -        const char *t1 = parse_expression(first + 2, last, db); -        if (t1 != first + 2) { -          const char *t2 = parse_expression(t1, last, db); -          if (t2 != t1) { -            const char *t3 = parse_expression(t2, last, db); -            if (t3 != t2) { -              if (db.names.size() < 3) -                return first; -              auto op3 = db.names.back().move_full(); -              db.names.pop_back(); -              auto op2 = db.names.back().move_full(); -              db.names.pop_back(); -              auto op1 = db.names.back().move_full(); -              db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")"; -              first = t3; -            } else { -              if (db.names.size() < 2) -                return first; -              db.names.pop_back(); -              db.names.pop_back(); -            } -          } else if (!db.names.empty()) -            db.names.pop_back(); -        } -      } +    } +    //           ::= Dp <type>       # pack expansion (C++0x) +    case 'p': { +      First += 2; +      Node *Child = parseType(); +      if (!Child) +        return nullptr; +      Result = make<ParameterPackExpansion>(Child);        break; -    case 'r': -      switch (t[1]) { -      case 'c': -        first = parse_reinterpret_cast_expr(first, last, db); -        break; -      case 'm': -        t = parse_binary_expression(first + 2, last, "%", db); -        if (t != first + 2) -          first = t; -        break; -      case 'M': -        t = parse_binary_expression(first + 2, last, "%=", db); -        if (t != first + 2) -          first = t; -        break; -      case 's': -        t = parse_binary_expression(first + 2, last, ">>", db); -        if (t != first + 2) -          first = t; -        break; -      case 'S': -        t = parse_binary_expression(first + 2, last, ">>=", db); -        if (t != first + 2) -          first = t; -        break; -      } +    } +    // Exception specifier on a function type. +    case 'o': +    case 'O': +    case 'w': +    // Transaction safe function type. +    case 'x': +      Result = parseFunctionType();        break; -    case 's': -      switch (t[1]) { -      case 'c': -        first = parse_static_cast_expr(first, last, db); -        break; -      case 'p': -        first = parse_pack_expansion(first, last, db); -        break; -      case 'r': -        return parse_unresolved_name(first, last, db); -      case 't': -        first = parse_sizeof_type_expr(first, last, db); -        break; -      case 'z': -        first = parse_sizeof_expr_expr(first, last, db); -        break; -      case 'Z': -        if (last - t >= 3) { -          switch (t[2]) { -          case 'T': -            first = parse_sizeof_param_pack_expr(first, last, db); -            break; -          case 'f': -            first = parse_sizeof_function_param_pack_expr(first, last, db); -            break; -          } -        } -        break; -      } +    } +    break; +  //             ::= <function-type> +  case 'F': { +    Result = parseFunctionType(); +    break; +  } +  //             ::= <array-type> +  case 'A': { +    Result = parseArrayType(); +    break; +  } +  //             ::= <pointer-to-member-type> +  case 'M': { +    Result = parsePointerToMemberType(); +    break; +  } +  //             ::= <template-param> +  case 'T': { +    // This could be an elaborate type specifier on a <class-enum-type>. +    if (look(1) == 's' || look(1) == 'u' || look(1) == 'e') { +      Result = parseClassEnumType();        break; -    case 't': -      switch (t[1]) { -      case 'e': -      case 'i': -        first = parse_typeid_expr(first, last, db); -        break; -      case 'r': -        db.names.push_back("throw"); -        first += 2; -        break; -      case 'w': -        first = parse_throw_expr(first, last, db); +    } + +    Result = parseTemplateParam(); +    if (Result == nullptr) +      return nullptr; + +    // Result could be either of: +    //   <type>        ::= <template-param> +    //   <type>        ::= <template-template-param> <template-args> +    // +    //   <template-template-param> ::= <template-param> +    //                             ::= <substitution> +    // +    // If this is followed by some <template-args>, and we're permitted to +    // parse them, take the second production. + +    if (TryToParseTemplateArgs && look() == 'I') { +      Node *TA = parseTemplateArgs(); +      if (TA == nullptr) +        return nullptr; +      Result = make<NameWithTemplateArgs>(Result, TA); +    } +    break; +  } +  //             ::= P <type>        # pointer +  case 'P': { +    ++First; +    Node *Ptr = parseType(); +    if (Ptr == nullptr) +      return nullptr; +    Result = make<PointerType>(Ptr); +    break; +  } +  //             ::= R <type>        # l-value reference +  case 'R': { +    ++First; +    Node *Ref = parseType(); +    if (Ref == nullptr) +      return nullptr; +    Result = make<ReferenceType>(Ref, ReferenceKind::LValue); +    break; +  } +  //             ::= O <type>        # r-value reference (C++11) +  case 'O': { +    ++First; +    Node *Ref = parseType(); +    if (Ref == nullptr) +      return nullptr; +    Result = make<ReferenceType>(Ref, ReferenceKind::RValue); +    break; +  } +  //             ::= C <type>        # complex pair (C99) +  case 'C': { +    ++First; +    Node *P = parseType(); +    if (P == nullptr) +      return nullptr; +    Result = make<PostfixQualifiedType>(P, " complex"); +    break; +  } +  //             ::= G <type>        # imaginary (C99) +  case 'G': { +    ++First; +    Node *P = parseType(); +    if (P == nullptr) +      return P; +    Result = make<PostfixQualifiedType>(P, " imaginary"); +    break; +  } +  //             ::= <substitution>  # See Compression below +  case 'S': { +    if (look(1) && look(1) != 't') { +      Node *Sub = parseSubstitution(); +      if (Sub == nullptr) +        return nullptr; + +      // Sub could be either of: +      //   <type>        ::= <substitution> +      //   <type>        ::= <template-template-param> <template-args> +      // +      //   <template-template-param> ::= <template-param> +      //                             ::= <substitution> +      // +      // If this is followed by some <template-args>, and we're permitted to +      // parse them, take the second production. + +      if (TryToParseTemplateArgs && look() == 'I') { +        Node *TA = parseTemplateArgs(); +        if (TA == nullptr) +          return nullptr; +        Result = make<NameWithTemplateArgs>(Sub, TA);          break;        } -      break; -    case '1': -    case '2': -    case '3': -    case '4': -    case '5': -    case '6': -    case '7': -    case '8': -    case '9': -      return parse_unresolved_name(first, last, db); -    } -  } -  return first; -} -// <template-arg> ::= <type>                                             # type -// or template -//                ::= X <expression> E                                   # -//                expression -//                ::= <expr-primary>                                     # -//                simple expressions -//                ::= J <template-arg>* E                                # -//                argument pack -//                ::= LZ <encoding> E                                    # -//                extension - -template <class C> -static const char *parse_template_arg(const char *first, const char *last, -                                      C &db) { -  if (first != last) { -    const char *t; -    switch (*first) { -    case 'X': -      t = parse_expression(first + 1, last, db); -      if (t != first + 1) { -        if (t != last && *t == 'E') -          first = t + 1; -      } -      break; -    case 'J': -      t = first + 1; -      if (t == last) -        return first; -      while (*t != 'E') { -        const char *t1 = parse_template_arg(t, last, db); -        if (t1 == t) -          return first; -        t = t1; -      } -      first = t + 1; -      break; -    case 'L': -      // <expr-primary> or LZ <encoding> E -      if (first + 1 != last && first[1] == 'Z') { -        t = parse_encoding(first + 2, last, db); -        if (t != first + 2 && t != last && *t == 'E') -          first = t + 1; -      } else -        first = parse_expr_primary(first, last, db); -      break; -    default: -      // <type> -      first = parse_type(first, last, db); -      break; +      // If all we parsed was a substitution, don't re-insert into the +      // substitution table. +      return Sub;      } +    LLVM_FALLTHROUGH; +  } +  //        ::= <class-enum-type> +  default: { +    Result = parseClassEnumType(); +    break;    } -  return first; +  } + +  // If we parsed a type, insert it into the substitution table. Note that all +  // <builtin-type>s and <substitution>s have already bailed out, because they +  // don't get substitutions. +  if (Result != nullptr) +    Subs.push_back(Result); +  return Result;  } -// <template-args> ::= I <template-arg>* E -//     extension, the abi says <template-arg>+ +Node *Db::parsePrefixExpr(StringView Kind) { +  Node *E = parseExpr(); +  if (E == nullptr) +    return nullptr; +  return make<PrefixExpr>(Kind, E); +} -template <class C> -static const char *parse_template_args(const char *first, const char *last, -                                       C &db) { -  if (last - first >= 2 && *first == 'I') { -    if (db.tag_templates) -      db.template_param.back().clear(); -    const char *t = first + 1; -    std::string args("<"); -    while (*t != 'E') { -      if (db.tag_templates) -        db.template_param.emplace_back(); -      size_t k0 = db.names.size(); -      const char *t1 = parse_template_arg(t, last, db); -      size_t k1 = db.names.size(); -      if (db.tag_templates) -        db.template_param.pop_back(); -      if (t1 == t || t1 == last) -        return first; -      if (db.tag_templates) { -        db.template_param.back().emplace_back(); -        for (size_t k = k0; k < k1; ++k) -          db.template_param.back().back().push_back(db.names[k]); -      } -      for (size_t k = k0; k < k1; ++k) { -        if (args.size() > 1) -          args += ", "; -        args += db.names[k].move_full(); -      } -      for (; k1 > k0; --k1) -        if (!db.names.empty()) -          db.names.pop_back(); -      t = t1; -    } -    first = t + 1; -    if (args.back() != '>') -      args += ">"; -    else -      args += " >"; -    db.names.push_back(std::move(args)); +Node *Db::parseBinaryExpr(StringView Kind) { +  Node *LHS = parseExpr(); +  if (LHS == nullptr) +    return nullptr; +  Node *RHS = parseExpr(); +  if (RHS == nullptr) +    return nullptr; +  return make<BinaryExpr>(LHS, Kind, RHS); +} + +Node *Db::parseIntegerLiteral(StringView Lit) { +  StringView Tmp = parseNumber(true); +  if (!Tmp.empty() && consumeIf('E')) +    return make<IntegerExpr>(Lit, Tmp); +  return nullptr; +} + +// <CV-Qualifiers> ::= [r] [V] [K] +Qualifiers Db::parseCVQualifiers() { +  Qualifiers CVR = QualNone; +  if (consumeIf('r')) +    addQualifiers(CVR, QualRestrict); +  if (consumeIf('V')) +    addQualifiers(CVR, QualVolatile); +  if (consumeIf('K')) +    addQualifiers(CVR, QualConst); +  return CVR; +} + +// <function-param> ::= fp <top-level CV-Qualifiers> _                                     # L == 0, first parameter +//                  ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters +//                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> _         # L > 0, first parameter +//                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters +Node *Db::parseFunctionParam() { +  if (consumeIf("fp")) { +    parseCVQualifiers(); +    StringView Num = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    return make<FunctionParam>(Num); +  } +  if (consumeIf("fL")) { +    if (parseNumber().empty()) +      return nullptr; +    if (!consumeIf('p')) +      return nullptr; +    parseCVQualifiers(); +    StringView Num = parseNumber(); +    if (!consumeIf('_')) +      return nullptr; +    return make<FunctionParam>(Num);    } -  return first; +  return nullptr;  } -// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> -// <unqualified-name> E -//               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> -//               <template-args> E -// -// <prefix> ::= <prefix> <unqualified-name> -//          ::= <template-prefix> <template-args> -//          ::= <template-param> -//          ::= <decltype> -//          ::= # empty -//          ::= <substitution> -//          ::= <prefix> <data-member-prefix> -//  extension ::= L -// -// <template-prefix> ::= <prefix> <template unqualified-name> -//                   ::= <template-param> -//                   ::= <substitution> +// [gs] nw <expression>* _ <type> E                     # new (expr-list) type +// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init) +// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type +// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init) +// <initializer> ::= pi <expression>* E                 # parenthesized initialization +Node *Db::parseNewExpr() { +  bool Global = consumeIf("gs"); +  bool IsArray = look(1) == 'a'; +  if (!consumeIf("nw") && !consumeIf("na")) +    return nullptr; +  size_t Exprs = Names.size(); +  while (!consumeIf('_')) { +    Node *Ex = parseExpr(); +    if (Ex == nullptr) +      return nullptr; +    Names.push_back(Ex); +  } +  NodeArray ExprList = popTrailingNodeArray(Exprs); +  Node *Ty = parseType(); +  if (Ty == nullptr) +    return Ty; +  if (consumeIf("pi")) { +    size_t InitsBegin = Names.size(); +    while (!consumeIf('E')) { +      Node *Init = parseExpr(); +      if (Init == nullptr) +        return Init; +      Names.push_back(Init); +    } +    NodeArray Inits = popTrailingNodeArray(InitsBegin); +    return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray); +  } else if (!consumeIf('E')) +    return nullptr; +  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray); +} -template <class C> -static const char *parse_nested_name(const char *first, const char *last, C &db, -                                     bool *ends_with_template_args) { -  if (first != last && *first == 'N') { -    unsigned cv; -    const char *t0 = parse_cv_qualifiers(first + 1, last, cv); -    if (t0 == last) -      return first; -    db.ref = 0; -    if (*t0 == 'R') { -      db.ref = 1; -      ++t0; -    } else if (*t0 == 'O') { -      db.ref = 2; -      ++t0; -    } -    db.names.emplace_back(); -    if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't') { -      t0 += 2; -      db.names.back().first = "std"; -    } -    if (t0 == last) { -      db.names.pop_back(); -      return first; -    } -    bool pop_subs = false; -    bool component_ends_with_template_args = false; -    while (*t0 != 'E') { -      component_ends_with_template_args = false; -      const char *t1; -      switch (*t0) { -      case 'S': -        if (t0 + 1 != last && t0[1] == 't') -          goto do_parse_unqualified_name; -        t1 = parse_substitution(t0, last, db); -        if (t1 != t0 && t1 != last) { -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          if (!db.names.back().first.empty()) { -            db.names.back().first += "::" + name; -            db.subs.push_back(typename C::sub_type(1, db.names.back())); -          } else -            db.names.back().first = name; -          pop_subs = true; -          t0 = t1; -        } else -          return first; -        break; -      case 'T': -        t1 = parse_template_param(t0, last, db); -        if (t1 != t0 && t1 != last) { -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          if (!db.names.back().first.empty()) -            db.names.back().first += "::" + name; -          else -            db.names.back().first = name; -          db.subs.push_back(typename C::sub_type(1, db.names.back())); -          pop_subs = true; -          t0 = t1; -        } else -          return first; -        break; -      case 'D': -        if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T') -          goto do_parse_unqualified_name; -        t1 = parse_decltype(t0, last, db); -        if (t1 != t0 && t1 != last) { -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          if (!db.names.back().first.empty()) -            db.names.back().first += "::" + name; -          else -            db.names.back().first = name; -          db.subs.push_back(typename C::sub_type(1, db.names.back())); -          pop_subs = true; -          t0 = t1; -        } else -          return first; -        break; -      case 'I': -        t1 = parse_template_args(t0, last, db); -        if (t1 != t0 && t1 != last) { -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          db.names.back().first += name; -          db.subs.push_back(typename C::sub_type(1, db.names.back())); -          t0 = t1; -          component_ends_with_template_args = true; -        } else -          return first; -        break; -      case 'L': -        if (++t0 == last) -          return first; -        break; -      default: -      do_parse_unqualified_name: -        t1 = parse_unqualified_name(t0, last, db); -        if (t1 != t0 && t1 != last) { -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          if (!db.names.back().first.empty()) -            db.names.back().first += "::" + name; -          else -            db.names.back().first = name; -          db.subs.push_back(typename C::sub_type(1, db.names.back())); -          pop_subs = true; -          t0 = t1; -        } else -          return first; -      } +// cv <type> <expression>                               # conversion with one argument +// cv <type> _ <expression>* E                          # conversion with a different number of arguments +Node *Db::parseConversionExpr() { +  if (!consumeIf("cv")) +    return nullptr; +  Node *Ty; +  { +    SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false); +    Ty = parseType(); +  } + +  if (Ty == nullptr) +    return nullptr; + +  if (consumeIf('_')) { +    size_t ExprsBegin = Names.size(); +    while (!consumeIf('E')) { +      Node *E = parseExpr(); +      if (E == nullptr) +        return E; +      Names.push_back(E);      } -    first = t0 + 1; -    db.cv = cv; -    if (pop_subs && !db.subs.empty()) -      db.subs.pop_back(); -    if (ends_with_template_args) -      *ends_with_template_args = component_ends_with_template_args; +    NodeArray Exprs = popTrailingNodeArray(ExprsBegin); +    return make<ConversionExpr>(Ty, Exprs);    } -  return first; -} -// <discriminator> := _ <non-negative number>      # when number < 10 -//                 := __ <non-negative number> _   # when number >= 10 -//  extension      := decimal-digit+               # at the end of string +  Node *E[1] = {parseExpr()}; +  if (E[0] == nullptr) +    return nullptr; +  return make<ConversionExpr>(Ty, makeNodeArray(E, E + 1)); +} -static const char *parse_discriminator(const char *first, const char *last) { -  // parse but ignore discriminator -  if (first != last) { -    if (*first == '_') { -      const char *t1 = first + 1; -      if (t1 != last) { -        if (std::isdigit(*t1)) -          first = t1 + 1; -        else if (*t1 == '_') { -          for (++t1; t1 != last && std::isdigit(*t1); ++t1) -            ; -          if (t1 != last && *t1 == '_') -            first = t1 + 1; -        } -      } -    } else if (std::isdigit(*first)) { -      const char *t1 = first + 1; -      for (; t1 != last && std::isdigit(*t1); ++t1) -        ; -      if (t1 == last) -        first = last; +// <expr-primary> ::= L <type> <value number> E                          # integer literal +//                ::= L <type> <value float> E                           # floating literal +//                ::= L <string type> E                                  # string literal +//                ::= L <nullptr type> E                                 # nullptr literal (i.e., "LDnE") +// FIXME:         ::= L <type> <real-part float> _ <imag-part float> E   # complex floating point literal (C 2000) +//                ::= L <mangled-name> E                                 # external name +Node *Db::parseExprPrimary() { +  if (!consumeIf('L')) +    return nullptr; +  switch (look()) { +  case 'w': +    ++First; +    return parseIntegerLiteral("wchar_t"); +  case 'b': +    if (consumeIf("b0E")) +      return make<BoolExpr>(0); +    if (consumeIf("b1E")) +      return make<BoolExpr>(1); +    return nullptr; +  case 'c': +    ++First; +    return parseIntegerLiteral("char"); +  case 'a': +    ++First; +    return parseIntegerLiteral("signed char"); +  case 'h': +    ++First; +    return parseIntegerLiteral("unsigned char"); +  case 's': +    ++First; +    return parseIntegerLiteral("short"); +  case 't': +    ++First; +    return parseIntegerLiteral("unsigned short"); +  case 'i': +    ++First; +    return parseIntegerLiteral(""); +  case 'j': +    ++First; +    return parseIntegerLiteral("u"); +  case 'l': +    ++First; +    return parseIntegerLiteral("l"); +  case 'm': +    ++First; +    return parseIntegerLiteral("ul"); +  case 'x': +    ++First; +    return parseIntegerLiteral("ll"); +  case 'y': +    ++First; +    return parseIntegerLiteral("ull"); +  case 'n': +    ++First; +    return parseIntegerLiteral("__int128"); +  case 'o': +    ++First; +    return parseIntegerLiteral("unsigned __int128"); +  case 'f': +    ++First; +    return parseFloatingLiteral<float>(); +  case 'd': +    ++First; +    return parseFloatingLiteral<double>(); +  case 'e': +    ++First; +    return parseFloatingLiteral<long double>(); +  case '_': +    if (consumeIf("_Z")) { +      Node *R = parseEncoding(); +      if (R != nullptr && consumeIf('E')) +        return R;      } +    return nullptr; +  case 'T': +    // Invalid mangled name per +    //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html +    return nullptr; +  default: { +    // might be named type +    Node *T = parseType(); +    if (T == nullptr) +      return nullptr; +    StringView N = parseNumber(); +    if (!N.empty()) { +      if (!consumeIf('E')) +        return nullptr; +      return make<IntegerCastExpr>(T, N); +    } +    if (consumeIf('E')) +      return T; +    return nullptr; +  }    } -  return first;  } -// <local-name> := Z <function encoding> E <entity name> [<discriminator>] -//              := Z <function encoding> E s [<discriminator>] -//              := Z <function encoding> Ed [ <parameter number> ] _ <entity -//              name> - -template <class C> -static const char *parse_local_name(const char *first, const char *last, C &db, -                                    bool *ends_with_template_args) { -  if (first != last && *first == 'Z') { -    const char *t = parse_encoding(first + 1, last, db); -    if (t != first + 1 && t != last && *t == 'E' && ++t != last) { -      switch (*t) { -      case 's': -        first = parse_discriminator(t + 1, last); -        if (db.names.empty()) -          return first; -        db.names.back().first.append("::string literal"); -        break; -      case 'd': -        if (++t != last) { -          const char *t1 = parse_number(t, last); -          if (t1 != last && *t1 == '_') { -            t = t1 + 1; -            t1 = parse_name(t, last, db, ends_with_template_args); -            if (t1 != t) { -              if (db.names.size() < 2) -                return first; -              auto name = db.names.back().move_full(); -              db.names.pop_back(); -              if (db.names.empty()) -                return first; -              db.names.back().first.append("::"); -              db.names.back().first.append(name); -              first = t1; -            } else if (!db.names.empty()) -              db.names.pop_back(); -          } -        } -        break; -      default: { -        const char *t1 = parse_name(t, last, db, ends_with_template_args); -        if (t1 != t) { -          // parse but ignore discriminator -          first = parse_discriminator(t1, last); -          if (db.names.size() < 2) -            return first; -          auto name = db.names.back().move_full(); -          db.names.pop_back(); -          if (db.names.empty()) -            return first; -          db.names.back().first.append("::"); -          db.names.back().first.append(name); -        } else if (!db.names.empty()) -          db.names.pop_back(); -      } break; -      } +// <braced-expression> ::= <expression> +//                     ::= di <field source-name> <braced-expression>    # .name = expr +//                     ::= dx <index expression> <braced-expression>     # [expr] = expr +//                     ::= dX <range begin expression> <range end expression> <braced-expression> +Node *Db::parseBracedExpr() { +  if (look() == 'd') { +    switch (look(1)) { +    case 'i': { +      First += 2; +      Node *Field = parseSourceName(/*NameState=*/nullptr); +      if (Field == nullptr) +        return nullptr; +      Node *Init = parseBracedExpr(); +      if (Init == nullptr) +        return nullptr; +      return make<BracedExpr>(Field, Init, /*isArray=*/false); +    } +    case 'x': { +      First += 2; +      Node *Index = parseExpr(); +      if (Index == nullptr) +        return nullptr; +      Node *Init = parseBracedExpr(); +      if (Init == nullptr) +        return nullptr; +      return make<BracedExpr>(Index, Init, /*isArray=*/true); +    } +    case 'X': { +      First += 2; +      Node *RangeBegin = parseExpr(); +      if (RangeBegin == nullptr) +        return nullptr; +      Node *RangeEnd = parseExpr(); +      if (RangeEnd == nullptr) +        return nullptr; +      Node *Init = parseBracedExpr(); +      if (Init == nullptr) +        return nullptr; +      return make<BracedRangeExpr>(RangeBegin, RangeEnd, Init); +    }      }    } -  return first; +  return parseExpr();  } -// <name> ::= <nested-name> // N -//        ::= <local-name> # See Scope Encoding below  // Z -//        ::= <unscoped-template-name> <template-args> -//        ::= <unscoped-name> +// (not yet in the spec) +// <fold-expr> ::= fL <binary-operator-name> <expression> <expression> +//             ::= fR <binary-operator-name> <expression> <expression> +//             ::= fl <binary-operator-name> <expression> +//             ::= fr <binary-operator-name> <expression> +Node *Db::parseFoldExpr() { +  if (!consumeIf('f')) +    return nullptr; -// <unscoped-template-name> ::= <unscoped-name> -//                          ::= <substitution> +  char FoldKind = look(); +  bool IsLeftFold, HasInitializer; +  HasInitializer = FoldKind == 'L' || FoldKind == 'R'; +  if (FoldKind == 'l' || FoldKind == 'L') +    IsLeftFold = true; +  else if (FoldKind == 'r' || FoldKind == 'R') +    IsLeftFold = false; +  else +    return nullptr; +  ++First; + +  // FIXME: This map is duplicated in parseOperatorName and parseExpr. +  StringView OperatorName; +  if      (consumeIf("aa")) OperatorName = "&&"; +  else if (consumeIf("an")) OperatorName = "&"; +  else if (consumeIf("aN")) OperatorName = "&="; +  else if (consumeIf("aS")) OperatorName = "="; +  else if (consumeIf("cm")) OperatorName = ","; +  else if (consumeIf("ds")) OperatorName = ".*"; +  else if (consumeIf("dv")) OperatorName = "/"; +  else if (consumeIf("dV")) OperatorName = "/="; +  else if (consumeIf("eo")) OperatorName = "^"; +  else if (consumeIf("eO")) OperatorName = "^="; +  else if (consumeIf("eq")) OperatorName = "=="; +  else if (consumeIf("ge")) OperatorName = ">="; +  else if (consumeIf("gt")) OperatorName = ">"; +  else if (consumeIf("le")) OperatorName = "<="; +  else if (consumeIf("ls")) OperatorName = "<<"; +  else if (consumeIf("lS")) OperatorName = "<<="; +  else if (consumeIf("lt")) OperatorName = "<"; +  else if (consumeIf("mi")) OperatorName = "-"; +  else if (consumeIf("mI")) OperatorName = "-="; +  else if (consumeIf("ml")) OperatorName = "*"; +  else if (consumeIf("mL")) OperatorName = "*="; +  else if (consumeIf("ne")) OperatorName = "!="; +  else if (consumeIf("oo")) OperatorName = "||"; +  else if (consumeIf("or")) OperatorName = "|"; +  else if (consumeIf("oR")) OperatorName = "|="; +  else if (consumeIf("pl")) OperatorName = "+"; +  else if (consumeIf("pL")) OperatorName = "+="; +  else if (consumeIf("rm")) OperatorName = "%"; +  else if (consumeIf("rM")) OperatorName = "%="; +  else if (consumeIf("rs")) OperatorName = ">>"; +  else if (consumeIf("rS")) OperatorName = ">>="; +  else return nullptr; + +  Node *Pack = parseExpr(), *Init = nullptr; +  if (Pack == nullptr) +    return nullptr; +  if (HasInitializer) { +    Init = parseExpr(); +    if (Init == nullptr) +      return nullptr; +  } -template <class C> -static const char *parse_name(const char *first, const char *last, C &db, -                              bool *ends_with_template_args) { -  if (last - first >= 2) { -    const char *t0 = first; -    // extension: ignore L here -    if (*t0 == 'L') -      ++t0; -    switch (*t0) { -    case 'N': { -      const char *t1 = parse_nested_name(t0, last, db, ends_with_template_args); -      if (t1 != t0) -        first = t1; -      break; +  if (IsLeftFold && Init) +    std::swap(Pack, Init); + +  return make<FoldExpr>(IsLeftFold, OperatorName, Pack, Init); +} + +// <expression> ::= <unary operator-name> <expression> +//              ::= <binary operator-name> <expression> <expression> +//              ::= <ternary operator-name> <expression> <expression> <expression> +//              ::= cl <expression>+ E                                   # call +//              ::= cv <type> <expression>                               # conversion with one argument +//              ::= cv <type> _ <expression>* E                          # conversion with a different number of arguments +//              ::= [gs] nw <expression>* _ <type> E                     # new (expr-list) type +//              ::= [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init) +//              ::= [gs] na <expression>* _ <type> E                     # new[] (expr-list) type +//              ::= [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init) +//              ::= [gs] dl <expression>                                 # delete expression +//              ::= [gs] da <expression>                                 # delete[] expression +//              ::= pp_ <expression>                                     # prefix ++ +//              ::= mm_ <expression>                                     # prefix -- +//              ::= ti <type>                                            # typeid (type) +//              ::= te <expression>                                      # typeid (expression) +//              ::= dc <type> <expression>                               # dynamic_cast<type> (expression) +//              ::= sc <type> <expression>                               # static_cast<type> (expression) +//              ::= cc <type> <expression>                               # const_cast<type> (expression) +//              ::= rc <type> <expression>                               # reinterpret_cast<type> (expression) +//              ::= st <type>                                            # sizeof (a type) +//              ::= sz <expression>                                      # sizeof (an expression) +//              ::= at <type>                                            # alignof (a type) +//              ::= az <expression>                                      # alignof (an expression) +//              ::= nx <expression>                                      # noexcept (expression) +//              ::= <template-param> +//              ::= <function-param> +//              ::= dt <expression> <unresolved-name>                    # expr.name +//              ::= pt <expression> <unresolved-name>                    # expr->name +//              ::= ds <expression> <expression>                         # expr.*expr +//              ::= sZ <template-param>                                  # size of a parameter pack +//              ::= sZ <function-param>                                  # size of a function parameter pack +//              ::= sP <template-arg>* E                                 # sizeof...(T), size of a captured template parameter pack from an alias template +//              ::= sp <expression>                                      # pack expansion +//              ::= tw <expression>                                      # throw expression +//              ::= tr                                                   # throw with no operand (rethrow) +//              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p), +//                                                                       # freestanding dependent name (e.g., T::x), +//                                                                       # objectless nonstatic member reference +//              ::= fL <binary-operator-name> <expression> <expression> +//              ::= fR <binary-operator-name> <expression> <expression> +//              ::= fl <binary-operator-name> <expression> +//              ::= fr <binary-operator-name> <expression> +//              ::= <expr-primary> +Node *Db::parseExpr() { +  bool Global = consumeIf("gs"); +  if (numLeft() < 2) +    return nullptr; + +  switch (*First) { +  case 'L': +    return parseExprPrimary(); +  case 'T': +    return parseTemplateParam(); +  case 'f': { +    // Disambiguate a fold expression from a <function-param>. +    if (look(1) == 'p' || (look(1) == 'L' && std::isdigit(look(2)))) +      return parseFunctionParam(); +    return parseFoldExpr(); +  } +  case 'a': +    switch (First[1]) { +    case 'a': +      First += 2; +      return parseBinaryExpr("&&"); +    case 'd': +      First += 2; +      return parsePrefixExpr("&"); +    case 'n': +      First += 2; +      return parseBinaryExpr("&"); +    case 'N': +      First += 2; +      return parseBinaryExpr("&="); +    case 'S': +      First += 2; +      return parseBinaryExpr("="); +    case 't': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      return make<EnclosingExpr>("alignof (", Ty, ")");      } -    case 'Z': { -      const char *t1 = parse_local_name(t0, last, db, ends_with_template_args); -      if (t1 != t0) -        first = t1; -      break; +    case 'z': { +      First += 2; +      Node *Ty = parseExpr(); +      if (Ty == nullptr) +        return nullptr; +      return make<EnclosingExpr>("alignof (", Ty, ")");      } -    default: { -      const char *t1 = parse_unscoped_name(t0, last, db); -      if (t1 != t0) { -        if (t1 != last && -            *t1 == 'I') // <unscoped-template-name> <template-args> -        { -          if (db.names.empty()) -            return first; -          db.subs.push_back(typename C::sub_type(1, db.names.back())); -          t0 = t1; -          t1 = parse_template_args(t0, last, db); -          if (t1 != t0) { -            if (db.names.size() < 2) -              return first; -            auto tmp = db.names.back().move_full(); -            db.names.pop_back(); -            if (db.names.empty()) -              return first; -            db.names.back().first += tmp; -            first = t1; -            if (ends_with_template_args) -              *ends_with_template_args = true; -          } -        } else // <unscoped-name> -          first = t1; -      } else { // try <substitution> <template-args> -        t1 = parse_substitution(t0, last, db); -        if (t1 != t0 && t1 != last && *t1 == 'I') { -          t0 = t1; -          t1 = parse_template_args(t0, last, db); -          if (t1 != t0) { -            if (db.names.size() < 2) -              return first; -            auto tmp = db.names.back().move_full(); -            db.names.pop_back(); -            if (db.names.empty()) -              return first; -            db.names.back().first += tmp; -            first = t1; -            if (ends_with_template_args) -              *ends_with_template_args = true; -          } -        } +    } +    return nullptr; +  case 'c': +    switch (First[1]) { +    // cc <type> <expression>                               # const_cast<type>(expression) +    case 'c': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return Ty; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<CastExpr>("const_cast", Ty, Ex); +    } +    // cl <expression>+ E                                   # call +    case 'l': { +      First += 2; +      Node *Callee = parseExpr(); +      if (Callee == nullptr) +        return Callee; +      size_t ExprsBegin = Names.size(); +      while (!consumeIf('E')) { +        Node *E = parseExpr(); +        if (E == nullptr) +          return E; +        Names.push_back(E);        } -      break; +      return make<CallExpr>(Callee, popTrailingNodeArray(ExprsBegin)); +    } +    case 'm': +      First += 2; +      return parseBinaryExpr(","); +    case 'o': +      First += 2; +      return parsePrefixExpr("~"); +    case 'v': +      return parseConversionExpr(); +    } +    return nullptr; +  case 'd': +    switch (First[1]) { +    case 'a': { +      First += 2; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<DeleteExpr>(Ex, Global, /*is_array=*/true); +    } +    case 'c': { +      First += 2; +      Node *T = parseType(); +      if (T == nullptr) +        return T; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<CastExpr>("dynamic_cast", T, Ex);      } +    case 'e': +      First += 2; +      return parsePrefixExpr("*"); +    case 'l': { +      First += 2; +      Node *E = parseExpr(); +      if (E == nullptr) +        return E; +      return make<DeleteExpr>(E, Global, /*is_array=*/false); +    } +    case 'n': +      return parseUnresolvedName(); +    case 's': { +      First += 2; +      Node *LHS = parseExpr(); +      if (LHS == nullptr) +        return nullptr; +      Node *RHS = parseExpr(); +      if (RHS == nullptr) +        return nullptr; +      return make<MemberExpr>(LHS, ".*", RHS); +    } +    case 't': { +      First += 2; +      Node *LHS = parseExpr(); +      if (LHS == nullptr) +        return LHS; +      Node *RHS = parseExpr(); +      if (RHS == nullptr) +        return nullptr; +      return make<MemberExpr>(LHS, ".", RHS); +    } +    case 'v': +      First += 2; +      return parseBinaryExpr("/"); +    case 'V': +      First += 2; +      return parseBinaryExpr("/="); +    } +    return nullptr; +  case 'e': +    switch (First[1]) { +    case 'o': +      First += 2; +      return parseBinaryExpr("^"); +    case 'O': +      First += 2; +      return parseBinaryExpr("^="); +    case 'q': +      First += 2; +      return parseBinaryExpr("==");      } +    return nullptr; +  case 'g': +    switch (First[1]) { +    case 'e': +      First += 2; +      return parseBinaryExpr(">="); +    case 't': +      First += 2; +      return parseBinaryExpr(">"); +    } +    return nullptr; +  case 'i': +    switch (First[1]) { +    case 'x': { +      First += 2; +      Node *Base = parseExpr(); +      if (Base == nullptr) +        return nullptr; +      Node *Index = parseExpr(); +      if (Index == nullptr) +        return Index; +      return make<ArraySubscriptExpr>(Base, Index); +    } +    case 'l': { +      First += 2; +      size_t InitsBegin = Names.size(); +      while (!consumeIf('E')) { +        Node *E = parseBracedExpr(); +        if (E == nullptr) +          return nullptr; +        Names.push_back(E); +      } +      return make<InitListExpr>(nullptr, popTrailingNodeArray(InitsBegin)); +    } +    } +    return nullptr; +  case 'l': +    switch (First[1]) { +    case 'e': +      First += 2; +      return parseBinaryExpr("<="); +    case 's': +      First += 2; +      return parseBinaryExpr("<<"); +    case 'S': +      First += 2; +      return parseBinaryExpr("<<="); +    case 't': +      First += 2; +      return parseBinaryExpr("<"); +    } +    return nullptr; +  case 'm': +    switch (First[1]) { +    case 'i': +      First += 2; +      return parseBinaryExpr("-"); +    case 'I': +      First += 2; +      return parseBinaryExpr("-="); +    case 'l': +      First += 2; +      return parseBinaryExpr("*"); +    case 'L': +      First += 2; +      return parseBinaryExpr("*="); +    case 'm': +      First += 2; +      if (consumeIf('_')) +        return parsePrefixExpr("--"); +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return nullptr; +      return make<PostfixExpr>(Ex, "--"); +    } +    return nullptr; +  case 'n': +    switch (First[1]) { +    case 'a': +    case 'w': +      return parseNewExpr(); +    case 'e': +      First += 2; +      return parseBinaryExpr("!="); +    case 'g': +      First += 2; +      return parsePrefixExpr("-"); +    case 't': +      First += 2; +      return parsePrefixExpr("!"); +    case 'x': +      First += 2; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<EnclosingExpr>("noexcept (", Ex, ")"); +    } +    return nullptr; +  case 'o': +    switch (First[1]) { +    case 'n': +      return parseUnresolvedName(); +    case 'o': +      First += 2; +      return parseBinaryExpr("||"); +    case 'r': +      First += 2; +      return parseBinaryExpr("|"); +    case 'R': +      First += 2; +      return parseBinaryExpr("|="); +    } +    return nullptr; +  case 'p': +    switch (First[1]) { +    case 'm': +      First += 2; +      return parseBinaryExpr("->*"); +    case 'l': +      First += 2; +      return parseBinaryExpr("+"); +    case 'L': +      First += 2; +      return parseBinaryExpr("+="); +    case 'p': { +      First += 2; +      if (consumeIf('_')) +        return parsePrefixExpr("++"); +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<PostfixExpr>(Ex, "++"); +    } +    case 's': +      First += 2; +      return parsePrefixExpr("+"); +    case 't': { +      First += 2; +      Node *L = parseExpr(); +      if (L == nullptr) +        return nullptr; +      Node *R = parseExpr(); +      if (R == nullptr) +        return nullptr; +      return make<MemberExpr>(L, "->", R); +    } +    } +    return nullptr; +  case 'q': +    if (First[1] == 'u') { +      First += 2; +      Node *Cond = parseExpr(); +      if (Cond == nullptr) +        return nullptr; +      Node *LHS = parseExpr(); +      if (LHS == nullptr) +        return nullptr; +      Node *RHS = parseExpr(); +      if (RHS == nullptr) +        return nullptr; +      return make<ConditionalExpr>(Cond, LHS, RHS); +    } +    return nullptr; +  case 'r': +    switch (First[1]) { +    case 'c': { +      First += 2; +      Node *T = parseType(); +      if (T == nullptr) +        return T; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<CastExpr>("reinterpret_cast", T, Ex); +    } +    case 'm': +      First += 2; +      return parseBinaryExpr("%"); +    case 'M': +      First += 2; +      return parseBinaryExpr("%="); +    case 's': +      First += 2; +      return parseBinaryExpr(">>"); +    case 'S': +      First += 2; +      return parseBinaryExpr(">>="); +    } +    return nullptr; +  case 's': +    switch (First[1]) { +    case 'c': { +      First += 2; +      Node *T = parseType(); +      if (T == nullptr) +        return T; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<CastExpr>("static_cast", T, Ex); +    } +    case 'p': { +      First += 2; +      Node *Child = parseExpr(); +      if (Child == nullptr) +        return nullptr; +      return make<ParameterPackExpansion>(Child); +    } +    case 'r': +      return parseUnresolvedName(); +    case 't': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return Ty; +      return make<EnclosingExpr>("sizeof (", Ty, ")"); +    } +    case 'z': { +      First += 2; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<EnclosingExpr>("sizeof (", Ex, ")"); +    } +    case 'Z': +      First += 2; +      if (look() == 'T') { +        Node *R = parseTemplateParam(); +        if (R == nullptr) +          return nullptr; +        return make<SizeofParamPackExpr>(R); +      } else if (look() == 'f') { +        Node *FP = parseFunctionParam(); +        if (FP == nullptr) +          return nullptr; +        return make<EnclosingExpr>("sizeof... (", FP, ")"); +      } +      return nullptr; +    case 'P': { +      First += 2; +      size_t ArgsBegin = Names.size(); +      while (!consumeIf('E')) { +        Node *Arg = parseTemplateArg(); +        if (Arg == nullptr) +          return nullptr; +        Names.push_back(Arg); +      } +      return make<EnclosingExpr>( +          "sizeof... (", make<NodeArrayNode>(popTrailingNodeArray(ArgsBegin)), +          ")"); +    } +    } +    return nullptr; +  case 't': +    switch (First[1]) { +    case 'e': { +      First += 2; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return Ex; +      return make<EnclosingExpr>("typeid (", Ex, ")"); +    } +    case 'i': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return Ty; +      return make<EnclosingExpr>("typeid (", Ty, ")"); +    } +    case 'l': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      size_t InitsBegin = Names.size(); +      while (!consumeIf('E')) { +        Node *E = parseBracedExpr(); +        if (E == nullptr) +          return nullptr; +        Names.push_back(E); +      } +      return make<InitListExpr>(Ty, popTrailingNodeArray(InitsBegin)); +    } +    case 'r': +      First += 2; +      return make<NameType>("throw"); +    case 'w': { +      First += 2; +      Node *Ex = parseExpr(); +      if (Ex == nullptr) +        return nullptr; +      return make<ThrowExpr>(Ex); +    } +    } +    return nullptr; +  case '1': +  case '2': +  case '3': +  case '4': +  case '5': +  case '6': +  case '7': +  case '8': +  case '9': +    return parseUnresolvedName();    } -  return first; +  return nullptr;  }  // <call-offset> ::= h <nv-offset> _ @@ -3811,26 +4380,15 @@ static const char *parse_name(const char *first, const char *last, C &db,  //  // <v-offset>  ::= <offset number> _ <virtual offset number>  //               # virtual base override, with vcall offset - -static const char *parse_call_offset(const char *first, const char *last) { -  if (first != last) { -    switch (*first) { -    case 'h': { -      const char *t = parse_number(first + 1, last); -      if (t != first + 1 && t != last && *t == '_') -        first = t + 1; -    } break; -    case 'v': { -      const char *t = parse_number(first + 1, last); -      if (t != first + 1 && t != last && *t == '_') { -        const char *t2 = parse_number(++t, last); -        if (t2 != t && t2 != last && *t2 == '_') -          first = t2 + 1; -      } -    } break; -    } -  } -  return first; +bool Db::parseCallOffset() { +  // Just scan through the call offset, we never add this information into the +  // output. +  if (consumeIf('h')) +    return parseNumber(true).empty() || !consumeIf('_'); +  if (consumeIf('v')) +    return parseNumber(true).empty() || !consumeIf('_') || +           parseNumber(true).empty() || !consumeIf('_'); +  return true;  }  // <special-name> ::= TV <type>    # virtual table @@ -3843,471 +4401,800 @@ static const char *parse_call_offset(const char *first, const char *last) {  //                    # second call-offset is result adjustment  //                ::= T <call-offset> <base encoding>  //                    # base is the nominal target function of thunk -//                ::= GV <object name> # Guard variable for one-time -//                initialization +//                ::= GV <object name> # Guard variable for one-time initialization  //                                     # No <type>  //                ::= TW <object name> # Thread-local wrapper  //                ::= TH <object name> # Thread-local initialization -//      extension ::= TC <first type> <number> _ <second type> # construction -//      vtable for second-in-first +//                ::= GR <object name> _             # First temporary +//                ::= GR <object name> <seq-id> _    # Subsequent temporaries +//      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first  //      extension ::= GR <object name> # reference temporary for object +Node *Db::parseSpecialName() { +  switch (look()) { +  case 'T': +    switch (look(1)) { +    // TV <type>    # virtual table +    case 'V': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      return make<SpecialName>("vtable for ", Ty); +    } +    // TT <type>    # VTT structure (construction vtable index) +    case 'T': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      return make<SpecialName>("VTT for ", Ty); +    } +    // TI <type>    # typeinfo structure +    case 'I': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      return make<SpecialName>("typeinfo for ", Ty); +    } +    // TS <type>    # typeinfo name (null-terminated byte string) +    case 'S': { +      First += 2; +      Node *Ty = parseType(); +      if (Ty == nullptr) +        return nullptr; +      return make<SpecialName>("typeinfo name for ", Ty); +    } +    // Tc <call-offset> <call-offset> <base encoding> +    case 'c': { +      First += 2; +      if (parseCallOffset() || parseCallOffset()) +        return nullptr; +      Node *Encoding = parseEncoding(); +      if (Encoding == nullptr) +        return nullptr; +      return make<SpecialName>("covariant return thunk to ", Encoding); +    } +    // extension ::= TC <first type> <number> _ <second type> +    //               # construction vtable for second-in-first +    case 'C': { +      First += 2; +      Node *FirstType = parseType(); +      if (FirstType == nullptr) +        return nullptr; +      if (parseNumber(true).empty() || !consumeIf('_')) +        return nullptr; +      Node *SecondType = parseType(); +      if (SecondType == nullptr) +        return nullptr; +      return make<CtorVtableSpecialName>(SecondType, FirstType); +    } +    // TW <object name> # Thread-local wrapper +    case 'W': { +      First += 2; +      Node *Name = parseName(); +      if (Name == nullptr) +        return nullptr; +      return make<SpecialName>("thread-local wrapper routine for ", Name); +    } +    // TH <object name> # Thread-local initialization +    case 'H': { +      First += 2; +      Node *Name = parseName(); +      if (Name == nullptr) +        return nullptr; +      return make<SpecialName>("thread-local initialization routine for ", Name); +    } +    // T <call-offset> <base encoding> +    default: { +      ++First; +      bool IsVirt = look() == 'v'; +      if (parseCallOffset()) +        return nullptr; +      Node *BaseEncoding = parseEncoding(); +      if (BaseEncoding == nullptr) +        return nullptr; +      if (IsVirt) +        return make<SpecialName>("virtual thunk to ", BaseEncoding); +      else +        return make<SpecialName>("non-virtual thunk to ", BaseEncoding); +    } +    } +  case 'G': +    switch (look(1)) { +    // GV <object name> # Guard variable for one-time initialization +    case 'V': { +      First += 2; +      Node *Name = parseName(); +      if (Name == nullptr) +        return nullptr; +      return make<SpecialName>("guard variable for ", Name); +    } +    // GR <object name> # reference temporary for object +    // GR <object name> _             # First temporary +    // GR <object name> <seq-id> _    # Subsequent temporaries +    case 'R': { +      First += 2; +      Node *Name = parseName(); +      if (Name == nullptr) +        return nullptr; +      size_t Count; +      bool ParsedSeqId = !parseSeqId(&Count); +      if (!consumeIf('_') && ParsedSeqId) +        return nullptr; +      return make<SpecialName>("reference temporary for ", Name); +    } +    } +  } +  return nullptr; +} -template <class C> -static const char *parse_special_name(const char *first, const char *last, -                                      C &db) { -  if (last - first > 2) { -    const char *t; -    switch (*first) { -    case 'T': -      switch (first[1]) { -      case 'V': -        // TV <type>    # virtual table -        t = parse_type(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "vtable for "); -          first = t; -        } -        break; -      case 'T': -        // TT <type>    # VTT structure (construction vtable index) -        t = parse_type(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "VTT for "); -          first = t; -        } -        break; -      case 'I': -        // TI <type>    # typeinfo structure -        t = parse_type(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "typeinfo for "); -          first = t; -        } -        break; -      case 'S': -        // TS <type>    # typeinfo name (null-terminated byte string) -        t = parse_type(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "typeinfo name for "); -          first = t; -        } -        break; -      case 'c': -        // Tc <call-offset> <call-offset> <base encoding> -        { -          const char *t0 = parse_call_offset(first + 2, last); -          if (t0 == first + 2) -            break; -          const char *t1 = parse_call_offset(t0, last); -          if (t1 == t0) -            break; -          t = parse_encoding(t1, last, db); -          if (t != t1) { -            if (db.names.empty()) -              return first; -            db.names.back().first.insert(0, "covariant return thunk to "); -            first = t; -          } -        } -        break; -      case 'C': -        // extension ::= TC <first type> <number> _ <second type> # construction -        // vtable for second-in-first -        t = parse_type(first + 2, last, db); -        if (t != first + 2) { -          const char *t0 = parse_number(t, last); -          if (t0 != t && t0 != last && *t0 == '_') { -            const char *t1 = parse_type(++t0, last, db); -            if (t1 != t0) { -              if (db.names.size() < 2) -                return first; -              auto left = db.names.back().move_full(); -              db.names.pop_back(); -              if (db.names.empty()) -                return first; -              db.names.back().first = "construction vtable for " + -                                      std::move(left) + "-in-" + -                                      db.names.back().move_full(); -              first = t1; -            } -          } -        } -        break; -      case 'W': -        // TW <object name> # Thread-local wrapper -        t = parse_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "thread-local wrapper routine for "); -          first = t; -        } -        break; -      case 'H': -        // TH <object name> # Thread-local initialization -        t = parse_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert( -              0, "thread-local initialization routine for "); -          first = t; -        } -        break; -      default: -        // T <call-offset> <base encoding> -        { -          const char *t0 = parse_call_offset(first + 1, last); -          if (t0 == first + 1) -            break; -          t = parse_encoding(t0, last, db); -          if (t != t0) { -            if (db.names.empty()) -              return first; -            if (first[1] == 'v') { -              db.names.back().first.insert(0, "virtual thunk to "); -              first = t; -            } else { -              db.names.back().first.insert(0, "non-virtual thunk to "); -              first = t; -            } -          } -        } -        break; -      } -      break; -    case 'G': -      switch (first[1]) { -      case 'V': -        // GV <object name> # Guard variable for one-time initialization -        t = parse_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "guard variable for "); -          first = t; -        } -        break; -      case 'R': -        // extension ::= GR <object name> # reference temporary for object -        t = parse_name(first + 2, last, db); -        if (t != first + 2) { -          if (db.names.empty()) -            return first; -          db.names.back().first.insert(0, "reference temporary for "); -          first = t; -        } -        break; -      } -      break; +// <encoding> ::= <function name> <bare-function-type> +//            ::= <data name> +//            ::= <special-name> +Node *Db::parseEncoding() { +  if (look() == 'G' || look() == 'T') +    return parseSpecialName(); + +  auto IsEndOfEncoding = [&] { +    // The set of chars that can potentially follow an <encoding> (none of which +    // can start a <type>). Enumerating these allows us to avoid speculative +    // parsing. +    return numLeft() == 0 || look() == 'E' || look() == '.' || look() == '_'; +  }; + +  NameState NameInfo(this); +  Node *Name = parseName(&NameInfo); +  if (Name == nullptr) +    return nullptr; + +  if (resolveForwardTemplateRefs(NameInfo)) +    return nullptr; + +  if (IsEndOfEncoding()) +    return Name; + +  Node *Attrs = nullptr; +  if (consumeIf("Ua9enable_ifI")) { +    size_t BeforeArgs = Names.size(); +    while (!consumeIf('E')) { +      Node *Arg = parseTemplateArg(); +      if (Arg == nullptr) +        return nullptr; +      Names.push_back(Arg);      } +    Attrs = make<EnableIfAttr>(popTrailingNodeArray(BeforeArgs)); +  } + +  Node *ReturnType = nullptr; +  if (!NameInfo.CtorDtorConversion && NameInfo.EndsWithTemplateArgs) { +    ReturnType = parseType(); +    if (ReturnType == nullptr) +      return nullptr;    } -  return first; + +  if (consumeIf('v')) +    return make<FunctionEncoding>(ReturnType, Name, NodeArray(), +                                  Attrs, NameInfo.CVQualifiers, +                                  NameInfo.ReferenceQualifier); + +  size_t ParamsBegin = Names.size(); +  do { +    Node *Ty = parseType(); +    if (Ty == nullptr) +      return nullptr; +    Names.push_back(Ty); +  } while (!IsEndOfEncoding()); + +  return make<FunctionEncoding>(ReturnType, Name, +                                popTrailingNodeArray(ParamsBegin), +                                Attrs, NameInfo.CVQualifiers, +                                NameInfo.ReferenceQualifier);  } -namespace { -template <class T> class save_value { -  T &restore_; -  T original_value_; +template <class Float> +struct FloatData; -public: -  save_value(T &restore) : restore_(restore), original_value_(restore) {} +template <> +struct FloatData<float> +{ +    static const size_t mangled_size = 8; +    static const size_t max_demangled_size = 24; +    static constexpr const char* spec = "%af"; +}; -  ~save_value() { restore_ = std::move(original_value_); } +constexpr const char* FloatData<float>::spec; -  save_value(const save_value &) = delete; -  save_value &operator=(const save_value &) = delete; +template <> +struct FloatData<double> +{ +    static const size_t mangled_size = 16; +    static const size_t max_demangled_size = 32; +    static constexpr const char* spec = "%a";  }; + +constexpr const char* FloatData<double>::spec; + +template <> +struct FloatData<long double> +{ +#if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) || \ +    defined(__wasm__) +    static const size_t mangled_size = 32; +#elif defined(__arm__) || defined(__mips__) || defined(__hexagon__) +    static const size_t mangled_size = 16; +#else +    static const size_t mangled_size = 20;  // May need to be adjusted to 16 or 24 on other platforms +#endif +    static const size_t max_demangled_size = 40; +    static constexpr const char *spec = "%LaL"; +}; + +constexpr const char *FloatData<long double>::spec; + +template <class Float> Node *Db::parseFloatingLiteral() { +  const size_t N = FloatData<Float>::mangled_size; +  if (numLeft() <= N) +    return nullptr; +  StringView Data(First, First + N); +  for (char C : Data) +    if (!std::isxdigit(C)) +      return nullptr; +  First += N; +  if (!consumeIf('E')) +    return nullptr; +  return make<FloatExpr<Float>>(Data);  } -// <encoding> ::= <function name> <bare-function-type> -//            ::= <data name> -//            ::= <special-name> +// <seq-id> ::= <0-9A-Z>+ +bool Db::parseSeqId(size_t *Out) { +  if (!(look() >= '0' && look() <= '9') && +      !(look() >= 'A' && look() <= 'Z')) +    return true; + +  size_t Id = 0; +  while (true) { +    if (look() >= '0' && look() <= '9') { +      Id *= 36; +      Id += static_cast<size_t>(look() - '0'); +    } else if (look() >= 'A' && look() <= 'Z') { +      Id *= 36; +      Id += static_cast<size_t>(look() - 'A') + 10; +    } else { +      *Out = Id; +      return false; +    } +    ++First; +  } +} + +// <substitution> ::= S <seq-id> _ +//                ::= S_ +// <substitution> ::= Sa # ::std::allocator +// <substitution> ::= Sb # ::std::basic_string +// <substitution> ::= Ss # ::std::basic_string < char, +//                                               ::std::char_traits<char>, +//                                               ::std::allocator<char> > +// <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> > +// <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> > +// <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> > +Node *Db::parseSubstitution() { +  if (!consumeIf('S')) +    return nullptr; -template <class C> -static const char *parse_encoding(const char *first, const char *last, C &db) { -  if (first != last) { -    save_value<decltype(db.encoding_depth)> su(db.encoding_depth); -    ++db.encoding_depth; -    save_value<decltype(db.tag_templates)> sb(db.tag_templates); -    if (db.encoding_depth > 1) -      db.tag_templates = true; -    save_value<decltype(db.parsed_ctor_dtor_cv)> sp(db.parsed_ctor_dtor_cv); -    db.parsed_ctor_dtor_cv = false; -    switch (*first) { -    case 'G': -    case 'T': -      first = parse_special_name(first, last, db); +  if (std::islower(look())) { +    Node *SpecialSub; +    switch (look()) { +    case 'a': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::allocator);        break; -    default: { -      bool ends_with_template_args = false; -      const char *t = parse_name(first, last, db, &ends_with_template_args); -      unsigned cv = db.cv; -      unsigned ref = db.ref; -      if (t != first) { -        if (t != last && *t != 'E' && *t != '.') { -          save_value<bool> sb2(db.tag_templates); -          db.tag_templates = false; -          const char *t2; -          std::string ret2; -          if (db.names.empty()) -            return first; -          const std::string &nm = db.names.back().first; -          if (nm.empty()) -            return first; -          if (!db.parsed_ctor_dtor_cv && ends_with_template_args) { -            t2 = parse_type(t, last, db); -            if (t2 == t) -              return first; -            if (db.names.size() < 2) -              return first; -            auto ret1 = std::move(db.names.back().first); -            ret2 = std::move(db.names.back().second); -            if (ret2.empty()) -              ret1 += ' '; -            db.names.pop_back(); -            if (db.names.empty()) -              return first; - -            db.names.back().first.insert(0, ret1); -            t = t2; -          } -          db.names.back().first += '('; -          if (t != last && *t == 'v') { -            ++t; -          } else { -            bool first_arg = true; -            while (true) { -              size_t k0 = db.names.size(); -              t2 = parse_type(t, last, db); -              size_t k1 = db.names.size(); -              if (t2 == t) -                break; -              if (k1 > k0) { -                std::string tmp; -                for (size_t k = k0; k < k1; ++k) { -                  if (!tmp.empty()) -                    tmp += ", "; -                  tmp += db.names[k].move_full(); -                } -                for (size_t k = k0; k < k1; ++k) { -                  if (db.names.empty()) -                    return first; -                  db.names.pop_back(); -                } -                if (!tmp.empty()) { -                  if (db.names.empty()) -                    return first; -                  if (!first_arg) -                    db.names.back().first += ", "; -                  else -                    first_arg = false; -                  db.names.back().first += tmp; -                } -              } -              t = t2; -            } -          } -          if (db.names.empty()) -            return first; -          db.names.back().first += ')'; -          if (cv & CV_const) -            db.names.back().first.append(" const"); -          if (cv & CV_volatile) -            db.names.back().first.append(" volatile"); -          if (cv & CV_restrict) -            db.names.back().first.append(" restrict"); -          if (ref == 1) -            db.names.back().first.append(" &"); -          else if (ref == 2) -            db.names.back().first.append(" &&"); -          db.names.back().first += ret2; -          first = t; -        } else -          first = t; -      } +    case 'b': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::basic_string);        break; +    case 's': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::string); +      break; +    case 'i': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::istream); +      break; +    case 'o': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::ostream); +      break; +    case 'd': +      ++First; +      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::iostream); +      break; +    default: +      return nullptr;      } +    // Itanium C++ ABI 5.1.2: If a name that would use a built-in <substitution> +    // has ABI tags, the tags are appended to the substitution; the result is a +    // substitutable component. +    Node *WithTags = parseAbiTags(SpecialSub); +    if (WithTags != SpecialSub) { +      Subs.push_back(WithTags); +      SpecialSub = WithTags;      } +    return SpecialSub;    } -  return first; + +  //                ::= S_ +  if (consumeIf('_')) { +    if (Subs.empty()) +      return nullptr; +    return Subs[0]; +  } + +  //                ::= S <seq-id> _ +  size_t Index = 0; +  if (parseSeqId(&Index)) +    return nullptr; +  ++Index; +  if (!consumeIf('_') || Index >= Subs.size()) +    return nullptr; +  return Subs[Index];  } -// _block_invoke -// _block_invoke<decimal-digit>+ -// _block_invoke_<decimal-digit>+ - -template <class C> -static const char *parse_block_invoke(const char *first, const char *last, -                                      C &db) { -  if (last - first >= 13) { -    const char test[] = "_block_invoke"; -    const char *t = first; -    for (int i = 0; i < 13; ++i, ++t) { -      if (*t != test[i]) -        return first; -    } -    if (t != last) { -      if (*t == '_') { -        // must have at least 1 decimal digit -        if (++t == last || !std::isdigit(*t)) -          return first; -        ++t; -      } -      // parse zero or more digits -      while (t != last && isdigit(*t)) -        ++t; +// <template-param> ::= T_    # first template parameter +//                  ::= T <parameter-2 non-negative number> _ +Node *Db::parseTemplateParam() { +  if (!consumeIf('T')) +    return nullptr; + +  size_t Index = 0; +  if (!consumeIf('_')) { +    if (parsePositiveInteger(&Index)) +      return nullptr; +    ++Index; +    if (!consumeIf('_')) +      return nullptr; +  } + +  // Itanium ABI 5.1.8: In a generic lambda, uses of auto in the parameter list +  // are mangled as the corresponding artificial template type parameter. +  if (ParsingLambdaParams) +    return make<NameType>("auto"); + +  // If we're in a context where this <template-param> refers to a +  // <template-arg> further ahead in the mangled name (currently just conversion +  // operator types), then we should only look it up in the right context. +  if (PermitForwardTemplateReferences) { +    ForwardTemplateRefs.push_back(make<ForwardTemplateReference>(Index)); +    return ForwardTemplateRefs.back(); +  } + +  if (Index >= TemplateParams.size()) +    return nullptr; +  return TemplateParams[Index]; +} + +// <template-arg> ::= <type>                    # type or template +//                ::= X <expression> E          # expression +//                ::= <expr-primary>            # simple expressions +//                ::= J <template-arg>* E       # argument pack +//                ::= LZ <encoding> E           # extension +Node *Db::parseTemplateArg() { +  switch (look()) { +  case 'X': { +    ++First; +    Node *Arg = parseExpr(); +    if (Arg == nullptr || !consumeIf('E')) +      return nullptr; +    return Arg; +  } +  case 'J': { +    ++First; +    size_t ArgsBegin = Names.size(); +    while (!consumeIf('E')) { +      Node *Arg = parseTemplateArg(); +      if (Arg == nullptr) +        return nullptr; +      Names.push_back(Arg);      } -    if (db.names.empty()) -      return first; -    db.names.back().first.insert(0, "invocation function for block in "); -    first = t; +    NodeArray Args = popTrailingNodeArray(ArgsBegin); +    return make<TemplateArgumentPack>(Args); +  } +  case 'L': { +    //                ::= LZ <encoding> E           # extension +    if (look(1) == 'Z') { +      First += 2; +      Node *Arg = parseEncoding(); +      if (Arg == nullptr || !consumeIf('E')) +        return nullptr; +      return Arg; +    } +    //                ::= <expr-primary>            # simple expressions +    return parseExprPrimary(); +  } +  default: +    return parseType();    } -  return first;  } -// extension -// <dot-suffix> := .<anything and everything> +// <template-args> ::= I <template-arg>* E +//     extension, the abi says <template-arg>+ +Node *Db::parseTemplateArgs(bool TagTemplates) { +  if (!consumeIf('I')) +    return nullptr; -template <class C> -static const char *parse_dot_suffix(const char *first, const char *last, -                                    C &db) { -  if (first != last && *first == '.') { -    if (db.names.empty()) -      return first; -    db.names.back().first += " (" + std::string(first, last) + ")"; -    first = last; +  // <template-params> refer to the innermost <template-args>. Clear out any +  // outer args that we may have inserted into TemplateParams. +  if (TagTemplates) +    TemplateParams.clear(); + +  size_t ArgsBegin = Names.size(); +  while (!consumeIf('E')) { +    if (TagTemplates) { +      auto OldParams = std::move(TemplateParams); +      Node *Arg = parseTemplateArg(); +      TemplateParams = std::move(OldParams); +      if (Arg == nullptr) +        return nullptr; +      Names.push_back(Arg); +      Node *TableEntry = Arg; +      if (Arg->getKind() == Node::KTemplateArgumentPack) { +        TableEntry = make<ParameterPack>( +            static_cast<TemplateArgumentPack*>(TableEntry)->getElements()); +      } +      TemplateParams.push_back(TableEntry); +    } else { +      Node *Arg = parseTemplateArg(); +      if (Arg == nullptr) +        return nullptr; +      Names.push_back(Arg); +    }    } -  return first; +  return make<TemplateArgs>(popTrailingNodeArray(ArgsBegin)); +} + +// <discriminator> := _ <non-negative number>      # when number < 10 +//                 := __ <non-negative number> _   # when number >= 10 +//  extension      := decimal-digit+               # at the end of string + +const char* +parse_discriminator(const char* first, const char* last) +{ +    // parse but ignore discriminator +    if (first != last) +    { +        if (*first == '_') +        { +            const char* t1 = first+1; +            if (t1 != last) +            { +                if (std::isdigit(*t1)) +                    first = t1+1; +                else if (*t1 == '_') +                { +                    for (++t1; t1 != last && std::isdigit(*t1); ++t1) +                        ; +                    if (t1 != last && *t1 == '_') +                        first = t1 + 1; +                } +            } +        } +        else if (std::isdigit(*first)) +        { +            const char* t1 = first+1; +            for (; t1 != last && std::isdigit(*t1); ++t1) +                ; +            if (t1 == last) +                first = last; +        } +    } +    return first;  } -// <block-involcaton-function> ___Z<encoding>_block_invoke -// <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+ -// <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+ -// <mangled-name> ::= _Z<encoding> +// <mangled-name> ::= _Z <encoding>  //                ::= <type> +// extension      ::= ___Z <encoding> _block_invoke +// extension      ::= ___Z <encoding> _block_invoke<decimal-digit>+ +// extension      ::= ___Z <encoding> _block_invoke_<decimal-digit>+ +Node *Db::parse() { +  if (consumeIf("_Z")) { +    Node *Encoding = parseEncoding(); +    if (Encoding == nullptr) +      return nullptr; +    if (look() == '.') { +      Encoding = make<DotSuffix>(Encoding, StringView(First, Last)); +      First = Last; +    } +    if (numLeft() != 0) +      return nullptr; +    return Encoding; +  } -template <class C> -static void demangle(const char *first, const char *last, C &db, int &status) { -  if (first >= last) { -    status = invalid_mangled_name; -    return; -  } -  if (*first == '_') { -    if (last - first >= 4) { -      if (first[1] == 'Z') { -        const char *t = parse_encoding(first + 2, last, db); -        if (t != first + 2 && t != last && *t == '.') -          t = parse_dot_suffix(t, last, db); -        if (t != last) -          status = invalid_mangled_name; -      } else if (first[1] == '_' && first[2] == '_' && first[3] == 'Z') { -        const char *t = parse_encoding(first + 4, last, db); -        if (t != first + 4 && t != last) { -          const char *t1 = parse_block_invoke(t, last, db); -          if (t1 != last) -            status = invalid_mangled_name; -        } else -          status = invalid_mangled_name; -      } else -        status = invalid_mangled_name; -    } else -      status = invalid_mangled_name; -  } else { -    const char *t = parse_type(first, last, db); -    if (t != last) -      status = invalid_mangled_name; -  } -  if (status == success && db.names.empty()) -    status = invalid_mangled_name; +  if (consumeIf("___Z")) { +    Node *Encoding = parseEncoding(); +    if (Encoding == nullptr || !consumeIf("_block_invoke")) +      return nullptr; +    bool RequireNumber = consumeIf('_'); +    if (parseNumber().empty() && RequireNumber) +      return nullptr; +    if (numLeft() != 0) +      return nullptr; +    return make<SpecialName>("invocation function for block in ", Encoding); +  } + +  Node *Ty = parseType(); +  if (numLeft() != 0) +    return nullptr; +  return Ty;  } -namespace { -template <class StrT> struct string_pair { -  StrT first; -  StrT second; - -  string_pair() = default; -  string_pair(StrT f) : first(std::move(f)) {} -  string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {} -  template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {} - -  size_t size() const { return first.size() + second.size(); } -  bool empty() const { return first.empty() && second.empty(); } -  StrT full() const { return first + second; } -  StrT move_full() { return std::move(first) + std::move(second); } -}; +bool initializeOutputStream(char *Buf, size_t *N, OutputStream &S, +                            size_t InitSize) { +  size_t BufferSize; +  if (Buf == nullptr) { +    Buf = static_cast<char *>(std::malloc(InitSize)); +    if (Buf == nullptr) +      return true; +    BufferSize = InitSize; +  } else +    BufferSize = *N; -struct Db { -  typedef std::vector<string_pair<std::string>> sub_type; -  typedef std::vector<sub_type> template_param_type; -  sub_type names; -  template_param_type subs; -  std::vector<template_param_type> template_param; -  unsigned cv = 0; -  unsigned ref = 0; -  unsigned encoding_depth = 0; -  bool parsed_ctor_dtor_cv = false; -  bool tag_templates = true; -  bool fix_forward_references = false; -  bool try_to_parse_template_args = true; - -  Db() : subs(0, names), template_param(0, subs) {} -}; +  S.reset(Buf, BufferSize); +  return false;  } -char *llvm::itaniumDemangle(const char *mangled_name, char *buf, size_t *n, -                            int *status) { -  if (mangled_name == nullptr || (buf != nullptr && n == nullptr)) { -    if (status) -      *status = invalid_args; +}  // unnamed namespace + +char *llvm::itaniumDemangle(const char *MangledName, char *Buf, +                            size_t *N, int *Status) { +  if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) { +    if (Status) +      *Status = demangle_invalid_args;      return nullptr;    } -  size_t internal_size = buf != nullptr ? *n : 0; -  Db db; -  db.template_param.emplace_back(); -  int internal_status = success; -  size_t len = std::strlen(mangled_name); -  demangle(mangled_name, mangled_name + len, db, internal_status); -  if (internal_status == success && db.fix_forward_references && -      !db.template_param.empty() && !db.template_param.front().empty()) { -    db.fix_forward_references = false; -    db.tag_templates = false; -    db.names.clear(); -    db.subs.clear(); -    demangle(mangled_name, mangled_name + len, db, internal_status); -    if (db.fix_forward_references) -      internal_status = invalid_mangled_name; -  } -  if (internal_status == success) { -    size_t sz = db.names.back().size() + 1; -    if (sz > internal_size) { -      char *newbuf = static_cast<char *>(std::realloc(buf, sz)); -      if (newbuf == nullptr) { -        internal_status = memory_alloc_failure; -        buf = nullptr; -      } else { -        buf = newbuf; -        if (n != nullptr) -          *n = sz; -      } + +  int InternalStatus = demangle_success; +  Db Parser(MangledName, MangledName + std::strlen(MangledName)); +  OutputStream S; + +  Node *AST = Parser.parse(); + +  if (AST == nullptr) +    InternalStatus = demangle_invalid_mangled_name; +  else if (initializeOutputStream(Buf, N, S, 1024)) +    InternalStatus = demangle_memory_alloc_failure; +  else { +    assert(Parser.ForwardTemplateRefs.empty()); +    AST->print(S); +    S += '\0'; +    if (N != nullptr) +      *N = S.getCurrentPosition(); +    Buf = S.getBuffer(); +  } + +  if (Status) +    *Status = InternalStatus; +  return InternalStatus == demangle_success ? Buf : nullptr; +} + +namespace llvm { + +ItaniumPartialDemangler::ItaniumPartialDemangler() +    : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {} + +ItaniumPartialDemangler::~ItaniumPartialDemangler() { +  delete static_cast<Db *>(Context); +} + +ItaniumPartialDemangler::ItaniumPartialDemangler( +    ItaniumPartialDemangler &&Other) +    : RootNode(Other.RootNode), Context(Other.Context) { +  Other.Context = Other.RootNode = nullptr; +} + +ItaniumPartialDemangler &ItaniumPartialDemangler:: +operator=(ItaniumPartialDemangler &&Other) { +  std::swap(RootNode, Other.RootNode); +  std::swap(Context, Other.Context); +  return *this; +} + +// Demangle MangledName into an AST, storing it into this->RootNode. +bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) { +  Db *Parser = static_cast<Db *>(Context); +  size_t Len = std::strlen(MangledName); +  Parser->reset(MangledName, MangledName + Len); +  RootNode = Parser->parse(); +  return RootNode == nullptr; +} + +static char *printNode(Node *RootNode, char *Buf, size_t *N) { +  OutputStream S; +  if (initializeOutputStream(Buf, N, S, 128)) +    return nullptr; +  RootNode->print(S); +  S += '\0'; +  if (N != nullptr) +    *N = S.getCurrentPosition(); +  return S.getBuffer(); +} + +char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const { +  if (!isFunction()) +    return nullptr; + +  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName(); + +  while (true) { +    switch (Name->getKind()) { +    case Node::KAbiTagAttr: +      Name = static_cast<AbiTagAttr *>(Name)->Base; +      continue; +    case Node::KStdQualifiedName: +      Name = static_cast<StdQualifiedName *>(Name)->Child; +      continue; +    case Node::KNestedName: +      Name = static_cast<NestedName *>(Name)->Name; +      continue; +    case Node::KLocalName: +      Name = static_cast<LocalName *>(Name)->Entity; +      continue; +    case Node::KNameWithTemplateArgs: +      Name = static_cast<NameWithTemplateArgs *>(Name)->Name; +      continue; +    default: +      return printNode(Name, Buf, N);      } -    if (buf != nullptr) { -      db.names.back().first += db.names.back().second; -      std::memcpy(buf, db.names.back().first.data(), sz - 1); -      buf[sz - 1] = char(0); +  } +} + +char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf, +                                                          size_t *N) const { +  if (!isFunction()) +    return nullptr; +  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName(); + +  OutputStream S; +  if (initializeOutputStream(Buf, N, S, 128)) +    return nullptr; + + KeepGoingLocalFunction: +  while (true) { +    if (Name->getKind() == Node::KAbiTagAttr) { +      Name = static_cast<AbiTagAttr *>(Name)->Base; +      continue;      } -  } else -    buf = nullptr; -  if (status) -    *status = internal_status; -  return buf; +    if (Name->getKind() == Node::KNameWithTemplateArgs) { +      Name = static_cast<NameWithTemplateArgs *>(Name)->Name; +      continue; +    } +    break; +  } + +  switch (Name->getKind()) { +  case Node::KStdQualifiedName: +    S += "std"; +    break; +  case Node::KNestedName: +    static_cast<NestedName *>(Name)->Qual->print(S); +    break; +  case Node::KLocalName: { +    auto *LN = static_cast<LocalName *>(Name); +    LN->Encoding->print(S); +    S += "::"; +    Name = LN->Entity; +    goto KeepGoingLocalFunction; +  } +  default: +    break; +  } +  S += '\0'; +  if (N != nullptr) +    *N = S.getCurrentPosition(); +  return S.getBuffer(); +} + +char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const { +  if (!isFunction()) +    return nullptr; +  auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName(); +  return printNode(Name, Buf, N); +} + +char *ItaniumPartialDemangler::getFunctionParameters(char *Buf, +                                                     size_t *N) const { +  if (!isFunction()) +    return nullptr; +  NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams(); + +  OutputStream S; +  if (initializeOutputStream(Buf, N, S, 128)) +    return nullptr; + +  S += '('; +  Params.printWithComma(S); +  S += ')'; +  S += '\0'; +  if (N != nullptr) +    *N = S.getCurrentPosition(); +  return S.getBuffer(); +} + +char *ItaniumPartialDemangler::getFunctionReturnType( +    char *Buf, size_t *N) const { +  if (!isFunction()) +    return nullptr; + +  OutputStream S; +  if (initializeOutputStream(Buf, N, S, 128)) +    return nullptr; + +  if (Node *Ret = static_cast<FunctionEncoding *>(RootNode)->getReturnType()) +    Ret->print(S); + +  S += '\0'; +  if (N != nullptr) +    *N = S.getCurrentPosition(); +  return S.getBuffer(); +} + +char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const { +  assert(RootNode != nullptr && "must call partialDemangle()"); +  return printNode(static_cast<Node *>(RootNode), Buf, N); +} + +bool ItaniumPartialDemangler::hasFunctionQualifiers() const { +  assert(RootNode != nullptr && "must call partialDemangle()"); +  if (!isFunction()) +    return false; +  auto *E = static_cast<FunctionEncoding *>(RootNode); +  return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone; +} + +bool ItaniumPartialDemangler::isCtorOrDtor() const { +  Node *N = static_cast<Node *>(RootNode); +  while (N) { +    switch (N->getKind()) { +    default: +      return false; +    case Node::KCtorDtorName: +      return true; + +    case Node::KAbiTagAttr: +      N = static_cast<AbiTagAttr *>(N)->Base; +      break; +    case Node::KFunctionEncoding: +      N = static_cast<FunctionEncoding *>(N)->getName(); +      break; +    case Node::KLocalName: +      N = static_cast<LocalName *>(N)->Entity; +      break; +    case Node::KNameWithTemplateArgs: +      N = static_cast<NameWithTemplateArgs *>(N)->Name; +      break; +    case Node::KNestedName: +      N = static_cast<NestedName *>(N)->Name; +      break; +    case Node::KStdQualifiedName: +      N = static_cast<StdQualifiedName *>(N)->Child; +      break; +    } +  } +  return false; +} + +bool ItaniumPartialDemangler::isFunction() const { +  assert(RootNode != nullptr && "must call partialDemangle()"); +  return static_cast<Node *>(RootNode)->getKind() == Node::KFunctionEncoding; +} + +bool ItaniumPartialDemangler::isSpecialName() const { +  assert(RootNode != nullptr && "must call partialDemangle()"); +  auto K = static_cast<Node *>(RootNode)->getKind(); +  return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName; +} + +bool ItaniumPartialDemangler::isData() const { +  return !isFunction() && !isSpecialName(); +} +  } | 
