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/ADT/SmallString.h"
  24 #include "llvm/Support/raw_ostream.h"
  25
  26 using namespace clang;
  27
  28 // Returns a desugared version of the QualType, and marks ShouldAKA as true
  29 // whenever we remove significant sugar from the type.
  30 static QualType Desugar(ASTContext &Context, QualType QT, bool &ShouldAKA) {
  31   QualifierCollector QC;
  32
  33   while (true) {
  34     const Type *Ty = QC.strip(QT);
  35
  36     // Don't aka just because we saw an elaborated type...
  37     if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(Ty)) {
  38       QT = ET->desugar();
  39       continue;
  40     }
  41     // ... or a paren type ...
  42     if (const ParenType *PT = dyn_cast<ParenType>(Ty)) {
  43       QT = PT->desugar();
  44       continue;
  45     }
  46     // ...or a substituted template type parameter ...
  47     if (const SubstTemplateTypeParmType *ST =
  48           dyn_cast<SubstTemplateTypeParmType>(Ty)) {
  49       QT = ST->desugar();
  50       continue;
  51     }
  52     // ...or an attributed type...
  53     if (const AttributedType *AT = dyn_cast<AttributedType>(Ty)) {
  54       QT = AT->desugar();
  55       continue;
  56     }
  57     // ...or an adjusted type...
  58     if (const AdjustedType *AT = dyn_cast<AdjustedType>(Ty)) {
  59       QT = AT->desugar();
  60       continue;
  61     }
  62     // ... or an auto type.
  63     if (const AutoType *AT = dyn_cast<AutoType>(Ty)) {
  64       if (!AT->isSugared())
  65         break;
  66       QT = AT->desugar();
  67       continue;
  68     }
  69
  70     // Desugar FunctionType if return type or any parameter type should be
  71     // desugared. Preserve nullability attribute on desugared types.
  72     if (const FunctionType *FT = dyn_cast<FunctionType>(Ty)) {
  73       bool DesugarReturn = false;
  74       QualType SugarRT = FT->getReturnType();
  75       QualType RT = Desugar(Context, SugarRT, DesugarReturn);
  76       if (auto nullability = AttributedType::stripOuterNullability(SugarRT)) {
  77         RT = Context.getAttributedType(
  78             AttributedType::getNullabilityAttrKind(*nullability), RT, RT);
  79       }
  80
  81       bool DesugarArgument = false;
  82       SmallVector<QualType, 4> Args;
  83       const FunctionProtoType *FPT = dyn_cast<FunctionProtoType>(FT);
  84       if (FPT) {
  85         for (QualType SugarPT : FPT->param_types()) {
  86           QualType PT = Desugar(Context, SugarPT, DesugarArgument);
  87           if (auto nullability =
  88                   AttributedType::stripOuterNullability(SugarPT)) {
  89             PT = Context.getAttributedType(
  90                 AttributedType::getNullabilityAttrKind(*nullability), PT, PT);
  91           }
  92           Args.push_back(PT);
  93         }
  94       }
  95
  96       if (DesugarReturn || DesugarArgument) {
  97         ShouldAKA = true;
  98         QT = FPT ? Context.getFunctionType(RT, Args, FPT->getExtProtoInfo())
  99                  : Context.getFunctionNoProtoType(RT, FT->getExtInfo());
 100         break;
 101       }
 102     }
 103
 104     // Desugar template specializations if any template argument should be
 105     // desugared.
 106     if (const TemplateSpecializationType *TST =
 107             dyn_cast<TemplateSpecializationType>(Ty)) {
 108       if (!TST->isTypeAlias()) {
 109         bool DesugarArgument = false;
 110         SmallVector<TemplateArgument, 4> Args;
 111         for (unsigned I = 0, N = TST->getNumArgs(); I != N; ++I) {
 112           const TemplateArgument &Arg = TST->getArg(I);
 113           if (Arg.getKind() == TemplateArgument::Type)
 114             Args.push_back(Desugar(Context, Arg.getAsType(), DesugarArgument));
 115           else
 116             Args.push_back(Arg);
 117         }
 118
 119         if (DesugarArgument) {
 120           ShouldAKA = true;
 121           QT = Context.getTemplateSpecializationType(
 122               TST->getTemplateName(), Args, QT);
 123         }
 124         break;
 125       }
 126     }
 127
 128     // Don't desugar magic Objective-C types.
 129     if (QualType(Ty,0) == Context.getObjCIdType() ||
 130         QualType(Ty,0) == Context.getObjCClassType() ||
 131         QualType(Ty,0) == Context.getObjCSelType() ||
 132         QualType(Ty,0) == Context.getObjCProtoType())
 133       break;
 134
 135     // Don't desugar va_list.
 136     if (QualType(Ty, 0) == Context.getBuiltinVaListType() ||
 137         QualType(Ty, 0) == Context.getBuiltinMSVaListType())
 138       break;
 139
 140     // Otherwise, do a single-step desugar.
 141     QualType Underlying;
 142     bool IsSugar = false;
 143     switch (Ty->getTypeClass()) {
 144 #define ABSTRACT_TYPE(Class, Base)
 145 #define TYPE(Class, Base) \
 146 case Type::Class: { \
 147 const Class##Type *CTy = cast<Class##Type>(Ty); \
 148 if (CTy->isSugared()) { \
 149 IsSugar = true; \
 150 Underlying = CTy->desugar(); \
 151 } \
 152 break; \
 153 }
 154 #include "clang/AST/TypeNodes.def"
 155     }
 156
 157     // If it wasn't sugared, we're done.
 158     if (!IsSugar)
 159       break;
 160
 161     // If the desugared type is a vector type, we don't want to expand
 162     // it, it will turn into an attribute mess. People want their "vec4".
 163     if (isa<VectorType>(Underlying))
 164       break;
 165
 166     // Don't desugar through the primary typedef of an anonymous type.
 167     if (const TagType *UTT = Underlying->getAs<TagType>())
 168       if (const TypedefType *QTT = dyn_cast<TypedefType>(QT))
 169         if (UTT->getDecl()->getTypedefNameForAnonDecl() == QTT->getDecl())
 170           break;
 171
 172     // Record that we actually looked through an opaque type here.
 173     ShouldAKA = true;
 174     QT = Underlying;
 175   }
 176
 177   // If we have a pointer-like type, desugar the pointee as well.
 178   // FIXME: Handle other pointer-like types.
 179   if (const PointerType *Ty = QT->getAs<PointerType>()) {
 180     QT = Context.getPointerType(Desugar(Context, Ty->getPointeeType(),
 181                                         ShouldAKA));
 182   } else if (const auto *Ty = QT->getAs<ObjCObjectPointerType>()) {
 183     QT = Context.getObjCObjectPointerType(Desugar(Context, Ty->getPointeeType(),
 184                                                   ShouldAKA));
 185   } else if (const LValueReferenceType *Ty = QT->getAs<LValueReferenceType>()) {
 186     QT = Context.getLValueReferenceType(Desugar(Context, Ty->getPointeeType(),
 187                                                 ShouldAKA));
 188   } else if (const RValueReferenceType *Ty = QT->getAs<RValueReferenceType>()) {
 189     QT = Context.getRValueReferenceType(Desugar(Context, Ty->getPointeeType(),
 190                                                 ShouldAKA));
 191   } else if (const auto *Ty = QT->getAs<ObjCObjectType>()) {
 192     if (Ty->getBaseType().getTypePtr() != Ty && !ShouldAKA) {
 193       QualType BaseType = Desugar(Context, Ty->getBaseType(), ShouldAKA);
 194       QT = Context.getObjCObjectType(BaseType, Ty->getTypeArgsAsWritten(),
 195                                      llvm::makeArrayRef(Ty->qual_begin(),
 196                                                         Ty->getNumProtocols()),
 197                                      Ty->isKindOfTypeAsWritten());
 198     }
 199   }
 200
 201   return QC.apply(Context, QT);
 202 }
 203
 204 /// \brief Convert the given type to a string suitable for printing as part of
 205 /// a diagnostic.
 206 ///
 207 /// There are four main criteria when determining whether we should have an
 208 /// a.k.a. clause when pretty-printing a type:
 209 ///
 210 /// 1) Some types provide very minimal sugar that doesn't impede the
 211 ///    user's understanding --- for example, elaborated type
 212 ///    specifiers.  If this is all the sugar we see, we don't want an
 213 ///    a.k.a. clause.
 214 /// 2) Some types are technically sugared but are much more familiar
 215 ///    when seen in their sugared form --- for example, va_list,
 216 ///    vector types, and the magic Objective C types.  We don't
 217 ///    want to desugar these, even if we do produce an a.k.a. clause.
 218 /// 3) Some types may have already been desugared previously in this diagnostic.
 219 ///    if this is the case, doing another "aka" would just be clutter.
 220 /// 4) Two different types within the same diagnostic have the same output
 221 ///    string.  In this case, force an a.k.a with the desugared type when
 222 ///    doing so will provide additional information.
 223 ///
 224 /// \param Context the context in which the type was allocated
 225 /// \param Ty the type to print
 226 /// \param QualTypeVals pointer values to QualTypes which are used in the
 227 /// diagnostic message
 228 static std::string
 229 ConvertTypeToDiagnosticString(ASTContext &Context, QualType Ty,
 230                             ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs,
 231                             ArrayRef<intptr_t> QualTypeVals) {
 232   // FIXME: Playing with std::string is really slow.
 233   bool ForceAKA = false;
 234   QualType CanTy = Ty.getCanonicalType();
 235   std::string S = Ty.getAsString(Context.getPrintingPolicy());
 236   std::string CanS = CanTy.getAsString(Context.getPrintingPolicy());
 237
 238   for (unsigned I = 0, E = QualTypeVals.size(); I != E; ++I) {
 239     QualType CompareTy =
 240         QualType::getFromOpaquePtr(reinterpret_cast<void*>(QualTypeVals[I]));
 241     if (CompareTy.isNull())
 242       continue;
 243     if (CompareTy == Ty)
 244       continue;  // Same types
 245     QualType CompareCanTy = CompareTy.getCanonicalType();
 246     if (CompareCanTy == CanTy)
 247       continue;  // Same canonical types
 248     std::string CompareS = CompareTy.getAsString(Context.getPrintingPolicy());
 249     bool ShouldAKA = false;
 250     QualType CompareDesugar = Desugar(Context, CompareTy, ShouldAKA);
 251     std::string CompareDesugarStr =
 252         CompareDesugar.getAsString(Context.getPrintingPolicy());
 253     if (CompareS != S && CompareDesugarStr != S)
 254       continue;  // The type string is different than the comparison string
 255                  // and the desugared comparison string.
 256     std::string CompareCanS =
 257         CompareCanTy.getAsString(Context.getPrintingPolicy());
 258
 259     if (CompareCanS == CanS)
 260       continue;  // No new info from canonical type
 261
 262     ForceAKA = true;
 263     break;
 264   }
 265
 266   // Check to see if we already desugared this type in this
 267   // diagnostic.  If so, don't do it again.
 268   bool Repeated = false;
 269   for (unsigned i = 0, e = PrevArgs.size(); i != e; ++i) {
 270     // TODO: Handle ak_declcontext case.
 271     if (PrevArgs[i].first == DiagnosticsEngine::ak_qualtype) {
 272       void *Ptr = (void*)PrevArgs[i].second;
 273       QualType PrevTy(QualType::getFromOpaquePtr(Ptr));
 274       if (PrevTy == Ty) {
 275         Repeated = true;
 276         break;
 277       }
 278     }
 279   }
 280
 281   // Consider producing an a.k.a. clause if removing all the direct
 282   // sugar gives us something "significantly different".
 283   if (!Repeated) {
 284     bool ShouldAKA = false;
 285     QualType DesugaredTy = Desugar(Context, Ty, ShouldAKA);
 286     if (ShouldAKA || ForceAKA) {
 287       if (DesugaredTy == Ty) {
 288         DesugaredTy = Ty.getCanonicalType();
 289       }
 290       std::string akaStr = DesugaredTy.getAsString(Context.getPrintingPolicy());
 291       if (akaStr != S) {
 292         S = "'" + S + "' (aka '" + akaStr + "')";
 293         return S;
 294       }
 295     }
 296
 297     // Give some additional info on vector types. These are either not desugared
 298     // or displaying complex __attribute__ expressions so add details of the
 299     // type and element count.
 300     if (Ty->isVectorType()) {
 301       const VectorType *VTy = Ty->getAs<VectorType>();
 302       std::string DecoratedString;
 303       llvm::raw_string_ostream OS(DecoratedString);
 304       const char *Values = VTy->getNumElements() > 1 ? "values" : "value";
 305       OS << "'" << S << "' (vector of " << VTy->getNumElements() << " '"
 306          << VTy->getElementType().getAsString(Context.getPrintingPolicy())
 307          << "' " << Values << ")";
 308       return OS.str();
 309     }
 310   }
 311
 312   S = "'" + S + "'";
 313   return S;
 314 }
 315
 316 static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
 317                                    QualType ToType, bool PrintTree,
 318                                    bool PrintFromType, bool ElideType,
 319                                    bool ShowColors, raw_ostream &OS);
 320
 321 void clang::FormatASTNodeDiagnosticArgument(
 322     DiagnosticsEngine::ArgumentKind Kind,
 323     intptr_t Val,
 324     StringRef Modifier,
 325     StringRef Argument,
 326     ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs,
 327     SmallVectorImpl<char> &Output,
 328     void *Cookie,
 329     ArrayRef<intptr_t> QualTypeVals) {
 330   ASTContext &Context = *static_cast<ASTContext*>(Cookie);
 331
 332   size_t OldEnd = Output.size();
 333   llvm::raw_svector_ostream OS(Output);
 334   bool NeedQuotes = true;
 335
 336   switch (Kind) {
 337     default: llvm_unreachable("unknown ArgumentKind");
 338     case DiagnosticsEngine::ak_qualtype_pair: {
 339       TemplateDiffTypes &TDT = *reinterpret_cast<TemplateDiffTypes*>(Val);
 340       QualType FromType =
 341           QualType::getFromOpaquePtr(reinterpret_cast<void*>(TDT.FromType));
 342       QualType ToType =
 343           QualType::getFromOpaquePtr(reinterpret_cast<void*>(TDT.ToType));
 344
 345       if (FormatTemplateTypeDiff(Context, FromType, ToType, TDT.PrintTree,
 346                                  TDT.PrintFromType, TDT.ElideType,
 347                                  TDT.ShowColors, OS)) {
 348         NeedQuotes = !TDT.PrintTree;
 349         TDT.TemplateDiffUsed = true;
 350         break;
 351       }
 352
 353       // Don't fall-back during tree printing.  The caller will handle
 354       // this case.
 355       if (TDT.PrintTree)
 356         return;
 357
 358       // Attempting to do a template diff on non-templates.  Set the variables
 359       // and continue with regular type printing of the appropriate type.
 360       Val = TDT.PrintFromType ? TDT.FromType : TDT.ToType;
 361       Modifier = StringRef();
 362       Argument = StringRef();
 363       // Fall through
 364     }
 365     case DiagnosticsEngine::ak_qualtype: {
 366       assert(Modifier.empty() && Argument.empty() &&
 367              "Invalid modifier for QualType argument");
 368
 369       QualType Ty(QualType::getFromOpaquePtr(reinterpret_cast<void*>(Val)));
 370       OS << ConvertTypeToDiagnosticString(Context, Ty, PrevArgs, QualTypeVals);
 371       NeedQuotes = false;
 372       break;
 373     }
 374     case DiagnosticsEngine::ak_declarationname: {
 375       if (Modifier == "objcclass" && Argument.empty())
 376         OS << '+';
 377       else if (Modifier == "objcinstance" && Argument.empty())
 378         OS << '-';
 379       else
 380         assert(Modifier.empty() && Argument.empty() &&
 381                "Invalid modifier for DeclarationName argument");
 382
 383       OS << DeclarationName::getFromOpaqueInteger(Val);
 384       break;
 385     }
 386     case DiagnosticsEngine::ak_nameddecl: {
 387       bool Qualified;
 388       if (Modifier == "q" && Argument.empty())
 389         Qualified = true;
 390       else {
 391         assert(Modifier.empty() && Argument.empty() &&
 392                "Invalid modifier for NamedDecl* argument");
 393         Qualified = false;
 394       }
 395       const NamedDecl *ND = reinterpret_cast<const NamedDecl*>(Val);
 396       ND->getNameForDiagnostic(OS, Context.getPrintingPolicy(), Qualified);
 397       break;
 398     }
 399     case DiagnosticsEngine::ak_nestednamespec: {
 400       NestedNameSpecifier *NNS = reinterpret_cast<NestedNameSpecifier*>(Val);
 401       NNS->print(OS, Context.getPrintingPolicy());
 402       NeedQuotes = false;
 403       break;
 404     }
 405     case DiagnosticsEngine::ak_declcontext: {
 406       DeclContext *DC = reinterpret_cast<DeclContext *> (Val);
 407       assert(DC && "Should never have a null declaration context");
 408       NeedQuotes = false;
 409
 410       // FIXME: Get the strings for DeclContext from some localized place
 411       if (DC->isTranslationUnit()) {
 412         if (Context.getLangOpts().CPlusPlus)
 413           OS << "the global namespace";
 414         else
 415           OS << "the global scope";
 416       } else if (DC->isClosure()) {
 417         OS << "block literal";
 418       } else if (isLambdaCallOperator(DC)) {
 419         OS << "lambda expression";
 420       } else if (TypeDecl *Type = dyn_cast<TypeDecl>(DC)) {
 421         OS << ConvertTypeToDiagnosticString(Context,
 422                                             Context.getTypeDeclType(Type),
 423                                             PrevArgs, QualTypeVals);
 424       } else {
 425         assert(isa<NamedDecl>(DC) && "Expected a NamedDecl");
 426         NamedDecl *ND = cast<NamedDecl>(DC);
 427         if (isa<NamespaceDecl>(ND))
 428           OS << "namespace ";
 429         else if (isa<ObjCMethodDecl>(ND))
 430           OS << "method ";
 431         else if (isa<FunctionDecl>(ND))
 432           OS << "function ";
 433
 434         OS << '\'';
 435         ND->getNameForDiagnostic(OS, Context.getPrintingPolicy(), true);
 436         OS << '\'';
 437       }
 438       break;
 439     }
 440     case DiagnosticsEngine::ak_attr: {
 441       const Attr *At = reinterpret_cast<Attr *>(Val);
 442       assert(At && "Received null Attr object!");
 443       OS << '\'' << At->getSpelling() << '\'';
 444       NeedQuotes = false;
 445       break;
 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
 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(const llvm::APSInt &FromInt, const 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, const 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         const 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 (!TST) return;
 921
 922         if (isEnd()) return;
 923
 924         // Set to first template argument.  If not a parameter pack, done.
 925         TemplateArgument TA = TST->getArg(0);
 926         if (TA.getKind() != TemplateArgument::Pack) return;
 927
 928         // Start looking into the parameter pack.
 929         CurrentTA = TA.pack_begin();
 930         EndTA = TA.pack_end();
 931
 932         // Found a valid template argument.
 933         if (CurrentTA != EndTA) return;
 934
 935         // Parameter pack is empty, use the increment to get to a valid
 936         // template argument.
 937         ++(*this);
 938       }
 939
 940       /// isEnd - Returns true if the iterator is one past the end.
 941       bool isEnd() const {
 942         assert(TST && "InternalIterator is invalid with a null TST.");
 943         return Index >= TST->getNumArgs();
 944       }
 945
 946       /// &operator++ - Increment the iterator to the next template argument.
 947       InternalIterator &operator++() {
 948         assert(TST && "InternalIterator is invalid with a null TST.");
 949         if (isEnd()) {
 950           return *this;
 951         }
 952
 953         // If in a parameter pack, advance in the parameter pack.
 954         if (CurrentTA != EndTA) {
 955           ++CurrentTA;
 956           if (CurrentTA != EndTA)
 957             return *this;
 958         }
 959
 960         // Loop until a template argument is found, or the end is reached.
 961         while (true) {
 962           // Advance to the next template argument.  Break if reached the end.
 963           if (++Index == TST->getNumArgs())
 964             break;
 965
 966           // If the TemplateArgument is not a parameter pack, done.
 967           TemplateArgument TA = TST->getArg(Index);
 968           if (TA.getKind() != TemplateArgument::Pack)
 969             break;
 970
 971           // Handle parameter packs.
 972           CurrentTA = TA.pack_begin();
 973           EndTA = TA.pack_end();
 974
 975           // If the parameter pack is empty, try to advance again.
 976           if (CurrentTA != EndTA)
 977             break;
 978         }
 979         return *this;
 980       }
 981
 982       /// operator* - Returns the appropriate TemplateArgument.
 983       reference operator*() const {
 984         assert(TST && "InternalIterator is invalid with a null TST.");
 985         assert(!isEnd() && "Index exceeds number of arguments.");
 986         if (CurrentTA == EndTA)
 987           return TST->getArg(Index);
 988         else
 989           return *CurrentTA;
 990       }
 991
 992       /// operator-> - Allow access to the underlying TemplateArgument.
 993       pointer operator->() const {
 994         assert(TST && "InternalIterator is invalid with a null TST.");
 995         return &operator*();
 996       }
 997     };
 998
 999     bool UseDesugaredIterator;
1000     InternalIterator SugaredIterator;
1001     InternalIterator DesugaredIterator;
1002
1003   public:
1004     TSTiterator(ASTContext &Context, const TemplateSpecializationType *TST)
1005         : UseDesugaredIterator(TST->isSugared() && !TST->isTypeAlias()),
1006           SugaredIterator(TST),
1007           DesugaredIterator(
1008               GetTemplateSpecializationType(Context, TST->desugar())) {}
1009
1010     /// &operator++ - Increment the iterator to the next template argument.
1011     TSTiterator &operator++() {
1012       ++SugaredIterator;
1013       if (UseDesugaredIterator)
1014         ++DesugaredIterator;
1015       return *this;
1016     }
1017
1018     /// operator* - Returns the appropriate TemplateArgument.
1019     reference operator*() const {
1020       return *SugaredIterator;
1021     }
1022
1023     /// operator-> - Allow access to the underlying TemplateArgument.
1024     pointer operator->() const {
1025       return &operator*();
1026     }
1027
1028     /// isEnd - Returns true if no more TemplateArguments are available.
1029     bool isEnd() const {
1030       return SugaredIterator.isEnd();
1031     }
1032
1033     /// hasDesugaredTA - Returns true if there is another TemplateArgument
1034     /// available.
1035     bool hasDesugaredTA() const {
1036       return UseDesugaredIterator && !DesugaredIterator.isEnd();
1037     }
1038
1039     /// getDesugaredTA - Returns the desugared TemplateArgument.
1040     reference getDesugaredTA() const {
1041       assert(UseDesugaredIterator &&
1042              "Desugared TemplateArgument should not be used.");
1043       return *DesugaredIterator;
1044     }
1045   };
1046
1047   // These functions build up the template diff tree, including functions to
1048   // retrieve and compare template arguments.
1049
1050   static const TemplateSpecializationType *GetTemplateSpecializationType(
1051       ASTContext &Context, QualType Ty) {
1052     if (const TemplateSpecializationType *TST =
1053             Ty->getAs<TemplateSpecializationType>())
1054       return TST;
1055
1056     const RecordType *RT = Ty->getAs<RecordType>();
1057
1058     if (!RT)
1059       return nullptr;
1060
1061     const ClassTemplateSpecializationDecl *CTSD =
1062         dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl());
1063
1064     if (!CTSD)
1065       return nullptr;
1066
1067     Ty = Context.getTemplateSpecializationType(
1068              TemplateName(CTSD->getSpecializedTemplate()),
1069              CTSD->getTemplateArgs().asArray(),
1070              Ty.getLocalUnqualifiedType().getCanonicalType());
1071
1072     return Ty->getAs<TemplateSpecializationType>();
1073   }
1074
1075   /// Returns true if the DiffType is Type and false for Template.
1076   static bool OnlyPerformTypeDiff(ASTContext &Context, QualType FromType,
1077                                   QualType ToType,
1078                                   const TemplateSpecializationType *&FromArgTST,
1079                                   const TemplateSpecializationType *&ToArgTST) {
1080     if (FromType.isNull() || ToType.isNull())
1081       return true;
1082
1083     if (Context.hasSameType(FromType, ToType))
1084       return true;
1085
1086     FromArgTST = GetTemplateSpecializationType(Context, FromType);
1087     ToArgTST = GetTemplateSpecializationType(Context, ToType);
1088
1089     if (!FromArgTST || !ToArgTST)
1090       return true;
1091
1092     if (!hasSameTemplate(FromArgTST, ToArgTST))
1093       return true;
1094
1095     return false;
1096   }
1097
1098   /// DiffTypes - Fills a DiffNode with information about a type difference.
1099   void DiffTypes(const TSTiterator &FromIter, const TSTiterator &ToIter) {
1100     QualType FromType = GetType(FromIter);
1101     QualType ToType = GetType(ToIter);
1102
1103     bool FromDefault = FromIter.isEnd() && !FromType.isNull();
1104     bool ToDefault = ToIter.isEnd() && !ToType.isNull();
1105
1106     const TemplateSpecializationType *FromArgTST = nullptr;
1107     const TemplateSpecializationType *ToArgTST = nullptr;
1108     if (OnlyPerformTypeDiff(Context, FromType, ToType, FromArgTST, ToArgTST)) {
1109       Tree.SetTypeDiff(FromType, ToType, FromDefault, ToDefault);
1110       Tree.SetSame(!FromType.isNull() && !ToType.isNull() &&
1111                    Context.hasSameType(FromType, ToType));
1112     } else {
1113       assert(FromArgTST && ToArgTST &&
1114              "Both template specializations need to be valid.");
1115       Qualifiers FromQual = FromType.getQualifiers(),
1116                  ToQual = ToType.getQualifiers();
1117       FromQual -= QualType(FromArgTST, 0).getQualifiers();
1118       ToQual -= QualType(ToArgTST, 0).getQualifiers();
1119       Tree.SetTemplateDiff(FromArgTST->getTemplateName().getAsTemplateDecl(),
1120                            ToArgTST->getTemplateName().getAsTemplateDecl(),
1121                            FromQual, ToQual, FromDefault, ToDefault);
1122       DiffTemplate(FromArgTST, ToArgTST);
1123     }
1124   }
1125
1126   /// DiffTemplateTemplates - Fills a DiffNode with information about a
1127   /// template template difference.
1128   void DiffTemplateTemplates(const TSTiterator &FromIter,
1129                              const TSTiterator &ToIter) {
1130     TemplateDecl *FromDecl = GetTemplateDecl(FromIter);
1131     TemplateDecl *ToDecl = GetTemplateDecl(ToIter);
1132     Tree.SetTemplateTemplateDiff(FromDecl, ToDecl, FromIter.isEnd() && FromDecl,
1133                                  ToIter.isEnd() && ToDecl);
1134     Tree.SetSame(FromDecl && ToDecl &&
1135                  FromDecl->getCanonicalDecl() == ToDecl->getCanonicalDecl());
1136   }
1137
1138   /// InitializeNonTypeDiffVariables - Helper function for DiffNonTypes
1139   static void InitializeNonTypeDiffVariables(ASTContext &Context,
1140                                              const TSTiterator &Iter,
1141                                              NonTypeTemplateParmDecl *Default,
1142                                              llvm::APSInt &Value, bool &HasInt,
1143                                              QualType &IntType, bool &IsNullPtr,
1144                                              Expr *&E, ValueDecl *&VD,
1145                                              bool &NeedAddressOf) {
1146     if (!Iter.isEnd()) {
1147       switch (Iter->getKind()) {
1148         default:
1149           llvm_unreachable("unknown ArgumentKind");
1150         case TemplateArgument::Integral:
1151           Value = Iter->getAsIntegral();
1152           HasInt = true;
1153           IntType = Iter->getIntegralType();
1154           return;
1155         case TemplateArgument::Declaration: {
1156           VD = Iter->getAsDecl();
1157           QualType ArgType = Iter->getParamTypeForDecl();
1158           QualType VDType = VD->getType();
1159           if (ArgType->isPointerType() &&
1160               Context.hasSameType(ArgType->getPointeeType(), VDType))
1161             NeedAddressOf = true;
1162           return;
1163         }
1164         case TemplateArgument::NullPtr:
1165           IsNullPtr = true;
1166           return;
1167         case TemplateArgument::Expression:
1168           E = Iter->getAsExpr();
1169       }
1170     } else if (!Default->isParameterPack()) {
1171       E = Default->getDefaultArgument();
1172     }
1173
1174     if (!Iter.hasDesugaredTA()) return;
1175
1176     const TemplateArgument& TA = Iter.getDesugaredTA();
1177     switch (TA.getKind()) {
1178       default:
1179         llvm_unreachable("unknown ArgumentKind");
1180       case TemplateArgument::Integral:
1181         Value = TA.getAsIntegral();
1182         HasInt = true;
1183         IntType = TA.getIntegralType();
1184         return;
1185       case TemplateArgument::Declaration: {
1186         VD = TA.getAsDecl();
1187         QualType ArgType = TA.getParamTypeForDecl();
1188         QualType VDType = VD->getType();
1189         if (ArgType->isPointerType() &&
1190             Context.hasSameType(ArgType->getPointeeType(), VDType))
1191           NeedAddressOf = true;
1192         return;
1193       }
1194       case TemplateArgument::NullPtr:
1195         IsNullPtr = true;
1196         return;
1197       case TemplateArgument::Expression:
1198         // TODO: Sometimes, the desugared template argument Expr differs from
1199         // the sugared template argument Expr.  It may be useful in the future
1200         // but for now, it is just discarded.
1201         if (!E)
1202           E = TA.getAsExpr();
1203         return;
1204     }
1205   }
1206
1207   /// DiffNonTypes - Handles any template parameters not handled by DiffTypes
1208   /// of DiffTemplatesTemplates, such as integer and declaration parameters.
1209   void DiffNonTypes(const TSTiterator &FromIter, const TSTiterator &ToIter,
1210                     NonTypeTemplateParmDecl *FromDefaultNonTypeDecl,
1211                     NonTypeTemplateParmDecl *ToDefaultNonTypeDecl) {
1212     Expr *FromExpr = nullptr, *ToExpr = nullptr;
1213     llvm::APSInt FromInt, ToInt;
1214     QualType FromIntType, ToIntType;
1215     ValueDecl *FromValueDecl = nullptr, *ToValueDecl = nullptr;
1216     bool HasFromInt = false, HasToInt = false, FromNullPtr = false,
1217          ToNullPtr = false, NeedFromAddressOf = false, NeedToAddressOf = false;
1218     InitializeNonTypeDiffVariables(
1219         Context, FromIter, FromDefaultNonTypeDecl, FromInt, HasFromInt,
1220         FromIntType, FromNullPtr, FromExpr, FromValueDecl, NeedFromAddressOf);
1221     InitializeNonTypeDiffVariables(Context, ToIter, ToDefaultNonTypeDecl, ToInt,
1222                                    HasToInt, ToIntType, ToNullPtr, ToExpr,
1223                                    ToValueDecl, NeedToAddressOf);
1224
1225     bool FromDefault = FromIter.isEnd() &&
1226                        (FromExpr || FromValueDecl || HasFromInt || FromNullPtr);
1227     bool ToDefault = ToIter.isEnd() &&
1228                      (ToExpr || ToValueDecl || HasToInt || ToNullPtr);
1229
1230     bool FromDeclaration = FromValueDecl || FromNullPtr;
1231     bool ToDeclaration = ToValueDecl || ToNullPtr;
1232
1233     if (FromDeclaration && HasToInt) {
1234       Tree.SetFromDeclarationAndToIntegerDiff(
1235           FromValueDecl, NeedFromAddressOf, FromNullPtr, FromExpr, ToInt,
1236           HasToInt, ToIntType, ToExpr, FromDefault, ToDefault);
1237       Tree.SetSame(false);
1238       return;
1239
1240     }
1241
1242     if (HasFromInt && ToDeclaration) {
1243       Tree.SetFromIntegerAndToDeclarationDiff(
1244           FromInt, HasFromInt, FromIntType, FromExpr, ToValueDecl,
1245           NeedToAddressOf, ToNullPtr, ToExpr, FromDefault, ToDefault);
1246       Tree.SetSame(false);
1247       return;
1248     }
1249
1250     if (HasFromInt || HasToInt) {
1251       Tree.SetIntegerDiff(FromInt, ToInt, HasFromInt, HasToInt, FromIntType,
1252                           ToIntType, FromExpr, ToExpr, FromDefault, ToDefault);
1253       if (HasFromInt && HasToInt) {
1254         Tree.SetSame(Context.hasSameType(FromIntType, ToIntType) &&
1255                      FromInt == ToInt);
1256       }
1257       return;
1258     }
1259
1260     if (FromDeclaration || ToDeclaration) {
1261       Tree.SetDeclarationDiff(FromValueDecl, ToValueDecl, NeedFromAddressOf,
1262                               NeedToAddressOf, FromNullPtr, ToNullPtr, FromExpr,
1263                               ToExpr, FromDefault, ToDefault);
1264       bool BothNull = FromNullPtr && ToNullPtr;
1265       bool SameValueDecl =
1266           FromValueDecl && ToValueDecl &&
1267           NeedFromAddressOf == NeedToAddressOf &&
1268           FromValueDecl->getCanonicalDecl() == ToValueDecl->getCanonicalDecl();
1269       Tree.SetSame(BothNull || SameValueDecl);
1270       return;
1271     }
1272
1273     assert((FromExpr || ToExpr) && "Both template arguments cannot be empty.");
1274     Tree.SetExpressionDiff(FromExpr, ToExpr, FromDefault, ToDefault);
1275     Tree.SetSame(IsEqualExpr(Context, FromExpr, ToExpr));
1276   }
1277
1278   /// DiffTemplate - recursively visits template arguments and stores the
1279   /// argument info into a tree.
1280   void DiffTemplate(const TemplateSpecializationType *FromTST,
1281                     const TemplateSpecializationType *ToTST) {
1282     // Begin descent into diffing template tree.
1283     TemplateParameterList *ParamsFrom =
1284         FromTST->getTemplateName().getAsTemplateDecl()->getTemplateParameters();
1285     TemplateParameterList *ParamsTo =
1286         ToTST->getTemplateName().getAsTemplateDecl()->getTemplateParameters();
1287     unsigned TotalArgs = 0;
1288     for (TSTiterator FromIter(Context, FromTST), ToIter(Context, ToTST);
1289          !FromIter.isEnd() || !ToIter.isEnd(); ++TotalArgs) {
1290       Tree.AddNode();
1291
1292       // Get the parameter at index TotalArgs.  If index is larger
1293       // than the total number of parameters, then there is an
1294       // argument pack, so re-use the last parameter.
1295       unsigned FromParamIndex = std::min(TotalArgs, ParamsFrom->size() - 1);
1296       unsigned ToParamIndex = std::min(TotalArgs, ParamsTo->size() - 1);
1297       NamedDecl *FromParamND = ParamsFrom->getParam(FromParamIndex);
1298       NamedDecl *ToParamND = ParamsTo->getParam(ToParamIndex);
1299
1300       assert(FromParamND->getKind() == ToParamND->getKind() &&
1301              "Parameter Decl are not the same kind.");
1302
1303       if (isa<TemplateTypeParmDecl>(FromParamND)) {
1304         DiffTypes(FromIter, ToIter);
1305       } else if (isa<TemplateTemplateParmDecl>(FromParamND)) {
1306         DiffTemplateTemplates(FromIter, ToIter);
1307       } else if (isa<NonTypeTemplateParmDecl>(FromParamND)) {
1308         NonTypeTemplateParmDecl *FromDefaultNonTypeDecl =
1309             cast<NonTypeTemplateParmDecl>(FromParamND);
1310         NonTypeTemplateParmDecl *ToDefaultNonTypeDecl =
1311             cast<NonTypeTemplateParmDecl>(ToParamND);
1312         DiffNonTypes(FromIter, ToIter, FromDefaultNonTypeDecl,
1313                      ToDefaultNonTypeDecl);
1314       } else {
1315         llvm_unreachable("Unexpected Decl type.");
1316       }
1317
1318       ++FromIter;
1319       ++ToIter;
1320       Tree.Up();
1321     }
1322   }
1323
1324   /// makeTemplateList - Dump every template alias into the vector.
1325   static void makeTemplateList(
1326       SmallVectorImpl<const TemplateSpecializationType *> &TemplateList,
1327       const TemplateSpecializationType *TST) {
1328     while (TST) {
1329       TemplateList.push_back(TST);
1330       if (!TST->isTypeAlias())
1331         return;
1332       TST = TST->getAliasedType()->getAs<TemplateSpecializationType>();
1333     }
1334   }
1335
1336   /// hasSameBaseTemplate - Returns true when the base templates are the same,
1337   /// even if the template arguments are not.
1338   static bool hasSameBaseTemplate(const TemplateSpecializationType *FromTST,
1339                                   const TemplateSpecializationType *ToTST) {
1340     return FromTST->getTemplateName().getAsTemplateDecl()->getCanonicalDecl() ==
1341            ToTST->getTemplateName().getAsTemplateDecl()->getCanonicalDecl();
1342   }
1343
1344   /// hasSameTemplate - Returns true if both types are specialized from the
1345   /// same template declaration.  If they come from different template aliases,
1346   /// do a parallel ascension search to determine the highest template alias in
1347   /// common and set the arguments to them.
1348   static bool hasSameTemplate(const TemplateSpecializationType *&FromTST,
1349                               const TemplateSpecializationType *&ToTST) {
1350     // Check the top templates if they are the same.
1351     if (hasSameBaseTemplate(FromTST, ToTST))
1352       return true;
1353
1354     // Create vectors of template aliases.
1355     SmallVector<const TemplateSpecializationType*, 1> FromTemplateList,
1356                                                       ToTemplateList;
1357
1358     makeTemplateList(FromTemplateList, FromTST);
1359     makeTemplateList(ToTemplateList, ToTST);
1360
1361     SmallVectorImpl<const TemplateSpecializationType *>::reverse_iterator
1362         FromIter = FromTemplateList.rbegin(), FromEnd = FromTemplateList.rend(),
1363         ToIter = ToTemplateList.rbegin(), ToEnd = ToTemplateList.rend();
1364
1365     // Check if the lowest template types are the same.  If not, return.
1366     if (!hasSameBaseTemplate(*FromIter, *ToIter))
1367       return false;
1368
1369     // Begin searching up the template aliases.  The bottom most template
1370     // matches so move up until one pair does not match.  Use the template
1371     // right before that one.
1372     for (; FromIter != FromEnd && ToIter != ToEnd; ++FromIter, ++ToIter) {
1373       if (!hasSameBaseTemplate(*FromIter, *ToIter))
1374         break;
1375     }
1376
1377     FromTST = FromIter[-1];
1378     ToTST = ToIter[-1];
1379
1380     return true;
1381   }
1382
1383   /// GetType - Retrieves the template type arguments, including default
1384   /// arguments.
1385   static QualType GetType(const TSTiterator &Iter) {
1386     if (!Iter.isEnd())
1387       return Iter->getAsType();
1388     if (Iter.hasDesugaredTA())
1389       return Iter.getDesugaredTA().getAsType();
1390     return QualType();
1391   }
1392
1393   /// GetTemplateDecl - Retrieves the template template arguments, including
1394   /// default arguments.
1395   static TemplateDecl *GetTemplateDecl(const TSTiterator &Iter) {
1396     if (!Iter.isEnd())
1397       return Iter->getAsTemplate().getAsTemplateDecl();
1398     if (Iter.hasDesugaredTA())
1399       return Iter.getDesugaredTA().getAsTemplate().getAsTemplateDecl();
1400     return nullptr;
1401   }
1402
1403   /// IsEqualExpr - Returns true if the expressions are the same in regards to
1404   /// template arguments.  These expressions are dependent, so profile them
1405   /// instead of trying to evaluate them.
1406   static bool IsEqualExpr(ASTContext &Context, Expr *FromExpr, Expr *ToExpr) {
1407     if (FromExpr == ToExpr)
1408       return true;
1409
1410     if (!FromExpr || !ToExpr)
1411       return false;
1412
1413     llvm::FoldingSetNodeID FromID, ToID;
1414     FromExpr->Profile(FromID, Context, true);
1415     ToExpr->Profile(ToID, Context, true);
1416     return FromID == ToID;
1417   }
1418
1419   // These functions converts the tree representation of the template
1420   // differences into the internal character vector.
1421
1422   /// TreeToString - Converts the Tree object into a character stream which
1423   /// will later be turned into the output string.
1424   void TreeToString(int Indent = 1) {
1425     if (PrintTree) {
1426       OS << '\n';
1427       OS.indent(2 * Indent);
1428       ++Indent;
1429     }
1430
1431     // Handle cases where the difference is not templates with different
1432     // arguments.
1433     switch (Tree.GetKind()) {
1434       case DiffTree::Invalid:
1435         llvm_unreachable("Template diffing failed with bad DiffNode");
1436       case DiffTree::Type: {
1437         QualType FromType, ToType;
1438         Tree.GetTypeDiff(FromType, ToType);
1439         PrintTypeNames(FromType, ToType, Tree.FromDefault(), Tree.ToDefault(),
1440                        Tree.NodeIsSame());
1441         return;
1442       }
1443       case DiffTree::Expression: {
1444         Expr *FromExpr, *ToExpr;
1445         Tree.GetExpressionDiff(FromExpr, ToExpr);
1446         PrintExpr(FromExpr, ToExpr, Tree.FromDefault(), Tree.ToDefault(),
1447                   Tree.NodeIsSame());
1448         return;
1449       }
1450       case DiffTree::TemplateTemplate: {
1451         TemplateDecl *FromTD, *ToTD;
1452         Tree.GetTemplateTemplateDiff(FromTD, ToTD);
1453         PrintTemplateTemplate(FromTD, ToTD, Tree.FromDefault(),
1454                               Tree.ToDefault(), Tree.NodeIsSame());
1455         return;
1456       }
1457       case DiffTree::Integer: {
1458         llvm::APSInt FromInt, ToInt;
1459         Expr *FromExpr, *ToExpr;
1460         bool IsValidFromInt, IsValidToInt;
1461         QualType FromIntType, ToIntType;
1462         Tree.GetIntegerDiff(FromInt, ToInt, IsValidFromInt, IsValidToInt,
1463                             FromIntType, ToIntType, FromExpr, ToExpr);
1464         PrintAPSInt(FromInt, ToInt, IsValidFromInt, IsValidToInt, FromIntType,
1465                     ToIntType, FromExpr, ToExpr, Tree.FromDefault(),
1466                     Tree.ToDefault(), Tree.NodeIsSame());
1467         return;
1468       }
1469       case DiffTree::Declaration: {
1470         ValueDecl *FromValueDecl, *ToValueDecl;
1471         bool FromAddressOf, ToAddressOf;
1472         bool FromNullPtr, ToNullPtr;
1473         Expr *FromExpr, *ToExpr;
1474         Tree.GetDeclarationDiff(FromValueDecl, ToValueDecl, FromAddressOf,
1475                                 ToAddressOf, FromNullPtr, ToNullPtr, FromExpr,
1476                                 ToExpr);
1477         PrintValueDecl(FromValueDecl, ToValueDecl, FromAddressOf, ToAddressOf,
1478                        FromNullPtr, ToNullPtr, FromExpr, ToExpr,
1479                        Tree.FromDefault(), Tree.ToDefault(), Tree.NodeIsSame());
1480         return;
1481       }
1482       case DiffTree::FromDeclarationAndToInteger: {
1483         ValueDecl *FromValueDecl;
1484         bool FromAddressOf;
1485         bool FromNullPtr;
1486         Expr *FromExpr;
1487         llvm::APSInt ToInt;
1488         bool IsValidToInt;
1489         QualType ToIntType;
1490         Expr *ToExpr;
1491         Tree.GetFromDeclarationAndToIntegerDiff(
1492             FromValueDecl, FromAddressOf, FromNullPtr, FromExpr, ToInt,
1493             IsValidToInt, ToIntType, ToExpr);
1494         assert((FromValueDecl || FromNullPtr) && IsValidToInt);
1495         PrintValueDeclAndInteger(FromValueDecl, FromAddressOf, FromNullPtr,
1496                                  FromExpr, Tree.FromDefault(), ToInt, ToIntType,
1497                                  ToExpr, Tree.ToDefault());
1498         return;
1499       }
1500       case DiffTree::FromIntegerAndToDeclaration: {
1501         llvm::APSInt FromInt;
1502         bool IsValidFromInt;
1503         QualType FromIntType;
1504         Expr *FromExpr;
1505         ValueDecl *ToValueDecl;
1506         bool ToAddressOf;
1507         bool ToNullPtr;
1508         Expr *ToExpr;
1509         Tree.GetFromIntegerAndToDeclarationDiff(
1510             FromInt, IsValidFromInt, FromIntType, FromExpr, ToValueDecl,
1511             ToAddressOf, ToNullPtr, ToExpr);
1512         assert(IsValidFromInt && (ToValueDecl || ToNullPtr));
1513         PrintIntegerAndValueDecl(FromInt, FromIntType, FromExpr,
1514                                  Tree.FromDefault(), ToValueDecl, ToAddressOf,
1515                                  ToNullPtr, ToExpr, Tree.ToDefault());
1516         return;
1517       }
1518       case DiffTree::Template: {
1519         // Node is root of template.  Recurse on children.
1520         TemplateDecl *FromTD, *ToTD;
1521         Qualifiers FromQual, ToQual;
1522         Tree.GetTemplateDiff(FromTD, ToTD, FromQual, ToQual);
1523
1524         PrintQualifiers(FromQual, ToQual);
1525
1526         if (!Tree.HasChildren()) {
1527           // If we're dealing with a template specialization with zero
1528           // arguments, there are no children; special-case this.
1529           OS << FromTD->getNameAsString() << "<>";
1530           return;
1531         }
1532
1533         OS << FromTD->getNameAsString() << '<';
1534         Tree.MoveToChild();
1535         unsigned NumElideArgs = 0;
1536         bool AllArgsElided = true;
1537         do {
1538           if (ElideType) {
1539             if (Tree.NodeIsSame()) {
1540               ++NumElideArgs;
1541               continue;
1542             }
1543             AllArgsElided = false;
1544             if (NumElideArgs > 0) {
1545               PrintElideArgs(NumElideArgs, Indent);
1546               NumElideArgs = 0;
1547               OS << ", ";
1548             }
1549           }
1550           TreeToString(Indent);
1551           if (Tree.HasNextSibling())
1552             OS << ", ";
1553         } while (Tree.AdvanceSibling());
1554         if (NumElideArgs > 0) {
1555           if (AllArgsElided)
1556             OS << "...";
1557           else
1558             PrintElideArgs(NumElideArgs, Indent);
1559         }
1560
1561         Tree.Parent();
1562         OS << ">";
1563         return;
1564       }
1565     }
1566   }
1567
1568   // To signal to the text printer that a certain text needs to be bolded,
1569   // a special character is injected into the character stream which the
1570   // text printer will later strip out.
1571
1572   /// Bold - Start bolding text.
1573   void Bold() {
1574     assert(!IsBold && "Attempting to bold text that is already bold.");
1575     IsBold = true;
1576     if (ShowColor)
1577       OS << ToggleHighlight;
1578   }
1579
1580   /// Unbold - Stop bolding text.
1581   void Unbold() {
1582     assert(IsBold && "Attempting to remove bold from unbold text.");
1583     IsBold = false;
1584     if (ShowColor)
1585       OS << ToggleHighlight;
1586   }
1587
1588   // Functions to print out the arguments and highlighting the difference.
1589
1590   /// PrintTypeNames - prints the typenames, bolding differences.  Will detect
1591   /// typenames that are the same and attempt to disambiguate them by using
1592   /// canonical typenames.
1593   void PrintTypeNames(QualType FromType, QualType ToType,
1594                       bool FromDefault, bool ToDefault, bool Same) {
1595     assert((!FromType.isNull() || !ToType.isNull()) &&
1596            "Only one template argument may be missing.");
1597
1598     if (Same) {
1599       OS << FromType.getAsString(Policy);
1600       return;
1601     }
1602
1603     if (!FromType.isNull() && !ToType.isNull() &&
1604         FromType.getLocalUnqualifiedType() ==
1605         ToType.getLocalUnqualifiedType()) {
1606       Qualifiers FromQual = FromType.getLocalQualifiers(),
1607                  ToQual = ToType.getLocalQualifiers();
1608       PrintQualifiers(FromQual, ToQual);
1609       FromType.getLocalUnqualifiedType().print(OS, Policy);
1610       return;
1611     }
1612
1613     std::string FromTypeStr = FromType.isNull() ? "(no argument)"
1614                                                 : FromType.getAsString(Policy);
1615     std::string ToTypeStr = ToType.isNull() ? "(no argument)"
1616                                             : ToType.getAsString(Policy);
1617     // Switch to canonical typename if it is better.
1618     // TODO: merge this with other aka printing above.
1619     if (FromTypeStr == ToTypeStr) {
1620       std::string FromCanTypeStr =
1621           FromType.getCanonicalType().getAsString(Policy);
1622       std::string ToCanTypeStr = ToType.getCanonicalType().getAsString(Policy);
1623       if (FromCanTypeStr != ToCanTypeStr) {
1624         FromTypeStr = FromCanTypeStr;
1625         ToTypeStr = ToCanTypeStr;
1626       }
1627     }
1628
1629     if (PrintTree) OS << '[';
1630     OS << (FromDefault ? "(default) " : "");
1631     Bold();
1632     OS << FromTypeStr;
1633     Unbold();
1634     if (PrintTree) {
1635       OS << " != " << (ToDefault ? "(default) " : "");
1636       Bold();
1637       OS << ToTypeStr;
1638       Unbold();
1639       OS << "]";
1640     }
1641   }
1642
1643   /// PrintExpr - Prints out the expr template arguments, highlighting argument
1644   /// differences.
1645   void PrintExpr(const Expr *FromExpr, const Expr *ToExpr, bool FromDefault,
1646                  bool ToDefault, bool Same) {
1647     assert((FromExpr || ToExpr) &&
1648             "Only one template argument may be missing.");
1649     if (Same) {
1650       PrintExpr(FromExpr);
1651     } else if (!PrintTree) {
1652       OS << (FromDefault ? "(default) " : "");
1653       Bold();
1654       PrintExpr(FromExpr);
1655       Unbold();
1656     } else {
1657       OS << (FromDefault ? "[(default) " : "[");
1658       Bold();
1659       PrintExpr(FromExpr);
1660       Unbold();
1661       OS << " != " << (ToDefault ? "(default) " : "");
1662       Bold();
1663       PrintExpr(ToExpr);
1664       Unbold();
1665       OS << ']';
1666     }
1667   }
1668
1669   /// PrintExpr - Actual formatting and printing of expressions.
1670   void PrintExpr(const Expr *E) {
1671     if (E) {
1672       E->printPretty(OS, nullptr, Policy);
1673       return;
1674     }
1675     OS << "(no argument)";
1676   }
1677
1678   /// PrintTemplateTemplate - Handles printing of template template arguments,
1679   /// highlighting argument differences.
1680   void PrintTemplateTemplate(TemplateDecl *FromTD, TemplateDecl *ToTD,
1681                              bool FromDefault, bool ToDefault, bool Same) {
1682     assert((FromTD || ToTD) && "Only one template argument may be missing.");
1683
1684     std::string FromName = FromTD ? FromTD->getName() : "(no argument)";
1685     std::string ToName = ToTD ? ToTD->getName() : "(no argument)";
1686     if (FromTD && ToTD && FromName == ToName) {
1687       FromName = FromTD->getQualifiedNameAsString();
1688       ToName = ToTD->getQualifiedNameAsString();
1689     }
1690
1691     if (Same) {
1692       OS << "template " << FromTD->getNameAsString();
1693     } else if (!PrintTree) {
1694       OS << (FromDefault ? "(default) template " : "template ");
1695       Bold();
1696       OS << FromName;
1697       Unbold();
1698     } else {
1699       OS << (FromDefault ? "[(default) template " : "[template ");
1700       Bold();
1701       OS << FromName;
1702       Unbold();
1703       OS << " != " << (ToDefault ? "(default) template " : "template ");
1704       Bold();
1705       OS << ToName;
1706       Unbold();
1707       OS << ']';
1708     }
1709   }
1710
1711   /// PrintAPSInt - Handles printing of integral arguments, highlighting
1712   /// argument differences.
1713   void PrintAPSInt(const llvm::APSInt &FromInt, const llvm::APSInt &ToInt,
1714                    bool IsValidFromInt, bool IsValidToInt, QualType FromIntType,
1715                    QualType ToIntType, Expr *FromExpr, Expr *ToExpr,
1716                    bool FromDefault, bool ToDefault, bool Same) {
1717     assert((IsValidFromInt || IsValidToInt) &&
1718            "Only one integral argument may be missing.");
1719
1720     if (Same) {
1721       if (FromIntType->isBooleanType()) {
1722         OS << ((FromInt == 0) ? "false" : "true");
1723       } else {
1724         OS << FromInt.toString(10);
1725       }
1726       return;
1727     }
1728
1729     bool PrintType = IsValidFromInt && IsValidToInt &&
1730                      !Context.hasSameType(FromIntType, ToIntType);
1731
1732     if (!PrintTree) {
1733       OS << (FromDefault ? "(default) " : "");
1734       PrintAPSInt(FromInt, FromExpr, IsValidFromInt, FromIntType, PrintType);
1735     } else {
1736       OS << (FromDefault ? "[(default) " : "[");
1737       PrintAPSInt(FromInt, FromExpr, IsValidFromInt, FromIntType, PrintType);
1738       OS << " != " << (ToDefault ? "(default) " : "");
1739       PrintAPSInt(ToInt, ToExpr, IsValidToInt, ToIntType, PrintType);
1740       OS << ']';
1741     }
1742   }
1743
1744   /// PrintAPSInt - If valid, print the APSInt.  If the expression is
1745   /// gives more information, print it too.
1746   void PrintAPSInt(const llvm::APSInt &Val, Expr *E, bool Valid,
1747                    QualType IntType, bool PrintType) {
1748     Bold();
1749     if (Valid) {
1750       if (HasExtraInfo(E)) {
1751         PrintExpr(E);
1752         Unbold();
1753         OS << " aka ";
1754         Bold();
1755       }
1756       if (PrintType) {
1757         Unbold();
1758         OS << "(";
1759         Bold();
1760         IntType.print(OS, Context.getPrintingPolicy());
1761         Unbold();
1762         OS << ") ";
1763         Bold();
1764       }
1765       if (IntType->isBooleanType()) {
1766         OS << ((Val == 0) ? "false" : "true");
1767       } else {
1768         OS << Val.toString(10);
1769       }
1770     } else if (E) {
1771       PrintExpr(E);
1772     } else {
1773       OS << "(no argument)";
1774     }
1775     Unbold();
1776   }
1777
1778   /// HasExtraInfo - Returns true if E is not an integer literal, the
1779   /// negation of an integer literal, or a boolean literal.
1780   bool HasExtraInfo(Expr *E) {
1781     if (!E) return false;
1782
1783     E = E->IgnoreImpCasts();
1784
1785     if (isa<IntegerLiteral>(E)) return false;
1786
1787     if (UnaryOperator *UO = dyn_cast<UnaryOperator>(E))
1788       if (UO->getOpcode() == UO_Minus)
1789         if (isa<IntegerLiteral>(UO->getSubExpr()))
1790           return false;
1791
1792     if (isa<CXXBoolLiteralExpr>(E))
1793       return false;
1794
1795     return true;
1796   }
1797
1798   void PrintValueDecl(ValueDecl *VD, bool AddressOf, Expr *E, bool NullPtr) {
1799     if (VD) {
1800       if (AddressOf)
1801         OS << "&";
1802       OS << VD->getName();
1803       return;
1804     }
1805
1806     if (NullPtr) {
1807       if (E && !isa<CXXNullPtrLiteralExpr>(E)) {
1808         PrintExpr(E);
1809         if (IsBold) {
1810           Unbold();
1811           OS << " aka ";
1812           Bold();
1813         } else {
1814           OS << " aka ";
1815         }
1816       }
1817
1818       OS << "nullptr";
1819       return;
1820     }
1821
1822     OS << "(no argument)";
1823   }
1824
1825   /// PrintDecl - Handles printing of Decl arguments, highlighting
1826   /// argument differences.
1827   void PrintValueDecl(ValueDecl *FromValueDecl, ValueDecl *ToValueDecl,
1828                       bool FromAddressOf, bool ToAddressOf, bool FromNullPtr,
1829                       bool ToNullPtr, Expr *FromExpr, Expr *ToExpr,
1830                       bool FromDefault, bool ToDefault, bool Same) {
1831     assert((FromValueDecl || FromNullPtr || ToValueDecl || ToNullPtr) &&
1832            "Only one Decl argument may be NULL");
1833
1834     if (Same) {
1835       PrintValueDecl(FromValueDecl, FromAddressOf, FromExpr, FromNullPtr);
1836     } else if (!PrintTree) {
1837       OS << (FromDefault ? "(default) " : "");
1838       Bold();
1839       PrintValueDecl(FromValueDecl, FromAddressOf, FromExpr, FromNullPtr);
1840       Unbold();
1841     } else {
1842       OS << (FromDefault ? "[(default) " : "[");
1843       Bold();
1844       PrintValueDecl(FromValueDecl, FromAddressOf, FromExpr, FromNullPtr);
1845       Unbold();
1846       OS << " != " << (ToDefault ? "(default) " : "");
1847       Bold();
1848       PrintValueDecl(ToValueDecl, ToAddressOf, ToExpr, ToNullPtr);
1849       Unbold();
1850       OS << ']';
1851     }
1852   }
1853
1854   /// PrintValueDeclAndInteger - Uses the print functions for ValueDecl and
1855   /// APSInt to print a mixed difference.
1856   void PrintValueDeclAndInteger(ValueDecl *VD, bool NeedAddressOf,
1857                                 bool IsNullPtr, Expr *VDExpr, bool DefaultDecl,
1858                                 const llvm::APSInt &Val, QualType IntType,
1859                                 Expr *IntExpr, bool DefaultInt) {
1860     if (!PrintTree) {
1861       OS << (DefaultDecl ? "(default) " : "");
1862       Bold();
1863       PrintValueDecl(VD, NeedAddressOf, VDExpr, IsNullPtr);
1864       Unbold();
1865     } else {
1866       OS << (DefaultDecl ? "[(default) " : "[");
1867       Bold();
1868       PrintValueDecl(VD, NeedAddressOf, VDExpr, IsNullPtr);
1869       Unbold();
1870       OS << " != " << (DefaultInt ? "(default) " : "");
1871       PrintAPSInt(Val, IntExpr, true /*Valid*/, IntType, false /*PrintType*/);
1872       OS << ']';
1873     }
1874   }
1875
1876   /// PrintIntegerAndValueDecl - Uses the print functions for APSInt and
1877   /// ValueDecl to print a mixed difference.
1878   void PrintIntegerAndValueDecl(const llvm::APSInt &Val, QualType IntType,
1879                                 Expr *IntExpr, bool DefaultInt, ValueDecl *VD,
1880                                 bool NeedAddressOf, bool IsNullPtr,
1881                                 Expr *VDExpr, bool DefaultDecl) {
1882     if (!PrintTree) {
1883       OS << (DefaultInt ? "(default) " : "");
1884       PrintAPSInt(Val, IntExpr, true /*Valid*/, IntType, false /*PrintType*/);
1885     } else {
1886       OS << (DefaultInt ? "[(default) " : "[");
1887       PrintAPSInt(Val, IntExpr, true /*Valid*/, IntType, false /*PrintType*/);
1888       OS << " != " << (DefaultDecl ? "(default) " : "");
1889       Bold();
1890       PrintValueDecl(VD, NeedAddressOf, VDExpr, IsNullPtr);
1891       Unbold();
1892       OS << ']';
1893     }
1894   }
1895
1896   // Prints the appropriate placeholder for elided template arguments.
1897   void PrintElideArgs(unsigned NumElideArgs, unsigned Indent) {
1898     if (PrintTree) {
1899       OS << '\n';
1900       for (unsigned i = 0; i < Indent; ++i)
1901         OS << "  ";
1902     }
1903     if (NumElideArgs == 0) return;
1904     if (NumElideArgs == 1)
1905       OS << "[...]";
1906     else
1907       OS << "[" << NumElideArgs << " * ...]";
1908   }
1909
1910   // Prints and highlights differences in Qualifiers.
1911   void PrintQualifiers(Qualifiers FromQual, Qualifiers ToQual) {
1912     // Both types have no qualifiers
1913     if (FromQual.empty() && ToQual.empty())
1914       return;
1915
1916     // Both types have same qualifiers
1917     if (FromQual == ToQual) {
1918       PrintQualifier(FromQual, /*ApplyBold*/false);
1919       return;
1920     }
1921
1922     // Find common qualifiers and strip them from FromQual and ToQual.
1923     Qualifiers CommonQual = Qualifiers::removeCommonQualifiers(FromQual,
1924                                                                ToQual);
1925
1926     // The qualifiers are printed before the template name.
1927     // Inline printing:
1928     // The common qualifiers are printed.  Then, qualifiers only in this type
1929     // are printed and highlighted.  Finally, qualifiers only in the other
1930     // type are printed and highlighted inside parentheses after "missing".
1931     // Tree printing:
1932     // Qualifiers are printed next to each other, inside brackets, and
1933     // separated by "!=".  The printing order is:
1934     // common qualifiers, highlighted from qualifiers, "!=",
1935     // common qualifiers, highlighted to qualifiers
1936     if (PrintTree) {
1937       OS << "[";
1938       if (CommonQual.empty() && FromQual.empty()) {
1939         Bold();
1940         OS << "(no qualifiers) ";
1941         Unbold();
1942       } else {
1943         PrintQualifier(CommonQual, /*ApplyBold*/false);
1944         PrintQualifier(FromQual, /*ApplyBold*/true);
1945       }
1946       OS << "!= ";
1947       if (CommonQual.empty() && ToQual.empty()) {
1948         Bold();
1949         OS << "(no qualifiers)";
1950         Unbold();
1951       } else {
1952         PrintQualifier(CommonQual, /*ApplyBold*/false,
1953                        /*appendSpaceIfNonEmpty*/!ToQual.empty());
1954         PrintQualifier(ToQual, /*ApplyBold*/true,
1955                        /*appendSpaceIfNonEmpty*/false);
1956       }
1957       OS << "] ";
1958     } else {
1959       PrintQualifier(CommonQual, /*ApplyBold*/false);
1960       PrintQualifier(FromQual, /*ApplyBold*/true);
1961     }
1962   }
1963
1964   void PrintQualifier(Qualifiers Q, bool ApplyBold,
1965                       bool AppendSpaceIfNonEmpty = true) {
1966     if (Q.empty()) return;
1967     if (ApplyBold) Bold();
1968     Q.print(OS, Policy, AppendSpaceIfNonEmpty);
1969     if (ApplyBold) Unbold();
1970   }
1971
1972 public:
1973
1974   TemplateDiff(raw_ostream &OS, ASTContext &Context, QualType FromType,
1975                QualType ToType, bool PrintTree, bool PrintFromType,
1976                bool ElideType, bool ShowColor)
1977     : Context(Context),
1978       Policy(Context.getLangOpts()),
1979       ElideType(ElideType),
1980       PrintTree(PrintTree),
1981       ShowColor(ShowColor),
1982       // When printing a single type, the FromType is the one printed.
1983       FromTemplateType(PrintFromType ? FromType : ToType),
1984       ToTemplateType(PrintFromType ? ToType : FromType),
1985       OS(OS),
1986       IsBold(false) {
1987   }
1988
1989   /// DiffTemplate - Start the template type diffing.
1990   void DiffTemplate() {
1991     Qualifiers FromQual = FromTemplateType.getQualifiers(),
1992                ToQual = ToTemplateType.getQualifiers();
1993
1994     const TemplateSpecializationType *FromOrigTST =
1995         GetTemplateSpecializationType(Context, FromTemplateType);
1996     const TemplateSpecializationType *ToOrigTST =
1997         GetTemplateSpecializationType(Context, ToTemplateType);
1998
1999     // Only checking templates.
2000     if (!FromOrigTST || !ToOrigTST)
2001       return;
2002
2003     // Different base templates.
2004     if (!hasSameTemplate(FromOrigTST, ToOrigTST)) {
2005       return;
2006     }
2007
2008     FromQual -= QualType(FromOrigTST, 0).getQualifiers();
2009     ToQual -= QualType(ToOrigTST, 0).getQualifiers();
2010
2011     // Same base template, but different arguments.
2012     Tree.SetTemplateDiff(FromOrigTST->getTemplateName().getAsTemplateDecl(),
2013                          ToOrigTST->getTemplateName().getAsTemplateDecl(),
2014                          FromQual, ToQual, false /*FromDefault*/,
2015                          false /*ToDefault*/);
2016
2017     DiffTemplate(FromOrigTST, ToOrigTST);
2018   }
2019
2020   /// Emit - When the two types given are templated types with the same
2021   /// base template, a string representation of the type difference will be
2022   /// emitted to the stream and return true.  Otherwise, return false.
2023   bool Emit() {
2024     Tree.StartTraverse();
2025     if (Tree.Empty())
2026       return false;
2027
2028     TreeToString();
2029     assert(!IsBold && "Bold is applied to end of string.");
2030     return true;
2031   }
2032 }; // end class TemplateDiff
2033 }  // end anonymous namespace
2034
2035 /// FormatTemplateTypeDiff - A helper static function to start the template
2036 /// diff and return the properly formatted string.  Returns true if the diff
2037 /// is successful.
2038 static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
2039                                    QualType ToType, bool PrintTree,
2040                                    bool PrintFromType, bool ElideType,
2041                                    bool ShowColors, raw_ostream &OS) {
2042   if (PrintTree)
2043     PrintFromType = true;
2044   TemplateDiff TD(OS, Context, FromType, ToType, PrintTree, PrintFromType,
2045                   ElideType, ShowColors);
2046   TD.DiffTemplate();
2047   return TD.Emit();
2048 }