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