Coverage Report

Created: 2019-07-24 05:18

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