1	//===--- ASTDiagnostic.cpp - Diagnostic Printing Hooks for AST Nodes ------===//
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	// This file implements a diagnostic formatting hook for AST elements.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/AST/ASTDiagnostic.h"
14	#include "clang/AST/ASTContext.h"
15	#include "clang/AST/ASTLambda.h"
16	#include "clang/AST/Attr.h"
17	#include "clang/AST/DeclObjC.h"
18	#include "clang/AST/DeclTemplate.h"
19	#include "clang/AST/ExprCXX.h"
20	#include "clang/AST/TemplateBase.h"
21	#include "clang/AST/Type.h"
22	#include "llvm/ADT/StringExtras.h"
23	#include "llvm/Support/ConvertUTF.h"
24	#include "llvm/Support/Format.h"
25	#include "llvm/Support/raw_ostream.h"
26
27	using namespace clang;
28
29	// Returns a desugared version of the QualType, and marks ShouldAKA as true
30	// whenever we remove significant sugar from the type. Make sure ShouldAKA
31	// is initialized before passing it in.
32	QualType clang::desugarForDiagnostic(ASTContext &Context, QualType QT,
33	bool &ShouldAKA) {
34	QualifierCollector QC;
35
36	while (true) {
37	const Type *Ty = QC.strip(type: QT);
38
39	// Don't aka just because we saw an elaborated type...
40	if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(Val: Ty)) {
41	QT = ET->desugar();
42	continue;
43	}
44	// ... or a using type ...
45	if (const UsingType *UT = dyn_cast<UsingType>(Val: Ty)) {
46	QT = UT->desugar();
47	continue;
48	}
49	// ... or a paren type ...
50	if (const ParenType *PT = dyn_cast<ParenType>(Val: Ty)) {
51	QT = PT->desugar();
52	continue;
53	}
54	// ... or a macro defined type ...
55	if (const MacroQualifiedType *MDT = dyn_cast<MacroQualifiedType>(Val: Ty)) {
56	QT = MDT->desugar();
57	continue;
58	}
59	// ...or a substituted template type parameter ...
60	if (const SubstTemplateTypeParmType *ST =
61	dyn_cast<SubstTemplateTypeParmType>(Val: Ty)) {
62	QT = ST->desugar();
63	continue;
64	}
65	// ...or an attributed type...
66	if (const AttributedType *AT = dyn_cast<AttributedType>(Val: Ty)) {
67	QT = AT->desugar();
68	continue;
69	}
70	// ...or an adjusted type...
71	if (const AdjustedType *AT = dyn_cast<AdjustedType>(Val: Ty)) {
72	QT = AT->desugar();
73	continue;
74	}
75	// ... or an auto type.
76	if (const AutoType *AT = dyn_cast<AutoType>(Val: Ty)) {
77	if (!AT->isSugared())
78	break;
79	QT = AT->desugar();
80	continue;
81	}
82
83	// Desugar FunctionType if return type or any parameter type should be
84	// desugared. Preserve nullability attribute on desugared types.
85	if (const FunctionType *FT = dyn_cast<FunctionType>(Val: Ty)) {
86	bool DesugarReturn = false;
87	QualType SugarRT = FT->getReturnType();
88	QualType RT = desugarForDiagnostic(Context, QT: SugarRT, ShouldAKA&: DesugarReturn);
89	if (auto nullability = AttributedType::stripOuterNullability(T&: SugarRT)) {
90	RT = Context.getAttributedType(nullability: *nullability, modifiedType: RT, equivalentType: RT);
91	}
92
93	bool DesugarArgument = false;
94	SmallVector<QualType, 4> Args;
95	const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(Val: FT);
96	if (FPT) {
97	for (QualType SugarPT : FPT->param_types()) {
98	QualType PT = desugarForDiagnostic(Context, QT: SugarPT, ShouldAKA&: DesugarArgument);
99	if (auto nullability =
100	AttributedType::stripOuterNullability(T&: SugarPT)) {
101	PT = Context.getAttributedType(nullability: *nullability, modifiedType: PT, equivalentType: PT);
102	}
103	Args.push_back(Elt: PT);
104	}
105	}
106
107	if (DesugarReturn || DesugarArgument) {
108	ShouldAKA = true;
109	QT = FPT ? Context.getFunctionType(ResultTy: RT, Args, EPI: FPT->getExtProtoInfo())
110	: Context.getFunctionNoProtoType(ResultTy: RT, Info: FT->getExtInfo());
111	break;
112	}
113	}
114
115	// Desugar template specializations if any template argument should be
116	// desugared.
117	if (const TemplateSpecializationType *TST =
118	dyn_cast<TemplateSpecializationType>(Val: Ty)) {
119	if (!TST->isTypeAlias()) {
120	bool DesugarArgument = false;
121	SmallVector<TemplateArgument, 4> Args;
122	for (const TemplateArgument &Arg : TST->template_arguments()) {
123	if (Arg.getKind() == TemplateArgument::Type)
124	Args.push_back(Elt: desugarForDiagnostic(Context, QT: Arg.getAsType(),
125	ShouldAKA&: DesugarArgument));
126	else
127	Args.push_back(Elt: Arg);
128	}
129
130	if (DesugarArgument) {
131	ShouldAKA = true;
132	QT = Context.getTemplateSpecializationType(
133	T: TST->getTemplateName(), SpecifiedArgs: Args, /*CanonicalArgs=*/{}, Underlying: QT);
134	}
135	break;
136	}
137	}
138
139	if (const auto *AT = dyn_cast<ArrayType>(Val: Ty)) {
140	QualType ElementTy =
141	desugarForDiagnostic(Context, QT: AT->getElementType(), ShouldAKA);
142	if (const auto *CAT = dyn_cast<ConstantArrayType>(Val: AT))
143	QT = Context.getConstantArrayType(
144	EltTy: ElementTy, ArySize: CAT->getSize(), SizeExpr: CAT->getSizeExpr(),
145	ASM: CAT->getSizeModifier(), IndexTypeQuals: CAT->getIndexTypeCVRQualifiers());
146	else if (const auto *VAT = dyn_cast<VariableArrayType>(Val: AT))
147	QT = Context.getVariableArrayType(EltTy: ElementTy, NumElts: VAT->getSizeExpr(),
148	ASM: VAT->getSizeModifier(),
149	IndexTypeQuals: VAT->getIndexTypeCVRQualifiers());
150	else if (const auto *DSAT = dyn_cast<DependentSizedArrayType>(Val: AT))
151	QT = Context.getDependentSizedArrayType(
152	EltTy: ElementTy, NumElts: DSAT->getSizeExpr(), ASM: DSAT->getSizeModifier(),
153	IndexTypeQuals: DSAT->getIndexTypeCVRQualifiers());
154	else if (const auto *IAT = dyn_cast<IncompleteArrayType>(Val: AT))
155	QT = Context.getIncompleteArrayType(EltTy: ElementTy, ASM: IAT->getSizeModifier(),
156	IndexTypeQuals: IAT->getIndexTypeCVRQualifiers());
157	else
158	llvm_unreachable("Unhandled array type");
159	break;
160	}
161
162	// Don't desugar magic Objective-C types.
163	if (QualType(Ty,0) == Context.getObjCIdType() ||
164	QualType(Ty,0) == Context.getObjCClassType() ||
165	QualType(Ty,0) == Context.getObjCSelType() ||
166	QualType(Ty,0) == Context.getObjCProtoType())
167	break;
168
169	// Don't desugar va_list.
170	if (QualType(Ty, 0) == Context.getBuiltinVaListType() ||
171	QualType(Ty, 0) == Context.getBuiltinMSVaListType())
172	break;
173
174	// Otherwise, do a single-step desugar.
175	QualType Underlying;
176	bool IsSugar = false;
177	switch (Ty->getTypeClass()) {
178	#define ABSTRACT_TYPE(Class, Base)
179	#define TYPE(Class, Base) \
180	case Type::Class: { \
181	const Class##Type *CTy = cast<Class##Type>(Ty); \
182	if (CTy->isSugared()) { \
183	IsSugar = true; \
184	Underlying = CTy->desugar(); \
185	} \
186	break; \
187	}
188	#include "clang/AST/TypeNodes.inc"
189	}
190
191	// If it wasn't sugared, we're done.
192	if (!IsSugar)
193	break;
194
195	// If the desugared type is a vector type, we don't want to expand
196	// it, it will turn into an attribute mess. People want their "vec4".
197	if (isa<VectorType>(Val: Underlying))
198	break;
199
200	// Don't desugar through the primary typedef of an anonymous type.
201	if (const TagType *UTT = Underlying->getAs<TagType>())
202	if (const TypedefType *QTT = dyn_cast<TypedefType>(Val&: QT))
203	if (UTT->getDecl()->getTypedefNameForAnonDecl() == QTT->getDecl())
204	break;
205
206	// Record that we actually looked through an opaque type here.
207	ShouldAKA = true;
208	QT = Underlying;
209	}
210
211	// If we have a pointer-like type, desugar the pointee as well.
212	// FIXME: Handle other pointer-like types.
213	if (const PointerType *Ty = QT->getAs<PointerType>()) {
214	QT = Context.getPointerType(
215	T: desugarForDiagnostic(Context, QT: Ty->getPointeeType(), ShouldAKA));
216	} else if (const auto *Ty = QT->getAs<ObjCObjectPointerType>()) {
217	QT = Context.getObjCObjectPointerType(
218	OIT: desugarForDiagnostic(Context, QT: Ty->getPointeeType(), ShouldAKA));
219	} else if (const LValueReferenceType *Ty = QT->getAs<LValueReferenceType>()) {
220	QT = Context.getLValueReferenceType(
221	T: desugarForDiagnostic(Context, QT: Ty->getPointeeType(), ShouldAKA));
222	} else if (const RValueReferenceType *Ty = QT->getAs<RValueReferenceType>()) {
223	QT = Context.getRValueReferenceType(
224	T: desugarForDiagnostic(Context, QT: Ty->getPointeeType(), ShouldAKA));
225	} else if (const auto *Ty = QT->getAs<ObjCObjectType>()) {
226	if (Ty->getBaseType().getTypePtr() != Ty && !ShouldAKA) {
227	QualType BaseType =
228	desugarForDiagnostic(Context, QT: Ty->getBaseType(), ShouldAKA);
229	QT = Context.getObjCObjectType(
230	Base: BaseType, typeArgs: Ty->getTypeArgsAsWritten(),
231	protocols: ArrayRef(Ty->qual_begin(), Ty->getNumProtocols()),
232	isKindOf: Ty->isKindOfTypeAsWritten());
233	}
234	}
235
236	return QC.apply(Context, QT);
237	}
238
239	/// Convert the given type to a string suitable for printing as part of
240	/// a diagnostic.
241	///
242	/// There are four main criteria when determining whether we should have an
243	/// a.k.a. clause when pretty-printing a type:
244	///
245	/// 1) Some types provide very minimal sugar that doesn't impede the
246	/// user's understanding --- for example, elaborated type
247	/// specifiers. If this is all the sugar we see, we don't want an
248	/// a.k.a. clause.
249	/// 2) Some types are technically sugared but are much more familiar
250	/// when seen in their sugared form --- for example, va_list,
251	/// vector types, and the magic Objective C types. We don't
252	/// want to desugar these, even if we do produce an a.k.a. clause.
253	/// 3) Some types may have already been desugared previously in this diagnostic.
254	/// if this is the case, doing another "aka" would just be clutter.
255	/// 4) Two different types within the same diagnostic have the same output
256	/// string. In this case, force an a.k.a with the desugared type when
257	/// doing so will provide additional information.
258	///
259	/// \param Context the context in which the type was allocated
260	/// \param Ty the type to print
261	/// \param QualTypeVals pointer values to QualTypes which are used in the
262	/// diagnostic message
263	static std::string
264	ConvertTypeToDiagnosticString(ASTContext &Context, QualType Ty,
265	ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs,
266	ArrayRef<intptr_t> QualTypeVals) {
267	// FIXME: Playing with std::string is really slow.
268	bool ForceAKA = false;
269	QualType CanTy = Ty.getCanonicalType();
270	std::string S = Ty.getAsString(Policy: Context.getPrintingPolicy());
271	std::string CanS = CanTy.getAsString(Policy: Context.getPrintingPolicy());
272
273	for (const intptr_t &QualTypeVal : QualTypeVals) {
274	QualType CompareTy =
275	QualType::getFromOpaquePtr(Ptr: reinterpret_cast<void *>(QualTypeVal));
276	if (CompareTy.isNull())
277	continue;
278	if (CompareTy == Ty)
279	continue; // Same types
280	QualType CompareCanTy = CompareTy.getCanonicalType();
281	if (CompareCanTy == CanTy)
282	continue; // Same canonical types
283	std::string CompareS = CompareTy.getAsString(Policy: Context.getPrintingPolicy());
284	bool ShouldAKA = false;
285	QualType CompareDesugar =
286	desugarForDiagnostic(Context, QT: CompareTy, ShouldAKA);
287	std::string CompareDesugarStr =
288	CompareDesugar.getAsString(Policy: Context.getPrintingPolicy());
289	if (CompareS != S && CompareDesugarStr != S)
290	continue; // The type string is different than the comparison string
291	// and the desugared comparison string.
292	std::string CompareCanS =
293	CompareCanTy.getAsString(Policy: Context.getPrintingPolicy());
294
295	if (CompareCanS == CanS)
296	continue; // No new info from canonical type
297
298	ForceAKA = true;
299	break;
300	}
301
302	// Check to see if we already desugared this type in this
303	// diagnostic. If so, don't do it again.
304	bool Repeated = false;
305	for (const auto &PrevArg : PrevArgs) {
306	// TODO: Handle ak_declcontext case.
307	if (PrevArg.first == DiagnosticsEngine::ak_qualtype) {
308	QualType PrevTy(
309	QualType::getFromOpaquePtr(Ptr: reinterpret_cast<void *>(PrevArg.second)));
310	if (PrevTy == Ty) {
311	Repeated = true;
312	break;
313	}
314	}
315	}
316
317	// Consider producing an a.k.a. clause if removing all the direct
318	// sugar gives us something "significantly different".
319	if (!Repeated) {
320	bool ShouldAKA = false;
321	QualType DesugaredTy = desugarForDiagnostic(Context, QT: Ty, ShouldAKA);
322	if (ShouldAKA || ForceAKA) {
323	if (DesugaredTy == Ty) {
324	DesugaredTy = Ty.getCanonicalType();
325	}
326	std::string akaStr = DesugaredTy.getAsString(Policy: Context.getPrintingPolicy());
327	if (akaStr != S) {
328	S = "'" + S + "' (aka '" + akaStr + "')";
329	return S;
330	}
331	}
332
333	// Give some additional info on vector types. These are either not desugared
334	// or displaying complex __attribute__ expressions so add details of the
335	// type and element count.
336	if (const auto *VTy = Ty->getAs<VectorType>()) {
337	std::string DecoratedString;
338	llvm::raw_string_ostream OS(DecoratedString);
339	const char *Values = VTy->getNumElements() > 1 ? "values" : "value";
340	OS << "'" << S << "' (vector of " << VTy->getNumElements() << " '"
341	<< VTy->getElementType().getAsString(Policy: Context.getPrintingPolicy())
342	<< "' " << Values << ")";
343	return DecoratedString;
344	}
345	}
346
347	S = "'" + S + "'";
348	return S;
349	}
350
351	static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
352	QualType ToType, bool PrintTree,
353	bool PrintFromType, bool ElideType,
354	bool ShowColors, raw_ostream &OS);
355
356	void clang::FormatASTNodeDiagnosticArgument(
357	DiagnosticsEngine::ArgumentKind Kind,
358	intptr_t Val,
359	StringRef Modifier,
360	StringRef Argument,
361	ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs,
362	SmallVectorImpl<char> &Output,
363	void *Cookie,
364	ArrayRef<intptr_t> QualTypeVals) {
365	ASTContext &Context = *static_cast<ASTContext*>(Cookie);
366
367	size_t OldEnd = Output.size();
368	llvm::raw_svector_ostream OS(Output);
369	bool NeedQuotes = true;
370
371	switch (Kind) {
372	default: llvm_unreachable("unknown ArgumentKind");
373	case DiagnosticsEngine::ak_addrspace: {
374	assert(Modifier.empty() && Argument.empty() &&
375	"Invalid modifier for Qualifiers argument");
376
377	auto S = Qualifiers::getAddrSpaceAsString(AS: static_cast<LangAS>(Val));
378	if (S.empty()) {
379	OS << (Context.getLangOpts().OpenCL ? "default" : "generic");
380	OS << " address space";
381	} else {
382	OS << "address space";
383	OS << " '" << S << "'";
384	}
385	NeedQuotes = false;
386	break;
387	}
388	case DiagnosticsEngine::ak_qual: {
389	assert(Modifier.empty() && Argument.empty() &&
390	"Invalid modifier for Qualifiers argument");
391
392	Qualifiers Q(Qualifiers::fromOpaqueValue(opaque: Val));
393	auto S = Q.getAsString();
394	if (S.empty()) {
395	OS << "unqualified";
396	NeedQuotes = false;
397	} else {
398	OS << S;
399	}
400	break;
401	}
402	case DiagnosticsEngine::ak_qualtype_pair: {
403	TemplateDiffTypes &TDT = *reinterpret_cast<TemplateDiffTypes*>(Val);
404	QualType FromType =
405	QualType::getFromOpaquePtr(Ptr: reinterpret_cast<void*>(TDT.FromType));
406	QualType ToType =
407	QualType::getFromOpaquePtr(Ptr: reinterpret_cast<void*>(TDT.ToType));
408
409	if (FormatTemplateTypeDiff(Context, FromType, ToType, PrintTree: TDT.PrintTree,
410	PrintFromType: TDT.PrintFromType, ElideType: TDT.ElideType,
411	ShowColors: TDT.ShowColors, OS)) {
412	NeedQuotes = !TDT.PrintTree;
413	TDT.TemplateDiffUsed = true;
414	break;
415	}
416
417	// Don't fall-back during tree printing. The caller will handle
418	// this case.
419	if (TDT.PrintTree)
420	return;
421
422	// Attempting to do a template diff on non-templates. Set the variables
423	// and continue with regular type printing of the appropriate type.
424	Val = TDT.PrintFromType ? TDT.FromType : TDT.ToType;
425	Modifier = StringRef();
426	Argument = StringRef();
427	// Fall through
428	[[fallthrough]];
429	}
430	case DiagnosticsEngine::ak_qualtype: {
431	assert(Modifier.empty() && Argument.empty() &&
432	"Invalid modifier for QualType argument");
433
434	QualType Ty(QualType::getFromOpaquePtr(Ptr: reinterpret_cast<void*>(Val)));
435	OS << ConvertTypeToDiagnosticString(Context, Ty, PrevArgs, QualTypeVals);
436	NeedQuotes = false;
437	break;
438	}
439	case DiagnosticsEngine::ak_declarationname: {
440	if (Modifier == "objcclass" && Argument.empty())
441	OS << '+';
442	else if (Modifier == "objcinstance" && Argument.empty())
443	OS << '-';
444	else
445	assert(Modifier.empty() && Argument.empty() &&
446	"Invalid modifier for DeclarationName argument");
447
448	OS << DeclarationName::getFromOpaqueInteger(P: Val);
449	break;
450	}
451	case DiagnosticsEngine::ak_nameddecl: {
452	bool Qualified;
453	if (Modifier == "q" && Argument.empty())
454	Qualified = true;
455	else {
456	assert(Modifier.empty() && Argument.empty() &&
457	"Invalid modifier for NamedDecl* argument");
458	Qualified = false;
459	}
460	const NamedDecl *ND = reinterpret_cast<const NamedDecl*>(Val);
461	ND->getNameForDiagnostic(OS, Policy: Context.getPrintingPolicy(), Qualified);
462	break;
463	}
464	case DiagnosticsEngine::ak_nestednamespec: {
465	NestedNameSpecifier *NNS = reinterpret_cast<NestedNameSpecifier*>(Val);
466	NNS->print(OS, Policy: Context.getPrintingPolicy(),
467	/*ResolveTemplateArguments=*/false,
468	/*PrintFinalScopeResOp=*/false);
469	break;
470	}
471	case DiagnosticsEngine::ak_declcontext: {
472	DeclContext *DC = reinterpret_cast<DeclContext *> (Val);
473	assert(DC && "Should never have a null declaration context");
474	NeedQuotes = false;
475
476	// FIXME: Get the strings for DeclContext from some localized place
477	if (DC->isTranslationUnit()) {
478	if (Context.getLangOpts().CPlusPlus)
479	OS << "the global namespace";
480	else
481	OS << "the global scope";
482	} else if (DC->isClosure()) {
483	OS << "block literal";
484	} else if (isLambdaCallOperator(DC)) {
485	OS << "lambda expression";
486	} else if (TypeDecl *Type = dyn_cast<TypeDecl>(Val: DC)) {
487	OS << ConvertTypeToDiagnosticString(Context,
488	Ty: Context.getTypeDeclType(Decl: Type),
489	PrevArgs, QualTypeVals);
490	} else {
491	assert(isa<NamedDecl>(DC) && "Expected a NamedDecl");
492	NamedDecl *ND = cast<NamedDecl>(Val: DC);
493	if (isa<NamespaceDecl>(Val: ND))
494	OS << "namespace ";
495	else if (isa<ObjCMethodDecl>(Val: ND))
496	OS << "method ";
497	else if (isa<FunctionDecl>(Val: ND))
498	OS << "function ";
499
500	OS << '\'';
501	ND->getNameForDiagnostic(OS, Policy: Context.getPrintingPolicy(), Qualified: true);
502	OS << '\'';
503	}
504	break;
505	}
506	case DiagnosticsEngine::ak_attr: {
507	const Attr *At = reinterpret_cast<Attr *>(Val);
508	assert(At && "Received null Attr object!");
509
510	OS << '\'';
511	if (At->hasScope()) {
512	OS << At->getNormalizedFullName(ScopeName: At->getScopeName()->getName(),
513	AttrName: At->getSpelling());
514	} else {
515	OS << At->getSpelling();
516	}
517	OS << '\'';
518	NeedQuotes = false;
519	break;
520	}
521	case DiagnosticsEngine::ak_expr: {
522	const Expr *E = reinterpret_cast<Expr *>(Val);
523	assert(E && "Received null Expr!");
524	E->printPretty(OS, /*Helper=*/nullptr, Policy: Context.getPrintingPolicy());
525	break;
526	}
527	case DiagnosticsEngine::ak_attr_info: {
528	AttributeCommonInfo *AT = reinterpret_cast<AttributeCommonInfo *>(Val);
529	assert(AT && "Received null AttributeCommonInfo object!");
530
531	OS << '\'';
532	if (AT->isStandardAttributeSyntax()) {
533	OS << AT->getNormalizedFullName();
534	} else {
535	OS << AT->getAttrName()->getName();
536	}
537	OS << '\'';
538	NeedQuotes = false;
539	break;
540	}
541	}
542
543	if (NeedQuotes) {
544	Output.insert(I: Output.begin()+OldEnd, Elt: '\'');
545	Output.push_back(Elt: '\'');
546	}
547	}
548
549	/// TemplateDiff - A class that constructs a pretty string for a pair of
550	/// QualTypes. For the pair of types, a diff tree will be created containing
551	/// all the information about the templates and template arguments. Afterwards,
552	/// the tree is transformed to a string according to the options passed in.
553	namespace {
554	class TemplateDiff {
555	/// Context - The ASTContext which is used for comparing template arguments.
556	ASTContext &Context;
557
558	/// Policy - Used during expression printing.
559	PrintingPolicy Policy;
560
561	/// ElideType - Option to elide identical types.
562	bool ElideType;
563
564	/// PrintTree - Format output string as a tree.
565	bool PrintTree;
566
567	/// ShowColor - Diagnostics support color, so bolding will be used.
568	bool ShowColor;
569
570	/// FromTemplateType - When single type printing is selected, this is the
571	/// type to be printed. When tree printing is selected, this type will
572	/// show up first in the tree.
573	QualType FromTemplateType;
574
575	/// ToTemplateType - The type that FromType is compared to. Only in tree
576	/// printing will this type be outputed.
577	QualType ToTemplateType;
578
579	/// OS - The stream used to construct the output strings.
580	raw_ostream &OS;
581
582	/// IsBold - Keeps track of the bold formatting for the output string.
583	bool IsBold;
584
585	/// DiffTree - A tree representation of the differences between two types.
586	class DiffTree {
587	public:
588	/// DiffKind - The difference in a DiffNode. Fields of
589	/// TemplateArgumentInfo needed by each difference can be found in the
590	/// Set* and Get* functions.
591	enum DiffKind {
592	/// Incomplete or invalid node.
593	Invalid,
594	/// Another level of templates
595	Template,
596	/// Type difference, all type differences except those falling under
597	/// the Template difference.
598	Type,
599	/// Expression difference, this is only when both arguments are
600	/// expressions. If one argument is an expression and the other is
601	/// Integer or Declaration, then use that diff type instead.
602	Expression,
603	/// Template argument difference
604	TemplateTemplate,
605	/// Integer difference
606	Integer,
607	/// Declaration difference, nullptr arguments are included here
608	Declaration,
609	/// One argument being integer and the other being declaration
610	FromIntegerAndToDeclaration,
611	FromDeclarationAndToInteger
612	};
613
614	private:
615	/// TemplateArgumentInfo - All the information needed to pretty print
616	/// a template argument. See the Set* and Get* functions to see which
617	/// fields are used for each DiffKind.
618	struct TemplateArgumentInfo {
619	QualType ArgType;
620	Qualifiers Qual;
621	llvm::APSInt Val;
622	bool IsValidInt = false;
623	Expr *ArgExpr = nullptr;
624	TemplateDecl *TD = nullptr;
625	ValueDecl *VD = nullptr;
626	bool NeedAddressOf = false;
627	bool IsNullPtr = false;
628	bool IsDefault = false;
629	};
630
631	/// DiffNode - The root node stores the original type. Each child node
632	/// stores template arguments of their parents. For templated types, the
633	/// template decl is also stored.
634	struct DiffNode {
635	DiffKind Kind = Invalid;
636
637	/// NextNode - The index of the next sibling node or 0.
638	unsigned NextNode = 0;
639
640	/// ChildNode - The index of the first child node or 0.
641	unsigned ChildNode = 0;
642
643	/// ParentNode - The index of the parent node.
644	unsigned ParentNode = 0;
645
646	TemplateArgumentInfo FromArgInfo, ToArgInfo;
647
648	/// Same - Whether the two arguments evaluate to the same value.
649	bool Same = false;
650
651	DiffNode(unsigned ParentNode = 0) : ParentNode(ParentNode) {}
652	};
653
654	/// FlatTree - A flattened tree used to store the DiffNodes.
655	SmallVector<DiffNode, 16> FlatTree;
656
657	/// CurrentNode - The index of the current node being used.
658	unsigned CurrentNode;
659
660	/// NextFreeNode - The index of the next unused node. Used when creating
661	/// child nodes.
662	unsigned NextFreeNode;
663
664	/// ReadNode - The index of the current node being read.
665	unsigned ReadNode;
666
667	public:
668	DiffTree() : CurrentNode(0), NextFreeNode(1), ReadNode(0) {
669	FlatTree.push_back(Elt: DiffNode());
670	}
671
672	// Node writing functions, one for each valid DiffKind element.
673	void SetTemplateDiff(TemplateDecl *FromTD, TemplateDecl *ToTD,
674	Qualifiers FromQual, Qualifiers ToQual,
675	bool FromDefault, bool ToDefault) {
676	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
677	FlatTree[CurrentNode].Kind = Template;
678	FlatTree[CurrentNode].FromArgInfo.TD = FromTD;
679	FlatTree[CurrentNode].ToArgInfo.TD = ToTD;
680	FlatTree[CurrentNode].FromArgInfo.Qual = FromQual;
681	FlatTree[CurrentNode].ToArgInfo.Qual = ToQual;
682	SetDefault(FromDefault, ToDefault);
683	}
684
685	void SetTypeDiff(QualType FromType, QualType ToType, bool FromDefault,
686	bool ToDefault) {
687	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
688	FlatTree[CurrentNode].Kind = Type;
689	FlatTree[CurrentNode].FromArgInfo.ArgType = FromType;
690	FlatTree[CurrentNode].ToArgInfo.ArgType = ToType;
691	SetDefault(FromDefault, ToDefault);
692	}
693
694	void SetExpressionDiff(Expr *FromExpr, Expr *ToExpr, bool FromDefault,
695	bool ToDefault) {
696	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
697	FlatTree[CurrentNode].Kind = Expression;
698	FlatTree[CurrentNode].FromArgInfo.ArgExpr = FromExpr;
699	FlatTree[CurrentNode].ToArgInfo.ArgExpr = ToExpr;
700	SetDefault(FromDefault, ToDefault);
701	}
702
703	void SetTemplateTemplateDiff(TemplateDecl *FromTD, TemplateDecl *ToTD,
704	bool FromDefault, bool ToDefault) {
705	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
706	FlatTree[CurrentNode].Kind = TemplateTemplate;
707	FlatTree[CurrentNode].FromArgInfo.TD = FromTD;
708	FlatTree[CurrentNode].ToArgInfo.TD = ToTD;
709	SetDefault(FromDefault, ToDefault);
710	}
711
712	void SetIntegerDiff(const llvm::APSInt &FromInt, const llvm::APSInt &ToInt,
713	bool IsValidFromInt, bool IsValidToInt,
714	QualType FromIntType, QualType ToIntType,
715	Expr *FromExpr, Expr *ToExpr, bool FromDefault,
716	bool ToDefault) {
717	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
718	FlatTree[CurrentNode].Kind = Integer;
719	FlatTree[CurrentNode].FromArgInfo.Val = FromInt;
720	FlatTree[CurrentNode].ToArgInfo.Val = ToInt;
721	FlatTree[CurrentNode].FromArgInfo.IsValidInt = IsValidFromInt;
722	FlatTree[CurrentNode].ToArgInfo.IsValidInt = IsValidToInt;
723	FlatTree[CurrentNode].FromArgInfo.ArgType = FromIntType;
724	FlatTree[CurrentNode].ToArgInfo.ArgType = ToIntType;
725	FlatTree[CurrentNode].FromArgInfo.ArgExpr = FromExpr;
726	FlatTree[CurrentNode].ToArgInfo.ArgExpr = ToExpr;
727	SetDefault(FromDefault, ToDefault);
728	}
729
730	void SetDeclarationDiff(ValueDecl *FromValueDecl, ValueDecl *ToValueDecl,
731	bool FromAddressOf, bool ToAddressOf,
732	bool FromNullPtr, bool ToNullPtr, Expr *FromExpr,
733	Expr *ToExpr, bool FromDefault, bool ToDefault) {
734	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
735	FlatTree[CurrentNode].Kind = Declaration;
736	FlatTree[CurrentNode].FromArgInfo.VD = FromValueDecl;
737	FlatTree[CurrentNode].ToArgInfo.VD = ToValueDecl;
738	FlatTree[CurrentNode].FromArgInfo.NeedAddressOf = FromAddressOf;
739	FlatTree[CurrentNode].ToArgInfo.NeedAddressOf = ToAddressOf;
740	FlatTree[CurrentNode].FromArgInfo.IsNullPtr = FromNullPtr;
741	FlatTree[CurrentNode].ToArgInfo.IsNullPtr = ToNullPtr;
742	FlatTree[CurrentNode].FromArgInfo.ArgExpr = FromExpr;
743	FlatTree[CurrentNode].ToArgInfo.ArgExpr = ToExpr;
744	SetDefault(FromDefault, ToDefault);
745	}
746
747	void SetFromDeclarationAndToIntegerDiff(
748	ValueDecl *FromValueDecl, bool FromAddressOf, bool FromNullPtr,
749	Expr *FromExpr, const llvm::APSInt &ToInt, bool IsValidToInt,
750	QualType ToIntType, Expr *ToExpr, bool FromDefault, bool ToDefault) {
751	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
752	FlatTree[CurrentNode].Kind = FromDeclarationAndToInteger;
753	FlatTree[CurrentNode].FromArgInfo.VD = FromValueDecl;
754	FlatTree[CurrentNode].FromArgInfo.NeedAddressOf = FromAddressOf;
755	FlatTree[CurrentNode].FromArgInfo.IsNullPtr = FromNullPtr;
756	FlatTree[CurrentNode].FromArgInfo.ArgExpr = FromExpr;
757	FlatTree[CurrentNode].ToArgInfo.Val = ToInt;
758	FlatTree[CurrentNode].ToArgInfo.IsValidInt = IsValidToInt;
759	FlatTree[CurrentNode].ToArgInfo.ArgType = ToIntType;
760	FlatTree[CurrentNode].ToArgInfo.ArgExpr = ToExpr;
761	SetDefault(FromDefault, ToDefault);
762	}
763
764	void SetFromIntegerAndToDeclarationDiff(
765	const llvm::APSInt &FromInt, bool IsValidFromInt, QualType FromIntType,
766	Expr *FromExpr, ValueDecl *ToValueDecl, bool ToAddressOf,
767	bool ToNullPtr, Expr *ToExpr, bool FromDefault, bool ToDefault) {
768	assert(FlatTree[CurrentNode].Kind == Invalid && "Node is not empty.");
769	FlatTree[CurrentNode].Kind = FromIntegerAndToDeclaration;
770	FlatTree[CurrentNode].FromArgInfo.Val = FromInt;
771	FlatTree[CurrentNode].FromArgInfo.IsValidInt = IsValidFromInt;
772	FlatTree[CurrentNode].FromArgInfo.ArgType = FromIntType;
773	FlatTree[CurrentNode].FromArgInfo.ArgExpr = FromExpr;
774	FlatTree[CurrentNode].ToArgInfo.VD = ToValueDecl;
775	FlatTree[CurrentNode].ToArgInfo.NeedAddressOf = ToAddressOf;
776	FlatTree[CurrentNode].ToArgInfo.IsNullPtr = ToNullPtr;
777	FlatTree[CurrentNode].ToArgInfo.ArgExpr = ToExpr;
778	SetDefault(FromDefault, ToDefault);
779	}
780
781	/// SetDefault - Sets FromDefault and ToDefault flags of the current node.
782	void SetDefault(bool FromDefault, bool ToDefault) {
783	assert((!FromDefault || !ToDefault) && "Both arguments cannot be default.");
784	FlatTree[CurrentNode].FromArgInfo.IsDefault = FromDefault;
785	FlatTree[CurrentNode].ToArgInfo.IsDefault = ToDefault;
786	}
787
788	/// SetSame - Sets the same flag of the current node.
789	void SetSame(bool Same) {
790	FlatTree[CurrentNode].Same = Same;
791	}
792
793	/// SetKind - Sets the current node's type.
794	void SetKind(DiffKind Kind) {
795	FlatTree[CurrentNode].Kind = Kind;
796	}
797
798	/// Up - Changes the node to the parent of the current node.
799	void Up() {
800	assert(FlatTree[CurrentNode].Kind != Invalid &&
801	"Cannot exit node before setting node information.");
802	CurrentNode = FlatTree[CurrentNode].ParentNode;
803	}
804
805	/// AddNode - Adds a child node to the current node, then sets that
806	/// node as the current node.
807	void AddNode() {
808	assert(FlatTree[CurrentNode].Kind == Template &&
809	"Only Template nodes can have children nodes.");
810	FlatTree.push_back(Elt: DiffNode(CurrentNode));
811	DiffNode &Node = FlatTree[CurrentNode];
812	if (Node.ChildNode == 0) {
813	// If a child node doesn't exist, add one.
814	Node.ChildNode = NextFreeNode;
815	} else {
816	// If a child node exists, find the last child node and add a
817	// next node to it.
818	unsigned i;
819	for (i = Node.ChildNode; FlatTree[i].NextNode != 0;
820	i = FlatTree[i].NextNode) {
821	}
822	FlatTree[i].NextNode = NextFreeNode;
823	}
824	CurrentNode = NextFreeNode;
825	++NextFreeNode;
826	}
827
828	// Node reading functions.
829	/// StartTraverse - Prepares the tree for recursive traversal.
830	void StartTraverse() {
831	ReadNode = 0;
832	CurrentNode = NextFreeNode;
833	NextFreeNode = 0;
834	}
835
836	/// Parent - Move the current read node to its parent.
837	void Parent() {
838	ReadNode = FlatTree[ReadNode].ParentNode;
839	}
840
841	void GetTemplateDiff(TemplateDecl *&FromTD, TemplateDecl *&ToTD,
842	Qualifiers &FromQual, Qualifiers &ToQual) {
843	assert(FlatTree[ReadNode].Kind == Template && "Unexpected kind.");
844	FromTD = FlatTree[ReadNode].FromArgInfo.TD;
845	ToTD = FlatTree[ReadNode].ToArgInfo.TD;
846	FromQual = FlatTree[ReadNode].FromArgInfo.Qual;
847	ToQual = FlatTree[ReadNode].ToArgInfo.Qual;
848	}
849
850	void GetTypeDiff(QualType &FromType, QualType &ToType) {
851	assert(FlatTree[ReadNode].Kind == Type && "Unexpected kind");
852	FromType = FlatTree[ReadNode].FromArgInfo.ArgType;
853	ToType = FlatTree[ReadNode].ToArgInfo.ArgType;
854	}
855
856	void GetExpressionDiff(Expr *&FromExpr, Expr *&ToExpr) {
857	assert(FlatTree[ReadNode].Kind == Expression && "Unexpected kind");
858	FromExpr = FlatTree[ReadNode].FromArgInfo.ArgExpr;
859	ToExpr = FlatTree[ReadNode].ToArgInfo.ArgExpr;
860	}
861
862	void GetTemplateTemplateDiff(TemplateDecl *&FromTD, TemplateDecl *&ToTD) {
863	assert(FlatTree[ReadNode].Kind == TemplateTemplate && "Unexpected kind.");
864	FromTD = FlatTree[ReadNode].FromArgInfo.TD;
865	ToTD = FlatTree[ReadNode].ToArgInfo.TD;
866	}
867
868	void GetIntegerDiff(llvm::APSInt &FromInt, llvm::APSInt &ToInt,
869	bool &IsValidFromInt, bool &IsValidToInt,
870	QualType &FromIntType, QualType &ToIntType,
871	Expr *&FromExpr, Expr *&ToExpr) {
872	assert(FlatTree[ReadNode].Kind == Integer && "Unexpected kind.");
873	FromInt = FlatTree[ReadNode].FromArgInfo.Val;
874	ToInt = FlatTree[ReadNode].ToArgInfo.Val;
875	IsValidFromInt = FlatTree[ReadNode].FromArgInfo.IsValidInt;
876	IsValidToInt = FlatTree[ReadNode].ToArgInfo.IsValidInt;
877	FromIntType = FlatTree[ReadNode].FromArgInfo.ArgType;
878	ToIntType = FlatTree[ReadNode].ToArgInfo.ArgType;
879	FromExpr = FlatTree[ReadNode].FromArgInfo.ArgExpr;
880	ToExpr = FlatTree[ReadNode].ToArgInfo.ArgExpr;
881	}
882
883	void GetDeclarationDiff(ValueDecl *&FromValueDecl, ValueDecl *&ToValueDecl,
884	bool &FromAddressOf, bool &ToAddressOf,
885	bool &FromNullPtr, bool &ToNullPtr, Expr *&FromExpr,
886	Expr *&ToExpr) {
887	assert(FlatTree[ReadNode].Kind == Declaration && "Unexpected kind.");
888	FromValueDecl = FlatTree[ReadNode].FromArgInfo.VD;
889	ToValueDecl = FlatTree[ReadNode].ToArgInfo.VD;
890	FromAddressOf = FlatTree[ReadNode].FromArgInfo.NeedAddressOf;
891	ToAddressOf = FlatTree[ReadNode].ToArgInfo.NeedAddressOf;
892	FromNullPtr = FlatTree[ReadNode].FromArgInfo.IsNullPtr;
893	ToNullPtr = FlatTree[ReadNode].ToArgInfo.IsNullPtr;
894	FromExpr = FlatTree[ReadNode].FromArgInfo.ArgExpr;
895	ToExpr = FlatTree[ReadNode].ToArgInfo.ArgExpr;
896	}
897
898	void GetFromDeclarationAndToIntegerDiff(
899	ValueDecl *&FromValueDecl, bool &FromAddressOf, bool &FromNullPtr,
900	Expr *&FromExpr, llvm::APSInt &ToInt, bool &IsValidToInt,
901	QualType &ToIntType, Expr *&ToExpr) {
902	assert(FlatTree[ReadNode].Kind == FromDeclarationAndToInteger &&
903	"Unexpected kind.");
904	FromValueDecl = FlatTree[ReadNode].FromArgInfo.VD;
905	FromAddressOf = FlatTree[ReadNode].FromArgInfo.NeedAddressOf;
906	FromNullPtr = FlatTree[ReadNode].FromArgInfo.IsNullPtr;
907	FromExpr = FlatTree[ReadNode].FromArgInfo.ArgExpr;
908	ToInt = FlatTree[ReadNode].ToArgInfo.Val;
909	IsValidToInt = FlatTree[ReadNode].ToArgInfo.IsValidInt;
910	ToIntType = FlatTree[ReadNode].ToArgInfo.ArgType;
911	ToExpr = FlatTree[ReadNode].ToArgInfo.ArgExpr;
912	}
913
914	void GetFromIntegerAndToDeclarationDiff(
915	llvm::APSInt &FromInt, bool &IsValidFromInt, QualType &FromIntType,
916	Expr *&FromExpr, ValueDecl *&ToValueDecl, bool &ToAddressOf,
917	bool &ToNullPtr, Expr *&ToExpr) {
918	assert(FlatTree[ReadNode].Kind == FromIntegerAndToDeclaration &&
919	"Unexpected kind.");
920	FromInt = FlatTree[ReadNode].FromArgInfo.Val;
921	IsValidFromInt = FlatTree[ReadNode].FromArgInfo.IsValidInt;
922	FromIntType = FlatTree[ReadNode].FromArgInfo.ArgType;
923	FromExpr = FlatTree[ReadNode].FromArgInfo.ArgExpr;
924	ToValueDecl = FlatTree[ReadNode].ToArgInfo.VD;
925	ToAddressOf = FlatTree[ReadNode].ToArgInfo.NeedAddressOf;
926	ToNullPtr = FlatTree[ReadNode].ToArgInfo.IsNullPtr;
927	ToExpr = FlatTree[ReadNode].ToArgInfo.ArgExpr;
928	}
929
930	/// FromDefault - Return true if the from argument is the default.
931	bool FromDefault() {
932	return FlatTree[ReadNode].FromArgInfo.IsDefault;
933	}
934
935	/// ToDefault - Return true if the to argument is the default.
936	bool ToDefault() {
937	return FlatTree[ReadNode].ToArgInfo.IsDefault;
938	}
939
940	/// NodeIsSame - Returns true if the arguments are the same.
941	bool NodeIsSame() {
942	return FlatTree[ReadNode].Same;
943	}
944
945	/// HasChildren - Returns true if the node has children.
946	bool HasChildren() {
947	return FlatTree[ReadNode].ChildNode != 0;
948	}
949
950	/// MoveToChild - Moves from the current node to its child.
951	void MoveToChild() {
952	ReadNode = FlatTree[ReadNode].ChildNode;
953	}
954
955	/// AdvanceSibling - If there is a next sibling, advance to it and return
956	/// true. Otherwise, return false.
957	bool AdvanceSibling() {
958	if (FlatTree[ReadNode].NextNode == 0)
959	return false;
960
961	ReadNode = FlatTree[ReadNode].NextNode;
962	return true;
963	}
964
965	/// HasNextSibling - Return true if the node has a next sibling.
966	bool HasNextSibling() {
967	return FlatTree[ReadNode].NextNode != 0;
968	}
969
970	/// Empty - Returns true if the tree has no information.
971	bool Empty() {
972	return GetKind() == Invalid;
973	}
974
975	/// GetKind - Returns the current node's type.
976	DiffKind GetKind() {
977	return FlatTree[ReadNode].Kind;
978	}
979	};
980
981	DiffTree Tree;
982
983	/// TSTiterator - a pair of iterators that walks the
984	/// TemplateSpecializationType and the desugared TemplateSpecializationType.
985	/// The desugared TemplateArgument should provide the canonical argument
986	/// for comparisons.
987	class TSTiterator {
988	typedef const TemplateArgument& reference;
989	typedef const TemplateArgument* pointer;
990
991	/// InternalIterator - an iterator that is used to enter a
992	/// TemplateSpecializationType and read TemplateArguments inside template
993	/// parameter packs in order with the rest of the TemplateArguments.
994	struct InternalIterator {
995	/// TST - the template specialization whose arguments this iterator
996	/// traverses over.
997	const TemplateSpecializationType *TST;
998
999	/// Index - the index of the template argument in TST.
1000	unsigned Index;
1001
1002	/// CurrentTA - if CurrentTA is not the same as EndTA, then CurrentTA
1003	/// points to a TemplateArgument within a parameter pack.
1004	TemplateArgument::pack_iterator CurrentTA;
1005
1006	/// EndTA - the end iterator of a parameter pack
1007	TemplateArgument::pack_iterator EndTA;
1008
1009	/// InternalIterator - Constructs an iterator and sets it to the first
1010	/// template argument.
1011	InternalIterator(const TemplateSpecializationType *TST)
1012	: TST(TST), Index(0), CurrentTA(nullptr), EndTA(nullptr) {
1013	if (!TST) return;
1014
1015	if (isEnd()) return;
1016
1017	// Set to first template argument. If not a parameter pack, done.
1018	TemplateArgument TA = TST->template_arguments()[0];
1019	if (TA.getKind() != TemplateArgument::Pack) return;
1020
1021	// Start looking into the parameter pack.
1022	CurrentTA = TA.pack_begin();
1023	EndTA = TA.pack_end();
1024
1025	// Found a valid template argument.
1026	if (CurrentTA != EndTA) return;
1027
1028	// Parameter pack is empty, use the increment to get to a valid
1029	// template argument.
1030	++(*this);
1031	}
1032
1033	/// Return true if the iterator is non-singular.
1034	bool isValid() const { return TST; }
1035
1036	/// isEnd - Returns true if the iterator is one past the end.
1037	bool isEnd() const {
1038	assert(TST && "InternalIterator is invalid with a null TST.");
1039	return Index >= TST->template_arguments().size();
1040	}
1041
1042	/// &operator++ - Increment the iterator to the next template argument.
1043	InternalIterator &operator++() {
1044	assert(TST && "InternalIterator is invalid with a null TST.");
1045	if (isEnd()) {
1046	return *this;
1047	}
1048
1049	// If in a parameter pack, advance in the parameter pack.
1050	if (CurrentTA != EndTA) {
1051	++CurrentTA;
1052	if (CurrentTA != EndTA)
1053	return *this;
1054	}
1055
1056	// Loop until a template argument is found, or the end is reached.
1057	while (true) {
1058	// Advance to the next template argument. Break if reached the end.
1059	if (++Index == TST->template_arguments().size())
1060	break;
1061
1062	// If the TemplateArgument is not a parameter pack, done.
1063	TemplateArgument TA = TST->template_arguments()[Index];
1064	if (TA.getKind() != TemplateArgument::Pack)
1065	break;
1066
1067	// Handle parameter packs.
1068	CurrentTA = TA.pack_begin();
1069	EndTA = TA.pack_end();
1070
1071	// If the parameter pack is empty, try to advance again.
1072	if (CurrentTA != EndTA)
1073	break;
1074	}
1075	return *this;
1076	}
1077
1078	/// operator* - Returns the appropriate TemplateArgument.
1079	reference operator*() const {
1080	assert(TST && "InternalIterator is invalid with a null TST.");
1081	assert(!isEnd() && "Index exceeds number of arguments.");
1082	if (CurrentTA == EndTA)
1083	return TST->template_arguments()[Index];
1084	else
1085	return *CurrentTA;
1086	}
1087
1088	/// operator-> - Allow access to the underlying TemplateArgument.
1089	pointer operator->() const {
1090	assert(TST && "InternalIterator is invalid with a null TST.");
1091	return &operator*();
1092	}
1093	};
1094
1095	InternalIterator SugaredIterator;
1096	InternalIterator DesugaredIterator;
1097
1098	public:
1099	TSTiterator(ASTContext &Context, const TemplateSpecializationType *TST)
1100	: SugaredIterator(TST),
1101	DesugaredIterator(
1102	(TST->isSugared() && !TST->isTypeAlias())
1103	? GetTemplateSpecializationType(Context, Ty: TST->desugar())
1104	: nullptr) {}
1105
1106	/// &operator++ - Increment the iterator to the next template argument.
1107	TSTiterator &operator++() {
1108	++SugaredIterator;
1109	if (DesugaredIterator.isValid())
1110	++DesugaredIterator;
1111	return *this;
1112	}
1113
1114	/// operator* - Returns the appropriate TemplateArgument.
1115	reference operator*() const {
1116	return *SugaredIterator;
1117	}
1118
1119	/// operator-> - Allow access to the underlying TemplateArgument.
1120	pointer operator->() const {
1121	return &operator*();
1122	}
1123
1124	/// isEnd - Returns true if no more TemplateArguments are available.
1125	bool isEnd() const {
1126	return SugaredIterator.isEnd();
1127	}
1128
1129	/// hasDesugaredTA - Returns true if there is another TemplateArgument
1130	/// available.
1131	bool hasDesugaredTA() const {
1132	return DesugaredIterator.isValid() && !DesugaredIterator.isEnd();
1133	}
1134
1135	/// getDesugaredTA - Returns the desugared TemplateArgument.
1136	reference getDesugaredTA() const {
1137	assert(DesugaredIterator.isValid() &&
1138	"Desugared TemplateArgument should not be used.");
1139	return *DesugaredIterator;
1140	}
1141	};
1142
1143	// These functions build up the template diff tree, including functions to
1144	// retrieve and compare template arguments.
1145
1146	static const TemplateSpecializationType *
1147	GetTemplateSpecializationType(ASTContext &Context, QualType Ty) {
1148	if (const TemplateSpecializationType *TST =
1149	Ty->getAs<TemplateSpecializationType>())
1150	return TST;
1151
1152	if (const auto* SubstType = Ty->getAs<SubstTemplateTypeParmType>())
1153	Ty = SubstType->getReplacementType();
1154
1155	const RecordType *RT = Ty->getAs<RecordType>();
1156
1157	if (!RT)
1158	return nullptr;
1159
1160	const ClassTemplateSpecializationDecl *CTSD =
1161	dyn_cast<ClassTemplateSpecializationDecl>(Val: RT->getDecl());
1162
1163	if (!CTSD)
1164	return nullptr;
1165
1166	Ty = Context.getTemplateSpecializationType(
1167	T: TemplateName(CTSD->getSpecializedTemplate()),
1168	SpecifiedArgs: CTSD->getTemplateArgs().asArray(), /*CanonicalArgs=*/{},
1169	Underlying: Ty.getLocalUnqualifiedType().getCanonicalType());
1170
1171	return Ty->getAs<TemplateSpecializationType>();
1172	}
1173
1174	/// Returns true if the DiffType is Type and false for Template.
1175	static bool OnlyPerformTypeDiff(ASTContext &Context, QualType FromType,
1176	QualType ToType,
1177	const TemplateSpecializationType *&FromArgTST,
1178	const TemplateSpecializationType *&ToArgTST) {
1179	if (FromType.isNull() || ToType.isNull())
1180	return true;
1181
1182	if (Context.hasSameType(T1: FromType, T2: ToType))
1183	return true;
1184
1185	FromArgTST = GetTemplateSpecializationType(Context, Ty: FromType);
1186	ToArgTST = GetTemplateSpecializationType(Context, Ty: ToType);
1187
1188	if (!FromArgTST || !ToArgTST)
1189	return true;
1190
1191	if (!hasSameTemplate(Context, FromTST&: FromArgTST, ToTST&: ToArgTST))
1192	return true;
1193
1194	return false;
1195	}
1196
1197	/// DiffTypes - Fills a DiffNode with information about a type difference.
1198	void DiffTypes(const TSTiterator &FromIter, const TSTiterator &ToIter) {
1199	QualType FromType = GetType(Iter: FromIter);
1200	QualType ToType = GetType(Iter: ToIter);
1201
1202	bool FromDefault = FromIter.isEnd() && !FromType.isNull();
1203	bool ToDefault = ToIter.isEnd() && !ToType.isNull();
1204
1205	const TemplateSpecializationType *FromArgTST = nullptr;
1206	const TemplateSpecializationType *ToArgTST = nullptr;
1207	if (OnlyPerformTypeDiff(Context, FromType, ToType, FromArgTST, ToArgTST)) {
1208	Tree.SetTypeDiff(FromType, ToType, FromDefault, ToDefault);
1209	Tree.SetSame(!FromType.isNull() && !ToType.isNull() &&
1210	Context.hasSameType(T1: FromType, T2: ToType));
1211	} else {
1212	assert(FromArgTST && ToArgTST &&
1213	"Both template specializations need to be valid.");
1214	Qualifiers FromQual = FromType.getQualifiers(),
1215	ToQual = ToType.getQualifiers();
1216	FromQual -= QualType(FromArgTST, 0).getQualifiers();
1217	ToQual -= QualType(ToArgTST, 0).getQualifiers();
1218	Tree.SetTemplateDiff(FromTD: FromArgTST->getTemplateName().getAsTemplateDecl(),
1219	ToTD: ToArgTST->getTemplateName().getAsTemplateDecl(),
1220	FromQual, ToQual, FromDefault, ToDefault);
1221	DiffTemplate(FromTST: FromArgTST, ToTST: ToArgTST);
1222	}
1223	}
1224
1225	/// DiffTemplateTemplates - Fills a DiffNode with information about a
1226	/// template template difference.
1227	void DiffTemplateTemplates(const TSTiterator &FromIter,
1228	const TSTiterator &ToIter) {
1229	TemplateDecl *FromDecl = GetTemplateDecl(Iter: FromIter);
1230	TemplateDecl *ToDecl = GetTemplateDecl(Iter: ToIter);
1231	Tree.SetTemplateTemplateDiff(FromTD: FromDecl, ToTD: ToDecl, FromDefault: FromIter.isEnd() && FromDecl,
1232	ToDefault: ToIter.isEnd() && ToDecl);
1233	Tree.SetSame(FromDecl && ToDecl &&
1234	FromDecl->getCanonicalDecl() == ToDecl->getCanonicalDecl());
1235	}
1236
1237	/// InitializeNonTypeDiffVariables - Helper function for DiffNonTypes
1238	static void InitializeNonTypeDiffVariables(ASTContext &Context,
1239	const TSTiterator &Iter,
1240	NonTypeTemplateParmDecl *Default,
1241	llvm::APSInt &Value, bool &HasInt,
1242	QualType &IntType, bool &IsNullPtr,
1243	Expr *&E, ValueDecl *&VD,
1244	bool &NeedAddressOf) {
1245	if (!Iter.isEnd()) {
1246	switch (Iter->getKind()) {
1247	case TemplateArgument::StructuralValue:
1248	// FIXME: Diffing of structural values is not implemented.
1249	// There is no possible fallback in this case, this will show up
1250	// as '(no argument)'.
1251	return;
1252	case TemplateArgument::Integral:
1253	Value = Iter->getAsIntegral();
1254	HasInt = true;
1255	IntType = Iter->getIntegralType();
1256	return;
1257	case TemplateArgument::Declaration: {
1258	VD = Iter->getAsDecl();
1259	QualType ArgType = Iter->getParamTypeForDecl();
1260	QualType VDType = VD->getType();
1261	if (ArgType->isPointerType() &&
1262	Context.hasSameType(T1: ArgType->getPointeeType(), T2: VDType))
1263	NeedAddressOf = true;
1264	return;
1265	}
1266	case TemplateArgument::NullPtr:
1267	IsNullPtr = true;
1268	return;
1269	case TemplateArgument::Expression:
1270	E = Iter->getAsExpr();
1271	break;
1272	case TemplateArgument::Null:
1273	case TemplateArgument::Type:
1274	case TemplateArgument::Template:
1275	case TemplateArgument::TemplateExpansion:
1276	llvm_unreachable("TemplateArgument kind is not expected for NTTP");
1277	case TemplateArgument::Pack:
1278	llvm_unreachable("TemplateArgument kind should be handled elsewhere");
1279	}
1280	} else if (!Default->isParameterPack()) {
1281	E = Default->getDefaultArgument().getArgument().getAsExpr();
1282	}
1283
1284	if (!Iter.hasDesugaredTA())
1285	return;
1286
1287	const TemplateArgument &TA = Iter.getDesugaredTA();
1288	switch (TA.getKind()) {
1289	case TemplateArgument::StructuralValue:
1290	// FIXME: Diffing of structural values is not implemented.
1291	// Just fall back to the expression.
1292	return;
1293	case TemplateArgument::Integral:
1294	Value = TA.getAsIntegral();
1295	HasInt = true;
1296	IntType = TA.getIntegralType();
1297	return;
1298	case TemplateArgument::Declaration: {
1299	VD = TA.getAsDecl();
1300	QualType ArgType = TA.getParamTypeForDecl();
1301	QualType VDType = VD->getType();
1302	if (ArgType->isPointerType() &&
1303	Context.hasSameType(T1: ArgType->getPointeeType(), T2: VDType))
1304	NeedAddressOf = true;
1305	return;
1306	}
1307	case TemplateArgument::NullPtr:
1308	IsNullPtr = true;
1309	return;
1310	case TemplateArgument::Expression:
1311	// TODO: Sometimes, the desugared template argument Expr differs from
1312	// the sugared template argument Expr. It may be useful in the future
1313	// but for now, it is just discarded.
1314	if (!E)
1315	E = TA.getAsExpr();
1316	return;
1317	case TemplateArgument::Null:
1318	case TemplateArgument::Type:
1319	case TemplateArgument::Template:
1320	case TemplateArgument::TemplateExpansion:
1321	llvm_unreachable("TemplateArgument kind is not expected for NTTP");
1322	case TemplateArgument::Pack:
1323	llvm_unreachable("TemplateArgument kind should be handled elsewhere");
1324	}
1325	llvm_unreachable("Unexpected TemplateArgument kind");
1326	}
1327
1328	/// DiffNonTypes - Handles any template parameters not handled by DiffTypes
1329	/// of DiffTemplatesTemplates, such as integer and declaration parameters.
1330	void DiffNonTypes(const TSTiterator &FromIter, const TSTiterator &ToIter,
1331	NonTypeTemplateParmDecl *FromDefaultNonTypeDecl,
1332	NonTypeTemplateParmDecl *ToDefaultNonTypeDecl) {
1333	Expr *FromExpr = nullptr, *ToExpr = nullptr;
1334	llvm::APSInt FromInt, ToInt;
1335	QualType FromIntType, ToIntType;
1336	ValueDecl *FromValueDecl = nullptr, *ToValueDecl = nullptr;
1337	bool HasFromInt = false, HasToInt = false, FromNullPtr = false,
1338	ToNullPtr = false, NeedFromAddressOf = false, NeedToAddressOf = false;
1339	InitializeNonTypeDiffVariables(
1340	Context, Iter: FromIter, Default: FromDefaultNonTypeDecl, Value&: FromInt, HasInt&: HasFromInt,
1341	IntType&: FromIntType, IsNullPtr&: FromNullPtr, E&: FromExpr, VD&: FromValueDecl, NeedAddressOf&: NeedFromAddressOf);
1342	InitializeNonTypeDiffVariables(Context, Iter: ToIter, Default: ToDefaultNonTypeDecl, Value&: ToInt,
1343	HasInt&: HasToInt, IntType&: ToIntType, IsNullPtr&: ToNullPtr, E&: ToExpr,
1344	VD&: ToValueDecl, NeedAddressOf&: NeedToAddressOf);
1345
1346	bool FromDefault = FromIter.isEnd() &&
1347	(FromExpr || FromValueDecl || HasFromInt || FromNullPtr);
1348	bool ToDefault = ToIter.isEnd() &&
1349	(ToExpr || ToValueDecl || HasToInt || ToNullPtr);
1350
1351	bool FromDeclaration = FromValueDecl || FromNullPtr;
1352	bool ToDeclaration = ToValueDecl || ToNullPtr;
1353
1354	if (FromDeclaration && HasToInt) {
1355	Tree.SetFromDeclarationAndToIntegerDiff(
1356	FromValueDecl, FromAddressOf: NeedFromAddressOf, FromNullPtr, FromExpr, ToInt,
1357	IsValidToInt: HasToInt, ToIntType, ToExpr, FromDefault, ToDefault);
1358	Tree.SetSame(false);
1359	return;
1360
1361	}
1362
1363	if (HasFromInt && ToDeclaration) {
1364	Tree.SetFromIntegerAndToDeclarationDiff(
1365	FromInt, IsValidFromInt: HasFromInt, FromIntType, FromExpr, ToValueDecl,
1366	ToAddressOf: NeedToAddressOf, ToNullPtr, ToExpr, FromDefault, ToDefault);
1367	Tree.SetSame(false);
1368	return;
1369	}
1370
1371	if (HasFromInt || HasToInt) {
1372	Tree.SetIntegerDiff(FromInt, ToInt, IsValidFromInt: HasFromInt, IsValidToInt: HasToInt, FromIntType,
1373	ToIntType, FromExpr, ToExpr, FromDefault, ToDefault);
1374	if (HasFromInt && HasToInt) {
1375	Tree.SetSame(Context.hasSameType(T1: FromIntType, T2: ToIntType) &&
1376	FromInt == ToInt);
1377	}
1378	return;
1379	}
1380
1381	if (FromDeclaration || ToDeclaration) {
1382	Tree.SetDeclarationDiff(FromValueDecl, ToValueDecl, FromAddressOf: NeedFromAddressOf,
1383	ToAddressOf: NeedToAddressOf, FromNullPtr, ToNullPtr, FromExpr,
1384	ToExpr, FromDefault, ToDefault);
1385	bool BothNull = FromNullPtr && ToNullPtr;
1386	bool SameValueDecl =
1387	FromValueDecl && ToValueDecl &&
1388	NeedFromAddressOf == NeedToAddressOf &&
1389	FromValueDecl->getCanonicalDecl() == ToValueDecl->getCanonicalDecl();
1390	Tree.SetSame(BothNull || SameValueDecl);
1391	return;
1392	}
1393
1394	assert((FromExpr || ToExpr) && "Both template arguments cannot be empty.");
1395	Tree.SetExpressionDiff(FromExpr, ToExpr, FromDefault, ToDefault);
1396	Tree.SetSame(IsEqualExpr(Context, FromExpr, ToExpr));
1397	}
1398
1399	/// DiffTemplate - recursively visits template arguments and stores the
1400	/// argument info into a tree.
1401	void DiffTemplate(const TemplateSpecializationType *FromTST,
1402	const TemplateSpecializationType *ToTST) {
1403	// FIXME: With P3310R0, A TST formed from a DeducedTemplateName might
1404	// differ in template arguments which were not written.
1405	// Begin descent into diffing template tree.
1406	TemplateParameterList *ParamsFrom =
1407	FromTST->getTemplateName()
1408	.getAsTemplateDecl(/*IgnoreDeduced=*/true)
1409	->getTemplateParameters();
1410	TemplateParameterList *ParamsTo =
1411	ToTST->getTemplateName()
1412	.getAsTemplateDecl(/*IgnoreDeduced=*/true)
1413	->getTemplateParameters();
1414	unsigned TotalArgs = 0;
1415	for (TSTiterator FromIter(Context, FromTST), ToIter(Context, ToTST);
1416	!FromIter.isEnd() || !ToIter.isEnd(); ++TotalArgs) {
1417	Tree.AddNode();
1418
1419	// Get the parameter at index TotalArgs. If index is larger
1420	// than the total number of parameters, then there is an
1421	// argument pack, so re-use the last parameter.
1422	unsigned FromParamIndex = std::min(a: TotalArgs, b: ParamsFrom->size() - 1);
1423	unsigned ToParamIndex = std::min(a: TotalArgs, b: ParamsTo->size() - 1);
1424	NamedDecl *FromParamND = ParamsFrom->getParam(Idx: FromParamIndex);
1425	NamedDecl *ToParamND = ParamsTo->getParam(Idx: ToParamIndex);
1426
1427	assert(FromParamND->getKind() == ToParamND->getKind() &&
1428	"Parameter Decl are not the same kind.");
1429
1430	if (isa<TemplateTypeParmDecl>(Val: FromParamND)) {
1431	DiffTypes(FromIter, ToIter);
1432	} else if (isa<TemplateTemplateParmDecl>(Val: FromParamND)) {
1433	DiffTemplateTemplates(FromIter, ToIter);
1434	} else if (isa<NonTypeTemplateParmDecl>(Val: FromParamND)) {
1435	NonTypeTemplateParmDecl *FromDefaultNonTypeDecl =
1436	cast<NonTypeTemplateParmDecl>(Val: FromParamND);
1437	NonTypeTemplateParmDecl *ToDefaultNonTypeDecl =
1438	cast<NonTypeTemplateParmDecl>(Val: ToParamND);
1439	DiffNonTypes(FromIter, ToIter, FromDefaultNonTypeDecl,
1440	ToDefaultNonTypeDecl);
1441	} else {
1442	llvm_unreachable("Unexpected Decl type.");
1443	}
1444
1445	++FromIter;
1446	++ToIter;
1447	Tree.Up();
1448	}
1449	}
1450
1451	/// makeTemplateList - Dump every template alias into the vector.
1452	static void makeTemplateList(
1453	SmallVectorImpl<const TemplateSpecializationType *> &TemplateList,
1454	const TemplateSpecializationType *TST) {
1455	while (TST) {
1456	TemplateList.push_back(Elt: TST);
1457	if (!TST->isTypeAlias())
1458	return;
1459	TST = TST->getAliasedType()->getAs<TemplateSpecializationType>();
1460	}
1461	}
1462
1463	/// hasSameBaseTemplate - Returns true when the base templates are the same,
1464	/// even if the template arguments are not.
1465	static bool hasSameBaseTemplate(ASTContext &Context,
1466	const TemplateSpecializationType *FromTST,
1467	const TemplateSpecializationType *ToTST) {
1468	return Context.getCanonicalTemplateName(Name: FromTST->getTemplateName(),
1469	/*IgnoreDeduced=*/true) ==
1470	Context.getCanonicalTemplateName(Name: ToTST->getTemplateName(),
1471	/*IgnoreDeduced=*/true);
1472	}
1473
1474	/// hasSameTemplate - Returns true if both types are specialized from the
1475	/// same template declaration. If they come from different template aliases,
1476	/// do a parallel ascension search to determine the highest template alias in
1477	/// common and set the arguments to them.
1478	static bool hasSameTemplate(ASTContext &Context,
1479	const TemplateSpecializationType *&FromTST,
1480	const TemplateSpecializationType *&ToTST) {
1481	// Check the top templates if they are the same.
1482	if (hasSameBaseTemplate(Context, FromTST, ToTST))
1483	return true;
1484
1485	// Create vectors of template aliases.
1486	SmallVector<const TemplateSpecializationType*, 1> FromTemplateList,
1487	ToTemplateList;
1488
1489	makeTemplateList(TemplateList&: FromTemplateList, TST: FromTST);
1490	makeTemplateList(TemplateList&: ToTemplateList, TST: ToTST);
1491
1492	SmallVectorImpl<const TemplateSpecializationType *>::reverse_iterator
1493	FromIter = FromTemplateList.rbegin(), FromEnd = FromTemplateList.rend(),
1494	ToIter = ToTemplateList.rbegin(), ToEnd = ToTemplateList.rend();
1495
1496	// Check if the lowest template types are the same. If not, return.
1497	if (!hasSameBaseTemplate(Context, FromTST: *FromIter, ToTST: *ToIter))
1498	return false;
1499
1500	// Begin searching up the template aliases. The bottom most template
1501	// matches so move up until one pair does not match. Use the template
1502	// right before that one.
1503	for (; FromIter != FromEnd && ToIter != ToEnd; ++FromIter, ++ToIter) {
1504	if (!hasSameBaseTemplate(Context, FromTST: *FromIter, ToTST: *ToIter))
1505	break;
1506	}
1507
1508	FromTST = FromIter[-1];
1509	ToTST = ToIter[-1];
1510
1511	return true;
1512	}
1513
1514	/// GetType - Retrieves the template type arguments, including default
1515	/// arguments.
1516	static QualType GetType(const TSTiterator &Iter) {
1517	if (!Iter.isEnd())
1518	return Iter->getAsType();
1519	if (Iter.hasDesugaredTA())
1520	return Iter.getDesugaredTA().getAsType();
1521	return QualType();
1522	}
1523
1524	/// GetTemplateDecl - Retrieves the template template arguments, including
1525	/// default arguments.
1526	static TemplateDecl *GetTemplateDecl(const TSTiterator &Iter) {
1527	if (!Iter.isEnd())
1528	return Iter->getAsTemplate().getAsTemplateDecl();
1529	if (Iter.hasDesugaredTA())
1530	return Iter.getDesugaredTA().getAsTemplate().getAsTemplateDecl();
1531	return nullptr;
1532	}
1533
1534	/// IsEqualExpr - Returns true if the expressions are the same in regards to
1535	/// template arguments. These expressions are dependent, so profile them
1536	/// instead of trying to evaluate them.
1537	static bool IsEqualExpr(ASTContext &Context, Expr *FromExpr, Expr *ToExpr) {
1538	if (FromExpr == ToExpr)
1539	return true;
1540
1541	if (!FromExpr || !ToExpr)
1542	return false;
1543
1544	llvm::FoldingSetNodeID FromID, ToID;
1545	FromExpr->Profile(ID&: FromID, Context, Canonical: true);
1546	ToExpr->Profile(ID&: ToID, Context, Canonical: true);
1547	return FromID == ToID;
1548	}
1549
1550	// These functions converts the tree representation of the template
1551	// differences into the internal character vector.
1552
1553	/// TreeToString - Converts the Tree object into a character stream which
1554	/// will later be turned into the output string.
1555	void TreeToString(int Indent = 1) {
1556	if (PrintTree) {
1557	OS << '\n';
1558	OS.indent(NumSpaces: 2 * Indent);
1559	++Indent;
1560	}
1561
1562	// Handle cases where the difference is not templates with different
1563	// arguments.
1564	switch (Tree.GetKind()) {
1565	case DiffTree::Invalid:
1566	llvm_unreachable("Template diffing failed with bad DiffNode");
1567	case DiffTree::Type: {
1568	QualType FromType, ToType;
1569	Tree.GetTypeDiff(FromType, ToType);
1570	PrintTypeNames(FromType, ToType, FromDefault: Tree.FromDefault(), ToDefault: Tree.ToDefault(),
1571	Same: Tree.NodeIsSame());
1572	return;
1573	}
1574	case DiffTree::Expression: {
1575	Expr *FromExpr, *ToExpr;
1576	Tree.GetExpressionDiff(FromExpr, ToExpr);
1577	PrintExpr(FromExpr, ToExpr, FromDefault: Tree.FromDefault(), ToDefault: Tree.ToDefault(),
1578	Same: Tree.NodeIsSame());
1579	return;
1580	}
1581	case DiffTree::TemplateTemplate: {
1582	TemplateDecl *FromTD, *ToTD;
1583	Tree.GetTemplateTemplateDiff(FromTD, ToTD);
1584	PrintTemplateTemplate(FromTD, ToTD, FromDefault: Tree.FromDefault(),
1585	ToDefault: Tree.ToDefault(), Same: Tree.NodeIsSame());
1586	return;
1587	}
1588	case DiffTree::Integer: {
1589	llvm::APSInt FromInt, ToInt;
1590	Expr *FromExpr, *ToExpr;
1591	bool IsValidFromInt, IsValidToInt;
1592	QualType FromIntType, ToIntType;
1593	Tree.GetIntegerDiff(FromInt, ToInt, IsValidFromInt, IsValidToInt,
1594	FromIntType, ToIntType, FromExpr, ToExpr);
1595	PrintAPSInt(FromInt, ToInt, IsValidFromInt, IsValidToInt, FromIntType,
1596	ToIntType, FromExpr, ToExpr, FromDefault: Tree.FromDefault(),
1597	ToDefault: Tree.ToDefault(), Same: Tree.NodeIsSame());
1598	return;
1599	}
1600	case DiffTree::Declaration: {
1601	ValueDecl *FromValueDecl, *ToValueDecl;
1602	bool FromAddressOf, ToAddressOf;
1603	bool FromNullPtr, ToNullPtr;
1604	Expr *FromExpr, *ToExpr;
1605	Tree.GetDeclarationDiff(FromValueDecl, ToValueDecl, FromAddressOf,
1606	ToAddressOf, FromNullPtr, ToNullPtr, FromExpr,
1607	ToExpr);
1608	PrintValueDecl(FromValueDecl, ToValueDecl, FromAddressOf, ToAddressOf,
1609	FromNullPtr, ToNullPtr, FromExpr, ToExpr,
1610	FromDefault: Tree.FromDefault(), ToDefault: Tree.ToDefault(), Same: Tree.NodeIsSame());
1611	return;
1612	}
1613	case DiffTree::FromDeclarationAndToInteger: {
1614	ValueDecl *FromValueDecl;
1615	bool FromAddressOf;
1616	bool FromNullPtr;
1617	Expr *FromExpr;
1618	llvm::APSInt ToInt;
1619	bool IsValidToInt;
1620	QualType ToIntType;
1621	Expr *ToExpr;
1622	Tree.GetFromDeclarationAndToIntegerDiff(
1623	FromValueDecl, FromAddressOf, FromNullPtr, FromExpr, ToInt,
1624	IsValidToInt, ToIntType, ToExpr);
1625	assert((FromValueDecl || FromNullPtr) && IsValidToInt);
1626	PrintValueDeclAndInteger(VD: FromValueDecl, NeedAddressOf: FromAddressOf, IsNullPtr: FromNullPtr,
1627	VDExpr: FromExpr, DefaultDecl: Tree.FromDefault(), Val: ToInt, IntType: ToIntType,
1628	IntExpr: ToExpr, DefaultInt: Tree.ToDefault());
1629	return;
1630	}
1631	case DiffTree::FromIntegerAndToDeclaration: {
1632	llvm::APSInt FromInt;
1633	bool IsValidFromInt;
1634	QualType FromIntType;
1635	Expr *FromExpr;
1636	ValueDecl *ToValueDecl;
1637	bool ToAddressOf;
1638	bool ToNullPtr;
1639	Expr *ToExpr;
1640	Tree.GetFromIntegerAndToDeclarationDiff(
1641	FromInt, IsValidFromInt, FromIntType, FromExpr, ToValueDecl,
1642	ToAddressOf, ToNullPtr, ToExpr);
1643	assert(IsValidFromInt && (ToValueDecl || ToNullPtr));
1644	PrintIntegerAndValueDecl(Val: FromInt, IntType: FromIntType, IntExpr: FromExpr,
1645	DefaultInt: Tree.FromDefault(), VD: ToValueDecl, NeedAddressOf: ToAddressOf,
1646	IsNullPtr: ToNullPtr, VDExpr: ToExpr, DefaultDecl: Tree.ToDefault());
1647	return;
1648	}
1649	case DiffTree::Template: {
1650	// Node is root of template. Recurse on children.
1651	TemplateDecl *FromTD, *ToTD;
1652	Qualifiers FromQual, ToQual;
1653	Tree.GetTemplateDiff(FromTD, ToTD, FromQual, ToQual);
1654
1655	PrintQualifiers(FromQual, ToQual);
1656
1657	if (!Tree.HasChildren()) {
1658	// If we're dealing with a template specialization with zero
1659	// arguments, there are no children; special-case this.
1660	OS << FromTD->getDeclName() << "<>";
1661	return;
1662	}
1663
1664	OS << FromTD->getDeclName() << '<';
1665	Tree.MoveToChild();
1666	unsigned NumElideArgs = 0;
1667	bool AllArgsElided = true;
1668	do {
1669	if (ElideType) {
1670	if (Tree.NodeIsSame()) {
1671	++NumElideArgs;
1672	continue;
1673	}
1674	AllArgsElided = false;
1675	if (NumElideArgs > 0) {
1676	PrintElideArgs(NumElideArgs, Indent);
1677	NumElideArgs = 0;
1678	OS << ", ";
1679	}
1680	}
1681	TreeToString(Indent);
1682	if (Tree.HasNextSibling())
1683	OS << ", ";
1684	} while (Tree.AdvanceSibling());
1685	if (NumElideArgs > 0) {
1686	if (AllArgsElided)
1687	OS << "...";
1688	else
1689	PrintElideArgs(NumElideArgs, Indent);
1690	}
1691
1692	Tree.Parent();
1693	OS << ">";
1694	return;
1695	}
1696	}
1697	}
1698
1699	// To signal to the text printer that a certain text needs to be bolded,
1700	// a special character is injected into the character stream which the
1701	// text printer will later strip out.
1702
1703	/// Bold - Start bolding text.
1704	void Bold() {
1705	assert(!IsBold && "Attempting to bold text that is already bold.");
1706	IsBold = true;
1707	if (ShowColor)
1708	OS << ToggleHighlight;
1709	}
1710
1711	/// Unbold - Stop bolding text.
1712	void Unbold() {
1713	assert(IsBold && "Attempting to remove bold from unbold text.");
1714	IsBold = false;
1715	if (ShowColor)
1716	OS << ToggleHighlight;
1717	}
1718
1719	// Functions to print out the arguments and highlighting the difference.
1720
1721	/// PrintTypeNames - prints the typenames, bolding differences. Will detect
1722	/// typenames that are the same and attempt to disambiguate them by using
1723	/// canonical typenames.
1724	void PrintTypeNames(QualType FromType, QualType ToType,
1725	bool FromDefault, bool ToDefault, bool Same) {
1726	assert((!FromType.isNull() || !ToType.isNull()) &&
1727	"Only one template argument may be missing.");
1728
1729	if (Same) {
1730	OS << FromType.getAsString(Policy);
1731	return;
1732	}
1733
1734	if (!FromType.isNull() && !ToType.isNull() &&
1735	FromType.getLocalUnqualifiedType() ==
1736	ToType.getLocalUnqualifiedType()) {
1737	Qualifiers FromQual = FromType.getLocalQualifiers(),
1738	ToQual = ToType.getLocalQualifiers();
1739	PrintQualifiers(FromQual, ToQual);
1740	FromType.getLocalUnqualifiedType().print(OS, Policy);
1741	return;
1742	}
1743
1744	std::string FromTypeStr = FromType.isNull() ? "(no argument)"
1745	: FromType.getAsString(Policy);
1746	std::string ToTypeStr = ToType.isNull() ? "(no argument)"
1747	: ToType.getAsString(Policy);
1748	// Print without ElaboratedType sugar if it is better.
1749	// TODO: merge this with other aka printing above.
1750	if (FromTypeStr == ToTypeStr) {
1751	const auto *FromElTy = dyn_cast<ElaboratedType>(Val&: FromType),
1752	*ToElTy = dyn_cast<ElaboratedType>(Val&: ToType);
1753	if (FromElTy || ToElTy) {
1754	std::string FromNamedTypeStr =
1755	FromElTy ? FromElTy->getNamedType().getAsString(Policy)
1756	: FromTypeStr;
1757	std::string ToNamedTypeStr =
1758	ToElTy ? ToElTy->getNamedType().getAsString(Policy) : ToTypeStr;
1759	if (FromNamedTypeStr != ToNamedTypeStr) {
1760	FromTypeStr = FromNamedTypeStr;
1761	ToTypeStr = ToNamedTypeStr;
1762	goto PrintTypes;
1763	}
1764	}
1765	// Switch to canonical typename if it is better.
1766	std::string FromCanTypeStr =
1767	FromType.getCanonicalType().getAsString(Policy);
1768	std::string ToCanTypeStr = ToType.getCanonicalType().getAsString(Policy);
1769	if (FromCanTypeStr != ToCanTypeStr) {
1770	FromTypeStr = FromCanTypeStr;
1771	ToTypeStr = ToCanTypeStr;
1772	}
1773	}
1774
1775	PrintTypes:
1776	if (PrintTree) OS << '[';
1777	OS << (FromDefault ? "(default) " : "");
1778	Bold();
1779	OS << FromTypeStr;
1780	Unbold();
1781	if (PrintTree) {
1782	OS << " != " << (ToDefault ? "(default) " : "");
1783	Bold();
1784	OS << ToTypeStr;
1785	Unbold();
1786	OS << "]";
1787	}
1788	}
1789
1790	/// PrintExpr - Prints out the expr template arguments, highlighting argument
1791	/// differences.
1792	void PrintExpr(const Expr *FromExpr, const Expr *ToExpr, bool FromDefault,
1793	bool ToDefault, bool Same) {
1794	assert((FromExpr || ToExpr) &&
1795	"Only one template argument may be missing.");
1796	if (Same) {
1797	PrintExpr(E: FromExpr);
1798	} else if (!PrintTree) {
1799	OS << (FromDefault ? "(default) " : "");
1800	Bold();
1801	PrintExpr(E: FromExpr);
1802	Unbold();
1803	} else {
1804	OS << (FromDefault ? "[(default) " : "[");
1805	Bold();
1806	PrintExpr(E: FromExpr);
1807	Unbold();
1808	OS << " != " << (ToDefault ? "(default) " : "");
1809	Bold();
1810	PrintExpr(E: ToExpr);
1811	Unbold();
1812	OS << ']';
1813	}
1814	}
1815
1816	/// PrintExpr - Actual formatting and printing of expressions.
1817	void PrintExpr(const Expr *E) {
1818	if (E) {
1819	E->printPretty(OS, Helper: nullptr, Policy);
1820	return;
1821	}
1822	OS << "(no argument)";
1823	}
1824
1825	/// PrintTemplateTemplate - Handles printing of template template arguments,
1826	/// highlighting argument differences.
1827	void PrintTemplateTemplate(TemplateDecl *FromTD, TemplateDecl *ToTD,
1828	bool FromDefault, bool ToDefault, bool Same) {
1829	assert((FromTD || ToTD) && "Only one template argument may be missing.");
1830
1831	std::string FromName =
1832	std::string(FromTD ? FromTD->getName() : "(no argument)");
1833	std::string ToName = std::string(ToTD ? ToTD->getName() : "(no argument)");
1834	if (FromTD && ToTD && FromName == ToName) {
1835	FromName = FromTD->getQualifiedNameAsString();
1836	ToName = ToTD->getQualifiedNameAsString();
1837	}
1838
1839	if (Same) {
1840	OS << "template " << FromTD->getDeclName();
1841	} else if (!PrintTree) {
1842	OS << (FromDefault ? "(default) template " : "template ");
1843	Bold();
1844	OS << FromName;
1845	Unbold();
1846	} else {
1847	OS << (FromDefault ? "[(default) template " : "[template ");
1848	Bold();
1849	OS << FromName;
1850	Unbold();
1851	OS << " != " << (ToDefault ? "(default) template " : "template ");
1852	Bold();
1853	OS << ToName;
1854	Unbold();
1855	OS << ']';
1856	}
1857	}
1858
1859	/// PrintAPSInt - Handles printing of integral arguments, highlighting
1860	/// argument differences.
1861	void PrintAPSInt(const llvm::APSInt &FromInt, const llvm::APSInt &ToInt,
1862	bool IsValidFromInt, bool IsValidToInt, QualType FromIntType,
1863	QualType ToIntType, Expr *FromExpr, Expr *ToExpr,
1864	bool FromDefault, bool ToDefault, bool Same) {
1865	assert((IsValidFromInt || IsValidToInt) &&
1866	"Only one integral argument may be missing.");
1867
1868	if (Same) {
1869	if (FromIntType->isBooleanType()) {
1870	OS << ((FromInt == 0) ? "false" : "true");
1871	} else {
1872	OS << toString(I: FromInt, Radix: 10);
1873	}
1874	return;
1875	}
1876
1877	bool PrintType = IsValidFromInt && IsValidToInt &&
1878	!Context.hasSameType(T1: FromIntType, T2: ToIntType);
1879
1880	if (!PrintTree) {
1881	OS << (FromDefault ? "(default) " : "");
1882	PrintAPSInt(Val: FromInt, E: FromExpr, Valid: IsValidFromInt, IntType: FromIntType, PrintType);
1883	} else {
1884	OS << (FromDefault ? "[(default) " : "[");
1885	PrintAPSInt(Val: FromInt, E: FromExpr, Valid: IsValidFromInt, IntType: FromIntType, PrintType);
1886	OS << " != " << (ToDefault ? "(default) " : "");
1887	PrintAPSInt(Val: ToInt, E: ToExpr, Valid: IsValidToInt, IntType: ToIntType, PrintType);
1888	OS << ']';
1889	}
1890	}
1891
1892	/// PrintAPSInt - If valid, print the APSInt. If the expression is
1893	/// gives more information, print it too.
1894	void PrintAPSInt(const llvm::APSInt &Val, Expr *E, bool Valid,
1895	QualType IntType, bool PrintType) {
1896	Bold();
1897	if (Valid) {
1898	if (HasExtraInfo(E)) {
1899	PrintExpr(E);
1900	Unbold();
1901	OS << " aka ";
1902	Bold();
1903	}
1904	if (PrintType) {
1905	Unbold();
1906	OS << "(";
1907	Bold();
1908	IntType.print(OS, Policy: Context.getPrintingPolicy());
1909	Unbold();
1910	OS << ") ";
1911	Bold();
1912	}
1913	if (IntType->isBooleanType()) {
1914	OS << ((Val == 0) ? "false" : "true");
1915	} else {
1916	OS << toString(I: Val, Radix: 10);
1917	}
1918	} else if (E) {
1919	PrintExpr(E);
1920	} else {
1921	OS << "(no argument)";
1922	}
1923	Unbold();
1924	}
1925
1926	/// HasExtraInfo - Returns true if E is not an integer literal, the
1927	/// negation of an integer literal, or a boolean literal.
1928	bool HasExtraInfo(Expr *E) {
1929	if (!E) return false;
1930
1931	E = E->IgnoreImpCasts();
1932
1933	auto CheckIntegerLiteral = [](Expr *E) {
1934	if (auto *TemplateExpr = dyn_cast<SubstNonTypeTemplateParmExpr>(Val: E))
1935	E = TemplateExpr->getReplacement();
1936	return isa<IntegerLiteral>(Val: E);
1937	};
1938
1939	if (CheckIntegerLiteral(E)) return false;
1940
1941	if (UnaryOperator *UO = dyn_cast<UnaryOperator>(Val: E))
1942	if (UO->getOpcode() == UO_Minus)
1943	if (CheckIntegerLiteral(UO->getSubExpr()))
1944	return false;
1945
1946	if (isa<CXXBoolLiteralExpr>(Val: E))
1947	return false;
1948
1949	return true;
1950	}
1951
1952	void PrintValueDecl(ValueDecl *VD, bool AddressOf, Expr *E, bool NullPtr) {
1953	if (VD) {
1954	if (AddressOf)
1955	OS << "&";
1956	else if (auto *TPO = dyn_cast<TemplateParamObjectDecl>(Val: VD)) {
1957	// FIXME: Diffing the APValue would be neat.
1958	// FIXME: Suppress this and use the full name of the declaration if the
1959	// parameter is a pointer or reference.
1960	TPO->getType().getUnqualifiedType().print(OS, Policy);
1961	TPO->printAsInit(OS, Policy);
1962	return;
1963	}
1964	VD->printName(OS, Policy);
1965	return;
1966	}
1967
1968	if (NullPtr) {
1969	if (E && !isa<CXXNullPtrLiteralExpr>(Val: E)) {
1970	PrintExpr(E);
1971	if (IsBold) {
1972	Unbold();
1973	OS << " aka ";
1974	Bold();
1975	} else {
1976	OS << " aka ";
1977	}
1978	}
1979
1980	OS << "nullptr";
1981	return;
1982	}
1983
1984	if (E) {
1985	PrintExpr(E);
1986	return;
1987	}
1988
1989	OS << "(no argument)";
1990	}
1991
1992	/// PrintDecl - Handles printing of Decl arguments, highlighting
1993	/// argument differences.
1994	void PrintValueDecl(ValueDecl *FromValueDecl, ValueDecl *ToValueDecl,
1995	bool FromAddressOf, bool ToAddressOf, bool FromNullPtr,
1996	bool ToNullPtr, Expr *FromExpr, Expr *ToExpr,
1997	bool FromDefault, bool ToDefault, bool Same) {
1998	assert((FromValueDecl || FromNullPtr || ToValueDecl || ToNullPtr) &&
1999	"Only one Decl argument may be NULL");
2000
2001	if (Same) {
2002	PrintValueDecl(VD: FromValueDecl, AddressOf: FromAddressOf, E: FromExpr, NullPtr: FromNullPtr);
2003	} else if (!PrintTree) {
2004	OS << (FromDefault ? "(default) " : "");
2005	Bold();
2006	PrintValueDecl(VD: FromValueDecl, AddressOf: FromAddressOf, E: FromExpr, NullPtr: FromNullPtr);
2007	Unbold();
2008	} else {
2009	OS << (FromDefault ? "[(default) " : "[");
2010	Bold();
2011	PrintValueDecl(VD: FromValueDecl, AddressOf: FromAddressOf, E: FromExpr, NullPtr: FromNullPtr);
2012	Unbold();
2013	OS << " != " << (ToDefault ? "(default) " : "");
2014	Bold();
2015	PrintValueDecl(VD: ToValueDecl, AddressOf: ToAddressOf, E: ToExpr, NullPtr: ToNullPtr);
2016	Unbold();
2017	OS << ']';
2018	}
2019	}
2020
2021	/// PrintValueDeclAndInteger - Uses the print functions for ValueDecl and
2022	/// APSInt to print a mixed difference.
2023	void PrintValueDeclAndInteger(ValueDecl *VD, bool NeedAddressOf,
2024	bool IsNullPtr, Expr *VDExpr, bool DefaultDecl,
2025	const llvm::APSInt &Val, QualType IntType,
2026	Expr *IntExpr, bool DefaultInt) {
2027	if (!PrintTree) {
2028	OS << (DefaultDecl ? "(default) " : "");
2029	Bold();
2030	PrintValueDecl(VD, AddressOf: NeedAddressOf, E: VDExpr, NullPtr: IsNullPtr);
2031	Unbold();
2032	} else {
2033	OS << (DefaultDecl ? "[(default) " : "[");
2034	Bold();
2035	PrintValueDecl(VD, AddressOf: NeedAddressOf, E: VDExpr, NullPtr: IsNullPtr);
2036	Unbold();
2037	OS << " != " << (DefaultInt ? "(default) " : "");
2038	PrintAPSInt(Val, E: IntExpr, Valid: true /*Valid*/, IntType, PrintType: false /*PrintType*/);
2039	OS << ']';
2040	}
2041	}
2042
2043	/// PrintIntegerAndValueDecl - Uses the print functions for APSInt and
2044	/// ValueDecl to print a mixed difference.
2045	void PrintIntegerAndValueDecl(const llvm::APSInt &Val, QualType IntType,
2046	Expr *IntExpr, bool DefaultInt, ValueDecl *VD,
2047	bool NeedAddressOf, bool IsNullPtr,
2048	Expr *VDExpr, bool DefaultDecl) {
2049	if (!PrintTree) {
2050	OS << (DefaultInt ? "(default) " : "");
2051	PrintAPSInt(Val, E: IntExpr, Valid: true /*Valid*/, IntType, PrintType: false /*PrintType*/);
2052	} else {
2053	OS << (DefaultInt ? "[(default) " : "[");
2054	PrintAPSInt(Val, E: IntExpr, Valid: true /*Valid*/, IntType, PrintType: false /*PrintType*/);
2055	OS << " != " << (DefaultDecl ? "(default) " : "");
2056	Bold();
2057	PrintValueDecl(VD, AddressOf: NeedAddressOf, E: VDExpr, NullPtr: IsNullPtr);
2058	Unbold();
2059	OS << ']';
2060	}
2061	}
2062
2063	// Prints the appropriate placeholder for elided template arguments.
2064	void PrintElideArgs(unsigned NumElideArgs, unsigned Indent) {
2065	if (PrintTree) {
2066	OS << '\n';
2067	for (unsigned i = 0; i < Indent; ++i)
2068	OS << " ";
2069	}
2070	if (NumElideArgs == 0) return;
2071	if (NumElideArgs == 1)
2072	OS << "[...]";
2073	else
2074	OS << "[" << NumElideArgs << " * ...]";
2075	}
2076
2077	// Prints and highlights differences in Qualifiers.
2078	void PrintQualifiers(Qualifiers FromQual, Qualifiers ToQual) {
2079	// Both types have no qualifiers
2080	if (FromQual.empty() && ToQual.empty())
2081	return;
2082
2083	// Both types have same qualifiers
2084	if (FromQual == ToQual) {
2085	PrintQualifier(Q: FromQual, /*ApplyBold*/false);
2086	return;
2087	}
2088
2089	// Find common qualifiers and strip them from FromQual and ToQual.
2090	Qualifiers CommonQual = Qualifiers::removeCommonQualifiers(L&: FromQual,
2091	R&: ToQual);
2092
2093	// The qualifiers are printed before the template name.
2094	// Inline printing:
2095	// The common qualifiers are printed. Then, qualifiers only in this type
2096	// are printed and highlighted. Finally, qualifiers only in the other
2097	// type are printed and highlighted inside parentheses after "missing".
2098	// Tree printing:
2099	// Qualifiers are printed next to each other, inside brackets, and
2100	// separated by "!=". The printing order is:
2101	// common qualifiers, highlighted from qualifiers, "!=",
2102	// common qualifiers, highlighted to qualifiers
2103	if (PrintTree) {
2104	OS << "[";
2105	if (CommonQual.empty() && FromQual.empty()) {
2106	Bold();
2107	OS << "(no qualifiers) ";
2108	Unbold();
2109	} else {
2110	PrintQualifier(Q: CommonQual, /*ApplyBold*/false);
2111	PrintQualifier(Q: FromQual, /*ApplyBold*/true);
2112	}
2113	OS << "!= ";
2114	if (CommonQual.empty() && ToQual.empty()) {
2115	Bold();
2116	OS << "(no qualifiers)";
2117	Unbold();
2118	} else {
2119	PrintQualifier(Q: CommonQual, /*ApplyBold*/false,
2120	/*appendSpaceIfNonEmpty*/AppendSpaceIfNonEmpty: !ToQual.empty());
2121	PrintQualifier(Q: ToQual, /*ApplyBold*/true,
2122	/*appendSpaceIfNonEmpty*/AppendSpaceIfNonEmpty: false);
2123	}
2124	OS << "] ";
2125	} else {
2126	PrintQualifier(Q: CommonQual, /*ApplyBold*/false);
2127	PrintQualifier(Q: FromQual, /*ApplyBold*/true);
2128	}
2129	}
2130
2131	void PrintQualifier(Qualifiers Q, bool ApplyBold,
2132	bool AppendSpaceIfNonEmpty = true) {
2133	if (Q.empty()) return;
2134	if (ApplyBold) Bold();
2135	Q.print(OS, Policy, appendSpaceIfNonEmpty: AppendSpaceIfNonEmpty);
2136	if (ApplyBold) Unbold();
2137	}
2138
2139	public:
2140
2141	TemplateDiff(raw_ostream &OS, ASTContext &Context, QualType FromType,
2142	QualType ToType, bool PrintTree, bool PrintFromType,
2143	bool ElideType, bool ShowColor)
2144	: Context(Context),
2145	Policy(Context.getLangOpts()),
2146	ElideType(ElideType),
2147	PrintTree(PrintTree),
2148	ShowColor(ShowColor),
2149	// When printing a single type, the FromType is the one printed.
2150	FromTemplateType(PrintFromType ? FromType : ToType),
2151	ToTemplateType(PrintFromType ? ToType : FromType),
2152	OS(OS),
2153	IsBold(false) {
2154	}
2155
2156	/// DiffTemplate - Start the template type diffing.
2157	void DiffTemplate() {
2158	Qualifiers FromQual = FromTemplateType.getQualifiers(),
2159	ToQual = ToTemplateType.getQualifiers();
2160
2161	const TemplateSpecializationType *FromOrigTST =
2162	GetTemplateSpecializationType(Context, Ty: FromTemplateType);
2163	const TemplateSpecializationType *ToOrigTST =
2164	GetTemplateSpecializationType(Context, Ty: ToTemplateType);
2165
2166	// Only checking templates.
2167	if (!FromOrigTST || !ToOrigTST)
2168	return;
2169
2170	// Different base templates.
2171	if (!hasSameTemplate(Context, FromTST&: FromOrigTST, ToTST&: ToOrigTST)) {
2172	return;
2173	}
2174
2175	FromQual -= QualType(FromOrigTST, 0).getQualifiers();
2176	ToQual -= QualType(ToOrigTST, 0).getQualifiers();
2177
2178	// Same base template, but different arguments.
2179	Tree.SetTemplateDiff(
2180	FromTD: FromOrigTST->getTemplateName().getAsTemplateDecl(
2181	/*IgnoreDeduced=*/true),
2182	ToTD: ToOrigTST->getTemplateName().getAsTemplateDecl(/*IgnoreDeduced=*/true),
2183	FromQual, ToQual, FromDefault: false /*FromDefault*/, ToDefault: false /*ToDefault*/);
2184
2185	DiffTemplate(FromTST: FromOrigTST, ToTST: ToOrigTST);
2186	}
2187
2188	/// Emit - When the two types given are templated types with the same
2189	/// base template, a string representation of the type difference will be
2190	/// emitted to the stream and return true. Otherwise, return false.
2191	bool Emit() {
2192	Tree.StartTraverse();
2193	if (Tree.Empty())
2194	return false;
2195
2196	TreeToString();
2197	assert(!IsBold && "Bold is applied to end of string.");
2198	return true;
2199	}
2200	}; // end class TemplateDiff
2201	} // end anonymous namespace
2202
2203	/// FormatTemplateTypeDiff - A helper static function to start the template
2204	/// diff and return the properly formatted string. Returns true if the diff
2205	/// is successful.
2206	static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
2207	QualType ToType, bool PrintTree,
2208	bool PrintFromType, bool ElideType,
2209	bool ShowColors, raw_ostream &OS) {
2210	if (PrintTree)
2211	PrintFromType = true;
2212	TemplateDiff TD(OS, Context, FromType, ToType, PrintTree, PrintFromType,
2213	ElideType, ShowColors);
2214	TD.DiffTemplate();
2215	return TD.Emit();
2216	}
2217
2218	std::string clang::FormatUTFCodeUnitAsCodepoint(unsigned Value, QualType T) {
2219	auto IsSingleCodeUnitCP = [](unsigned Value, QualType T) {
2220	if (T->isChar8Type()) {
2221	assert(Value <= 0xFF && "not a valid UTF-8 code unit");
2222	return Value <= 0x7F;
2223	}
2224	if (T->isChar16Type()) {
2225	assert(Value <= 0xFFFF && "not a valid UTF-16 code unit");
2226	return llvm::IsSingleCodeUnitUTF16Codepoint(Value);
2227	}
2228	assert(T->isChar32Type());
2229	return llvm::IsSingleCodeUnitUTF32Codepoint(Value);
2230	};
2231	llvm::SmallVector<char, 16> Str;
2232	if (!IsSingleCodeUnitCP(Value, T)) {
2233	llvm::raw_svector_ostream OS(Str);
2234	OS << "<" << llvm::format_hex(N: Value, Width: 1, /*Upper=*/true) << ">";
2235	return std::string(Str.begin(), Str.end());
2236	}
2237
2238	char Buffer[UNI_MAX_UTF8_BYTES_PER_CODE_POINT];
2239	char *Ptr = Buffer;
2240	[[maybe_unused]] bool Converted = llvm::ConvertCodePointToUTF8(Source: Value, ResultPtr&: Ptr);
2241	assert(Converted && "trying to encode invalid code unit");
2242	EscapeStringForDiagnostic(Str: StringRef(Buffer, Ptr - Buffer), OutStr&: Str);
2243	return std::string(Str.begin(), Str.end());
2244	}
2245