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