Coverage Report

Created: 2022-01-25 06:29

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/Sema/SemaTemplateDeduction.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===//
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 C++ template argument deduction.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "clang/Sema/TemplateDeduction.h"
14
#include "TreeTransform.h"
15
#include "TypeLocBuilder.h"
16
#include "clang/AST/ASTContext.h"
17
#include "clang/AST/ASTLambda.h"
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/DeclAccessPair.h"
20
#include "clang/AST/DeclBase.h"
21
#include "clang/AST/DeclCXX.h"
22
#include "clang/AST/DeclTemplate.h"
23
#include "clang/AST/DeclarationName.h"
24
#include "clang/AST/Expr.h"
25
#include "clang/AST/ExprCXX.h"
26
#include "clang/AST/NestedNameSpecifier.h"
27
#include "clang/AST/RecursiveASTVisitor.h"
28
#include "clang/AST/TemplateBase.h"
29
#include "clang/AST/TemplateName.h"
30
#include "clang/AST/Type.h"
31
#include "clang/AST/TypeLoc.h"
32
#include "clang/AST/UnresolvedSet.h"
33
#include "clang/Basic/AddressSpaces.h"
34
#include "clang/Basic/ExceptionSpecificationType.h"
35
#include "clang/Basic/LLVM.h"
36
#include "clang/Basic/LangOptions.h"
37
#include "clang/Basic/PartialDiagnostic.h"
38
#include "clang/Basic/SourceLocation.h"
39
#include "clang/Basic/Specifiers.h"
40
#include "clang/Sema/Ownership.h"
41
#include "clang/Sema/Sema.h"
42
#include "clang/Sema/Template.h"
43
#include "llvm/ADT/APInt.h"
44
#include "llvm/ADT/APSInt.h"
45
#include "llvm/ADT/ArrayRef.h"
46
#include "llvm/ADT/DenseMap.h"
47
#include "llvm/ADT/FoldingSet.h"
48
#include "llvm/ADT/Optional.h"
49
#include "llvm/ADT/SmallBitVector.h"
50
#include "llvm/ADT/SmallPtrSet.h"
51
#include "llvm/ADT/SmallVector.h"
52
#include "llvm/Support/Casting.h"
53
#include "llvm/Support/Compiler.h"
54
#include "llvm/Support/ErrorHandling.h"
55
#include <algorithm>
56
#include <cassert>
57
#include <tuple>
58
#include <utility>
59
60
namespace clang {
61
62
  /// Various flags that control template argument deduction.
63
  ///
64
  /// These flags can be bitwise-OR'd together.
65
  enum TemplateDeductionFlags {
66
    /// No template argument deduction flags, which indicates the
67
    /// strictest results for template argument deduction (as used for, e.g.,
68
    /// matching class template partial specializations).
69
    TDF_None = 0,
70
71
    /// Within template argument deduction from a function call, we are
72
    /// matching with a parameter type for which the original parameter was
73
    /// a reference.
74
    TDF_ParamWithReferenceType = 0x1,
75
76
    /// Within template argument deduction from a function call, we
77
    /// are matching in a case where we ignore cv-qualifiers.
78
    TDF_IgnoreQualifiers = 0x02,
79
80
    /// Within template argument deduction from a function call,
81
    /// we are matching in a case where we can perform template argument
82
    /// deduction from a template-id of a derived class of the argument type.
83
    TDF_DerivedClass = 0x04,
84
85
    /// Allow non-dependent types to differ, e.g., when performing
86
    /// template argument deduction from a function call where conversions
87
    /// may apply.
88
    TDF_SkipNonDependent = 0x08,
89
90
    /// Whether we are performing template argument deduction for
91
    /// parameters and arguments in a top-level template argument
92
    TDF_TopLevelParameterTypeList = 0x10,
93
94
    /// Within template argument deduction from overload resolution per
95
    /// C++ [over.over] allow matching function types that are compatible in
96
    /// terms of noreturn and default calling convention adjustments, or
97
    /// similarly matching a declared template specialization against a
98
    /// possible template, per C++ [temp.deduct.decl]. In either case, permit
99
    /// deduction where the parameter is a function type that can be converted
100
    /// to the argument type.
101
    TDF_AllowCompatibleFunctionType = 0x20,
102
103
    /// Within template argument deduction for a conversion function, we are
104
    /// matching with an argument type for which the original argument was
105
    /// a reference.
106
    TDF_ArgWithReferenceType = 0x40,
107
  };
108
}
109
110
using namespace clang;
111
using namespace sema;
112
113
/// Compare two APSInts, extending and switching the sign as
114
/// necessary to compare their values regardless of underlying type.
115
440k
static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
116
440k
  if (Y.getBitWidth() > X.getBitWidth())
117
12
    X = X.extend(Y.getBitWidth());
118
440k
  else if (Y.getBitWidth() < X.getBitWidth())
119
12
    Y = Y.extend(X.getBitWidth());
120
121
  // If there is a signedness mismatch, correct it.
122
440k
  if (X.isSigned() != Y.isSigned()) {
123
    // If the signed value is negative, then the values cannot be the same.
124
16
    if ((Y.isSigned() && 
Y.isNegative()9
) || (X.isSigned() &&
X.isNegative()7
))
125
0
      return false;
126
127
16
    Y.setIsSigned(true);
128
16
    X.setIsSigned(true);
129
16
  }
130
131
440k
  return X == Y;
132
440k
}
133
134
static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch(
135
    Sema &S, TemplateParameterList *TemplateParams, QualType Param,
136
    QualType Arg, TemplateDeductionInfo &Info,
137
    SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
138
    bool PartialOrdering = false, bool DeducedFromArrayBound = false);
139
140
static Sema::TemplateDeductionResult
141
DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
142
                        ArrayRef<TemplateArgument> Ps,
143
                        ArrayRef<TemplateArgument> As,
144
                        TemplateDeductionInfo &Info,
145
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
146
                        bool NumberOfArgumentsMustMatch);
147
148
static void MarkUsedTemplateParameters(ASTContext &Ctx,
149
                                       const TemplateArgument &TemplateArg,
150
                                       bool OnlyDeduced, unsigned Depth,
151
                                       llvm::SmallBitVector &Used);
152
153
static void MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
154
                                       bool OnlyDeduced, unsigned Level,
155
                                       llvm::SmallBitVector &Deduced);
156
157
/// If the given expression is of a form that permits the deduction
158
/// of a non-type template parameter, return the declaration of that
159
/// non-type template parameter.
160
static const NonTypeTemplateParmDecl *
161
328k
getDeducedParameterFromExpr(const Expr *E, unsigned Depth) {
162
  // If we are within an alias template, the expression may have undergone
163
  // any number of parameter substitutions already.
164
336k
  while (true) {
165
336k
    if (const auto *IC = dyn_cast<ImplicitCastExpr>(E))
166
7.46k
      E = IC->getSubExpr();
167
328k
    else if (const auto *CE = dyn_cast<ConstantExpr>(E))
168
0
      E = CE->getSubExpr();
169
328k
    else if (const auto *Subst = dyn_cast<SubstNonTypeTemplateParmExpr>(E))
170
212
      E = Subst->getReplacement();
171
328k
    else if (const auto *CCE = dyn_cast<CXXConstructExpr>(E)) {
172
      // Look through implicit copy construction from an lvalue of the same type.
173
0
      if (CCE->getParenOrBraceRange().isValid())
174
0
        break;
175
      // Note, there could be default arguments.
176
0
      assert(CCE->getNumArgs() >= 1 && "implicit construct expr should have 1 arg");
177
0
      E = CCE->getArg(0);
178
0
    } else
179
328k
      break;
180
336k
  }
181
182
328k
  if (const auto *DRE = dyn_cast<DeclRefExpr>(E))
183
321k
    if (const auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
184
321k
      if (NTTP->getDepth() == Depth)
185
321k
        return NTTP;
186
187
7.44k
  return nullptr;
188
328k
}
189
190
static const NonTypeTemplateParmDecl *
191
242k
getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) {
192
242k
  return getDeducedParameterFromExpr(E, Info.getDeducedDepth());
193
242k
}
194
195
/// Determine whether two declaration pointers refer to the same
196
/// declaration.
197
97
static bool isSameDeclaration(Decl *X, Decl *Y) {
198
97
  if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
199
97
    X = NX->getUnderlyingDecl();
200
97
  if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
201
97
    Y = NY->getUnderlyingDecl();
202
203
97
  return X->getCanonicalDecl() == Y->getCanonicalDecl();
204
97
}
205
206
/// Verify that the given, deduced template arguments are compatible.
207
///
208
/// \returns The deduced template argument, or a NULL template argument if
209
/// the deduced template arguments were incompatible.
210
static DeducedTemplateArgument
211
checkDeducedTemplateArguments(ASTContext &Context,
212
                              const DeducedTemplateArgument &X,
213
1.72M
                              const DeducedTemplateArgument &Y) {
214
  // We have no deduction for one or both of the arguments; they're compatible.
215
1.72M
  if (X.isNull())
216
1.63M
    return Y;
217
88.4k
  if (Y.isNull())
218
58
    return X;
219
220
  // If we have two non-type template argument values deduced for the same
221
  // parameter, they must both match the type of the parameter, and thus must
222
  // match each other's type. As we're only keeping one of them, we must check
223
  // for that now. The exception is that if either was deduced from an array
224
  // bound, the type is permitted to differ.
225
88.3k
  if (!X.wasDeducedFromArrayBound() && 
!Y.wasDeducedFromArrayBound()88.2k
) {
226
88.2k
    QualType XType = X.getNonTypeTemplateArgumentType();
227
88.2k
    if (!XType.isNull()) {
228
981
      QualType YType = Y.getNonTypeTemplateArgumentType();
229
981
      if (YType.isNull() || !Context.hasSameType(XType, YType))
230
24
        return DeducedTemplateArgument();
231
981
    }
232
88.2k
  }
233
234
88.3k
  switch (X.getKind()) {
235
0
  case TemplateArgument::Null:
236
0
    llvm_unreachable("Non-deduced template arguments handled above");
237
238
87.0k
  case TemplateArgument::Type:
239
    // If two template type arguments have the same type, they're compatible.
240
87.0k
    if (Y.getKind() == TemplateArgument::Type &&
241
87.0k
        Context.hasSameType(X.getAsType(), Y.getAsType()))
242
58.9k
      return X;
243
244
    // If one of the two arguments was deduced from an array bound, the other
245
    // supersedes it.
246
28.1k
    if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
247
25
      return X.wasDeducedFromArrayBound() ? 
Y3
:
X22
;
248
249
    // The arguments are not compatible.
250
28.1k
    return DeducedTemplateArgument();
251
252
221
  case TemplateArgument::Integral:
253
    // If we deduced a constant in one case and either a dependent expression or
254
    // declaration in another case, keep the integral constant.
255
    // If both are integral constants with the same value, keep that value.
256
221
    if (Y.getKind() == TemplateArgument::Expression ||
257
221
        Y.getKind() == TemplateArgument::Declaration ||
258
221
        (Y.getKind() == TemplateArgument::Integral &&
259
221
         hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
260
202
      return X.wasDeducedFromArrayBound() ? 
Y131
:
X71
;
261
262
    // All other combinations are incompatible.
263
19
    return DeducedTemplateArgument();
264
265
26
  case TemplateArgument::Template:
266
26
    if (Y.getKind() == TemplateArgument::Template &&
267
26
        Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
268
26
      return X;
269
270
    // All other combinations are incompatible.
271
0
    return DeducedTemplateArgument();
272
273
0
  case TemplateArgument::TemplateExpansion:
274
0
    if (Y.getKind() == TemplateArgument::TemplateExpansion &&
275
0
        Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
276
0
                                    Y.getAsTemplateOrTemplatePattern()))
277
0
      return X;
278
279
    // All other combinations are incompatible.
280
0
    return DeducedTemplateArgument();
281
282
876
  case TemplateArgument::Expression: {
283
876
    if (Y.getKind() != TemplateArgument::Expression)
284
0
      return checkDeducedTemplateArguments(Context, Y, X);
285
286
    // Compare the expressions for equality
287
876
    llvm::FoldingSetNodeID ID1, ID2;
288
876
    X.getAsExpr()->Profile(ID1, Context, true);
289
876
    Y.getAsExpr()->Profile(ID2, Context, true);
290
876
    if (ID1 == ID2)
291
0
      return X.wasDeducedFromArrayBound() ? Y : X;
292
293
    // Differing dependent expressions are incompatible.
294
876
    return DeducedTemplateArgument();
295
876
  }
296
297
9
  case TemplateArgument::Declaration:
298
9
    assert(!X.wasDeducedFromArrayBound());
299
300
    // If we deduced a declaration and a dependent expression, keep the
301
    // declaration.
302
9
    if (Y.getKind() == TemplateArgument::Expression)
303
0
      return X;
304
305
    // If we deduced a declaration and an integral constant, keep the
306
    // integral constant and whichever type did not come from an array
307
    // bound.
308
9
    if (Y.getKind() == TemplateArgument::Integral) {
309
0
      if (Y.wasDeducedFromArrayBound())
310
0
        return TemplateArgument(Context, Y.getAsIntegral(),
311
0
                                X.getParamTypeForDecl());
312
0
      return Y;
313
0
    }
314
315
    // If we deduced two declarations, make sure that they refer to the
316
    // same declaration.
317
9
    if (Y.getKind() == TemplateArgument::Declaration &&
318
9
        isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
319
6
      return X;
320
321
    // All other combinations are incompatible.
322
3
    return DeducedTemplateArgument();
323
324
0
  case TemplateArgument::NullPtr:
325
    // If we deduced a null pointer and a dependent expression, keep the
326
    // null pointer.
327
0
    if (Y.getKind() == TemplateArgument::Expression)
328
0
      return X;
329
330
    // If we deduced a null pointer and an integral constant, keep the
331
    // integral constant.
332
0
    if (Y.getKind() == TemplateArgument::Integral)
333
0
      return Y;
334
335
    // If we deduced two null pointers, they are the same.
336
0
    if (Y.getKind() == TemplateArgument::NullPtr)
337
0
      return X;
338
339
    // All other combinations are incompatible.
340
0
    return DeducedTemplateArgument();
341
342
129
  case TemplateArgument::Pack: {
343
129
    if (Y.getKind() != TemplateArgument::Pack ||
344
129
        X.pack_size() != Y.pack_size())
345
36
      return DeducedTemplateArgument();
346
347
93
    llvm::SmallVector<TemplateArgument, 8> NewPack;
348
93
    for (TemplateArgument::pack_iterator XA = X.pack_begin(),
349
93
                                      XAEnd = X.pack_end(),
350
93
                                         YA = Y.pack_begin();
351
233
         XA != XAEnd; 
++XA, ++YA140
) {
352
159
      TemplateArgument Merged = checkDeducedTemplateArguments(
353
159
          Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
354
159
          DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()));
355
159
      if (Merged.isNull() && 
!(23
XA->isNull()23
&&
YA->isNull()4
))
356
19
        return DeducedTemplateArgument();
357
140
      NewPack.push_back(Merged);
358
140
    }
359
360
74
    return DeducedTemplateArgument(
361
74
        TemplateArgument::CreatePackCopy(Context, NewPack),
362
74
        X.wasDeducedFromArrayBound() && 
Y.wasDeducedFromArrayBound()2
);
363
93
  }
364
88.3k
  }
365
366
0
  llvm_unreachable("Invalid TemplateArgument Kind!");
367
0
}
368
369
/// Deduce the value of the given non-type template parameter
370
/// as the given deduced template argument. All non-type template parameter
371
/// deduction is funneled through here.
372
static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
373
    Sema &S, TemplateParameterList *TemplateParams,
374
    const NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,
375
    QualType ValueType, TemplateDeductionInfo &Info,
376
242k
    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
377
242k
  assert(NTTP->getDepth() == Info.getDeducedDepth() &&
378
242k
         "deducing non-type template argument with wrong depth");
379
380
0
  DeducedTemplateArgument Result = checkDeducedTemplateArguments(
381
242k
      S.Context, Deduced[NTTP->getIndex()], NewDeduced);
382
242k
  if (Result.isNull()) {
383
921
    Info.Param = const_cast<NonTypeTemplateParmDecl*>(NTTP);
384
921
    Info.FirstArg = Deduced[NTTP->getIndex()];
385
921
    Info.SecondArg = NewDeduced;
386
921
    return Sema::TDK_Inconsistent;
387
921
  }
388
389
241k
  Deduced[NTTP->getIndex()] = Result;
390
241k
  if (!S.getLangOpts().CPlusPlus17)
391
236k
    return Sema::TDK_Success;
392
393
5.08k
  if (NTTP->isExpandedParameterPack())
394
    // FIXME: We may still need to deduce parts of the type here! But we
395
    // don't have any way to find which slice of the type to use, and the
396
    // type stored on the NTTP itself is nonsense. Perhaps the type of an
397
    // expanded NTTP should be a pack expansion type?
398
24
    return Sema::TDK_Success;
399
400
  // Get the type of the parameter for deduction. If it's a (dependent) array
401
  // or function type, we will not have decayed it yet, so do that now.
402
5.05k
  QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
403
5.05k
  if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
404
39
    ParamType = Expansion->getPattern();
405
406
  // FIXME: It's not clear how deduction of a parameter of reference
407
  // type from an argument (of non-reference type) should be performed.
408
  // For now, we just remove reference types from both sides and let
409
  // the final check for matching types sort out the mess.
410
5.05k
  ValueType = ValueType.getNonReferenceType();
411
5.05k
  if (ParamType->isReferenceType())
412
11
    ParamType = ParamType.getNonReferenceType();
413
5.04k
  else
414
    // Top-level cv-qualifiers are irrelevant for a non-reference type.
415
5.04k
    ValueType = ValueType.getUnqualifiedType();
416
417
5.05k
  return DeduceTemplateArgumentsByTypeMatch(
418
5.05k
      S, TemplateParams, ParamType, ValueType, Info, Deduced,
419
5.05k
      TDF_SkipNonDependent, /*PartialOrdering=*/false,
420
5.05k
      /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());
421
5.08k
}
422
423
/// Deduce the value of the given non-type template parameter
424
/// from the given integral constant.
425
static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
426
    Sema &S, TemplateParameterList *TemplateParams,
427
    const NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
428
    QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
429
169k
    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
430
169k
  return DeduceNonTypeTemplateArgument(
431
169k
      S, TemplateParams, NTTP,
432
169k
      DeducedTemplateArgument(S.Context, Value, ValueType,
433
169k
                              DeducedFromArrayBound),
434
169k
      ValueType, Info, Deduced);
435
169k
}
436
437
/// Deduce the value of the given non-type template parameter
438
/// from the given null pointer template argument type.
439
static Sema::TemplateDeductionResult DeduceNullPtrTemplateArgument(
440
    Sema &S, TemplateParameterList *TemplateParams,
441
    const NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
442
    TemplateDeductionInfo &Info,
443
39
    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
444
39
  Expr *Value = S.ImpCastExprToType(
445
39
                     new (S.Context) CXXNullPtrLiteralExpr(S.Context.NullPtrTy,
446
39
                                                           NTTP->getLocation()),
447
39
                     NullPtrType,
448
39
                     NullPtrType->isMemberPointerType() ? 
CK_NullToMemberPointer4
449
39
                                                        : 
CK_NullToPointer35
)
450
39
                    .get();
451
39
  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
452
39
                                       DeducedTemplateArgument(Value),
453
39
                                       Value->getType(), Info, Deduced);
454
39
}
455
456
/// Deduce the value of the given non-type template parameter
457
/// from the given type- or value-dependent expression.
458
///
459
/// \returns true if deduction succeeded, false otherwise.
460
static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
461
    Sema &S, TemplateParameterList *TemplateParams,
462
    const NonTypeTemplateParmDecl *NTTP, Expr *Value, TemplateDeductionInfo &Info,
463
71.0k
    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
464
71.0k
  return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
465
71.0k
                                       DeducedTemplateArgument(Value),
466
71.0k
                                       Value->getType(), Info, Deduced);
467
71.0k
}
468
469
/// Deduce the value of the given non-type template parameter
470
/// from the given declaration.
471
///
472
/// \returns true if deduction succeeded, false otherwise.
473
static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
474
    Sema &S, TemplateParameterList *TemplateParams,
475
    const NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T,
476
    TemplateDeductionInfo &Info,
477
1.19k
    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
478
1.19k
  D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : 
nullptr0
;
479
1.19k
  TemplateArgument New(D, T);
480
1.19k
  return DeduceNonTypeTemplateArgument(
481
1.19k
      S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
482
1.19k
}
483
484
static Sema::TemplateDeductionResult
485
DeduceTemplateArguments(Sema &S,
486
                        TemplateParameterList *TemplateParams,
487
                        TemplateName Param,
488
                        TemplateName Arg,
489
                        TemplateDeductionInfo &Info,
490
666k
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
491
666k
  TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
492
666k
  if (!ParamDecl) {
493
    // The parameter type is dependent and is not a template template parameter,
494
    // so there is nothing that we can deduce.
495
12
    return Sema::TDK_Success;
496
12
  }
497
498
666k
  if (TemplateTemplateParmDecl *TempParam
499
666k
        = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
500
    // If we're not deducing at this depth, there's nothing to deduce.
501
2.88k
    if (TempParam->getDepth() != Info.getDeducedDepth())
502
0
      return Sema::TDK_Success;
503
504
2.88k
    DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
505
2.88k
    DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
506
2.88k
                                                 Deduced[TempParam->getIndex()],
507
2.88k
                                                                   NewDeduced);
508
2.88k
    if (Result.isNull()) {
509
0
      Info.Param = TempParam;
510
0
      Info.FirstArg = Deduced[TempParam->getIndex()];
511
0
      Info.SecondArg = NewDeduced;
512
0
      return Sema::TDK_Inconsistent;
513
0
    }
514
515
2.88k
    Deduced[TempParam->getIndex()] = Result;
516
2.88k
    return Sema::TDK_Success;
517
2.88k
  }
518
519
  // Verify that the two template names are equivalent.
520
663k
  if (S.Context.hasSameTemplateName(Param, Arg))
521
509k
    return Sema::TDK_Success;
522
523
  // Mismatch of non-dependent template parameter to argument.
524
154k
  Info.FirstArg = TemplateArgument(Param);
525
154k
  Info.SecondArg = TemplateArgument(Arg);
526
154k
  return Sema::TDK_NonDeducedMismatch;
527
663k
}
528
529
/// Deduce the template arguments by comparing the template parameter
530
/// type (which is a template-id) with the template argument type.
531
///
532
/// \param S the Sema
533
///
534
/// \param TemplateParams the template parameters that we are deducing
535
///
536
/// \param Param the parameter type
537
///
538
/// \param Arg the argument type
539
///
540
/// \param Info information about the template argument deduction itself
541
///
542
/// \param Deduced the deduced template arguments
543
///
544
/// \returns the result of template argument deduction so far. Note that a
545
/// "success" result means that template argument deduction has not yet failed,
546
/// but it may still fail, later, for other reasons.
547
static Sema::TemplateDeductionResult
548
DeduceTemplateSpecArguments(Sema &S, TemplateParameterList *TemplateParams,
549
                            const QualType P, QualType A,
550
                            TemplateDeductionInfo &Info,
551
1.23M
                            SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
552
1.23M
  QualType UP = P;
553
1.23M
  if (const auto *IP = P->getAs<InjectedClassNameType>())
554
312
    UP = IP->getInjectedSpecializationType();
555
  // FIXME: Try to preserve type sugar here, which is hard
556
  // because of the unresolved template arguments.
557
1.23M
  const auto *TP = UP.getCanonicalType()->castAs<TemplateSpecializationType>();
558
1.23M
  ArrayRef<TemplateArgument> PResolved = TP->template_arguments();
559
560
1.23M
  QualType UA = A;
561
  // Treat an injected-class-name as its underlying template-id.
562
1.23M
  if (const auto *Injected = A->getAs<InjectedClassNameType>())
563
14
    UA = Injected->getInjectedSpecializationType();
564
565
  // Check whether the template argument is a dependent template-id.
566
  // FIXME: Should not lose sugar here.
567
1.23M
  if (const auto *SA =
568
1.23M
          dyn_cast<TemplateSpecializationType>(UA.getCanonicalType())) {
569
    // Perform template argument deduction for the template name.
570
353k
    if (auto Result =
571
353k
            DeduceTemplateArguments(S, TemplateParams, TP->getTemplateName(),
572
353k
                                    SA->getTemplateName(), Info, Deduced))
573
6
      return Result;
574
    // Perform template argument deduction on each template
575
    // argument. Ignore any missing/extra arguments, since they could be
576
    // filled in by default arguments.
577
353k
    return DeduceTemplateArguments(S, TemplateParams, PResolved,
578
353k
                                   SA->template_arguments(), Info, Deduced,
579
353k
                                   /*NumberOfArgumentsMustMatch=*/false);
580
353k
  }
581
582
  // If the argument type is a class template specialization, we
583
  // perform template argument deduction using its template
584
  // arguments.
585
881k
  const auto *RA = UA->getAs<RecordType>();
586
881k
  const auto *SA =
587
881k
      RA ? 
dyn_cast<ClassTemplateSpecializationDecl>(RA->getDecl())426k
:
nullptr455k
;
588
881k
  if (!SA) {
589
568k
    Info.FirstArg = TemplateArgument(P);
590
568k
    Info.SecondArg = TemplateArgument(A);
591
568k
    return Sema::TDK_NonDeducedMismatch;
592
568k
  }
593
594
  // Perform template argument deduction for the template name.
595
313k
  if (auto Result = DeduceTemplateArguments(
596
313k
          S, TemplateParams, TP->getTemplateName(),
597
313k
          TemplateName(SA->getSpecializedTemplate()), Info, Deduced))
598
154k
    return Result;
599
600
  // Perform template argument deduction for the template arguments.
601
158k
  return DeduceTemplateArguments(S, TemplateParams, PResolved,
602
158k
                                 SA->getTemplateArgs().asArray(), Info, Deduced,
603
158k
                                 /*NumberOfArgumentsMustMatch=*/true);
604
313k
}
605
606
1.20M
static bool IsPossiblyOpaquelyQualifiedTypeInternal(const Type *T) {
607
1.20M
  assert(T->isCanonicalUnqualified());
608
609
0
  switch (T->getTypeClass()) {
610
0
  case Type::TypeOfExpr:
611
0
  case Type::TypeOf:
612
101k
  case Type::DependentName:
613
108k
  case Type::Decltype:
614
108k
  case Type::UnresolvedUsing:
615
155k
  case Type::TemplateTypeParm:
616
155k
    return true;
617
618
23
  case Type::ConstantArray:
619
25.2k
  case Type::IncompleteArray:
620
25.2k
  case Type::VariableArray:
621
46.7k
  case Type::DependentSizedArray:
622
46.7k
    return IsPossiblyOpaquelyQualifiedTypeInternal(
623
46.7k
        cast<ArrayType>(T)->getElementType().getTypePtr());
624
625
1.00M
  default:
626
1.00M
    return false;
627
1.20M
  }
628
1.20M
}
629
630
/// Determines whether the given type is an opaque type that
631
/// might be more qualified when instantiated.
632
1.16M
static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
633
1.16M
  return IsPossiblyOpaquelyQualifiedTypeInternal(
634
1.16M
      T->getCanonicalTypeInternal().getTypePtr());
635
1.16M
}
636
637
/// Helper function to build a TemplateParameter when we don't
638
/// know its type statically.
639
80.2k
static TemplateParameter makeTemplateParameter(Decl *D) {
640
80.2k
  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
641
68.6k
    return TemplateParameter(TTP);
642
11.6k
  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
643
11.5k
    return TemplateParameter(NTTP);
644
645
27
  return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
646
11.6k
}
647
648
/// A pack that we're currently deducing.
649
struct clang::DeducedPack {
650
  // The index of the pack.
651
  unsigned Index;
652
653
  // The old value of the pack before we started deducing it.
654
  DeducedTemplateArgument Saved;
655
656
  // A deferred value of this pack from an inner deduction, that couldn't be
657
  // deduced because this deduction hadn't happened yet.
658
  DeducedTemplateArgument DeferredDeduction;
659
660
  // The new value of the pack.
661
  SmallVector<DeducedTemplateArgument, 4> New;
662
663
  // The outer deduction for this pack, if any.
664
  DeducedPack *Outer = nullptr;
665
666
60.8k
  DeducedPack(unsigned Index) : Index(Index) {}
667
};
668
669
namespace {
670
671
/// A scope in which we're performing pack deduction.
672
class PackDeductionScope {
673
public:
674
  /// Prepare to deduce the packs named within Pattern.
675
  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
676
                     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
677
                     TemplateDeductionInfo &Info, TemplateArgument Pattern)
678
42.8k
      : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
679
42.8k
    unsigned NumNamedPacks = addPacks(Pattern);
680
42.8k
    finishConstruction(NumNamedPacks);
681
42.8k
  }
682
683
  /// Prepare to directly deduce arguments of the parameter with index \p Index.
684
  PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
685
                     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
686
                     TemplateDeductionInfo &Info, unsigned Index)
687
17.9k
      : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
688
17.9k
    addPack(Index);
689
17.9k
    finishConstruction(1);
690
17.9k
  }
