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
25using 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.
29QualType 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) \
179case Type::Class: { \
180const Class##Type *CTy = cast<Class##Type>(Ty); \
181if (CTy->isSugared()) { \
182IsSugar = true; \
183Underlying = CTy->desugar(); \
184} \
185break; \
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
262static std::string
263ConvertTypeToDiagnosticString(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
350static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
351                                   QualType ToType, bool PrintTree,
352                                   bool PrintFromType, bool ElideType,
353                                   bool ShowColors, raw_ostream &OS);
354
355void 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.
523namespace {
524class 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
2065public:
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.
2131static 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}
2142