Clang Project

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