691
692
private:
693
60.8k
  void addPack(unsigned Index) {
694
    // Save the deduced template argument for the parameter pack expanded
695
    // by this pack expansion, then clear out the deduction.
696
60.8k
    DeducedPack Pack(Index);
697
60.8k
    Pack.Saved = Deduced[Index];
698
60.8k
    Deduced[Index] = TemplateArgument();
699
700
    // FIXME: What if we encounter multiple packs with different numbers of
701
    // pre-expanded expansions? (This should already have been diagnosed
702
    // during substitution.)
703
60.8k
    if (Optional<unsigned> ExpandedPackExpansions =
704
60.8k
            getExpandedPackSize(TemplateParams->getParam(Index)))
705
27
      FixedNumExpansions = ExpandedPackExpansions;
706
707
60.8k
    Packs.push_back(Pack);
708
60.8k
  }
709
710
42.8k
  unsigned addPacks(TemplateArgument Pattern) {
711
    // Compute the set of template parameter indices that correspond to
712
    // parameter packs expanded by the pack expansion.
713
42.8k
    llvm::SmallBitVector SawIndices(TemplateParams->size());
714
42.8k
    llvm::SmallVector<TemplateArgument, 4> ExtraDeductions;
715
716
42.9k
    auto AddPack = [&](unsigned Index) {
717
42.9k
      if (SawIndices[Index])
718
7
        return;
719
42.9k
      SawIndices[Index] = true;
720
42.9k
      addPack(Index);
721
722
      // Deducing a parameter pack that is a pack expansion also constrains the
723
      // packs appearing in that parameter to have the same deduced arity. Also,
724
      // in C++17 onwards, deducing a non-type template parameter deduces its
725
      // type, so we need to collect the pending deduced values for those packs.
726
42.9k
      if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(
727
42.9k
              TemplateParams->getParam(Index))) {
728
3.23k
        if (!NTTP->isExpandedParameterPack())
729
3.23k
          if (auto *Expansion = dyn_cast<PackExpansionType>(NTTP->getType()))
730
21
            ExtraDeductions.push_back(Expansion->getPattern());
731
3.23k
      }
732
      // FIXME: Also collect the unexpanded packs in any type and template
733
      // parameter packs that are pack expansions.
734
42.9k
    };
735
736
42.9k
    auto Collect = [&](TemplateArgument Pattern) {
737
42.9k
      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
738
42.9k
      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
739
85.8k
      for (unsigned I = 0, N = Unexpanded.size(); I != N; 
++I42.9k
) {
740
42.9k
        unsigned Depth, Index;
741
42.9k
        std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
742
42.9k
        if (Depth == Info.getDeducedDepth())
743
42.9k
          AddPack(Index);
744
42.9k
      }
745
42.9k
    };
746
747
    // Look for unexpanded packs in the pattern.
748
42.8k
    Collect(Pattern);
749
42.8k
    assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
750
751
0
    unsigned NumNamedPacks = Packs.size();
752
753
    // Also look for unexpanded packs that are indirectly deduced by deducing
754
    // the sizes of the packs in this pattern.
755
42.9k
    while (!ExtraDeductions.empty())
756
21
      Collect(ExtraDeductions.pop_back_val());
757
758
42.8k
    return NumNamedPacks;
759
42.8k
  }
760
761
60.8k
  void finishConstruction(unsigned NumNamedPacks) {
762
    // Dig out the partially-substituted pack, if there is one.
763
60.8k
    const TemplateArgument *PartialPackArgs = nullptr;
764
60.8k
    unsigned NumPartialPackArgs = 0;
765
60.8k
    std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
766
60.8k
    if (auto *Scope = S.CurrentInstantiationScope)
767
52.1k
      if (auto *Partial = Scope->getPartiallySubstitutedPack(
768
52.1k
              &PartialPackArgs, &NumPartialPackArgs))
769
18.1k
        PartialPackDepthIndex = getDepthAndIndex(Partial);
770
771
    // This pack expansion will have been partially or fully expanded if
772
    // it only names explicitly-specified parameter packs (including the
773
    // partially-substituted one, if any).
774
60.8k
    bool IsExpanded = true;
775
78.9k
    for (unsigned I = 0; I != NumNamedPacks; 
++I18.0k
) {
776
60.8k
      if (Packs[I].Index >= Info.getNumExplicitArgs()) {
777
42.7k
        IsExpanded = false;
778
42.7k
        IsPartiallyExpanded = false;
779
42.7k
        break;
780
42.7k
      }
781
18.0k
      if (PartialPackDepthIndex ==
782
18.0k
            std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
783
18.0k
        IsPartiallyExpanded = true;
784
18.0k
      }
785
18.0k
    }
786
787
    // Skip over the pack elements that were expanded into separate arguments.
788
    // If we partially expanded, this is the number of partial arguments.
789
60.8k
    if (IsPartiallyExpanded)
790
18.0k
      PackElements += NumPartialPackArgs;
791
42.7k
    else if (IsExpanded)
792
0
      PackElements += *FixedNumExpansions;
793
794
60.8k
    for (auto &Pack : Packs) {
795
60.8k
      if (Info.PendingDeducedPacks.size() > Pack.Index)
796
611
        Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
797
60.2k
      else
798
60.2k
        Info.PendingDeducedPacks.resize(Pack.Index + 1);
799
60.8k
      Info.PendingDeducedPacks[Pack.Index] = &Pack;
800
801
60.8k
      if (PartialPackDepthIndex ==
802
60.8k
            std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
803
18.0k
        Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
804
        // We pre-populate the deduced value of the partially-substituted
805
        // pack with the specified value. This is not entirely correct: the
806
        // value is supposed to have been substituted, not deduced, but the
807
        // cases where this is observable require an exact type match anyway.
808
        //
809
        // FIXME: If we could represent a "depth i, index j, pack elem k"
810
        // parameter, we could substitute the partially-substituted pack
811
        // everywhere and avoid this.
812
18.0k
        if (!IsPartiallyExpanded)
813
0
          Deduced[Pack.Index] = Pack.New[PackElements];
814
18.0k
      }
815
60.8k
    }
816
60.8k
  }
817
818
public:
819
60.8k
  ~PackDeductionScope() {
820
60.8k
    for (auto &Pack : Packs)
821
60.8k
      Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
822
60.8k
  }
823
824
  /// Determine whether this pack has already been partially expanded into a
825
  /// sequence of (prior) function parameters / template arguments.
826
12
  bool isPartiallyExpanded() { return IsPartiallyExpanded; }
827
828
  /// Determine whether this pack expansion scope has a known, fixed arity.
829
  /// This happens if it involves a pack from an outer template that has
830
  /// (notionally) already been expanded.
831
173
  bool hasFixedArity() { return FixedNumExpansions.hasValue(); }
832
833
  /// Determine whether the next element of the argument is still part of this
834
  /// pack. This is the case unless the pack is already expanded to a fixed
835
  /// length.
836
139k
  bool hasNextElement() {
837
139k
    return !FixedNumExpansions || 
*FixedNumExpansions > PackElements34
;
838
139k
  }
839
840
  /// Move to deducing the next element in each pack that is being deduced.
841
139k
  void nextPackElement() {
842
    // Capture the deduced template arguments for each parameter pack expanded
843
    // by this pack expansion, add them to the list of arguments we've deduced
844
    // for that pack, then clear out the deduced argument.
845
139k
    for (auto &Pack : Packs) {
846
139k
      DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
847
139k
      if (!Pack.New.empty() || 
!DeducedArg.isNull()33.2k
) {
848
139k
        while (Pack.New.size() < PackElements)
849
44
          Pack.New.push_back(DeducedTemplateArgument());
850
138k
        if (Pack.New.size() == PackElements)
851
138k
          Pack.New.push_back(DeducedArg);
852
0
        else
853
0
          Pack.New[PackElements] = DeducedArg;
854
138k
        DeducedArg = Pack.New.size() > PackElements + 1
855
138k
                         ? 
Pack.New[PackElements + 1]0
856
138k
                         : DeducedTemplateArgument();
857
138k
      }
858
139k
    }
859
139k
    ++PackElements;
860
139k
  }
861
862
  /// Finish template argument deduction for a set of argument packs,
863
  /// producing the argument packs and checking for consistency with prior
864
  /// deductions.
865
60.7k
  Sema::TemplateDeductionResult finish() {
866
    // Build argument packs for each of the parameter packs expanded by this
867
    // pack expansion.
868
60.8k
    for (auto &Pack : Packs) {
869
      // Put back the old value for this pack.
870
60.8k
      Deduced[Pack.Index] = Pack.Saved;
871
872
      // Always make sure the size of this pack is correct, even if we didn't
873
      // deduce any values for it.
874
      //
875
      // FIXME: This isn't required by the normative wording, but substitution
876
      // and post-substitution checking will always fail if the arity of any
877
      // pack is not equal to the number of elements we processed. (Either that
878
      // or something else has gone *very* wrong.) We're permitted to skip any
879
      // hard errors from those follow-on steps by the intent (but not the
880
      // wording) of C++ [temp.inst]p8:
881
      //
882
      //   If the function selected by overload resolution can be determined
883
      //   without instantiating a class template definition, it is unspecified
884
      //   whether that instantiation actually takes place
885
60.8k
      Pack.New.resize(PackElements);
886
887
      // Build or find a new value for this pack.
888
60.8k
      DeducedTemplateArgument NewPack;
889
60.8k
      if (Pack.New.empty()) {
890
        // If we deduced an empty argument pack, create it now.
891
9.53k
        NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
892
51.2k
      } else {
893
51.2k
        TemplateArgument *ArgumentPack =
894
51.2k
            new (S.Context) TemplateArgument[Pack.New.size()];
895
51.2k
        std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
896
51.2k
        NewPack = DeducedTemplateArgument(
897
51.2k
            TemplateArgument(llvm::makeArrayRef(ArgumentPack, Pack.New.size())),
898
            // FIXME: This is wrong, it's possible that some pack elements are
899
            // deduced from an array bound and others are not:
900
            //   template<typename ...T, T ...V> void g(const T (&...p)[V]);
901
            //   g({1, 2, 3}, {{}, {}});
902
            // ... should deduce T = {int, size_t (from array bound)}.
903
51.2k
            Pack.New[0].wasDeducedFromArrayBound());
904
51.2k
      }
905
906
      // Pick where we're going to put the merged pack.
907
60.8k
      DeducedTemplateArgument *Loc;
908
60.8k
      if (Pack.Outer) {
909
17
        if (Pack.Outer->DeferredDeduction.isNull()) {
910
          // Defer checking this pack until we have a complete pack to compare
911
          // it against.
912
8
          Pack.Outer->DeferredDeduction = NewPack;
913
8
          continue;
914
8
        }
915
9
        Loc = &Pack.Outer->DeferredDeduction;
916
60.8k
      } else {
917
60.8k
        Loc = &Deduced[Pack.Index];
918
60.8k
      }
919
920
      // Check the new pack matches any previous value.
921
60.8k
      DeducedTemplateArgument OldPack = *Loc;
922
60.8k
      DeducedTemplateArgument Result =
923
60.8k
          checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
924
925
      // If we deferred a deduction of this pack, check that one now too.
926
60.8k
      if (!Result.isNull() && 
!Pack.DeferredDeduction.isNull()60.7k
) {
927
5
        OldPack = Result;
928
5
        NewPack = Pack.DeferredDeduction;
929
5
        Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
930
5
      }
931
932
60.8k
      NamedDecl *Param = TemplateParams->getParam(Pack.Index);
933
60.8k
      if (Result.isNull()) {
934
55
        Info.Param = makeTemplateParameter(Param);
935
55
        Info.FirstArg = OldPack;
936
55
        Info.SecondArg = NewPack;
937
55
        return Sema::TDK_Inconsistent;
938
55
      }
939
940
      // If we have a pre-expanded pack and we didn't deduce enough elements
941
      // for it, fail deduction.
942
60.7k
      if (Optional<unsigned> Expansions = getExpandedPackSize(Param)) {
943
27
        if (*Expansions != PackElements) {
944
9
          Info.Param = makeTemplateParameter(Param);
945
9
          Info.FirstArg = Result;
946
9
          return Sema::TDK_IncompletePack;
947
9
        }
948
27
      }
949
950
60.7k
      *Loc = Result;
951
60.7k
    }
952
953
60.7k
    return Sema::TDK_Success;
954
60.7k
  }
955
956
private:
957
  Sema &S;
958
  TemplateParameterList *TemplateParams;
959
  SmallVectorImpl<DeducedTemplateArgument> &Deduced;
960
  TemplateDeductionInfo &Info;
961
  unsigned PackElements = 0;
962
  bool IsPartiallyExpanded = false;
963
  /// The number of expansions, if we have a fully-expanded pack in this scope.
964
  Optional<unsigned> FixedNumExpansions;
965
966
  SmallVector<DeducedPack, 2> Packs;
967
};
968
969
} // namespace
970
971
/// Deduce the template arguments by comparing the list of parameter
972
/// types to the list of argument types, as in the parameter-type-lists of
973
/// function types (C++ [temp.deduct.type]p10).
974
///
975
/// \param S The semantic analysis object within which we are deducing
976
///
977
/// \param TemplateParams The template parameters that we are deducing
978
///
979
/// \param Params The list of parameter types
980
///
981
/// \param NumParams The number of types in \c Params
982
///
983
/// \param Args The list of argument types
984
///
985
/// \param NumArgs The number of types in \c Args
986
///
987
/// \param Info information about the template argument deduction itself
988
///
989
/// \param Deduced the deduced template arguments
990
///
991
/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
992
/// how template argument deduction is performed.
993
///
994
/// \param PartialOrdering If true, we are performing template argument
995
/// deduction for during partial ordering for a call
996
/// (C++0x [temp.deduct.partial]).
997
///
998
/// \returns the result of template argument deduction so far. Note that a
999
/// "success" result means that template argument deduction has not yet failed,
1000
/// but it may still fail, later, for other reasons.
1001
static Sema::TemplateDeductionResult
1002
DeduceTemplateArguments(Sema &S,
1003
                        TemplateParameterList *TemplateParams,
1004
                        const QualType *Params, unsigned NumParams,
1005
                        const QualType *Args, unsigned NumArgs,
1006
                        TemplateDeductionInfo &Info,
1007
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1008
                        unsigned TDF,
1009
106k
                        bool PartialOrdering = false) {
1010
  // C++0x [temp.deduct.type]p10:
1011
  //   Similarly, if P has a form that contains (T), then each parameter type
1012
  //   Pi of the respective parameter-type- list of P is compared with the
1013
  //   corresponding parameter type Ai of the corresponding parameter-type-list
1014
  //   of A. [...]
1015
106k
  unsigned ArgIdx = 0, ParamIdx = 0;
1016
203k
  for (; ParamIdx != NumParams; 
++ParamIdx97.3k
) {
1017
    // Check argument types.
1018
178k
    const PackExpansionType *Expansion
1019
178k
                                = dyn_cast<PackExpansionType>(Params[ParamIdx]);
1020
178k
    if (!Expansion) {
1021
      // Simple case: compare the parameter and argument types at this point.
1022
1023
      // Make sure we have an argument.
1024
176k
      if (ArgIdx >= NumArgs)
1025
6.43k
        return Sema::TDK_MiscellaneousDeductionFailure;
1026
1027
170k
      if (isa<PackExpansionType>(Args[ArgIdx])) {
1028
        // C++0x [temp.deduct.type]p22:
1029
        //   If the original function parameter associated with A is a function
1030
        //   parameter pack and the function parameter associated with P is not
1031
        //   a function parameter pack, then template argument deduction fails.
1032
556
        return Sema::TDK_MiscellaneousDeductionFailure;
1033
556
      }
1034
1035
169k
      if (Sema::TemplateDeductionResult Result =
1036
169k
              DeduceTemplateArgumentsByTypeMatch(
1037
169k
                  S, TemplateParams, Params[ParamIdx].getUnqualifiedType(),
1038
169k
                  Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1039
169k
                  PartialOrdering,
1040
169k
                  /*DeducedFromArrayBound=*/false))
1041
73.7k
        return Result;
1042
1043
96.1k
      ++ArgIdx;
1044
96.1k
      continue;
1045
169k
    }
1046
1047
    // C++0x [temp.deduct.type]p10:
1048
    //   If the parameter-declaration corresponding to Pi is a function
1049
    //   parameter pack, then the type of its declarator- id is compared with
1050
    //   each remaining parameter type in the parameter-type-list of A. Each
1051
    //   comparison deduces template arguments for subsequent positions in the
1052
    //   template parameter packs expanded by the function parameter pack.
1053
1054
1.18k
    QualType Pattern = Expansion->getPattern();
1055
1.18k
    PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1056
1057
    // A pack scope with fixed arity is not really a pack any more, so is not
1058
    // a non-deduced context.
1059
1.18k
    if (ParamIdx + 1 == NumParams || 
PackScope.hasFixedArity()9
) {
1060
2.96k
      for (; ArgIdx < NumArgs && 
PackScope.hasNextElement()1.79k
;
++ArgIdx1.78k
) {
1061
        // Deduce template arguments from the pattern.
1062
1.79k
        if (Sema::TemplateDeductionResult Result =
1063
1.79k
                DeduceTemplateArgumentsByTypeMatch(
1064
1.79k
                    S, TemplateParams, Pattern.getUnqualifiedType(),
1065
1.79k
                    Args[ArgIdx].getUnqualifiedType(), Info, Deduced, TDF,
1066
1.79k
                    PartialOrdering, /*DeducedFromArrayBound=*/false))
1067
5
          return Result;
1068
1069
1.78k
        PackScope.nextPackElement();
1070
1.78k
      }
1071
1.17k
    } else {
1072
      // C++0x [temp.deduct.type]p5:
1073
      //   The non-deduced contexts are:
1074
      //     - A function parameter pack that does not occur at the end of the
1075
      //       parameter-declaration-clause.
1076
      //
1077
      // FIXME: There is no wording to say what we should do in this case. We
1078
      // choose to resolve this by applying the same rule that is applied for a
1079
      // function call: that is, deduce all contained packs to their
1080
      // explicitly-specified values (or to <> if there is no such value).
1081
      //
1082
      // This is seemingly-arbitrarily different from the case of a template-id
1083
      // with a non-trailing pack-expansion in its arguments, which renders the
1084
      // entire template-argument-list a non-deduced context.
1085
1086
      // If the parameter type contains an explicitly-specified pack that we
1087
      // could not expand, skip the number of parameters notionally created
1088
      // by the expansion.
1089
9
      Optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1090
9
      if (NumExpansions && 
!PackScope.isPartiallyExpanded()0
) {
1091
0
        for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1092
0
             ++I, ++ArgIdx)
1093
0
          PackScope.nextPackElement();
1094
0
      }
1095
9
    }
1096
1097
    // Build argument packs for each of the parameter packs expanded by this
1098
    // pack expansion.
1099
1.17k
    if (auto Result = PackScope.finish())
1100
2
      return Result;
1101
1.17k
  }
1102
1103
  // Make sure we don't have any extra arguments.
1104
25.5k
  if (ArgIdx < NumArgs)
1105
4.47k
    return Sema::TDK_MiscellaneousDeductionFailure;
1106
1107
21.0k
  return Sema::TDK_Success;
1108
25.5k
}
1109
1110
/// Determine whether the parameter has qualifiers that the argument
1111
/// lacks. Put another way, determine whether there is no way to add
1112
/// a deduced set of qualifiers to the ParamType that would result in
1113
/// its qualifiers matching those of the ArgType.
1114
static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
1115
2.02M
                                                  QualType ArgType) {
1116
2.02M
  Qualifiers ParamQs = ParamType.getQualifiers();
1117
2.02M
  Qualifiers ArgQs = ArgType.getQualifiers();
1118
1119
2.02M
  if (ParamQs == ArgQs)
1120
1.91M
    return false;
1121
1122
  // Mismatched (but not missing) Objective-C GC attributes.
1123
110k
  if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1124
110k
      
ParamQs.hasObjCGCAttr()0
)
1125
0
    return true;
1126
1127
  // Mismatched (but not missing) address spaces.
1128
110k
  if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1129
110k
      
ParamQs.hasAddressSpace()216
)
1130
140
    return true;
1131
1132
  // Mismatched (but not missing) Objective-C lifetime qualifiers.
1133
110k
  if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1134
110k
      
ParamQs.hasObjCLifetime()139
)
1135
85
    return true;
1136
1137
  // CVR qualifiers inconsistent or a superset.
1138
110k
  return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1139
110k
}
1140
1141
/// Compare types for equality with respect to possibly compatible
1142
/// function types (noreturn adjustment, implicit calling conventions). If any
1143
/// of parameter and argument is not a function, just perform type comparison.
1144
///
1145
/// \param P the template parameter type.
1146
///
1147
/// \param A the argument type.
1148
18.1k
bool Sema::isSameOrCompatibleFunctionType(QualType P, QualType A) {
1149
18.1k
  const FunctionType *PF = P->getAs<FunctionType>(),
1150
18.1k
                     *AF = A->getAs<FunctionType>();
1151
1152
  // Just compare if not functions.
1153
18.1k
  if (!PF || !AF)
1154
0
    return Context.hasSameType(P, A);
1155
1156
  // Noreturn and noexcept adjustment.
1157
18.1k
  QualType AdjustedParam;
1158
18.1k
  if (IsFunctionConversion(P, A, AdjustedParam))
1159
270
    return Context.hasSameType(AdjustedParam, A);
1160
1161
  // FIXME: Compatible calling conventions.
1162
1163
17.8k
  return Context.hasSameType(P, A);
1164
18.1k
}
1165
1166
/// Get the index of the first template parameter that was originally from the
1167
/// innermost template-parameter-list. This is 0 except when we concatenate
1168
/// the template parameter lists of a class template and a constructor template
1169
/// when forming an implicit deduction guide.
1170
1.33M
static unsigned getFirstInnerIndex(FunctionTemplateDecl *FTD) {
1171
1.33M
  auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1172
1.33M
  if (!Guide || 
!Guide->isImplicit()1.08k
)
1173
1.33M
    return 0;
1174
912
  return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1175
1.33M
}
1176
1177
/// Determine whether a type denotes a forwarding reference.
1178
925k
static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1179
  // C++1z [temp.deduct.call]p3:
1180
  //   A forwarding reference is an rvalue reference to a cv-unqualified
1181
  //   template parameter that does not represent a template parameter of a
1182
  //   class template.
1183
925k
  if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1184
91.6k
    if (ParamRef->getPointeeType().getQualifiers())
1185
4.14k
      return false;
1186
87.5k
    auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1187
87.5k
    return TypeParm && 
TypeParm->getIndex() >= FirstInnerIndex62.5k
;
1188
91.6k
  }
1189
833k
  return false;
1190
925k
}
1191
1192
276k
static CXXRecordDecl *getCanonicalRD(QualType T) {
1193
276k
  return cast<CXXRecordDecl>(
1194
276k
      T->castAs<RecordType>()->getDecl()->getCanonicalDecl());
1195
276k
}
1196
1197
///  Attempt to deduce the template arguments by checking the base types
1198
///  according to (C++20 [temp.deduct.call] p4b3.
1199
///
1200
/// \param S the semantic analysis object within which we are deducing.
1201
///
1202
/// \param RecordT the top level record object we are deducing against.
1203
///
1204
/// \param TemplateParams the template parameters that we are deducing.
1205
///
1206
/// \param SpecParam the template specialization parameter type.
1207
///
1208
/// \param Info information about the template argument deduction itself.
1209
///
1210
/// \param Deduced the deduced template arguments.
1211
///
1212
/// \returns the result of template argument deduction with the bases. "invalid"
1213
/// means no matches, "success" found a single item, and the
1214
/// "MiscellaneousDeductionFailure" result happens when the match is ambiguous.
1215
static Sema::TemplateDeductionResult
1216
DeduceTemplateBases(Sema &S, const CXXRecordDecl *RD,
1217
                    TemplateParameterList *TemplateParams, QualType P,
1218
                    TemplateDeductionInfo &Info,
1219
219k
                    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1220
  // C++14 [temp.deduct.call] p4b3:
1221
  //   If P is a class and P has the form simple-template-id, then the
1222
  //   transformed A can be a derived class of the deduced A. Likewise if
1223
  //   P is a pointer to a class of the form simple-template-id, the
1224
  //   transformed A can be a pointer to a derived class pointed to by the
1225
  //   deduced A. However, if there is a class C that is a (direct or
1226
  //   indirect) base class of D and derived (directly or indirectly) from a
1227
  //   class B and that would be a valid deduced A, the deduced A cannot be
1228
  //   B or pointer to B, respectively.
1229
  //
1230
  //   These alternatives are considered only if type deduction would
1231
  //   otherwise fail. If they yield more than one possible deduced A, the
1232
  //   type deduction fails.
1233
1234
  // Use a breadth-first search through the bases to collect the set of
1235
  // successful matches. Visited contains the set of nodes we have already
1236
  // visited, while ToVisit is our stack of records that we still need to
1237
  // visit.  Matches contains a list of matches that have yet to be
1238
  // disqualified.
1239
219k
  llvm::SmallPtrSet<const CXXRecordDecl *, 8> Visited;
1240
219k
  SmallVector<QualType, 8> ToVisit;
1241
  // We iterate over this later, so we have to use MapVector to ensure
1242
  // determinism.
1243
219k
  llvm::MapVector<const CXXRecordDecl *,
1244
219k
                  SmallVector<DeducedTemplateArgument, 8>>
1245
219k
      Matches;
1246
1247
239k
  auto AddBases = [&Visited, &ToVisit](const CXXRecordDecl *RD) {
1248
239k
    for (const auto &Base : RD->bases()) {
1249
28.7k
      QualType T = Base.getType();
1250
28.7k
      assert(T->isRecordType() && "Base class that isn't a record?");
1251
28.7k
      if (Visited.insert(::getCanonicalRD(T)).second)
1252
28.7k
        ToVisit.push_back(T);
1253
28.7k
    }
1254
239k
  };
1255
1256
  // Set up the loop by adding all the bases.
1257
219k
  AddBases(RD);
1258
1259
  // Search each path of bases until we either run into a successful match
1260
  // (where all bases of it are invalid), or we run out of bases.
1261
248k
  while (!ToVisit.empty()) {
1262
28.7k
    QualType NextT = ToVisit.pop_back_val();
1263
1264
28.7k
    SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(),
1265
28.7k
                                                        Deduced.end());
1266
28.7k
    TemplateDeductionInfo BaseInfo(TemplateDeductionInfo::ForBase, Info);
1267
28.7k
    Sema::TemplateDeductionResult BaseResult = DeduceTemplateSpecArguments(
1268
28.7k
        S, TemplateParams, P, NextT, BaseInfo, DeducedCopy);
1269
1270
    // If this was a successful deduction, add it to the list of matches,
1271
    // otherwise we need to continue searching its bases.
1272
28.7k
    const CXXRecordDecl *RD = ::getCanonicalRD(NextT);
1273
28.7k
    if (BaseResult == Sema::TDK_Success)
1274
8.61k
      Matches.insert({RD, DeducedCopy});
1275
20.0k
    else
1276
20.0k
      AddBases(RD);
1277
28.7k
  }
1278
1279
  // At this point, 'Matches' contains a list of seemingly valid bases, however
1280
  // in the event that we have more than 1 match, it is possible that the base
1281
  // of one of the matches might be disqualified for being a base of another
1282
  // valid match. We can count on cyclical instantiations being invalid to
1283
  // simplify the disqualifications.  That is, if A & B are both matches, and B
1284
  // inherits from A (disqualifying A), we know that A cannot inherit from B.
1285
219k
  if (Matches.size() > 1) {
1286
10
    Visited.clear();
1287
10
    for (const auto &Match : Matches)
1288
20
      AddBases(Match.first);
1289
1290
    // We can give up once we have a single item (or have run out of things to
1291
    // search) since cyclical inheritance isn't valid.
1292
22
    while (Matches.size() > 1 && 
!ToVisit.empty()14
) {
1293
12
      const CXXRecordDecl *RD = ::getCanonicalRD(ToVisit.pop_back_val());
1294
12
      Matches.erase(RD);
1295
1296
      // Always add all bases, since the inheritance tree can contain
1297
      // disqualifications for multiple matches.
1298
12
      AddBases(RD);
1299
12
    }
1300
10
  }
1301
1302
219k
  if (Matches.empty())
1303
210k
    return Sema::TDK_Invalid;
1304
8.60k
  if (Matches.size() > 1)
1305
2
    return Sema::TDK_MiscellaneousDeductionFailure;
1306
1307
8.60k
  std::swap(Matches.front().second, Deduced);
1308
8.60k
  return Sema::TDK_Success;
