From eb11fae6d08f479c0799db45860a98af528fa6e7 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Sat, 28 Jul 2018 10:51:19 +0000 Subject: Vendor import of llvm trunk r338150: https://llvm.org/svn/llvm-project/llvm/trunk@338150 --- lib/Demangle/ItaniumDemangle.cpp | 8951 +++++++++++++++++++++----------------- 1 file changed, 4919 insertions(+), 4032 deletions(-) (limited to 'lib/Demangle/ItaniumDemangle.cpp') 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,3800 +7,4369 @@ // //===----------------------------------------------------------------------===// -#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 +#include #include +#include #include #include #include -#include +#include #include -#ifdef _MSC_VER -// snprintf is implemented in VS 2015 -#if _MSC_VER < 1900 -#define snprintf _snprintf_s -#endif -#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); + } -enum { - unknown_error = -4, - invalid_args = -3, - invalid_mangled_name, - memory_alloc_failure, - success -}; + bool hasArray(OutputStream &S) const { + if (ArrayCache != Cache::Unknown) + return ArrayCache == Cache::Yes; + return hasArraySlow(S); + } -enum { - CV_const = (1 << 0), - CV_volatile = (1 << 1), - CV_restrict = (1 << 2), -}; + bool hasFunction(OutputStream &S) const { + if (FunctionCache != Cache::Unknown) + return FunctionCache == Cache::Yes; + return hasFunctionSlow(S); + } -template -static const char *parse_type(const char *first, const char *last, C &db); -template -static const char *parse_encoding(const char *first, const char *last, C &db); -template -static const char *parse_name(const char *first, const char *last, C &db, - bool *ends_with_template_args = 0); -template -static const char *parse_expression(const char *first, const char *last, C &db); -template -static const char *parse_template_args(const char *first, const char *last, - C &db); -template -static const char *parse_operator_name(const char *first, const char *last, - C &db); -template -static const char *parse_unqualified_name(const char *first, const char *last, - C &db); -template -static const char *parse_decltype(const char *first, const char *last, C &db); + Kind getKind() const { return K; } -// ::= [n] + virtual bool hasRHSComponentSlow(OutputStream &) const { return false; } + virtual bool hasArraySlow(OutputStream &) const { return false; } + virtual bool hasFunctionSlow(OutputStream &) const { return false; } -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; - } - } + // 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; } - return first; -} -namespace { -template struct float_data; + void print(OutputStream &S) const { + printLeft(S); + if (RHSComponentCache != Cache::No) + printRight(S); + } -template <> struct float_data { - static const size_t mangled_size = 8; - static const size_t max_demangled_size = 24; - static const char *spec; -}; -const char *float_data::spec = "%af"; + // Print the "left" side of this Node into OutputStream. + virtual void printLeft(OutputStream &) const = 0; -template <> struct float_data { - static const size_t mangled_size = 16; - static const size_t max_demangled_size = 32; - static const char *spec; -}; + // 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 {} -const char *float_data::spec = "%a"; + virtual StringView getBaseName() const { return StringView(); } -template <> struct float_data { -#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 + // Silence compiler warnings, this dtor will never be called. + virtual ~Node() = default; + +#ifndef NDEBUG + LLVM_DUMP_METHOD void dump() const { + char *Buffer = static_cast(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 - static const size_t max_demangled_size = 40; - static const char *spec; }; -const char *float_data::spec = "%LaL"; -} +class NodeArray { + Node **Elements; + size_t NumElements; -template -static const char *parse_floating_number(const char *first, const char *last, - C &db) { - const size_t N = float_data::mangled_size; - if (static_cast(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(*t - '0') - : static_cast(*t - 'a' + 10); - ++t; - unsigned d0 = isdigit(*t) ? static_cast(*t - '0') - : static_cast(*t - 'a' + 10); - *e = static_cast((d1 << 4) + d0); - } - if (*t == 'E') { -#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ - std::reverse(buf, e); -#endif - char num[float_data::max_demangled_size] = {0}; - int n = snprintf(num, sizeof(num), float_data::spec, value); - if (static_cast(n) >= sizeof(num)) - return first; - db.names.push_back(std::string(num, static_cast(n))); - first = t + 1; +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; + } + + FirstElement = false; } } - return first; -} +}; -// ::= +struct NodeArrayNode : Node { + NodeArray Array; + NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {} + void printLeft(OutputStream &S) const override { + Array.printWithComma(S); + } +}; -template -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(c - '0'); - for (c = *t; isdigit(c); c = *t) { - n = n * 10 + static_cast(c - '0'); - if (++t == last) - return first; - } - if (static_cast(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; - } - } +class DotSuffix final : public Node { + const Node *Prefix; + const StringView Suffix; + +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 += ")"; } - return first; -} +}; -// ::= S _ -// ::= S_ -// ::= Sa # ::std::allocator -// ::= Sb # ::std::basic_string -// ::= Ss # ::std::basic_string < char, -// ::std::char_traits, -// ::std::allocator > -// ::= Si # ::std::basic_istream > -// ::= So # ::std::basic_ostream > -// ::= Sd # ::std::basic_iostream > +class VendorExtQualType final : public Node { + const Node *Ty; + StringView Ext; -template -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(*t - '0'); - else - sub = static_cast(*t - 'A') + 10; - for (++t; t != last && (std::isdigit(*t) || std::isupper(*t)); ++t) { - sub *= 36; - if (std::isdigit(*t)) - sub += static_cast(*t - '0'); - else - sub += static_cast(*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; - } - } +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(Q1 | Q2); } -// ::= 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 # vendor extended type - -template -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; - break; - case 'x': - db.names.push_back("long long"); - ++first; - break; - case 'y': - db.names.push_back("unsigned long long"); - ++first; - break; - case 'n': - db.names.push_back("__int128"); - ++first; - break; - case 'o': - db.names.push_back("unsigned __int128"); - ++first; - break; - case 'f': - db.names.push_back("float"); - ++first; - break; - case 'd': - db.names.push_back("double"); - ++first; - break; - case 'e': - db.names.push_back("long double"); - ++first; - break; - case 'g': - db.names.push_back("__float128"); - ++first; - break; - case 'z': - db.names.push_back("..."); - ++first; - 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; - } - } - break; - } +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"; } - return first; -} -// ::= [r] [V] [K] +public: + QualType(Node *Child_, Qualifiers Quals_) + : Node(KQualType, Child_->RHSComponentCache, + Child_->ArrayCache, Child_->FunctionCache), + Quals(Quals_), Child(Child_) {} -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; - } + 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); } - return first; -} - -// ::= T_ # first template parameter -// ::= T _ -template -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(*t - '0'); - for (++t; t != last && isdigit(*t); ++t) { - sub *= 10; - sub += static_cast(*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; - } - } - } + void printLeft(OutputStream &S) const override { + Child->printLeft(S); + printQuals(S); } - return first; -} -// cc # const_cast -// (expression) - -template -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; - } - } + void printRight(OutputStream &S) const override { Child->printRight(S); } +}; + +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); } - return first; -} +}; -// dc # dynamic_cast -// (expression) - -template -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 PostfixQualifiedType final : public Node { + const Node *Ty; + const StringView Postfix; + +public: + PostfixQualifiedType(Node *Ty_, StringView Postfix_) + : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {} + + void printLeft(OutputStream &s) const override { + Ty->printLeft(s); + s += Postfix; } - return first; -} +}; -// rc # reinterpret_cast -// (expression) - -template -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 NameType final : public Node { + const StringView Name; + +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); } - return first; -} +}; -// sc # static_cast -// (expression) - -template -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; - } - } +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 += "]"; } - return first; -} +}; -// sp # pack expansion +class EnableIfAttr : public Node { + NodeArray Conditions; +public: + EnableIfAttr(NodeArray Conditions_) + : Node(KEnableIfAttr), Conditions(Conditions_) {} -template -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; + void printLeft(OutputStream &S) const override { + S += " [enable_if:"; + Conditions.printWithComma(S); + S += ']'; } - return first; -} +}; -// st # sizeof (a type) +class ObjCProtoName : public Node { + Node *Ty; + StringView Protocol; -template -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; - } + friend class PointerType; + +public: + ObjCProtoName(Node *Ty_, StringView Protocol_) + : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {} + + bool isObjCObject() const { + return Ty->getKind() == KNameType && + static_cast(Ty)->getName() == "objc_object"; } - return first; -} -// sz # sizeof (a expression) + void printLeft(OutputStream &S) const override { + Ty->print(S); + S += "<"; + S += Protocol; + S += ">"; + } +}; -template -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 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); } - return first; -} -// sZ # size of a parameter -// pack - -template -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; + void printLeft(OutputStream &s) const override { + // We rewrite objc_object* into id. + if (Pointee->getKind() != KObjCProtoName || + !static_cast(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(Pointee); + s += "id<"; + s += objcProto->Protocol; + s += ">"; } } - return first; -} -// ::= fp _ # L == 0, first parameter -// ::= fp _ # L == 0, second and later parameters -// ::= fL p -// _ # L > 0, first parameter -// ::= fL p -// _ # L > 0, second and -// later parameters - -template -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; - } - } 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; - } - } + void printRight(OutputStream &s) const override { + if (Pointee->getKind() != KObjCProtoName || + !static_cast(Pointee)->isObjCObject()) { + if (Pointee->hasArray(s) || Pointee->hasFunction(s)) + s += ")"; + Pointee->printRight(s); } } - return first; -} +}; -// sZ # size of a function -// parameter pack +enum class ReferenceKind { + LValue, + RValue, +}; -template -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; +// 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 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(SN); + SoFar.second = RT->Pointee; + SoFar.first = std::min(SoFar.first, RT->RK); } + return SoFar; } - return first; -} -// te # typeid (expression) -// ti # typeid (type) - -template -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; - } +public: + ReferenceType(Node *Pointee_, ReferenceKind RK_) + : Node(KReferenceType, Pointee_->RHSComponentCache), + Pointee(Pointee_), RK(RK_) {} + + bool hasRHSComponentSlow(OutputStream &S) const override { + return Pointee->hasRHSComponent(S); } - return first; -} -// tw # throw expression + void printLeft(OutputStream &s) const override { + std::pair Collapsed = collapse(s); + Collapsed.second->printLeft(s); + if (Collapsed.second->hasArray(s)) + s += " "; + if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) + s += "("; -template -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; - } + s += (Collapsed.first == ReferenceKind::LValue ? "&" : "&&"); } - return first; -} - -// ds # expr.*expr - -template -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; - } - } + void printRight(OutputStream &s) const override { + std::pair Collapsed = collapse(s); + if (Collapsed.second->hasArray(s) || Collapsed.second->hasFunction(s)) + s += ")"; + Collapsed.second->printRight(s); } - return first; -} +}; -// ::= [ ] +class PointerToMemberType final : public Node { + const Node *ClassType; + const Node *MemberType; -template -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; +public: + PointerToMemberType(Node *ClassType_, Node *MemberType_) + : Node(KPointerToMemberType, MemberType_->RHSComponentCache), + ClassType(ClassType_), MemberType(MemberType_) {} + + bool hasRHSComponentSlow(OutputStream &S) const override { + return MemberType->hasRHSComponent(S); } - return first; -} -// ::= -// ::= -// ::= + void printLeft(OutputStream &s) const override { + MemberType->printLeft(s); + if (MemberType->hasArray(s) || MemberType->hasFunction(s)) + s += "("; + else + s += " "; + ClassType->print(s); + s += "::*"; + } -template -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; - } - 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; - } + void printRight(OutputStream &s) const override { + if (MemberType->hasArray(s) || MemberType->hasFunction(s)) + s += ")"; + MemberType->printRight(s); } - return first; -} +}; -// ::= # e.g., -// ~T or ~decltype(f()) -// ::= # e.g., -// ~A<2*N> - -template -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; -} +class NodeOrString { + const void *First; + const void *Second; -// ::= # -// unresolved name -// extension ::= # -// unresolved operator-function-id -// extension ::= # -// unresolved operator template-id -// ::= on # -// unresolved operator-function-id -// ::= on # -// unresolved operator template-id -// ::= dn # -// destructor or pseudo-destructor; -// # -// e.g. -// ~X or -// ~X - -template -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; - } - } 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; +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(FirstChar); + Second = static_cast(SecondChar); } - return first; -} -// ::= + /* implicit */ NodeOrString(Node *N) + : First(static_cast(N)), Second(nullptr) {} + NodeOrString() : First(nullptr), Second(nullptr) {} -template -static const char *parse_unresolved_qualifier_level(const char *first, - const char *last, C &db) { - return parse_simple_id(first, last, db); -} + bool isString() const { return Second && First; } + bool isNode() const { return First && !Second; } + bool isEmpty() const { return !First && !Second; } -// -// extension ::= srN [] -// * E -// ::= [gs] # x or -// (with "gs") ::x -// ::= [gs] sr + E -// -// # A::x, -// N::y, -// A::z; -// "gs" -// means -// leading -// "::" -// ::= sr # T::x -// / decltype(p)::x -// extension ::= sr -// -// # -// T::N::x -// /decltype(p)::N::x -// (ignored) ::= srN + E -// - -template -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; - } - } - } + StringView asString() const { + assert(isString()); + return StringView(static_cast(First), + static_cast(Second)); } - return first; -} -// dt # expr.name - -template -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; - } - } + const Node *asNode() const { + assert(isNode()); + return static_cast(First); } - return first; -} +}; -// cl + E # call - -template -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; - } - } - return first; -} +class ArrayType final : public Node { + Node *Base; + NodeOrString Dimension; -// [gs] nw * _ E # new (expr-list) type -// [gs] nw * _ # new (expr-list) type -// (init) -// [gs] na * _ E # new[] (expr-list) type -// [gs] na * _ # new[] (expr-list) type -// (init) -// ::= pi * E # parenthesized -// initialization - -template -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; - } +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); } - return first; -} +}; -// cv # conversion with one -// argument -// cv _ * E # conversion with a -// different number of arguments - -template -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; - } +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 += " "; } - return first; -} -// pt # expr->name - -template -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 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); } } - return first; -} +}; -// ::= R # & ref-qualifier -// ::= O # && ref-qualifier - -// ::= F [Y] [] E - -template -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; - } - } +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 += ")"; } - return first; -} +}; -// ::= M +class DynamicExceptionSpec : public Node { + NodeArray Types; +public: + DynamicExceptionSpec(NodeArray Types_) + : Node(KDynamicExceptionSpec), Types(Types_) {} -template -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; - } + 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(Name); } + + void printLeft(OutputStream &S) const override { + if (Ret) { + Ret->printLeft(S); + if (!Ret->hasRHSComponent(S)) + S += " "; } + Name->print(S); } - return first; -} -// ::= A _ -// ::= A [] _ + 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); + } +}; -template -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; - } - } +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 { - 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; - } - } + BaseType->print(S); + S += " vector["; + if (Dimension.isNode()) + Dimension.asNode()->print(S); + else if (Dimension.isString()) + S += Dimension.asString(); + S += "]"; } } - return first; -} +}; -// ::= Dt E # decltype of an id-expression or class -// member access (C++0x) -// ::= DT E # decltype of an expression (C++0x) +/// 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 are found that apply to an +/// , and is stored in the TemplateParams table. In order for this to +/// appear in the final AST, it has to referenced via a (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::max()) { + S.CurrentPackMax = static_cast(Data.size()); + S.CurrentPackIndex = 0; + } + } -template -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; +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 +/// JE in some . It isn't itself unexpanded, unless +/// one of it's Elements is. The parser inserts a ParameterPack into the +/// TemplateParams table if the this pack belongs to apply to an +/// . +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::max(); + SwapAndRestore SavePackIdx(S.CurrentPackIndex, Max); + SwapAndRestore 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 . + 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); } } - return first; -} +}; -// extension: -// ::= Dv _ -// -// ::= Dv [] _ -// ::= -// ::= p # AltiVec vector pixel +class TemplateArgs final : public Node { + NodeArray Params; -template -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(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; - } - } +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 SavePrinting(Printing, true); + return Ref->hasRHSComponent(S); + } + bool hasArraySlow(OutputStream &S) const override { + if (Printing) + return false; + SwapAndRestore SavePrinting(Printing, true); + return Ref->hasArray(S); + } + bool hasFunctionSlow(OutputStream &S) const override { + if (Printing) + return false; + SwapAndRestore SavePrinting(Printing, true); + return Ref->hasFunction(S); + } + const Node *getSyntaxNode(OutputStream &S) const override { + if (Printing) + return this; + SwapAndRestore SavePrinting(Printing, true); + return Ref->getSyntaxNode(S); + } + + void printLeft(OutputStream &S) const override { + if (Printing) + return; + SwapAndRestore SavePrinting(Printing, true); + Ref->printLeft(S); + } + void printRight(OutputStream &S) const override { + if (Printing) + return; + SwapAndRestore SavePrinting(Printing, true); + Ref->printRight(S); + } +}; + +struct NameWithTemplateArgs : Node { + // name + 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; } - return first; -} -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= -// ::= P # pointer-to -// ::= R # reference-to -// ::= O # rvalue reference-to (C++0x) -// ::= C # complex pair (C 2000) -// ::= G # imaginary (C 2000) -// ::= Dp # pack expansion (C++0x) -// ::= U # vendor extended type qualifier -// extension := U # objc-type -// extension := # starts with Dv - -// ::= objcproto # k0 = 9 + -// + k1 -// := # PU<11+>objcproto 11objc_object -// 11objc_object -> id - -template -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 - // it might be followed by . - 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 - // - 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; - } - } + void printLeft(OutputStream &S) const override { + switch (SSK) { + case SpecialSubKind::allocator: + S += "std::basic_string, " + "std::allocator >"; + break; + case SpecialSubKind::basic_string: + case SpecialSubKind::string: + S += "std::basic_string, " + "std::allocator >"; + break; + case SpecialSubKind::istream: + S += "std::basic_istream >"; + break; + case SpecialSubKind::ostream: + S += "std::basic_ostream >"; + break; + case SpecialSubKind::iostream: + S += "std::basic_iostream >"; break; } + } +}; + +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; } - return first; -} -// -// ::= aa # && -// ::= ad # & (unary) -// ::= an # & -// ::= aN # &= -// ::= aS # = -// ::= cl # () -// ::= cm # , -// ::= co # ~ -// ::= cv # (cast) -// ::= da # delete[] -// ::= de # * (unary) -// ::= dl # delete -// ::= dv # / -// ::= dV # /= -// ::= eo # ^ -// ::= eO # ^= -// ::= eq # == -// ::= ge # >= -// ::= gt # > -// ::= ix # [] -// ::= le # <= -// ::= li # operator "" -// ::= ls # << -// ::= lS # <<= -// ::= lt # < -// ::= mi # - -// ::= mI # -= -// ::= ml # * -// ::= mL # *= -// ::= mm # -- (postfix in context) -// ::= na # new[] -// ::= ne # != -// ::= ng # - (unary) -// ::= nt # ! -// ::= nw # new -// ::= oo # || -// ::= or # | -// ::= oR # |= -// ::= pm # ->* -// ::= pl # + -// ::= pL # += -// ::= pp # ++ (postfix in context) -// ::= ps # + (unary) -// ::= pt # -> -// ::= qu # ? -// ::= rm # % -// ::= rM # %= -// ::= rs # >> -// ::= rS # >>= -// ::= v # vendor extended -// operator - -template -static const char *parse_operator_name(const char *first, const char *last, - C &db) { - if (last - first >= 2) { - switch (first[0]) { - 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; - 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 '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; - } + void printLeft(OutputStream &S) const override { + switch (SSK) { + case SpecialSubKind::allocator: + S += "std::allocator"; break; - case 'i': - if (first[1] == 'x') { - db.names.push_back("operator[]"); - first += 2; - } - break; - 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; - 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; - 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; - } + case SpecialSubKind::basic_string: + S += "std::basic_string"; 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; - } + case SpecialSubKind::string: + S += "std::string"; break; - case 'q': - if (first[1] == 'u') { - db.names.push_back("operator?"); - first += 2; - } + case SpecialSubKind::istream: + S += "std::istream"; break; - 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; - } + case SpecialSubKind::ostream: + S += "std::ostream"; 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; - } - } + case SpecialSubKind::iostream: + S += "std::iostream"; break; } } - return first; -} +}; -template -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; - } - db.names.back().first.append(first, t); - if (lit.size() <= 3) - db.names.back().first += lit; - first = t + 1; +class CtorDtorName final : public Node { + const Node *Basename; + const bool IsDtor; + +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; -} +}; -// ::= L E # -// integer literal -// ::= L E # -// floating literal -// ::= L E # -// string literal -// ::= L E # -// nullptr literal (i.e., "LDnE") -// ::= L _ E # -// complex floating point literal (C 2000) -// ::= L E # -// external name - -template -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(first + 2, last, db); - if (t != first + 2) - first = t; - } break; - case 'd': { - const char *t = parse_floating_number(first + 2, last, db); - if (t != first + 2) - first = t; - } break; - case 'e': { - const char *t = parse_floating_number(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 - 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; - } - } - } - } +class DtorName : public Node { + const Node *Base; + +public: + DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {} + + void printLeft(OutputStream &S) const override { + S += "~"; + Base->printLeft(S); } - return first; -} +}; -static std::string base_name(std::string &s) { - if (s.empty()) - return s; - if (s == "std::string") { - s = "std::basic_string, std::allocator " - ">"; - return "basic_string"; - } - if (s == "std::istream") { - s = "std::basic_istream >"; - return "basic_istream"; - } - if (s == "std::ostream") { - s = "std::basic_ostream >"; - return "basic_ostream"; - } - if (s == "std::iostream") { - s = "std::basic_iostream >"; - 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; - } +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 += "\'"; } - if (pe - pf <= 1) - return std::string(); - const char *p0 = pe - 1; - for (; p0 != pf; --p0) { - if (*p0 == ':') { - ++p0; - break; - } - if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_') { - return std::string(); - } +}; + +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 std::string(p0, pe); -} +}; -// ::= 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 # ? +class StructuredBindingName : public Node { + NodeArray Bindings; +public: + StructuredBindingName(NodeArray Bindings_) + : Node(KStructuredBindingName), Bindings(Bindings_) {} -template -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; - } + void printLeft(OutputStream &S) const override { + S += '['; + Bindings.printWithComma(S); + S += ']'; } - return first; -} +}; -// ::= Ut [ ] _ -// ::= -// -// ::= Ul E [ ] _ -// -// ::= + # Parameter types or "v" if the lambda -// has no parameters - -template -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(db.names.size()); - const char *t1 = parse_type(t0, last, db); - long k1 = static_cast(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; - } +// -- 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; -} +}; -// ::= -// ::= -// ::= -// ::= +class ArraySubscriptExpr : public Expr { + const Node *Op1; + const Node *Op2; -template -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; - }; +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 # ::std:: -// extension ::= StL +class PostfixExpr : public Expr { + const Node *Child; + const StringView Operand; -template -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; - } +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; -} +}; -// at # alignof (a type) +class ConditionalExpr : public Expr { + const Node *Cond; + const Node *Then; + const Node *Else; -template -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; - } +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 += ")"; } - return first; -} +}; -// az # alignof (a -// expression) +class MemberExpr : public Expr { + const Node *LHS; + const StringView Kind; + const Node *RHS; -template -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; +public: + MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_) + : LHS(LHS_), Kind(Kind_), RHS(RHS_) {} + + 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(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 += ")"; + } +}; + +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; -} +}; -template -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; -} +class DeleteExpr : public Expr { + Node *Op; + bool IsGlobal; + bool IsArray; -template -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; -} +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); + } +}; -template -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; -} +class PrefixExpr : public Expr { + StringView Prefix; + Node *Child; -// ::= -// ::= -// ::= -// -// ::= cl + E # call -// ::= cv # -// conversion with one argument -// ::= cv _ * E # -// conversion with a different number of arguments -// ::= [gs] nw * _ E # new -// (expr-list) type -// ::= [gs] nw * _ # new -// (expr-list) type (init) -// ::= [gs] na * _ E # new[] -// (expr-list) type -// ::= [gs] na * _ # new[] -// (expr-list) type (init) -// ::= [gs] dl # -// delete expression -// ::= [gs] da # -// delete[] expression -// ::= pp_ # -// prefix ++ -// ::= mm_ # -// prefix -- -// ::= ti # -// typeid (type) -// ::= te # -// typeid (expression) -// ::= dc # -// dynamic_cast (expression) -// ::= sc # -// static_cast (expression) -// ::= cc # -// const_cast (expression) -// ::= rc # -// reinterpret_cast (expression) -// ::= st # -// sizeof (a type) -// ::= sz # -// sizeof (an expression) -// ::= at # -// alignof (a type) -// ::= az # -// alignof (an expression) -// ::= nx # -// noexcept (expression) -// ::= -// ::= -// ::= dt # -// expr.name -// ::= pt # -// expr->name -// ::= ds # -// expr.*expr -// ::= sZ # size -// of a parameter pack -// ::= sZ # size -// of a function parameter pack -// ::= sp # pack -// expansion -// ::= tw # throw -// expression -// ::= tr # throw -// with no operand (rethrow) -// ::= # f(p), -// N::f(p), ::f(p), -// # -// freestanding -// dependent -// name -// (e.g., -// T::x), -// # -// objectless -// nonstatic -// member -// reference -// ::= +public: + PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {} -template -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); - break; - case 'f': - first = parse_function_param(first, last, db); - 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; - } - 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; + 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); + } +}; + +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); + } +}; + +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 += ' '; } - break; - 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; + // ... 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); } - break; - 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; + } + S += ')'; + } +}; + +class ThrowExpr : public Expr { + const Node *Op; + +public: + ThrowExpr(Node *Op_) : Op(Op_) {} + + void printLeft(OutputStream &S) const override { + S += "throw "; + Op->print(S); + } +}; + +class BoolExpr : public Expr { + bool Value; + +public: + BoolExpr(bool Value_) : Value(Value_) {} + + void printLeft(OutputStream &S) const override { + S += Value ? StringView("true") : StringView("false"); + } +}; + +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; + +public: + IntegerExpr(StringView Type_, StringView Value_) : Type(Type_), Value(Value_) {} + + 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; + } +}; + +template struct FloatData; + +template 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::mangled_size; + if (static_cast(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(*t - '0') + : static_cast(*t - 'a' + 10); + ++t; + unsigned d0 = isdigit(*t) ? static_cast(*t - '0') + : static_cast(*t - 'a' + 10); + *e = static_cast((d1 << 4) + d0); } - 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; +#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ + std::reverse(buf, e); +#endif + char num[FloatData::max_demangled_size] = {0}; + int n = snprintf(num, sizeof(num), FloatData::spec, value); + s += StringView(num, num + n); + } + } +}; + +class BumpPointerAllocator { + struct BlockMeta { + BlockMeta* Next; + size_t Current; + }; + + 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(std::malloc(AllocSize)); + if (NewMeta == nullptr) + std::terminate(); + BlockList = new (NewMeta) BlockMeta{BlockList, 0}; + } + + void* allocateMassive(size_t NBytes) { + NBytes += sizeof(BlockMeta); + BlockMeta* NewMeta = reinterpret_cast(std::malloc(NBytes)); + if (NewMeta == nullptr) + std::terminate(); + BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0}; + return static_cast(NewMeta + 1); + } + +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(); + } + BlockList->Current += N; + return static_cast(reinterpret_cast(BlockList + 1) + + BlockList->Current - N); + } + + void reset() { + while (BlockList) { + BlockMeta* Tmp = BlockList; + BlockList = BlockList->Next; + if (reinterpret_cast(Tmp) != InitialBuffer) + std::free(Tmp); + } + BlockList = new (InitialBuffer) BlockMeta{nullptr, 0}; + } + + ~BumpPointerAllocator() { reset(); } +}; + +template +class PODSmallVector { + static_assert(std::is_pod::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(std::malloc(NewCap * sizeof(T))); + if (Tmp == nullptr) + std::terminate(); + std::copy(First, Last, Tmp); + First = Tmp; + } else { + First = static_cast(std::realloc(First, NewCap * sizeof(T))); + if (First == nullptr) + std::terminate(); + } + Last = First + S; + Cap = First + NewCap; + } + +public: + PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {} + + PODSmallVector(const PODSmallVector&) = delete; + PODSmallVector& operator=(const PODSmallVector&) = delete; + + 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(); + } + + PODSmallVector& operator=(PODSmallVector&& Other) { + if (Other.isInline()) { + if (!isInline()) { + std::free(First); + clearInline(); } - break; + std::copy(Other.begin(), Other.end(), First); + Last = First + Other.size(); + Other.clear(); + return *this; + } + + 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; + } + + void push_back(const T& Elem) { + if (Last == Cap) + reserve(size() * 2); + *Last++ = Elem; + } + + void pop_back() { + assert(Last != First && "Popping empty vector!"); + --Last; + } + + 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(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 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 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 TemplateParams; + + // Set of unresolved forward references. These can occur in a + // conversion operator's type, and are resolved in the enclosing . + PODSmallVector 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 T *make(Args &&... args) { + return new (ASTAllocator.allocate(sizeof(T))) + T(std::forward(args)...); + } + + template NodeArray makeNodeArray(It begin, It end) { + size_t sz = static_cast(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; + } + + bool consumeIf(char C) { + if (First != Last && *First == C) { + ++First; + return true; + } + return false; + } + + char consume() { return First != Last ? *First++ : '\0'; } + + char look(unsigned Lookahead = 0) { + if (static_cast(Last - First) <= Lookahead) + return '\0'; + return First[Lookahead]; + } + + size_t numLeft() const { return static_cast(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 production. + Node *parseExpr(); + Node *parsePrefixExpr(StringView Kind); + Node *parseBinaryExpr(StringView Kind); + Node *parseIntegerLiteral(StringView Lit); + Node *parseExprPrimary(); + template Node *parseFloatingLiteral(); + Node *parseFunctionParam(); + Node *parseNewExpr(); + Node *parseConversionExpr(); + Node *parseBracedExpr(); + Node *parseFoldExpr(); + + /// Parse the 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 that is being parsed. This + /// information is only pertinent if the refers to an . + 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; + } + + /// Parse the 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 production. + Node *parseUnresolvedName(); + Node *parseSimpleId(); + Node *parseBaseUnresolvedName(); + Node *parseUnresolvedType(); + Node *parseDestructorName(); + + /// Top-level entry point into the parser. + Node *parse(); +}; + +const char* parse_discriminator(const char* first, const char* last); + +// ::= // N +// ::= # See Scope Encoding below // Z +// ::= +// ::= +// +// ::= +// ::= +Node *Db::parseName(NameState *State) { + consumeIf('L'); // extension + + if (look() == 'N') + return parseNestedName(State); + if (look() == 'Z') + return parseLocalName(State); + + // ::= + 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(S, TA); + } + + Node *N = parseUnscopedName(State); + if (N == nullptr) + return nullptr; + // ::= + if (look() == 'I') { + Subs.push_back(N); + Node *TA = parseTemplateArgs(State != nullptr); + if (TA == nullptr) + return nullptr; + if (State) State->EndsWithTemplateArgs = true; + return make(N, TA); + } + // ::= + return N; +} + +// := Z E [] +// := Z E s [] +// := Z Ed [ ] _ +Node *Db::parseLocalName(NameState *State) { + if (!consumeIf('Z')) + return nullptr; + Node *Encoding = parseEncoding(); + if (Encoding == nullptr || !consumeIf('E')) + return nullptr; + + if (consumeIf('s')) { + First = parse_discriminator(First, Last); + return make(Encoding, make("string literal")); + } + + if (consumeIf('d')) { + parseNumber(true); + if (!consumeIf('_')) + return nullptr; + Node *N = parseName(State); + if (N == nullptr) + return nullptr; + return make(Encoding, N); + } + + Node *Entity = parseName(State); + if (Entity == nullptr) + return nullptr; + First = parse_discriminator(First, Last); + return make(Encoding, Entity); +} + +// ::= +// ::= St # ::std:: +// extension ::= StL +Node *Db::parseUnscopedName(NameState *State) { + if (consumeIf("StL") || consumeIf("St")) { + Node *R = parseUnqualifiedName(State); + if (R == nullptr) + return nullptr; + return make(R); + } + return parseUnqualifiedName(State); +} + +// ::= [abi-tags] +// ::= +// ::= +// ::= +// ::= DC + E # structured binding declaration +Node *Db::parseUnqualifiedName(NameState *State) { + // 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(popTrailingNodeArray(BindingsBegin)); + } else + Result = parseOperatorName(State); + if (Result != nullptr) + Result = parseAbiTags(Result); + return Result; +} + +// ::= Ut [] _ +// ::= +// +// ::= Ul E [ ] _ +// +// ::= + # 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(Count); + } + if (consumeIf("Ul")) { + NodeArray Params; + SwapAndRestore 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(Params, Count); + } + return nullptr; +} + +// ::= +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("(anonymous namespace)"); + return make(Name); +} + +// ::= aa # && +// ::= ad # & (unary) +// ::= an # & +// ::= aN # &= +// ::= aS # = +// ::= cl # () +// ::= cm # , +// ::= co # ~ +// ::= cv # (cast) +// ::= da # delete[] +// ::= de # * (unary) +// ::= dl # delete +// ::= dv # / +// ::= dV # /= +// ::= eo # ^ +// ::= eO # ^= +// ::= eq # == +// ::= ge # >= +// ::= gt # > +// ::= ix # [] +// ::= le # <= +// ::= li # operator "" +// ::= ls # << +// ::= lS # <<= +// ::= lt # < +// ::= mi # - +// ::= mI # -= +// ::= ml # * +// ::= mL # *= +// ::= mm # -- (postfix in context) +// ::= na # new[] +// ::= ne # != +// ::= ng # - (unary) +// ::= nt # ! +// ::= nw # new +// ::= oo # || +// ::= or # | +// ::= oR # |= +// ::= pm # ->* +// ::= pl # + +// ::= pL # += +// ::= pp # ++ (postfix in context) +// ::= ps # + (unary) +// ::= pt # -> +// ::= qu # ? +// ::= rm # % +// ::= rM # %= +// ::= rs # >> +// ::= rS # >>= +// ::= ss # <=> C++2a +// ::= v # vendor extended operator +Node *Db::parseOperatorName(NameState *State) { + switch (look()) { + case 'a': + switch (look(1)) { + case 'a': + First += 2; + return make("operator&&"); + case 'd': + case 'n': + First += 2; + return make("operator&"); + case 'N': + First += 2; + return make("operator&="); + case 'S': + First += 2; + return make("operator="); + } + return nullptr; + case 'c': + switch (look(1)) { + case 'l': + First += 2; + return make("operator()"); + case 'm': + First += 2; + return make("operator,"); + case 'o': + First += 2; + return make("operator~"); + // ::= cv # (cast) + case 'v': { + First += 2; + SwapAndRestore SaveTemplate(TryToParseTemplateArgs, false); + // If we're parsing an encoding, State != nullptr and the conversion + // operators' could have a that refers to some + // s further ahead in the mangled name. + SwapAndRestore SavePermit(PermitForwardTemplateReferences, + PermitForwardTemplateReferences || + State != nullptr); + Node* Ty = parseType(); + if (Ty == nullptr) + return nullptr; + if (State) State->CtorDtorConversion = true; + return make(Ty); + } + } + return nullptr; + case 'd': + switch (look(1)) { + case 'a': + First += 2; + return make("operator delete[]"); + case 'e': + First += 2; + return make("operator*"); + case 'l': + First += 2; + return make("operator delete"); + case 'v': + First += 2; + return make("operator/"); + case 'V': + First += 2; + return make("operator/="); + } + return nullptr; + case 'e': + switch (look(1)) { + case 'o': + First += 2; + return make("operator^"); + case 'O': + First += 2; + return make("operator^="); + case 'q': + First += 2; + return make("operator=="); + } + return nullptr; + case 'g': + switch (look(1)) { + case 'e': + First += 2; + return make("operator>="); + case 't': + First += 2; + return make("operator>"); + } + return nullptr; + case 'i': + if (look(1) == 'x') { + First += 2; + return make("operator[]"); + } + return nullptr; + case 'l': + switch (look(1)) { + case 'e': + First += 2; + return make("operator<="); + // ::= li # operator "" + case 'i': { + First += 2; + Node *SN = parseSourceName(State); + if (SN == nullptr) + return nullptr; + return make(SN); + } + case 's': + First += 2; + return make("operator<<"); + case 'S': + First += 2; + return make("operator<<="); + case 't': + First += 2; + return make("operator<"); + } + return nullptr; + case 'm': + switch (look(1)) { 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; + First += 2; + return make("operator-"); + case 'I': + First += 2; + return make("operator-="); 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; + First += 2; + return make("operator*"); + case 'L': + First += 2; + return make("operator*="); 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; - 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; + First += 2; + return make("operator--"); + } + return nullptr; + case 'n': + switch (look(1)) { + case 'a': + First += 2; + return make("operator new[]"); + case 'e': + First += 2; + return make("operator!="); + case 'g': + First += 2; + return make("operator-"); + case 't': + First += 2; + return make("operator!"); + case 'w': + First += 2; + return make("operator new"); + } + return nullptr; + case 'o': + switch (look(1)) { 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; - } - break; + First += 2; + return make("operator||"); + case 'r': + First += 2; + return make("operator|"); + case 'R': + First += 2; + return make("operator|="); + } + return nullptr; + case 'p': + switch (look(1)) { + case 'm': + First += 2; + return make("operator->*"); + case 'l': + First += 2; + return make("operator+"); + case 'L': + First += 2; + return make("operator+="); 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; - } - 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(); - } - } + First += 2; + return make("operator++"); + case 's': + First += 2; + return make("operator+"); + case 't': + First += 2; + return make("operator->"); + } + return nullptr; + case 'q': + if (look(1) == 'u') { + First += 2; + return make("operator?"); + } + return nullptr; + case 'r': + switch (look(1)) { + case 'm': + First += 2; + return make("operator%"); + case 'M': + First += 2; + return make("operator%="); + case 's': + First += 2; + return make("operator>>"); + case 'S': + First += 2; + return make("operator>>="); + } + return nullptr; + case 's': + if (look(1) == 's') { + First += 2; + return make("operator<=>"); + } + return nullptr; + // ::= v # vendor extended operator + case 'v': + if (std::isdigit(look(1))) { + First += 2; + Node *SN = parseSourceName(State); + if (SN == nullptr) + return nullptr; + return make(SN); + } + return nullptr; + } + return nullptr; +} + +// ::= 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(SoFar)->SSK; + switch (SSK) { + case SpecialSubKind::string: + case SpecialSubKind::istream: + case SpecialSubKind::ostream: + case SpecialSubKind::iostream: + SoFar = make(SSK); + default: 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; - } + } + } + + 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(SoFar, false); + } + + if (look() == 'D' && + (look(1) == '0' || look(1) == '1' || look(1) == '2' || look(1) == '5')) { + First += 2; + if (State) State->CtorDtorConversion = true; + return make(SoFar, true); + } + + return nullptr; +} + +// ::= N [] [] E +// ::= N [] [] E +// +// ::= +// ::= +// ::= +// ::= +// ::= # empty +// ::= +// ::= +// extension ::= L +// +// := [] M +// +// ::=