Coverage Report

Created: 2021-08-24 07:12

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