contrib/llvm/tools/clang/lib/AST/ASTDiagnostic.cpp

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