1309
8.60k
}
1310
1311
/// Deduce the template arguments by comparing the parameter type and
1312
/// the argument type (C++ [temp.deduct.type]).
1313
///
1314
/// \param S the semantic analysis object within which we are deducing
1315
///
1316
/// \param TemplateParams the template parameters that we are deducing
1317
///
1318
/// \param ParamIn the parameter type
1319
///
1320
/// \param ArgIn the argument type
1321
///
1322
/// \param Info information about the template argument deduction itself
1323
///
1324
/// \param Deduced the deduced template arguments
1325
///
1326
/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1327
/// how template argument deduction is performed.
1328
///
1329
/// \param PartialOrdering Whether we're performing template argument deduction
1330
/// in the context of partial ordering (C++0x [temp.deduct.partial]).
1331
///
1332
/// \returns the result of template argument deduction so far. Note that a
1333
/// "success" result means that template argument deduction has not yet failed,
1334
/// but it may still fail, later, for other reasons.
1335
static Sema::TemplateDeductionResult DeduceTemplateArgumentsByTypeMatch(
1336
    Sema &S, TemplateParameterList *TemplateParams, QualType P, QualType A,
1337
    TemplateDeductionInfo &Info,
1338
    SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF,
1339
3.34M
    bool PartialOrdering, bool DeducedFromArrayBound) {
1340
1341
  // If the argument type is a pack expansion, look at its pattern.
1342
  // This isn't explicitly called out
1343
3.34M
  if (const auto *AExp = dyn_cast<PackExpansionType>(A))
1344
48
    A = AExp->getPattern();
1345
3.34M
  assert(!isa<PackExpansionType>(A.getCanonicalType()));
1346
1347
3.34M
  if (PartialOrdering) {
1348
    // C++11 [temp.deduct.partial]p5:
1349
    //   Before the partial ordering is done, certain transformations are
1350
    //   performed on the types used for partial ordering:
1351
    //     - If P is a reference type, P is replaced by the type referred to.
1352
368k
    const ReferenceType *PRef = P->getAs<ReferenceType>();
1353
368k
    if (PRef)
1354
6.48k
      P = PRef->getPointeeType();
1355
1356
    //     - If A is a reference type, A is replaced by the type referred to.
1357
368k
    const ReferenceType *ARef = A->getAs<ReferenceType>();
1358
368k
    if (ARef)
1359
6.44k
      A = A->getPointeeType();
1360
1361
368k
    if (PRef && 
ARef6.48k
&&
S.Context.hasSameUnqualifiedType(P, A)6.20k
) {
1362
      // C++11 [temp.deduct.partial]p9:
1363
      //   If, for a given type, deduction succeeds in both directions (i.e.,
1364
      //   the types are identical after the transformations above) and both
1365
      //   P and A were reference types [...]:
1366
      //     - if [one type] was an lvalue reference and [the other type] was
1367
      //       not, [the other type] is not considered to be at least as
1368
      //       specialized as [the first type]
1369
      //     - if [one type] is more cv-qualified than [the other type],
1370
      //       [the other type] is not considered to be at least as specialized
1371
      //       as [the first type]
1372
      // Objective-C ARC adds:
1373
      //     - [one type] has non-trivial lifetime, [the other type] has
1374
      //       __unsafe_unretained lifetime, and the types are otherwise
1375
      //       identical
1376
      //
1377
      // A is "considered to be at least as specialized" as P iff deduction
1378
      // succeeds, so we model this as a deduction failure. Note that
1379
      // [the first type] is P and [the other type] is A here; the standard
1380
      // gets this backwards.
1381
2.68k
      Qualifiers PQuals = P.getQualifiers(), AQuals = A.getQualifiers();
1382
2.68k
      if ((PRef->isLValueReferenceType() && 
!ARef->isLValueReferenceType()2.59k
) ||
1383
2.68k
          
PQuals.isStrictSupersetOf(AQuals)2.67k
||
1384
2.68k
          
(2.60k
PQuals.hasNonTrivialObjCLifetime()2.60k
&&
1385
2.60k
           
AQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone4
&&
1386
2.60k
           
PQuals.withoutObjCLifetime() == AQuals.withoutObjCLifetime()4
)) {
1387
84
        Info.FirstArg = TemplateArgument(P);
1388
84
        Info.SecondArg = TemplateArgument(A);
1389
84
        return Sema::TDK_NonDeducedMismatch;
1390
84
      }
1391
2.68k
    }
1392
368k
    Qualifiers DiscardedQuals;
1393
    // C++11 [temp.deduct.partial]p7:
1394
    //   Remove any top-level cv-qualifiers:
1395
    //     - If P is a cv-qualified type, P is replaced by the cv-unqualified
1396
    //       version of P.
1397
368k
    P = S.Context.getUnqualifiedArrayType(P, DiscardedQuals);
1398
    //     - If A is a cv-qualified type, A is replaced by the cv-unqualified
1399
    //       version of A.
1400
368k
    A = S.Context.getUnqualifiedArrayType(A, DiscardedQuals);
1401
2.98M
  } else {
1402
    // C++0x [temp.deduct.call]p4 bullet 1:
1403
    //   - If the original P is a reference type, the deduced A (i.e., the type
1404
    //     referred to by the reference) can be more cv-qualified than the
1405
    //     transformed A.
1406
2.98M
    if (TDF & TDF_ParamWithReferenceType) {
1407
778k
      Qualifiers Quals;
1408
778k
      QualType UnqualP = S.Context.getUnqualifiedArrayType(P, Quals);
1409
778k
      Quals.setCVRQualifiers(Quals.getCVRQualifiers() & A.getCVRQualifiers());
1410
778k
      P = S.Context.getQualifiedType(UnqualP, Quals);
1411
778k
    }
1412
1413
2.98M
    if ((TDF & TDF_TopLevelParameterTypeList) && 
!P->isFunctionType()281k
) {
1414
      // C++0x [temp.deduct.type]p10:
1415
      //   If P and A are function types that originated from deduction when
1416
      //   taking the address of a function template (14.8.2.2) or when deducing
1417
      //   template arguments from a function declaration (14.8.2.6) and Pi and
1418
      //   Ai are parameters of the top-level parameter-type-list of P and A,
1419
      //   respectively, Pi is adjusted if it is a forwarding reference and Ai
1420
      //   is an lvalue reference, in
1421
      //   which case the type of Pi is changed to be the template parameter
1422
      //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
1423
      //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1424
      //   deduced as X&. - end note ]
1425
146k
      TDF &= ~TDF_TopLevelParameterTypeList;
1426
146k
      if (isForwardingReference(P, /*FirstInnerIndex=*/0) &&
1427
146k
          
A->isLValueReferenceType()3
)
1428
3
        P = P->getPointeeType();
1429
146k
    }
1430
2.98M
  }
1431
1432
  // C++ [temp.deduct.type]p9:
1433
  //   A template type argument T, a template template argument TT or a
1434
  //   template non-type argument i can be deduced if P and A have one of
1435
  //   the following forms:
1436
  //
1437
  //     T
1438
  //     cv-list T
1439
3.34M
  if (const auto *TTP = P->getAs<TemplateTypeParmType>()) {
1440
    // Just skip any attempts to deduce from a placeholder type or a parameter
1441
    // at a different depth.
1442
1.48M
    if (A->isPlaceholderType() || Info.getDeducedDepth() != TTP->getDepth())
1443
4
      return Sema::TDK_Success;
1444
1445
1.48M
    unsigned Index = TTP->getIndex();
1446
1447
    // If the argument type is an array type, move the qualifiers up to the
1448
    // top level, so they can be matched with the qualifiers on the parameter.
1449
1.48M
    if (A->isArrayType()) {
1450
7.81k
      Qualifiers Quals;
1451
7.81k
      A = S.Context.getUnqualifiedArrayType(A, Quals);
1452
7.81k
      if (Quals)
1453
525
        A = S.Context.getQualifiedType(A, Quals);
1454
7.81k
    }
1455
1456
    // The argument type can not be less qualified than the parameter
1457
    // type.
1458
1.48M
    if (!(TDF & TDF_IgnoreQualifiers) &&
1459
1.48M
        
hasInconsistentOrSupersetQualifiersOf(P, A)1.41M
) {
1460
69.3k
      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1461
69.3k
      Info.FirstArg = TemplateArgument(P);
1462
69.3k
      Info.SecondArg = TemplateArgument(A);
1463
69.3k
      return Sema::TDK_Underqualified;
1464
69.3k
    }
1465
1466
    // Do not match a function type with a cv-qualified type.
1467
    // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1468
1.41M
    if (A->isFunctionType() && 
P.hasQualifiers()9.39k
)
1469
8
      return Sema::TDK_NonDeducedMismatch;
1470
1471
1.41M
    assert(TTP->getDepth() == Info.getDeducedDepth() &&
1472
1.41M
           "saw template type parameter with wrong depth");
1473
0
    assert(A->getCanonicalTypeInternal() != S.Context.OverloadTy &&
1474
1.41M
           "Unresolved overloaded function");
1475
0
    QualType DeducedType = A;
1476
1477
    // Remove any qualifiers on the parameter from the deduced type.
1478
    // We checked the qualifiers for consistency above.
1479
1.41M
    Qualifiers DeducedQs = DeducedType.getQualifiers();
1480
1.41M
    Qualifiers ParamQs = P.getQualifiers();
1481
1.41M
    DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1482
1.41M
    if (ParamQs.hasObjCGCAttr())
1483
0
      DeducedQs.removeObjCGCAttr();
1484
1.41M
    if (ParamQs.hasAddressSpace())
1485
21
      DeducedQs.removeAddressSpace();
1486
1.41M
    if (ParamQs.hasObjCLifetime())
1487
63
      DeducedQs.removeObjCLifetime();
1488
1489
    // Objective-C ARC:
1490
    //   If template deduction would produce a lifetime qualifier on a type
1491
    //   that is not a lifetime type, template argument deduction fails.
1492
1.41M
    if (ParamQs.hasObjCLifetime() && 
!DeducedType->isObjCLifetimeType()63
&&
1493
1.41M
        
!DeducedType->isDependentType()2
) {
1494
2
      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1495
2
      Info.FirstArg = TemplateArgument(P);
1496
2
      Info.SecondArg = TemplateArgument(A);
1497
2
      return Sema::TDK_Underqualified;
1498
2
    }
1499
1500
    // Objective-C ARC:
1501
    //   If template deduction would produce an argument type with lifetime type
1502
    //   but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1503
1.41M
    if (S.getLangOpts().ObjCAutoRefCount && 
DeducedType->isObjCLifetimeType()391
&&
1504
1.41M
        
!DeducedQs.hasObjCLifetime()178
)
1505
124
      DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1506
1507
1.41M
    DeducedType =
1508
1.41M
        S.Context.getQualifiedType(DeducedType.getUnqualifiedType(), DeducedQs);
1509
1510
1.41M
    DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1511
1.41M
    DeducedTemplateArgument Result =
1512
1.41M
        checkDeducedTemplateArguments(S.Context, Deduced[Index], NewDeduced);
1513
1.41M
    if (Result.isNull()) {
1514
28.1k
      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1515
28.1k
      Info.FirstArg = Deduced[Index];
1516
28.1k
      Info.SecondArg = NewDeduced;
1517
28.1k
      return Sema::TDK_Inconsistent;
1518
28.1k
    }
1519
1520
1.38M
    Deduced[Index] = Result;
1521
1.38M
    return Sema::TDK_Success;
1522
1.41M
  }
1523
1524
  // Set up the template argument deduction information for a failure.
1525
1.86M
  Info.FirstArg = TemplateArgument(P);
1526
1.86M
  Info.SecondArg = TemplateArgument(A);
1527
1528
  // If the parameter is an already-substituted template parameter
1529
  // pack, do nothing: we don't know which of its arguments to look
1530
  // at, so we have to wait until all of the parameter packs in this
1531
  // expansion have arguments.
1532
1.86M
  if (P->getAs<SubstTemplateTypeParmPackType>())
1533
46
    return Sema::TDK_Success;
1534
1535
  // Check the cv-qualifiers on the parameter and argument types.
1536
1.86M
  if (!(TDF & TDF_IgnoreQualifiers)) {
1537
1.77M
    if (TDF & TDF_ParamWithReferenceType) {
1538
613k
      if (hasInconsistentOrSupersetQualifiersOf(P, A))
1539
0
        return Sema::TDK_NonDeducedMismatch;
1540
1.16M
    } else if (TDF & TDF_ArgWithReferenceType) {
1541
      // C++ [temp.deduct.conv]p4:
1542
      //   If the original A is a reference type, A can be more cv-qualified
1543
      //   than the deduced A
1544
53
      if (!A.getQualifiers().compatiblyIncludes(P.getQualifiers()))
1545
0
        return Sema::TDK_NonDeducedMismatch;
1546
1547
      // Strip out all extra qualifiers from the argument to figure out the
1548
      // type we're converting to, prior to the qualification conversion.
1549
53
      Qualifiers Quals;
1550
53
      A = S.Context.getUnqualifiedArrayType(A, Quals);
1551
53
      A = S.Context.getQualifiedType(A, P.getQualifiers());
1552
1.16M
    } else if (!IsPossiblyOpaquelyQualifiedType(P)) {
1553
1.00M
      if (P.getCVRQualifiers() != A.getCVRQualifiers())
1554
25.1k
        return Sema::TDK_NonDeducedMismatch;
1555
1.00M
    }
1556
1.77M
  }
1557
1558
  // If the parameter type is not dependent, there is nothing to deduce.
1559
1.83M
  if (!P->isDependentType()) {
1560
137k
    if (TDF & TDF_SkipNonDependent)
1561
4.71k
      return Sema::TDK_Success;
1562
132k
    if ((TDF & TDF_IgnoreQualifiers) ? 
S.Context.hasSameUnqualifiedType(P, A)73
1563
132k
                                     : 
S.Context.hasSameType(P, A)132k
)
1564
81.6k
      return Sema::TDK_Success;
1565
50.7k
    if (TDF & TDF_AllowCompatibleFunctionType &&
1566
50.7k
        
S.isSameOrCompatibleFunctionType(P, A)13.1k
)
1567
18
      return Sema::TDK_Success;
1568
50.7k
    if (!(TDF & TDF_IgnoreQualifiers))
1569
50.7k
      return Sema::TDK_NonDeducedMismatch;
1570
    // Otherwise, when ignoring qualifiers, the types not having the same
1571
    // unqualified type does not mean they do not match, so in this case we
1572
    // must keep going and analyze with a non-dependent parameter type.
1573
50.7k
  }
1574
1575
1.70M
  switch (P.getCanonicalType()->getTypeClass()) {
1576
    // Non-canonical types cannot appear here.
1577
0
#define NON_CANONICAL_TYPE(Class, Base) \
1578
0
  case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1579
0
#define TYPE(Class, Base)
1580
0
#include "clang/AST/TypeNodes.inc"
1581
1582
0
    case Type::TemplateTypeParm:
1583
0
    case Type::SubstTemplateTypeParmPack:
1584
0
      llvm_unreachable("Type nodes handled above");
1585
1586
1.16k
    case Type::Auto:
1587
      // FIXME: Implement deduction in dependent case.
1588
1.16k
      if (P->isDependentType())
1589
1.16k
        return Sema::TDK_Success;
1590
1.16k
      
LLVM_FALLTHROUGH0
;0
1591
2
    case Type::Builtin:
1592
2
    case Type::VariableArray:
1593
2
    case Type::Vector:
1594
2
    case Type::FunctionNoProto:
1595
2
    case Type::Record:
1596
2
    case Type::Enum:
1597
2
    case Type::ObjCObject:
1598
2
    case Type::ObjCInterface:
1599
2
    case Type::ObjCObjectPointer:
1600
2
    case Type::BitInt:
1601
2
      return (TDF & TDF_SkipNonDependent) ||
1602
2
                     ((TDF & TDF_IgnoreQualifiers)
1603
2
                          ? S.Context.hasSameUnqualifiedType(P, A)
1604
2
                          : 
S.Context.hasSameType(P, A)0
)
1605
2
                 ? 
Sema::TDK_Success0
1606
2
                 : Sema::TDK_NonDeducedMismatch;
1607
1608
    //     _Complex T   [placeholder extension]
1609
0
    case Type::Complex: {
1610
0
      const auto *CP = P->castAs<ComplexType>(), *CA = A->getAs<ComplexType>();
1611
0
      if (!CA)
1612
0
        return Sema::TDK_NonDeducedMismatch;
1613
0
      return DeduceTemplateArgumentsByTypeMatch(
1614
0
          S, TemplateParams, CP->getElementType(), CA->getElementType(), Info,
1615
0
          Deduced, TDF);
1616
0
    }
1617
1618
    //     _Atomic T   [extension]
1619
0
    case Type::Atomic: {
1620
0
      const auto *PA = P->castAs<AtomicType>(), *AA = A->getAs<AtomicType>();
1621
0
      if (!AA)
1622
0
        return Sema::TDK_NonDeducedMismatch;
1623
0
      return DeduceTemplateArgumentsByTypeMatch(
1624
0
          S, TemplateParams, PA->getValueType(), AA->getValueType(), Info,
1625
0
          Deduced, TDF);
1626
0
    }
1627
1628
    //     T *
1629
71.5k
    case Type::Pointer: {
1630
71.5k
      QualType PointeeType;
1631
71.5k
      if (const auto *PA = A->getAs<PointerType>()) {
1632
44.1k
        PointeeType = PA->getPointeeType();
1633
44.1k
      } else 
if (const auto *27.4k
PA27.4k
= A->getAs<ObjCObjectPointerType>()) {
1634
44
        PointeeType = PA->getPointeeType();
1635
27.4k
      } else {
1636
27.4k
        return Sema::TDK_NonDeducedMismatch;
1637
27.4k
      }
1638
44.1k
      return DeduceTemplateArgumentsByTypeMatch(
1639
44.1k
          S, TemplateParams, P->castAs<PointerType>()->getPointeeType(),
1640
44.1k
          PointeeType, Info, Deduced,
1641
44.1k
          TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass));
1642
71.5k
    }
1643
1644
    //     T &
1645
94.8k
    case Type::LValueReference: {
1646
94.8k
      const auto *RP = P->castAs<LValueReferenceType>(),
1647
94.8k
                 *RA = A->getAs<LValueReferenceType>();
1648
94.8k
      if (!RA)
1649
58.8k
        return Sema::TDK_NonDeducedMismatch;
1650
1651
35.9k
      return DeduceTemplateArgumentsByTypeMatch(
1652
35.9k
          S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1653
35.9k
          Deduced, 0);
1654
94.8k
    }
1655
1656
    //     T && [C++0x]
1657
34.6k
    case Type::RValueReference: {
1658
34.6k
      const auto *RP = P->castAs<RValueReferenceType>(),
1659
34.6k
                 *RA = A->getAs<RValueReferenceType>();
1660
34.6k
      if (!RA)
1661
33.9k
        return Sema::TDK_NonDeducedMismatch;
1662
1663
758
      return DeduceTemplateArgumentsByTypeMatch(
1664
758
          S, TemplateParams, RP->getPointeeType(), RA->getPointeeType(), Info,
1665
758
          Deduced, 0);
1666
34.6k
    }
1667
1668
    //     T [] (implied, but not stated explicitly)
1669
25.2k
    case Type::IncompleteArray: {
1670
25.2k
      const auto *IAA = S.Context.getAsIncompleteArrayType(A);
1671
25.2k
      if (!IAA)
1672
24.9k
        return Sema::TDK_NonDeducedMismatch;
1673
1674
294
      return DeduceTemplateArgumentsByTypeMatch(
1675
294
          S, TemplateParams,
1676
294
          S.Context.getAsIncompleteArrayType(P)->getElementType(),
1677
294
          IAA->getElementType(), Info, Deduced, TDF & TDF_IgnoreQualifiers);
1678
25.2k
    }
1679
1680
    //     T [integer-constant]
1681
56
    case Type::ConstantArray: {
1682
56
      const auto *CAA = S.Context.getAsConstantArrayType(A),
1683
56
                 *CAP = S.Context.getAsConstantArrayType(P);
1684
56
      assert(CAP);
1685
56
      if (!CAA || 
CAA->getSize() != CAP->getSize()45
)
1686
15
        return Sema::TDK_NonDeducedMismatch;
1687
1688
41
      return DeduceTemplateArgumentsByTypeMatch(
1689
41
          S, TemplateParams, CAP->getElementType(), CAA->getElementType(), Info,
1690
41
          Deduced, TDF & TDF_IgnoreQualifiers);
1691
56
    }
1692
1693
    //     type [i]
1694
24.9k
    case Type::DependentSizedArray: {
1695
24.9k
      const auto *AA = S.Context.getAsArrayType(A);
1696
24.9k
      if (!AA)
1697
24.3k
        return Sema::TDK_NonDeducedMismatch;
1698
1699
      // Check the element type of the arrays
1700
607
      const auto *DAP = S.Context.getAsDependentSizedArrayType(P);
1701
607
      assert(DAP);
1702
607
      if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1703
607
              S, TemplateParams, DAP->getElementType(), AA->getElementType(),
1704
607
              Info, Deduced, TDF & TDF_IgnoreQualifiers))
1705
42
        return Result;
1706
1707
      // Determine the array bound is something we can deduce.
1708
565
      const NonTypeTemplateParmDecl *NTTP =
1709
565
          getDeducedParameterFromExpr(Info, DAP->getSizeExpr());
1710
565
      if (!NTTP)
1711
4
        return Sema::TDK_Success;
1712
1713
      // We can perform template argument deduction for the given non-type
1714
      // template parameter.
1715
561
      assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1716
561
             "saw non-type template parameter with wrong depth");
1717
561
      if (const auto *CAA = dyn_cast<ConstantArrayType>(AA)) {
1718
470
        llvm::APSInt Size(CAA->getSize());
1719
470
        return DeduceNonTypeTemplateArgument(
1720
470
            S, TemplateParams, NTTP, Size, S.Context.getSizeType(),
1721
470
            /*ArrayBound=*/true, Info, Deduced);
1722
470
      }
1723
91
      if (const auto *DAA = dyn_cast<DependentSizedArrayType>(AA))
1724
34
        if (DAA->getSizeExpr())
1725
34
          return DeduceNonTypeTemplateArgument(
1726
34
              S, TemplateParams, NTTP, DAA->getSizeExpr(), Info, Deduced);
1727
1728
      // Incomplete type does not match a dependently-sized array type
1729
57
      return Sema::TDK_NonDeducedMismatch;
1730
91
    }
1731
1732
    //     type(*)(T)
1733
    //     T(*)()
1734
    //     T(*)(T)
1735
113k
    case Type::FunctionProto: {
1736
113k
      const auto *FPP = P->castAs<FunctionProtoType>(),
1737
113k
                 *FPA = A->getAs<FunctionProtoType>();
1738
113k
      if (!FPA)
1739
8.79k
        return Sema::TDK_NonDeducedMismatch;
1740
1741
104k
      if (FPP->getMethodQuals() != FPA->getMethodQuals() ||
1742
104k
          
FPP->getRefQualifier() != FPA->getRefQualifier()104k
||
1743
104k
          
FPP->isVariadic() != FPA->isVariadic()104k
)
1744
109
        return Sema::TDK_NonDeducedMismatch;
1745
1746
      // Check return types.
1747
104k
      if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1748
104k
              S, TemplateParams, FPP->getReturnType(), FPA->getReturnType(),
1749
104k
              Info, Deduced, 0,
1750
104k
              /*PartialOrdering=*/false,
1751
104k
              /*DeducedFromArrayBound=*/false))
1752
11.2k
        return Result;
1753
1754
      // Check parameter types.
1755
93.1k
      if (auto Result = DeduceTemplateArguments(
1756
93.1k
              S, TemplateParams, FPP->param_type_begin(), FPP->getNumParams(),
1757
93.1k
              FPA->param_type_begin(), FPA->getNumParams(), Info, Deduced,
1758
93.1k
              TDF & TDF_TopLevelParameterTypeList))
1759
79.0k
        return Result;
1760
1761
14.0k
      if (TDF & TDF_AllowCompatibleFunctionType)
1762
12.0k
        return Sema::TDK_Success;
1763
1764
      // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1765
      // deducing through the noexcept-specifier if it's part of the canonical
1766
      // type. libstdc++ relies on this.
1767
2.05k
      Expr *NoexceptExpr = FPP->getNoexceptExpr();
1768
2.05k
      if (const NonTypeTemplateParmDecl *NTTP =
1769
2.05k
              NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1770
2.05k
                           : nullptr) {
1771
13
        assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1772
13
               "saw non-type template parameter with wrong depth");
1773
1774
0
        llvm::APSInt Noexcept(1);
1775
13
        switch (FPA->canThrow()) {
1776
8
        case CT_Cannot:
1777
8
          Noexcept = 1;
1778
8
          LLVM_FALLTHROUGH;
1779
1780
13
        case CT_Can:
1781
          // We give E in noexcept(E) the "deduced from array bound" treatment.
1782
          // FIXME: Should we?
1783
13
          return DeduceNonTypeTemplateArgument(
1784
13
              S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1785
13
              /*DeducedFromArrayBound=*/true, Info, Deduced);
1786
1787
0
        case CT_Dependent:
1788
0
          if (Expr *ArgNoexceptExpr = FPA->getNoexceptExpr())
1789
0
            return DeduceNonTypeTemplateArgument(
1790
0
                S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1791
          // Can't deduce anything from throw(T...).
1792
0
          break;
1793
13
        }
1794
13
      }
1795
      // FIXME: Detect non-deduced exception specification mismatches?
1796
      //
1797
      // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1798
      // top-level differences in noexcept-specifications.
1799
1800
2.04k
      return Sema::TDK_Success;
1801
2.05k
    }
1802
1803
307
    case Type::InjectedClassName:
1804
      // Treat a template's injected-class-name as if the template
1805
      // specialization type had been used.
1806
1807
    //     template-name<T> (where template-name refers to a class template)
1808
    //     template-name<i>
1809
    //     TT<T>
1810
    //     TT<i>
1811
    //     TT<>
1812
1.20M
    case Type::TemplateSpecialization: {
1813
      // When Arg cannot be a derived class, we can just try to deduce template
1814
      // arguments from the template-id.
1815
1.20M
      if (!(TDF & TDF_DerivedClass) || 
!A->isRecordType()712k
)
1816
904k
        return DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info,
1817
904k
                                           Deduced);
1818
1819
302k
      SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1820
302k
                                                          Deduced.end());
1821
1822
302k
      auto Result =
1823
302k
          DeduceTemplateSpecArguments(S, TemplateParams, P, A, Info, Deduced);
1824
302k
      if (Result == Sema::TDK_Success)
1825
82.9k
        return Result;
1826
1827
      // We cannot inspect base classes as part of deduction when the type
1828
      // is incomplete, so either instantiate any templates necessary to
1829
      // complete the type, or skip over it if it cannot be completed.
1830
219k
      if (!S.isCompleteType(Info.getLocation(), A))
1831
6
        return Result;
1832
1833
      // Reset the incorrectly deduced argument from above.
1834
219k
      Deduced = DeducedOrig;
1835
1836
      // Check bases according to C++14 [temp.deduct.call] p4b3:
1837
219k
      auto BaseResult = DeduceTemplateBases(S, getCanonicalRD(A),
1838
219k
                                            TemplateParams, P, Info, Deduced);
1839
219k
      return BaseResult != Sema::TDK_Invalid ? 
BaseResult8.60k
:
Result210k
;
1840
219k
    }
1841
1842
    //     T type::*
1843
    //     T T::*
1844
    //     T (type::*)()
1845
    //     type (T::*)()
1846
    //     type (type::*)(T)
1847
    //     type (T::*)(T)
1848
    //     T (type::*)(T)
1849
    //     T (T::*)()
1850
    //     T (T::*)(T)
1851
18.9k
    case Type::MemberPointer: {
1852
18.9k
      const auto *MPP = P->castAs<MemberPointerType>(),
1853
18.9k
                 *MPA = A->getAs<MemberPointerType>();
1854
18.9k
      if (!MPA)
1855
18.6k
        return Sema::TDK_NonDeducedMismatch;
1856
1857
261
      QualType PPT = MPP->getPointeeType();
1858
261
      if (PPT->isFunctionType())
1859
161
        S.adjustMemberFunctionCC(PPT, /*IsStatic=*/true,
1860
161
                                 /*IsCtorOrDtor=*/false, Info.getLocation());
1861
261
      QualType APT = MPA->getPointeeType();
1862
261
      if (APT->isFunctionType())
1863
176
        S.adjustMemberFunctionCC(APT, /*IsStatic=*/true,
1864
176
                                 /*IsCtorOrDtor=*/false, Info.getLocation());
1865
1866
261
      unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1867
261
      if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1868
261
              S, TemplateParams, PPT, APT, Info, Deduced, SubTDF))
1869
85
        return Result;
1870
176
      return DeduceTemplateArgumentsByTypeMatch(
1871
176
          S, TemplateParams, QualType(MPP->getClass(), 0),
1872
176
          QualType(MPA->getClass(), 0), Info, Deduced, SubTDF);
1873
261
    }
1874
1875
    //     (clang extension)
1876
    //
1877
    //     type(^)(T)
1878
    //     T(^)()
1879
    //     T(^)(T)
1880
500
    case Type::BlockPointer: {
1881
500
      const auto *BPP = P->castAs<BlockPointerType>(),
1882
500
                 *BPA = A->getAs<BlockPointerType>();
1883
500
      if (!BPA)
1884
488
        return Sema::TDK_NonDeducedMismatch;
1885
12
      return DeduceTemplateArgumentsByTypeMatch(
1886
12
          S, TemplateParams, BPP->getPointeeType(), BPA->getPointeeType(), Info,
1887
12
          Deduced, 0);
1888
500
    }
1889
1890
    //     (clang extension)
1891
    //
1892
    //     T __attribute__(((ext_vector_type(<integral constant>))))
