Coverage Report

Created: 2020-09-15 12:33

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