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