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