ItaniumDemangle.h source code [engine/third_party/libcxxabi/src/demangle/ItaniumDemangle.h]

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

Browse the source code of engine/third_party/libcxxabi/src/demangle/ItaniumDemangle.h