Coverage Report

Created: 2020-02-25 14:32

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