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