WebSVN – QNX 8.QNX8 LLVM/Clang compiler suite – Blame – //llvm-build/x86_64/include/llvm/Demangle/ItaniumDemangle.h

Rev	Author	Line No.	Line
14	pmbaty	1	//===--- ItaniumDemangle.h ------------ mode:c++;eval:(read-only-mode) --===//
		2	// Do not edit! See README.txt.
		3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
		4	// See https://llvm.org/LICENSE.txt for license information.
		5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
		6	//
		7	//===----------------------------------------------------------------------===//
		8	//
		9	// Generic itanium demangler library.
		10	// There are two copies of this file in the source tree. The one under
		11	// libcxxabi is the original and the one under llvm is the copy. Use
		12	// cp-to-llvm.sh to update the copy. See README.txt for more details.
		13	//
		14	//===----------------------------------------------------------------------===//
		15
		16	#ifndef DEMANGLE_ITANIUMDEMANGLE_H
		17	#define DEMANGLE_ITANIUMDEMANGLE_H
		18
		19	#include "DemangleConfig.h"
		20	#include "StringView.h"
		21	#include "Utility.h"
		22	#include <algorithm>
		23	#include <cassert>
		24	#include <cctype>
		25	#include <cstdio>
		26	#include <cstdlib>
		27	#include <cstring>
		28	#include <limits>
		29	#include <new>
		30	#include <utility>
		31
		32	DEMANGLE_NAMESPACE_BEGIN
		33
		34	template <class T, size_t N> class PODSmallVector {
		35	static_assert(std::is_pod<T>::value,
		36	"T is required to be a plain old data type");
		37
		38	T *First = nullptr;
		39	T *Last = nullptr;
		40	T *Cap = nullptr;
		41	T Inline[N] = {0};
		42
		43	bool isInline() const { return First == Inline; }
		44
		45	void clearInline() {
		46	First = Inline;
		47	Last = Inline;
		48	Cap = Inline + N;
		49	}
		50
		51	void reserve(size_t NewCap) {
		52	size_t S = size();
		53	if (isInline()) {
		54	auto Tmp = static_cast<T >(std::malloc(NewCap * sizeof(T)));
		55	if (Tmp == nullptr)
		56	std::terminate();
		57	std::copy(First, Last, Tmp);
		58	First = Tmp;
		59	} else {
		60	First = static_cast<T >(std::realloc(First, NewCap sizeof(T)));
		61	if (First == nullptr)
		62	std::terminate();
		63	}
		64	Last = First + S;
		65	Cap = First + NewCap;
		66	}
		67
		68	public:
		69	PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
		70
		71	PODSmallVector(const PODSmallVector &) = delete;
		72	PODSmallVector &operator=(const PODSmallVector &) = delete;
		73
		74	PODSmallVector(PODSmallVector &&Other) : PODSmallVector() {
		75	if (Other.isInline()) {
		76	std::copy(Other.begin(), Other.end(), First);
		77	Last = First + Other.size();
		78	Other.clear();
		79	return;
		80	}
		81
		82	First = Other.First;
		83	Last = Other.Last;
		84	Cap = Other.Cap;
		85	Other.clearInline();
		86	}
		87
		88	PODSmallVector &operator=(PODSmallVector &&Other) {
		89	if (Other.isInline()) {
		90	if (!isInline()) {
		91	std::free(First);
		92	clearInline();
		93	}
		94	std::copy(Other.begin(), Other.end(), First);
		95	Last = First + Other.size();
		96	Other.clear();
		97	return *this;
		98	}
		99
		100	if (isInline()) {
		101	First = Other.First;
		102	Last = Other.Last;
		103	Cap = Other.Cap;
		104	Other.clearInline();
		105	return *this;
		106	}
		107
		108	std::swap(First, Other.First);
		109	std::swap(Last, Other.Last);
		110	std::swap(Cap, Other.Cap);
		111	Other.clear();
		112	return *this;
		113	}
		114
		115	// NOLINTNEXTLINE(readability-identifier-naming)
		116	void push_back(const T &Elem) {
		117	if (Last == Cap)
		118	reserve(size() * 2);
		119	*Last++ = Elem;
		120	}
		121
		122	// NOLINTNEXTLINE(readability-identifier-naming)
		123	void pop_back() {
		124	assert(Last != First && "Popping empty vector!");
		125	--Last;
		126	}
		127
		128	void dropBack(size_t Index) {
		129	assert(Index <= size() && "dropBack() can't expand!");
		130	Last = First + Index;
		131	}
		132
		133	T *begin() { return First; }
		134	T *end() { return Last; }
		135
		136	bool empty() const { return First == Last; }
		137	size_t size() const { return static_cast<size_t>(Last - First); }
		138	T &back() {
		139	assert(Last != First && "Calling back() on empty vector!");
		140	return *(Last - 1);
		141	}
		142	T &operator[](size_t Index) {
		143	assert(Index < size() && "Invalid access!");
		144	return *(begin() + Index);
		145	}
		146	void clear() { Last = First; }
		147
		148	~PODSmallVector() {
		149	if (!isInline())
		150	std::free(First);
		151	}
		152	};
		153
		154	// Base class of all AST nodes. The AST is built by the parser, then is
		155	// traversed by the printLeft/Right functions to produce a demangled string.
		156	class Node {
		157	public:
		158	enum Kind : unsigned char {
		159	#define NODE(NodeKind) K##NodeKind,
		160	#include "ItaniumNodes.def"
		161	};
		162
		163	/// Three-way bool to track a cached value. Unknown is possible if this node
		164	/// has an unexpanded parameter pack below it that may affect this cache.
		165	enum class Cache : unsigned char { Yes, No, Unknown, };
		166
		167	/// Operator precedence for expression nodes. Used to determine required
		168	/// parens in expression emission.
		169	enum class Prec {
		170	Primary,
		171	Postfix,
		172	Unary,
		173	Cast,
		174	PtrMem,
		175	Multiplicative,
		176	Additive,
		177	Shift,
		178	Spaceship,
		179	Relational,
		180	Equality,
		181	And,
		182	Xor,
		183	Ior,
		184	AndIf,
		185	OrIf,
		186	Conditional,
		187	Assign,
		188	Comma,
		189	Default,
		190	};
		191
		192	private:
		193	Kind K;
		194
		195	Prec Precedence : 6;
		196
		197	// FIXME: Make these protected.
		198	public:
		199	/// Tracks if this node has a component on its right side, in which case we
		200	/// need to call printRight.
		201	Cache RHSComponentCache : 2;
		202
		203	/// Track if this node is a (possibly qualified) array type. This can affect
		204	/// how we format the output string.
		205	Cache ArrayCache : 2;
		206
		207	/// Track if this node is a (possibly qualified) function type. This can
		208	/// affect how we format the output string.
		209	Cache FunctionCache : 2;
		210
		211	public:
		212	Node(Kind K_, Prec Precedence_ = Prec::Primary,
		213	Cache RHSComponentCache_ = Cache::No, Cache ArrayCache_ = Cache::No,
		214	Cache FunctionCache_ = Cache::No)
		215	: K(K_), Precedence(Precedence_), RHSComponentCache(RHSComponentCache_),
		216	ArrayCache(ArrayCache_), FunctionCache(FunctionCache_) {}
		217	Node(Kind K_, Cache RHSComponentCache_, Cache ArrayCache_ = Cache::No,
		218	Cache FunctionCache_ = Cache::No)
		219	: Node(K_, Prec::Primary, RHSComponentCache_, ArrayCache_,
		220	FunctionCache_) {}
		221
		222	/// Visit the most-derived object corresponding to this object.
		223	template<typename Fn> void visit(Fn F) const;
		224
		225	// The following function is provided by all derived classes:
		226	//
		227	// Call F with arguments that, when passed to the constructor of this node,
		228	// would construct an equivalent node.
		229	//template<typename Fn> void match(Fn F) const;
		230
		231	bool hasRHSComponent(OutputBuffer &OB) const {
		232	if (RHSComponentCache != Cache::Unknown)
		233	return RHSComponentCache == Cache::Yes;
		234	return hasRHSComponentSlow(OB);
		235	}
		236
		237	bool hasArray(OutputBuffer &OB) const {
		238	if (ArrayCache != Cache::Unknown)
		239	return ArrayCache == Cache::Yes;
		240	return hasArraySlow(OB);
		241	}
		242
		243	bool hasFunction(OutputBuffer &OB) const {
		244	if (FunctionCache != Cache::Unknown)
		245	return FunctionCache == Cache::Yes;
		246	return hasFunctionSlow(OB);
		247	}
		248
		249	Kind getKind() const { return K; }
		250
		251	Prec getPrecedence() const { return Precedence; }
		252
		253	virtual bool hasRHSComponentSlow(OutputBuffer &) const { return false; }
		254	virtual bool hasArraySlow(OutputBuffer &) const { return false; }
		255	virtual bool hasFunctionSlow(OutputBuffer &) const { return false; }
		256
		257	// Dig through "glue" nodes like ParameterPack and ForwardTemplateReference to
		258	// get at a node that actually represents some concrete syntax.
		259	virtual const Node *getSyntaxNode(OutputBuffer &) const { return this; }
		260
		261	// Print this node as an expression operand, surrounding it in parentheses if
		262	// its precedence is [Strictly] weaker than P.
		263	void printAsOperand(OutputBuffer &OB, Prec P = Prec::Default,
		264	bool StrictlyWorse = false) const {
		265	bool Paren =
		266	unsigned(getPrecedence()) >= unsigned(P) + unsigned(StrictlyWorse);
		267	if (Paren)
		268	OB.printOpen();
		269	print(OB);
		270	if (Paren)
		271	OB.printClose();
		272	}
		273
		274	void print(OutputBuffer &OB) const {
		275	printLeft(OB);
		276	if (RHSComponentCache != Cache::No)
		277	printRight(OB);
		278	}
		279
		280	// Print the "left" side of this Node into OutputBuffer.
		281	virtual void printLeft(OutputBuffer &) const = 0;
		282
		283	// Print the "right". This distinction is necessary to represent C++ types
		284	// that appear on the RHS of their subtype, such as arrays or functions.
		285	// Since most types don't have such a component, provide a default
		286	// implementation.
		287	virtual void printRight(OutputBuffer &) const {}
		288
		289	virtual StringView getBaseName() const { return StringView(); }
		290
		291	// Silence compiler warnings, this dtor will never be called.
		292	virtual ~Node() = default;
		293
		294	#ifndef NDEBUG
		295	DEMANGLE_DUMP_METHOD void dump() const;
		296	#endif
		297	};
		298
		299	class NodeArray {
		300	Node **Elements;
		301	size_t NumElements;
		302
		303	public:
		304	NodeArray() : Elements(nullptr), NumElements(0) {}
		305	NodeArray(Node **Elements_, size_t NumElements_)
		306	: Elements(Elements_), NumElements(NumElements_) {}
		307
		308	bool empty() const { return NumElements == 0; }
		309	size_t size() const { return NumElements; }
		310
		311	Node **begin() const { return Elements; }
		312	Node **end() const { return Elements + NumElements; }
		313
		314	Node *operator[](size_t Idx) const { return Elements[Idx]; }
		315
		316	void printWithComma(OutputBuffer &OB) const {
		317	bool FirstElement = true;
		318	for (size_t Idx = 0; Idx != NumElements; ++Idx) {
		319	size_t BeforeComma = OB.getCurrentPosition();
		320	if (!FirstElement)
		321	OB += ", ";
		322	size_t AfterComma = OB.getCurrentPosition();
		323	Elements[Idx]->printAsOperand(OB, Node::Prec::Comma);
		324
		325	// Elements[Idx] is an empty parameter pack expansion, we should erase the
		326	// comma we just printed.
		327	if (AfterComma == OB.getCurrentPosition()) {
		328	OB.setCurrentPosition(BeforeComma);
		329	continue;
		330	}
		331
		332	FirstElement = false;
		333	}
		334	}
		335	};
		336
		337	struct NodeArrayNode : Node {
		338	NodeArray Array;
		339	NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {}
		340
		341	template<typename Fn> void match(Fn F) const { F(Array); }
		342
		343	void printLeft(OutputBuffer &OB) const override { Array.printWithComma(OB); }
		344	};
		345
		346	class DotSuffix final : public Node {
		347	const Node *Prefix;
		348	const StringView Suffix;
		349
		350	public:
		351	DotSuffix(const Node *Prefix_, StringView Suffix_)
		352	: Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
		353
		354	template<typename Fn> void match(Fn F) const { F(Prefix, Suffix); }
		355
		356	void printLeft(OutputBuffer &OB) const override {
		357	Prefix->print(OB);
		358	OB += " (";
		359	OB += Suffix;
		360	OB += ")";
		361	}
		362	};
		363
		364	class VendorExtQualType final : public Node {
		365	const Node *Ty;
		366	StringView Ext;
		367	const Node *TA;
		368
		369	public:
		370	VendorExtQualType(const Node Ty_, StringView Ext_, const Node TA_)
		371	: Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_), TA(TA_) {}
		372
		373	const Node *getTy() const { return Ty; }
		374	StringView getExt() const { return Ext; }
		375	const Node *getTA() const { return TA; }
		376
		377	template <typename Fn> void match(Fn F) const { F(Ty, Ext, TA); }
		378
		379	void printLeft(OutputBuffer &OB) const override {
		380	Ty->print(OB);
		381	OB += " ";
		382	OB += Ext;
		383	if (TA != nullptr)
		384	TA->print(OB);
		385	}
		386	};
		387
		388	enum FunctionRefQual : unsigned char {
		389	FrefQualNone,
		390	FrefQualLValue,
		391	FrefQualRValue,
		392	};
		393
		394	enum Qualifiers {
		395	QualNone = 0,
		396	QualConst = 0x1,
		397	QualVolatile = 0x2,
		398	QualRestrict = 0x4,
		399	};
		400
		401	inline Qualifiers operator\|=(Qualifiers &Q1, Qualifiers Q2) {
		402	return Q1 = static_cast<Qualifiers>(Q1 \| Q2);
		403	}
		404
		405	class QualType final : public Node {
		406	protected:
		407	const Qualifiers Quals;
		408	const Node *Child;
		409
		410	void printQuals(OutputBuffer &OB) const {
		411	if (Quals & QualConst)
		412	OB += " const";
		413	if (Quals & QualVolatile)
		414	OB += " volatile";
		415	if (Quals & QualRestrict)
		416	OB += " restrict";
		417	}
		418
		419	public:
		420	QualType(const Node *Child_, Qualifiers Quals_)
		421	: Node(KQualType, Child_->RHSComponentCache,
		422	Child_->ArrayCache, Child_->FunctionCache),
		423	Quals(Quals_), Child(Child_) {}
		424
		425	Qualifiers getQuals() const { return Quals; }
		426	const Node *getChild() const { return Child; }
		427
		428	template<typename Fn> void match(Fn F) const { F(Child, Quals); }
		429
		430	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		431	return Child->hasRHSComponent(OB);
		432	}
		433	bool hasArraySlow(OutputBuffer &OB) const override {
		434	return Child->hasArray(OB);
		435	}
		436	bool hasFunctionSlow(OutputBuffer &OB) const override {
		437	return Child->hasFunction(OB);
		438	}
		439
		440	void printLeft(OutputBuffer &OB) const override {
		441	Child->printLeft(OB);
		442	printQuals(OB);
		443	}
		444
		445	void printRight(OutputBuffer &OB) const override { Child->printRight(OB); }
		446	};
		447
		448	class ConversionOperatorType final : public Node {
		449	const Node *Ty;
		450
		451	public:
		452	ConversionOperatorType(const Node *Ty_)
		453	: Node(KConversionOperatorType), Ty(Ty_) {}
		454
		455	template<typename Fn> void match(Fn F) const { F(Ty); }
		456
		457	void printLeft(OutputBuffer &OB) const override {
		458	OB += "operator ";
		459	Ty->print(OB);
		460	}
		461	};
		462
		463	class PostfixQualifiedType final : public Node {
		464	const Node *Ty;
		465	const StringView Postfix;
		466
		467	public:
		468	PostfixQualifiedType(const Node *Ty_, StringView Postfix_)
		469	: Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {}
		470
		471	template<typename Fn> void match(Fn F) const { F(Ty, Postfix); }
		472
		473	void printLeft(OutputBuffer &OB) const override {
		474	Ty->printLeft(OB);
		475	OB += Postfix;
		476	}
		477	};
		478
		479	class NameType final : public Node {
		480	const StringView Name;
		481
		482	public:
		483	NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
		484
		485	template<typename Fn> void match(Fn F) const { F(Name); }
		486
		487	StringView getName() const { return Name; }
		488	StringView getBaseName() const override { return Name; }
		489
		490	void printLeft(OutputBuffer &OB) const override { OB += Name; }
		491	};
		492
		493	class BitIntType final : public Node {
		494	const Node *Size;
		495	bool Signed;
		496
		497	public:
		498	BitIntType(const Node *Size_, bool Signed_)
		499	: Node(KBitIntType), Size(Size_), Signed(Signed_) {}
		500
		501	template <typename Fn> void match(Fn F) const { F(Size, Signed); }
		502
		503	void printLeft(OutputBuffer &OB) const override {
		504	if (!Signed)
		505	OB += "unsigned ";
		506	OB += "_BitInt";
		507	OB.printOpen();
		508	Size->printAsOperand(OB);
		509	OB.printClose();
		510	}
		511	};
		512
		513	class ElaboratedTypeSpefType : public Node {
		514	StringView Kind;
		515	Node *Child;
		516	public:
		517	ElaboratedTypeSpefType(StringView Kind_, Node *Child_)
		518	: Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {}
		519
		520	template<typename Fn> void match(Fn F) const { F(Kind, Child); }
		521
		522	void printLeft(OutputBuffer &OB) const override {
		523	OB += Kind;
		524	OB += ' ';
		525	Child->print(OB);
		526	}
		527	};
		528
		529	struct AbiTagAttr : Node {
		530	Node *Base;
		531	StringView Tag;
		532
		533	AbiTagAttr(Node* Base_, StringView Tag_)
		534	: Node(KAbiTagAttr, Base_->RHSComponentCache,
		535	Base_->ArrayCache, Base_->FunctionCache),
		536	Base(Base_), Tag(Tag_) {}
		537
		538	template<typename Fn> void match(Fn F) const { F(Base, Tag); }
		539
		540	void printLeft(OutputBuffer &OB) const override {
		541	Base->printLeft(OB);
		542	OB += "[abi:";
		543	OB += Tag;
		544	OB += "]";
		545	}
		546	};
		547
		548	class EnableIfAttr : public Node {
		549	NodeArray Conditions;
		550	public:
		551	EnableIfAttr(NodeArray Conditions_)
		552	: Node(KEnableIfAttr), Conditions(Conditions_) {}
		553
		554	template<typename Fn> void match(Fn F) const { F(Conditions); }
		555
		556	void printLeft(OutputBuffer &OB) const override {
		557	OB += " [enable_if:";
		558	Conditions.printWithComma(OB);
		559	OB += ']';
		560	}
		561	};
		562
		563	class ObjCProtoName : public Node {
		564	const Node *Ty;
		565	StringView Protocol;
		566
		567	friend class PointerType;
		568
		569	public:
		570	ObjCProtoName(const Node *Ty_, StringView Protocol_)
		571	: Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
		572
		573	template<typename Fn> void match(Fn F) const { F(Ty, Protocol); }
		574
		575	bool isObjCObject() const {
		576	return Ty->getKind() == KNameType &&
		577	static_cast<const NameType *>(Ty)->getName() == "objc_object";
		578	}
		579
		580	void printLeft(OutputBuffer &OB) const override {
		581	Ty->print(OB);
		582	OB += "<";
		583	OB += Protocol;
		584	OB += ">";
		585	}
		586	};
		587
		588	class PointerType final : public Node {
		589	const Node *Pointee;
		590
		591	public:
		592	PointerType(const Node *Pointee_)
		593	: Node(KPointerType, Pointee_->RHSComponentCache),
		594	Pointee(Pointee_) {}
		595
		596	const Node *getPointee() const { return Pointee; }
		597
		598	template<typename Fn> void match(Fn F) const { F(Pointee); }
		599
		600	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		601	return Pointee->hasRHSComponent(OB);
		602	}
		603
		604	void printLeft(OutputBuffer &OB) const override {
		605	// We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
		606	if (Pointee->getKind() != KObjCProtoName \|\|
		607	!static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
		608	Pointee->printLeft(OB);
		609	if (Pointee->hasArray(OB))
		610	OB += " ";
		611	if (Pointee->hasArray(OB) \|\| Pointee->hasFunction(OB))
		612	OB += "(";
		613	OB += "*";
		614	} else {
		615	const auto objcProto = static_cast<const ObjCProtoName >(Pointee);
		616	OB += "id<";
		617	OB += objcProto->Protocol;
		618	OB += ">";
		619	}
		620	}
		621
		622	void printRight(OutputBuffer &OB) const override {
		623	if (Pointee->getKind() != KObjCProtoName \|\|
		624	!static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
		625	if (Pointee->hasArray(OB) \|\| Pointee->hasFunction(OB))
		626	OB += ")";
		627	Pointee->printRight(OB);
		628	}
		629	}
		630	};
		631
		632	enum class ReferenceKind {
		633	LValue,
		634	RValue,
		635	};
		636
		637	// Represents either a LValue or an RValue reference type.
		638	class ReferenceType : public Node {
		639	const Node *Pointee;
		640	ReferenceKind RK;
		641
		642	mutable bool Printing = false;
		643
		644	// Dig through any refs to refs, collapsing the ReferenceTypes as we go. The
		645	// rule here is rvalue ref to rvalue ref collapses to a rvalue ref, and any
		646	// other combination collapses to a lvalue ref.
		647	//
		648	// A combination of a TemplateForwardReference and a back-ref Substitution
		649	// from an ill-formed string may have created a cycle; use cycle detection to
		650	// avoid looping forever.
		651	std::pair<ReferenceKind, const Node *> collapse(OutputBuffer &OB) const {
		652	auto SoFar = std::make_pair(RK, Pointee);
		653	// Track the chain of nodes for the Floyd's 'tortoise and hare'
		654	// cycle-detection algorithm, since getSyntaxNode(S) is impure
		655	PODSmallVector<const Node *, 8> Prev;
		656	for (;;) {
		657	const Node *SN = SoFar.second->getSyntaxNode(OB);
		658	if (SN->getKind() != KReferenceType)
		659	break;
		660	auto RT = static_cast<const ReferenceType >(SN);
		661	SoFar.second = RT->Pointee;
		662	SoFar.first = std::min(SoFar.first, RT->RK);
		663
		664	// The middle of Prev is the 'slow' pointer moving at half speed
		665	Prev.push_back(SoFar.second);
		666	if (Prev.size() > 1 && SoFar.second == Prev[(Prev.size() - 1) / 2]) {
		667	// Cycle detected
		668	SoFar.second = nullptr;
		669	break;
		670	}
		671	}
		672	return SoFar;
		673	}
		674
		675	public:
		676	ReferenceType(const Node *Pointee_, ReferenceKind RK_)
		677	: Node(KReferenceType, Pointee_->RHSComponentCache),
		678	Pointee(Pointee_), RK(RK_) {}
		679
		680	template<typename Fn> void match(Fn F) const { F(Pointee, RK); }
		681
		682	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		683	return Pointee->hasRHSComponent(OB);
		684	}
		685
		686	void printLeft(OutputBuffer &OB) const override {
		687	if (Printing)
		688	return;
		689	ScopedOverride<bool> SavePrinting(Printing, true);
		690	std::pair<ReferenceKind, const Node *> Collapsed = collapse(OB);
		691	if (!Collapsed.second)
		692	return;
		693	Collapsed.second->printLeft(OB);
		694	if (Collapsed.second->hasArray(OB))
		695	OB += " ";
		696	if (Collapsed.second->hasArray(OB) \|\| Collapsed.second->hasFunction(OB))
		697	OB += "(";
		698
		699	OB += (Collapsed.first == ReferenceKind::LValue ? "&" : "&&");
		700	}
		701	void printRight(OutputBuffer &OB) const override {
		702	if (Printing)
		703	return;
		704	ScopedOverride<bool> SavePrinting(Printing, true);
		705	std::pair<ReferenceKind, const Node *> Collapsed = collapse(OB);
		706	if (!Collapsed.second)
		707	return;
		708	if (Collapsed.second->hasArray(OB) \|\| Collapsed.second->hasFunction(OB))
		709	OB += ")";
		710	Collapsed.second->printRight(OB);
		711	}
		712	};
		713
		714	class PointerToMemberType final : public Node {
		715	const Node *ClassType;
		716	const Node *MemberType;
		717
		718	public:
		719	PointerToMemberType(const Node ClassType_, const Node MemberType_)
		720	: Node(KPointerToMemberType, MemberType_->RHSComponentCache),
		721	ClassType(ClassType_), MemberType(MemberType_) {}
		722
		723	template<typename Fn> void match(Fn F) const { F(ClassType, MemberType); }
		724
		725	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		726	return MemberType->hasRHSComponent(OB);
		727	}
		728
		729	void printLeft(OutputBuffer &OB) const override {
		730	MemberType->printLeft(OB);
		731	if (MemberType->hasArray(OB) \|\| MemberType->hasFunction(OB))
		732	OB += "(";
		733	else
		734	OB += " ";
		735	ClassType->print(OB);
		736	OB += "::*";
		737	}
		738
		739	void printRight(OutputBuffer &OB) const override {
		740	if (MemberType->hasArray(OB) \|\| MemberType->hasFunction(OB))
		741	OB += ")";
		742	MemberType->printRight(OB);
		743	}
		744	};
		745
		746	class ArrayType final : public Node {
		747	const Node *Base;
		748	Node *Dimension;
		749
		750	public:
		751	ArrayType(const Node Base_, Node Dimension_)
		752	: Node(KArrayType,
		753	/RHSComponentCache=/Cache::Yes,
		754	/ArrayCache=/Cache::Yes),
		755	Base(Base_), Dimension(Dimension_) {}
		756
		757	template<typename Fn> void match(Fn F) const { F(Base, Dimension); }
		758
		759	bool hasRHSComponentSlow(OutputBuffer &) const override { return true; }
		760	bool hasArraySlow(OutputBuffer &) const override { return true; }
		761
		762	void printLeft(OutputBuffer &OB) const override { Base->printLeft(OB); }
		763
		764	void printRight(OutputBuffer &OB) const override {
		765	if (OB.back() != ']')
		766	OB += " ";
		767	OB += "[";
		768	if (Dimension)
		769	Dimension->print(OB);
		770	OB += "]";
		771	Base->printRight(OB);
		772	}
		773	};
		774
		775	class FunctionType final : public Node {
		776	const Node *Ret;
		777	NodeArray Params;
		778	Qualifiers CVQuals;
		779	FunctionRefQual RefQual;
		780	const Node *ExceptionSpec;
		781
		782	public:
		783	FunctionType(const Node *Ret_, NodeArray Params_, Qualifiers CVQuals_,
		784	FunctionRefQual RefQual_, const Node *ExceptionSpec_)
		785	: Node(KFunctionType,
		786	/RHSComponentCache=/Cache::Yes, /ArrayCache=/Cache::No,
		787	/FunctionCache=/Cache::Yes),
		788	Ret(Ret_), Params(Params_), CVQuals(CVQuals_), RefQual(RefQual_),
		789	ExceptionSpec(ExceptionSpec_) {}
		790
		791	template<typename Fn> void match(Fn F) const {
		792	F(Ret, Params, CVQuals, RefQual, ExceptionSpec);
		793	}
		794
		795	bool hasRHSComponentSlow(OutputBuffer &) const override { return true; }
		796	bool hasFunctionSlow(OutputBuffer &) const override { return true; }
		797
		798	// Handle C++'s ... quirky decl grammar by using the left & right
		799	// distinction. Consider:
		800	// int (*f(float))(char) {}
		801	// f is a function that takes a float and returns a pointer to a function
		802	// that takes a char and returns an int. If we're trying to print f, start
		803	// by printing out the return types's left, then print our parameters, then
		804	// finally print right of the return type.
		805	void printLeft(OutputBuffer &OB) const override {
		806	Ret->printLeft(OB);
		807	OB += " ";
		808	}
		809
		810	void printRight(OutputBuffer &OB) const override {
		811	OB.printOpen();
		812	Params.printWithComma(OB);
		813	OB.printClose();
		814	Ret->printRight(OB);
		815
		816	if (CVQuals & QualConst)
		817	OB += " const";
		818	if (CVQuals & QualVolatile)
		819	OB += " volatile";
		820	if (CVQuals & QualRestrict)
		821	OB += " restrict";
		822
		823	if (RefQual == FrefQualLValue)
		824	OB += " &";
		825	else if (RefQual == FrefQualRValue)
		826	OB += " &&";
		827
		828	if (ExceptionSpec != nullptr) {
		829	OB += ' ';
		830	ExceptionSpec->print(OB);
		831	}
		832	}
		833	};
		834
		835	class NoexceptSpec : public Node {
		836	const Node *E;
		837	public:
		838	NoexceptSpec(const Node *E_) : Node(KNoexceptSpec), E(E_) {}
		839
		840	template<typename Fn> void match(Fn F) const { F(E); }
		841
		842	void printLeft(OutputBuffer &OB) const override {
		843	OB += "noexcept";
		844	OB.printOpen();
		845	E->printAsOperand(OB);
		846	OB.printClose();
		847	}
		848	};
		849
		850	class DynamicExceptionSpec : public Node {
		851	NodeArray Types;
		852	public:
		853	DynamicExceptionSpec(NodeArray Types_)
		854	: Node(KDynamicExceptionSpec), Types(Types_) {}
		855
		856	template<typename Fn> void match(Fn F) const { F(Types); }
		857
		858	void printLeft(OutputBuffer &OB) const override {
		859	OB += "throw";
		860	OB.printOpen();
		861	Types.printWithComma(OB);
		862	OB.printClose();
		863	}
		864	};
		865
		866	class FunctionEncoding final : public Node {
		867	const Node *Ret;
		868	const Node *Name;
		869	NodeArray Params;
		870	const Node *Attrs;
		871	Qualifiers CVQuals;
		872	FunctionRefQual RefQual;
		873
		874	public:
		875	FunctionEncoding(const Node Ret_, const Node Name_, NodeArray Params_,
		876	const Node *Attrs_, Qualifiers CVQuals_,
		877	FunctionRefQual RefQual_)
		878	: Node(KFunctionEncoding,
		879	/RHSComponentCache=/Cache::Yes, /ArrayCache=/Cache::No,
		880	/FunctionCache=/Cache::Yes),
		881	Ret(Ret_), Name(Name_), Params(Params_), Attrs(Attrs_),
		882	CVQuals(CVQuals_), RefQual(RefQual_) {}
		883
		884	template<typename Fn> void match(Fn F) const {
		885	F(Ret, Name, Params, Attrs, CVQuals, RefQual);
		886	}
		887
		888	Qualifiers getCVQuals() const { return CVQuals; }
		889	FunctionRefQual getRefQual() const { return RefQual; }
		890	NodeArray getParams() const { return Params; }
		891	const Node *getReturnType() const { return Ret; }
		892
		893	bool hasRHSComponentSlow(OutputBuffer &) const override { return true; }
		894	bool hasFunctionSlow(OutputBuffer &) const override { return true; }
		895
		896	const Node *getName() const { return Name; }
		897
		898	void printLeft(OutputBuffer &OB) const override {
		899	if (Ret) {
		900	Ret->printLeft(OB);
		901	if (!Ret->hasRHSComponent(OB))
		902	OB += " ";
		903	}
		904	Name->print(OB);
		905	}
		906
		907	void printRight(OutputBuffer &OB) const override {
		908	OB.printOpen();
		909	Params.printWithComma(OB);
		910	OB.printClose();
		911	if (Ret)
		912	Ret->printRight(OB);
		913
		914	if (CVQuals & QualConst)
		915	OB += " const";
		916	if (CVQuals & QualVolatile)
		917	OB += " volatile";
		918	if (CVQuals & QualRestrict)
		919	OB += " restrict";
		920
		921	if (RefQual == FrefQualLValue)
		922	OB += " &";
		923	else if (RefQual == FrefQualRValue)
		924	OB += " &&";
		925
		926	if (Attrs != nullptr)
		927	Attrs->print(OB);
		928	}
		929	};
		930
		931	class LiteralOperator : public Node {
		932	const Node *OpName;
		933
		934	public:
		935	LiteralOperator(const Node *OpName_)
		936	: Node(KLiteralOperator), OpName(OpName_) {}
		937
		938	template<typename Fn> void match(Fn F) const { F(OpName); }
		939
		940	void printLeft(OutputBuffer &OB) const override {
		941	OB += "operator\"\" ";
		942	OpName->print(OB);
		943	}
		944	};
		945
		946	class SpecialName final : public Node {
		947	const StringView Special;
		948	const Node *Child;
		949
		950	public:
		951	SpecialName(StringView Special_, const Node *Child_)
		952	: Node(KSpecialName), Special(Special_), Child(Child_) {}
		953
		954	template<typename Fn> void match(Fn F) const { F(Special, Child); }
		955
		956	void printLeft(OutputBuffer &OB) const override {
		957	OB += Special;
		958	Child->print(OB);
		959	}
		960	};
		961
		962	class CtorVtableSpecialName final : public Node {
		963	const Node *FirstType;
		964	const Node *SecondType;
		965
		966	public:
		967	CtorVtableSpecialName(const Node FirstType_, const Node SecondType_)
		968	: Node(KCtorVtableSpecialName),
		969	FirstType(FirstType_), SecondType(SecondType_) {}
		970
		971	template<typename Fn> void match(Fn F) const { F(FirstType, SecondType); }
		972
		973	void printLeft(OutputBuffer &OB) const override {
		974	OB += "construction vtable for ";
		975	FirstType->print(OB);
		976	OB += "-in-";
		977	SecondType->print(OB);
		978	}
		979	};
		980
		981	struct NestedName : Node {
		982	Node *Qual;
		983	Node *Name;
		984
		985	NestedName(Node Qual_, Node Name_)
		986	: Node(KNestedName), Qual(Qual_), Name(Name_) {}
		987
		988	template<typename Fn> void match(Fn F) const { F(Qual, Name); }
		989
		990	StringView getBaseName() const override { return Name->getBaseName(); }
		991
		992	void printLeft(OutputBuffer &OB) const override {
		993	Qual->print(OB);
		994	OB += "::";
		995	Name->print(OB);
		996	}
		997	};
		998
		999	struct ModuleName : Node {
		1000	ModuleName *Parent;
		1001	Node *Name;
		1002	bool IsPartition;
		1003
		1004	ModuleName(ModuleName Parent_, Node Name_, bool IsPartition_ = false)
		1005	: Node(KModuleName), Parent(Parent_), Name(Name_),
		1006	IsPartition(IsPartition_) {}
		1007
		1008	template <typename Fn> void match(Fn F) const {
		1009	F(Parent, Name, IsPartition);
		1010	}
		1011
		1012	void printLeft(OutputBuffer &OB) const override {
		1013	if (Parent)
		1014	Parent->print(OB);
		1015	if (Parent \|\| IsPartition)
		1016	OB += IsPartition ? ':' : '.';
		1017	Name->print(OB);
		1018	}
		1019	};
		1020
		1021	struct ModuleEntity : Node {
		1022	ModuleName *Module;
		1023	Node *Name;
		1024
		1025	ModuleEntity(ModuleName Module_, Node Name_)
		1026	: Node(KModuleEntity), Module(Module_), Name(Name_) {}
		1027
		1028	template <typename Fn> void match(Fn F) const { F(Module, Name); }
		1029
		1030	StringView getBaseName() const override { return Name->getBaseName(); }
		1031
		1032	void printLeft(OutputBuffer &OB) const override {
		1033	Name->print(OB);
		1034	OB += '@';
		1035	Module->print(OB);
		1036	}
		1037	};
		1038
		1039	struct LocalName : Node {
		1040	Node *Encoding;
		1041	Node *Entity;
		1042
		1043	LocalName(Node Encoding_, Node Entity_)
		1044	: Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
		1045
		1046	template<typename Fn> void match(Fn F) const { F(Encoding, Entity); }
		1047
		1048	void printLeft(OutputBuffer &OB) const override {
		1049	Encoding->print(OB);
		1050	OB += "::";
		1051	Entity->print(OB);
		1052	}
		1053	};
		1054
		1055	class QualifiedName final : public Node {
		1056	// qualifier::name
		1057	const Node *Qualifier;
		1058	const Node *Name;
		1059
		1060	public:
		1061	QualifiedName(const Node Qualifier_, const Node Name_)
		1062	: Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {}
		1063
		1064	template<typename Fn> void match(Fn F) const { F(Qualifier, Name); }
		1065
		1066	StringView getBaseName() const override { return Name->getBaseName(); }
		1067
		1068	void printLeft(OutputBuffer &OB) const override {
		1069	Qualifier->print(OB);
		1070	OB += "::";
		1071	Name->print(OB);
		1072	}
		1073	};
		1074
		1075	class VectorType final : public Node {
		1076	const Node *BaseType;
		1077	const Node *Dimension;
		1078
		1079	public:
		1080	VectorType(const Node BaseType_, const Node Dimension_)
		1081	: Node(KVectorType), BaseType(BaseType_), Dimension(Dimension_) {}
		1082
		1083	const Node *getBaseType() const { return BaseType; }
		1084	const Node *getDimension() const { return Dimension; }
		1085
		1086	template<typename Fn> void match(Fn F) const { F(BaseType, Dimension); }
		1087
		1088	void printLeft(OutputBuffer &OB) const override {
		1089	BaseType->print(OB);
		1090	OB += " vector[";
		1091	if (Dimension)
		1092	Dimension->print(OB);
		1093	OB += "]";
		1094	}
		1095	};
		1096
		1097	class PixelVectorType final : public Node {
		1098	const Node *Dimension;
		1099
		1100	public:
		1101	PixelVectorType(const Node *Dimension_)
		1102	: Node(KPixelVectorType), Dimension(Dimension_) {}
		1103
		1104	template<typename Fn> void match(Fn F) const { F(Dimension); }
		1105
		1106	void printLeft(OutputBuffer &OB) const override {
		1107	// FIXME: This should demangle as "vector pixel".
		1108	OB += "pixel vector[";
		1109	Dimension->print(OB);
		1110	OB += "]";
		1111	}
		1112	};
		1113
		1114	class BinaryFPType final : public Node {
		1115	const Node *Dimension;
		1116
		1117	public:
		1118	BinaryFPType(const Node *Dimension_)
		1119	: Node(KBinaryFPType), Dimension(Dimension_) {}
		1120
		1121	template<typename Fn> void match(Fn F) const { F(Dimension); }
		1122
		1123	void printLeft(OutputBuffer &OB) const override {
		1124	OB += "_Float";
		1125	Dimension->print(OB);
		1126	}
		1127	};
		1128
		1129	enum class TemplateParamKind { Type, NonType, Template };
		1130
		1131	/// An invented name for a template parameter for which we don't have a
		1132	/// corresponding template argument.
		1133	///
		1134	/// This node is created when parsing the <lambda-sig> for a lambda with
		1135	/// explicit template arguments, which might be referenced in the parameter
		1136	/// types appearing later in the <lambda-sig>.
		1137	class SyntheticTemplateParamName final : public Node {
		1138	TemplateParamKind Kind;
		1139	unsigned Index;
		1140
		1141	public:
		1142	SyntheticTemplateParamName(TemplateParamKind Kind_, unsigned Index_)
		1143	: Node(KSyntheticTemplateParamName), Kind(Kind_), Index(Index_) {}
		1144
		1145	template<typename Fn> void match(Fn F) const { F(Kind, Index); }
		1146
		1147	void printLeft(OutputBuffer &OB) const override {
		1148	switch (Kind) {
		1149	case TemplateParamKind::Type:
		1150	OB += "$T";
		1151	break;
		1152	case TemplateParamKind::NonType:
		1153	OB += "$N";
		1154	break;
		1155	case TemplateParamKind::Template:
		1156	OB += "$TT";
		1157	break;
		1158	}
		1159	if (Index > 0)
		1160	OB << Index - 1;
		1161	}
		1162	};
		1163
		1164	/// A template type parameter declaration, 'typename T'.
		1165	class TypeTemplateParamDecl final : public Node {
		1166	Node *Name;
		1167
		1168	public:
		1169	TypeTemplateParamDecl(Node *Name_)
		1170	: Node(KTypeTemplateParamDecl, Cache::Yes), Name(Name_) {}
		1171
		1172	template<typename Fn> void match(Fn F) const { F(Name); }
		1173
		1174	void printLeft(OutputBuffer &OB) const override { OB += "typename "; }
		1175
		1176	void printRight(OutputBuffer &OB) const override { Name->print(OB); }
		1177	};
		1178
		1179	/// A non-type template parameter declaration, 'int N'.
		1180	class NonTypeTemplateParamDecl final : public Node {
		1181	Node *Name;
		1182	Node *Type;
		1183
		1184	public:
		1185	NonTypeTemplateParamDecl(Node Name_, Node Type_)
		1186	: Node(KNonTypeTemplateParamDecl, Cache::Yes), Name(Name_), Type(Type_) {}
		1187
		1188	template<typename Fn> void match(Fn F) const { F(Name, Type); }
		1189
		1190	void printLeft(OutputBuffer &OB) const override {
		1191	Type->printLeft(OB);
		1192	if (!Type->hasRHSComponent(OB))
		1193	OB += " ";
		1194	}
		1195
		1196	void printRight(OutputBuffer &OB) const override {
		1197	Name->print(OB);
		1198	Type->printRight(OB);
		1199	}
		1200	};
		1201
		1202	/// A template template parameter declaration,
		1203	/// 'template<typename T> typename N'.
		1204	class TemplateTemplateParamDecl final : public Node {
		1205	Node *Name;
		1206	NodeArray Params;
		1207
		1208	public:
		1209	TemplateTemplateParamDecl(Node *Name_, NodeArray Params_)
		1210	: Node(KTemplateTemplateParamDecl, Cache::Yes), Name(Name_),
		1211	Params(Params_) {}
		1212
		1213	template<typename Fn> void match(Fn F) const { F(Name, Params); }
		1214
		1215	void printLeft(OutputBuffer &OB) const override {
		1216	ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
		1217	OB += "template<";
		1218	Params.printWithComma(OB);
		1219	OB += "> typename ";
		1220	}
		1221
		1222	void printRight(OutputBuffer &OB) const override { Name->print(OB); }
		1223	};
		1224
		1225	/// A template parameter pack declaration, 'typename ...T'.
		1226	class TemplateParamPackDecl final : public Node {
		1227	Node *Param;
		1228
		1229	public:
		1230	TemplateParamPackDecl(Node *Param_)
		1231	: Node(KTemplateParamPackDecl, Cache::Yes), Param(Param_) {}
		1232
		1233	template<typename Fn> void match(Fn F) const { F(Param); }
		1234
		1235	void printLeft(OutputBuffer &OB) const override {
		1236	Param->printLeft(OB);
		1237	OB += "...";
		1238	}
		1239
		1240	void printRight(OutputBuffer &OB) const override { Param->printRight(OB); }
		1241	};
		1242
		1243	/// An unexpanded parameter pack (either in the expression or type context). If
		1244	/// this AST is correct, this node will have a ParameterPackExpansion node above
		1245	/// it.
		1246	///
		1247	/// This node is created when some <template-args> are found that apply to an
		1248	/// <encoding>, and is stored in the TemplateParams table. In order for this to
		1249	/// appear in the final AST, it has to referenced via a <template-param> (ie,
		1250	/// T_).
		1251	class ParameterPack final : public Node {
		1252	NodeArray Data;
		1253
		1254	// Setup OutputBuffer for a pack expansion, unless we're already expanding
		1255	// one.
		1256	void initializePackExpansion(OutputBuffer &OB) const {
		1257	if (OB.CurrentPackMax == std::numeric_limits<unsigned>::max()) {
		1258	OB.CurrentPackMax = static_cast<unsigned>(Data.size());
		1259	OB.CurrentPackIndex = 0;
		1260	}
		1261	}
		1262
		1263	public:
		1264	ParameterPack(NodeArray Data_) : Node(KParameterPack), Data(Data_) {
		1265	ArrayCache = FunctionCache = RHSComponentCache = Cache::Unknown;
		1266	if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
		1267	return P->ArrayCache == Cache::No;
		1268	}))
		1269	ArrayCache = Cache::No;
		1270	if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
		1271	return P->FunctionCache == Cache::No;
		1272	}))
		1273	FunctionCache = Cache::No;
		1274	if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
		1275	return P->RHSComponentCache == Cache::No;
		1276	}))
		1277	RHSComponentCache = Cache::No;
		1278	}
		1279
		1280	template<typename Fn> void match(Fn F) const { F(Data); }
		1281
		1282	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		1283	initializePackExpansion(OB);
		1284	size_t Idx = OB.CurrentPackIndex;
		1285	return Idx < Data.size() && Data[Idx]->hasRHSComponent(OB);
		1286	}
		1287	bool hasArraySlow(OutputBuffer &OB) const override {
		1288	initializePackExpansion(OB);
		1289	size_t Idx = OB.CurrentPackIndex;
		1290	return Idx < Data.size() && Data[Idx]->hasArray(OB);
		1291	}
		1292	bool hasFunctionSlow(OutputBuffer &OB) const override {
		1293	initializePackExpansion(OB);
		1294	size_t Idx = OB.CurrentPackIndex;
		1295	return Idx < Data.size() && Data[Idx]->hasFunction(OB);
		1296	}
		1297	const Node *getSyntaxNode(OutputBuffer &OB) const override {
		1298	initializePackExpansion(OB);
		1299	size_t Idx = OB.CurrentPackIndex;
		1300	return Idx < Data.size() ? Data[Idx]->getSyntaxNode(OB) : this;
		1301	}
		1302
		1303	void printLeft(OutputBuffer &OB) const override {
		1304	initializePackExpansion(OB);
		1305	size_t Idx = OB.CurrentPackIndex;
		1306	if (Idx < Data.size())
		1307	Data[Idx]->printLeft(OB);
		1308	}
		1309	void printRight(OutputBuffer &OB) const override {
		1310	initializePackExpansion(OB);
		1311	size_t Idx = OB.CurrentPackIndex;
		1312	if (Idx < Data.size())
		1313	Data[Idx]->printRight(OB);
		1314	}
		1315	};
		1316
		1317	/// A variadic template argument. This node represents an occurrence of
		1318	/// J<something>E in some <template-args>. It isn't itself unexpanded, unless
		1319	/// one of it's Elements is. The parser inserts a ParameterPack into the
		1320	/// TemplateParams table if the <template-args> this pack belongs to apply to an
		1321	/// <encoding>.
		1322	class TemplateArgumentPack final : public Node {
		1323	NodeArray Elements;
		1324	public:
		1325	TemplateArgumentPack(NodeArray Elements_)
		1326	: Node(KTemplateArgumentPack), Elements(Elements_) {}
		1327
		1328	template<typename Fn> void match(Fn F) const { F(Elements); }
		1329
		1330	NodeArray getElements() const { return Elements; }
		1331
		1332	void printLeft(OutputBuffer &OB) const override {
		1333	Elements.printWithComma(OB);
		1334	}
		1335	};
		1336
		1337	/// A pack expansion. Below this node, there are some unexpanded ParameterPacks
		1338	/// which each have Child->ParameterPackSize elements.
		1339	class ParameterPackExpansion final : public Node {
		1340	const Node *Child;
		1341
		1342	public:
		1343	ParameterPackExpansion(const Node *Child_)
		1344	: Node(KParameterPackExpansion), Child(Child_) {}
		1345
		1346	template<typename Fn> void match(Fn F) const { F(Child); }
		1347
		1348	const Node *getChild() const { return Child; }
		1349
		1350	void printLeft(OutputBuffer &OB) const override {
		1351	constexpr unsigned Max = std::numeric_limits<unsigned>::max();
		1352	ScopedOverride<unsigned> SavePackIdx(OB.CurrentPackIndex, Max);
		1353	ScopedOverride<unsigned> SavePackMax(OB.CurrentPackMax, Max);
		1354	size_t StreamPos = OB.getCurrentPosition();
		1355
		1356	// Print the first element in the pack. If Child contains a ParameterPack,
		1357	// it will set up S.CurrentPackMax and print the first element.
		1358	Child->print(OB);
		1359
		1360	// No ParameterPack was found in Child. This can occur if we've found a pack
		1361	// expansion on a <function-param>.
		1362	if (OB.CurrentPackMax == Max) {
		1363	OB += "...";
		1364	return;
		1365	}
		1366
		1367	// We found a ParameterPack, but it has no elements. Erase whatever we may
		1368	// of printed.
		1369	if (OB.CurrentPackMax == 0) {
		1370	OB.setCurrentPosition(StreamPos);
		1371	return;
		1372	}
		1373
		1374	// Else, iterate through the rest of the elements in the pack.
		1375	for (unsigned I = 1, E = OB.CurrentPackMax; I < E; ++I) {
		1376	OB += ", ";
		1377	OB.CurrentPackIndex = I;
		1378	Child->print(OB);
		1379	}
		1380	}
		1381	};
		1382
		1383	class TemplateArgs final : public Node {
		1384	NodeArray Params;
		1385
		1386	public:
		1387	TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {}
		1388
		1389	template<typename Fn> void match(Fn F) const { F(Params); }
		1390
		1391	NodeArray getParams() { return Params; }
		1392
		1393	void printLeft(OutputBuffer &OB) const override {
		1394	ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
		1395	OB += "<";
		1396	Params.printWithComma(OB);
		1397	OB += ">";
		1398	}
		1399	};
		1400
		1401	/// A forward-reference to a template argument that was not known at the point
		1402	/// where the template parameter name was parsed in a mangling.
		1403	///
		1404	/// This is created when demangling the name of a specialization of a
		1405	/// conversion function template:
		1406	///
		1407	/// \code
		1408	/// struct A {
		1409	/// template<typename T> operator T*();
		1410	/// };
		1411	/// \endcode
		1412	///
		1413	/// When demangling a specialization of the conversion function template, we
		1414	/// encounter the name of the template (including the \c T) before we reach
		1415	/// the template argument list, so we cannot substitute the parameter name
		1416	/// for the corresponding argument while parsing. Instead, we create a
		1417	/// \c ForwardTemplateReference node that is resolved after we parse the
		1418	/// template arguments.
		1419	struct ForwardTemplateReference : Node {
		1420	size_t Index;
		1421	Node *Ref = nullptr;
		1422
		1423	// If we're currently printing this node. It is possible (though invalid) for
		1424	// a forward template reference to refer to itself via a substitution. This
		1425	// creates a cyclic AST, which will stack overflow printing. To fix this, bail
		1426	// out if more than one print* function is active.
		1427	mutable bool Printing = false;
		1428
		1429	ForwardTemplateReference(size_t Index_)
		1430	: Node(KForwardTemplateReference, Cache::Unknown, Cache::Unknown,
		1431	Cache::Unknown),
		1432	Index(Index_) {}
		1433
		1434	// We don't provide a matcher for these, because the value of the node is
		1435	// not determined by its construction parameters, and it generally needs
		1436	// special handling.
		1437	template<typename Fn> void match(Fn F) const = delete;
		1438
		1439	bool hasRHSComponentSlow(OutputBuffer &OB) const override {
		1440	if (Printing)
		1441	return false;
		1442	ScopedOverride<bool> SavePrinting(Printing, true);
		1443	return Ref->hasRHSComponent(OB);
		1444	}
		1445	bool hasArraySlow(OutputBuffer &OB) const override {
		1446	if (Printing)
		1447	return false;
		1448	ScopedOverride<bool> SavePrinting(Printing, true);
		1449	return Ref->hasArray(OB);
		1450	}
		1451	bool hasFunctionSlow(OutputBuffer &OB) const override {
		1452	if (Printing)
		1453	return false;
		1454	ScopedOverride<bool> SavePrinting(Printing, true);
		1455	return Ref->hasFunction(OB);
		1456	}
		1457	const Node *getSyntaxNode(OutputBuffer &OB) const override {
		1458	if (Printing)
		1459	return this;
		1460	ScopedOverride<bool> SavePrinting(Printing, true);
		1461	return Ref->getSyntaxNode(OB);
		1462	}
		1463
		1464	void printLeft(OutputBuffer &OB) const override {
		1465	if (Printing)
		1466	return;
		1467	ScopedOverride<bool> SavePrinting(Printing, true);
		1468	Ref->printLeft(OB);
		1469	}
		1470	void printRight(OutputBuffer &OB) const override {
		1471	if (Printing)
		1472	return;
		1473	ScopedOverride<bool> SavePrinting(Printing, true);
		1474	Ref->printRight(OB);
		1475	}
		1476	};
		1477
		1478	struct NameWithTemplateArgs : Node {
		1479	// name<template_args>
		1480	Node *Name;
		1481	Node *TemplateArgs;
		1482
		1483	NameWithTemplateArgs(Node Name_, Node TemplateArgs_)
		1484	: Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {}
		1485
		1486	template<typename Fn> void match(Fn F) const { F(Name, TemplateArgs); }
		1487
		1488	StringView getBaseName() const override { return Name->getBaseName(); }
		1489
		1490	void printLeft(OutputBuffer &OB) const override {
		1491	Name->print(OB);
		1492	TemplateArgs->print(OB);
		1493	}
		1494	};
		1495
		1496	class GlobalQualifiedName final : public Node {
		1497	Node *Child;
		1498
		1499	public:
		1500	GlobalQualifiedName(Node* Child_)
		1501	: Node(KGlobalQualifiedName), Child(Child_) {}
		1502
		1503	template<typename Fn> void match(Fn F) const { F(Child); }
		1504
		1505	StringView getBaseName() const override { return Child->getBaseName(); }
		1506
		1507	void printLeft(OutputBuffer &OB) const override {
		1508	OB += "::";
		1509	Child->print(OB);
		1510	}
		1511	};
		1512
		1513	enum class SpecialSubKind {
		1514	allocator,
		1515	basic_string,
		1516	string,
		1517	istream,
		1518	ostream,
		1519	iostream,
		1520	};
		1521
		1522	class SpecialSubstitution;
		1523	class ExpandedSpecialSubstitution : public Node {
		1524	protected:
		1525	SpecialSubKind SSK;
		1526
		1527	ExpandedSpecialSubstitution(SpecialSubKind SSK_, Kind K_)
		1528	: Node(K_), SSK(SSK_) {}
		1529	public:
		1530	ExpandedSpecialSubstitution(SpecialSubKind SSK_)
		1531	: ExpandedSpecialSubstitution(SSK_, KExpandedSpecialSubstitution) {}
		1532	inline ExpandedSpecialSubstitution(SpecialSubstitution const *);
		1533
		1534	template<typename Fn> void match(Fn F) const { F(SSK); }
		1535
		1536	protected:
		1537	bool isInstantiation() const {
		1538	return unsigned(SSK) >= unsigned(SpecialSubKind::string);
		1539	}
		1540
		1541	StringView getBaseName() const override {
		1542	switch (SSK) {
		1543	case SpecialSubKind::allocator:
		1544	return StringView("allocator");
		1545	case SpecialSubKind::basic_string:
		1546	return StringView("basic_string");
		1547	case SpecialSubKind::string:
		1548	return StringView("basic_string");
		1549	case SpecialSubKind::istream:
		1550	return StringView("basic_istream");
		1551	case SpecialSubKind::ostream:
		1552	return StringView("basic_ostream");
		1553	case SpecialSubKind::iostream:
		1554	return StringView("basic_iostream");
		1555	}
		1556	DEMANGLE_UNREACHABLE;
		1557	}
		1558
		1559	private:
		1560	void printLeft(OutputBuffer &OB) const override {
		1561	OB << "std::" << getBaseName();
		1562	if (isInstantiation()) {
		1563	OB << "<char, std::char_traits<char>";
		1564	if (SSK == SpecialSubKind::string)
		1565	OB << ", std::allocator<char>";
		1566	OB << ">";
		1567	}
		1568	}
		1569	};
		1570
		1571	class SpecialSubstitution final : public ExpandedSpecialSubstitution {
		1572	public:
		1573	SpecialSubstitution(SpecialSubKind SSK_)
		1574	: ExpandedSpecialSubstitution(SSK_, KSpecialSubstitution) {}
		1575
		1576	template<typename Fn> void match(Fn F) const { F(SSK); }
		1577
		1578	StringView getBaseName() const override {
		1579	auto SV = ExpandedSpecialSubstitution::getBaseName ();
		1580	if (isInstantiation()) {
		1581	// The instantiations are typedefs that drop the "basic_" prefix.
		1582	assert(SV.startsWith("basic_"));
		1583	SV = SV.dropFront(sizeof("basic_") - 1);
		1584	}
		1585	return SV;
		1586	}
		1587
		1588	void printLeft(OutputBuffer &OB) const override {
		1589	OB << "std::" << getBaseName();
		1590	}
		1591	};
		1592
		1593	inline ExpandedSpecialSubstitution::ExpandedSpecialSubstitution(
		1594	SpecialSubstitution const *SS)
		1595	: ExpandedSpecialSubstitution(SS->SSK) {}
		1596
		1597	class CtorDtorName final : public Node {
		1598	const Node *Basename;
		1599	const bool IsDtor;
		1600	const int Variant;
		1601
		1602	public:
		1603	CtorDtorName(const Node *Basename_, bool IsDtor_, int Variant_)
		1604	: Node(KCtorDtorName), Basename(Basename_), IsDtor(IsDtor_),
		1605	Variant(Variant_) {}
		1606
		1607	template<typename Fn> void match(Fn F) const { F(Basename, IsDtor, Variant); }
		1608
		1609	void printLeft(OutputBuffer &OB) const override {
		1610	if (IsDtor)
		1611	OB += "~";
		1612	OB += Basename->getBaseName();
		1613	}
		1614	};
		1615
		1616	class DtorName : public Node {
		1617	const Node *Base;
		1618
		1619	public:
		1620	DtorName(const Node *Base_) : Node(KDtorName), Base(Base_) {}
		1621
		1622	template<typename Fn> void match(Fn F) const { F(Base); }
		1623
		1624	void printLeft(OutputBuffer &OB) const override {
		1625	OB += "~";
		1626	Base->printLeft(OB);
		1627	}
		1628	};
		1629
		1630	class UnnamedTypeName : public Node {
		1631	const StringView Count;
		1632
		1633	public:
		1634	UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {}
		1635
		1636	template<typename Fn> void match(Fn F) const { F(Count); }
		1637
		1638	void printLeft(OutputBuffer &OB) const override {
		1639	OB += "'unnamed";
		1640	OB += Count;
		1641	OB += "\'";
		1642	}
		1643	};
		1644
		1645	class ClosureTypeName : public Node {
		1646	NodeArray TemplateParams;
		1647	NodeArray Params;
		1648	StringView Count;
		1649
		1650	public:
		1651	ClosureTypeName(NodeArray TemplateParams_, NodeArray Params_,
		1652	StringView Count_)
		1653	: Node(KClosureTypeName), TemplateParams(TemplateParams_),
		1654	Params(Params_), Count(Count_) {}
		1655
		1656	template<typename Fn> void match(Fn F) const {
		1657	F(TemplateParams, Params, Count);
		1658	}
		1659
		1660	void printDeclarator(OutputBuffer &OB) const {
		1661	if (!TemplateParams.empty()) {
		1662	ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
		1663	OB += "<";
		1664	TemplateParams.printWithComma(OB);
		1665	OB += ">";
		1666	}
		1667	OB.printOpen();
		1668	Params.printWithComma(OB);
		1669	OB.printClose();
		1670	}
		1671
		1672	void printLeft(OutputBuffer &OB) const override {
		1673	OB += "\'lambda";
		1674	OB += Count;
		1675	OB += "\'";
		1676	printDeclarator(OB);
		1677	}
		1678	};
		1679
		1680	class StructuredBindingName : public Node {
		1681	NodeArray Bindings;
		1682	public:
		1683	StructuredBindingName(NodeArray Bindings_)
		1684	: Node(KStructuredBindingName), Bindings(Bindings_) {}
		1685
		1686	template<typename Fn> void match(Fn F) const { F(Bindings); }
		1687
		1688	void printLeft(OutputBuffer &OB) const override {
		1689	OB.printOpen('[');
		1690	Bindings.printWithComma(OB);
		1691	OB.printClose(']');
		1692	}
		1693	};
		1694
		1695	// -- Expression Nodes --
		1696
		1697	class BinaryExpr : public Node {
		1698	const Node *LHS;
		1699	const StringView InfixOperator;
		1700	const Node *RHS;
		1701
		1702	public:
		1703	BinaryExpr(const Node LHS_, StringView InfixOperator_, const Node RHS_,
		1704	Prec Prec_)
		1705	: Node(KBinaryExpr, Prec_), LHS(LHS_), InfixOperator(InfixOperator_),
		1706	RHS(RHS_) {}
		1707
		1708	template <typename Fn> void match(Fn F) const {
		1709	F(LHS, InfixOperator, RHS, getPrecedence());
		1710	}
		1711
		1712	void printLeft(OutputBuffer &OB) const override {
		1713	bool ParenAll = OB.isGtInsideTemplateArgs() &&
		1714	(InfixOperator == ">" \|\| InfixOperator == ">>");
		1715	if (ParenAll)
		1716	OB.printOpen();
		1717	// Assignment is right associative, with special LHS precedence.
		1718	bool IsAssign = getPrecedence() == Prec::Assign;
		1719	LHS->printAsOperand(OB, IsAssign ? Prec::OrIf : getPrecedence(), !IsAssign);
		1720	// No space before comma operator
		1721	if (!(InfixOperator == ","))
		1722	OB += " ";
		1723	OB += InfixOperator;
		1724	OB += " ";
		1725	RHS->printAsOperand(OB, getPrecedence(), IsAssign);
		1726	if (ParenAll)
		1727	OB.printClose();
		1728	}
		1729	};
		1730
		1731	class ArraySubscriptExpr : public Node {
		1732	const Node *Op1;
		1733	const Node *Op2;
		1734
		1735	public:
		1736	ArraySubscriptExpr(const Node Op1_, const Node Op2_, Prec Prec_)
		1737	: Node(KArraySubscriptExpr, Prec_), Op1(Op1_), Op2(Op2_) {}
		1738
		1739	template <typename Fn> void match(Fn F) const {
		1740	F(Op1, Op2, getPrecedence());
		1741	}
		1742
		1743	void printLeft(OutputBuffer &OB) const override {
		1744	Op1->printAsOperand(OB, getPrecedence());
		1745	OB.printOpen('[');
		1746	Op2->printAsOperand(OB);
		1747	OB.printClose(']');
		1748	}
		1749	};
		1750
		1751	class PostfixExpr : public Node {
		1752	const Node *Child;
		1753	const StringView Operator;
		1754
		1755	public:
		1756	PostfixExpr(const Node *Child_, StringView Operator_, Prec Prec_)
		1757	: Node(KPostfixExpr, Prec_), Child(Child_), Operator(Operator_) {}
		1758
		1759	template <typename Fn> void match(Fn F) const {
		1760	F(Child, Operator, getPrecedence());
		1761	}
		1762
		1763	void printLeft(OutputBuffer &OB) const override {
		1764	Child->printAsOperand(OB, getPrecedence(), true);
		1765	OB += Operator;
		1766	}
		1767	};
		1768
		1769	class ConditionalExpr : public Node {
		1770	const Node *Cond;
		1771	const Node *Then;
		1772	const Node *Else;
		1773
		1774	public:
		1775	ConditionalExpr(const Node Cond_, const Node Then_, const Node *Else_,
		1776	Prec Prec_)
		1777	: Node(KConditionalExpr, Prec_), Cond(Cond_), Then(Then_), Else(Else_) {}
		1778
		1779	template <typename Fn> void match(Fn F) const {
		1780	F(Cond, Then, Else, getPrecedence());
		1781	}
		1782
		1783	void printLeft(OutputBuffer &OB) const override {
		1784	Cond->printAsOperand(OB, getPrecedence());
		1785	OB += " ? ";
		1786	Then->printAsOperand(OB);
		1787	OB += " : ";
		1788	Else->printAsOperand(OB, Prec::Assign, true);
		1789	}
		1790	};
		1791
		1792	class MemberExpr : public Node {
		1793	const Node *LHS;
		1794	const StringView Kind;
		1795	const Node *RHS;
		1796
		1797	public:
		1798	MemberExpr(const Node LHS_, StringView Kind_, const Node RHS_, Prec Prec_)
		1799	: Node(KMemberExpr, Prec_), LHS(LHS_), Kind(Kind_), RHS(RHS_) {}
		1800
		1801	template <typename Fn> void match(Fn F) const {
		1802	F(LHS, Kind, RHS, getPrecedence());
		1803	}
		1804
		1805	void printLeft(OutputBuffer &OB) const override {
		1806	LHS->printAsOperand(OB, getPrecedence(), true);
		1807	OB += Kind;
		1808	RHS->printAsOperand(OB, getPrecedence(), false);
		1809	}
		1810	};
		1811
		1812	class SubobjectExpr : public Node {
		1813	const Node *Type;
		1814	const Node *SubExpr;
		1815	StringView Offset;
		1816	NodeArray UnionSelectors;
		1817	bool OnePastTheEnd;
		1818
		1819	public:
		1820	SubobjectExpr(const Node Type_, const Node SubExpr_, StringView Offset_,
		1821	NodeArray UnionSelectors_, bool OnePastTheEnd_)
		1822	: Node(KSubobjectExpr), Type(Type_), SubExpr(SubExpr_), Offset(Offset_),
		1823	UnionSelectors(UnionSelectors_), OnePastTheEnd(OnePastTheEnd_) {}
		1824
		1825	template<typename Fn> void match(Fn F) const {
		1826	F(Type, SubExpr, Offset, UnionSelectors, OnePastTheEnd);
		1827	}
		1828
		1829	void printLeft(OutputBuffer &OB) const override {
		1830	SubExpr->print(OB);
		1831	OB += ".<";
		1832	Type->print(OB);
		1833	OB += " at offset ";
		1834	if (Offset.empty()) {
		1835	OB += "0";
		1836	} else if (Offset[0] == 'n') {
		1837	OB += "-";
		1838	OB += Offset.dropFront();
		1839	} else {
		1840	OB += Offset;
		1841	}
		1842	OB += ">";
		1843	}
		1844	};
		1845
		1846	class EnclosingExpr : public Node {
		1847	const StringView Prefix;
		1848	const Node *Infix;
		1849	const StringView Postfix;
		1850
		1851	public:
		1852	EnclosingExpr(StringView Prefix_, const Node *Infix_,
		1853	Prec Prec_ = Prec::Primary)
		1854	: Node(KEnclosingExpr, Prec_), Prefix(Prefix_), Infix(Infix_) {}
		1855
		1856	template <typename Fn> void match(Fn F) const {
		1857	F(Prefix, Infix, getPrecedence());
		1858	}
		1859
		1860	void printLeft(OutputBuffer &OB) const override {
		1861	OB += Prefix;
		1862	OB.printOpen();
		1863	Infix->print(OB);
		1864	OB.printClose();
		1865	OB += Postfix;
		1866	}
		1867	};
		1868
		1869	class CastExpr : public Node {
		1870	// cast_kind<to>(from)
		1871	const StringView CastKind;
		1872	const Node *To;
		1873	const Node *From;
		1874
		1875	public:
		1876	CastExpr(StringView CastKind_, const Node To_, const Node From_, Prec Prec_)
		1877	: Node(KCastExpr, Prec_), CastKind(CastKind_), To(To_), From(From_) {}
		1878
		1879	template <typename Fn> void match(Fn F) const {
		1880	F(CastKind, To, From, getPrecedence());
		1881	}
		1882
		1883	void printLeft(OutputBuffer &OB) const override {
		1884	OB += CastKind;
		1885	{
		1886	ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
		1887	OB += "<";
		1888	To->printLeft(OB);
		1889	OB += ">";
		1890	}
		1891	OB.printOpen();
		1892	From->printAsOperand(OB);
		1893	OB.printClose();
		1894	}
		1895	};
		1896
		1897	class SizeofParamPackExpr : public Node {
		1898	const Node *Pack;
		1899
		1900	public:
		1901	SizeofParamPackExpr(const Node *Pack_)
		1902	: Node(KSizeofParamPackExpr), Pack(Pack_) {}
		1903
		1904	template<typename Fn> void match(Fn F) const { F(Pack); }
		1905
		1906	void printLeft(OutputBuffer &OB) const override {
		1907	OB += "sizeof...";
		1908	OB.printOpen();
		1909	ParameterPackExpansion PPE(Pack);
		1910	PPE.printLeft(OB);
		1911	OB.printClose();
		1912	}
		1913	};
		1914
		1915	class CallExpr : public Node {
		1916	const Node *Callee;
		1917	NodeArray Args;
		1918
		1919	public:
		1920	CallExpr(const Node *Callee_, NodeArray Args_, Prec Prec_)
		1921	: Node(KCallExpr, Prec_), Callee(Callee_), Args(Args_) {}
		1922
		1923	template <typename Fn> void match(Fn F) const {
		1924	F(Callee, Args, getPrecedence());
		1925	}
		1926
		1927	void printLeft(OutputBuffer &OB) const override {
		1928	Callee->print(OB);
		1929	OB.printOpen();
		1930	Args.printWithComma(OB);
		1931	OB.printClose();
		1932	}
		1933	};
		1934
		1935	class NewExpr : public Node {
		1936	// new (expr_list) type(init_list)
		1937	NodeArray ExprList;
		1938	Node *Type;
		1939	NodeArray InitList;
		1940	bool IsGlobal; // ::operator new ?
		1941	bool IsArray; // new[] ?
		1942	public:
		1943	NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
		1944	bool IsArray_, Prec Prec_)
		1945	: Node(KNewExpr, Prec_), ExprList(ExprList_), Type(Type_),
		1946	InitList(InitList_), IsGlobal(IsGlobal_), IsArray(IsArray_) {}
		1947
		1948	template<typename Fn> void match(Fn F) const {
		1949	F(ExprList, Type, InitList, IsGlobal, IsArray, getPrecedence());
		1950	}
		1951
		1952	void printLeft(OutputBuffer &OB) const override {
		1953	if (IsGlobal)
		1954	OB += "::";
		1955	OB += "new";
		1956	if (IsArray)
		1957	OB += "[]";
		1958	if (!ExprList.empty()) {
		1959	OB.printOpen();
		1960	ExprList.printWithComma(OB);
		1961	OB.printClose();
		1962	}
		1963	OB += " ";
		1964	Type->print(OB);
		1965	if (!InitList.empty()) {
		1966	OB.printOpen();
		1967	InitList.printWithComma(OB);
		1968	OB.printClose();
		1969	}
		1970	}
		1971	};
		1972
		1973	class DeleteExpr : public Node {
		1974	Node *Op;
		1975	bool IsGlobal;
		1976	bool IsArray;
		1977
		1978	public:
		1979	DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_, Prec Prec_)
		1980	: Node(KDeleteExpr, Prec_), Op(Op_), IsGlobal(IsGlobal_),
		1981	IsArray(IsArray_) {}
		1982
		1983	template <typename Fn> void match(Fn F) const {
		1984	F(Op, IsGlobal, IsArray, getPrecedence());
		1985	}
		1986
		1987	void printLeft(OutputBuffer &OB) const override {
		1988	if (IsGlobal)
		1989	OB += "::";
		1990	OB += "delete";
		1991	if (IsArray)
		1992	OB += "[]";
		1993	OB += ' ';
		1994	Op->print(OB);
		1995	}
		1996	};
		1997
		1998	class PrefixExpr : public Node {
		1999	StringView Prefix;
		2000	Node *Child;
		2001
		2002	public:
		2003	PrefixExpr(StringView Prefix_, Node *Child_, Prec Prec_)
		2004	: Node(KPrefixExpr, Prec_), Prefix(Prefix_), Child(Child_) {}
		2005
		2006	template <typename Fn> void match(Fn F) const {
		2007	F(Prefix, Child, getPrecedence());
		2008	}
		2009
		2010	void printLeft(OutputBuffer &OB) const override {
		2011	OB += Prefix;
		2012	Child->printAsOperand(OB, getPrecedence());
		2013	}
		2014	};
		2015
		2016	class FunctionParam : public Node {
		2017	StringView Number;
		2018
		2019	public:
		2020	FunctionParam(StringView Number_) : Node(KFunctionParam), Number(Number_) {}
		2021
		2022	template<typename Fn> void match(Fn F) const { F(Number); }
		2023
		2024	void printLeft(OutputBuffer &OB) const override {
		2025	OB += "fp";
		2026	OB += Number;
		2027	}
		2028	};
		2029
		2030	class ConversionExpr : public Node {
		2031	const Node *Type;
		2032	NodeArray Expressions;
		2033
		2034	public:
		2035	ConversionExpr(const Node *Type_, NodeArray Expressions_, Prec Prec_)
		2036	: Node(KConversionExpr, Prec_), Type(Type_), Expressions(Expressions_) {}
		2037
		2038	template <typename Fn> void match(Fn F) const {
		2039	F(Type, Expressions, getPrecedence());
		2040	}
		2041
		2042	void printLeft(OutputBuffer &OB) const override {
		2043	OB.printOpen();
		2044	Type->print(OB);
		2045	OB.printClose();
		2046	OB.printOpen();
		2047	Expressions.printWithComma(OB);
		2048	OB.printClose();
		2049	}
		2050	};
		2051
		2052	class PointerToMemberConversionExpr : public Node {
		2053	const Node *Type;
		2054	const Node *SubExpr;
		2055	StringView Offset;
		2056
		2057	public:
		2058	PointerToMemberConversionExpr(const Node Type_, const Node SubExpr_,
		2059	StringView Offset_, Prec Prec_)
		2060	: Node(KPointerToMemberConversionExpr, Prec_), Type(Type_),
		2061	SubExpr(SubExpr_), Offset(Offset_) {}
		2062
		2063	template <typename Fn> void match(Fn F) const {
		2064	F(Type, SubExpr, Offset, getPrecedence());
		2065	}
		2066
		2067	void printLeft(OutputBuffer &OB) const override {
		2068	OB.printOpen();
		2069	Type->print(OB);
		2070	OB.printClose();
		2071	OB.printOpen();
		2072	SubExpr->print(OB);
		2073	OB.printClose();
		2074	}
		2075	};
		2076
		2077	class InitListExpr : public Node {
		2078	const Node *Ty;
		2079	NodeArray Inits;
		2080	public:
		2081	InitListExpr(const Node *Ty_, NodeArray Inits_)
		2082	: Node(KInitListExpr), Ty(Ty_), Inits(Inits_) {}
		2083
		2084	template<typename Fn> void match(Fn F) const { F(Ty, Inits); }
		2085
		2086	void printLeft(OutputBuffer &OB) const override {
		2087	if (Ty)
		2088	Ty->print(OB);
		2089	OB += '{';
		2090	Inits.printWithComma(OB);
		2091	OB += '}';
		2092	}
		2093	};
		2094
		2095	class BracedExpr : public Node {
		2096	const Node *Elem;
		2097	const Node *Init;
		2098	bool IsArray;
		2099	public:
		2100	BracedExpr(const Node Elem_, const Node Init_, bool IsArray_)
		2101	: Node(KBracedExpr), Elem(Elem_), Init(Init_), IsArray(IsArray_) {}
		2102
		2103	template<typename Fn> void match(Fn F) const { F(Elem, Init, IsArray); }
		2104
		2105	void printLeft(OutputBuffer &OB) const override {
		2106	if (IsArray) {
		2107	OB += '[';
		2108	Elem->print(OB);
		2109	OB += ']';
		2110	} else {
		2111	OB += '.';
		2112	Elem->print(OB);
		2113	}
		2114	if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
		2115	OB += " = ";
		2116	Init->print(OB);
		2117	}
		2118	};
		2119
		2120	class BracedRangeExpr : public Node {
		2121	const Node *First;
		2122	const Node *Last;
		2123	const Node *Init;
		2124	public:
		2125	BracedRangeExpr(const Node First_, const Node Last_, const Node *Init_)
		2126	: Node(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {}
		2127
		2128	template<typename Fn> void match(Fn F) const { F(First, Last, Init); }
		2129
		2130	void printLeft(OutputBuffer &OB) const override {
		2131	OB += '[';
		2132	First->print(OB);
		2133	OB += " ... ";
		2134	Last->print(OB);
		2135	OB += ']';
		2136	if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
		2137	OB += " = ";
		2138	Init->print(OB);
		2139	}
		2140	};
		2141
		2142	class FoldExpr : public Node {
		2143	const Node Pack, Init;
		2144	StringView OperatorName;
		2145	bool IsLeftFold;
		2146
		2147	public:
		2148	FoldExpr(bool IsLeftFold_, StringView OperatorName_, const Node *Pack_,
		2149	const Node *Init_)
		2150	: Node(KFoldExpr), Pack(Pack_), Init(Init_), OperatorName(OperatorName_),
		2151	IsLeftFold(IsLeftFold_) {}
		2152
		2153	template<typename Fn> void match(Fn F) const {
		2154	F(IsLeftFold, OperatorName, Pack, Init);
		2155	}
		2156
		2157	void printLeft(OutputBuffer &OB) const override {
		2158	auto PrintPack = [&] {
		2159	OB.printOpen();
		2160	ParameterPackExpansion(Pack).print(OB);
		2161	OB.printClose();
		2162	};
		2163
		2164	OB.printOpen();
		2165	// Either '[init op ]... op pack' or 'pack op ...[ op init]'
		2166	// Refactored to '[(init\|pack) op ]...[ op (pack\|init)]'
		2167	// Fold expr operands are cast-expressions
		2168	if (!IsLeftFold \|\| Init != nullptr) {
		2169	// '(init\|pack) op '
		2170	if (IsLeftFold)
		2171	Init->printAsOperand(OB, Prec::Cast, true);
		2172	else
		2173	PrintPack();
		2174	OB << " " << OperatorName << " ";
		2175	}
		2176	OB << "...";
		2177	if (IsLeftFold \|\| Init != nullptr) {
		2178	// ' op (init\|pack)'
		2179	OB << " " << OperatorName << " ";
		2180	if (IsLeftFold)
		2181	PrintPack();
		2182	else
		2183	Init->printAsOperand(OB, Prec::Cast, true);
		2184	}
		2185	OB.printClose();
		2186	}
		2187	};
		2188
		2189	class ThrowExpr : public Node {
		2190	const Node *Op;
		2191
		2192	public:
		2193	ThrowExpr(const Node *Op_) : Node(KThrowExpr), Op(Op_) {}
		2194
		2195	template<typename Fn> void match(Fn F) const { F(Op); }
		2196
		2197	void printLeft(OutputBuffer &OB) const override {
		2198	OB += "throw ";
		2199	Op->print(OB);
		2200	}
		2201	};
		2202
		2203	class BoolExpr : public Node {
		2204	bool Value;
		2205
		2206	public:
		2207	BoolExpr(bool Value_) : Node(KBoolExpr), Value(Value_) {}
		2208
		2209	template<typename Fn> void match(Fn F) const { F(Value); }
		2210
		2211	void printLeft(OutputBuffer &OB) const override {
		2212	OB += Value ? StringView("true") : StringView("false");
		2213	}
		2214	};
		2215
		2216	class StringLiteral : public Node {
		2217	const Node *Type;
		2218
		2219	public:
		2220	StringLiteral(const Node *Type_) : Node(KStringLiteral), Type(Type_) {}
		2221
		2222	template<typename Fn> void match(Fn F) const { F(Type); }
		2223
		2224	void printLeft(OutputBuffer &OB) const override {
		2225	OB += "\"<";
		2226	Type->print(OB);
		2227	OB += ">\"";
		2228	}
		2229	};
		2230
		2231	class LambdaExpr : public Node {
		2232	const Node *Type;
		2233
		2234	public:
		2235	LambdaExpr(const Node *Type_) : Node(KLambdaExpr), Type(Type_) {}
		2236
		2237	template<typename Fn> void match(Fn F) const { F(Type); }
		2238
		2239	void printLeft(OutputBuffer &OB) const override {
		2240	OB += "[]";
		2241	if (Type->getKind() == KClosureTypeName)
		2242	static_cast<const ClosureTypeName *>(Type)->printDeclarator(OB);
		2243	OB += "{...}";
		2244	}
		2245	};
		2246
		2247	class EnumLiteral : public Node {
		2248	// ty(integer)
		2249	const Node *Ty;
		2250	StringView Integer;
		2251
		2252	public:
		2253	EnumLiteral(const Node *Ty_, StringView Integer_)
		2254	: Node(KEnumLiteral), Ty(Ty_), Integer(Integer_) {}
		2255
		2256	template<typename Fn> void match(Fn F) const { F(Ty, Integer); }
		2257
		2258	void printLeft(OutputBuffer &OB) const override {
		2259	OB.printOpen();
		2260	Ty->print(OB);
		2261	OB.printClose();
		2262
		2263	if (Integer[0] == 'n')
		2264	OB << "-" << Integer.dropFront(1);
		2265	else
		2266	OB << Integer;
		2267	}
		2268	};
		2269
		2270	class IntegerLiteral : public Node {
		2271	StringView Type;
		2272	StringView Value;
		2273
		2274	public:
		2275	IntegerLiteral(StringView Type_, StringView Value_)
		2276	: Node(KIntegerLiteral), Type(Type_), Value(Value_) {}
		2277
		2278	template<typename Fn> void match(Fn F) const { F(Type, Value); }
		2279
		2280	void printLeft(OutputBuffer &OB) const override {
		2281	if (Type.size() > 3) {
		2282	OB.printOpen();
		2283	OB += Type;
		2284	OB.printClose();
		2285	}
		2286
		2287	if (Value[0] == 'n') {
		2288	OB += '-';
		2289	OB += Value.dropFront(1);
		2290	} else
		2291	OB += Value;
		2292
		2293	if (Type.size() <= 3)
		2294	OB += Type;
		2295	}
		2296	};
		2297
		2298	template <class Float> struct FloatData;
		2299
		2300	namespace float_literal_impl {
		2301	constexpr Node::Kind getFloatLiteralKind(float *) {
		2302	return Node::KFloatLiteral;
		2303	}
		2304	constexpr Node::Kind getFloatLiteralKind(double *) {
		2305	return Node::KDoubleLiteral;
		2306	}
		2307	constexpr Node::Kind getFloatLiteralKind(long double *) {
		2308	return Node::KLongDoubleLiteral;
		2309	}
		2310	}
		2311
		2312	template <class Float> class FloatLiteralImpl : public Node {
		2313	const StringView Contents;
		2314
		2315	static constexpr Kind KindForClass =
		2316	float_literal_impl::getFloatLiteralKind((Float *)nullptr);
		2317
		2318	public:
		2319	FloatLiteralImpl(StringView Contents_)
		2320	: Node(KindForClass), Contents(Contents_) {}
		2321
		2322	template<typename Fn> void match(Fn F) const { F(Contents); }
		2323
		2324	void printLeft(OutputBuffer &OB) const override {
		2325	const char *first = Contents.begin();
		2326	const char *last = Contents.end() + 1;
		2327
		2328	const size_t N = FloatData<Float>::mangled_size;
		2329	if (static_cast<std::size_t>(last - first) > N) {
		2330	last = first + N;
		2331	union {
		2332	Float value;
		2333	char buf[sizeof(Float)];
		2334	};
		2335	const char *t = first;
		2336	char *e = buf;
		2337	for (; t != last; ++t, ++e) {
		2338	unsigned d1 = isdigit(t) ? static_cast<unsigned>(t - '0')
		2339	: static_cast<unsigned>(*t - 'a' + 10);
		2340	++t;
		2341	unsigned d0 = isdigit(t) ? static_cast<unsigned>(t - '0')
		2342	: static_cast<unsigned>(*t - 'a' + 10);
		2343	*e = static_cast<char>((d1 << 4) + d0);
		2344	}
		2345	#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
		2346	std::reverse(buf, e);
		2347	#endif
		2348	char num[FloatData<Float>::max_demangled_size] = {0};
		2349	int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
		2350	OB += StringView(num, num + n);
		2351	}
		2352	}
		2353	};
		2354
		2355	using FloatLiteral = FloatLiteralImpl<float>;
		2356	using DoubleLiteral = FloatLiteralImpl<double>;
		2357	using LongDoubleLiteral = FloatLiteralImpl<long double>;
		2358
		2359	/// Visit the node. Calls \c F(P), where \c P is the node cast to the
		2360	/// appropriate derived class.
		2361	template<typename Fn>
		2362	void Node::visit(Fn F) const {
		2363	switch (K) {
		2364	#define NODE(X) \
		2365	case K##X: \
		2366	return F(static_cast<const X *>(this));
		2367	#include "ItaniumNodes.def"
		2368	}
		2369	assert(0 && "unknown mangling node kind");
		2370	}
		2371
		2372	/// Determine the kind of a node from its type.
		2373	template<typename NodeT> struct NodeKind;
		2374	#define NODE(X) \
		2375	template <> struct NodeKind<X> { \
		2376	static constexpr Node::Kind Kind = Node::K##X; \
		2377	static constexpr const char *name() { return #X; } \
		2378	};
		2379	#include "ItaniumNodes.def"
		2380
		2381	template <typename Derived, typename Alloc> struct AbstractManglingParser {
		2382	const char *First;
		2383	const char *Last;
		2384
		2385	// Name stack, this is used by the parser to hold temporary names that were
		2386	// parsed. The parser collapses multiple names into new nodes to construct
		2387	// the AST. Once the parser is finished, names.size() == 1.
		2388	PODSmallVector<Node *, 32> Names;
		2389
		2390	// Substitution table. Itanium supports name substitutions as a means of
		2391	// compression. The string "S42_" refers to the 44nd entry (base-36) in this
		2392	// table.
		2393	PODSmallVector<Node *, 32> Subs;
		2394
		2395	using TemplateParamList = PODSmallVector<Node *, 8>;
		2396
		2397	class ScopedTemplateParamList {
		2398	AbstractManglingParser *Parser;
		2399	size_t OldNumTemplateParamLists;
		2400	TemplateParamList Params;
		2401
		2402	public:
		2403	ScopedTemplateParamList(AbstractManglingParser *TheParser)
		2404	: Parser(TheParser),
		2405	OldNumTemplateParamLists(TheParser->TemplateParams.size()) {
		2406	Parser->TemplateParams.push_back(&Params);
		2407	}
		2408	~ScopedTemplateParamList() {
		2409	assert(Parser->TemplateParams.size() >= OldNumTemplateParamLists);
		2410	Parser->TemplateParams.dropBack(OldNumTemplateParamLists);
		2411	}
		2412	};
		2413
		2414	// Template parameter table. Like the above, but referenced like "T42_".
		2415	// This has a smaller size compared to Subs and Names because it can be
		2416	// stored on the stack.
		2417	TemplateParamList OuterTemplateParams;
		2418
		2419	// Lists of template parameters indexed by template parameter depth,
		2420	// referenced like "TL2_4_". If nonempty, element 0 is always
		2421	// OuterTemplateParams; inner elements are always template parameter lists of
		2422	// lambda expressions. For a generic lambda with no explicit template
		2423	// parameter list, the corresponding parameter list pointer will be null.
		2424	PODSmallVector<TemplateParamList *, 4> TemplateParams;
		2425
		2426	// Set of unresolved forward <template-param> references. These can occur in a
		2427	// conversion operator's type, and are resolved in the enclosing <encoding>.
		2428	PODSmallVector<ForwardTemplateReference *, 4> ForwardTemplateRefs;
		2429
		2430	bool TryToParseTemplateArgs = true;
		2431	bool PermitForwardTemplateReferences = false;
		2432	size_t ParsingLambdaParamsAtLevel = (size_t)-1;
		2433
		2434	unsigned NumSyntheticTemplateParameters[3] = {};
		2435
		2436	Alloc ASTAllocator;
		2437
		2438	AbstractManglingParser(const char First_, const char Last_)
		2439	: First(First_), Last(Last_) {}
		2440
		2441	Derived &getDerived() { return static_cast<Derived &>(*this); }
		2442
		2443	void reset(const char First_, const char Last_) {
		2444	First = First_;
		2445	Last = Last_;
		2446	Names.clear();
		2447	Subs.clear();
		2448	TemplateParams.clear();
		2449	ParsingLambdaParamsAtLevel = (size_t)-1;
		2450	TryToParseTemplateArgs = true;
		2451	PermitForwardTemplateReferences = false;
		2452	for (int I = 0; I != 3; ++I)
		2453	NumSyntheticTemplateParameters[I] = 0;
		2454	ASTAllocator.reset();
		2455	}
		2456
		2457	template <class T, class... Args> Node *make(Args &&... args) {
		2458	return ASTAllocator.template makeNode<T>(std::forward<Args>(args)...);
		2459	}
		2460
		2461	template <class It> NodeArray makeNodeArray(It begin, It end) {
		2462	size_t sz = static_cast<size_t>(end - begin);
		2463	void *mem = ASTAllocator.allocateNodeArray(sz);
		2464	Node *data = new (mem) Node [sz];
		2465	std::copy(begin, end, data);
		2466	return NodeArray(data, sz);
		2467	}
		2468
		2469	NodeArray popTrailingNodeArray(size_t FromPosition) {
		2470	assert(FromPosition <= Names.size());
		2471	NodeArray res =
		2472	makeNodeArray(Names.begin() + (long)FromPosition, Names.end());
		2473	Names.dropBack(FromPosition);
		2474	return res;
		2475	}
		2476
		2477	bool consumeIf(StringView S) {
		2478	if (StringView(First, Last).startsWith(S)) {
		2479	First += S.size();
		2480	return true;
		2481	}
		2482	return false;
		2483	}
		2484
		2485	bool consumeIf(char C) {
		2486	if (First != Last && *First == C) {
		2487	++First;
		2488	return true;
		2489	}
		2490	return false;
		2491	}
		2492
		2493	char consume() { return First != Last ? *First++ : '\0'; }
		2494
		2495	char look(unsigned Lookahead = 0) const {
		2496	if (static_cast<size_t>(Last - First) <= Lookahead)
		2497	return '\0';
		2498	return First[Lookahead];
		2499	}
		2500
		2501	size_t numLeft() const { return static_cast<size_t>(Last - First); }
		2502
		2503	StringView parseNumber(bool AllowNegative = false);
		2504	Qualifiers parseCVQualifiers();
		2505	bool parsePositiveInteger(size_t *Out);
		2506	StringView parseBareSourceName();
		2507
		2508	bool parseSeqId(size_t *Out);
		2509	Node *parseSubstitution();
		2510	Node *parseTemplateParam();
		2511	Node *parseTemplateParamDecl();
		2512	Node *parseTemplateArgs(bool TagTemplates = false);
		2513	Node *parseTemplateArg();
		2514
		2515	/// Parse the <expr> production.
		2516	Node *parseExpr();
		2517	Node *parsePrefixExpr(StringView Kind, Node::Prec Prec);
		2518	Node *parseBinaryExpr(StringView Kind, Node::Prec Prec);
		2519	Node *parseIntegerLiteral(StringView Lit);
		2520	Node *parseExprPrimary();
		2521	template <class Float> Node *parseFloatingLiteral();
		2522	Node *parseFunctionParam();
		2523	Node *parseConversionExpr();
		2524	Node *parseBracedExpr();
		2525	Node *parseFoldExpr();
		2526	Node *parsePointerToMemberConversionExpr(Node::Prec Prec);
		2527	Node *parseSubobjectExpr();
		2528
		2529	/// Parse the <type> production.
		2530	Node *parseType();
		2531	Node *parseFunctionType();
		2532	Node *parseVectorType();
		2533	Node *parseDecltype();
		2534	Node *parseArrayType();
		2535	Node *parsePointerToMemberType();
		2536	Node *parseClassEnumType();
		2537	Node *parseQualifiedType();
		2538
		2539	Node *parseEncoding();
		2540	bool parseCallOffset();
		2541	Node *parseSpecialName();
		2542
		2543	/// Holds some extra information about a <name> that is being parsed. This
		2544	/// information is only pertinent if the <name> refers to an <encoding>.
		2545	struct NameState {
		2546	bool CtorDtorConversion = false;
		2547	bool EndsWithTemplateArgs = false;
		2548	Qualifiers CVQualifiers = QualNone;
		2549	FunctionRefQual ReferenceQualifier = FrefQualNone;
		2550	size_t ForwardTemplateRefsBegin;
		2551
		2552	NameState(AbstractManglingParser *Enclosing)
		2553	: ForwardTemplateRefsBegin(Enclosing->ForwardTemplateRefs.size()) {}
		2554	};
		2555
		2556	bool resolveForwardTemplateRefs(NameState &State) {
		2557	size_t I = State.ForwardTemplateRefsBegin;
		2558	size_t E = ForwardTemplateRefs.size();
		2559	for (; I < E; ++I) {
		2560	size_t Idx = ForwardTemplateRefs[I]->Index;
		2561	if (TemplateParams.empty() \|\| !TemplateParams[0] \|\|
		2562	Idx >= TemplateParams[0]->size())
		2563	return true;
		2564	ForwardTemplateRefs[I]->Ref = (*TemplateParams[0])[Idx];
		2565	}
		2566	ForwardTemplateRefs.dropBack(State.ForwardTemplateRefsBegin);
		2567	return false;
		2568	}
		2569
		2570	/// Parse the <name> production>
		2571	Node parseName(NameState State = nullptr);
		2572	Node parseLocalName(NameState State);
		2573	Node parseOperatorName(NameState State);
		2574	bool parseModuleNameOpt(ModuleName *&Module);
		2575	Node parseUnqualifiedName(NameState State, Node Scope, ModuleName Module);
		2576	Node parseUnnamedTypeName(NameState State);
		2577	Node parseSourceName(NameState State);
		2578	Node parseUnscopedName(NameState State, bool *isSubstName);
		2579	Node parseNestedName(NameState State);
		2580	Node parseCtorDtorName(Node &SoFar, NameState *State);
		2581
		2582	Node parseAbiTags(Node N);
		2583
		2584	struct OperatorInfo {
		2585	enum OIKind : unsigned char {
		2586	Prefix, // Prefix unary: @ expr
		2587	Postfix, // Postfix unary: expr @
		2588	Binary, // Binary: lhs @ rhs
		2589	Array, // Array index: lhs [ rhs ]
		2590	Member, // Member access: lhs @ rhs
		2591	New, // New
		2592	Del, // Delete
		2593	Call, // Function call: expr (expr*)
		2594	CCast, // C cast: (type)expr
		2595	Conditional, // Conditional: expr ? expr : expr
		2596	NameOnly, // Overload only, not allowed in expression.
		2597	// Below do not have operator names
		2598	NamedCast, // Named cast, @<type>(expr)
		2599	OfIdOp, // alignof, sizeof, typeid
		2600
		2601	Unnameable = NamedCast,
		2602	};
		2603	char Enc[2]; // Encoding
		2604	OIKind Kind; // Kind of operator
		2605	bool Flag : 1; // Entry-specific flag
		2606	Node::Prec Prec : 7; // Precedence
		2607	const char *Name; // Spelling
		2608
		2609	public:
		2610	constexpr OperatorInfo(const char (&E)[3], OIKind K, bool F, Node::Prec P,
		2611	const char *N)
		2612	: Enc{E[0], E[1]}, Kind{K}, Flag{F}, Prec{P}, Name{N} {}
		2613
		2614	public:
		2615	bool operator<(const OperatorInfo &Other) const {
		2616	return *this < Other.Enc;
		2617	}
		2618	bool operator<(const char *Peek) const {
		2619	return Enc[0] < Peek[0] \|\| (Enc[0] == Peek[0] && Enc[1] < Peek[1]);
		2620	}
		2621	bool operator==(const char *Peek) const {
		2622	return Enc[0] == Peek[0] && Enc[1] == Peek[1];
		2623	}
		2624	bool operator!=(const char *Peek) const { return !this->operator==(Peek); }
		2625
		2626	public:
		2627	StringView getSymbol() const {
		2628	StringView Res = Name;
		2629	if (Kind < Unnameable) {
		2630	assert(Res.startsWith("operator") &&
		2631	"operator name does not start with 'operator'");
		2632	Res = Res.dropFront(sizeof("operator") - 1);
		2633	Res.consumeFront(' ');
		2634	}
		2635	return Res;
		2636	}
		2637	StringView getName() const { return Name; }
		2638	OIKind getKind() const { return Kind; }
		2639	bool getFlag() const { return Flag; }
		2640	Node::Prec getPrecedence() const { return Prec; }
		2641	};
		2642	static const OperatorInfo Ops[];
		2643	static const size_t NumOps;
		2644	const OperatorInfo *parseOperatorEncoding();
		2645
		2646	/// Parse the <unresolved-name> production.
		2647	Node *parseUnresolvedName(bool Global);
		2648	Node *parseSimpleId();
		2649	Node *parseBaseUnresolvedName();
		2650	Node *parseUnresolvedType();
		2651	Node *parseDestructorName();
		2652
		2653	/// Top-level entry point into the parser.
		2654	Node *parse();
		2655	};
		2656
		2657	const char* parse_discriminator(const char* first, const char* last);
		2658
		2659	// <name> ::= <nested-name> // N
		2660	// ::= <local-name> # See Scope Encoding below // Z
		2661	// ::= <unscoped-template-name> <template-args>
		2662	// ::= <unscoped-name>
		2663	//
		2664	// <unscoped-template-name> ::= <unscoped-name>
		2665	// ::= <substitution>
		2666	template <typename Derived, typename Alloc>
		2667	Node AbstractManglingParser<Derived, Alloc>::parseName(NameState State) {
		2668	if (look() == 'N')
		2669	return getDerived().parseNestedName(State);
		2670	if (look() == 'Z')
		2671	return getDerived().parseLocalName(State);
		2672
		2673	Node *Result = nullptr;
		2674	bool IsSubst = false;
		2675
		2676	Result = getDerived().parseUnscopedName(State, &IsSubst);
		2677	if (!Result)
		2678	return nullptr;
		2679
		2680	if (look() == 'I') {
		2681	// ::= <unscoped-template-name> <template-args>
		2682	if (!IsSubst)
		2683	// An unscoped-template-name is substitutable.
		2684	Subs.push_back(Result);
		2685	Node *TA = getDerived().parseTemplateArgs(State != nullptr);
		2686	if (TA == nullptr)
		2687	return nullptr;
		2688	if (State)
		2689	State->EndsWithTemplateArgs = true;
		2690	Result = make<NameWithTemplateArgs>(Result, TA);
		2691	} else if (IsSubst) {
		2692	// The substitution case must be followed by <template-args>.
		2693	return nullptr;
		2694	}
		2695
		2696	return Result;
		2697	}
		2698
		2699	// <local-name> := Z <function encoding> E <entity name> [<discriminator>]
		2700	// := Z <function encoding> E s [<discriminator>]
		2701	// := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
		2702	template <typename Derived, typename Alloc>
		2703	Node AbstractManglingParser<Derived, Alloc>::parseLocalName(NameState State) {
		2704	if (!consumeIf('Z'))
		2705	return nullptr;
		2706	Node *Encoding = getDerived().parseEncoding();
		2707	if (Encoding == nullptr \|\| !consumeIf('E'))
		2708	return nullptr;
		2709
		2710	if (consumeIf('s')) {
		2711	First = parse_discriminator(First, Last);
		2712	auto *StringLitName = make<NameType>("string literal");
		2713	if (!StringLitName)
		2714	return nullptr;
		2715	return make<LocalName>(Encoding, StringLitName);
		2716	}
		2717
		2718	if (consumeIf('d')) {
		2719	parseNumber(true);
		2720	if (!consumeIf('_'))
		2721	return nullptr;
		2722	Node *N = getDerived().parseName(State);
		2723	if (N == nullptr)
		2724	return nullptr;
		2725	return make<LocalName>(Encoding, N);
		2726	}
		2727
		2728	Node *Entity = getDerived().parseName(State);
		2729	if (Entity == nullptr)
		2730	return nullptr;
		2731	First = parse_discriminator(First, Last);
		2732	return make<LocalName>(Encoding, Entity);
		2733	}
		2734
		2735	// <unscoped-name> ::= <unqualified-name>
		2736	// ::= St <unqualified-name> # ::std::
		2737	// [*] extension
		2738	template <typename Derived, typename Alloc>
		2739	Node *
		2740	AbstractManglingParser<Derived, Alloc>::parseUnscopedName(NameState *State,
		2741	bool *IsSubst) {
		2742
		2743	Node *Std = nullptr;
		2744	if (consumeIf("St")) {
		2745	Std = make<NameType>("std");
		2746	if (Std == nullptr)
		2747	return nullptr;
		2748	}
		2749
		2750	Node *Res = nullptr;
		2751	ModuleName *Module = nullptr;
		2752	if (look() == 'S') {
		2753	Node *S = getDerived().parseSubstitution();
		2754	if (!S)
		2755	return nullptr;
		2756	if (S->getKind() == Node::KModuleName)
		2757	Module = static_cast<ModuleName *>(S);
		2758	else if (IsSubst && Std == nullptr) {
		2759	Res = S;
		2760	*IsSubst = true;
		2761	} else {
		2762	return nullptr;
		2763	}
		2764	}
		2765
		2766	if (Res == nullptr \|\| Std != nullptr) {
		2767	Res = getDerived().parseUnqualifiedName(State, Std, Module);
		2768	}
		2769
		2770	return Res;
		2771	}
		2772
		2773	// <unqualified-name> ::= [<module-name>] L? <operator-name> [<abi-tags>]
		2774	// ::= [<module-name>] <ctor-dtor-name> [<abi-tags>]
		2775	// ::= [<module-name>] L? <source-name> [<abi-tags>]
		2776	// ::= [<module-name>] L? <unnamed-type-name> [<abi-tags>]
		2777	// # structured binding declaration
		2778	// ::= [<module-name>] L? DC <source-name>+ E
		2779	template <typename Derived, typename Alloc>
		2780	Node *AbstractManglingParser<Derived, Alloc>::parseUnqualifiedName(
		2781	NameState State, Node Scope, ModuleName *Module) {
		2782	if (getDerived().parseModuleNameOpt(Module))
		2783	return nullptr;
		2784
		2785	consumeIf('L');
		2786
		2787	Node *Result;
		2788	if (look() >= '1' && look() <= '9') {
		2789	Result = getDerived().parseSourceName(State);
		2790	} else if (look() == 'U') {
		2791	Result = getDerived().parseUnnamedTypeName(State);
		2792	} else if (consumeIf("DC")) {
		2793	// Structured binding
		2794	size_t BindingsBegin = Names.size();
		2795	do {
		2796	Node *Binding = getDerived().parseSourceName(State);
		2797	if (Binding == nullptr)
		2798	return nullptr;
		2799	Names.push_back(Binding);
		2800	} while (!consumeIf('E'));
		2801	Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
		2802	} else if (look() == 'C' \|\| look() == 'D') {
		2803	// A <ctor-dtor-name>.
		2804	if (Scope == nullptr \|\| Module != nullptr)
		2805	return nullptr;
		2806	Result = getDerived().parseCtorDtorName(Scope, State);
		2807	} else {
		2808	Result = getDerived().parseOperatorName(State);
		2809	}
		2810
		2811	if (Result != nullptr && Module != nullptr)
		2812	Result = make<ModuleEntity>(Module, Result);
		2813	if (Result != nullptr)
		2814	Result = getDerived().parseAbiTags(Result);
		2815	if (Result != nullptr && Scope != nullptr)
		2816	Result = make<NestedName>(Scope, Result);
		2817
		2818	return Result;
		2819	}
		2820
		2821	// <module-name> ::= <module-subname>
		2822	// ::= <module-name> <module-subname>
		2823	// ::= <substitution> # passed in by caller
		2824	// <module-subname> ::= W <source-name>
		2825	// ::= W P <source-name>
		2826	template <typename Derived, typename Alloc>
		2827	bool AbstractManglingParser<Derived, Alloc>::parseModuleNameOpt(
		2828	ModuleName *&Module) {
		2829	while (consumeIf('W')) {
		2830	bool IsPartition = consumeIf('P');
		2831	Node *Sub = getDerived().parseSourceName(nullptr);
		2832	if (!Sub)
		2833	return true;
		2834	Module =
		2835	static_cast<ModuleName *>(make<ModuleName>(Module, Sub, IsPartition));
		2836	Subs.push_back(Module);
		2837	}
		2838
		2839	return false;
		2840	}
		2841
		2842	// <unnamed-type-name> ::= Ut [<nonnegative number>] _
		2843	// ::= <closure-type-name>
		2844	//
		2845	// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
		2846	//
		2847	// <lambda-sig> ::= <parameter type>+ # Parameter types or "v" if the lambda has no parameters
		2848	template <typename Derived, typename Alloc>
		2849	Node *
		2850	AbstractManglingParser<Derived, Alloc>::parseUnnamedTypeName(NameState *State) {
		2851	// <template-params> refer to the innermost <template-args>. Clear out any
		2852	// outer args that we may have inserted into TemplateParams.
		2853	if (State != nullptr)
		2854	TemplateParams.clear();
		2855
		2856	if (consumeIf("Ut")) {
		2857	StringView Count = parseNumber();
		2858	if (!consumeIf('_'))
		2859	return nullptr;
		2860	return make<UnnamedTypeName>(Count);
		2861	}
		2862	if (consumeIf("Ul")) {
		2863	ScopedOverride<size_t> SwapParams(ParsingLambdaParamsAtLevel,
		2864	TemplateParams.size());
		2865	ScopedTemplateParamList LambdaTemplateParams(this);
		2866
		2867	size_t ParamsBegin = Names.size();
		2868	while (look() == 'T' &&
		2869	StringView("yptn").find(look(1)) != StringView::npos) {
		2870	Node *T = parseTemplateParamDecl();
		2871	if (!T)
		2872	return nullptr;
		2873	Names.push_back(T);
		2874	}
		2875	NodeArray TempParams = popTrailingNodeArray(ParamsBegin);
		2876
		2877	// FIXME: If TempParams is empty and none of the function parameters
		2878	// includes 'auto', we should remove LambdaTemplateParams from the
		2879	// TemplateParams list. Unfortunately, we don't find out whether there are
		2880	// any 'auto' parameters until too late in an example such as:
		2881	//
		2882	// template<typename T> void f(
		2883	// decltype([](decltype([]<typename T>(T v) {}),
		2884	// auto) {})) {}
		2885	// template<typename T> void f(
		2886	// decltype([](decltype([]<typename T>(T w) {}),
		2887	// int) {})) {}
		2888	//
		2889	// Here, the type of v is at level 2 but the type of w is at level 1. We
		2890	// don't find this out until we encounter the type of the next parameter.
		2891	//
		2892	// However, compilers can't actually cope with the former example in
		2893	// practice, and it's likely to be made ill-formed in future, so we don't
		2894	// need to support it here.
		2895	//
		2896	// If we encounter an 'auto' in the function parameter types, we will
		2897	// recreate a template parameter scope for it, but any intervening lambdas
		2898	// will be parsed in the 'wrong' template parameter depth.
		2899	if (TempParams.empty())
		2900	TemplateParams.pop_back();
		2901
		2902	if (!consumeIf("vE")) {
		2903	do {
		2904	Node *P = getDerived().parseType();
		2905	if (P == nullptr)
		2906	return nullptr;
		2907	Names.push_back(P);
		2908	} while (!consumeIf('E'));
		2909	}
		2910	NodeArray Params = popTrailingNodeArray(ParamsBegin);
		2911
		2912	StringView Count = parseNumber();
		2913	if (!consumeIf('_'))
		2914	return nullptr;
		2915	return make<ClosureTypeName>(TempParams, Params, Count);
		2916	}
		2917	if (consumeIf("Ub")) {
		2918	(void)parseNumber();
		2919	if (!consumeIf('_'))
		2920	return nullptr;
		2921	return make<NameType>("'block-literal'");
		2922	}
		2923	return nullptr;
		2924	}
		2925
		2926	// <source-name> ::= <positive length number> <identifier>
		2927	template <typename Derived, typename Alloc>
		2928	Node AbstractManglingParser<Derived, Alloc>::parseSourceName(NameState ) {
		2929	size_t Length = 0;
		2930	if (parsePositiveInteger(&Length))
		2931	return nullptr;
		2932	if (numLeft() < Length \|\| Length == 0)
		2933	return nullptr;
		2934	StringView Name(First, First + Length);
		2935	First += Length;
		2936	if (Name.startsWith("_GLOBAL__N"))
		2937	return make<NameType>("(anonymous namespace)");
		2938	return make<NameType>(Name);
		2939	}
		2940
		2941	// Operator encodings
		2942	template <typename Derived, typename Alloc>
		2943	const typename AbstractManglingParser<
		2944	Derived, Alloc>::OperatorInfo AbstractManglingParser<Derived,
		2945	Alloc>::Ops[] = {
		2946	// Keep ordered by encoding
		2947	{"aN", OperatorInfo::Binary, false, Node::Prec::Assign, "operator&="},
		2948	{"aS", OperatorInfo::Binary, false, Node::Prec::Assign, "operator="},
		2949	{"aa", OperatorInfo::Binary, false, Node::Prec::AndIf, "operator&&"},
		2950	{"ad", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator&"},
		2951	{"an", OperatorInfo::Binary, false, Node::Prec::And, "operator&"},
		2952	{"at", OperatorInfo::OfIdOp, /Type/ true, Node::Prec::Unary, "alignof "},
		2953	{"aw", OperatorInfo::NameOnly, false, Node::Prec::Primary,
		2954	"operator co_await"},
		2955	{"az", OperatorInfo::OfIdOp, /Type/ false, Node::Prec::Unary, "alignof "},
		2956	{"cc", OperatorInfo::NamedCast, false, Node::Prec::Postfix, "const_cast"},
		2957	{"cl", OperatorInfo::Call, false, Node::Prec::Postfix, "operator()"},
		2958	{"cm", OperatorInfo::Binary, false, Node::Prec::Comma, "operator,"},
		2959	{"co", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator~"},
		2960	{"cv", OperatorInfo::CCast, false, Node::Prec::Cast, "operator"}, // C Cast
		2961	{"dV", OperatorInfo::Binary, false, Node::Prec::Assign, "operator/="},
		2962	{"da", OperatorInfo::Del, /Ary/ true, Node::Prec::Unary,
		2963	"operator delete[]"},
		2964	{"dc", OperatorInfo::NamedCast, false, Node::Prec::Postfix, "dynamic_cast"},
		2965	{"de", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator*"},
		2966	{"dl", OperatorInfo::Del, /Ary/ false, Node::Prec::Unary,
		2967	"operator delete"},
		2968	{"ds", OperatorInfo::Member, /Named/ false, Node::Prec::PtrMem,
		2969	"operator.*"},
		2970	{"dt", OperatorInfo::Member, /Named/ false, Node::Prec::Postfix,
		2971	"operator."},
		2972	{"dv", OperatorInfo::Binary, false, Node::Prec::Assign, "operator/"},
		2973	{"eO", OperatorInfo::Binary, false, Node::Prec::Assign, "operator^="},
		2974	{"eo", OperatorInfo::Binary, false, Node::Prec::Xor, "operator^"},
		2975	{"eq", OperatorInfo::Binary, false, Node::Prec::Equality, "operator=="},
		2976	{"ge", OperatorInfo::Binary, false, Node::Prec::Relational, "operator>="},
		2977	{"gt", OperatorInfo::Binary, false, Node::Prec::Relational, "operator>"},
		2978	{"ix", OperatorInfo::Array, false, Node::Prec::Postfix, "operator[]"},
		2979	{"lS", OperatorInfo::Binary, false, Node::Prec::Assign, "operator<<="},
		2980	{"le", OperatorInfo::Binary, false, Node::Prec::Relational, "operator<="},
		2981	{"ls", OperatorInfo::Binary, false, Node::Prec::Shift, "operator<<"},
		2982	{"lt", OperatorInfo::Binary, false, Node::Prec::Relational, "operator<"},
		2983	{"mI", OperatorInfo::Binary, false, Node::Prec::Assign, "operator-="},
		2984	{"mL", OperatorInfo::Binary, false, Node::Prec::Assign, "operator*="},
		2985	{"mi", OperatorInfo::Binary, false, Node::Prec::Additive, "operator-"},
		2986	{"ml", OperatorInfo::Binary, false, Node::Prec::Multiplicative,
		2987	"operator*"},
		2988	{"mm", OperatorInfo::Postfix, false, Node::Prec::Postfix, "operator--"},
		2989	{"na", OperatorInfo::New, /Ary/ true, Node::Prec::Unary,
		2990	"operator new[]"},
		2991	{"ne", OperatorInfo::Binary, false, Node::Prec::Equality, "operator!="},
		2992	{"ng", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator-"},
		2993	{"nt", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator!"},
		2994	{"nw", OperatorInfo::New, /Ary/ false, Node::Prec::Unary, "operator new"},
		2995	{"oR", OperatorInfo::Binary, false, Node::Prec::Assign, "operator\|="},
		2996	{"oo", OperatorInfo::Binary, false, Node::Prec::OrIf, "operator\|\|"},
		2997	{"or", OperatorInfo::Binary, false, Node::Prec::Ior, "operator\|"},
		2998	{"pL", OperatorInfo::Binary, false, Node::Prec::Assign, "operator+="},
		2999	{"pl", OperatorInfo::Binary, false, Node::Prec::Additive, "operator+"},
		3000	{"pm", OperatorInfo::Member, /Named/ false, Node::Prec::PtrMem,
		3001	"operator->*"},
		3002	{"pp", OperatorInfo::Postfix, false, Node::Prec::Postfix, "operator++"},
		3003	{"ps", OperatorInfo::Prefix, false, Node::Prec::Unary, "operator+"},
		3004	{"pt", OperatorInfo::Member, /Named/ true, Node::Prec::Postfix,
		3005	"operator->"},
		3006	{"qu", OperatorInfo::Conditional, false, Node::Prec::Conditional,
		3007	"operator?"},
		3008	{"rM", OperatorInfo::Binary, false, Node::Prec::Assign, "operator%="},
		3009	{"rS", OperatorInfo::Binary, false, Node::Prec::Assign, "operator>>="},
		3010	{"rc", OperatorInfo::NamedCast, false, Node::Prec::Postfix,
		3011	"reinterpret_cast"},
		3012	{"rm", OperatorInfo::Binary, false, Node::Prec::Multiplicative,
		3013	"operator%"},
		3014	{"rs", OperatorInfo::Binary, false, Node::Prec::Shift, "operator>>"},
		3015	{"sc", OperatorInfo::NamedCast, false, Node::Prec::Postfix, "static_cast"},
		3016	{"ss", OperatorInfo::Binary, false, Node::Prec::Spaceship, "operator<=>"},
		3017	{"st", OperatorInfo::OfIdOp, /Type/ true, Node::Prec::Unary, "sizeof "},
		3018	{"sz", OperatorInfo::OfIdOp, /Type/ false, Node::Prec::Unary, "sizeof "},
		3019	{"te", OperatorInfo::OfIdOp, /Type/ false, Node::Prec::Postfix,
		3020	"typeid "},
		3021	{"ti", OperatorInfo::OfIdOp, /Type/ true, Node::Prec::Postfix, "typeid "},
		3022	};
		3023	template <typename Derived, typename Alloc>
		3024	const size_t AbstractManglingParser<Derived, Alloc>::NumOps = sizeof(Ops) /
		3025	sizeof(Ops[0]);
		3026
		3027	// If the next 2 chars are an operator encoding, consume them and return their
		3028	// OperatorInfo. Otherwise return nullptr.
		3029	template <typename Derived, typename Alloc>
		3030	const typename AbstractManglingParser<Derived, Alloc>::OperatorInfo *
		3031	AbstractManglingParser<Derived, Alloc>::parseOperatorEncoding() {
		3032	if (numLeft() < 2)
		3033	return nullptr;
		3034
		3035	// We can't use lower_bound as that can link to symbols in the C++ library,
		3036	// and this must remain independant of that.
		3037	size_t lower = 0u, upper = NumOps - 1; // Inclusive bounds.
		3038	while (upper != lower) {
		3039	size_t middle = (upper + lower) / 2;
		3040	if (Ops[middle] < First)
		3041	lower = middle + 1;
		3042	else
		3043	upper = middle;
		3044	}
		3045	if (Ops[lower] != First)
		3046	return nullptr;
		3047
		3048	First += 2;
		3049	return &Ops[lower];
		3050	}
		3051
		3052	// <operator-name> ::= See parseOperatorEncoding()
		3053	// ::= li <source-name> # operator ""
		3054	// ::= v <digit> <source-name> # vendor extended operator
		3055	template <typename Derived, typename Alloc>
		3056	Node *
		3057	AbstractManglingParser<Derived, Alloc>::parseOperatorName(NameState *State) {
		3058	if (const auto *Op = parseOperatorEncoding()) {
		3059	if (Op->getKind() == OperatorInfo::CCast) {
		3060	// ::= cv <type> # (cast)
		3061	ScopedOverride<bool> SaveTemplate(TryToParseTemplateArgs, false);
		3062	// If we're parsing an encoding, State != nullptr and the conversion
		3063	// operators' <type> could have a <template-param> that refers to some
		3064	// <template-arg>s further ahead in the mangled name.
		3065	ScopedOverride<bool> SavePermit(PermitForwardTemplateReferences,
		3066	PermitForwardTemplateReferences \|\|
		3067	State != nullptr);
		3068	Node *Ty = getDerived().parseType();
		3069	if (Ty == nullptr)
		3070	return nullptr;
		3071	if (State) State->CtorDtorConversion = true;
		3072	return make<ConversionOperatorType>(Ty);
		3073	}
		3074
		3075	if (Op->getKind() >= OperatorInfo::Unnameable)
		3076	/* Not a nameable operator. */
		3077	return nullptr;
		3078	if (Op->getKind() == OperatorInfo::Member && !Op->getFlag())
		3079	/* Not a nameable MemberExpr */
		3080	return nullptr;
		3081
		3082	return make<NameType>(Op->getName());
		3083	}
		3084
		3085	if (consumeIf("li")) {
		3086	// ::= li <source-name> # operator ""
		3087	Node *SN = getDerived().parseSourceName(State);
		3088	if (SN == nullptr)
		3089	return nullptr;
		3090	return make<LiteralOperator>(SN);
		3091	}
		3092
		3093	if (consumeIf('v')) {
		3094	// ::= v <digit> <source-name> # vendor extended operator
		3095	if (look() >= '0' && look() <= '9') {
		3096	First++;
		3097	Node *SN = getDerived().parseSourceName(State);
		3098	if (SN == nullptr)
		3099	return nullptr;
		3100	return make<ConversionOperatorType>(SN);
		3101	}
		3102	return nullptr;
		3103	}
		3104
		3105	return nullptr;
		3106	}
		3107
		3108	// <ctor-dtor-name> ::= C1 # complete object constructor
		3109	// ::= C2 # base object constructor
		3110	// ::= C3 # complete object allocating constructor
		3111	// extension ::= C4 # gcc old-style "[unified]" constructor
		3112	// extension ::= C5 # the COMDAT used for ctors
		3113	// ::= D0 # deleting destructor
		3114	// ::= D1 # complete object destructor
		3115	// ::= D2 # base object destructor
		3116	// extension ::= D4 # gcc old-style "[unified]" destructor
		3117	// extension ::= D5 # the COMDAT used for dtors
		3118	template <typename Derived, typename Alloc>
		3119	Node *
		3120	AbstractManglingParser<Derived, Alloc>::parseCtorDtorName(Node *&SoFar,
		3121	NameState *State) {
		3122	if (SoFar->getKind() == Node::KSpecialSubstitution) {
		3123	// Expand the special substitution.
		3124	SoFar = make<ExpandedSpecialSubstitution>(
		3125	static_cast<SpecialSubstitution *>(SoFar));
		3126	if (!SoFar)
		3127	return nullptr;
		3128	}
		3129
		3130	if (consumeIf('C')) {
		3131	bool IsInherited = consumeIf('I');
		3132	if (look() != '1' && look() != '2' && look() != '3' && look() != '4' &&
		3133	look() != '5')
		3134	return nullptr;
		3135	int Variant = look() - '0';
		3136	++First;
		3137	if (State) State->CtorDtorConversion = true;
		3138	if (IsInherited) {
		3139	if (getDerived().parseName(State) == nullptr)
		3140	return nullptr;
		3141	}
		3142	return make<CtorDtorName>(SoFar, /IsDtor=/false, Variant);
		3143	}
		3144
		3145	if (look() == 'D' && (look(1) == '0' \|\| look(1) == '1' \|\| look(1) == '2' \|\|
		3146	look(1) == '4' \|\| look(1) == '5')) {
		3147	int Variant = look(1) - '0';
		3148	First += 2;
		3149	if (State) State->CtorDtorConversion = true;
		3150	return make<CtorDtorName>(SoFar, /IsDtor=/true, Variant);
		3151	}
		3152
		3153	return nullptr;
		3154	}
		3155
		3156	// <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix>
		3157	// <unqualified-name> E
		3158	// ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix>
		3159	// <template-args> E
		3160	//
		3161	// <prefix> ::= <prefix> <unqualified-name>
		3162	// ::= <template-prefix> <template-args>
		3163	// ::= <template-param>
		3164	// ::= <decltype>
		3165	// ::= # empty
		3166	// ::= <substitution>
		3167	// ::= <prefix> <data-member-prefix>
		3168	// [*] extension
		3169	//
		3170	// <data-member-prefix> := <member source-name> [<template-args>] M
		3171	//
		3172	// <template-prefix> ::= <prefix> <template unqualified-name>
		3173	// ::= <template-param>
		3174	// ::= <substitution>
		3175	template <typename Derived, typename Alloc>
		3176	Node *
		3177	AbstractManglingParser<Derived, Alloc>::parseNestedName(NameState *State) {
		3178	if (!consumeIf('N'))
		3179	return nullptr;
		3180
		3181	Qualifiers CVTmp = parseCVQualifiers();
		3182	if (State) State->CVQualifiers = CVTmp;
		3183
		3184	if (consumeIf('O')) {
		3185	if (State) State->ReferenceQualifier = FrefQualRValue;
		3186	} else if (consumeIf('R')) {
		3187	if (State) State->ReferenceQualifier = FrefQualLValue;
		3188	} else {
		3189	if (State) State->ReferenceQualifier = FrefQualNone;
		3190	}
		3191
		3192	Node *SoFar = nullptr;
		3193	while (!consumeIf('E')) {
		3194	if (State)
		3195	// Only set end-with-template on the case that does that.
		3196	State->EndsWithTemplateArgs = false;
		3197
		3198	if (look() == 'T') {
		3199	// ::= <template-param>
		3200	if (SoFar != nullptr)
		3201	return nullptr; // Cannot have a prefix.
		3202	SoFar = getDerived().parseTemplateParam();
		3203	} else if (look() == 'I') {
		3204	// ::= <template-prefix> <template-args>
		3205	if (SoFar == nullptr)
		3206	return nullptr; // Must have a prefix.
		3207	Node *TA = getDerived().parseTemplateArgs(State != nullptr);
		3208	if (TA == nullptr)
		3209	return nullptr;
		3210	if (SoFar->getKind() == Node::KNameWithTemplateArgs)
		3211	// Semantically <template-args> <template-args> cannot be generated by a
		3212	// C++ entity. There will always be [something like] a name between
		3213	// them.
		3214	return nullptr;
		3215	if (State)
		3216	State->EndsWithTemplateArgs = true;
		3217	SoFar = make<NameWithTemplateArgs>(SoFar, TA);
		3218	} else if (look() == 'D' && (look(1) == 't' \|\| look(1) == 'T')) {
		3219	// ::= <decltype>
		3220	if (SoFar != nullptr)
		3221	return nullptr; // Cannot have a prefix.
		3222	SoFar = getDerived().parseDecltype();
		3223	} else {
		3224	ModuleName *Module = nullptr;
		3225
		3226	if (look() == 'S') {
		3227	// ::= <substitution>
		3228	Node *S = nullptr;
		3229	if (look(1) == 't') {
		3230	First += 2;
		3231	S = make<NameType>("std");
		3232	} else {
		3233	S = getDerived().parseSubstitution();
		3234	}
		3235	if (!S)
		3236	return nullptr;
		3237	if (S->getKind() == Node::KModuleName) {
		3238	Module = static_cast<ModuleName *>(S);
		3239	} else if (SoFar != nullptr) {
		3240	return nullptr; // Cannot have a prefix.
		3241	} else {
		3242	SoFar = S;
		3243	continue; // Do not push a new substitution.
		3244	}
		3245	}
		3246
		3247	// ::= [<prefix>] <unqualified-name>
		3248	SoFar = getDerived().parseUnqualifiedName(State, SoFar, Module);
		3249	}
		3250
		3251	if (SoFar == nullptr)
		3252	return nullptr;
		3253	Subs.push_back(SoFar);
		3254
		3255	// No longer used.
		3256	// <data-member-prefix> := <member source-name> [<template-args>] M
		3257	consumeIf('M');
		3258	}
		3259
		3260	if (SoFar == nullptr \|\| Subs.empty())
		3261	return nullptr;
		3262
		3263	Subs.pop_back();
		3264	return SoFar;
		3265	}
		3266
		3267	// <simple-id> ::= <source-name> [ <template-args> ]
		3268	template <typename Derived, typename Alloc>
		3269	Node *AbstractManglingParser<Derived, Alloc>::parseSimpleId() {
		3270	Node SN = getDerived().parseSourceName(/NameState=*/nullptr);
		3271	if (SN == nullptr)
		3272	return nullptr;
		3273	if (look() == 'I') {
		3274	Node *TA = getDerived().parseTemplateArgs();
		3275	if (TA == nullptr)
		3276	return nullptr;
		3277	return make<NameWithTemplateArgs>(SN, TA);
		3278	}
		3279	return SN;
		3280	}
		3281
		3282	// <destructor-name> ::= <unresolved-type> # e.g., ~T or ~decltype(f())
		3283	// ::= <simple-id> # e.g., ~A<2*N>
		3284	template <typename Derived, typename Alloc>
		3285	Node *AbstractManglingParser<Derived, Alloc>::parseDestructorName() {
		3286	Node *Result;
		3287	if (std::isdigit(look()))
		3288	Result = getDerived().parseSimpleId();
		3289	else
		3290	Result = getDerived().parseUnresolvedType();
		3291	if (Result == nullptr)
		3292	return nullptr;
		3293	return make<DtorName>(Result);
		3294	}
		3295
		3296	// <unresolved-type> ::= <template-param>
		3297	// ::= <decltype>
		3298	// ::= <substitution>
		3299	template <typename Derived, typename Alloc>
		3300	Node *AbstractManglingParser<Derived, Alloc>::parseUnresolvedType() {
		3301	if (look() == 'T') {
		3302	Node *TP = getDerived().parseTemplateParam();
		3303	if (TP == nullptr)
		3304	return nullptr;
		3305	Subs.push_back(TP);
		3306	return TP;
		3307	}
		3308	if (look() == 'D') {
		3309	Node *DT = getDerived().parseDecltype();
		3310	if (DT == nullptr)
		3311	return nullptr;
		3312	Subs.push_back(DT);
		3313	return DT;
		3314	}
		3315	return getDerived().parseSubstitution();
		3316	}
		3317
		3318	// <base-unresolved-name> ::= <simple-id> # unresolved name
		3319	// extension ::= <operator-name> # unresolved operator-function-id
		3320	// extension ::= <operator-name> <template-args> # unresolved operator template-id
		3321	// ::= on <operator-name> # unresolved operator-function-id
		3322	// ::= on <operator-name> <template-args> # unresolved operator template-id
		3323	// ::= dn <destructor-name> # destructor or pseudo-destructor;
		3324	// # e.g. ~X or ~X<N-1>
		3325	template <typename Derived, typename Alloc>
		3326	Node *AbstractManglingParser<Derived, Alloc>::parseBaseUnresolvedName() {
		3327	if (std::isdigit(look()))
		3328	return getDerived().parseSimpleId();
		3329
		3330	if (consumeIf("dn"))
		3331	return getDerived().parseDestructorName();
		3332
		3333	consumeIf("on");
		3334
		3335	Node Oper = getDerived().parseOperatorName(/NameState=*/nullptr);
		3336	if (Oper == nullptr)
		3337	return nullptr;
		3338	if (look() == 'I') {
		3339	Node *TA = getDerived().parseTemplateArgs();
		3340	if (TA == nullptr)
		3341	return nullptr;
		3342	return make<NameWithTemplateArgs>(Oper, TA);
		3343	}
		3344	return Oper;
		3345	}
		3346
		3347	// <unresolved-name>
		3348	// extension ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
		3349	// ::= [gs] <base-unresolved-name> # x or (with "gs") ::x
		3350	// ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
		3351	// # A::x, N::y, A<T>::z; "gs" means leading "::"
		3352	// [gs] has been parsed by caller.
		3353	// ::= sr <unresolved-type> <base-unresolved-name> # T::x / decltype(p)::x
		3354	// extension ::= sr <unresolved-type> <template-args> <base-unresolved-name>
		3355	// # T::N::x /decltype(p)::N::x
		3356	// (ignored) ::= srN <unresolved-type> <unresolved-qualifier-level>+ E <base-unresolved-name>
		3357	//
		3358	// <unresolved-qualifier-level> ::= <simple-id>
		3359	template <typename Derived, typename Alloc>
		3360	Node *AbstractManglingParser<Derived, Alloc>::parseUnresolvedName(bool Global) {
		3361	Node *SoFar = nullptr;
		3362
		3363	// srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
		3364	// srN <unresolved-type> <unresolved-qualifier-level>+ E <base-unresolved-name>
		3365	if (consumeIf("srN")) {
		3366	SoFar = getDerived().parseUnresolvedType();
		3367	if (SoFar == nullptr)
		3368	return nullptr;
		3369
		3370	if (look() == 'I') {
		3371	Node *TA = getDerived().parseTemplateArgs();
		3372	if (TA == nullptr)
		3373	return nullptr;
		3374	SoFar = make<NameWithTemplateArgs>(SoFar, TA);
		3375	if (!SoFar)
		3376	return nullptr;
		3377	}
		3378
		3379	while (!consumeIf('E')) {
		3380	Node *Qual = getDerived().parseSimpleId();
		3381	if (Qual == nullptr)
		3382	return nullptr;
		3383	SoFar = make<QualifiedName>(SoFar, Qual);
		3384	if (!SoFar)
		3385	return nullptr;
		3386	}
		3387
		3388	Node *Base = getDerived().parseBaseUnresolvedName();
		3389	if (Base == nullptr)
		3390	return nullptr;
		3391	return make<QualifiedName>(SoFar, Base);
		3392	}
		3393
		3394	// [gs] <base-unresolved-name> # x or (with "gs") ::x
		3395	if (!consumeIf("sr")) {
		3396	SoFar = getDerived().parseBaseUnresolvedName();
		3397	if (SoFar == nullptr)
		3398	return nullptr;
		3399	if (Global)
		3400	SoFar = make<GlobalQualifiedName>(SoFar);
		3401	return SoFar;
		3402	}
		3403
		3404	// [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
		3405	if (std::isdigit(look())) {
		3406	do {
		3407	Node *Qual = getDerived().parseSimpleId();
		3408	if (Qual == nullptr)
		3409	return nullptr;
		3410	if (SoFar)
		3411	SoFar = make<QualifiedName>(SoFar, Qual);
		3412	else if (Global)
		3413	SoFar = make<GlobalQualifiedName>(Qual);
		3414	else
		3415	SoFar = Qual;
		3416	if (!SoFar)
		3417	return nullptr;
		3418	} while (!consumeIf('E'));
		3419	}
		3420	// sr <unresolved-type> <base-unresolved-name>
		3421	// sr <unresolved-type> <template-args> <base-unresolved-name>
		3422	else {
		3423	SoFar = getDerived().parseUnresolvedType();
		3424	if (SoFar == nullptr)
		3425	return nullptr;
		3426
		3427	if (look() == 'I') {
		3428	Node *TA = getDerived().parseTemplateArgs();
		3429	if (TA == nullptr)
		3430	return nullptr;
		3431	SoFar = make<NameWithTemplateArgs>(SoFar, TA);
		3432	if (!SoFar)
		3433	return nullptr;
		3434	}
		3435	}
		3436
		3437	assert(SoFar != nullptr);
		3438
		3439	Node *Base = getDerived().parseBaseUnresolvedName();
		3440	if (Base == nullptr)
		3441	return nullptr;
		3442	return make<QualifiedName>(SoFar, Base);
		3443	}
		3444
		3445	// <abi-tags> ::= <abi-tag> [<abi-tags>]
		3446	// <abi-tag> ::= B <source-name>
		3447	template <typename Derived, typename Alloc>
		3448	Node AbstractManglingParser<Derived, Alloc>::parseAbiTags(Node N) {
		3449	while (consumeIf('B')) {
		3450	StringView SN = parseBareSourceName();
		3451	if (SN.empty())
		3452	return nullptr;
		3453	N = make<AbiTagAttr>(N, SN);
		3454	if (!N)
		3455	return nullptr;
		3456	}
		3457	return N;
		3458	}
		3459
		3460	// <number> ::= [n] <non-negative decimal integer>
		3461	template <typename Alloc, typename Derived>
		3462	StringView
		3463	AbstractManglingParser<Alloc, Derived>::parseNumber(bool AllowNegative) {
		3464	const char *Tmp = First;
		3465	if (AllowNegative)
		3466	consumeIf('n');
		3467	if (numLeft() == 0 \|\| !std::isdigit(*First))
		3468	return StringView();
		3469	while (numLeft() != 0 && std::isdigit(*First))
		3470	++First;
		3471	return StringView(Tmp, First);
		3472	}
		3473
		3474	// <positive length number> ::= [0-9]*
		3475	template <typename Alloc, typename Derived>
		3476	bool AbstractManglingParser<Alloc, Derived>::parsePositiveInteger(size_t *Out) {
		3477	*Out = 0;
		3478	if (look() < '0' \|\| look() > '9')
		3479	return true;
		3480	while (look() >= '0' && look() <= '9') {
		3481	Out = 10;
		3482	*Out += static_cast<size_t>(consume() - '0');
		3483	}
		3484	return false;
		3485	}
		3486
		3487	template <typename Alloc, typename Derived>
		3488	StringView AbstractManglingParser<Alloc, Derived>::parseBareSourceName() {
		3489	size_t Int = 0;
		3490	if (parsePositiveInteger(&Int) \|\| numLeft() < Int)
		3491	return StringView();
		3492	StringView R(First, First + Int);
		3493	First += Int;
		3494	return R;
		3495	}
		3496
		3497	// <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
		3498	//
		3499	// <exception-spec> ::= Do # non-throwing exception-specification (e.g., noexcept, throw())
		3500	// ::= DO <expression> E # computed (instantiation-dependent) noexcept
		3501	// ::= Dw <type>+ E # dynamic exception specification with instantiation-dependent types
		3502	//
		3503	// <ref-qualifier> ::= R # & ref-qualifier
		3504	// <ref-qualifier> ::= O # && ref-qualifier
		3505	template <typename Derived, typename Alloc>
		3506	Node *AbstractManglingParser<Derived, Alloc>::parseFunctionType() {
		3507	Qualifiers CVQuals = parseCVQualifiers();
		3508
		3509	Node *ExceptionSpec = nullptr;
		3510	if (consumeIf("Do")) {
		3511	ExceptionSpec = make<NameType>("noexcept");
		3512	if (!ExceptionSpec)
		3513	return nullptr;
		3514	} else if (consumeIf("DO")) {
		3515	Node *E = getDerived().parseExpr();
		3516	if (E == nullptr \|\| !consumeIf('E'))
		3517	return nullptr;
		3518	ExceptionSpec = make<NoexceptSpec>(E);
		3519	if (!ExceptionSpec)
		3520	return nullptr;
		3521	} else if (consumeIf("Dw")) {
		3522	size_t SpecsBegin = Names.size();
		3523	while (!consumeIf('E')) {
		3524	Node *T = getDerived().parseType();
		3525	if (T == nullptr)
		3526	return nullptr;
		3527	Names.push_back(T);
		3528	}
		3529	ExceptionSpec =
		3530	make<DynamicExceptionSpec>(popTrailingNodeArray(SpecsBegin));
		3531	if (!ExceptionSpec)
		3532	return nullptr;
		3533	}
		3534
		3535	consumeIf("Dx"); // transaction safe
		3536
		3537	if (!consumeIf('F'))
		3538	return nullptr;
		3539	consumeIf('Y'); // extern "C"
		3540	Node *ReturnType = getDerived().parseType();
		3541	if (ReturnType == nullptr)
		3542	return nullptr;
		3543
		3544	FunctionRefQual ReferenceQualifier = FrefQualNone;
		3545	size_t ParamsBegin = Names.size();
		3546	while (true) {
		3547	if (consumeIf('E'))
		3548	break;
		3549	if (consumeIf('v'))
		3550	continue;
		3551	if (consumeIf("RE")) {
		3552	ReferenceQualifier = FrefQualLValue;
		3553	break;
		3554	}
		3555	if (consumeIf("OE")) {
		3556	ReferenceQualifier = FrefQualRValue;
		3557	break;
		3558	}
		3559	Node *T = getDerived().parseType();
		3560	if (T == nullptr)
		3561	return nullptr;
		3562	Names.push_back(T);
		3563	}
		3564
		3565	NodeArray Params = popTrailingNodeArray(ParamsBegin);
		3566	return make<FunctionType>(ReturnType, Params, CVQuals,
		3567	ReferenceQualifier, ExceptionSpec);
		3568	}
		3569
		3570	// extension:
		3571	// <vector-type> ::= Dv <positive dimension number> _ <extended element type>
		3572	// ::= Dv [<dimension expression>] _ <element type>
		3573	// <extended element type> ::= <element type>
		3574	// ::= p # AltiVec vector pixel
		3575	template <typename Derived, typename Alloc>
		3576	Node *AbstractManglingParser<Derived, Alloc>::parseVectorType() {
		3577	if (!consumeIf("Dv"))
		3578	return nullptr;
		3579	if (look() >= '1' && look() <= '9') {
		3580	Node *DimensionNumber = make<NameType>(parseNumber());
		3581	if (!DimensionNumber)
		3582	return nullptr;
		3583	if (!consumeIf('_'))
		3584	return nullptr;
		3585	if (consumeIf('p'))
		3586	return make<PixelVectorType>(DimensionNumber);
		3587	Node *ElemType = getDerived().parseType();
		3588	if (ElemType == nullptr)
		3589	return nullptr;
		3590	return make<VectorType>(ElemType, DimensionNumber);
		3591	}
		3592
		3593	if (!consumeIf('_')) {
		3594	Node *DimExpr = getDerived().parseExpr();
		3595	if (!DimExpr)
		3596	return nullptr;
		3597	if (!consumeIf('_'))
		3598	return nullptr;
		3599	Node *ElemType = getDerived().parseType();
		3600	if (!ElemType)
		3601	return nullptr;
		3602	return make<VectorType>(ElemType, DimExpr);
		3603	}
		3604	Node *ElemType = getDerived().parseType();
		3605	if (!ElemType)
		3606	return nullptr;
		3607	return make<VectorType>(ElemType, /Dimension=/nullptr);
		3608	}
		3609
		3610	// <decltype> ::= Dt <expression> E # decltype of an id-expression or class member access (C++0x)
		3611	// ::= DT <expression> E # decltype of an expression (C++0x)
		3612	template <typename Derived, typename Alloc>
		3613	Node *AbstractManglingParser<Derived, Alloc>::parseDecltype() {
		3614	if (!consumeIf('D'))
		3615	return nullptr;
		3616	if (!consumeIf('t') && !consumeIf('T'))
		3617	return nullptr;
		3618	Node *E = getDerived().parseExpr();
		3619	if (E == nullptr)
		3620	return nullptr;
		3621	if (!consumeIf('E'))
		3622	return nullptr;
		3623	return make<EnclosingExpr>("decltype", E);
		3624	}
		3625
		3626	// <array-type> ::= A <positive dimension number> _ <element type>
		3627	// ::= A [<dimension expression>] _ <element type>
		3628	template <typename Derived, typename Alloc>
		3629	Node *AbstractManglingParser<Derived, Alloc>::parseArrayType() {
		3630	if (!consumeIf('A'))
		3631	return nullptr;
		3632
		3633	Node *Dimension = nullptr;
		3634
		3635	if (std::isdigit(look())) {
		3636	Dimension = make<NameType>(parseNumber());
		3637	if (!Dimension)
		3638	return nullptr;
		3639	if (!consumeIf('_'))
		3640	return nullptr;
		3641	} else if (!consumeIf('_')) {
		3642	Node *DimExpr = getDerived().parseExpr();
		3643	if (DimExpr == nullptr)
		3644	return nullptr;
		3645	if (!consumeIf('_'))
		3646	return nullptr;
		3647	Dimension = DimExpr;
		3648	}
		3649
		3650	Node *Ty = getDerived().parseType();
		3651	if (Ty == nullptr)
		3652	return nullptr;
		3653	return make<ArrayType>(Ty, Dimension);
		3654	}
		3655
		3656	// <pointer-to-member-type> ::= M <class type> <member type>
		3657	template <typename Derived, typename Alloc>
		3658	Node *AbstractManglingParser<Derived, Alloc>::parsePointerToMemberType() {
		3659	if (!consumeIf('M'))
		3660	return nullptr;
		3661	Node *ClassType = getDerived().parseType();
		3662	if (ClassType == nullptr)
		3663	return nullptr;
		3664	Node *MemberType = getDerived().parseType();
		3665	if (MemberType == nullptr)
		3666	return nullptr;
		3667	return make<PointerToMemberType>(ClassType, MemberType);
		3668	}
		3669
		3670	// <class-enum-type> ::= <name> # non-dependent type name, dependent type name, or dependent typename-specifier
		3671	// ::= Ts <name> # dependent elaborated type specifier using 'struct' or 'class'
		3672	// ::= Tu <name> # dependent elaborated type specifier using 'union'
		3673	// ::= Te <name> # dependent elaborated type specifier using 'enum'
		3674	template <typename Derived, typename Alloc>
		3675	Node *AbstractManglingParser<Derived, Alloc>::parseClassEnumType() {
		3676	StringView ElabSpef;
		3677	if (consumeIf("Ts"))
		3678	ElabSpef = "struct";
		3679	else if (consumeIf("Tu"))
		3680	ElabSpef = "union";
		3681	else if (consumeIf("Te"))
		3682	ElabSpef = "enum";
		3683
		3684	Node *Name = getDerived().parseName();
		3685	if (Name == nullptr)
		3686	return nullptr;
		3687
		3688	if (!ElabSpef.empty())
		3689	return make<ElaboratedTypeSpefType>(ElabSpef, Name);
		3690
		3691	return Name;
		3692	}
		3693
		3694	// <qualified-type> ::= <qualifiers> <type>
		3695	// <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
		3696	// <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
		3697	template <typename Derived, typename Alloc>
		3698	Node *AbstractManglingParser<Derived, Alloc>::parseQualifiedType() {
		3699	if (consumeIf('U')) {
		3700	StringView Qual = parseBareSourceName();
		3701	if (Qual.empty())
		3702	return nullptr;
		3703
		3704	// extension ::= U <objc-name> <objc-type> # objc-type<identifier>
		3705	if (Qual.startsWith("objcproto")) {
		3706	StringView ProtoSourceName = Qual.dropFront(std::strlen("objcproto"));
		3707	StringView Proto;
		3708	{
		3709	ScopedOverride<const char *> SaveFirst(First, ProtoSourceName.begin()),
		3710	SaveLast(Last, ProtoSourceName.end());
		3711	Proto = parseBareSourceName();
		3712	}
		3713	if (Proto.empty())
		3714	return nullptr;
		3715	Node *Child = getDerived().parseQualifiedType();
		3716	if (Child == nullptr)
		3717	return nullptr;
		3718	return make<ObjCProtoName>(Child, Proto);
		3719	}
		3720
		3721	Node *TA = nullptr;
		3722	if (look() == 'I') {
		3723	TA = getDerived().parseTemplateArgs();
		3724	if (TA == nullptr)
		3725	return nullptr;
		3726	}
		3727
		3728	Node *Child = getDerived().parseQualifiedType();
		3729	if (Child == nullptr)
		3730	return nullptr;
		3731	return make<VendorExtQualType>(Child, Qual, TA);
		3732	}
		3733
		3734	Qualifiers Quals = parseCVQualifiers();
		3735	Node *Ty = getDerived().parseType();
		3736	if (Ty == nullptr)
		3737	return nullptr;
		3738	if (Quals != QualNone)
		3739	Ty = make<QualType>(Ty, Quals);
		3740	return Ty;
		3741	}
		3742
		3743	// <type> ::= <builtin-type>
		3744	// ::= <qualified-type>
		3745	// ::= <function-type>
		3746	// ::= <class-enum-type>
		3747	// ::= <array-type>
		3748	// ::= <pointer-to-member-type>
		3749	// ::= <template-param>
		3750	// ::= <template-template-param> <template-args>
		3751	// ::= <decltype>
		3752	// ::= P <type> # pointer
		3753	// ::= R <type> # l-value reference
		3754	// ::= O <type> # r-value reference (C++11)
		3755	// ::= C <type> # complex pair (C99)
		3756	// ::= G <type> # imaginary (C99)
		3757	// ::= <substitution> # See Compression below
		3758	// extension ::= U <objc-name> <objc-type> # objc-type<identifier>
		3759	// extension ::= <vector-type> # <vector-type> starts with Dv
		3760	//
		3761	// <objc-name> ::= <k0 number> objcproto <k1 number> <identifier> # k0 = 9 + <number of digits in k1> + k1
		3762	// <objc-type> ::= <source-name> # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
		3763	template <typename Derived, typename Alloc>
		3764	Node *AbstractManglingParser<Derived, Alloc>::parseType() {
		3765	Node *Result = nullptr;
		3766
		3767	switch (look()) {
		3768	// ::= <qualified-type>
		3769	case 'r':
		3770	case 'V':
		3771	case 'K': {
		3772	unsigned AfterQuals = 0;
		3773	if (look(AfterQuals) == 'r') ++AfterQuals;
		3774	if (look(AfterQuals) == 'V') ++AfterQuals;
		3775	if (look(AfterQuals) == 'K') ++AfterQuals;
		3776
		3777	if (look(AfterQuals) == 'F' \|\|
		3778	(look(AfterQuals) == 'D' &&
		3779	(look(AfterQuals + 1) == 'o' \|\| look(AfterQuals + 1) == 'O' \|\|
		3780	look(AfterQuals + 1) == 'w' \|\| look(AfterQuals + 1) == 'x'))) {
		3781	Result = getDerived().parseFunctionType();
		3782	break;
		3783	}
		3784	DEMANGLE_FALLTHROUGH;
		3785	}
		3786	case 'U': {
		3787	Result = getDerived().parseQualifiedType();
		3788	break;
		3789	}
		3790	// <builtin-type> ::= v # void
		3791	case 'v':
		3792	++First;
		3793	return make<NameType>("void");
		3794	// ::= w # wchar_t
		3795	case 'w':
		3796	++First;
		3797	return make<NameType>("wchar_t");
		3798	// ::= b # bool
		3799	case 'b':
		3800	++First;
		3801	return make<NameType>("bool");
		3802	// ::= c # char
		3803	case 'c':
		3804	++First;
		3805	return make<NameType>("char");
		3806	// ::= a # signed char
		3807	case 'a':
		3808	++First;
		3809	return make<NameType>("signed char");
		3810	// ::= h # unsigned char
		3811	case 'h':
		3812	++First;
		3813	return make<NameType>("unsigned char");
		3814	// ::= s # short
		3815	case 's':
		3816	++First;
		3817	return make<NameType>("short");
		3818	// ::= t # unsigned short
		3819	case 't':
		3820	++First;
		3821	return make<NameType>("unsigned short");
		3822	// ::= i # int
		3823	case 'i':
		3824	++First;
		3825	return make<NameType>("int");
		3826	// ::= j # unsigned int
		3827	case 'j':
		3828	++First;
		3829	return make<NameType>("unsigned int");
		3830	// ::= l # long
		3831	case 'l':
		3832	++First;
		3833	return make<NameType>("long");
		3834	// ::= m # unsigned long
		3835	case 'm':
		3836	++First;
		3837	return make<NameType>("unsigned long");
		3838	// ::= x # long long, __int64
		3839	case 'x':
		3840	++First;
		3841	return make<NameType>("long long");
		3842	// ::= y # unsigned long long, __int64
		3843	case 'y':
		3844	++First;
		3845	return make<NameType>("unsigned long long");
		3846	// ::= n # __int128
		3847	case 'n':
		3848	++First;
		3849	return make<NameType>("__int128");
		3850	// ::= o # unsigned __int128
		3851	case 'o':
		3852	++First;
		3853	return make<NameType>("unsigned __int128");
		3854	// ::= f # float
		3855	case 'f':
		3856	++First;
		3857	return make<NameType>("float");
		3858	// ::= d # double
		3859	case 'd':
		3860	++First;
		3861	return make<NameType>("double");
		3862	// ::= e # long double, __float80
		3863	case 'e':
		3864	++First;
		3865	return make<NameType>("long double");
		3866	// ::= g # __float128
		3867	case 'g':
		3868	++First;
		3869	return make<NameType>("__float128");
		3870	// ::= z # ellipsis
		3871	case 'z':
		3872	++First;
		3873	return make<NameType>("...");
		3874
		3875	// <builtin-type> ::= u <source-name> # vendor extended type
		3876	case 'u': {
		3877	++First;
		3878	StringView Res = parseBareSourceName();
		3879	if (Res.empty())
		3880	return nullptr;
		3881	// Typically, <builtin-type>s are not considered substitution candidates,
		3882	// but the exception to that exception is vendor extended types (Itanium C++
		3883	// ABI 5.9.1).
		3884	Result = make<NameType>(Res);
		3885	break;
		3886	}
		3887	case 'D':
		3888	switch (look(1)) {
		3889	// ::= Dd # IEEE 754r decimal floating point (64 bits)
		3890	case 'd':
		3891	First += 2;
		3892	return make<NameType>("decimal64");
		3893	// ::= De # IEEE 754r decimal floating point (128 bits)
		3894	case 'e':
		3895	First += 2;
		3896	return make<NameType>("decimal128");
		3897	// ::= Df # IEEE 754r decimal floating point (32 bits)
		3898	case 'f':
		3899	First += 2;
		3900	return make<NameType>("decimal32");
		3901	// ::= Dh # IEEE 754r half-precision floating point (16 bits)
		3902	case 'h':
		3903	First += 2;
		3904	return make<NameType>("half");
		3905	// ::= DF <number> _ # ISO/IEC TS 18661 binary floating point (N bits)
		3906	case 'F': {
		3907	First += 2;
		3908	Node *DimensionNumber = make<NameType>(parseNumber());
		3909	if (!DimensionNumber)
		3910	return nullptr;
		3911	if (!consumeIf('_'))
		3912	return nullptr;
		3913	return make<BinaryFPType>(DimensionNumber);
		3914	}
		3915	// ::= DB <number> _ # C23 signed _BitInt(N)
		3916	// ::= DB <instantiation-dependent expression> _ # C23 signed _BitInt(N)
		3917	// ::= DU <number> _ # C23 unsigned _BitInt(N)
		3918	// ::= DU <instantiation-dependent expression> _ # C23 unsigned _BitInt(N)
		3919	case 'B':
		3920	case 'U': {
		3921	bool Signed = look(1) == 'B';
		3922	First += 2;
		3923	Node *Size = std::isdigit(look()) ? make<NameType>(parseNumber())
		3924	: getDerived().parseExpr();
		3925	if (!Size)
		3926	return nullptr;
		3927	if (!consumeIf('_'))
		3928	return nullptr;
		3929	return make<BitIntType>(Size, Signed);
		3930	}
		3931	// ::= Di # char32_t
		3932	case 'i':
		3933	First += 2;
		3934	return make<NameType>("char32_t");
		3935	// ::= Ds # char16_t
		3936	case 's':
		3937	First += 2;
		3938	return make<NameType>("char16_t");
		3939	// ::= Du # char8_t (C++2a, not yet in the Itanium spec)
		3940	case 'u':
		3941	First += 2;
		3942	return make<NameType>("char8_t");
		3943	// ::= Da # auto (in dependent new-expressions)
		3944	case 'a':
		3945	First += 2;
		3946	return make<NameType>("auto");
		3947	// ::= Dc # decltype(auto)
		3948	case 'c':
		3949	First += 2;
		3950	return make<NameType>("decltype(auto)");
		3951	// ::= Dn # std::nullptr_t (i.e., decltype(nullptr))
		3952	case 'n':
		3953	First += 2;
		3954	return make<NameType>("std::nullptr_t");
		3955
		3956	// ::= <decltype>
		3957	case 't':
		3958	case 'T': {
		3959	Result = getDerived().parseDecltype();
		3960	break;
		3961	}
		3962	// extension ::= <vector-type> # <vector-type> starts with Dv
		3963	case 'v': {
		3964	Result = getDerived().parseVectorType();
		3965	break;
		3966	}
		3967	// ::= Dp <type> # pack expansion (C++0x)
		3968	case 'p': {
		3969	First += 2;
		3970	Node *Child = getDerived().parseType();
		3971	if (!Child)
		3972	return nullptr;
		3973	Result = make<ParameterPackExpansion>(Child);
		3974	break;
		3975	}
		3976	// Exception specifier on a function type.
		3977	case 'o':
		3978	case 'O':
		3979	case 'w':
		3980	// Transaction safe function type.
		3981	case 'x':
		3982	Result = getDerived().parseFunctionType();
		3983	break;
		3984	}
		3985	break;
		3986	// ::= <function-type>
		3987	case 'F': {
		3988	Result = getDerived().parseFunctionType();
		3989	break;
		3990	}
		3991	// ::= <array-type>
		3992	case 'A': {
		3993	Result = getDerived().parseArrayType();
		3994	break;
		3995	}
		3996	// ::= <pointer-to-member-type>
		3997	case 'M': {
		3998	Result = getDerived().parsePointerToMemberType();
		3999	break;
		4000	}
		4001	// ::= <template-param>
		4002	case 'T': {
		4003	// This could be an elaborate type specifier on a <class-enum-type>.
		4004	if (look(1) == 's' \|\| look(1) == 'u' \|\| look(1) == 'e') {
		4005	Result = getDerived().parseClassEnumType();
		4006	break;
		4007	}
		4008
		4009	Result = getDerived().parseTemplateParam();
		4010	if (Result == nullptr)
		4011	return nullptr;
		4012
		4013	// Result could be either of:
		4014	// <type> ::= <template-param>
		4015	// <type> ::= <template-template-param> <template-args>
		4016	//
		4017	// <template-template-param> ::= <template-param>
		4018	// ::= <substitution>
		4019	//
		4020	// If this is followed by some <template-args>, and we're permitted to
		4021	// parse them, take the second production.
		4022
		4023	if (TryToParseTemplateArgs && look() == 'I') {
		4024	Node *TA = getDerived().parseTemplateArgs();
		4025	if (TA == nullptr)
		4026	return nullptr;
		4027	Result = make<NameWithTemplateArgs>(Result, TA);
		4028	}
		4029	break;
		4030	}
		4031	// ::= P <type> # pointer
		4032	case 'P': {
		4033	++First;
		4034	Node *Ptr = getDerived().parseType();
		4035	if (Ptr == nullptr)
		4036	return nullptr;
		4037	Result = make<PointerType>(Ptr);
		4038	break;
		4039	}
		4040	// ::= R <type> # l-value reference
		4041	case 'R': {
		4042	++First;
		4043	Node *Ref = getDerived().parseType();
		4044	if (Ref == nullptr)
		4045	return nullptr;
		4046	Result = make<ReferenceType>(Ref, ReferenceKind::LValue);
		4047	break;
		4048	}
		4049	// ::= O <type> # r-value reference (C++11)
		4050	case 'O': {
		4051	++First;
		4052	Node *Ref = getDerived().parseType();
		4053	if (Ref == nullptr)
		4054	return nullptr;
		4055	Result = make<ReferenceType>(Ref, ReferenceKind::RValue);
		4056	break;
		4057	}
		4058	// ::= C <type> # complex pair (C99)
		4059	case 'C': {
		4060	++First;
		4061	Node *P = getDerived().parseType();
		4062	if (P == nullptr)
		4063	return nullptr;
		4064	Result = make<PostfixQualifiedType>(P, " complex");
		4065	break;
		4066	}
		4067	// ::= G <type> # imaginary (C99)
		4068	case 'G': {
		4069	++First;
		4070	Node *P = getDerived().parseType();
		4071	if (P == nullptr)
		4072	return P;
		4073	Result = make<PostfixQualifiedType>(P, " imaginary");
		4074	break;
		4075	}
		4076	// ::= <substitution> # See Compression below
		4077	case 'S': {
		4078	if (look(1) != 't') {
		4079	bool IsSubst = false;
		4080	Result = getDerived().parseUnscopedName(nullptr, &IsSubst);
		4081	if (!Result)
		4082	return nullptr;
		4083
		4084	// Sub could be either of:
		4085	// <type> ::= <substitution>
		4086	// <type> ::= <template-template-param> <template-args>
		4087	//
		4088	// <template-template-param> ::= <template-param>
		4089	// ::= <substitution>
		4090	//
		4091	// If this is followed by some <template-args>, and we're permitted to
		4092	// parse them, take the second production.
		4093
		4094	if (look() == 'I' && (!IsSubst \|\| TryToParseTemplateArgs)) {
		4095	if (!IsSubst)
		4096	Subs.push_back(Result);
		4097	Node *TA = getDerived().parseTemplateArgs();
		4098	if (TA == nullptr)
		4099	return nullptr;
		4100	Result = make<NameWithTemplateArgs>(Result, TA);
		4101	} else if (IsSubst) {
		4102	// If all we parsed was a substitution, don't re-insert into the
		4103	// substitution table.
		4104	return Result;
		4105	}
		4106	break;
		4107	}
		4108	DEMANGLE_FALLTHROUGH;
		4109	}
		4110	// ::= <class-enum-type>
		4111	default: {
		4112	Result = getDerived().parseClassEnumType();
		4113	break;
		4114	}
		4115	}
		4116
		4117	// If we parsed a type, insert it into the substitution table. Note that all
		4118	// <builtin-type>s and <substitution>s have already bailed out, because they
		4119	// don't get substitutions.
		4120	if (Result != nullptr)
		4121	Subs.push_back(Result);
		4122	return Result;
		4123	}
		4124
		4125	template <typename Derived, typename Alloc>
		4126	Node *AbstractManglingParser<Derived, Alloc>::parsePrefixExpr(StringView Kind,
		4127	Node::Prec Prec) {
		4128	Node *E = getDerived().parseExpr();
		4129	if (E == nullptr)
		4130	return nullptr;
		4131	return make<PrefixExpr>(Kind, E, Prec);
		4132	}
		4133
		4134	template <typename Derived, typename Alloc>
		4135	Node *AbstractManglingParser<Derived, Alloc>::parseBinaryExpr(StringView Kind,
		4136	Node::Prec Prec) {
		4137	Node *LHS = getDerived().parseExpr();
		4138	if (LHS == nullptr)
		4139	return nullptr;
		4140	Node *RHS = getDerived().parseExpr();
		4141	if (RHS == nullptr)
		4142	return nullptr;
		4143	return make<BinaryExpr>(LHS, Kind, RHS, Prec);
		4144	}
		4145
		4146	template <typename Derived, typename Alloc>
		4147	Node *
		4148	AbstractManglingParser<Derived, Alloc>::parseIntegerLiteral(StringView Lit) {
		4149	StringView Tmp = parseNumber(true);
		4150	if (!Tmp.empty() && consumeIf('E'))
		4151	return make<IntegerLiteral>(Lit, Tmp);
		4152	return nullptr;
		4153	}
		4154
		4155	// <CV-Qualifiers> ::= [r] [V] [K]
		4156	template <typename Alloc, typename Derived>
		4157	Qualifiers AbstractManglingParser<Alloc, Derived>::parseCVQualifiers() {
		4158	Qualifiers CVR = QualNone;
		4159	if (consumeIf('r'))
		4160	CVR \|= QualRestrict;
		4161	if (consumeIf('V'))
		4162	CVR \|= QualVolatile;
		4163	if (consumeIf('K'))
		4164	CVR \|= QualConst;
		4165	return CVR;
		4166	}
		4167
		4168	// <function-param> ::= fp <top-level CV-Qualifiers> _ # L == 0, first parameter
		4169	// ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _ # L == 0, second and later parameters
		4170	// ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> _ # L > 0, first parameter
		4171	// ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> <parameter-2 non-negative number> _ # L > 0, second and later parameters
		4172	// ::= fpT # 'this' expression (not part of standard?)
		4173	template <typename Derived, typename Alloc>
		4174	Node *AbstractManglingParser<Derived, Alloc>::parseFunctionParam() {
		4175	if (consumeIf("fpT"))
		4176	return make<NameType>("this");
		4177	if (consumeIf("fp")) {
		4178	parseCVQualifiers();
		4179	StringView Num = parseNumber();
		4180	if (!consumeIf('_'))
		4181	return nullptr;
		4182	return make<FunctionParam>(Num);
		4183	}
		4184	if (consumeIf("fL")) {
		4185	if (parseNumber().empty())
		4186	return nullptr;
		4187	if (!consumeIf('p'))
		4188	return nullptr;
		4189	parseCVQualifiers();
		4190	StringView Num = parseNumber();
		4191	if (!consumeIf('_'))
		4192	return nullptr;
		4193	return make<FunctionParam>(Num);
		4194	}
		4195	return nullptr;
		4196	}
		4197
		4198	// cv <type> <expression> # conversion with one argument
		4199	// cv <type> _ <expression>* E # conversion with a different number of arguments
		4200	template <typename Derived, typename Alloc>
		4201	Node *AbstractManglingParser<Derived, Alloc>::parseConversionExpr() {
		4202	if (!consumeIf("cv"))
		4203	return nullptr;
		4204	Node *Ty;
		4205	{
		4206	ScopedOverride<bool> SaveTemp(TryToParseTemplateArgs, false);
		4207	Ty = getDerived().parseType();
		4208	}
		4209
		4210	if (Ty == nullptr)
		4211	return nullptr;
		4212
		4213	if (consumeIf('_')) {
		4214	size_t ExprsBegin = Names.size();
		4215	while (!consumeIf('E')) {
		4216	Node *E = getDerived().parseExpr();
		4217	if (E == nullptr)
		4218	return E;
		4219	Names.push_back(E);
		4220	}
		4221	NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
		4222	return make<ConversionExpr>(Ty, Exprs);
		4223	}
		4224
		4225	Node *E[1] = {getDerived().parseExpr()};
		4226	if (E[0] == nullptr)
		4227	return nullptr;
		4228	return make<ConversionExpr>(Ty, makeNodeArray(E, E + 1));
		4229	}
		4230
		4231	// <expr-primary> ::= L <type> <value number> E # integer literal
		4232	// ::= L <type> <value float> E # floating literal
		4233	// ::= L <string type> E # string literal
		4234	// ::= L <nullptr type> E # nullptr literal (i.e., "LDnE")
		4235	// ::= L <lambda type> E # lambda expression
		4236	// FIXME: ::= L <type> <real-part float> _ <imag-part float> E # complex floating point literal (C 2000)
		4237	// ::= L <mangled-name> E # external name
		4238	template <typename Derived, typename Alloc>
		4239	Node *AbstractManglingParser<Derived, Alloc>::parseExprPrimary() {
		4240	if (!consumeIf('L'))
		4241	return nullptr;
		4242	switch (look()) {
		4243	case 'w':
		4244	++First;
		4245	return getDerived().parseIntegerLiteral("wchar_t");
		4246	case 'b':
		4247	if (consumeIf("b0E"))
		4248	return make<BoolExpr>(0);
		4249	if (consumeIf("b1E"))
		4250	return make<BoolExpr>(1);
		4251	return nullptr;
		4252	case 'c':
		4253	++First;
		4254	return getDerived().parseIntegerLiteral("char");
		4255	case 'a':
		4256	++First;
		4257	return getDerived().parseIntegerLiteral("signed char");
		4258	case 'h':
		4259	++First;
		4260	return getDerived().parseIntegerLiteral("unsigned char");
		4261	case 's':
		4262	++First;
		4263	return getDerived().parseIntegerLiteral("short");
		4264	case 't':
		4265	++First;
		4266	return getDerived().parseIntegerLiteral("unsigned short");
		4267	case 'i':
		4268	++First;
		4269	return getDerived().parseIntegerLiteral("");
		4270	case 'j':
		4271	++First;
		4272	return getDerived().parseIntegerLiteral("u");
		4273	case 'l':
		4274	++First;
		4275	return getDerived().parseIntegerLiteral("l");
		4276	case 'm':
		4277	++First;
		4278	return getDerived().parseIntegerLiteral("ul");
		4279	case 'x':
		4280	++First;
		4281	return getDerived().parseIntegerLiteral("ll");
		4282	case 'y':
		4283	++First;
		4284	return getDerived().parseIntegerLiteral("ull");
		4285	case 'n':
		4286	++First;
		4287	return getDerived().parseIntegerLiteral("__int128");
		4288	case 'o':
		4289	++First;
		4290	return getDerived().parseIntegerLiteral("unsigned __int128");
		4291	case 'f':
		4292	++First;
		4293	return getDerived().template parseFloatingLiteral<float>();
		4294	case 'd':
		4295	++First;
		4296	return getDerived().template parseFloatingLiteral<double>();
		4297	case 'e':
		4298	++First;
		4299	#if defined(__powerpc__) \|\| defined(__s390__)
		4300	// Handle cases where long doubles encoded with e have the same size
		4301	// and representation as doubles.
		4302	return getDerived().template parseFloatingLiteral<double>();
		4303	#else
		4304	return getDerived().template parseFloatingLiteral<long double>();
		4305	#endif
		4306	case '_':
		4307	if (consumeIf("_Z")) {
		4308	Node *R = getDerived().parseEncoding();
		4309	if (R != nullptr && consumeIf('E'))
		4310	return R;
		4311	}
		4312	return nullptr;
		4313	case 'A': {
		4314	Node *T = getDerived().parseType();
		4315	if (T == nullptr)
		4316	return nullptr;
		4317	// FIXME: We need to include the string contents in the mangling.
		4318	if (consumeIf('E'))
		4319	return make<StringLiteral>(T);
		4320	return nullptr;
		4321	}
		4322	case 'D':
		4323	if (consumeIf("Dn") && (consumeIf('0'), consumeIf('E')))
		4324	return make<NameType>("nullptr");
		4325	return nullptr;
		4326	case 'T':
		4327	// Invalid mangled name per
		4328	// http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
		4329	return nullptr;
		4330	case 'U': {
		4331	// FIXME: Should we support LUb... for block literals?
		4332	if (look(1) != 'l')
		4333	return nullptr;
		4334	Node *T = parseUnnamedTypeName(nullptr);
		4335	if (!T \|\| !consumeIf('E'))
		4336	return nullptr;
		4337	return make<LambdaExpr>(T);
		4338	}
		4339	default: {
		4340	// might be named type
		4341	Node *T = getDerived().parseType();
		4342	if (T == nullptr)
		4343	return nullptr;
		4344	StringView N = parseNumber(/AllowNegative=/true);
		4345	if (N.empty())
		4346	return nullptr;
		4347	if (!consumeIf('E'))
		4348	return nullptr;
		4349	return make<EnumLiteral>(T, N);
		4350	}
		4351	}
		4352	}
		4353
		4354	// <braced-expression> ::= <expression>
		4355	// ::= di <field source-name> <braced-expression> # .name = expr
		4356	// ::= dx <index expression> <braced-expression> # [expr] = expr
		4357	// ::= dX <range begin expression> <range end expression> <braced-expression>
		4358	template <typename Derived, typename Alloc>
		4359	Node *AbstractManglingParser<Derived, Alloc>::parseBracedExpr() {
		4360	if (look() == 'd') {
		4361	switch (look(1)) {
		4362	case 'i': {
		4363	First += 2;
		4364	Node Field = getDerived().parseSourceName(/NameState=*/nullptr);
		4365	if (Field == nullptr)
		4366	return nullptr;
		4367	Node *Init = getDerived().parseBracedExpr();
		4368	if (Init == nullptr)
		4369	return nullptr;
		4370	return make<BracedExpr>(Field, Init, /isArray=/false);
		4371	}
		4372	case 'x': {
		4373	First += 2;
		4374	Node *Index = getDerived().parseExpr();
		4375	if (Index == nullptr)
		4376	return nullptr;
		4377	Node *Init = getDerived().parseBracedExpr();
		4378	if (Init == nullptr)
		4379	return nullptr;
		4380	return make<BracedExpr>(Index, Init, /isArray=/true);
		4381	}
		4382	case 'X': {
		4383	First += 2;
		4384	Node *RangeBegin = getDerived().parseExpr();
		4385	if (RangeBegin == nullptr)
		4386	return nullptr;
		4387	Node *RangeEnd = getDerived().parseExpr();
		4388	if (RangeEnd == nullptr)
		4389	return nullptr;
		4390	Node *Init = getDerived().parseBracedExpr();
		4391	if (Init == nullptr)
		4392	return nullptr;
		4393	return make<BracedRangeExpr>(RangeBegin, RangeEnd, Init);
		4394	}
		4395	}
		4396	}
		4397	return getDerived().parseExpr();
		4398	}
		4399
		4400	// (not yet in the spec)
		4401	// <fold-expr> ::= fL <binary-operator-name> <expression> <expression>
		4402	// ::= fR <binary-operator-name> <expression> <expression>
		4403	// ::= fl <binary-operator-name> <expression>
		4404	// ::= fr <binary-operator-name> <expression>
		4405	template <typename Derived, typename Alloc>
		4406	Node *AbstractManglingParser<Derived, Alloc>::parseFoldExpr() {
		4407	if (!consumeIf('f'))
		4408	return nullptr;
		4409
		4410	bool IsLeftFold = false, HasInitializer = false;
		4411	switch (look()) {
		4412	default:
		4413	return nullptr;
		4414	case 'L':
		4415	IsLeftFold = true;
		4416	HasInitializer = true;
		4417	break;
		4418	case 'R':
		4419	HasInitializer = true;
		4420	break;
		4421	case 'l':
		4422	IsLeftFold = true;
		4423	break;
		4424	case 'r':
		4425	break;
		4426	}
		4427	++First;
		4428
		4429	const auto *Op = parseOperatorEncoding();
		4430	if (!Op)
		4431	return nullptr;
		4432	if (!(Op->getKind() == OperatorInfo::Binary
		4433	\|\| (Op->getKind() == OperatorInfo::Member
		4434	&& Op->getName().back() == '*')))
		4435	return nullptr;
		4436
		4437	Node *Pack = getDerived().parseExpr();
		4438	if (Pack == nullptr)
		4439	return nullptr;
		4440
		4441	Node *Init = nullptr;
		4442	if (HasInitializer) {
		4443	Init = getDerived().parseExpr();
		4444	if (Init == nullptr)
		4445	return nullptr;
		4446	}
		4447
		4448	if (IsLeftFold && Init)
		4449	std::swap(Pack, Init);
		4450
		4451	return make<FoldExpr>(IsLeftFold, Op->getSymbol(), Pack, Init);
		4452	}
		4453
		4454	// <expression> ::= mc <parameter type> <expr> [<offset number>] E
		4455	//
		4456	// Not yet in the spec: https://github.com/itanium-cxx-abi/cxx-abi/issues/47
		4457	template <typename Derived, typename Alloc>
		4458	Node *
		4459	AbstractManglingParser<Derived, Alloc>::parsePointerToMemberConversionExpr(
		4460	Node::Prec Prec) {
		4461	Node *Ty = getDerived().parseType();
		4462	if (!Ty)
		4463	return nullptr;
		4464	Node *Expr = getDerived().parseExpr();
		4465	if (!Expr)
		4466	return nullptr;
		4467	StringView Offset = getDerived().parseNumber(true);
		4468	if (!consumeIf('E'))
		4469	return nullptr;
		4470	return make<PointerToMemberConversionExpr>(Ty, Expr, Offset, Prec);
		4471	}
		4472
		4473	// <expression> ::= so <referent type> <expr> [<offset number>] <union-selector>* [p] E
		4474	// <union-selector> ::= _ [<number>]
		4475	//
		4476	// Not yet in the spec: https://github.com/itanium-cxx-abi/cxx-abi/issues/47
		4477	template <typename Derived, typename Alloc>
		4478	Node *AbstractManglingParser<Derived, Alloc>::parseSubobjectExpr() {
		4479	Node *Ty = getDerived().parseType();
		4480	if (!Ty)
		4481	return nullptr;
		4482	Node *Expr = getDerived().parseExpr();
		4483	if (!Expr)
		4484	return nullptr;
		4485	StringView Offset = getDerived().parseNumber(true);
		4486	size_t SelectorsBegin = Names.size();
		4487	while (consumeIf('_')) {
		4488	Node *Selector = make<NameType>(parseNumber());
		4489	if (!Selector)
		4490	return nullptr;
		4491	Names.push_back(Selector);
		4492	}
		4493	bool OnePastTheEnd = consumeIf('p');
		4494	if (!consumeIf('E'))
		4495	return nullptr;
		4496	return make<SubobjectExpr>(
		4497	Ty, Expr, Offset, popTrailingNodeArray(SelectorsBegin), OnePastTheEnd);
		4498	}
		4499
		4500	// <expression> ::= <unary operator-name> <expression>
		4501	// ::= <binary operator-name> <expression> <expression>
		4502	// ::= <ternary operator-name> <expression> <expression> <expression>
		4503	// ::= cl <expression>+ E # call
		4504	// ::= cv <type> <expression> # conversion with one argument
		4505	// ::= cv <type> _ <expression>* E # conversion with a different number of arguments
		4506	// ::= [gs] nw <expression>* _ <type> E # new (expr-list) type
		4507	// ::= [gs] nw <expression>* _ <type> <initializer> # new (expr-list) type (init)
		4508	// ::= [gs] na <expression>* _ <type> E # new[] (expr-list) type
		4509	// ::= [gs] na <expression>* _ <type> <initializer> # new[] (expr-list) type (init)
		4510	// ::= [gs] dl <expression> # delete expression
		4511	// ::= [gs] da <expression> # delete[] expression
		4512	// ::= pp_ <expression> # prefix ++
		4513	// ::= mm_ <expression> # prefix --
		4514	// ::= ti <type> # typeid (type)
		4515	// ::= te <expression> # typeid (expression)
		4516	// ::= dc <type> <expression> # dynamic_cast<type> (expression)
		4517	// ::= sc <type> <expression> # static_cast<type> (expression)
		4518	// ::= cc <type> <expression> # const_cast<type> (expression)
		4519	// ::= rc <type> <expression> # reinterpret_cast<type> (expression)
		4520	// ::= st <type> # sizeof (a type)
		4521	// ::= sz <expression> # sizeof (an expression)
		4522	// ::= at <type> # alignof (a type)
		4523	// ::= az <expression> # alignof (an expression)
		4524	// ::= nx <expression> # noexcept (expression)
		4525	// ::= <template-param>
		4526	// ::= <function-param>
		4527	// ::= dt <expression> <unresolved-name> # expr.name
		4528	// ::= pt <expression> <unresolved-name> # expr->name
		4529	// ::= ds <expression> <expression> # expr.*expr
		4530	// ::= sZ <template-param> # size of a parameter pack
		4531	// ::= sZ <function-param> # size of a function parameter pack
		4532	// ::= sP <template-arg>* E # sizeof...(T), size of a captured template parameter pack from an alias template
		4533	// ::= sp <expression> # pack expansion
		4534	// ::= tw <expression> # throw expression
		4535	// ::= tr # throw with no operand (rethrow)
		4536	// ::= <unresolved-name> # f(p), N::f(p), ::f(p),
		4537	// # freestanding dependent name (e.g., T::x),
		4538	// # objectless nonstatic member reference
		4539	// ::= fL <binary-operator-name> <expression> <expression>
		4540	// ::= fR <binary-operator-name> <expression> <expression>
		4541	// ::= fl <binary-operator-name> <expression>
		4542	// ::= fr <binary-operator-name> <expression>
		4543	// ::= <expr-primary>
		4544	template <typename Derived, typename Alloc>
		4545	Node *AbstractManglingParser<Derived, Alloc>::parseExpr() {
		4546	bool Global = consumeIf("gs");
		4547
		4548	const auto *Op = parseOperatorEncoding();
		4549	if (Op) {
		4550	auto Sym = Op->getSymbol();
		4551	switch (Op->getKind()) {
		4552	case OperatorInfo::Binary:
		4553	// Binary operator: lhs @ rhs
		4554	return getDerived().parseBinaryExpr(Sym, Op->getPrecedence());
		4555	case OperatorInfo::Prefix:
		4556	// Prefix unary operator: @ expr
		4557	return getDerived().parsePrefixExpr(Sym, Op->getPrecedence());
		4558	case OperatorInfo::Postfix: {
		4559	// Postfix unary operator: expr @
		4560	if (consumeIf('_'))
		4561	return getDerived().parsePrefixExpr(Sym, Op->getPrecedence());
		4562	Node *Ex = getDerived().parseExpr();
		4563	if (Ex == nullptr)
		4564	return nullptr;
		4565	return make<PostfixExpr>(Ex, Sym, Op->getPrecedence());
		4566	}
		4567	case OperatorInfo::Array: {
		4568	// Array Index: lhs [ rhs ]
		4569	Node *Base = getDerived().parseExpr();
		4570	if (Base == nullptr)
		4571	return nullptr;
		4572	Node *Index = getDerived().parseExpr();
		4573	if (Index == nullptr)
		4574	return nullptr;
		4575	return make<ArraySubscriptExpr>(Base, Index, Op->getPrecedence());
		4576	}
		4577	case OperatorInfo::Member: {
		4578	// Member access lhs @ rhs
		4579	Node *LHS = getDerived().parseExpr();
		4580	if (LHS == nullptr)
		4581	return nullptr;
		4582	Node *RHS = getDerived().parseExpr();
		4583	if (RHS == nullptr)
		4584	return nullptr;
		4585	return make<MemberExpr>(LHS, Sym, RHS, Op->getPrecedence());
		4586	}
		4587	case OperatorInfo::New: {
		4588	// New
		4589	// # new (expr-list) type [(init)]
		4590	// [gs] nw <expression>* _ <type> [pi <expression>*] E
		4591	// # new[] (expr-list) type [(init)]
		4592	// [gs] na <expression>* _ <type> [pi <expression>*] E
		4593	size_t Exprs = Names.size();
		4594	while (!consumeIf('_')) {
		4595	Node *Ex = getDerived().parseExpr();
		4596	if (Ex == nullptr)
		4597	return nullptr;
		4598	Names.push_back(Ex);
		4599	}
		4600	NodeArray ExprList = popTrailingNodeArray(Exprs);
		4601	Node *Ty = getDerived().parseType();
		4602	if (Ty == nullptr)
		4603	return nullptr;
		4604	bool HaveInits = consumeIf("pi");
		4605	size_t InitsBegin = Names.size();
		4606	while (!consumeIf('E')) {
		4607	if (!HaveInits)
		4608	return nullptr;
		4609	Node *Init = getDerived().parseExpr();
		4610	if (Init == nullptr)
		4611	return Init;
		4612	Names.push_back(Init);
		4613	}
		4614	NodeArray Inits = popTrailingNodeArray(InitsBegin);
		4615	return make<NewExpr>(ExprList, Ty, Inits, Global,
		4616	/IsArray=/Op->getFlag(), Op->getPrecedence());
		4617	}
		4618	case OperatorInfo::Del: {
		4619	// Delete
		4620	Node *Ex = getDerived().parseExpr();
		4621	if (Ex == nullptr)
		4622	return nullptr;
		4623	return make<DeleteExpr>(Ex, Global, /IsArray=/Op->getFlag(),
		4624	Op->getPrecedence());
		4625	}
		4626	case OperatorInfo::Call: {
		4627	// Function Call
		4628	Node *Callee = getDerived().parseExpr();
		4629	if (Callee == nullptr)
		4630	return nullptr;
		4631	size_t ExprsBegin = Names.size();
		4632	while (!consumeIf('E')) {
		4633	Node *E = getDerived().parseExpr();
		4634	if (E == nullptr)
		4635	return nullptr;
		4636	Names.push_back(E);
		4637	}
		4638	return make<CallExpr>(Callee, popTrailingNodeArray(ExprsBegin),
		4639	Op->getPrecedence());
		4640	}
		4641	case OperatorInfo::CCast: {
		4642	// C Cast: (type)expr
		4643	Node *Ty;
		4644	{
		4645	ScopedOverride<bool> SaveTemp(TryToParseTemplateArgs, false);
		4646	Ty = getDerived().parseType();
		4647	}
		4648	if (Ty == nullptr)
		4649	return nullptr;
		4650
		4651	size_t ExprsBegin = Names.size();
		4652	bool IsMany = consumeIf('_');
		4653	while (!consumeIf('E')) {
		4654	Node *E = getDerived().parseExpr();
		4655	if (E == nullptr)
		4656	return E;
		4657	Names.push_back(E);
		4658	if (!IsMany)
		4659	break;
		4660	}
		4661	NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
		4662	if (!IsMany && Exprs.size() != 1)
		4663	return nullptr;
		4664	return make<ConversionExpr>(Ty, Exprs, Op->getPrecedence());
		4665	}
		4666	case OperatorInfo::Conditional: {
		4667	// Conditional operator: expr ? expr : expr
		4668	Node *Cond = getDerived().parseExpr();
		4669	if (Cond == nullptr)
		4670	return nullptr;
		4671	Node *LHS = getDerived().parseExpr();
		4672	if (LHS == nullptr)
		4673	return nullptr;
		4674	Node *RHS = getDerived().parseExpr();
		4675	if (RHS == nullptr)
		4676	return nullptr;
		4677	return make<ConditionalExpr>(Cond, LHS, RHS, Op->getPrecedence());
		4678	}
		4679	case OperatorInfo::NamedCast: {
		4680	// Named cast operation, @<type>(expr)
		4681	Node *Ty = getDerived().parseType();
		4682	if (Ty == nullptr)
		4683	return nullptr;
		4684	Node *Ex = getDerived().parseExpr();
		4685	if (Ex == nullptr)
		4686	return nullptr;
		4687	return make<CastExpr>(Sym, Ty, Ex, Op->getPrecedence());
		4688	}
		4689	case OperatorInfo::OfIdOp: {
		4690	// [sizeof/alignof/typeid] ( <type>\|<expr> )
		4691	Node *Arg =
		4692	Op->getFlag() ? getDerived().parseType() : getDerived().parseExpr();
		4693	if (!Arg)
		4694	return nullptr;
		4695	return make<EnclosingExpr>(Sym, Arg, Op->getPrecedence());
		4696	}
		4697	case OperatorInfo::NameOnly: {
		4698	// Not valid as an expression operand.
		4699	return nullptr;
		4700	}
		4701	}
		4702	DEMANGLE_UNREACHABLE;
		4703	}
		4704
		4705	if (numLeft() < 2)
		4706	return nullptr;
		4707
		4708	if (look() == 'L')
		4709	return getDerived().parseExprPrimary();
		4710	if (look() == 'T')
		4711	return getDerived().parseTemplateParam();
		4712	if (look() == 'f') {
		4713	// Disambiguate a fold expression from a <function-param>.
		4714	if (look(1) == 'p' \|\| (look(1) == 'L' && std::isdigit(look(2))))
		4715	return getDerived().parseFunctionParam();
		4716	return getDerived().parseFoldExpr();
		4717	}
		4718	if (consumeIf("il")) {
		4719	size_t InitsBegin = Names.size();
		4720	while (!consumeIf('E')) {
		4721	Node *E = getDerived().parseBracedExpr();
		4722	if (E == nullptr)
		4723	return nullptr;
		4724	Names.push_back(E);
		4725	}
		4726	return make<InitListExpr>(nullptr, popTrailingNodeArray(InitsBegin));
		4727	}
		4728	if (consumeIf("mc"))
		4729	return parsePointerToMemberConversionExpr(Node::Prec::Unary);
		4730	if (consumeIf("nx")) {
		4731	Node *Ex = getDerived().parseExpr();
		4732	if (Ex == nullptr)
		4733	return Ex;
		4734	return make<EnclosingExpr>("noexcept ", Ex, Node::Prec::Unary);
		4735	}
		4736	if (consumeIf("so"))
		4737	return parseSubobjectExpr();
		4738	if (consumeIf("sp")) {
		4739	Node *Child = getDerived().parseExpr();
		4740	if (Child == nullptr)
		4741	return nullptr;
		4742	return make<ParameterPackExpansion>(Child);
		4743	}
		4744	if (consumeIf("sZ")) {
		4745	if (look() == 'T') {
		4746	Node *R = getDerived().parseTemplateParam();
		4747	if (R == nullptr)
		4748	return nullptr;
		4749	return make<SizeofParamPackExpr>(R);
		4750	}
		4751	Node *FP = getDerived().parseFunctionParam();
		4752	if (FP == nullptr)
		4753	return nullptr;
		4754	return make<EnclosingExpr>("sizeof... ", FP);
		4755	}
		4756	if (consumeIf("sP")) {
		4757	size_t ArgsBegin = Names.size();
		4758	while (!consumeIf('E')) {
		4759	Node *Arg = getDerived().parseTemplateArg();
		4760	if (Arg == nullptr)
		4761	return nullptr;
		4762	Names.push_back(Arg);
		4763	}
		4764	auto *Pack = make<NodeArrayNode>(popTrailingNodeArray(ArgsBegin));
		4765	if (!Pack)
		4766	return nullptr;
		4767	return make<EnclosingExpr>("sizeof... ", Pack);
		4768	}
		4769	if (consumeIf("tl")) {
		4770	Node *Ty = getDerived().parseType();
		4771	if (Ty == nullptr)
		4772	return nullptr;
		4773	size_t InitsBegin = Names.size();
		4774	while (!consumeIf('E')) {
		4775	Node *E = getDerived().parseBracedExpr();
		4776	if (E == nullptr)
		4777	return nullptr;
		4778	Names.push_back(E);
		4779	}
		4780	return make<InitListExpr>(Ty, popTrailingNodeArray(InitsBegin));
		4781	}
		4782	if (consumeIf("tr"))
		4783	return make<NameType>("throw");
		4784	if (consumeIf("tw")) {
		4785	Node *Ex = getDerived().parseExpr();
		4786	if (Ex == nullptr)
		4787	return nullptr;
		4788	return make<ThrowExpr>(Ex);
		4789	}
		4790	if (consumeIf('u')) {
		4791	Node Name = getDerived().parseSourceName(/NameState=*/nullptr);
		4792	if (!Name)
		4793	return nullptr;
		4794	// Special case legacy __uuidof mangling. The 't' and 'z' appear where the
		4795	// standard encoding expects a <template-arg>, and would be otherwise be
		4796	// interpreted as <type> node 'short' or 'ellipsis'. However, neither
		4797	// __uuidof(short) nor __uuidof(...) can actually appear, so there is no
		4798	// actual conflict here.
		4799	bool IsUUID = false;
		4800	Node *UUID = nullptr;
		4801	if (Name->getBaseName() == "__uuidof") {
		4802	if (consumeIf('t')) {
		4803	UUID = getDerived().parseType();
		4804	IsUUID = true;
		4805	} else if (consumeIf('z')) {
		4806	UUID = getDerived().parseExpr();
		4807	IsUUID = true;
		4808	}
		4809	}
		4810	size_t ExprsBegin = Names.size();
		4811	if (IsUUID) {
		4812	if (UUID == nullptr)
		4813	return nullptr;
		4814	Names.push_back(UUID);
		4815	} else {
		4816	while (!consumeIf('E')) {
		4817	Node *E = getDerived().parseTemplateArg();
		4818	if (E == nullptr)
		4819	return E;
		4820	Names.push_back(E);
		4821	}
		4822	}
		4823	return make<CallExpr>(Name, popTrailingNodeArray(ExprsBegin),
		4824	Node::Prec::Postfix);
		4825	}
		4826
		4827	// Only unresolved names remain.
		4828	return getDerived().parseUnresolvedName(Global);
		4829	}
		4830
		4831	// <call-offset> ::= h <nv-offset> _
		4832	// ::= v <v-offset> _
		4833	//
		4834	// <nv-offset> ::= <offset number>
		4835	// # non-virtual base override
		4836	//
		4837	// <v-offset> ::= <offset number> _ <virtual offset number>
		4838	// # virtual base override, with vcall offset
		4839	template <typename Alloc, typename Derived>
		4840	bool AbstractManglingParser<Alloc, Derived>::parseCallOffset() {
		4841	// Just scan through the call offset, we never add this information into the
		4842	// output.
		4843	if (consumeIf('h'))
		4844	return parseNumber(true).empty() \|\| !consumeIf('_');
		4845	if (consumeIf('v'))
		4846	return parseNumber(true).empty() \|\| !consumeIf('_') \|\|
		4847	parseNumber(true).empty() \|\| !consumeIf('_');
		4848	return true;
		4849	}
		4850
		4851	// <special-name> ::= TV <type> # virtual table
		4852	// ::= TT <type> # VTT structure (construction vtable index)
		4853	// ::= TI <type> # typeinfo structure
		4854	// ::= TS <type> # typeinfo name (null-terminated byte string)
		4855	// ::= Tc <call-offset> <call-offset> <base encoding>
		4856	// # base is the nominal target function of thunk
		4857	// # first call-offset is 'this' adjustment
		4858	// # second call-offset is result adjustment
		4859	// ::= T <call-offset> <base encoding>
		4860	// # base is the nominal target function of thunk
		4861	// # Guard variable for one-time initialization
		4862	// ::= GV <object name>
		4863	// # No <type>
		4864	// ::= TW <object name> # Thread-local wrapper
		4865	// ::= TH <object name> # Thread-local initialization
		4866	// ::= GR <object name> _ # First temporary
		4867	// ::= GR <object name> <seq-id> _ # Subsequent temporaries
		4868	// # construction vtable for second-in-first
		4869	// extension ::= TC <first type> <number> _ <second type>
		4870	// extension ::= GR <object name> # reference temporary for object
		4871	// extension ::= GI <module name> # module global initializer
		4872	template <typename Derived, typename Alloc>
		4873	Node *AbstractManglingParser<Derived, Alloc>::parseSpecialName() {
		4874	switch (look()) {
		4875	case 'T':
		4876	switch (look(1)) {
		4877	// TA <template-arg> # template parameter object
		4878	//
		4879	// Not yet in the spec: https://github.com/itanium-cxx-abi/cxx-abi/issues/63
		4880	case 'A': {
		4881	First += 2;
		4882	Node *Arg = getDerived().parseTemplateArg();
		4883	if (Arg == nullptr)
		4884	return nullptr;
		4885	return make<SpecialName>("template parameter object for ", Arg);
		4886	}
		4887	// TV <type> # virtual table
		4888	case 'V': {
		4889	First += 2;
		4890	Node *Ty = getDerived().parseType();
		4891	if (Ty == nullptr)
		4892	return nullptr;
		4893	return make<SpecialName>("vtable for ", Ty);
		4894	}
		4895	// TT <type> # VTT structure (construction vtable index)
		4896	case 'T': {
		4897	First += 2;
		4898	Node *Ty = getDerived().parseType();
		4899	if (Ty == nullptr)
		4900	return nullptr;
		4901	return make<SpecialName>("VTT for ", Ty);
		4902	}
		4903	// TI <type> # typeinfo structure
		4904	case 'I': {
		4905	First += 2;
		4906	Node *Ty = getDerived().parseType();
		4907	if (Ty == nullptr)
		4908	return nullptr;
		4909	return make<SpecialName>("typeinfo for ", Ty);
		4910	}
		4911	// TS <type> # typeinfo name (null-terminated byte string)
		4912	case 'S': {
		4913	First += 2;
		4914	Node *Ty = getDerived().parseType();
		4915	if (Ty == nullptr)
		4916	return nullptr;
		4917	return make<SpecialName>("typeinfo name for ", Ty);
		4918	}
		4919	// Tc <call-offset> <call-offset> <base encoding>
		4920	case 'c': {
		4921	First += 2;
		4922	if (parseCallOffset() \|\| parseCallOffset())
		4923	return nullptr;
		4924	Node *Encoding = getDerived().parseEncoding();
		4925	if (Encoding == nullptr)
		4926	return nullptr;
		4927	return make<SpecialName>("covariant return thunk to ", Encoding);
		4928	}
		4929	// extension ::= TC <first type> <number> _ <second type>
		4930	// # construction vtable for second-in-first
		4931	case 'C': {
		4932	First += 2;
		4933	Node *FirstType = getDerived().parseType();
		4934	if (FirstType == nullptr)
		4935	return nullptr;
		4936	if (parseNumber(true).empty() \|\| !consumeIf('_'))
		4937	return nullptr;
		4938	Node *SecondType = getDerived().parseType();
		4939	if (SecondType == nullptr)
		4940	return nullptr;
		4941	return make<CtorVtableSpecialName>(SecondType, FirstType);
		4942	}
		4943	// TW <object name> # Thread-local wrapper
		4944	case 'W': {
		4945	First += 2;
		4946	Node *Name = getDerived().parseName();
		4947	if (Name == nullptr)
		4948	return nullptr;
		4949	return make<SpecialName>("thread-local wrapper routine for ", Name);
		4950	}
		4951	// TH <object name> # Thread-local initialization
		4952	case 'H': {
		4953	First += 2;
		4954	Node *Name = getDerived().parseName();
		4955	if (Name == nullptr)
		4956	return nullptr;
		4957	return make<SpecialName>("thread-local initialization routine for ", Name);
		4958	}
		4959	// T <call-offset> <base encoding>
		4960	default: {
		4961	++First;
		4962	bool IsVirt = look() == 'v';
		4963	if (parseCallOffset())
		4964	return nullptr;
		4965	Node *BaseEncoding = getDerived().parseEncoding();
		4966	if (BaseEncoding == nullptr)
		4967	return nullptr;
		4968	if (IsVirt)
		4969	return make<SpecialName>("virtual thunk to ", BaseEncoding);
		4970	else
		4971	return make<SpecialName>("non-virtual thunk to ", BaseEncoding);
		4972	}
		4973	}
		4974	case 'G':
		4975	switch (look(1)) {
		4976	// GV <object name> # Guard variable for one-time initialization
		4977	case 'V': {
		4978	First += 2;
		4979	Node *Name = getDerived().parseName();
		4980	if (Name == nullptr)
		4981	return nullptr;
		4982	return make<SpecialName>("guard variable for ", Name);
		4983	}
		4984	// GR <object name> # reference temporary for object
		4985	// GR <object name> _ # First temporary
		4986	// GR <object name> <seq-id> _ # Subsequent temporaries
		4987	case 'R': {
		4988	First += 2;
		4989	Node *Name = getDerived().parseName();
		4990	if (Name == nullptr)
		4991	return nullptr;
		4992	size_t Count;
		4993	bool ParsedSeqId = !parseSeqId(&Count);
		4994	if (!consumeIf('_') && ParsedSeqId)
		4995	return nullptr;
		4996	return make<SpecialName>("reference temporary for ", Name);
		4997	}
		4998	// GI <module-name> v
		4999	case 'I': {
		5000	First += 2;
		5001	ModuleName *Module = nullptr;
		5002	if (getDerived().parseModuleNameOpt(Module))
		5003	return nullptr;
		5004	if (Module == nullptr)
		5005	return nullptr;
		5006	return make<SpecialName>("initializer for module ", Module);
		5007	}
		5008	}
		5009	}
		5010	return nullptr;
		5011	}
		5012
		5013	// <encoding> ::= <function name> <bare-function-type>
		5014	// ::= <data name>
		5015	// ::= <special-name>
		5016	template <typename Derived, typename Alloc>
		5017	Node *AbstractManglingParser<Derived, Alloc>::parseEncoding() {
		5018	// The template parameters of an encoding are unrelated to those of the
		5019	// enclosing context.
		5020	class SaveTemplateParams {
		5021	AbstractManglingParser *Parser;
		5022	decltype(TemplateParams) OldParams;
		5023	decltype(OuterTemplateParams) OldOuterParams;
		5024
		5025	public:
		5026	SaveTemplateParams(AbstractManglingParser *TheParser) : Parser(TheParser) {
		5027	OldParams = std::move(Parser->TemplateParams);
		5028	OldOuterParams = std::move(Parser->OuterTemplateParams);
		5029	Parser->TemplateParams.clear();
		5030	Parser->OuterTemplateParams.clear();
		5031	}
		5032	~SaveTemplateParams() {
		5033	Parser->TemplateParams = std::move(OldParams);
		5034	Parser->OuterTemplateParams = std::move(OldOuterParams);
		5035	}
		5036	} SaveTemplateParams(this);
		5037
		5038	if (look() == 'G' \|\| look() == 'T')
		5039	return getDerived().parseSpecialName();
		5040
		5041	auto IsEndOfEncoding = [&] {
		5042	// The set of chars that can potentially follow an <encoding> (none of which
		5043	// can start a <type>). Enumerating these allows us to avoid speculative
		5044	// parsing.
		5045	return numLeft() == 0 \|\| look() == 'E' \|\| look() == '.' \|\| look() == '_';
		5046	};
		5047
		5048	NameState NameInfo(this);
		5049	Node *Name = getDerived().parseName(&NameInfo);
		5050	if (Name == nullptr)
		5051	return nullptr;
		5052
		5053	if (resolveForwardTemplateRefs(NameInfo))
		5054	return nullptr;
		5055
		5056	if (IsEndOfEncoding())
		5057	return Name;
		5058
		5059	Node *Attrs = nullptr;
		5060	if (consumeIf("Ua9enable_ifI")) {
		5061	size_t BeforeArgs = Names.size();
		5062	while (!consumeIf('E')) {
		5063	Node *Arg = getDerived().parseTemplateArg();
		5064	if (Arg == nullptr)
		5065	return nullptr;
		5066	Names.push_back(Arg);
		5067	}
		5068	Attrs = make<EnableIfAttr>(popTrailingNodeArray(BeforeArgs));
		5069	if (!Attrs)
		5070	return nullptr;
		5071	}
		5072
		5073	Node *ReturnType = nullptr;
		5074	if (!NameInfo.CtorDtorConversion && NameInfo.EndsWithTemplateArgs) {
		5075	ReturnType = getDerived().parseType();
		5076	if (ReturnType == nullptr)
		5077	return nullptr;
		5078	}
		5079
		5080	if (consumeIf('v'))
		5081	return make<FunctionEncoding>(ReturnType, Name, NodeArray(),
		5082	Attrs, NameInfo.CVQualifiers,
		5083	NameInfo.ReferenceQualifier);
		5084
		5085	size_t ParamsBegin = Names.size();
		5086	do {
		5087	Node *Ty = getDerived().parseType();
		5088	if (Ty == nullptr)
		5089	return nullptr;
		5090	Names.push_back(Ty);
		5091	} while (!IsEndOfEncoding());
		5092
		5093	return make<FunctionEncoding>(ReturnType, Name,
		5094	popTrailingNodeArray(ParamsBegin),
		5095	Attrs, NameInfo.CVQualifiers,
		5096	NameInfo.ReferenceQualifier);
		5097	}
		5098
		5099	template <class Float>
		5100	struct FloatData;
		5101
		5102	template <>
		5103	struct FloatData<float>
		5104	{
		5105	static const size_t mangled_size = 8;
		5106	static const size_t max_demangled_size = 24;
		5107	static constexpr const char* spec = "%af";
		5108	};
		5109
		5110	template <>
		5111	struct FloatData<double>
		5112	{
		5113	static const size_t mangled_size = 16;
		5114	static const size_t max_demangled_size = 32;
		5115	static constexpr const char* spec = "%a";
		5116	};
		5117
		5118	template <>
		5119	struct FloatData<long double>
		5120	{
		5121	#if defined(__mips__) && defined(__mips_n64) \|\| defined(__aarch64__) \|\| \
		5122	defined(__wasm__) \|\| defined(__riscv) \|\| defined(__loongarch__)
		5123	static const size_t mangled_size = 32;
		5124	#elif defined(__arm__) \|\| defined(__mips__) \|\| defined(__hexagon__)
		5125	static const size_t mangled_size = 16;
		5126	#else
		5127	static const size_t mangled_size = 20; // May need to be adjusted to 16 or 24 on other platforms
		5128	#endif
		5129	// `-0x1.ffffffffffffffffffffffffffffp+16383` + 'L' + '\0' == 42 bytes.
		5130	// 28 'f's * 4 bits == 112 bits, which is the number of mantissa bits.
		5131	// Negatives are one character longer than positives.
		5132	// `0x1.` and `p` are constant, and exponents `+16383` and `-16382` are the
		5133	// same length. 1 sign bit, 112 mantissa bits, and 15 exponent bits == 128.
		5134	static const size_t max_demangled_size = 42;
		5135	static constexpr const char *spec = "%LaL";
		5136	};
		5137
		5138	template <typename Alloc, typename Derived>
		5139	template <class Float>
		5140	Node *AbstractManglingParser<Alloc, Derived>::parseFloatingLiteral() {
		5141	const size_t N = FloatData<Float>::mangled_size;
		5142	if (numLeft() <= N)
		5143	return nullptr;
		5144	StringView Data(First, First + N);
		5145	for (char C : Data)
		5146	if (!std::isxdigit(C))
		5147	return nullptr;
		5148	First += N;
		5149	if (!consumeIf('E'))
		5150	return nullptr;
		5151	return make<FloatLiteralImpl<Float>>(Data);
		5152	}
		5153
		5154	// <seq-id> ::= <0-9A-Z>+
		5155	template <typename Alloc, typename Derived>
		5156	bool AbstractManglingParser<Alloc, Derived>::parseSeqId(size_t *Out) {
		5157	if (!(look() >= '0' && look() <= '9') &&
		5158	!(look() >= 'A' && look() <= 'Z'))
		5159	return true;
		5160
		5161	size_t Id = 0;
		5162	while (true) {
		5163	if (look() >= '0' && look() <= '9') {
		5164	Id *= 36;
		5165	Id += static_cast<size_t>(look() - '0');
		5166	} else if (look() >= 'A' && look() <= 'Z') {
		5167	Id *= 36;
		5168	Id += static_cast<size_t>(look() - 'A') + 10;
		5169	} else {
		5170	*Out = Id;
		5171	return false;
		5172	}
		5173	++First;
		5174	}
		5175	}
		5176
		5177	// <substitution> ::= S <seq-id> _
		5178	// ::= S_
		5179	// <substitution> ::= Sa # ::std::allocator
		5180	// <substitution> ::= Sb # ::std::basic_string
		5181	// <substitution> ::= Ss # ::std::basic_string < char,
		5182	// ::std::char_traits<char>,
		5183	// ::std::allocator<char> >
		5184	// <substitution> ::= Si # ::std::basic_istream<char, std::char_traits<char> >
		5185	// <substitution> ::= So # ::std::basic_ostream<char, std::char_traits<char> >
		5186	// <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
		5187	// The St case is handled specially in parseNestedName.
		5188	template <typename Derived, typename Alloc>
		5189	Node *AbstractManglingParser<Derived, Alloc>::parseSubstitution() {
		5190	if (!consumeIf('S'))
		5191	return nullptr;
		5192
		5193	if (look() >= 'a' && look() <= 'z') {
		5194	SpecialSubKind Kind;
		5195	switch (look()) {
		5196	case 'a':
		5197	Kind = SpecialSubKind::allocator;
		5198	break;
		5199	case 'b':
		5200	Kind = SpecialSubKind::basic_string;
		5201	break;
		5202	case 'd':
		5203	Kind = SpecialSubKind::iostream;
		5204	break;
		5205	case 'i':
		5206	Kind = SpecialSubKind::istream;
		5207	break;
		5208	case 'o':
		5209	Kind = SpecialSubKind::ostream;
		5210	break;
		5211	case 's':
		5212	Kind = SpecialSubKind::string;
		5213	break;
		5214	default:
		5215	return nullptr;
		5216	}
		5217	++First;
		5218	auto *SpecialSub = make<SpecialSubstitution>(Kind);
		5219	if (!SpecialSub)
		5220	return nullptr;
		5221
		5222	// Itanium C++ ABI 5.1.2: If a name that would use a built-in <substitution>
		5223	// has ABI tags, the tags are appended to the substitution; the result is a
		5224	// substitutable component.
		5225	Node *WithTags = getDerived().parseAbiTags(SpecialSub);
		5226	if (WithTags != SpecialSub) {
		5227	Subs.push_back(WithTags);
		5228	SpecialSub = WithTags;
		5229	}
		5230	return SpecialSub;
		5231	}
		5232
		5233	// ::= S_
		5234	if (consumeIf('_')) {
		5235	if (Subs.empty())
		5236	return nullptr;
		5237	return Subs[0];
		5238	}
		5239
		5240	// ::= S <seq-id> _
		5241	size_t Index = 0;
		5242	if (parseSeqId(&Index))
		5243	return nullptr;
		5244	++Index;
		5245	if (!consumeIf('_') \|\| Index >= Subs.size())
		5246	return nullptr;
		5247	return Subs[Index];
		5248	}
		5249
		5250	// <template-param> ::= T_ # first template parameter
		5251	// ::= T <parameter-2 non-negative number> _
		5252	// ::= TL <level-1> __
		5253	// ::= TL <level-1> _ <parameter-2 non-negative number> _
		5254	template <typename Derived, typename Alloc>
		5255	Node *AbstractManglingParser<Derived, Alloc>::parseTemplateParam() {
		5256	if (!consumeIf('T'))
		5257	return nullptr;
		5258
		5259	size_t Level = 0;
		5260	if (consumeIf('L')) {
		5261	if (parsePositiveInteger(&Level))
		5262	return nullptr;
		5263	++Level;
		5264	if (!consumeIf('_'))
		5265	return nullptr;
		5266	}
		5267
		5268	size_t Index = 0;
		5269	if (!consumeIf('_')) {
		5270	if (parsePositiveInteger(&Index))
		5271	return nullptr;
		5272	++Index;
		5273	if (!consumeIf('_'))
		5274	return nullptr;
		5275	}
		5276
		5277	// If we're in a context where this <template-param> refers to a
		5278	// <template-arg> further ahead in the mangled name (currently just conversion
		5279	// operator types), then we should only look it up in the right context.
		5280	// This can only happen at the outermost level.
		5281	if (PermitForwardTemplateReferences && Level == 0) {
		5282	Node *ForwardRef = make<ForwardTemplateReference>(Index);
		5283	if (!ForwardRef)
		5284	return nullptr;
		5285	assert(ForwardRef->getKind() == Node::KForwardTemplateReference);
		5286	ForwardTemplateRefs.push_back(
		5287	static_cast<ForwardTemplateReference *>(ForwardRef));
		5288	return ForwardRef;
		5289	}
		5290
		5291	if (Level >= TemplateParams.size() \|\| !TemplateParams[Level] \|\|
		5292	Index >= TemplateParams[Level]->size()) {
		5293	// Itanium ABI 5.1.8: In a generic lambda, uses of auto in the parameter
		5294	// list are mangled as the corresponding artificial template type parameter.
		5295	if (ParsingLambdaParamsAtLevel == Level && Level <= TemplateParams.size()) {
		5296	// This will be popped by the ScopedTemplateParamList in
		5297	// parseUnnamedTypeName.
		5298	if (Level == TemplateParams.size())
		5299	TemplateParams.push_back(nullptr);
		5300	return make<NameType>("auto");
		5301	}
		5302
		5303	return nullptr;
		5304	}
		5305
		5306	return (*TemplateParams[Level])[Index];
		5307	}
		5308
		5309	// <template-param-decl> ::= Ty # type parameter
		5310	// ::= Tn <type> # non-type parameter
		5311	// ::= Tt <template-param-decl>* E # template parameter
		5312	// ::= Tp <template-param-decl> # parameter pack
		5313	template <typename Derived, typename Alloc>
		5314	Node *AbstractManglingParser<Derived, Alloc>::parseTemplateParamDecl() {
		5315	auto InventTemplateParamName = [&](TemplateParamKind Kind) {
		5316	unsigned Index = NumSyntheticTemplateParameters[(int)Kind]++;
		5317	Node *N = make<SyntheticTemplateParamName>(Kind, Index);
		5318	if (N) TemplateParams.back()->push_back(N);
		5319	return N;
		5320	};
		5321
		5322	if (consumeIf("Ty")) {
		5323	Node *Name = InventTemplateParamName(TemplateParamKind::Type);
		5324	if (!Name)
		5325	return nullptr;
		5326	return make<TypeTemplateParamDecl>(Name);
		5327	}
		5328
		5329	if (consumeIf("Tn")) {
		5330	Node *Name = InventTemplateParamName(TemplateParamKind::NonType);
		5331	if (!Name)
		5332	return nullptr;
		5333	Node *Type = parseType();
		5334	if (!Type)
		5335	return nullptr;
		5336	return make<NonTypeTemplateParamDecl>(Name, Type);
		5337	}
		5338
		5339	if (consumeIf("Tt")) {
		5340	Node *Name = InventTemplateParamName(TemplateParamKind::Template);
		5341	if (!Name)
		5342	return nullptr;
		5343	size_t ParamsBegin = Names.size();
		5344	ScopedTemplateParamList TemplateTemplateParamParams(this);
		5345	while (!consumeIf("E")) {
		5346	Node *P = parseTemplateParamDecl();
		5347	if (!P)
		5348	return nullptr;
		5349	Names.push_back(P);
		5350	}
		5351	NodeArray Params = popTrailingNodeArray(ParamsBegin);
		5352	return make<TemplateTemplateParamDecl>(Name, Params);
		5353	}
		5354
		5355	if (consumeIf("Tp")) {
		5356	Node *P = parseTemplateParamDecl();
		5357	if (!P)
		5358	return nullptr;
		5359	return make<TemplateParamPackDecl>(P);
		5360	}
		5361
		5362	return nullptr;
		5363	}
		5364
		5365	// <template-arg> ::= <type> # type or template
		5366	// ::= X <expression> E # expression
		5367	// ::= <expr-primary> # simple expressions
		5368	// ::= J <template-arg>* E # argument pack
		5369	// ::= LZ <encoding> E # extension
		5370	template <typename Derived, typename Alloc>
		5371	Node *AbstractManglingParser<Derived, Alloc>::parseTemplateArg() {
		5372	switch (look()) {
		5373	case 'X': {
		5374	++First;
		5375	Node *Arg = getDerived().parseExpr();
		5376	if (Arg == nullptr \|\| !consumeIf('E'))
		5377	return nullptr;
		5378	return Arg;
		5379	}
		5380	case 'J': {
		5381	++First;
		5382	size_t ArgsBegin = Names.size();
		5383	while (!consumeIf('E')) {
		5384	Node *Arg = getDerived().parseTemplateArg();
		5385	if (Arg == nullptr)
		5386	return nullptr;
		5387	Names.push_back(Arg);
		5388	}
		5389	NodeArray Args = popTrailingNodeArray(ArgsBegin);
		5390	return make<TemplateArgumentPack>(Args);
		5391	}
		5392	case 'L': {
		5393	// ::= LZ <encoding> E # extension
		5394	if (look(1) == 'Z') {
		5395	First += 2;
		5396	Node *Arg = getDerived().parseEncoding();
		5397	if (Arg == nullptr \|\| !consumeIf('E'))
		5398	return nullptr;
		5399	return Arg;
		5400	}
		5401	// ::= <expr-primary> # simple expressions
		5402	return getDerived().parseExprPrimary();
		5403	}
		5404	default:
		5405	return getDerived().parseType();
		5406	}
		5407	}
		5408
		5409	// <template-args> ::= I <template-arg>* E
		5410	// extension, the abi says <template-arg>+
		5411	template <typename Derived, typename Alloc>
		5412	Node *
		5413	AbstractManglingParser<Derived, Alloc>::parseTemplateArgs(bool TagTemplates) {
		5414	if (!consumeIf('I'))
		5415	return nullptr;
		5416
		5417	// <template-params> refer to the innermost <template-args>. Clear out any
		5418	// outer args that we may have inserted into TemplateParams.
		5419	if (TagTemplates) {
		5420	TemplateParams.clear();
		5421	TemplateParams.push_back(&OuterTemplateParams);
		5422	OuterTemplateParams.clear();
		5423	}
		5424
		5425	size_t ArgsBegin = Names.size();
		5426	while (!consumeIf('E')) {
		5427	if (TagTemplates) {
		5428	auto OldParams = std::move(TemplateParams);
		5429	Node *Arg = getDerived().parseTemplateArg();
		5430	TemplateParams = std::move(OldParams);
		5431	if (Arg == nullptr)
		5432	return nullptr;
		5433	Names.push_back(Arg);
		5434	Node *TableEntry = Arg;
		5435	if (Arg->getKind() == Node::KTemplateArgumentPack) {
		5436	TableEntry = make<ParameterPack>(
		5437	static_cast<TemplateArgumentPack*>(TableEntry)->getElements());
		5438	if (!TableEntry)
		5439	return nullptr;
		5440	}
		5441	TemplateParams.back()->push_back(TableEntry);
		5442	} else {
		5443	Node *Arg = getDerived().parseTemplateArg();
		5444	if (Arg == nullptr)
		5445	return nullptr;
		5446	Names.push_back(Arg);
		5447	}
		5448	}
		5449	return make<TemplateArgs>(popTrailingNodeArray(ArgsBegin));
		5450	}
		5451
		5452	// <mangled-name> ::= _Z <encoding>
		5453	// ::= <type>
		5454	// extension ::= ___Z <encoding> _block_invoke
		5455	// extension ::= ___Z <encoding> _block_invoke<decimal-digit>+
		5456	// extension ::= ___Z <encoding> _block_invoke_<decimal-digit>+
		5457	template <typename Derived, typename Alloc>
		5458	Node *AbstractManglingParser<Derived, Alloc>::parse() {
		5459	if (consumeIf("_Z") \|\| consumeIf("__Z")) {
		5460	Node *Encoding = getDerived().parseEncoding();
		5461	if (Encoding == nullptr)
		5462	return nullptr;
		5463	if (look() == '.') {
		5464	Encoding = make<DotSuffix>(Encoding, StringView(First, Last));
		5465	First = Last;
		5466	}
		5467	if (numLeft() != 0)
		5468	return nullptr;
		5469	return Encoding;
		5470	}
		5471
		5472	if (consumeIf("___Z") \|\| consumeIf("____Z")) {
		5473	Node *Encoding = getDerived().parseEncoding();
		5474	if (Encoding == nullptr \|\| !consumeIf("_block_invoke"))
		5475	return nullptr;
		5476	bool RequireNumber = consumeIf('_');
		5477	if (parseNumber().empty() && RequireNumber)
		5478	return nullptr;
		5479	if (look() == '.')
		5480	First = Last;
		5481	if (numLeft() != 0)
		5482	return nullptr;
		5483	return make<SpecialName>("invocation function for block in ", Encoding);
		5484	}
		5485
		5486	Node *Ty = getDerived().parseType();
		5487	if (numLeft() != 0)
		5488	return nullptr;
		5489	return Ty;
		5490	}
		5491
		5492	template <typename Alloc>
		5493	struct ManglingParser : AbstractManglingParser<ManglingParser<Alloc>, Alloc> {
		5494	using AbstractManglingParser<ManglingParser<Alloc>,
		5495	Alloc>::AbstractManglingParser;
		5496	};
		5497
		5498	DEMANGLE_NAMESPACE_END
		5499
		5500	#endif // DEMANGLE_ITANIUMDEMANGLE_H

Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

QNX 8.QNX8 LLVM/Clang compiler suite//llvm-build/x86_64/include/llvm/Demangle/ItaniumDemangle.h – Rev 14