1893
6
    case Type::ExtVector: {
1894
6
      const auto *VP = P->castAs<ExtVectorType>();
1895
6
      QualType ElementType;
1896
6
      if (const auto *VA = A->getAs<ExtVectorType>()) {
1897
        // Make sure that the vectors have the same number of elements.
1898
3
        if (VP->getNumElements() != VA->getNumElements())
1899
2
          return Sema::TDK_NonDeducedMismatch;
1900
1
        ElementType = VA->getElementType();
1901
3
      } else if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
1902
        // We can't check the number of elements, since the argument has a
1903
        // dependent number of elements. This can only occur during partial
1904
        // ordering.
1905
2
        ElementType = VA->getElementType();
1906
2
      } else {
1907
1
        return Sema::TDK_NonDeducedMismatch;
1908
1
      }
1909
      // Perform deduction on the element types.
1910
3
      return DeduceTemplateArgumentsByTypeMatch(
1911
3
          S, TemplateParams, VP->getElementType(), ElementType, Info, Deduced,
1912
3
          TDF);
1913
6
    }
1914
1915
0
    case Type::DependentVector: {
1916
0
      const auto *VP = P->castAs<DependentVectorType>();
1917
1918
0
      if (const auto *VA = A->getAs<VectorType>()) {
1919
        // Perform deduction on the element types.
1920
0
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1921
0
                S, TemplateParams, VP->getElementType(), VA->getElementType(),
1922
0
                Info, Deduced, TDF))
1923
0
          return Result;
1924
1925
        // Perform deduction on the vector size, if we can.
1926
0
        const NonTypeTemplateParmDecl *NTTP =
1927
0
            getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1928
0
        if (!NTTP)
1929
0
          return Sema::TDK_Success;
1930
1931
0
        llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1932
0
        ArgSize = VA->getNumElements();
1933
        // Note that we use the "array bound" rules here; just like in that
1934
        // case, we don't have any particular type for the vector size, but
1935
        // we can provide one if necessary.
1936
0
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1937
0
                                             S.Context.UnsignedIntTy, true,
1938
0
                                             Info, Deduced);
1939
0
      }
1940
1941
0
      if (const auto *VA = A->getAs<DependentVectorType>()) {
1942
        // Perform deduction on the element types.
1943
0
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1944
0
                S, TemplateParams, VP->getElementType(), VA->getElementType(),
1945
0
                Info, Deduced, TDF))
1946
0
          return Result;
1947
1948
        // Perform deduction on the vector size, if we can.
1949
0
        const NonTypeTemplateParmDecl *NTTP =
1950
0
            getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1951
0
        if (!NTTP)
1952
0
          return Sema::TDK_Success;
1953
1954
0
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
1955
0
                                             VA->getSizeExpr(), Info, Deduced);
1956
0
      }
1957
1958
0
      return Sema::TDK_NonDeducedMismatch;
1959
0
    }
1960
1961
    //     (clang extension)
1962
    //
1963
    //     T __attribute__(((ext_vector_type(N))))
1964
14
    case Type::DependentSizedExtVector: {
1965
14
      const auto *VP = P->castAs<DependentSizedExtVectorType>();
1966
1967
14
      if (const auto *VA = A->getAs<ExtVectorType>()) {
1968
        // Perform deduction on the element types.
1969
8
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1970
8
                S, TemplateParams, VP->getElementType(), VA->getElementType(),
1971
8
                Info, Deduced, TDF))
1972
2
          return Result;
1973
1974
        // Perform deduction on the vector size, if we can.
1975
6
        const NonTypeTemplateParmDecl *NTTP =
1976
6
            getDeducedParameterFromExpr(Info, VP->getSizeExpr());
1977
6
        if (!NTTP)
1978
0
          return Sema::TDK_Success;
1979
1980
6
        llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1981
6
        ArgSize = VA->getNumElements();
1982
        // Note that we use the "array bound" rules here; just like in that
1983
        // case, we don't have any particular type for the vector size, but
1984
        // we can provide one if necessary.
1985
6
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1986
6
                                             S.Context.IntTy, true, Info,
1987
6
                                             Deduced);
1988
6
      }
1989
1990
6
      if (const auto *VA = A->getAs<DependentSizedExtVectorType>()) {
1991
        // Perform deduction on the element types.
1992
4
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1993
4
                S, TemplateParams, VP->getElementType(), VA->getElementType(),
1994
4
                Info, Deduced, TDF))
1995
2
          return Result;
1996
1997
        // Perform deduction on the vector size, if we can.
1998
2
        const NonTypeTemplateParmDecl *NTTP =
1999
2
            getDeducedParameterFromExpr(Info, VP->getSizeExpr());
2000
2
        if (!NTTP)
2001
0
          return Sema::TDK_Success;
2002
2003
2
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2004
2
                                             VA->getSizeExpr(), Info, Deduced);
2005
2
      }
2006
2007
2
      return Sema::TDK_NonDeducedMismatch;
2008
6
    }
2009
2010
    //     (clang extension)
2011
    //
2012
    //     T __attribute__((matrix_type(<integral constant>,
2013
    //                                  <integral constant>)))
2014
17
    case Type::ConstantMatrix: {
2015
17
      const auto *MP = P->castAs<ConstantMatrixType>(),
2016
17
                 *MA = A->getAs<ConstantMatrixType>();
2017
17
      if (!MA)
2018
9
        return Sema::TDK_NonDeducedMismatch;
2019
2020
      // Check that the dimensions are the same
2021
8
      if (MP->getNumRows() != MA->getNumRows() ||
2022
8
          
MP->getNumColumns() != MA->getNumColumns()3
) {
2023
6
        return Sema::TDK_NonDeducedMismatch;
2024
6
      }
2025
      // Perform deduction on element types.
2026
2
      return DeduceTemplateArgumentsByTypeMatch(
2027
2
          S, TemplateParams, MP->getElementType(), MA->getElementType(), Info,
2028
2
          Deduced, TDF);
2029
8
    }
2030
2031
338
    case Type::DependentSizedMatrix: {
2032
338
      const auto *MP = P->castAs<DependentSizedMatrixType>();
2033
338
      const auto *MA = A->getAs<MatrixType>();
2034
338
      if (!MA)
2035
248
        return Sema::TDK_NonDeducedMismatch;
2036
2037
      // Check the element type of the matrixes.
2038
90
      if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2039
90
              S, TemplateParams, MP->getElementType(), MA->getElementType(),
2040
90
              Info, Deduced, TDF))
2041
7
        return Result;
2042
2043
      // Try to deduce a matrix dimension.
2044
83
      auto DeduceMatrixArg =
2045
83
          [&S, &Info, &Deduced, &TemplateParams](
2046
83
              Expr *ParamExpr, const MatrixType *A,
2047
83
              unsigned (ConstantMatrixType::*GetArgDimension)() const,
2048
157
              Expr *(DependentSizedMatrixType::*GetArgDimensionExpr)() const) {
2049
157
            const auto *ACM = dyn_cast<ConstantMatrixType>(A);
2050
157
            const auto *ADM = dyn_cast<DependentSizedMatrixType>(A);
2051
157
            if (!ParamExpr->isValueDependent()) {
2052
42
              Optional<llvm::APSInt> ParamConst =
2053
42
                  ParamExpr->getIntegerConstantExpr(S.Context);
2054
42
              if (!ParamConst)
2055
0
                return Sema::TDK_NonDeducedMismatch;
2056
2057
42
              if (ACM) {
2058
26
                if ((ACM->*GetArgDimension)() == *ParamConst)
2059
19
                  return Sema::TDK_Success;
2060
7
                return Sema::TDK_NonDeducedMismatch;
2061
26
              }
2062
2063
16
              Expr *ArgExpr = (ADM->*GetArgDimensionExpr)();
2064
16
              if (Optional<llvm::APSInt> ArgConst =
2065
16
                      ArgExpr->getIntegerConstantExpr(S.Context))
2066
2
                if (*ArgConst == *ParamConst)
2067
2
                  return Sema::TDK_Success;
2068
14
              return Sema::TDK_NonDeducedMismatch;
2069
16
            }
2070
2071
115
            const NonTypeTemplateParmDecl *NTTP =
2072
115
                getDeducedParameterFromExpr(Info, ParamExpr);
2073
115
            if (!NTTP)
2074
9
              return Sema::TDK_Success;
2075
2076
106
            if (ACM) {
2077
80
              llvm::APSInt ArgConst(
2078
80
                  S.Context.getTypeSize(S.Context.getSizeType()));
2079
80
              ArgConst = (ACM->*GetArgDimension)();
2080
80
              return DeduceNonTypeTemplateArgument(
2081
80
                  S, TemplateParams, NTTP, ArgConst, S.Context.getSizeType(),
2082
80
                  /*ArrayBound=*/true, Info, Deduced);
2083
80
            }
2084
2085
26
            return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2086
26
                                                 (ADM->*GetArgDimensionExpr)(),
2087
26
                                                 Info, Deduced);
2088
106
          };
2089
2090
83
      if (auto Result = DeduceMatrixArg(MP->getRowExpr(), MA,
2091
83
                                        &ConstantMatrixType::getNumRows,
2092
83
                                        &DependentSizedMatrixType::getRowExpr))
2093
9
        return Result;
2094
2095
74
      return DeduceMatrixArg(MP->getColumnExpr(), MA,
2096
74
                             &ConstantMatrixType::getNumColumns,
2097
74
                             &DependentSizedMatrixType::getColumnExpr);
2098
83
    }
2099
2100
    //     (clang extension)
2101
    //
2102
    //     T __attribute__(((address_space(N))))
2103
2
    case Type::DependentAddressSpace: {
2104
2
      const auto *ASP = P->castAs<DependentAddressSpaceType>();
2105
2106
2
      if (const auto *ASA = A->getAs<DependentAddressSpaceType>()) {
2107
        // Perform deduction on the pointer type.
2108
0
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2109
0
                S, TemplateParams, ASP->getPointeeType(), ASA->getPointeeType(),
2110
0
                Info, Deduced, TDF))
2111
0
          return Result;
2112
2113
        // Perform deduction on the address space, if we can.
2114
0
        const NonTypeTemplateParmDecl *NTTP =
2115
0
            getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2116
0
        if (!NTTP)
2117
0
          return Sema::TDK_Success;
2118
2119
0
        return DeduceNonTypeTemplateArgument(
2120
0
            S, TemplateParams, NTTP, ASA->getAddrSpaceExpr(), Info, Deduced);
2121
0
      }
2122
2123
2
      if (isTargetAddressSpace(A.getAddressSpace())) {
2124
2
        llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2125
2
                                     false);
2126
2
        ArgAddressSpace = toTargetAddressSpace(A.getAddressSpace());
2127
2128
        // Perform deduction on the pointer types.
2129
2
        if (auto Result = DeduceTemplateArgumentsByTypeMatch(
2130
2
                S, TemplateParams, ASP->getPointeeType(),
2131
2
                S.Context.removeAddrSpaceQualType(A), Info, Deduced, TDF))
2132
0
          return Result;
2133
2134
        // Perform deduction on the address space, if we can.
2135
2
        const NonTypeTemplateParmDecl *NTTP =
2136
2
            getDeducedParameterFromExpr(Info, ASP->getAddrSpaceExpr());
2137
2
        if (!NTTP)
2138
0
          return Sema::TDK_Success;
2139
2140
2
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2141
2
                                             ArgAddressSpace, S.Context.IntTy,
2142
2
                                             true, Info, Deduced);
2143
2
      }
2144
2145
0
      return Sema::TDK_NonDeducedMismatch;
2146
2
    }
2147
1
    case Type::DependentBitInt: {
2148
1
      const auto *IP = P->castAs<DependentBitIntType>();
2149
2150
1
      if (const auto *IA = A->getAs<BitIntType>()) {
2151
1
        if (IP->isUnsigned() != IA->isUnsigned())
2152
0
          return Sema::TDK_NonDeducedMismatch;
2153
2154
1
        const NonTypeTemplateParmDecl *NTTP =
2155
1
            getDeducedParameterFromExpr(Info, IP->getNumBitsExpr());
2156
1
        if (!NTTP)
2157
0
          return Sema::TDK_Success;
2158
2159
1
        llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2160
1
        ArgSize = IA->getNumBits();
2161
2162
1
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2163
1
                                             S.Context.IntTy, true, Info,
2164
1
                                             Deduced);
2165
1
      }
2166
2167
0
      if (const auto *IA = A->getAs<DependentBitIntType>()) {
2168
0
        if (IP->isUnsigned() != IA->isUnsigned())
2169
0
          return Sema::TDK_NonDeducedMismatch;
2170
0
        return Sema::TDK_Success;
2171
0
      }
2172
2173
0
      return Sema::TDK_NonDeducedMismatch;
2174
0
    }
2175
2176
0
    case Type::TypeOfExpr:
2177
0
    case Type::TypeOf:
2178
101k
    case Type::DependentName:
2179
101k
    case Type::UnresolvedUsing:
2180
108k
    case Type::Decltype:
2181
108k
    case Type::UnaryTransform:
2182
108k
    case Type::DeducedTemplateSpecialization:
2183
108k
    case Type::DependentTemplateSpecialization:
2184
108k
    case Type::PackExpansion:
2185
108k
    case Type::Pipe:
2186
      // No template argument deduction for these types
2187
108k
      return Sema::TDK_Success;
2188
1.70M
    }
2189
2190
0
  llvm_unreachable("Invalid Type Class!");
2191
0
}
2192
2193
static Sema::TemplateDeductionResult
2194
DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
2195
                        const TemplateArgument &P, TemplateArgument A,
2196
                        TemplateDeductionInfo &Info,
2197
1.99M
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2198
  // If the template argument is a pack expansion, perform template argument
2199
  // deduction against the pattern of that expansion. This only occurs during
2200
  // partial ordering.
2201
1.99M
  if (A.isPackExpansion())
2202
5.24k
    A = A.getPackExpansionPattern();
2203
2204
1.99M
  switch (P.getKind()) {
2205
0
  case TemplateArgument::Null:
2206
0
    llvm_unreachable("Null template argument in parameter list");
2207
2208
1.49M
  case TemplateArgument::Type:
2209
1.49M
    if (A.getKind() == TemplateArgument::Type)
2210
1.49M
      return DeduceTemplateArgumentsByTypeMatch(
2211
1.49M
          S, TemplateParams, P.getAsType(), A.getAsType(), Info, Deduced, 0);
2212
3
    Info.FirstArg = P;
2213
3
    Info.SecondArg = A;
2214
3
    return Sema::TDK_NonDeducedMismatch;
2215
2216
98
  case TemplateArgument::Template:
2217
98
    if (A.getKind() == TemplateArgument::Template)
2218
98
      return DeduceTemplateArguments(S, TemplateParams, P.getAsTemplate(),
2219
98
                                     A.getAsTemplate(), Info, Deduced);
2220
0
    Info.FirstArg = P;
2221
0
    Info.SecondArg = A;
2222
0
    return Sema::TDK_NonDeducedMismatch;
2223
2224
0
  case TemplateArgument::TemplateExpansion:
2225
0
    llvm_unreachable("caller should handle pack expansions");
2226
2227
29
  case TemplateArgument::Declaration:
2228
29
    if (A.getKind() == TemplateArgument::Declaration &&
2229
29
        
isSameDeclaration(P.getAsDecl(), A.getAsDecl())6
)
2230
6
      return Sema::TDK_Success;
2231
2232
23
    Info.FirstArg = P;
2233
23
    Info.SecondArg = A;
2234
23
    return Sema::TDK_NonDeducedMismatch;
2235
2236
6
  case TemplateArgument::NullPtr:
2237
6
    if (A.getKind() == TemplateArgument::NullPtr &&
2238
6
        
S.Context.hasSameType(P.getNullPtrType(), A.getNullPtrType())5
)
2239
5
      return Sema::TDK_Success;
2240
2241
1
    Info.FirstArg = P;
2242
1
    Info.SecondArg = A;
2243
1
    return Sema::TDK_NonDeducedMismatch;
2244
2245
264k
  case TemplateArgument::Integral:
2246
264k
    if (A.getKind() == TemplateArgument::Integral) {
2247
212k
      if (hasSameExtendedValue(P.getAsIntegral(), A.getAsIntegral()))
2248
112k
        return Sema::TDK_Success;
2249
212k
    }
2250
151k
    Info.FirstArg = P;
2251
151k
    Info.SecondArg = A;
2252
151k
    return Sema::TDK_NonDeducedMismatch;
2253
2254
241k
  case TemplateArgument::Expression:
2255
241k
    if (const NonTypeTemplateParmDecl *NTTP =
2256
241k
            getDeducedParameterFromExpr(Info, P.getAsExpr())) {
2257
241k
      if (A.getKind() == TemplateArgument::Integral)
2258
168k
        return DeduceNonTypeTemplateArgument(
2259
168k
            S, TemplateParams, NTTP, A.getAsIntegral(), A.getIntegralType(),
2260
168k
            /*ArrayBound=*/false, Info, Deduced);
2261
72.2k
      if (A.getKind() == TemplateArgument::NullPtr)
2262
39
        return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2263
39
                                             A.getNullPtrType(), Info, Deduced);
2264
72.1k
      if (A.getKind() == TemplateArgument::Expression)
2265
70.9k
        return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2266
70.9k
                                             A.getAsExpr(), Info, Deduced);
2267
1.19k
      if (A.getKind() == TemplateArgument::Declaration)
2268
1.19k
        return DeduceNonTypeTemplateArgument(
2269
1.19k
            S, TemplateParams, NTTP, A.getAsDecl(), A.getParamTypeForDecl(),
2270
1.19k
            Info, Deduced);
2271
2272
6
      Info.FirstArg = P;
2273
6
      Info.SecondArg = A;
2274
6
      return Sema::TDK_NonDeducedMismatch;
2275
1.19k
    }
2276
2277
    // Can't deduce anything, but that's okay.
2278
276
    return Sema::TDK_Success;
2279
0
  case TemplateArgument::Pack:
2280
0
    llvm_unreachable("Argument packs should be expanded by the caller!");
2281
1.99M
  }
2282
2283
0
  llvm_unreachable("Invalid TemplateArgument Kind!");
2284
0
}
2285
2286
/// Determine whether there is a template argument to be used for
2287
/// deduction.
2288
///
2289
/// This routine "expands" argument packs in-place, overriding its input
2290
/// parameters so that \c Args[ArgIdx] will be the available template argument.
2291
///
2292
/// \returns true if there is another template argument (which will be at
2293
/// \c Args[ArgIdx]), false otherwise.
2294
static bool hasTemplateArgumentForDeduction(ArrayRef<TemplateArgument> &Args,
2295
4.50M
                                            unsigned &ArgIdx) {
2296
4.50M
  if (ArgIdx == Args.size())
2297
580k
    return false;
2298
2299
3.92M
  const TemplateArgument &Arg = Args[ArgIdx];
2300
3.92M
  if (Arg.getKind() != TemplateArgument::Pack)
2301
3.75M
    return true;
2302
2303
170k
  assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2304
0
  Args = Arg.pack_elements();
2305
170k
  ArgIdx = 0;
2306
170k
  return ArgIdx < Args.size();
2307
3.92M
}
2308
2309
/// Determine whether the given set of template arguments has a pack
2310
/// expansion that is not the last template argument.
2311
2.12M
static bool hasPackExpansionBeforeEnd(ArrayRef<TemplateArgument> Args) {
2312
2.12M
  bool FoundPackExpansion = false;
2313
3.89M
  for (const auto &A : Args) {
2314
3.89M
    if (FoundPackExpansion)
2315
12
      return true;
2316
2317
3.89M
    if (A.getKind() == TemplateArgument::Pack)
2318
166k
      return hasPackExpansionBeforeEnd(A.pack_elements());
2319
2320
    // FIXME: If this is a fixed-arity pack expansion from an outer level of
2321
    // templates, it should not be treated as a pack expansion.
2322
3.72M
    if (A.isPackExpansion())
2323
111k
      FoundPackExpansion = true;
2324
3.72M
  }
2325
2326
1.95M
  return false;
2327
2.12M
}
2328
2329
static Sema::TemplateDeductionResult
2330
DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
2331
                        ArrayRef<TemplateArgument> Ps,
2332
                        ArrayRef<TemplateArgument> As,
2333
                        TemplateDeductionInfo &Info,
2334
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2335
1.04M
                        bool NumberOfArgumentsMustMatch) {
2336
  // C++0x [temp.deduct.type]p9:
2337
  //   If the template argument list of P contains a pack expansion that is not
2338
  //   the last template argument, the entire template argument list is a
2339
  //   non-deduced context.
2340
1.04M
  if (hasPackExpansionBeforeEnd(Ps))
2341
2
    return Sema::TDK_Success;
2342
2343
  // C++0x [temp.deduct.type]p9:
2344
  //   If P has a form that contains <T> or <i>, then each argument Pi of the
2345
  //   respective template argument list P is compared with the corresponding
2346
  //   argument Ai of the corresponding template argument list of A.
2347
1.04M
  unsigned ArgIdx = 0, ParamIdx = 0;
2348
2.46M
  for (; hasTemplateArgumentForDeduction(Ps, ParamIdx); 
++ParamIdx1.41M
) {
2349
1.92M
    const TemplateArgument &P = Ps[ParamIdx];
2350
1.92M
    if (!P.isPackExpansion()) {
2351
      // The simple case: deduce template arguments by matching Pi and Ai.
2352
2353
      // Check whether we have enough arguments.
2354
1.89M
      if (!hasTemplateArgumentForDeduction(As, ArgIdx))
2355
12.0k
        return NumberOfArgumentsMustMatch
2356
12.0k
                   ? 
Sema::TDK_MiscellaneousDeductionFailure494
2357
12.0k
                   : 
Sema::TDK_Success11.5k
;
2358
2359
      // C++1z [temp.deduct.type]p9:
2360
      //   During partial ordering, if Ai was originally a pack expansion [and]
2361
      //   Pi is not a pack expansion, template argument deduction fails.
2362
1.88M
      if (As[ArgIdx].isPackExpansion())
2363
3.85k
        return Sema::TDK_MiscellaneousDeductionFailure;
2364
2365
      // Perform deduction for this Pi/Ai pair.
2366
1.87M
      if (auto Result = DeduceTemplateArguments(S, TemplateParams, P,
2367
1.87M
                                                As[ArgIdx], Info, Deduced))
2368
486k
        return Result;
2369
2370
      // Move to the next argument.
2371
1.39M
      ++ArgIdx;
2372
1.39M
      continue;
2373
1.87M
    }
2374
2375
    // The parameter is a pack expansion.
2376
2377
    // C++0x [temp.deduct.type]p9:
2378
    //   If Pi is a pack expansion, then the pattern of Pi is compared with
2379
    //   each remaining argument in the template argument list of A. Each
2380
    //   comparison deduces template arguments for subsequent positions in the
2381
    //   template parameter packs expanded by Pi.
2382
27.5k
    TemplateArgument Pattern = P.getPackExpansionPattern();
2383
2384
    // Prepare to deduce the packs within the pattern.
2385
27.5k
    PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2386
2387
    // Keep track of the deduced template arguments for each parameter pack
2388
    // expanded by this pack expansion (the outer index) and for each
2389
    // template argument (the inner SmallVectors).
2390
147k
    for (; hasTemplateArgumentForDeduction(As, ArgIdx) &&
2391
147k
           
PackScope.hasNextElement()120k
;
2392
120k
         
++ArgIdx120k
) {
2393
      // Deduce template arguments from the pattern.
2394
120k
      if (auto Result = DeduceTemplateArguments(S, TemplateParams, Pattern,
2395
120k
                                                As[ArgIdx], Info, Deduced))
2396
21
        return Result;
2397
2398
120k
      PackScope.nextPackElement();
2399
120k
    }
2400
2401
    // Build argument packs for each of the parameter packs expanded by this
2402
    // pack expansion.
2403
27.5k
    if (auto Result = PackScope.finish())
2404
14
      return Result;
2405
27.5k
  }
2406
2407
544k
  return Sema::TDK_Success;
2408
1.04M
}
2409
2410
static Sema::TemplateDeductionResult
2411
DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
2412
                        const TemplateArgumentList &ParamList,
2413
                        const TemplateArgumentList &ArgList,
2414
                        TemplateDeductionInfo &Info,
2415
534k
                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2416
534k
  return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(),
2417
534k
                                 ArgList.asArray(), Info, Deduced,
2418
534k
                                 /*NumberOfArgumentsMustMatch=*/false);
