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