Coverage Report

Created: 2020-09-22 08:39

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