clang/lib/AST/ASTDiagnostic.cpp

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