2419
534k
}
2420
2421
/// Determine whether two template arguments are the same.
2422
static bool isSameTemplateArg(ASTContext &Context,
2423
                              TemplateArgument X,
2424
                              const TemplateArgument &Y,
2425
855k
                              bool PackExpansionMatchesPack = false) {
2426
  // If we're checking deduced arguments (X) against original arguments (Y),
2427
  // we will have flattened packs to non-expansions in X.
2428
855k
  if (PackExpansionMatchesPack && 
X.isPackExpansion()361k
&&
!Y.isPackExpansion()4.67k
)
2429
4.67k
    X = X.getPackExpansionPattern();
2430
2431
855k
  if (X.getKind() != Y.getKind())
2432
0
    return false;
2433
2434
855k
  switch (X.getKind()) {
2435
0
    case TemplateArgument::Null:
2436
0
      llvm_unreachable("Comparing NULL template argument");
2437
2438
549k
    case TemplateArgument::Type:
2439
549k
      return Context.getCanonicalType(X.getAsType()) ==
2440
549k
             Context.getCanonicalType(Y.getAsType());
2441
2442
82
    case TemplateArgument::Declaration:
2443
82
      return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2444
2445
6
    case TemplateArgument::NullPtr:
2446
6
      return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2447
2448
65
    case TemplateArgument::Template:
2449
65
    case TemplateArgument::TemplateExpansion:
2450
65
      return Context.getCanonicalTemplateName(
2451
65
                    X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2452
65
             Context.getCanonicalTemplateName(
2453
65
                    Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
2454
2455
228k
    case TemplateArgument::Integral:
2456
228k
      return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2457
2458
41.8k
    case TemplateArgument::Expression: {
2459
41.8k
      llvm::FoldingSetNodeID XID, YID;
2460
41.8k
      X.getAsExpr()->Profile(XID, Context, true);
2461
41.8k
      Y.getAsExpr()->Profile(YID, Context, true);
2462
41.8k
      return XID == YID;
2463
65
    }
2464
2465
36.0k
    case TemplateArgument::Pack:
2466
36.0k
      if (X.pack_size() != Y.pack_size())
2467
7.05k
        return false;
2468
2469
29.0k
      for (TemplateArgument::pack_iterator XP = X.pack_begin(),
2470
29.0k
                                        XPEnd = X.pack_end(),
2471
29.0k
                                           YP = Y.pack_begin();
2472
80.8k
           XP != XPEnd; 
++XP, ++YP51.8k
)
2473
51.8k
        if (!isSameTemplateArg(Context, *XP, *YP, PackExpansionMatchesPack))
2474
0
          return false;
2475
2476
29.0k
      return true;
2477
855k
  }
2478
2479
0
  llvm_unreachable("Invalid TemplateArgument Kind!");
2480
0
}
2481
2482
/// Allocate a TemplateArgumentLoc where all locations have
2483
/// been initialized to the given location.
2484
///
2485
/// \param Arg The template argument we are producing template argument
2486
/// location information for.
2487
///
2488
/// \param NTTPType For a declaration template argument, the type of
2489
/// the non-type template parameter that corresponds to this template
2490
/// argument. Can be null if no type sugar is available to add to the
2491
/// type from the template argument.
2492
///
2493
/// \param Loc The source location to use for the resulting template
2494
/// argument.
2495
TemplateArgumentLoc
2496
Sema::getTrivialTemplateArgumentLoc(const TemplateArgument &Arg,
2497
1.31M
                                    QualType NTTPType, SourceLocation Loc) {
2498
1.31M
  switch (Arg.getKind()) {
2499
0
  case TemplateArgument::Null:
2500
0
    llvm_unreachable("Can't get a NULL template argument here");
2501
2502
1.12M
  case TemplateArgument::Type:
2503
1.12M
    return TemplateArgumentLoc(
2504
1.12M
        Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2505
2506
127
  case TemplateArgument::Declaration: {
2507
127
    if (NTTPType.isNull())
2508
127
      NTTPType = Arg.getParamTypeForDecl();
2509
127
    Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2510
127
                  .getAs<Expr>();
2511
127
    return TemplateArgumentLoc(TemplateArgument(E), E);
2512
0
  }
2513
2514
1
  case TemplateArgument::NullPtr: {
2515
1
    if (NTTPType.isNull())
2516
1
      NTTPType = Arg.getNullPtrType();
2517
1
    Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2518
1
                  .getAs<Expr>();
2519
1
    return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2520
1
                               E);
2521
0
  }
2522
2523
144k
  case TemplateArgument::Integral: {
2524
144k
    Expr *E =
2525
144k
        BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2526
144k
    return TemplateArgumentLoc(TemplateArgument(E), E);
2527
0
  }
2528
2529
1.67k
    case TemplateArgument::Template:
2530
1.68k
    case TemplateArgument::TemplateExpansion: {
2531
1.68k
      NestedNameSpecifierLocBuilder Builder;
2532
1.68k
      TemplateName Template = Arg.getAsTemplateOrTemplatePattern();
2533
1.68k
      if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2534
0
        Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2535
1.68k
      else if (QualifiedTemplateName *QTN =
2536
1.68k
                   Template.getAsQualifiedTemplateName())
2537
0
        Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2538
2539
1.68k
      if (Arg.getKind() == TemplateArgument::Template)
2540
1.67k
        return TemplateArgumentLoc(Context, Arg,
2541
1.67k
                                   Builder.getWithLocInContext(Context), Loc);
2542
2543
6
      return TemplateArgumentLoc(
2544
6
          Context, Arg, Builder.getWithLocInContext(Context), Loc, Loc);
2545
1.68k
    }
2546
2547
42.1k
  case TemplateArgument::Expression:
2548
42.1k
    return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2549
2550
6
  case TemplateArgument::Pack:
2551
6
    return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2552
1.31M
  }
2553
2554
0
  llvm_unreachable("Invalid TemplateArgument Kind!");
2555
0
}
2556
2557
TemplateArgumentLoc
2558
Sema::getIdentityTemplateArgumentLoc(NamedDecl *TemplateParm,
2559
94
                                     SourceLocation Location) {
2560
94
  return getTrivialTemplateArgumentLoc(
2561
94
      Context.getInjectedTemplateArg(TemplateParm), QualType(), Location);
2562
94
}
2563
2564
/// Convert the given deduced template argument and add it to the set of
2565
/// fully-converted template arguments.
2566
static bool
2567
ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2568
                               DeducedTemplateArgument Arg,
2569
                               NamedDecl *Template,
2570
                               TemplateDeductionInfo &Info,
2571
                               bool IsDeduced,
2572
1.12M
                               SmallVectorImpl<TemplateArgument> &Output) {
2573
1.12M
  auto ConvertArg = [&](DeducedTemplateArgument Arg,
2574
1.24M
                        unsigned ArgumentPackIndex) {
2575
    // Convert the deduced template argument into a template
2576
    // argument that we can check, almost as if the user had written
2577
    // the template argument explicitly.
2578
1.24M
    TemplateArgumentLoc ArgLoc =
2579
1.24M
        S.getTrivialTemplateArgumentLoc(Arg, QualType(), Info.getLocation());
2580
2581
    // Check the template argument, converting it as necessary.
2582
1.24M
    return S.CheckTemplateArgument(
2583
1.24M
        Param, ArgLoc, Template, Template->getLocation(),
2584
1.24M
        Template->getSourceRange().getEnd(), ArgumentPackIndex, Output,
2585
1.24M
        IsDeduced
2586
1.24M
            ? 
(832k
Arg.wasDeducedFromArrayBound()832k
?
Sema::CTAK_DeducedFromArrayBound579
2587
832k
                                              : 
Sema::CTAK_Deduced831k
)
2588
1.24M
            : 
Sema::CTAK_Specified413k
);
2589
1.24M
  };
2590
2591
1.12M
  if (Arg.getKind() == TemplateArgument::Pack) {
2592
    // This is a template argument pack, so check each of its arguments against
2593
    // the template parameter.
2594
57.0k
    SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2595
177k
    for (const auto &P : Arg.pack_elements()) {
2596
      // When converting the deduced template argument, append it to the
2597
      // general output list. We need to do this so that the template argument
2598
      // checking logic has all of the prior template arguments available.
2599
177k
      DeducedTemplateArgument InnerArg(P);
2600
177k
      InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2601
177k
      assert(InnerArg.getKind() != TemplateArgument::Pack &&
2602
177k
             "deduced nested pack");
2603
177k
      if (P.isNull()) {
2604
        // We deduced arguments for some elements of this pack, but not for
2605
        // all of them. This happens if we get a conditionally-non-deduced
2606
        // context in a pack expansion (such as an overload set in one of the
2607
        // arguments).
2608
19
        S.Diag(Param->getLocation(),
2609
19
               diag::err_template_arg_deduced_incomplete_pack)
2610
19
          << Arg << Param;
2611
19
        return true;
2612
19
      }
2613
177k
      if (ConvertArg(InnerArg, PackedArgsBuilder.size()))
2614
2
        return true;
2615
2616
      // Move the converted template argument into our argument pack.
2617
177k
      PackedArgsBuilder.push_back(Output.pop_back_val());
2618
177k
    }
2619
2620
    // If the pack is empty, we still need to substitute into the parameter
2621
    // itself, in case that substitution fails.
2622
57.0k
    if (PackedArgsBuilder.empty()) {
2623
7.98k
      LocalInstantiationScope Scope(S);
2624
7.98k
      TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, Output);
2625
7.98k
      MultiLevelTemplateArgumentList Args(TemplateArgs);
2626
2627
7.98k
      if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2628
1.33k
        Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2629
1.33k
                                         NTTP, Output,
2630
1.33k
                                         Template->getSourceRange());
2631
1.33k
        if (Inst.isInvalid() ||
2632
1.33k
            S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2633
1.33k
                        NTTP->getDeclName()).isNull())
2634
2
          return true;
2635
6.65k
      } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2636
14
        Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2637
14
                                         TTP, Output,
2638
14
                                         Template->getSourceRange());
2639
14
        if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args))
2640
4
          return true;
2641
14
      }
2642
      // For type parameters, no substitution is ever required.
2643
7.98k
    }
2644
2645
    // Create the resulting argument pack.
2646
57.0k
    Output.push_back(
2647
57.0k
        TemplateArgument::CreatePackCopy(S.Context, PackedArgsBuilder));
2648
57.0k
    return false;
2649
57.0k
  }
2650
2651
1.06M
  return ConvertArg(Arg, 0);
2652
1.12M
}
2653
2654
// FIXME: This should not be a template, but
2655
// ClassTemplatePartialSpecializationDecl sadly does not derive from
2656
// TemplateDecl.
2657
template<typename TemplateDeclT>
2658
static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
2659
    Sema &S, TemplateDeclT *Template, bool IsDeduced,
2660
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2661
    TemplateDeductionInfo &Info, SmallVectorImpl<TemplateArgument> &Builder,
2662
    LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2663
937k
    unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2664
937k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2665
2666
2.37M
  for (unsigned I = 0, N = TemplateParams->size(); I != N; 
++I1.43M
) {
2667
1.49M
    NamedDecl *Param = TemplateParams->getParam(I);
2668
2669
    // C++0x [temp.arg.explicit]p3:
2670
    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2671
    //    be deduced to an empty sequence of template arguments.
2672
    // FIXME: Where did the word "trailing" come from?
2673
1.49M
    if (Deduced[I].isNull() && 
Param->isTemplateParameterPack()144k
) {
2674
17.9k
      if (auto Result =
2675
17.9k
              PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2676
8
        return Result;
2677
17.9k
    }
2678
2679
1.49M
    if (!Deduced[I].isNull()) {
2680
1.37M
      if (I < NumAlreadyConverted) {
2681
        // We may have had explicitly-specified template arguments for a
2682
        // template parameter pack (that may or may not have been extended
2683
        // via additional deduced arguments).
2684
265k
        if (Param->isParameterPack() && 
CurrentInstantiationScope18.0k
&&
2685
265k
            
CurrentInstantiationScope->getPartiallySubstitutedPack() == Param18.0k
) {
2686
          // Forget the partially-substituted pack; its substitution is now
2687
          // complete.
2688
18.0k
          CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2689
          // We still need to check the argument in case it was extended by
2690
          // deduction.
2691
247k
        } else {
2692
          // We have already fully type-checked and converted this
2693
          // argument, because it was explicitly-specified. Just record the
2694
          // presence of this argument.
2695
247k
          Builder.push_back(Deduced[I]);
2696
247k
          continue;
2697
247k
        }
2698
265k
      }
2699
2700
      // We may have deduced this argument, so it still needs to be
2701
      // checked and converted.
2702
1.12M
      if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2703
1.12M
                                         IsDeduced, Builder)) {
2704
84
        Info.Param = makeTemplateParameter(Param);
2705
        // FIXME: These template arguments are temporary. Free them!
2706
84
        Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2707
84
        return Sema::TDK_SubstitutionFailure;
2708
84
      }
2709
2710
1.12M
      continue;
2711
1.12M
    }
2712
2713
    // Substitute into the default template argument, if available.
2714
126k
    bool HasDefaultArg = false;
2715
126k
    TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2716
126k
    if (!TD) {
2717
11.5k
      assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2718
11.5k
             isa<VarTemplatePartialSpecializationDecl>(Template));
2719
0
      return Sema::TDK_Incomplete;
2720
11.5k
    }
2721
2722
114k
    TemplateArgumentLoc DefArg;
2723
114k
    {
2724
114k
      Qualifiers ThisTypeQuals;
2725
114k
      CXXRecordDecl *ThisContext = nullptr;
2726
114k
      if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2727
102k
        if (Rec->isLambda())
2728
20
          if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2729
6
            ThisContext = Method->getParent();
2730
6
            ThisTypeQuals = Method->getMethodQualifiers();
2731
6
          }
2732
2733
114k
      Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2734
114k
                                       S.getLangOpts().CPlusPlus17);
2735
2736
114k
      DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2737
114k
          TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2738
114k
          HasDefaultArg);
2739
114k
    }
2740
2741
    // If there was no default argument, deduction is incomplete.
2742
114k
    if (DefArg.getArgument().isNull()) {
2743
37.8k
      Info.Param = makeTemplateParameter(
2744
37.8k
          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2745
37.8k
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2746
37.8k
      if (PartialOverloading) 
break66
;
2747
2748
37.7k
      return HasDefaultArg ? 
Sema::TDK_SubstitutionFailure36.2k
2749
37.7k
                           : 
Sema::TDK_Incomplete1.48k
;
2750
37.8k
    }
2751
2752
    // Check whether we can actually use the default argument.
2753
76.9k
    if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2754
76.9k
                                TD->getSourceRange().getEnd(), 0, Builder,
2755
76.9k
                                Sema::CTAK_Specified)) {
2756
9.42k
      Info.Param = makeTemplateParameter(
2757
9.42k
                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2758
      // FIXME: These template arguments are temporary. Free them!
2759
9.42k
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2760
9.42k
      return Sema::TDK_SubstitutionFailure;
2761
9.42k
    }
2762
2763
    // If we get here, we successfully used the default template argument.
2764
76.9k
  }
2765
2766
878k
  return Sema::TDK_Success;
2767
937k
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult ConvertDeducedTemplateArguments<clang::ClassTemplatePartialSpecializationDecl>(clang::Sema&, clang::ClassTemplatePartialSpecializationDecl*, bool, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::TemplateArgument>&, clang::LocalInstantiationScope*, unsigned int, bool)
Line
Count
Source
2663
241k
    unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2664
241k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2665
2666
619k
  for (unsigned I = 0, N = TemplateParams->size(); I != N; 
++I377k
) {
2667
389k
    NamedDecl *Param = TemplateParams->getParam(I);
2668
2669
    // C++0x [temp.arg.explicit]p3:
2670
    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2671
    //    be deduced to an empty sequence of template arguments.
2672
    // FIXME: Where did the word "trailing" come from?
2673
389k
    if (Deduced[I].isNull() && 
Param->isTemplateParameterPack()11.5k
) {
2674
6
      if (auto Result =
2675
6
              PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2676
0
        return Result;
2677
6
    }
2678
2679
389k
    if (!Deduced[I].isNull()) {
2680
378k
      if (I < NumAlreadyConverted) {
2681
        // We may have had explicitly-specified template arguments for a
2682
        // template parameter pack (that may or may not have been extended
2683
        // via additional deduced arguments).
2684
0
        if (Param->isParameterPack() && CurrentInstantiationScope &&
2685
0
            CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2686
          // Forget the partially-substituted pack; its substitution is now
2687
          // complete.
2688
0
          CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2689
          // We still need to check the argument in case it was extended by
2690
          // deduction.
2691
0
        } else {
2692
          // We have already fully type-checked and converted this
2693
          // argument, because it was explicitly-specified. Just record the
2694
          // presence of this argument.
2695
0
          Builder.push_back(Deduced[I]);
2696
0
          continue;
2697
0
        }
2698
0
      }
2699
2700
      // We may have deduced this argument, so it still needs to be
2701
      // checked and converted.
2702
378k
      if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2703
378k
                                         IsDeduced, Builder)) {
2704
45
        Info.Param = makeTemplateParameter(Param);
2705
        // FIXME: These template arguments are temporary. Free them!
2706
45
        Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2707
45
        return Sema::TDK_SubstitutionFailure;
2708
45
      }
2709
2710
377k
      continue;
2711
378k
    }
2712
2713
    // Substitute into the default template argument, if available.
2714
11.5k
    bool HasDefaultArg = false;
2715
11.5k
    TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2716
11.5k
    if (!TD) {
2717
11.5k
      assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2718
11.5k
             isa<VarTemplatePartialSpecializationDecl>(Template));
2719
0
      return Sema::TDK_Incomplete;
2720
11.5k
    }
2721
2722
0
    TemplateArgumentLoc DefArg;
2723
0
    {
2724
0
      Qualifiers ThisTypeQuals;
2725
0
      CXXRecordDecl *ThisContext = nullptr;
2726
0
      if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2727
0
        if (Rec->isLambda())
2728
0
          if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2729
0
            ThisContext = Method->getParent();
2730
0
            ThisTypeQuals = Method->getMethodQualifiers();
2731
0
          }
2732
2733
0
      Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2734
0
                                       S.getLangOpts().CPlusPlus17);
2735
2736
0
      DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2737
0
          TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2738
0
          HasDefaultArg);
2739
0
    }
2740
2741
    // If there was no default argument, deduction is incomplete.
2742
0
    if (DefArg.getArgument().isNull()) {
2743
0
      Info.Param = makeTemplateParameter(
2744
0
          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2745
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2746
0
      if (PartialOverloading) break;
2747
2748
0
      return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2749
0
                           : Sema::TDK_Incomplete;
2750
0
    }
2751
2752
    // Check whether we can actually use the default argument.
2753
0
    if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2754
0
                                TD->getSourceRange().getEnd(), 0, Builder,
2755
0
                                Sema::CTAK_Specified)) {
2756
0
      Info.Param = makeTemplateParameter(
2757
0
                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2758
      // FIXME: These template arguments are temporary. Free them!
2759
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2760
0
      return Sema::TDK_SubstitutionFailure;
2761
0
    }
2762
2763
    // If we get here, we successfully used the default template argument.
2764
0
  }
2765
2766
229k
  return Sema::TDK_Success;
2767
241k
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult ConvertDeducedTemplateArguments<clang::VarTemplatePartialSpecializationDecl>(clang::Sema&, clang::VarTemplatePartialSpecializationDecl*, bool, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::TemplateArgument>&, clang::LocalInstantiationScope*, unsigned int, bool)
Line
Count
Source
2663
894
    unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2664
894
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2665
2666
1.85k
  for (unsigned I = 0, N = TemplateParams->size(); I != N; 
++I957
) {
2667
958
    NamedDecl *Param = TemplateParams->getParam(I);
2668
2669
    // C++0x [temp.arg.explicit]p3:
2670
    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2671
    //    be deduced to an empty sequence of template arguments.
2672
    // FIXME: Where did the word "trailing" come from?
2673
958
    if (Deduced[I].isNull() && 
Param->isTemplateParameterPack()1
) {
2674
0
      if (auto Result =
2675
0
              PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2676
0
        return Result;
2677
0
    }
2678
2679
958
    if (!Deduced[I].isNull()) {
2680
957
      if (I < NumAlreadyConverted) {
2681
        // We may have had explicitly-specified template arguments for a
2682
        // template parameter pack (that may or may not have been extended
2683
        // via additional deduced arguments).
2684
0
        if (Param->isParameterPack() && CurrentInstantiationScope &&
2685
0
            CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2686
          // Forget the partially-substituted pack; its substitution is now
2687
          // complete.
2688
0
          CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2689
          // We still need to check the argument in case it was extended by
2690
          // deduction.
2691
0
        } else {
2692
          // We have already fully type-checked and converted this
2693
          // argument, because it was explicitly-specified. Just record the
2694
          // presence of this argument.
2695
0
          Builder.push_back(Deduced[I]);
2696
0
          continue;
2697
0
        }
2698
0
      }
2699
2700
      // We may have deduced this argument, so it still needs to be
2701
      // checked and converted.
2702
957
      if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2703
957
                                         IsDeduced, Builder)) {
2704
0
        Info.Param = makeTemplateParameter(Param);
2705
        // FIXME: These template arguments are temporary. Free them!
2706
0
        Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2707
0
        return Sema::TDK_SubstitutionFailure;
2708
0
      }
2709
2710
957
      continue;
2711
957
    }
2712
2713
    // Substitute into the default template argument, if available.
2714
1
    bool HasDefaultArg = false;
2715
1
    TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2716
1
    if (!TD) {
2717
1
      assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2718
1
             isa<VarTemplatePartialSpecializationDecl>(Template));
2719
0
      return Sema::TDK_Incomplete;
2720
1
    }
2721
2722
0
    TemplateArgumentLoc DefArg;
2723
0
    {
2724
0
      Qualifiers ThisTypeQuals;
2725
0
      CXXRecordDecl *ThisContext = nullptr;
2726
0
      if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2727
0
        if (Rec->isLambda())
2728
0
          if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2729
0
            ThisContext = Method->getParent();
2730
0
            ThisTypeQuals = Method->getMethodQualifiers();
2731
0
          }
2732
2733
0
      Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2734
0
                                       S.getLangOpts().CPlusPlus17);
2735
2736
0
      DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2737
0
          TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2738
0
          HasDefaultArg);
2739
0
    }
2740
2741
    // If there was no default argument, deduction is incomplete.
2742
0
    if (DefArg.getArgument().isNull()) {
2743
0
      Info.Param = makeTemplateParameter(
2744
0
          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2745
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2746
0
      if (PartialOverloading) break;
2747
2748
0
      return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2749
0
                           : Sema::TDK_Incomplete;
2750
0
    }
2751
2752
    // Check whether we can actually use the default argument.
2753
0
    if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2754
0
                                TD->getSourceRange().getEnd(), 0, Builder,
2755
0
                                Sema::CTAK_Specified)) {
2756
0
      Info.Param = makeTemplateParameter(
2757
0
                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2758
      // FIXME: These template arguments are temporary. Free them!
2759
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2760
0
      return Sema::TDK_SubstitutionFailure;
2761
0
    }
2762
2763
    // If we get here, we successfully used the default template argument.
2764
0
  }
2765
2766
893
  return Sema::TDK_Success;
2767
894
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult ConvertDeducedTemplateArguments<clang::FunctionTemplateDecl>(clang::Sema&, clang::FunctionTemplateDecl*, bool, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::TemplateArgument>&, clang::LocalInstantiationScope*, unsigned int, bool)
Line
Count
Source
2663
537k
    unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2664
537k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2665
2666
1.24M
  for (unsigned I = 0, N = TemplateParams->size(); I != N; 
++I710k
) {
2667
758k
    NamedDecl *Param = TemplateParams->getParam(I);
2668
2669
    // C++0x [temp.arg.explicit]p3:
2670
    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2671
    //    be deduced to an empty sequence of template arguments.
2672
    // FIXME: Where did the word "trailing" come from?
2673
758k
    if (Deduced[I].isNull() && 
Param->isTemplateParameterPack()132k
) {
2674
17.9k
      if (auto Result =
2675
17.9k
              PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2676
8
        return Result;
2677
17.9k
    }
2678
2679
758k
    if (!Deduced[I].isNull()) {
2680
643k
      if (I < NumAlreadyConverted) {
2681
        // We may have had explicitly-specified template arguments for a
2682
        // template parameter pack (that may or may not have been extended
2683
        // via additional deduced arguments).
2684
265k
        if (Param->isParameterPack() && 
CurrentInstantiationScope18.0k
&&
2685
265k
            
CurrentInstantiationScope->getPartiallySubstitutedPack() == Param18.0k
) {
2686
          // Forget the partially-substituted pack; its substitution is now
2687
          // complete.
2688
18.0k
          CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2689
          // We still need to check the argument in case it was extended by
2690
          // deduction.
2691
247k
        } else {
2692
          // We have already fully type-checked and converted this
2693
          // argument, because it was explicitly-specified. Just record the
2694
          // presence of this argument.
2695
247k
          Builder.push_back(Deduced[I]);
2696
247k
          continue;
2697
247k
        }
2698
265k
      }
2699
2700
      // We may have deduced this argument, so it still needs to be
2701
      // checked and converted.
2702
396k
      if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2703
396k
                                         IsDeduced, Builder)) {
2704
36
        Info.Param = makeTemplateParameter(Param);
2705
        // FIXME: These template arguments are temporary. Free them!
2706
36
        Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2707
36
        return Sema::TDK_SubstitutionFailure;
2708
36
      }
2709
2710
396k
      continue;
2711
396k
    }
2712
2713
    // Substitute into the default template argument, if available.
2714
114k
    bool HasDefaultArg = false;
2715
114k
    TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2716
114k
    if (!TD) {
2717
0
      assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2718
0
             isa<VarTemplatePartialSpecializationDecl>(Template));
2719
0
      return Sema::TDK_Incomplete;
2720
0
    }
2721
2722
114k
    TemplateArgumentLoc DefArg;
2723
114k
    {
2724
114k
      Qualifiers ThisTypeQuals;
2725
114k
      CXXRecordDecl *ThisContext = nullptr;
2726
114k
      if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2727
102k
        if (Rec->isLambda())
2728
20
          if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2729
6
            ThisContext = Method->getParent();
2730
6
            ThisTypeQuals = Method->getMethodQualifiers();
2731
6
          }
2732
2733
114k
      Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2734
114k
                                       S.getLangOpts().CPlusPlus17);
2735
2736
114k
      DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2737
114k
          TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2738
114k
          HasDefaultArg);
2739
114k
    }
2740
2741
    // If there was no default argument, deduction is incomplete.
2742
114k
    if (DefArg.getArgument().isNull()) {
2743
37.8k
      Info.Param = makeTemplateParameter(
2744
37.8k
          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2745
37.8k
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2746
37.8k
      if (PartialOverloading) 
break66
;
2747
2748
37.7k
      return HasDefaultArg ? 
Sema::TDK_SubstitutionFailure36.2k
2749
37.7k
                           : 
Sema::TDK_Incomplete1.48k
;
2750
37.8k
    }
2751
2752
    // Check whether we can actually use the default argument.
2753
76.9k
    if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2754
76.9k
                                TD->getSourceRange().getEnd(), 0, Builder,
2755
76.9k
                                Sema::CTAK_Specified)) {
2756
9.42k
      Info.Param = makeTemplateParameter(
2757
9.42k
                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2758
      // FIXME: These template arguments are temporary. Free them!
2759
9.42k
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2760
9.42k
      return Sema::TDK_SubstitutionFailure;
2761
9.42k
    }
2762
2763
    // If we get here, we successfully used the default template argument.
2764
76.9k
  }
2765
2766
490k
  return Sema::TDK_Success;
2767
537k
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult ConvertDeducedTemplateArguments<clang::TemplateDecl>(clang::Sema&, clang::TemplateDecl*, bool, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&, llvm::SmallVectorImpl<clang::TemplateArgument>&, clang::LocalInstantiationScope*, unsigned int, bool)
Line
Count
Source
2663
158k
    unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2664
158k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2665
2666
506k
  for (unsigned I = 0, N = TemplateParams->size(); I != N; 
++I348k
) {
2667
348k
    NamedDecl *Param = TemplateParams->getParam(I);
2668
2669
    // C++0x [temp.arg.explicit]p3:
2670
    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2671
    //    be deduced to an empty sequence of template arguments.
2672
    // FIXME: Where did the word "trailing" come from?
2673
348k
    if (Deduced[I].isNull() && 
Param->isTemplateParameterPack()0
) {
2674
0
      if (auto Result =
2675
0
              PackDeductionScope(S, TemplateParams, Deduced, Info, I).finish())
2676
0
        return Result;
2677
0
    }
2678
2679
348k
    if (!Deduced[I].isNull()) {
2680
348k
      if (I < NumAlreadyConverted) {
2681
        // We may have had explicitly-specified template arguments for a
2682
        // template parameter pack (that may or may not have been extended
2683
        // via additional deduced arguments).
2684
0
        if (Param->isParameterPack() && CurrentInstantiationScope &&
2685
0
            CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2686
          // Forget the partially-substituted pack; its substitution is now
2687
          // complete.
2688
0
          CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2689
          // We still need to check the argument in case it was extended by
2690
          // deduction.
2691
0
        } else {
2692
          // We have already fully type-checked and converted this
2693
          // argument, because it was explicitly-specified. Just record the
2694
          // presence of this argument.
2695
0
          Builder.push_back(Deduced[I]);
2696
0
          continue;
2697
0
        }
2698
0
      }
2699
2700
      // We may have deduced this argument, so it still needs to be
2701
      // checked and converted.
2702
348k
      if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2703
348k
                                         IsDeduced, Builder)) {
2704
3
        Info.Param = makeTemplateParameter(Param);
2705
        // FIXME: These template arguments are temporary. Free them!
2706
3
        Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2707
3
        return Sema::TDK_SubstitutionFailure;
2708
3
      }
2709
2710
348k
      continue;
2711
348k
    }
2712
2713
    // Substitute into the default template argument, if available.
2714
0
    bool HasDefaultArg = false;
2715
0
    TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2716
0
    if (!TD) {
2717
0
      assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2718
0
             isa<VarTemplatePartialSpecializationDecl>(Template));
2719
0
      return Sema::TDK_Incomplete;
2720
0
    }
2721
2722
0
    TemplateArgumentLoc DefArg;
2723
0
    {
2724
0
      Qualifiers ThisTypeQuals;
2725
0
      CXXRecordDecl *ThisContext = nullptr;
2726
0
      if (auto *Rec = dyn_cast<CXXRecordDecl>(TD->getDeclContext()))
2727
0
        if (Rec->isLambda())
2728
0
          if (auto *Method = dyn_cast<CXXMethodDecl>(Rec->getDeclContext())) {
2729
0
            ThisContext = Method->getParent();
2730
0
            ThisTypeQuals = Method->getMethodQualifiers();
2731
0
          }
2732
2733
0
      Sema::CXXThisScopeRAII ThisScope(S, ThisContext, ThisTypeQuals,
2734
0
                                       S.getLangOpts().CPlusPlus17);
2735
2736
0
      DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2737
0
          TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2738
0
          HasDefaultArg);
2739
0
    }
2740
2741
    // If there was no default argument, deduction is incomplete.
2742
0
    if (DefArg.getArgument().isNull()) {
2743
0
      Info.Param = makeTemplateParameter(
2744
0
          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2745
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2746
0
      if (PartialOverloading) break;
2747
2748
0
      return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2749
0
                           : Sema::TDK_Incomplete;
2750
0
    }
2751
2752
    // Check whether we can actually use the default argument.
2753
0
    if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2754
0
                                TD->getSourceRange().getEnd(), 0, Builder,
2755
0
                                Sema::CTAK_Specified)) {
2756
0
      Info.Param = makeTemplateParameter(
2757
0
                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2758
      // FIXME: These template arguments are temporary. Free them!
2759
0
      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2760
0
      return Sema::TDK_SubstitutionFailure;
2761
0
    }
2762
2763
    // If we get here, we successfully used the default template argument.
2764
0
  }
2765
2766
158k
  return Sema::TDK_Success;
2767
158k
}
2768
2769
400k
static DeclContext *getAsDeclContextOrEnclosing(Decl *D) {
2770
400k
  if (auto *DC = dyn_cast<DeclContext>(D))
2771
241k
    return DC;
2772
158k
  return D->getDeclContext();
2773
400k
}
2774
2775
template<typename T> struct IsPartialSpecialization {
2776
  static constexpr bool value = false;
2777
};
2778
template<>
2779
struct IsPartialSpecialization<ClassTemplatePartialSpecializationDecl> {
2780
  static constexpr bool value = true;
2781
};
2782
template<>
2783
struct IsPartialSpecialization<VarTemplatePartialSpecializationDecl> {
2784
  static constexpr bool value = true;
2785
};
2786
2787
template<typename TemplateDeclT>
2788
static Sema::TemplateDeductionResult
2789
CheckDeducedArgumentConstraints(Sema& S, TemplateDeclT *Template,
2790
                                ArrayRef<TemplateArgument> DeducedArgs,
2791
357k
                                TemplateDeductionInfo& Info) {
2792
357k
  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2793
357k
  Template->getAssociatedConstraints(AssociatedConstraints);
2794
357k
  if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints,
2795
357k
                                    DeducedArgs, Info.getLocation(),
2796
357k
                                    Info.AssociatedConstraintsSatisfaction) ||
2797
357k
      
!Info.AssociatedConstraintsSatisfaction.IsSatisfied357k
) {
2798
19
    Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs));
2799
19
    return Sema::TDK_ConstraintsNotSatisfied;
2800
19
  }
2801
357k
  return Sema::TDK_Success;
2802
357k
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult CheckDeducedArgumentConstraints<clang::ClassTemplatePartialSpecializationDecl>(clang::Sema&, clang::ClassTemplatePartialSpecializationDecl*, llvm::ArrayRef<clang::TemplateArgument>, clang::sema::TemplateDeductionInfo&)
Line
Count
Source
2791
198k
                                TemplateDeductionInfo& Info) {
2792
198k
  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2793
198k
  Template->getAssociatedConstraints(AssociatedConstraints);
2794
198k
  if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints,
2795
198k
                                    DeducedArgs, Info.getLocation(),
2796
198k
                                    Info.AssociatedConstraintsSatisfaction) ||
