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