Coverage Report

Created: 2021-01-23 06:44

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