2797
198k
      
!Info.AssociatedConstraintsSatisfaction.IsSatisfied198k
) {
2798
8
    Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs));
2799
8
    return Sema::TDK_ConstraintsNotSatisfied;
2800
8
  }
2801
198k
  return Sema::TDK_Success;
2802
198k
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult CheckDeducedArgumentConstraints<clang::VarTemplatePartialSpecializationDecl>(clang::Sema&, clang::VarTemplatePartialSpecializationDecl*, llvm::ArrayRef<clang::TemplateArgument>, clang::sema::TemplateDeductionInfo&)
Line
Count
Source
2791
889
                                TemplateDeductionInfo& Info) {
2792
889
  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2793
889
  Template->getAssociatedConstraints(AssociatedConstraints);
2794
889
  if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints,
2795
889
                                    DeducedArgs, Info.getLocation(),
2796
889
                                    Info.AssociatedConstraintsSatisfaction) ||
2797
889
      
!Info.AssociatedConstraintsSatisfaction.IsSatisfied885
) {
2798
11
    Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs));
2799
11
    return Sema::TDK_ConstraintsNotSatisfied;
2800
11
  }
2801
878
  return Sema::TDK_Success;
2802
889
}
SemaTemplateDeduction.cpp:clang::Sema::TemplateDeductionResult CheckDeducedArgumentConstraints<clang::TemplateDecl>(clang::Sema&, clang::TemplateDecl*, llvm::ArrayRef<clang::TemplateArgument>, clang::sema::TemplateDeductionInfo&)
Line
Count
Source
2791
158k
                                TemplateDeductionInfo& Info) {
2792
158k
  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
2793
158k
  Template->getAssociatedConstraints(AssociatedConstraints);
2794
158k
  if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints,
2795
158k
                                    DeducedArgs, Info.getLocation(),
2796
158k
                                    Info.AssociatedConstraintsSatisfaction) ||
2797
158k
      !Info.AssociatedConstraintsSatisfaction.IsSatisfied) {
2798
0
    Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs));
2799
0
    return Sema::TDK_ConstraintsNotSatisfied;
2800
0
  }
2801
158k
  return Sema::TDK_Success;
2802
158k
}
2803
2804
/// Complete template argument deduction for a partial specialization.
2805
template <typename T>
2806
static std::enable_if_t<IsPartialSpecialization<T>::value,
2807
                        Sema::TemplateDeductionResult>
2808
FinishTemplateArgumentDeduction(
2809
    Sema &S, T *Partial, bool IsPartialOrdering,
2810
    const TemplateArgumentList &TemplateArgs,
2811
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2812
242k
    TemplateDeductionInfo &Info) {
2813
  // Unevaluated SFINAE context.
2814
242k
  EnterExpressionEvaluationContext Unevaluated(
2815
242k
      S, Sema::ExpressionEvaluationContext::Unevaluated);
2816
242k
  Sema::SFINAETrap Trap(S);
2817
2818
242k
  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2819
2820
  // C++ [temp.deduct.type]p2:
2821
  //   [...] or if any template argument remains neither deduced nor
2822
  //   explicitly specified, template argument deduction fails.
2823
242k
  SmallVector<TemplateArgument, 4> Builder;
2824
242k
  if (auto Result = ConvertDeducedTemplateArguments(
2825
242k
          S, Partial, IsPartialOrdering, Deduced, Info, Builder))
2826
11.6k
    return Result;
2827
2828
  // Form the template argument list from the deduced template arguments.
2829
230k
  TemplateArgumentList *DeducedArgumentList
2830
230k
    = TemplateArgumentList::CreateCopy(S.Context, Builder);
2831
2832
230k
  Info.reset(DeducedArgumentList);
2833
2834
  // Substitute the deduced template arguments into the template
2835
  // arguments of the class template partial specialization, and
2836
  // verify that the instantiated template arguments are both valid
2837
  // and are equivalent to the template arguments originally provided
2838
  // to the class template.
2839
230k
  LocalInstantiationScope InstScope(S);
2840
230k
  auto *Template = Partial->getSpecializedTemplate();
2841
230k
  const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2842
230k
      Partial->getTemplateArgsAsWritten();
2843
2844
230k
  TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2845
230k
                                    PartialTemplArgInfo->RAngleLoc);
2846
2847
230k
  if (S.SubstTemplateArguments(
2848
230k
          PartialTemplArgInfo->arguments(),
2849
230k
          MultiLevelTemplateArgumentList(*DeducedArgumentList), InstArgs)) {
2850
12.2k
    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2851
12.2k
    if (ParamIdx >= Partial->getTemplateParameters()->size())
2852
12.2k
      ParamIdx = Partial->getTemplateParameters()->size() - 1;
2853
2854
12.2k
    Decl *Param = const_cast<NamedDecl *>(
2855
12.2k
        Partial->getTemplateParameters()->getParam(ParamIdx));
2856
12.2k
    Info.Param = makeTemplateParameter(Param);
2857
12.2k
    Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
2858
12.2k
    return Sema::TDK_SubstitutionFailure;
2859
12.2k
  }
2860
2861
218k
  bool ConstraintsNotSatisfied;
2862
218k
  SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2863
218k
  if (S.CheckTemplateArgumentList(Template, Partial->getLocation(), InstArgs,
2864
218k
                                  false, ConvertedInstArgs,
2865
218k
                                  /*UpdateArgsWithConversions=*/true,
2866
218k
                                  &ConstraintsNotSatisfied))
2867
2
    return ConstraintsNotSatisfied ? 
Sema::TDK_ConstraintsNotSatisfied0
:
2868
2
                                     Sema::TDK_SubstitutionFailure;
2869
2870
218k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2871
654k
  for (unsigned I = 0, E = TemplateParams->size(); I != E; 
++I436k
) {
2872
455k
    TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2873
455k
    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2874
19.0k
      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2875
19.0k
      Info.FirstArg = TemplateArgs[I];
2876
19.0k
      Info.SecondArg = InstArg;
2877
19.0k
      return Sema::TDK_NonDeducedMismatch;
2878
19.0k
    }
2879
455k
  }
2880
2881
199k
  if (Trap.hasErrorOccurred())
2882
0
    return Sema::TDK_SubstitutionFailure;
2883
2884
199k
  if (auto Result = CheckDeducedArgumentConstraints(S, Partial, Builder, Info))
2885
19
    return Result;
2886
2887
199k
  return Sema::TDK_Success;
2888
199k
}
SemaTemplateDeduction.cpp:std::__1::enable_if<IsPartialSpecialization<clang::ClassTemplatePartialSpecializationDecl>::value, clang::Sema::TemplateDeductionResult>::type FinishTemplateArgumentDeduction<clang::ClassTemplatePartialSpecializationDecl>(clang::Sema&, clang::ClassTemplatePartialSpecializationDecl*, bool, clang::TemplateArgumentList const&, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&)
Line
Count
Source
2812
241k
    TemplateDeductionInfo &Info) {
2813
  // Unevaluated SFINAE context.
2814
241k
  EnterExpressionEvaluationContext Unevaluated(
2815
241k
      S, Sema::ExpressionEvaluationContext::Unevaluated);
2816
241k
  Sema::SFINAETrap Trap(S);
2817
2818
241k
  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2819
2820
  // C++ [temp.deduct.type]p2:
2821
  //   [...] or if any template argument remains neither deduced nor
2822
  //   explicitly specified, template argument deduction fails.
2823
241k
  SmallVector<TemplateArgument, 4> Builder;
2824
241k
  if (auto Result = ConvertDeducedTemplateArguments(
2825
241k
          S, Partial, IsPartialOrdering, Deduced, Info, Builder))
2826
11.6k
    return Result;
2827
2828
  // Form the template argument list from the deduced template arguments.
2829
229k
  TemplateArgumentList *DeducedArgumentList
2830
229k
    = TemplateArgumentList::CreateCopy(S.Context, Builder);
2831
2832
229k
  Info.reset(DeducedArgumentList);
2833
2834
  // Substitute the deduced template arguments into the template
2835
  // arguments of the class template partial specialization, and
2836
  // verify that the instantiated template arguments are both valid
2837
  // and are equivalent to the template arguments originally provided
2838
  // to the class template.
2839
229k
  LocalInstantiationScope InstScope(S);
2840
229k
  auto *Template = Partial->getSpecializedTemplate();
2841
229k
  const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2842
229k
      Partial->getTemplateArgsAsWritten();
2843
2844
229k
  TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2845
229k
                                    PartialTemplArgInfo->RAngleLoc);
2846
2847
229k
  if (S.SubstTemplateArguments(
2848
229k
          PartialTemplArgInfo->arguments(),
2849
229k
          MultiLevelTemplateArgumentList(*DeducedArgumentList), InstArgs)) {
2850
12.2k
    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2851
12.2k
    if (ParamIdx >= Partial->getTemplateParameters()->size())
2852
12.2k
      ParamIdx = Partial->getTemplateParameters()->size() - 1;
2853
2854
12.2k
    Decl *Param = const_cast<NamedDecl *>(
2855
12.2k
        Partial->getTemplateParameters()->getParam(ParamIdx));
2856
12.2k
    Info.Param = makeTemplateParameter(Param);
2857
12.2k
    Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
2858
12.2k
    return Sema::TDK_SubstitutionFailure;
2859
12.2k
  }
2860
2861
217k
  bool ConstraintsNotSatisfied;
2862
217k
  SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2863
217k
  if (S.CheckTemplateArgumentList(Template, Partial->getLocation(), InstArgs,
2864
217k
                                  false, ConvertedInstArgs,
2865
217k
                                  /*UpdateArgsWithConversions=*/true,
2866
217k
                                  &ConstraintsNotSatisfied))
2867
2
    return ConstraintsNotSatisfied ? 
Sema::TDK_ConstraintsNotSatisfied0
:
2868
2
                                     Sema::TDK_SubstitutionFailure;
2869
2870
217k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2871
652k
  for (unsigned I = 0, E = TemplateParams->size(); I != E; 
++I434k
) {
2872
453k
    TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2873
453k
    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2874
18.9k
      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2875
18.9k
      Info.FirstArg = TemplateArgs[I];
2876
18.9k
      Info.SecondArg = InstArg;
2877
18.9k
      return Sema::TDK_NonDeducedMismatch;
2878
18.9k
    }
2879
453k
  }
2880
2881
198k
  if (Trap.hasErrorOccurred())
2882
0
    return Sema::TDK_SubstitutionFailure;
2883
2884
198k
  if (auto Result = CheckDeducedArgumentConstraints(S, Partial, Builder, Info))
2885
8
    return Result;
2886
2887
198k
  return Sema::TDK_Success;
2888
198k
}
SemaTemplateDeduction.cpp:std::__1::enable_if<IsPartialSpecialization<clang::VarTemplatePartialSpecializationDecl>::value, clang::Sema::TemplateDeductionResult>::type FinishTemplateArgumentDeduction<clang::VarTemplatePartialSpecializationDecl>(clang::Sema&, clang::VarTemplatePartialSpecializationDecl*, bool, clang::TemplateArgumentList const&, llvm::SmallVectorImpl<clang::DeducedTemplateArgument>&, clang::sema::TemplateDeductionInfo&)
Line
Count
Source
2812
894
    TemplateDeductionInfo &Info) {
2813
  // Unevaluated SFINAE context.
2814
894
  EnterExpressionEvaluationContext Unevaluated(
2815
894
      S, Sema::ExpressionEvaluationContext::Unevaluated);
2816
894
  Sema::SFINAETrap Trap(S);
2817
2818
894
  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2819
2820
  // C++ [temp.deduct.type]p2:
2821
  //   [...] or if any template argument remains neither deduced nor
2822
  //   explicitly specified, template argument deduction fails.
2823
894
  SmallVector<TemplateArgument, 4> Builder;
2824
894
  if (auto Result = ConvertDeducedTemplateArguments(
2825
894
          S, Partial, IsPartialOrdering, Deduced, Info, Builder))
2826
1
    return Result;
2827
2828
  // Form the template argument list from the deduced template arguments.
2829
893
  TemplateArgumentList *DeducedArgumentList
2830
893
    = TemplateArgumentList::CreateCopy(S.Context, Builder);
2831
2832
893
  Info.reset(DeducedArgumentList);
2833
2834
  // Substitute the deduced template arguments into the template
2835
  // arguments of the class template partial specialization, and
2836
  // verify that the instantiated template arguments are both valid
2837
  // and are equivalent to the template arguments originally provided
2838
  // to the class template.
2839
893
  LocalInstantiationScope InstScope(S);
2840
893
  auto *Template = Partial->getSpecializedTemplate();
2841
893
  const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2842
893
      Partial->getTemplateArgsAsWritten();
2843
2844
893
  TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2845
893
                                    PartialTemplArgInfo->RAngleLoc);
2846
2847
893
  if (S.SubstTemplateArguments(
2848
893
          PartialTemplArgInfo->arguments(),
2849
893
          MultiLevelTemplateArgumentList(*DeducedArgumentList), InstArgs)) {
2850
2
    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2851
2
    if (ParamIdx >= Partial->getTemplateParameters()->size())
2852
2
      ParamIdx = Partial->getTemplateParameters()->size() - 1;
2853
2854
2
    Decl *Param = const_cast<NamedDecl *>(
2855
2
        Partial->getTemplateParameters()->getParam(ParamIdx));
2856
2
    Info.Param = makeTemplateParameter(Param);
2857
2
    Info.FirstArg = (*PartialTemplArgInfo)[ArgIdx].getArgument();
2858
2
    return Sema::TDK_SubstitutionFailure;
2859
2
  }
2860
2861
891
  bool ConstraintsNotSatisfied;
2862
891
  SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2863
891
  if (S.CheckTemplateArgumentList(Template, Partial->getLocation(), InstArgs,
2864
891
                                  false, ConvertedInstArgs,
2865
891
                                  /*UpdateArgsWithConversions=*/true,
2866
891
                                  &ConstraintsNotSatisfied))
2867
0
    return ConstraintsNotSatisfied ? Sema::TDK_ConstraintsNotSatisfied :
2868
0
                                     Sema::TDK_SubstitutionFailure;
2869
2870
891
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2871
2.56k
  for (unsigned I = 0, E = TemplateParams->size(); I != E; 
++I1.67k
) {
2872
1.67k
    TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2873
1.67k
    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2874
2
      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2875
2
      Info.FirstArg = TemplateArgs[I];
2876
2
      Info.SecondArg = InstArg;
2877
2
      return Sema::TDK_NonDeducedMismatch;
2878
2
    }
2879
1.67k
  }
2880
2881
889
  if (Trap.hasErrorOccurred())
2882
0
    return Sema::TDK_SubstitutionFailure;
2883
2884
889
  if (auto Result = CheckDeducedArgumentConstraints(S, Partial, Builder, Info))
2885
11
    return Result;
2886
2887
878
  return Sema::TDK_Success;
2888
889
}
2889
2890
/// Complete template argument deduction for a class or variable template,
2891
/// when partial ordering against a partial specialization.
2892
// FIXME: Factor out duplication with partial specialization version above.
2893
static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2894
    Sema &S, TemplateDecl *Template, bool PartialOrdering,
2895
    const TemplateArgumentList &TemplateArgs,
2896
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2897
158k
    TemplateDeductionInfo &Info) {
2898
  // Unevaluated SFINAE context.
2899
158k
  EnterExpressionEvaluationContext Unevaluated(
2900
158k
      S, Sema::ExpressionEvaluationContext::Unevaluated);
2901
158k
  Sema::SFINAETrap Trap(S);
2902
2903
158k
  Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
2904
2905
  // C++ [temp.deduct.type]p2:
2906
  //   [...] or if any template argument remains neither deduced nor
2907
  //   explicitly specified, template argument deduction fails.
2908
158k
  SmallVector<TemplateArgument, 4> Builder;
2909
158k
  if (auto Result = ConvertDeducedTemplateArguments(
2910
158k
          S, Template, /*IsDeduced*/PartialOrdering, Deduced, Info, Builder))
2911
3
    return Result;
2912
2913
  // Check that we produced the correct argument list.
2914
158k
  TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2915
506k
  for (unsigned I = 0, E = TemplateParams->size(); I != E; 
++I348k
) {
2916
348k
    TemplateArgument InstArg = Builder[I];
2917
348k
    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
2918
348k
                           /*PackExpansionMatchesPack*/true)) {
2919
0
      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2920
0
      Info.FirstArg = TemplateArgs[I];
2921
0
      Info.SecondArg = InstArg;
2922
0
      return Sema::TDK_NonDeducedMismatch;
2923
0
    }
2924
348k
  }
2925
2926
158k
  if (Trap.hasErrorOccurred())
2927
0
    return Sema::TDK_SubstitutionFailure;
2928
2929
158k
  if (auto Result = CheckDeducedArgumentConstraints(S, Template, Builder,
2930
158k
                                                    Info))
2931
0
    return Result;
2932
2933
158k
  return Sema::TDK_Success;
2934
158k
}
2935
2936
/// Perform template argument deduction to determine whether
2937
/// the given template arguments match the given class template
2938
/// partial specialization per C++ [temp.class.spec.match].
2939
Sema::TemplateDeductionResult
2940
Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2941
                              const TemplateArgumentList &TemplateArgs,
2942
533k
                              TemplateDeductionInfo &Info) {
2943
533k
  if (Partial->isInvalidDecl())
2944
4
    return TDK_Invalid;
2945
2946
  // C++ [temp.class.spec.match]p2:
2947
  //   A partial specialization matches a given actual template
2948
  //   argument list if the template arguments of the partial
2949
  //   specialization can be deduced from the actual template argument
2950
  //   list (14.8.2).
2951
2952
  // Unevaluated SFINAE context.
2953
533k
  EnterExpressionEvaluationContext Unevaluated(
2954
533k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
2955
533k
  SFINAETrap Trap(*this);
2956
2957
  // This deduction has no relation to any outer instantiation we might be
2958
  // performing.
2959
533k
  LocalInstantiationScope InstantiationScope(*this);
2960
2961
533k
  SmallVector<DeducedTemplateArgument, 4> Deduced;
2962
533k
  Deduced.resize(Partial->getTemplateParameters()->size());
2963
533k
  if (TemplateDeductionResult Result
2964
533k
        = ::DeduceTemplateArguments(*this,
2965
533k
                                    Partial->getTemplateParameters(),
2966
533k
                                    Partial->getTemplateArgs(),
2967
533k
                                    TemplateArgs, Info, Deduced))
2968
318k
    return Result;
2969
2970
214k
  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2971
214k
  InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2972
214k
                             Info);
2973
214k
  if (Inst.isInvalid())
2974
0
    return TDK_InstantiationDepth;
2975
2976
214k
  if (Trap.hasErrorOccurred())
2977
0
    return Sema::TDK_SubstitutionFailure;
2978
2979
214k
  TemplateDeductionResult Result;
2980
214k
  runWithSufficientStackSpace(Info.getLocation(), [&] {
2981
214k
    Result = ::FinishTemplateArgumentDeduction(*this, Partial,
2982
214k
                                               /*IsPartialOrdering=*/false,
2983
214k
                                               TemplateArgs, Deduced, Info);
2984
214k
  });
2985
214k
  return Result;
2986
214k
}
2987
2988
/// Perform template argument deduction to determine whether
2989
/// the given template arguments match the given variable template
2990
/// partial specialization per C++ [temp.class.spec.match].
2991
Sema::TemplateDeductionResult
2992
Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2993
                              const TemplateArgumentList &TemplateArgs,
2994
1.04k
                              TemplateDeductionInfo &Info) {
2995
1.04k
  if (Partial->isInvalidDecl())
2996
0
    return TDK_Invalid;
2997
2998
  // C++ [temp.class.spec.match]p2:
2999
  //   A partial specialization matches a given actual template
3000
  //   argument list if the template arguments of the partial
3001
  //   specialization can be deduced from the actual template argument
3002
  //   list (14.8.2).
3003
3004
  // Unevaluated SFINAE context.
3005
1.04k
  EnterExpressionEvaluationContext Unevaluated(
3006
1.04k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
3007
1.04k
  SFINAETrap Trap(*this);
3008
3009
  // This deduction has no relation to any outer instantiation we might be
3010
  // performing.
3011
1.04k
  LocalInstantiationScope InstantiationScope(*this);
3012
3013
1.04k
  SmallVector<DeducedTemplateArgument, 4> Deduced;
3014
1.04k
  Deduced.resize(Partial->getTemplateParameters()->size());
3015
1.04k
  if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
3016
1.04k
          *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
3017
1.04k
          TemplateArgs, Info, Deduced))
3018
202
    return Result;
3019
3020
844
  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3021
844
  InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
3022
844
                             Info);
3023
844
  if (Inst.isInvalid())
3024
0
    return TDK_InstantiationDepth;
3025
3026
844
  if (Trap.hasErrorOccurred())
3027
0
    return Sema::TDK_SubstitutionFailure;
3028
3029
844
  TemplateDeductionResult Result;
3030
844
  runWithSufficientStackSpace(Info.getLocation(), [&] {
3031
844
    Result = ::FinishTemplateArgumentDeduction(*this, Partial,
3032
844
                                               /*IsPartialOrdering=*/false,
3033
844
                                               TemplateArgs, Deduced, Info);
3034
844
  });
3035
844
  return Result;
3036
844
}
3037
3038
/// Determine whether the given type T is a simple-template-id type.
3039
1.06M
static bool isSimpleTemplateIdType(QualType T) {
3040
1.06M
  if (const TemplateSpecializationType *Spec
3041
1.06M
        = T->getAs<TemplateSpecializationType>())
3042
720k
    return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
3043
3044
  // C++17 [temp.local]p2:
3045
  //   the injected-class-name [...] is equivalent to the template-name followed
3046
  //   by the template-arguments of the class template specialization or partial
3047
  //   specialization enclosed in <>
3048
  // ... which means it's equivalent to a simple-template-id.
3049
  //
3050
  // This only arises during class template argument deduction for a copy
3051
  // deduction candidate, where it permits slicing.
3052
343k
  if (T->getAs<InjectedClassNameType>())
3053
264
    return true;
3054
3055
343k
  return false;
3056
343k
}
3057
3058
/// Substitute the explicitly-provided template arguments into the
3059
/// given function template according to C++ [temp.arg.explicit].
3060
///
3061
/// \param FunctionTemplate the function template into which the explicit
3062
/// template arguments will be substituted.
3063
///
3064
/// \param ExplicitTemplateArgs the explicitly-specified template
3065
/// arguments.
3066
///
3067
/// \param Deduced the deduced template arguments, which will be populated
3068
/// with the converted and checked explicit template arguments.
3069
///
3070
/// \param ParamTypes will be populated with the instantiated function
3071
/// parameters.
3072
///
3073
/// \param FunctionType if non-NULL, the result type of the function template
3074
/// will also be instantiated and the pointed-to value will be updated with
3075
/// the instantiated function type.
3076
///
3077
/// \param Info if substitution fails for any reason, this object will be
3078
/// populated with more information about the failure.
3079
///
3080
/// \returns TDK_Success if substitution was successful, or some failure
3081
/// condition.
3082
Sema::TemplateDeductionResult
3083
Sema::SubstituteExplicitTemplateArguments(
3084
                                      FunctionTemplateDecl *FunctionTemplate,
3085
                               TemplateArgumentListInfo &ExplicitTemplateArgs,
3086
                       SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3087
                                 SmallVectorImpl<QualType> &ParamTypes,
3088
                                          QualType *FunctionType,
3089
293k
                                          TemplateDeductionInfo &Info) {
3090
293k
  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3091
293k
  TemplateParameterList *TemplateParams
3092
293k
    = FunctionTemplate->getTemplateParameters();
3093
3094
293k
  if (ExplicitTemplateArgs.size() == 0) {
3095
    // No arguments to substitute; just copy over the parameter types and
3096
    // fill in the function type.
3097
32.8k
    for (auto P : Function->parameters())
3098
61.9k
      ParamTypes.push_back(P->getType());
3099
3100
32.8k
    if (FunctionType)
3101
32.7k
      *FunctionType = Function->getType();
3102
32.8k
    return TDK_Success;
3103
32.8k
  }
3104
3105
  // Unevaluated SFINAE context.
3106
260k
  EnterExpressionEvaluationContext Unevaluated(
3107
260k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
3108
260k
  SFINAETrap Trap(*this);
3109
3110
  // C++ [temp.arg.explicit]p3:
3111
  //   Template arguments that are present shall be specified in the
3112
  //   declaration order of their corresponding template-parameters. The
3113
  //   template argument list shall not specify more template-arguments than
3114
  //   there are corresponding template-parameters.
3115
260k
  SmallVector<TemplateArgument, 4> Builder;
3116
3117
  // Enter a new template instantiation context where we check the
3118
  // explicitly-specified template arguments against this function template,
3119
  // and then substitute them into the function parameter types.
3120
260k
  SmallVector<TemplateArgument, 4> DeducedArgs;
3121
260k
  InstantiatingTemplate Inst(
3122
260k
      *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3123
260k
      CodeSynthesisContext::ExplicitTemplateArgumentSubstitution, Info);
3124
260k
  if (Inst.isInvalid())
3125
11
    return TDK_InstantiationDepth;
3126
3127
260k
  if (CheckTemplateArgumentList(FunctionTemplate, SourceLocation(),
3128
260k
                                ExplicitTemplateArgs, true, Builder, false) ||
3129
260k
      
Trap.hasErrorOccurred()257k
) {
3130
2.64k
    unsigned Index = Builder.size();
3131
2.64k
    if (Index >= TemplateParams->size())
3132
982
      return TDK_SubstitutionFailure;
3133
1.66k
    Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3134
1.66k
    return TDK_InvalidExplicitArguments;
3135
2.64k
  }
3136
3137
  // Form the template argument list from the explicitly-specified
3138
  // template arguments.
3139
257k
  TemplateArgumentList *ExplicitArgumentList
3140
257k
    = TemplateArgumentList::CreateCopy(Context, Builder);
3141
257k
  Info.setExplicitArgs(ExplicitArgumentList);
3142
3143
  // Template argument deduction and the final substitution should be
3144
  // done in the context of the templated declaration.  Explicit
3145
  // argument substitution, on the other hand, needs to happen in the
3146
  // calling context.
3147
257k
  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3148
3149
  // If we deduced template arguments for a template parameter pack,
3150
  // note that the template argument pack is partially substituted and record
3151
  // the explicit template arguments. They'll be used as part of deduction
3152
  // for this template parameter pack.
3153
257k
  unsigned PartiallySubstitutedPackIndex = -1u;
3154
257k
  if (!Builder.empty()) {
3155
257k
    const TemplateArgument &Arg = Builder.back();
3156
257k
    if (Arg.getKind() == TemplateArgument::Pack) {
3157
24.5k
      auto *Param = TemplateParams->getParam(Builder.size() - 1);
3158
      // If this is a fully-saturated fixed-size pack, it should be
3159
      // fully-substituted, not partially-substituted.
3160
24.5k
      Optional<unsigned> Expansions = getExpandedPackSize(Param);
3161
24.5k
      if (!Expansions || 
Arg.pack_size() < *Expansions16
) {
3162
24.5k
        PartiallySubstitutedPackIndex = Builder.size() - 1;
3163
24.5k
        CurrentInstantiationScope->SetPartiallySubstitutedPack(
3164
24.5k
            Param, Arg.pack_begin(), Arg.pack_size());
3165
24.5k
      }
3166
24.5k
    }
3167
257k
  }
3168
3169
257k
  const FunctionProtoType *Proto
3170
257k
    = Function->getType()->getAs<FunctionProtoType>();
3171
257k
  assert(Proto && "Function template does not have a prototype?");
3172
3173
  // Isolate our substituted parameters from our caller.
3174
0
  LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
3175
3176
257k
  ExtParameterInfoBuilder ExtParamInfos;
3177
3178
  // Instantiate the types of each of the function parameters given the
3179
  // explicitly-specified template arguments. If the function has a trailing
3180
  // return type, substitute it after the arguments to ensure we substitute
3181
  // in lexical order.
3182
257k
  if (Proto->hasTrailingReturn()) {
3183
374
    if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3184
374
                       Proto->getExtParameterInfosOrNull(),
3185
374
                       MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3186
374
                       ParamTypes, /*params*/ nullptr, ExtParamInfos))
3187
1
      return TDK_SubstitutionFailure;
3188
374
  }
3189
3190
  // Instantiate the return type.
3191
257k
  QualType ResultType;
3192
257k
  {
3193
    // C++11 [expr.prim.general]p3:
3194
    //   If a declaration declares a member function or member function
3195
    //   template of a class X, the expression this is a prvalue of type
3196
    //   "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3197
    //   and the end of the function-definition, member-declarator, or
3198
    //   declarator.
3199
257k
    Qualifiers ThisTypeQuals;
3200
257k
    CXXRecordDecl *ThisContext = nullptr;
3201
257k
    if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3202
69.2k
      ThisContext = Method->getParent();
3203
69.2k
      ThisTypeQuals = Method->getMethodQualifiers();
3204
69.2k
    }
