Coverage Report

Created: 2019-07-24 05:18

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