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