3205
3206
257k
    CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3207
257k
                               getLangOpts().CPlusPlus11);
3208
3209
257k
    ResultType =
3210
257k
        SubstType(Proto->getReturnType(),
3211
257k
                  MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3212
257k
                  Function->getTypeSpecStartLoc(), Function->getDeclName());
3213
257k
    if (ResultType.isNull() || 
Trap.hasErrorOccurred()251k
)
3214
6.96k
      return TDK_SubstitutionFailure;
3215
    // CUDA: Kernel function must have 'void' return type.
3216
251k
    if (getLangOpts().CUDA)
3217
200
      if (Function->hasAttr<CUDAGlobalAttr>() && 
!ResultType->isVoidType()51
) {
3218
1
        Diag(Function->getLocation(), diag::err_kern_type_not_void_return)
3219
1
            << Function->getType() << Function->getSourceRange();
3220
1
        return TDK_SubstitutionFailure;
3221
1
      }
3222
251k
  }
3223
3224
  // Instantiate the types of each of the function parameters given the
3225
  // explicitly-specified template arguments if we didn't do so earlier.
3226
251k
  if (!Proto->hasTrailingReturn() &&
3227
251k
      SubstParmTypes(Function->getLocation(), Function->parameters(),
3228
250k
                     Proto->getExtParameterInfosOrNull(),
3229
250k
                     MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3230
250k
                     ParamTypes, /*params*/ nullptr, ExtParamInfos))
3231
375
    return TDK_SubstitutionFailure;
3232
3233
250k
  if (FunctionType) {
3234
26.3k
    auto EPI = Proto->getExtProtoInfo();
3235
26.3k
    EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3236
3237
    // In C++1z onwards, exception specifications are part of the function type,
3238
    // so substitution into the type must also substitute into the exception
3239
    // specification.
3240
26.3k
    SmallVector<QualType, 4> ExceptionStorage;
3241
26.3k
    if (getLangOpts().CPlusPlus17 &&
3242
26.3k
        SubstExceptionSpec(
3243
1.65k
            Function->getLocation(), EPI.ExceptionSpec, ExceptionStorage,
3244
1.65k
            MultiLevelTemplateArgumentList(*ExplicitArgumentList)))
3245
2
      return TDK_SubstitutionFailure;
3246
3247
26.3k
    *FunctionType = BuildFunctionType(ResultType, ParamTypes,
3248
26.3k
                                      Function->getLocation(),
3249
26.3k
                                      Function->getDeclName(),
3250
26.3k
                                      EPI);
3251
26.3k
    if (FunctionType->isNull() || Trap.hasErrorOccurred())
3252
1
      return TDK_SubstitutionFailure;
3253
26.3k
  }
3254
3255
  // C++ [temp.arg.explicit]p2:
3256
  //   Trailing template arguments that can be deduced (14.8.2) may be
3257
  //   omitted from the list of explicit template-arguments. If all of the
3258
  //   template arguments can be deduced, they may all be omitted; in this
3259
  //   case, the empty template argument list <> itself may also be omitted.
3260
  //
3261
  // Take all of the explicitly-specified arguments and put them into
3262
  // the set of deduced template arguments. The partially-substituted
3263
  // parameter pack, however, will be set to NULL since the deduction
3264
  // mechanism handles the partially-substituted argument pack directly.
3265
250k
  Deduced.reserve(TemplateParams->size());
3266
537k
  for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; 
++I286k
) {
3267
286k
    const TemplateArgument &Arg = ExplicitArgumentList->get(I);
3268
286k
    if (I == PartiallySubstitutedPackIndex)
3269
18.0k
      Deduced.push_back(DeducedTemplateArgument());
3270
268k
    else
3271
268k
      Deduced.push_back(Arg);
3272
286k
  }
3273
3274
250k
  return TDK_Success;
3275
250k
}
3276
3277
/// Check whether the deduced argument type for a call to a function
3278
/// template matches the actual argument type per C++ [temp.deduct.call]p4.
3279
static Sema::TemplateDeductionResult
3280
CheckOriginalCallArgDeduction(Sema &S, TemplateDeductionInfo &Info,
3281
                              Sema::OriginalCallArg OriginalArg,
3282
256k
                              QualType DeducedA) {
3283
256k
  ASTContext &Context = S.Context;
3284
3285
256k
  auto Failed = [&]() -> Sema::TemplateDeductionResult {
3286
1.02k
    Info.FirstArg = TemplateArgument(DeducedA);
3287
1.02k
    Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3288
1.02k
    Info.CallArgIndex = OriginalArg.ArgIdx;
3289
1.02k
    return OriginalArg.DecomposedParam ? 
Sema::TDK_DeducedMismatchNested1
3290
1.02k
                                       : 
Sema::TDK_DeducedMismatch1.02k
;
3291
1.02k
  };
3292
3293
256k
  QualType A = OriginalArg.OriginalArgType;
3294
256k
  QualType OriginalParamType = OriginalArg.OriginalParamType;
3295
3296
  // Check for type equality (top-level cv-qualifiers are ignored).
3297
256k
  if (Context.hasSameUnqualifiedType(A, DeducedA))
3298
122k
    return Sema::TDK_Success;
3299
3300
  // Strip off references on the argument types; they aren't needed for
3301
  // the following checks.
3302
134k
  if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3303
126k
    DeducedA = DeducedARef->getPointeeType();
3304
134k
  if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3305
0
    A = ARef->getPointeeType();
3306
3307
  // C++ [temp.deduct.call]p4:
3308
  //   [...] However, there are three cases that allow a difference:
3309
  //     - If the original P is a reference type, the deduced A (i.e., the
3310
  //       type referred to by the reference) can be more cv-qualified than
3311
  //       the transformed A.
3312
134k
  if (const ReferenceType *OriginalParamRef
3313
134k
      = OriginalParamType->getAs<ReferenceType>()) {
3314
    // We don't want to keep the reference around any more.
3315
126k
    OriginalParamType = OriginalParamRef->getPointeeType();
3316
3317
    // FIXME: Resolve core issue (no number yet): if the original P is a
3318
    // reference type and the transformed A is function type "noexcept F",
3319
    // the deduced A can be F.
3320
126k
    QualType Tmp;
3321
126k
    if (A->isFunctionType() && 
S.IsFunctionConversion(A, DeducedA, Tmp)55
)
3322
1
      return Sema::TDK_Success;
3323
3324
126k
    Qualifiers AQuals = A.getQualifiers();
3325
126k
    Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3326
3327
    // Under Objective-C++ ARC, the deduced type may have implicitly
3328
    // been given strong or (when dealing with a const reference)
3329
    // unsafe_unretained lifetime. If so, update the original
3330
    // qualifiers to include this lifetime.
3331
126k
    if (S.getLangOpts().ObjCAutoRefCount &&
3332
126k
        
(86
(86
DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong86
&&
3333
86
          
AQuals.getObjCLifetime() == Qualifiers::OCL_None20
) ||
3334
86
         
(85
DeducedAQuals.hasConst()85
&&
3335
85
          
DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone16
))) {
3336
6
      AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3337
6
    }
3338
3339
126k
    if (AQuals == DeducedAQuals) {
3340
      // Qualifiers match; there's nothing to do.
3341
66.0k
    } else 
if (60.3k
!DeducedAQuals.compatiblyIncludes(AQuals)60.3k
) {
3342
986
      return Failed();
3343
59.3k
    } else {
3344
      // Qualifiers are compatible, so have the argument type adopt the
3345
      // deduced argument type's qualifiers as if we had performed the
3346
      // qualification conversion.
3347
59.3k
      A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3348
59.3k
    }
3349
126k
  }
3350
3351
  //    - The transformed A can be another pointer or pointer to member
3352
  //      type that can be converted to the deduced A via a function pointer
3353
  //      conversion and/or a qualification conversion.
3354
  //
3355
  // Also allow conversions which merely strip __attribute__((noreturn)) from
3356
  // function types (recursively).
3357
133k
  bool ObjCLifetimeConversion = false;
3358
133k
  QualType ResultTy;
3359
133k
  if ((A->isAnyPointerType() || 
A->isMemberPointerType()117k
) &&
3360
133k
      
(15.7k
S.IsQualificationConversion(A, DeducedA, false,
3361
15.7k
                                   ObjCLifetimeConversion) ||
3362
15.7k
       
S.IsFunctionConversion(A, DeducedA, ResultTy)15.4k
))
3363
267
    return Sema::TDK_Success;
3364
3365
  //    - If P is a class and P has the form simple-template-id, then the
3366
  //      transformed A can be a derived class of the deduced A. [...]
3367
  //     [...] Likewise, if P is a pointer to a class of the form
3368
  //      simple-template-id, the transformed A can be a pointer to a
3369
  //      derived class pointed to by the deduced A.
3370
132k
  if (const PointerType *OriginalParamPtr
3371
132k
      = OriginalParamType->getAs<PointerType>()) {
3372
8.06k
    if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3373
8.06k
      if (const PointerType *APtr = A->getAs<PointerType>()) {
3374
8.06k
        if (A->getPointeeType()->isRecordType()) {
3375
7.59k
          OriginalParamType = OriginalParamPtr->getPointeeType();
3376
7.59k
          DeducedA = DeducedAPtr->getPointeeType();
3377
7.59k
          A = APtr->getPointeeType();
3378
7.59k
        }
3379
8.06k
      }
3380
8.06k
    }
3381
8.06k
  }
3382
3383
132k
  if (Context.hasSameUnqualifiedType(A, DeducedA))
3384
125k
    return Sema::TDK_Success;
3385
3386
7.77k
  if (A->isRecordType() && 
isSimpleTemplateIdType(OriginalParamType)7.74k
&&
3387
7.77k
      
S.IsDerivedFrom(Info.getLocation(), A, DeducedA)7.74k
)
3388
7.74k
    return Sema::TDK_Success;
3389
3390
36
  return Failed();
3391
7.77k
}
3392
3393
/// Find the pack index for a particular parameter index in an instantiation of
3394
/// a function template with specific arguments.
3395
///
3396
/// \return The pack index for whichever pack produced this parameter, or -1
3397
///         if this was not produced by a parameter. Intended to be used as the
3398
///         ArgumentPackSubstitutionIndex for further substitutions.
3399
// FIXME: We should track this in OriginalCallArgs so we don't need to
3400
// reconstruct it here.
3401
static unsigned getPackIndexForParam(Sema &S,
3402
                                     FunctionTemplateDecl *FunctionTemplate,
3403
                                     const MultiLevelTemplateArgumentList &Args,
3404
105
                                     unsigned ParamIdx) {
3405
105
  unsigned Idx = 0;
3406
105
  for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3407
105
    if (PD->isParameterPack()) {
3408
15
      unsigned NumExpansions =
3409
15
          S.getNumArgumentsInExpansion(PD->getType(), Args).getValueOr(1);
3410
15
      if (Idx + NumExpansions > ParamIdx)
3411
15
        return ParamIdx - Idx;
3412
0
      Idx += NumExpansions;
3413
90
    } else {
3414
90
      if (Idx == ParamIdx)
3415
90
        return -1; // Not a pack expansion
3416
0
      ++Idx;
3417
0
    }
3418
105
  }
3419
3420
0
  llvm_unreachable("parameter index would not be produced from template");
3421
0
}
3422
3423
/// Finish template argument deduction for a function template,
3424
/// checking the deduced template arguments for completeness and forming
3425
/// the function template specialization.
3426
///
3427
/// \param OriginalCallArgs If non-NULL, the original call arguments against
3428
/// which the deduced argument types should be compared.
3429
Sema::TemplateDeductionResult Sema::FinishTemplateArgumentDeduction(
3430
    FunctionTemplateDecl *FunctionTemplate,
3431
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3432
    unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3433
    TemplateDeductionInfo &Info,
3434
    SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3435
539k
    bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3436
  // Unevaluated SFINAE context.
3437
539k
  EnterExpressionEvaluationContext Unevaluated(
3438
539k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
3439
539k
  SFINAETrap Trap(*this);
3440
3441
  // Enter a new template instantiation context while we instantiate the
3442
  // actual function declaration.
3443
539k
  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3444
539k
  InstantiatingTemplate Inst(
3445
539k
      *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3446
539k
      CodeSynthesisContext::DeducedTemplateArgumentSubstitution, Info);
3447
539k
  if (Inst.isInvalid())
3448
2.23k
    return TDK_InstantiationDepth;
3449
3450
537k
  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3451
3452
  // C++ [temp.deduct.type]p2:
3453
  //   [...] or if any template argument remains neither deduced nor
3454
  //   explicitly specified, template argument deduction fails.
3455
537k
  SmallVector<TemplateArgument, 4> Builder;
3456
537k
  if (auto Result = ConvertDeducedTemplateArguments(
3457
537k
          *this, FunctionTemplate, /*IsDeduced*/true, Deduced, Info, Builder,
3458
537k
          CurrentInstantiationScope, NumExplicitlySpecified,
3459
537k
          PartialOverloading))
3460
47.2k
    return Result;
3461
3462
  // C++ [temp.deduct.call]p10: [DR1391]
3463
  //   If deduction succeeds for all parameters that contain
3464
  //   template-parameters that participate in template argument deduction,
3465
  //   and all template arguments are explicitly specified, deduced, or
3466
  //   obtained from default template arguments, remaining parameters are then
3467
  //   compared with the corresponding arguments. For each remaining parameter
3468
  //   P with a type that was non-dependent before substitution of any
3469
  //   explicitly-specified template arguments, if the corresponding argument
3470
  //   A cannot be implicitly converted to P, deduction fails.
3471
490k
  if (CheckNonDependent())
3472
30.9k
    return TDK_NonDependentConversionFailure;
3473
3474
  // Form the template argument list from the deduced template arguments.
3475
459k
  TemplateArgumentList *DeducedArgumentList
3476
459k
    = TemplateArgumentList::CreateCopy(Context, Builder);
3477
459k
  Info.reset(DeducedArgumentList);
3478
3479
  // Substitute the deduced template arguments into the function template
3480
  // declaration to produce the function template specialization.
3481
459k
  DeclContext *Owner = FunctionTemplate->getDeclContext();
3482
459k
  if (FunctionTemplate->getFriendObjectKind())
3483
55
    Owner = FunctionTemplate->getLexicalDeclContext();
3484
459k
  MultiLevelTemplateArgumentList SubstArgs(*DeducedArgumentList);
3485
459k
  Specialization = cast_or_null<FunctionDecl>(
3486
459k
      SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, SubstArgs));
3487
459k
  if (!Specialization || 
Specialization->isInvalidDecl()409k
)
3488
49.6k
    return TDK_SubstitutionFailure;
3489
3490
409k
  assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3491
409k
         FunctionTemplate->getCanonicalDecl());
3492
3493
  // If the template argument list is owned by the function template
3494
  // specialization, release it.
3495
409k
  if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
3496
409k
      
!Trap.hasErrorOccurred()0
)
3497
0
    Info.take();
3498
3499
  // There may have been an error that did not prevent us from constructing a
3500
  // declaration. Mark the declaration invalid and return with a substitution
3501
  // failure.
3502
409k
  if (Trap.hasErrorOccurred()) {
3503
115
    Specialization->setInvalidDecl(true);
3504
115
    return TDK_SubstitutionFailure;
3505
115
  }
3506
3507
  // C++2a [temp.deduct]p5
3508
  //   [...] When all template arguments have been deduced [...] all uses of
3509
  //   template parameters [...] are replaced with the corresponding deduced
3510
  //   or default argument values.
3511
  //   [...] If the function template has associated constraints
3512
  //   ([temp.constr.decl]), those constraints are checked for satisfaction
3513
  //   ([temp.constr.constr]). If the constraints are not satisfied, type
3514
  //   deduction fails.
3515
409k
  if (!PartialOverloading ||
3516
409k
      
(Builder.size() == FunctionTemplate->getTemplateParameters()->size())87
) {
3517
409k
    if (CheckInstantiatedFunctionTemplateConstraints(Info.getLocation(),
3518
409k
            Specialization, Builder, Info.AssociatedConstraintsSatisfaction))
3519
1
      return TDK_MiscellaneousDeductionFailure;
3520
3521
409k
    if (!Info.AssociatedConstraintsSatisfaction.IsSatisfied) {
3522
99
      Info.reset(TemplateArgumentList::CreateCopy(Context, Builder));
3523
99
      return TDK_ConstraintsNotSatisfied;
3524
99
    }
3525
409k
  }
3526
3527
409k
  if (OriginalCallArgs) {
3528
    // C++ [temp.deduct.call]p4:
3529
    //   In general, the deduction process attempts to find template argument
3530
    //   values that will make the deduced A identical to A (after the type A
3531
    //   is transformed as described above). [...]
3532
381k
    llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3533
614k
    for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; 
++I233k
) {
3534
234k
      OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3535
3536
234k
      auto ParamIdx = OriginalArg.ArgIdx;
3537
234k
      if (ParamIdx >= Specialization->getNumParams())
3538
        // FIXME: This presumably means a pack ended up smaller than we
3539
        // expected while deducing. Should this not result in deduction
3540
        // failure? Can it even happen?
3541
0
        continue;
3542
3543
234k
      QualType DeducedA;
3544
234k
      if (!OriginalArg.DecomposedParam) {
3545
        // P is one of the function parameters, just look up its substituted
3546
        // type.
3547
233k
        DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
3548
233k
      } else {
3549
        // P is a decomposed element of a parameter corresponding to a
3550
        // braced-init-list argument. Substitute back into P to find the
3551
        // deduced A.
3552
383
        QualType &CacheEntry =
3553
383
            DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3554
383
        if (CacheEntry.isNull()) {
3555
105
          ArgumentPackSubstitutionIndexRAII PackIndex(
3556
105
              *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs,
3557
105
                                          ParamIdx));
3558
105
          CacheEntry =
3559
105
              SubstType(OriginalArg.OriginalParamType, SubstArgs,
3560
105
                        Specialization->getTypeSpecStartLoc(),
3561
105
                        Specialization->getDeclName());
3562
105
        }
3563
383
        DeducedA = CacheEntry;
3564
383
      }
3565
3566
234k
      if (auto TDK =
3567
234k
              CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA))
3568
1.01k
        return TDK;
3569
234k
    }
3570
381k
  }
3571
3572
  // If we suppressed any diagnostics while performing template argument
3573
  // deduction, and if we haven't already instantiated this declaration,
3574
  // keep track of these diagnostics. They'll be emitted if this specialization
3575
  // is actually used.
3576
408k
  if (Info.diag_begin() != Info.diag_end()) {
3577
9.40k
    SuppressedDiagnosticsMap::iterator
3578
9.40k
      Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3579
9.40k
    if (Pos == SuppressedDiagnostics.end())
3580
5.14k
        SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3581
5.14k
          .append(Info.diag_begin(), Info.diag_end());
3582
9.40k
  }
3583
3584
408k
  return TDK_Success;
3585
409k
}
3586
3587
/// Gets the type of a function for template-argument-deducton
3588
/// purposes when it's considered as part of an overload set.
3589
static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
3590
474
                                  FunctionDecl *Fn) {
3591
  // We may need to deduce the return type of the function now.
3592
474
  if (S.getLangOpts().CPlusPlus14 && 
Fn->getReturnType()->isUndeducedType()301
&&
3593
474
      
S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false)36
)
3594
0
    return {};
3595
3596
474
  if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3597
111
    if (Method->isInstance()) {
3598
      // An instance method that's referenced in a form that doesn't
3599
      // look like a member pointer is just invalid.
3600
45
      if (!R.HasFormOfMemberPointer)
3601
18
        return {};
3602
3603
27
      return S.Context.getMemberPointerType(Fn->getType(),
3604
27
               S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3605
45
    }
3606
3607
429
  if (!R.IsAddressOfOperand) 
return Fn->getType()306
;
3608
123
  return S.Context.getPointerType(Fn->getType());
3609
429
}
3610
3611
/// Apply the deduction rules for overload sets.
3612
///
3613
/// \return the null type if this argument should be treated as an
3614
/// undeduced context
3615
static QualType
3616
ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
3617
                            Expr *Arg, QualType ParamType,
3618
1.11k
                            bool ParamWasReference) {
3619
3620
1.11k
  OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3621
3622
1.11k
  OverloadExpr *Ovl = R.Expression;
3623
3624
  // C++0x [temp.deduct.call]p4
3625
1.11k
  unsigned TDF = 0;
3626
1.11k
  if (ParamWasReference)
3627
404
    TDF |= TDF_ParamWithReferenceType;
3628
1.11k
  if (R.IsAddressOfOperand)
3629
196
    TDF |= TDF_IgnoreQualifiers;
3630
3631
  // C++0x [temp.deduct.call]p6:
3632
  //   When P is a function type, pointer to function type, or pointer
3633
  //   to member function type:
3634
3635
1.11k
  if (!ParamType->isFunctionType() &&
3636
1.11k
      
!ParamType->isFunctionPointerType()1.10k
&&
3637
1.11k
      
!ParamType->isMemberFunctionPointerType()829
) {
3638
809
    if (Ovl->hasExplicitTemplateArgs()) {
3639
      // But we can still look for an explicit specialization.
3640
87
      if (FunctionDecl *ExplicitSpec
3641
87
            = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3642
83
        return GetTypeOfFunction(S, R, ExplicitSpec);
3643
87
    }
3644
3645
726
    DeclAccessPair DAP;
3646
726
    if (FunctionDecl *Viable =
3647
726
            S.resolveAddressOfSingleOverloadCandidate(Arg, DAP))
3648
6
      return GetTypeOfFunction(S, R, Viable);
3649
3650
720
    return {};
3651
726
  }
3652
3653
  // Gather the explicit template arguments, if any.
3654
302
  TemplateArgumentListInfo ExplicitTemplateArgs;
3655
302
  if (Ovl->hasExplicitTemplateArgs())
3656
93
    Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3657
302
  QualType Match;
3658
302
  for (UnresolvedSetIterator I = Ovl->decls_begin(),
3659
623
         E = Ovl->decls_end(); I != E; 
++I321
) {
3660
465
    NamedDecl *D = (*I)->getUnderlyingDecl();
3661
3662
465
    if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3663
      //   - If the argument is an overload set containing one or more
3664
      //     function templates, the parameter is treated as a
3665
      //     non-deduced context.
3666
173
      if (!Ovl->hasExplicitTemplateArgs())
3667
70
        return {};
3668
3669
      // Otherwise, see if we can resolve a function type
3670
103
      FunctionDecl *Specialization = nullptr;
3671
103
      TemplateDeductionInfo Info(Ovl->getNameLoc());
3672
103
      if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3673
103
                                    Specialization, Info))
3674
10
        continue;
3675
3676
93
      D = Specialization;
3677
93
    }
3678
3679
385
    FunctionDecl *Fn = cast<FunctionDecl>(D);
3680
385
    QualType ArgType = GetTypeOfFunction(S, R, Fn);
3681
385
    if (ArgType.isNull()) 
continue18
;
3682
3683
    // Function-to-pointer conversion.
3684
367
    if (!ParamWasReference && 
ParamType->isPointerType()359
&&
3685
367
        
ArgType->isFunctionType()328
)
3686
249
      ArgType = S.Context.getPointerType(ArgType);
3687
3688
    //   - If the argument is an overload set (not containing function
3689
    //     templates), trial argument deduction is attempted using each
3690
    //     of the members of the set. If deduction succeeds for only one
3691
    //     of the overload set members, that member is used as the
3692
    //     argument value for the deduction. If deduction succeeds for
3693
    //     more than one member of the overload set the parameter is
3694
    //     treated as a non-deduced context.
3695
3696
    // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3697
    //   Type deduction is done independently for each P/A pair, and
3698
    //   the deduced template argument values are then combined.
3699
    // So we do not reject deductions which were made elsewhere.
3700
367
    SmallVector<DeducedTemplateArgument, 8>
3701
367
      Deduced(TemplateParams->size());
3702
367
    TemplateDeductionInfo Info(Ovl->getNameLoc());
3703
367
    Sema::TemplateDeductionResult Result
3704
367
      = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3705
367
                                           ArgType, Info, Deduced, TDF);
3706
367
    if (Result) 
continue89
;
3707
278
    if (!Match.isNull())
3708
74
      return {};
3709
204
    Match = ArgType;
3710
204
  }
3711
3712
158
  return Match;
3713
302
}
3714
3715
/// Perform the adjustments to the parameter and argument types
3716
/// described in C++ [temp.deduct.call].
3717
///
3718
/// \returns true if the caller should not attempt to perform any template
3719
/// argument deduction based on this P/A pair because the argument is an
3720
/// overloaded function set that could not be resolved.
3721
static bool AdjustFunctionParmAndArgTypesForDeduction(
3722
    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3723
1.00M
    QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF) {
3724
  // C++0x [temp.deduct.call]p3:
3725
  //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
3726
  //   are ignored for type deduction.
3727
1.00M
  if (ParamType.hasQualifiers())
3728
4.13k
    ParamType = ParamType.getUnqualifiedType();
3729
3730
  //   [...] If P is a reference type, the type referred to by P is
3731
  //   used for type deduction.
3732
1.00M
  const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3733
1.00M
  if (ParamRefType)
3734
779k
    ParamType = ParamRefType->getPointeeType();
3735
3736
  // Overload sets usually make this parameter an undeduced context,
3737
  // but there are sometimes special circumstances.  Typically
3738
  // involving a template-id-expr.
3739
1.00M
  if (ArgType == S.Context.OverloadTy) {
3740
1.11k
    ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3741
1.11k
                                          Arg, ParamType,
3742
1.11k
                                          ParamRefType != nullptr);
3743
1.11k
    if (ArgType.isNull())
3744
898
      return true;
3745
1.11k
  }
3746
3747
1.00M
  if (ParamRefType) {
3748
    // If the argument has incomplete array type, try to complete its type.
3749
778k
    if (ArgType->isIncompleteArrayType())
3750
12
      ArgType = S.getCompletedType(Arg);
3751
3752
    // C++1z [temp.deduct.call]p3:
3753
    //   If P is a forwarding reference and the argument is an lvalue, the type
3754
    //   "lvalue reference to A" is used in place of A for type deduction.
3755
778k
    if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
3756
778k
        
Arg->isLValue()62.4k
) {
3757
29.2k
      if (S.getLangOpts().OpenCL && 
!ArgType.hasAddressSpace()2
)
3758
1
        ArgType = S.Context.getAddrSpaceQualType(
3759
1
            ArgType, S.Context.getDefaultOpenCLPointeeAddrSpace());
3760
29.2k
      ArgType = S.Context.getLValueReferenceType(ArgType);
3761
29.2k
    }
3762
778k
  } else {
3763
    // C++ [temp.deduct.call]p2:
3764
    //   If P is not a reference type:
3765
    //   - If A is an array type, the pointer type produced by the
3766
    //     array-to-pointer standard conversion (4.2) is used in place of
3767
    //     A for type deduction; otherwise,
3768
229k
    if (ArgType->isArrayType())
3769
3.77k
      ArgType = S.Context.getArrayDecayedType(ArgType);
3770
    //   - If A is a function type, the pointer type produced by the
3771
    //     function-to-pointer standard conversion (4.3) is used in place
3772
    //     of A for type deduction; otherwise,
3773
225k
    else if (ArgType->isFunctionType())
3774
325
      ArgType = S.Context.getPointerType(ArgType);
3775
225k
    else {
3776
      // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3777
      //   type are ignored for type deduction.
3778
225k
      ArgType = ArgType.getUnqualifiedType();
3779
225k
    }
3780
229k
  }
3781
3782
  // C++0x [temp.deduct.call]p4:
3783
  //   In general, the deduction process attempts to find template argument
3784
  //   values that will make the deduced A identical to A (after the type A
3785
  //   is transformed as described above). [...]
3786
1.00M
  TDF = TDF_SkipNonDependent;
3787
3788
  //     - If the original P is a reference type, the deduced A (i.e., the
3789
  //       type referred to by the reference) can be more cv-qualified than
3790
  //       the transformed A.
3791
1.00M
  if (ParamRefType)
3792
778k
    TDF |= TDF_ParamWithReferenceType;
3793
  //     - The transformed A can be another pointer or pointer to member
3794
  //       type that can be converted to the deduced A via a qualification
3795
  //       conversion (4.4).
3796
1.00M
  if (ArgType->isPointerType() || 
ArgType->isMemberPointerType()887k
||
3797
1.00M
      
ArgType->isObjCObjectPointerType()886k
)
3798
121k
    TDF |= TDF_IgnoreQualifiers;
3799
  //     - If P is a class and P has the form simple-template-id, then the
3800
  //       transformed A can be a derived class of the deduced A. Likewise,
3801
  //       if P is a pointer to a class of the form simple-template-id, the
3802
  //       transformed A can be a pointer to a derived class pointed to by
3803
  //       the deduced A.
3804
1.00M
  if (isSimpleTemplateIdType(ParamType) ||
3805
1.00M
      
(303k
isa<PointerType>(ParamType)303k
&&
3806
303k
       isSimpleTemplateIdType(
3807
48.1k
           ParamType->castAs<PointerType>()->getPointeeType())))
3808
712k
    TDF |= TDF_DerivedClass;
3809
3810
1.00M
  return false;
3811
1.00M
}
3812
3813
static bool
3814
hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3815
                               QualType T);
