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