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) | |
download | src-eb11fae6d08f479c0799db45860a98af528fa6e7.tar.gz src-eb11fae6d08f479c0799db45860a98af528fa6e7.zip |
Vendor import of llvm trunk r338150:vendor/llvm/llvm-trunk-r338150
Notes
Notes:
svn path=/vendor/llvm/dist/; revision=336809
svn path=/vendor/llvm/llvm-trunk-r338150/; revision=336814; tag=vendor/llvm/llvm-trunk-r338150
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(); +} + } |