Coverage Report

Created: 2021-09-21 08:58

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