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