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