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