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