3816
3817
static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3818
    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3819
    QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3820
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3821
    SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3822
    bool DecomposedParam, unsigned ArgIdx, unsigned TDF);
3823
3824
/// Attempt template argument deduction from an initializer list
3825
///        deemed to be an argument in a function call.
3826
static Sema::TemplateDeductionResult DeduceFromInitializerList(
3827
    Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
3828
    InitListExpr *ILE, TemplateDeductionInfo &Info,
3829
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3830
    SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
3831
825
    unsigned TDF) {
3832
  // C++ [temp.deduct.call]p1: (CWG 1591)
3833
  //   If removing references and cv-qualifiers from P gives
3834
  //   std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
3835
  //   a non-empty initializer list, then deduction is performed instead for
3836
  //   each element of the initializer list, taking P0 as a function template
3837
  //   parameter type and the initializer element as its argument
3838
  //
3839
  // We've already removed references and cv-qualifiers here.
3840
825
  if (!ILE->getNumInits())
3841
33
    return Sema::TDK_Success;
3842
3843
792
  QualType ElTy;
3844
792
  auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
3845
792
  if (ArrTy)
3846
400
    ElTy = ArrTy->getElementType();
3847
392
  else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
3848
    //   Otherwise, an initializer list argument causes the parameter to be
3849
    //   considered a non-deduced context
3850
307
    return Sema::TDK_Success;
3851
307
  }
3852
3853
  // Resolving a core issue: a braced-init-list containing any designators is
3854
  // a non-deduced context.
3855
485
  for (Expr *E : ILE->inits())
3856
1.09k
    if (isa<DesignatedInitExpr>(E))
3857
4
      return Sema::TDK_Success;
3858
3859
  // Deduction only needs to be done for dependent types.
3860
481
  if (ElTy->isDependentType()) {
3861
960
    for (Expr *E : ILE->inits()) {
3862
960
      if (auto Result = DeduceTemplateArgumentsFromCallArgument(
3863
960
              S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
3864
960
              ArgIdx, TDF))
3865
72
        return Result;
3866
960
    }
3867
455
  }
3868
3869
  //   in the P0[N] case, if N is a non-type template parameter, N is deduced
3870
  //   from the length of the initializer list.
3871
409
  if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
3872
    // Determine the array bound is something we can deduce.
3873
315
    if (const NonTypeTemplateParmDecl *NTTP =
3874
315
            getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
3875
      // We can perform template argument deduction for the given non-type
3876
      // template parameter.
3877
      // C++ [temp.deduct.type]p13:
3878
      //   The type of N in the type T[N] is std::size_t.
3879
315
      QualType T = S.Context.getSizeType();
3880
315
      llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
3881
315
      if (auto Result = DeduceNonTypeTemplateArgument(
3882
315
              S, TemplateParams, NTTP, llvm::APSInt(Size), T,
3883
315
              /*ArrayBound=*/true, Info, Deduced))
3884
11
        return Result;
3885
315
    }
3886
315
  }
3887
3888
398
  return Sema::TDK_Success;
3889
409
}
3890
3891
/// Perform template argument deduction per [temp.deduct.call] for a
3892
///        single parameter / argument pair.
3893
static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3894
    Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3895
    QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3896
    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3897
    SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3898
1.00M
    bool DecomposedParam, unsigned ArgIdx, unsigned TDF) {
3899
1.00M
  QualType ArgType = Arg->getType();
3900
1.00M
  QualType OrigParamType = ParamType;
3901
3902
  //   If P is a reference type [...]
3903
  //   If P is a cv-qualified type [...]
3904
1.00M
  if (AdjustFunctionParmAndArgTypesForDeduction(
3905
1.00M
          S, TemplateParams, FirstInnerIndex, ParamType, ArgType, Arg, TDF))
3906
898
    return Sema::TDK_Success;
3907
3908
  //   If [...] the argument is a non-empty initializer list [...]
3909
1.00M
  if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg))
3910
825
    return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
3911
825
                                     Deduced, OriginalCallArgs, ArgIdx, TDF);
3912
3913
  //   [...] the deduction process attempts to find template argument values
3914
  //   that will make the deduced A identical to A
3915
  //
3916
  // Keep track of the argument type and corresponding parameter index,
3917
  // so we can check for compatibility between the deduced A and A.
3918
1.00M
  OriginalCallArgs.push_back(
3919
1.00M
      Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
3920
1.00M
  return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3921
1.00M
                                            ArgType, Info, Deduced, TDF);
3922
1.00M
}
3923
3924
/// Perform template argument deduction from a function call
3925
/// (C++ [temp.deduct.call]).
3926
///
3927
/// \param FunctionTemplate the function template for which we are performing
3928
/// template argument deduction.
3929
///
3930
/// \param ExplicitTemplateArgs the explicit template arguments provided
3931
/// for this call.
3932
///
3933
/// \param Args the function call arguments
3934
///
3935
/// \param Specialization if template argument deduction was successful,
3936
/// this will be set to the function template specialization produced by
3937
/// template argument deduction.
3938
///
3939
/// \param Info the argument will be updated to provide additional information
3940
/// about template argument deduction.
3941
///
3942
/// \param CheckNonDependent A callback to invoke to check conversions for
3943
/// non-dependent parameters, between deduction and substitution, per DR1391.
3944
/// If this returns true, substitution will be skipped and we return
3945
/// TDK_NonDependentConversionFailure. The callback is passed the parameter
3946
/// types (after substituting explicit template arguments).
3947
///
3948
/// \returns the result of template argument deduction.
3949
Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3950
    FunctionTemplateDecl *FunctionTemplate,
3951
    TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
3952
    FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3953
    bool PartialOverloading,
3954
1.33M
    llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
3955
1.33M
  if (FunctionTemplate->isInvalidDecl())
3956
12
    return TDK_Invalid;
3957
3958
1.33M
  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3959
1.33M
  unsigned NumParams = Function->getNumParams();
3960
3961
1.33M
  unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
3962
3963
  // C++ [temp.deduct.call]p1:
3964
  //   Template argument deduction is done by comparing each function template
3965
  //   parameter type (call it P) with the type of the corresponding argument
3966
  //   of the call (call it A) as described below.
3967
1.33M
  if (Args.size() < Function->getMinRequiredArguments() && 
!PartialOverloading151k
)
3968
151k
    return TDK_TooFewArguments;
3969
1.18M
  else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3970
73.4k
    const auto *Proto = Function->getType()->castAs<FunctionProtoType>();
3971
73.4k
    if (Proto->isTemplateVariadic())
3972
2.85k
      /* Do nothing */;
3973
70.6k
    else if (!Proto->isVariadic())
3974
32.7k
      return TDK_TooManyArguments;
3975
73.4k
  }
3976
3977
  // The types of the parameters from which we will perform template argument
3978
  // deduction.
3979
1.15M
  LocalInstantiationScope InstScope(*this);
3980
1.15M
  TemplateParameterList *TemplateParams
3981
1.15M
    = FunctionTemplate->getTemplateParameters();
3982
1.15M
  SmallVector<DeducedTemplateArgument, 4> Deduced;
3983
1.15M
  SmallVector<QualType, 8> ParamTypes;
3984
1.15M
  unsigned NumExplicitlySpecified = 0;
3985
1.15M
  if (ExplicitTemplateArgs) {
3986
232k
    TemplateDeductionResult Result;
3987
232k
    runWithSufficientStackSpace(Info.getLocation(), [&] {
3988
232k
      Result = SubstituteExplicitTemplateArguments(
3989
232k
          FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes, nullptr,
3990
232k
          Info);
3991
232k
    });
3992
232k
    if (Result)
3993
7.94k
      return Result;
3994
3995
224k
    NumExplicitlySpecified = Deduced.size();
3996
923k
  } else {
3997
    // Just fill in the parameter types from the function declaration.
3998
2.63M
    for (unsigned I = 0; I != NumParams; 
++I1.71M
)
3999
1.71M
      ParamTypes.push_back(Function->getParamDecl(I)->getType());
4000
923k
  }
4001
4002
1.14M
  SmallVector<OriginalCallArg, 8> OriginalCallArgs;
4003
4004
  // Deduce an argument of type ParamType from an expression with index ArgIdx.
4005
1.27M
  auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) {
4006
    // C++ [demp.deduct.call]p1: (DR1391)
4007
    //   Template argument deduction is done by comparing each function template
4008
    //   parameter that contains template-parameters that participate in
4009
    //   template argument deduction ...
4010
1.27M
    if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
4011
287k
      return Sema::TDK_Success;
4012
4013
    //   ... with the type of the corresponding argument
4014
985k
    return DeduceTemplateArgumentsFromCallArgument(
4015
985k
        *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
4016
985k
        OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0);
4017
1.27M
  };
4018
4019
  // Deduce template arguments from the function parameters.
4020
1.14M
  Deduced.resize(TemplateParams->size());
4021
1.14M
  SmallVector<QualType, 8> ParamTypesForArgChecking;
4022
1.14M
  for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
4023
1.77M
       ParamIdx != NumParamTypes; 
++ParamIdx627k
) {
4024
1.33M
    QualType ParamType = ParamTypes[ParamIdx];
4025
4026
1.33M
    const PackExpansionType *ParamExpansion =
4027
1.33M
        dyn_cast<PackExpansionType>(ParamType);
4028
1.33M
    if (!ParamExpansion) {
4029
      // Simple case: matching a function parameter to a function argument.
4030
1.32M
      if (ArgIdx >= Args.size())
4031
65.8k
        break;
4032
4033
1.25M
      ParamTypesForArgChecking.push_back(ParamType);
4034
1.25M
      if (auto Result = DeduceCallArgument(ParamType, ArgIdx++))
4035
642k
        return Result;
4036
4037
613k
      continue;
4038
1.25M
    }
4039
4040
14.1k
    QualType ParamPattern = ParamExpansion->getPattern();
4041
14.1k
    PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
4042
14.1k
                                 ParamPattern);
4043
4044
    // C++0x [temp.deduct.call]p1:
4045
    //   For a function parameter pack that occurs at the end of the
4046
    //   parameter-declaration-list, the type A of each remaining argument of
4047
    //   the call is compared with the type P of the declarator-id of the
4048
    //   function parameter pack. Each comparison deduces template arguments
4049
    //   for subsequent positions in the template parameter packs expanded by
4050
    //   the function parameter pack. When a function parameter pack appears
4051
    //   in a non-deduced context [not at the end of the list], the type of
4052
    //   that parameter pack is never deduced.
4053
    //
4054
    // FIXME: The above rule allows the size of the parameter pack to change
4055
    // after we skip it (in the non-deduced case). That makes no sense, so
4056
    // we instead notionally deduce the pack against N arguments, where N is
4057
    // the length of the explicitly-specified pack if it's expanded by the
4058
    // parameter pack and 0 otherwise, and we treat each deduction as a
4059
    // non-deduced context.
4060
14.1k
    if (ParamIdx + 1 == NumParamTypes || 
PackScope.hasFixedArity()164
) {
4061
30.7k
      for (; ArgIdx < Args.size() && 
PackScope.hasNextElement()16.7k
;
4062
16.7k
           
PackScope.nextPackElement(), ++ArgIdx16.7k
) {
4063
16.7k
        ParamTypesForArgChecking.push_back(ParamPattern);
4064
16.7k
        if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx))
4065
10
          return Result;
4066
16.7k
      }
4067
14.0k
    } else {
4068
      // If the parameter type contains an explicitly-specified pack that we
4069
      // could not expand, skip the number of parameters notionally created
4070
      // by the expansion.
4071
162
      Optional<unsigned> NumExpansions = ParamExpansion->getNumExpansions();
4072
162
      if (NumExpansions && 
!PackScope.isPartiallyExpanded()12
) {
4073
36
        for (unsigned I = 0; I != *NumExpansions && 
ArgIdx < Args.size()24
;
4074
24
             ++I, ++ArgIdx) {
4075
24
          ParamTypesForArgChecking.push_back(ParamPattern);
4076
          // FIXME: Should we add OriginalCallArgs for these? What if the
4077
          // corresponding argument is a list?
4078
24
          PackScope.nextPackElement();
4079
24
        }
4080
12
      }
4081
162
    }
4082
4083
    // Build argument packs for each of the parameter packs expanded by this
4084
    // pack expansion.
4085
14.1k
    if (auto Result = PackScope.finish())
4086
40
      return Result;
4087
14.1k
  }
4088
4089
  // Capture the context in which the function call is made. This is the context
4090
  // that is needed when the accessibility of template arguments is checked.
4091
505k
  DeclContext *CallingCtx = CurContext;
4092
4093
505k
  TemplateDeductionResult Result;
4094
505k
  runWithSufficientStackSpace(Info.getLocation(), [&] {
4095
505k
    Result = FinishTemplateArgumentDeduction(
4096
505k
        FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
4097
505k
        &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
4098
458k
          ContextRAII SavedContext(*this, CallingCtx);
4099
458k
          return CheckNonDependent(ParamTypesForArgChecking);
4100
458k
        });
4101
505k
  });
4102
505k
  return Result;
4103
1.14M
}
4104
4105
QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
4106
                                   QualType FunctionType,
4107
327k
                                   bool AdjustExceptionSpec) {
4108
327k
  if (ArgFunctionType.isNull())
4109
196
    return ArgFunctionType;
4110
4111
326k
  const auto *FunctionTypeP = FunctionType->castAs<FunctionProtoType>();
4112
326k
  const auto *ArgFunctionTypeP = ArgFunctionType->castAs<FunctionProtoType>();
4113
326k
  FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
4114
326k
  bool Rebuild = false;
4115
4116
326k
  CallingConv CC = FunctionTypeP->getCallConv();
4117
326k
  if (EPI.ExtInfo.getCC() != CC) {
4118
182
    EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
4119
182
    Rebuild = true;
4120
182
  }
4121
4122
326k
  bool NoReturn = FunctionTypeP->getNoReturnAttr();
4123
326k
  if (EPI.ExtInfo.getNoReturn() != NoReturn) {
4124
1
    EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
4125
1
    Rebuild = true;
4126
1
  }
4127
4128
326k
  if (AdjustExceptionSpec && 
(193k
FunctionTypeP->hasExceptionSpec()193k
||
4129
193k
                              
ArgFunctionTypeP->hasExceptionSpec()157k
)) {
4130
42.3k
    EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
4131
42.3k
    Rebuild = true;
4132
42.3k
  }
4133
4134
326k
  if (!Rebuild)
4135
284k
    return ArgFunctionType;
4136
4137
42.4k
  return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
4138
42.4k
                                 ArgFunctionTypeP->getParamTypes(), EPI);
4139
326k
}
4140
4141
/// Deduce template arguments when taking the address of a function
4142
/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
4143
/// a template.
4144
///
4145
/// \param FunctionTemplate the function template for which we are performing
4146
/// template argument deduction.
4147
///
4148
/// \param ExplicitTemplateArgs the explicitly-specified template
4149
/// arguments.
4150
///
4151
/// \param ArgFunctionType the function type that will be used as the
4152
/// "argument" type (A) when performing template argument deduction from the
4153
/// function template's function type. This type may be NULL, if there is no
4154
/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4155
///
4156
/// \param Specialization if template argument deduction was successful,
4157
/// this will be set to the function template specialization produced by
4158
/// template argument deduction.
4159
///
4160
/// \param Info the argument will be updated to provide additional information
4161
/// about template argument deduction.
4162
///
4163
/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4164
/// the address of a function template per [temp.deduct.funcaddr] and
4165
/// [over.over]. If \c false, we are looking up a function template
4166
/// specialization based on its signature, per [temp.deduct.decl].
4167
///
4168
/// \returns the result of template argument deduction.
4169
Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4170
    FunctionTemplateDecl *FunctionTemplate,
4171
    TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4172
    FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4173
137k
    bool IsAddressOfFunction) {
4174
137k
  if (FunctionTemplate->isInvalidDecl())
4175
0
    return TDK_Invalid;
4176
4177
137k
  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4178
137k
  TemplateParameterList *TemplateParams
4179
137k
    = FunctionTemplate->getTemplateParameters();
4180
137k
  QualType FunctionType = Function->getType();
4181
4182
  // Substitute any explicit template arguments.
4183
137k
  LocalInstantiationScope InstScope(*this);
4184
137k
  SmallVector<DeducedTemplateArgument, 4> Deduced;
4185
137k
  unsigned NumExplicitlySpecified = 0;
4186
137k
  SmallVector<QualType, 4> ParamTypes;
4187
137k
  if (ExplicitTemplateArgs) {
4188
61.2k
    TemplateDeductionResult Result;
4189
61.2k
    runWithSufficientStackSpace(Info.getLocation(), [&] {
4190
61.2k
      Result = SubstituteExplicitTemplateArguments(
4191
61.2k
          FunctionTemplate, *ExplicitTemplateArgs, Deduced, ParamTypes,
4192
61.2k
          &FunctionType, Info);
4193
61.2k
    });
4194
61.2k
    if (Result)
4195
2.06k
      return Result;
4196
4197
59.1k
    NumExplicitlySpecified = Deduced.size();
4198
59.1k
  }
4199
4200
  // When taking the address of a function, we require convertibility of
4201
  // the resulting function type. Otherwise, we allow arbitrary mismatches
4202
  // of calling convention and noreturn.
4203
135k
  if (!IsAddressOfFunction)
4204
130k
    ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4205
130k
                                          /*AdjustExceptionSpec*/false);
4206
4207
  // Unevaluated SFINAE context.
4208
135k
  EnterExpressionEvaluationContext Unevaluated(
4209
135k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
4210
135k
  SFINAETrap Trap(*this);
4211
4212
135k
  Deduced.resize(TemplateParams->size());
4213
4214
  // If the function has a deduced return type, substitute it for a dependent
4215
  // type so that we treat it as a non-deduced context in what follows. If we
4216
  // are looking up by signature, the signature type should also have a deduced
4217
  // return type, which we instead expect to exactly match.
4218
135k
  bool HasDeducedReturnType = false;
4219
135k
  if (getLangOpts().CPlusPlus14 && 
IsAddressOfFunction12.8k
&&
4220
135k
      
Function->getReturnType()->getContainedAutoType()2.43k
) {
4221
722
    FunctionType = SubstAutoTypeDependent(FunctionType);
4222
722
    HasDeducedReturnType = true;
4223
722
  }
4224
4225
135k
  if (!ArgFunctionType.isNull() && 
!FunctionType.isNull()135k
) {
4226
135k
    unsigned TDF =
4227
135k
        TDF_TopLevelParameterTypeList | TDF_AllowCompatibleFunctionType;
4228
    // Deduce template arguments from the function type.
4229
135k
    if (TemplateDeductionResult Result
4230
135k
          = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4231
135k
                                               FunctionType, ArgFunctionType,
4232
135k
                                               Info, Deduced, TDF))
4233
105k
      return Result;
4234
135k
  }
4235
4236
30.7k
  TemplateDeductionResult Result;
4237
30.7k
  runWithSufficientStackSpace(Info.getLocation(), [&] {
4238
30.7k
    Result = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4239
30.7k
                                             NumExplicitlySpecified,
4240
30.7k
                                             Specialization, Info);
4241
30.7k
  });
4242
30.7k
  if (Result)
4243
5.92k
    return Result;
4244
4245
  // If the function has a deduced return type, deduce it now, so we can check
4246
  // that the deduced function type matches the requested type.
4247
24.7k
  if (HasDeducedReturnType &&
4248
24.7k
      
Specialization->getReturnType()->isUndeducedType()348
&&
4249
24.7k
      
DeduceReturnType(Specialization, Info.getLocation(), false)60
)
4250
12
    return TDK_MiscellaneousDeductionFailure;
4251
4252
  // If the function has a dependent exception specification, resolve it now,
4253
  // so we can check that the exception specification matches.
4254
24.7k
  auto *SpecializationFPT =
4255
24.7k
      Specialization->getType()->castAs<FunctionProtoType>();
4256
24.7k
  if (getLangOpts().CPlusPlus17 &&
4257
24.7k
      
isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType())2.32k
&&
4258
24.7k
      
!ResolveExceptionSpec(Info.getLocation(), SpecializationFPT)8
)
4259
0
    return TDK_MiscellaneousDeductionFailure;
4260
4261
  // Adjust the exception specification of the argument to match the
4262
  // substituted and resolved type we just formed. (Calling convention and
4263
  // noreturn can't be dependent, so we don't actually need this for them
4264
  // right now.)
4265
24.7k
  QualType SpecializationType = Specialization->getType();
4266
24.7k
  if (!IsAddressOfFunction)
4267
21.6k
    ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4268
21.6k
                                          /*AdjustExceptionSpec*/true);
4269
4270
  // If the requested function type does not match the actual type of the
4271
  // specialization with respect to arguments of compatible pointer to function
4272
  // types, template argument deduction fails.
4273
24.7k
  if (!ArgFunctionType.isNull()) {
4274
24.1k
    if (IsAddressOfFunction &&
4275
24.1k
        !isSameOrCompatibleFunctionType(
4276
2.52k
            Context.getCanonicalType(SpecializationType),
4277
2.52k
            Context.getCanonicalType(ArgFunctionType)))
4278
23
      return TDK_MiscellaneousDeductionFailure;
4279
4280
24.0k
    if (!IsAddressOfFunction &&
4281
24.0k
        
!Context.hasSameType(SpecializationType, ArgFunctionType)21.5k
)
4282
36
      return TDK_MiscellaneousDeductionFailure;
4283
24.0k
  }
4284
4285
24.7k
  return TDK_Success;
4286
24.7k
}
4287
4288
/// Deduce template arguments for a templated conversion
4289
/// function (C++ [temp.deduct.conv]) and, if successful, produce a
4290
/// conversion function template specialization.
4291
Sema::TemplateDeductionResult
4292
Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
4293
                              QualType ToType,
4294
                              CXXConversionDecl *&Specialization,
4295
4.31k
                              TemplateDeductionInfo &Info) {
4296
4.31k
  if (ConversionTemplate->isInvalidDecl())
4297
0
    return TDK_Invalid;
4298
4299
4.31k
  CXXConversionDecl *ConversionGeneric
4300
4.31k
    = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4301
4302
4.31k
  QualType FromType = ConversionGeneric->getConversionType();
4303
4304
  // Canonicalize the types for deduction.
4305
4.31k
  QualType P = Context.getCanonicalType(FromType);
4306
4.31k
  QualType A = Context.getCanonicalType(ToType);
4307
4308
  // C++0x [temp.deduct.conv]p2:
4309
  //   If P is a reference type, the type referred to by P is used for
4310
  //   type deduction.
4311
4.31k
  if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4312
89
    P = PRef->getPointeeType();
4313
4314
  // C++0x [temp.deduct.conv]p4:
4315
  //   [...] If A is a reference type, the type referred to by A is used
4316
  //   for type deduction.
4317
4.31k
  if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4318
190
    A = ARef->getPointeeType();
4319
    // We work around a defect in the standard here: cv-qualifiers are also
4320
    // removed from P and A in this case, unless P was a reference type. This
4321
    // seems to mostly match what other compilers are doing.
4322
190
    if (!FromType->getAs<ReferenceType>()) {
4323
123
      A = A.getUnqualifiedType();
4324
123
      P = P.getUnqualifiedType();
4325
123
    }
4326
4327
  // C++ [temp.deduct.conv]p3:
4328
  //
4329
  //   If A is not a reference type:
4330
4.12k
  } else {
4331
4.12k
    assert(!A->isReferenceType() && "Reference types were handled above");
4332
4333
    //   - If P is an array type, the pointer type produced by the
4334
    //     array-to-pointer standard conversion (4.2) is used in place
4335
    //     of P for type deduction; otherwise,
4336
4.12k
    if (P->isArrayType())
4337
1
      P = Context.getArrayDecayedType(P);
4338
    //   - If P is a function type, the pointer type produced by the
4339
    //     function-to-pointer standard conversion (4.3) is used in
4340
    //     place of P for type deduction; otherwise,
4341
4.12k
    else if (P->isFunctionType())
4342
0
      P = Context.getPointerType(P);
4343
    //   - If P is a cv-qualified type, the top level cv-qualifiers of
4344
    //     P's type are ignored for type deduction.
4345
4.12k
    else
4346
4.12k
      P = P.getUnqualifiedType();
4347
4348
    // C++0x [temp.deduct.conv]p4:
4349
    //   If A is a cv-qualified type, the top level cv-qualifiers of A's
4350
    //   type are ignored for type deduction. If A is a reference type, the type
4351
    //   referred to by A is used for type deduction.
4352
4.12k
    A = A.getUnqualifiedType();
4353
4.12k
  }
4354
4355
  // Unevaluated SFINAE context.
4356
0
  EnterExpressionEvaluationContext Unevaluated(
4357
4.31k
      *this, Sema::ExpressionEvaluationContext::Unevaluated);
4358
4.31k
  SFINAETrap Trap(*this);
4359
4360
  // C++ [temp.deduct.conv]p1:
4361
  //   Template argument deduction is done by comparing the return
4362
  //   type of the template conversion function (call it P) with the
4363
  //   type that is required as the result of the conversion (call it
4364
  //   A) as described in 14.8.2.4.
4365
4.31k
  TemplateParameterList *TemplateParams
4366
4.31k
    = ConversionTemplate->getTemplateParameters();
4367
4.31k
  SmallVector<DeducedTemplateArgument, 4> Deduced;
4368
4.31k
  Deduced.resize(TemplateParams->size());
4369
4370
  // C++0x [temp.deduct.conv]p4:
4371
  //   In general, the deduction process attempts to find template
4372
  //   argument values that will make the deduced A identical to
4373
  //   A. However, there are two cases that allow a difference:
4374
4.31k
  unsigned TDF = 0;
4375
  //     - If the original A is a reference type, A can be more
4376
  //       cv-qualified than the deduced A (i.e., the type referred to
4377
  //       by the reference)
4378
4.31k
  if (ToType->isReferenceType())
4379
190
    TDF |= TDF_ArgWithReferenceType;
4380
  //     - The deduced A can be another pointer or pointer to member
4381
  //       type that can be converted to A via a qualification
4382
  //       conversion.
4383
  //
4384
  // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4385
  // both P and A are pointers or member pointers. In this case, we
4386
  // just ignore cv-qualifiers completely).
4387
4.31k
  if ((P->isPointerType() && 
A->isPointerType()1.10k
) ||
4388
4.31k
      
(3.31k
P->isMemberPointerType()3.31k
&&
A->isMemberPointerType()20
))
4389
1.01k
    TDF |= TDF_IgnoreQualifiers;
4390
4.31k
  if (TemplateDeductionResult Result
4391
4.31k
        = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4392
4.31k
                                             P, A, Info, Deduced, TDF))
4393
446
    return Result;
4394
4395
  // Create an Instantiation Scope for finalizing the operator.
4396
3.86k
  LocalInstantiationScope InstScope(*this);
4397
  // Finish template argument deduction.
4398
3.86k
  FunctionDecl *ConversionSpecialized = nullptr;
4399
3.86k
  TemplateDeductionResult Result;
4400
3.86k
  runWithSufficientStackSpace(Info.getLocation(), [&] {
4401
3.86k
    Result = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4402
3.86k
                                             ConversionSpecialized, Info);
4403
3.86k
  });
4404
3.86k
  Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4405
3.86k
  return Result;
4406
4.31k
}
4407
4408
/// Deduce template arguments for a function template when there is
4409
/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4410
///
4411
/// \param FunctionTemplate the function template for which we are performing
4412
/// template argument deduction.
4413
///
4414
/// \param ExplicitTemplateArgs the explicitly-specified template
4415
/// arguments.
4416
///
4417
/// \param Specialization if template argument deduction was successful,
4418
/// this will be set to the function template specialization produced by
4419
/// template argument deduction.
4420
///
4421
/// \param Info the argument will be updated to provide additional information
4422
/// about template argument deduction.
4423
///
4424
/// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4425
/// the address of a function template in a context where we do not have a
4426
/// target type, per [over.over]. If \c false, we are looking up a function
4427
/// template specialization based on its signature, which only happens when
4428
/// deducing a function parameter type from an argument that is a template-id
4429
/// naming a function template specialization.
4430
///
4431
/// \returns the result of template argument deduction.
4432
Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4433
    FunctionTemplateDecl *FunctionTemplate,
4434
    TemplateArgumentListInfo *ExplicitTemplateArgs,
4435
    FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4436
756
    bool IsAddressOfFunction) {
4437
756
  return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4438
756
                                 QualType(), Specialization, Info,
4439
756
                                 IsAddressOfFunction);
4440
756
}
4441
4442
namespace {
4443
  struct DependentAuto { bool IsPack; };
4444
4445
  /// Substitute the 'auto' specifier or deduced template specialization type
4446
  /// specifier within a type for a given replacement type.
4447
  class SubstituteDeducedTypeTransform :
4448
      public TreeTransform<SubstituteDeducedTypeTransform> {
4449
    QualType Replacement;
4450
    bool ReplacementIsPack;
4451
    bool UseTypeSugar;
4452
4453
  public:
4454
    SubstituteDeducedTypeTransform(Sema &SemaRef, DependentAuto DA)
4455
        : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4456
9.77k
          ReplacementIsPack(DA.IsPack), UseTypeSugar(true) {}
4457
4458
    SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4459
                                   bool UseTypeSugar = true)