Coverage Report

Created: 2022-01-25 06:29

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