1 //===- SemaTemplateDeduction.cpp - Template Argument Deduction ------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements C++ template argument deduction.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "clang/Sema/TemplateDeduction.h"
15 #include "TreeTransform.h"
16 #include "TypeLocBuilder.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/ASTLambda.h"
19 #include "clang/AST/Decl.h"
20 #include "clang/AST/DeclAccessPair.h"
21 #include "clang/AST/DeclBase.h"
22 #include "clang/AST/DeclCXX.h"
23 #include "clang/AST/DeclTemplate.h"
24 #include "clang/AST/DeclarationName.h"
25 #include "clang/AST/Expr.h"
26 #include "clang/AST/ExprCXX.h"
27 #include "clang/AST/NestedNameSpecifier.h"
28 #include "clang/AST/TemplateBase.h"
29 #include "clang/AST/TemplateName.h"
30 #include "clang/AST/Type.h"
31 #include "clang/AST/TypeLoc.h"
32 #include "clang/AST/UnresolvedSet.h"
33 #include "clang/Basic/AddressSpaces.h"
34 #include "clang/Basic/ExceptionSpecificationType.h"
35 #include "clang/Basic/LLVM.h"
36 #include "clang/Basic/LangOptions.h"
37 #include "clang/Basic/PartialDiagnostic.h"
38 #include "clang/Basic/SourceLocation.h"
39 #include "clang/Basic/Specifiers.h"
40 #include "clang/Sema/Ownership.h"
41 #include "clang/Sema/Sema.h"
42 #include "clang/Sema/Template.h"
43 #include "llvm/ADT/APInt.h"
44 #include "llvm/ADT/APSInt.h"
45 #include "llvm/ADT/ArrayRef.h"
46 #include "llvm/ADT/DenseMap.h"
47 #include "llvm/ADT/FoldingSet.h"
48 #include "llvm/ADT/Optional.h"
49 #include "llvm/ADT/SmallBitVector.h"
50 #include "llvm/ADT/SmallPtrSet.h"
51 #include "llvm/ADT/SmallVector.h"
52 #include "llvm/Support/Casting.h"
53 #include "llvm/Support/Compiler.h"
54 #include "llvm/Support/ErrorHandling.h"
55 #include <algorithm>
56 #include <cassert>
57 #include <tuple>
58 #include <utility>
59
60 namespace clang {
61
62 /// Various flags that control template argument deduction.
63 ///
64 /// These flags can be bitwise-OR'd together.
65 enum TemplateDeductionFlags {
66 /// No template argument deduction flags, which indicates the
67 /// strictest results for template argument deduction (as used for, e.g.,
68 /// matching class template partial specializations).
69 TDF_None = 0,
70
71 /// Within template argument deduction from a function call, we are
72 /// matching with a parameter type for which the original parameter was
73 /// a reference.
74 TDF_ParamWithReferenceType = 0x1,
75
76 /// Within template argument deduction from a function call, we
77 /// are matching in a case where we ignore cv-qualifiers.
78 TDF_IgnoreQualifiers = 0x02,
79
80 /// Within template argument deduction from a function call,
81 /// we are matching in a case where we can perform template argument
82 /// deduction from a template-id of a derived class of the argument type.
83 TDF_DerivedClass = 0x04,
84
85 /// Allow non-dependent types to differ, e.g., when performing
86 /// template argument deduction from a function call where conversions
87 /// may apply.
88 TDF_SkipNonDependent = 0x08,
89
90 /// Whether we are performing template argument deduction for
91 /// parameters and arguments in a top-level template argument
92 TDF_TopLevelParameterTypeList = 0x10,
93
94 /// Within template argument deduction from overload resolution per
95 /// C++ [over.over] allow matching function types that are compatible in
96 /// terms of noreturn and default calling convention adjustments, or
97 /// similarly matching a declared template specialization against a
98 /// possible template, per C++ [temp.deduct.decl]. In either case, permit
99 /// deduction where the parameter is a function type that can be converted
100 /// to the argument type.
101 TDF_AllowCompatibleFunctionType = 0x20,
102
103 /// Within template argument deduction for a conversion function, we are
104 /// matching with an argument type for which the original argument was
105 /// a reference.
106 TDF_ArgWithReferenceType = 0x40,
107 };
108 }
109
110 using namespace clang;
111 using namespace sema;
112
113 /// Compare two APSInts, extending and switching the sign as
114 /// necessary to compare their values regardless of underlying type.
hasSameExtendedValue(llvm::APSInt X,llvm::APSInt Y)115 static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
116 if (Y.getBitWidth() > X.getBitWidth())
117 X = X.extend(Y.getBitWidth());
118 else if (Y.getBitWidth() < X.getBitWidth())
119 Y = Y.extend(X.getBitWidth());
120
121 // If there is a signedness mismatch, correct it.
122 if (X.isSigned() != Y.isSigned()) {
123 // If the signed value is negative, then the values cannot be the same.
124 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
125 return false;
126
127 Y.setIsSigned(true);
128 X.setIsSigned(true);
129 }
130
131 return X == Y;
132 }
133
134 static Sema::TemplateDeductionResult
135 DeduceTemplateArguments(Sema &S,
136 TemplateParameterList *TemplateParams,
137 const TemplateArgument &Param,
138 TemplateArgument Arg,
139 TemplateDeductionInfo &Info,
140 SmallVectorImpl<DeducedTemplateArgument> &Deduced);
141
142 static Sema::TemplateDeductionResult
143 DeduceTemplateArgumentsByTypeMatch(Sema &S,
144 TemplateParameterList *TemplateParams,
145 QualType Param,
146 QualType Arg,
147 TemplateDeductionInfo &Info,
148 SmallVectorImpl<DeducedTemplateArgument> &
149 Deduced,
150 unsigned TDF,
151 bool PartialOrdering = false,
152 bool DeducedFromArrayBound = false);
153
154 static Sema::TemplateDeductionResult
155 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
156 ArrayRef<TemplateArgument> Params,
157 ArrayRef<TemplateArgument> Args,
158 TemplateDeductionInfo &Info,
159 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
160 bool NumberOfArgumentsMustMatch);
161
162 static void MarkUsedTemplateParameters(ASTContext &Ctx,
163 const TemplateArgument &TemplateArg,
164 bool OnlyDeduced, unsigned Depth,
165 llvm::SmallBitVector &Used);
166
167 static void MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
168 bool OnlyDeduced, unsigned Level,
169 llvm::SmallBitVector &Deduced);
170
171 /// If the given expression is of a form that permits the deduction
172 /// of a non-type template parameter, return the declaration of that
173 /// non-type template parameter.
174 static NonTypeTemplateParmDecl *
getDeducedParameterFromExpr(TemplateDeductionInfo & Info,Expr * E)175 getDeducedParameterFromExpr(TemplateDeductionInfo &Info, Expr *E) {
176 // If we are within an alias template, the expression may have undergone
177 // any number of parameter substitutions already.
178 while (true) {
179 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
180 E = IC->getSubExpr();
181 else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(E))
182 E = CE->getSubExpr();
183 else if (SubstNonTypeTemplateParmExpr *Subst =
184 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
185 E = Subst->getReplacement();
186 else
187 break;
188 }
189
190 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
191 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()))
192 if (NTTP->getDepth() == Info.getDeducedDepth())
193 return NTTP;
194
195 return nullptr;
196 }
197
198 /// Determine whether two declaration pointers refer to the same
199 /// declaration.
isSameDeclaration(Decl * X,Decl * Y)200 static bool isSameDeclaration(Decl *X, Decl *Y) {
201 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
202 X = NX->getUnderlyingDecl();
203 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
204 Y = NY->getUnderlyingDecl();
205
206 return X->getCanonicalDecl() == Y->getCanonicalDecl();
207 }
208
209 /// Verify that the given, deduced template arguments are compatible.
210 ///
211 /// \returns The deduced template argument, or a NULL template argument if
212 /// the deduced template arguments were incompatible.
213 static DeducedTemplateArgument
checkDeducedTemplateArguments(ASTContext & Context,const DeducedTemplateArgument & X,const DeducedTemplateArgument & Y)214 checkDeducedTemplateArguments(ASTContext &Context,
215 const DeducedTemplateArgument &X,
216 const DeducedTemplateArgument &Y) {
217 // We have no deduction for one or both of the arguments; they're compatible.
218 if (X.isNull())
219 return Y;
220 if (Y.isNull())
221 return X;
222
223 // If we have two non-type template argument values deduced for the same
224 // parameter, they must both match the type of the parameter, and thus must
225 // match each other's type. As we're only keeping one of them, we must check
226 // for that now. The exception is that if either was deduced from an array
227 // bound, the type is permitted to differ.
228 if (!X.wasDeducedFromArrayBound() && !Y.wasDeducedFromArrayBound()) {
229 QualType XType = X.getNonTypeTemplateArgumentType();
230 if (!XType.isNull()) {
231 QualType YType = Y.getNonTypeTemplateArgumentType();
232 if (YType.isNull() || !Context.hasSameType(XType, YType))
233 return DeducedTemplateArgument();
234 }
235 }
236
237 switch (X.getKind()) {
238 case TemplateArgument::Null:
239 llvm_unreachable("Non-deduced template arguments handled above");
240
241 case TemplateArgument::Type:
242 // If two template type arguments have the same type, they're compatible.
243 if (Y.getKind() == TemplateArgument::Type &&
244 Context.hasSameType(X.getAsType(), Y.getAsType()))
245 return X;
246
247 // If one of the two arguments was deduced from an array bound, the other
248 // supersedes it.
249 if (X.wasDeducedFromArrayBound() != Y.wasDeducedFromArrayBound())
250 return X.wasDeducedFromArrayBound() ? Y : X;
251
252 // The arguments are not compatible.
253 return DeducedTemplateArgument();
254
255 case TemplateArgument::Integral:
256 // If we deduced a constant in one case and either a dependent expression or
257 // declaration in another case, keep the integral constant.
258 // If both are integral constants with the same value, keep that value.
259 if (Y.getKind() == TemplateArgument::Expression ||
260 Y.getKind() == TemplateArgument::Declaration ||
261 (Y.getKind() == TemplateArgument::Integral &&
262 hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
263 return X.wasDeducedFromArrayBound() ? Y : X;
264
265 // All other combinations are incompatible.
266 return DeducedTemplateArgument();
267
268 case TemplateArgument::Template:
269 if (Y.getKind() == TemplateArgument::Template &&
270 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
271 return X;
272
273 // All other combinations are incompatible.
274 return DeducedTemplateArgument();
275
276 case TemplateArgument::TemplateExpansion:
277 if (Y.getKind() == TemplateArgument::TemplateExpansion &&
278 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
279 Y.getAsTemplateOrTemplatePattern()))
280 return X;
281
282 // All other combinations are incompatible.
283 return DeducedTemplateArgument();
284
285 case TemplateArgument::Expression: {
286 if (Y.getKind() != TemplateArgument::Expression)
287 return checkDeducedTemplateArguments(Context, Y, X);
288
289 // Compare the expressions for equality
290 llvm::FoldingSetNodeID ID1, ID2;
291 X.getAsExpr()->Profile(ID1, Context, true);
292 Y.getAsExpr()->Profile(ID2, Context, true);
293 if (ID1 == ID2)
294 return X.wasDeducedFromArrayBound() ? Y : X;
295
296 // Differing dependent expressions are incompatible.
297 return DeducedTemplateArgument();
298 }
299
300 case TemplateArgument::Declaration:
301 assert(!X.wasDeducedFromArrayBound());
302
303 // If we deduced a declaration and a dependent expression, keep the
304 // declaration.
305 if (Y.getKind() == TemplateArgument::Expression)
306 return X;
307
308 // If we deduced a declaration and an integral constant, keep the
309 // integral constant and whichever type did not come from an array
310 // bound.
311 if (Y.getKind() == TemplateArgument::Integral) {
312 if (Y.wasDeducedFromArrayBound())
313 return TemplateArgument(Context, Y.getAsIntegral(),
314 X.getParamTypeForDecl());
315 return Y;
316 }
317
318 // If we deduced two declarations, make sure that they refer to the
319 // same declaration.
320 if (Y.getKind() == TemplateArgument::Declaration &&
321 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
322 return X;
323
324 // All other combinations are incompatible.
325 return DeducedTemplateArgument();
326
327 case TemplateArgument::NullPtr:
328 // If we deduced a null pointer and a dependent expression, keep the
329 // null pointer.
330 if (Y.getKind() == TemplateArgument::Expression)
331 return X;
332
333 // If we deduced a null pointer and an integral constant, keep the
334 // integral constant.
335 if (Y.getKind() == TemplateArgument::Integral)
336 return Y;
337
338 // If we deduced two null pointers, they are the same.
339 if (Y.getKind() == TemplateArgument::NullPtr)
340 return X;
341
342 // All other combinations are incompatible.
343 return DeducedTemplateArgument();
344
345 case TemplateArgument::Pack: {
346 if (Y.getKind() != TemplateArgument::Pack ||
347 X.pack_size() != Y.pack_size())
348 return DeducedTemplateArgument();
349
350 llvm::SmallVector<TemplateArgument, 8> NewPack;
351 for (TemplateArgument::pack_iterator XA = X.pack_begin(),
352 XAEnd = X.pack_end(),
353 YA = Y.pack_begin();
354 XA != XAEnd; ++XA, ++YA) {
355 TemplateArgument Merged = checkDeducedTemplateArguments(
356 Context, DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
357 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()));
358 if (Merged.isNull())
359 return DeducedTemplateArgument();
360 NewPack.push_back(Merged);
361 }
362
363 return DeducedTemplateArgument(
364 TemplateArgument::CreatePackCopy(Context, NewPack),
365 X.wasDeducedFromArrayBound() && Y.wasDeducedFromArrayBound());
366 }
367 }
368
369 llvm_unreachable("Invalid TemplateArgument Kind!");
370 }
371
372 /// Deduce the value of the given non-type template parameter
373 /// as the given deduced template argument. All non-type template parameter
374 /// deduction is funneled through here.
DeduceNonTypeTemplateArgument(Sema & S,TemplateParameterList * TemplateParams,NonTypeTemplateParmDecl * NTTP,const DeducedTemplateArgument & NewDeduced,QualType ValueType,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)375 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
376 Sema &S, TemplateParameterList *TemplateParams,
377 NonTypeTemplateParmDecl *NTTP, const DeducedTemplateArgument &NewDeduced,
378 QualType ValueType, TemplateDeductionInfo &Info,
379 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
380 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
381 "deducing non-type template argument with wrong depth");
382
383 DeducedTemplateArgument Result = checkDeducedTemplateArguments(
384 S.Context, Deduced[NTTP->getIndex()], NewDeduced);
385 if (Result.isNull()) {
386 Info.Param = NTTP;
387 Info.FirstArg = Deduced[NTTP->getIndex()];
388 Info.SecondArg = NewDeduced;
389 return Sema::TDK_Inconsistent;
390 }
391
392 Deduced[NTTP->getIndex()] = Result;
393 if (!S.getLangOpts().CPlusPlus17)
394 return Sema::TDK_Success;
395
396 if (NTTP->isExpandedParameterPack())
397 // FIXME: We may still need to deduce parts of the type here! But we
398 // don't have any way to find which slice of the type to use, and the
399 // type stored on the NTTP itself is nonsense. Perhaps the type of an
400 // expanded NTTP should be a pack expansion type?
401 return Sema::TDK_Success;
402
403 // Get the type of the parameter for deduction. If it's a (dependent) array
404 // or function type, we will not have decayed it yet, so do that now.
405 QualType ParamType = S.Context.getAdjustedParameterType(NTTP->getType());
406 if (auto *Expansion = dyn_cast<PackExpansionType>(ParamType))
407 ParamType = Expansion->getPattern();
408
409 // FIXME: It's not clear how deduction of a parameter of reference
410 // type from an argument (of non-reference type) should be performed.
411 // For now, we just remove reference types from both sides and let
412 // the final check for matching types sort out the mess.
413 return DeduceTemplateArgumentsByTypeMatch(
414 S, TemplateParams, ParamType.getNonReferenceType(),
415 ValueType.getNonReferenceType(), Info, Deduced, TDF_SkipNonDependent,
416 /*PartialOrdering=*/false,
417 /*ArrayBound=*/NewDeduced.wasDeducedFromArrayBound());
418 }
419
420 /// Deduce the value of the given non-type template parameter
421 /// from the given integral constant.
DeduceNonTypeTemplateArgument(Sema & S,TemplateParameterList * TemplateParams,NonTypeTemplateParmDecl * NTTP,const llvm::APSInt & Value,QualType ValueType,bool DeducedFromArrayBound,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)422 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
423 Sema &S, TemplateParameterList *TemplateParams,
424 NonTypeTemplateParmDecl *NTTP, const llvm::APSInt &Value,
425 QualType ValueType, bool DeducedFromArrayBound, TemplateDeductionInfo &Info,
426 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
427 return DeduceNonTypeTemplateArgument(
428 S, TemplateParams, NTTP,
429 DeducedTemplateArgument(S.Context, Value, ValueType,
430 DeducedFromArrayBound),
431 ValueType, Info, Deduced);
432 }
433
434 /// Deduce the value of the given non-type template parameter
435 /// from the given null pointer template argument type.
DeduceNullPtrTemplateArgument(Sema & S,TemplateParameterList * TemplateParams,NonTypeTemplateParmDecl * NTTP,QualType NullPtrType,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)436 static Sema::TemplateDeductionResult DeduceNullPtrTemplateArgument(
437 Sema &S, TemplateParameterList *TemplateParams,
438 NonTypeTemplateParmDecl *NTTP, QualType NullPtrType,
439 TemplateDeductionInfo &Info,
440 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
441 Expr *Value =
442 S.ImpCastExprToType(new (S.Context) CXXNullPtrLiteralExpr(
443 S.Context.NullPtrTy, NTTP->getLocation()),
444 NullPtrType, CK_NullToPointer)
445 .get();
446 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
447 DeducedTemplateArgument(Value),
448 Value->getType(), Info, Deduced);
449 }
450
451 /// Deduce the value of the given non-type template parameter
452 /// from the given type- or value-dependent expression.
453 ///
454 /// \returns true if deduction succeeded, false otherwise.
DeduceNonTypeTemplateArgument(Sema & S,TemplateParameterList * TemplateParams,NonTypeTemplateParmDecl * NTTP,Expr * Value,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)455 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
456 Sema &S, TemplateParameterList *TemplateParams,
457 NonTypeTemplateParmDecl *NTTP, Expr *Value, TemplateDeductionInfo &Info,
458 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
459 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
460 DeducedTemplateArgument(Value),
461 Value->getType(), Info, Deduced);
462 }
463
464 /// Deduce the value of the given non-type template parameter
465 /// from the given declaration.
466 ///
467 /// \returns true if deduction succeeded, false otherwise.
DeduceNonTypeTemplateArgument(Sema & S,TemplateParameterList * TemplateParams,NonTypeTemplateParmDecl * NTTP,ValueDecl * D,QualType T,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)468 static Sema::TemplateDeductionResult DeduceNonTypeTemplateArgument(
469 Sema &S, TemplateParameterList *TemplateParams,
470 NonTypeTemplateParmDecl *NTTP, ValueDecl *D, QualType T,
471 TemplateDeductionInfo &Info,
472 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
473 D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
474 TemplateArgument New(D, T);
475 return DeduceNonTypeTemplateArgument(
476 S, TemplateParams, NTTP, DeducedTemplateArgument(New), T, Info, Deduced);
477 }
478
479 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,TemplateName Param,TemplateName Arg,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)480 DeduceTemplateArguments(Sema &S,
481 TemplateParameterList *TemplateParams,
482 TemplateName Param,
483 TemplateName Arg,
484 TemplateDeductionInfo &Info,
485 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
486 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
487 if (!ParamDecl) {
488 // The parameter type is dependent and is not a template template parameter,
489 // so there is nothing that we can deduce.
490 return Sema::TDK_Success;
491 }
492
493 if (TemplateTemplateParmDecl *TempParam
494 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
495 // If we're not deducing at this depth, there's nothing to deduce.
496 if (TempParam->getDepth() != Info.getDeducedDepth())
497 return Sema::TDK_Success;
498
499 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
500 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
501 Deduced[TempParam->getIndex()],
502 NewDeduced);
503 if (Result.isNull()) {
504 Info.Param = TempParam;
505 Info.FirstArg = Deduced[TempParam->getIndex()];
506 Info.SecondArg = NewDeduced;
507 return Sema::TDK_Inconsistent;
508 }
509
510 Deduced[TempParam->getIndex()] = Result;
511 return Sema::TDK_Success;
512 }
513
514 // Verify that the two template names are equivalent.
515 if (S.Context.hasSameTemplateName(Param, Arg))
516 return Sema::TDK_Success;
517
518 // Mismatch of non-dependent template parameter to argument.
519 Info.FirstArg = TemplateArgument(Param);
520 Info.SecondArg = TemplateArgument(Arg);
521 return Sema::TDK_NonDeducedMismatch;
522 }
523
524 /// Deduce the template arguments by comparing the template parameter
525 /// type (which is a template-id) with the template argument type.
526 ///
527 /// \param S the Sema
528 ///
529 /// \param TemplateParams the template parameters that we are deducing
530 ///
531 /// \param Param the parameter type
532 ///
533 /// \param Arg the argument type
534 ///
535 /// \param Info information about the template argument deduction itself
536 ///
537 /// \param Deduced the deduced template arguments
538 ///
539 /// \returns the result of template argument deduction so far. Note that a
540 /// "success" result means that template argument deduction has not yet failed,
541 /// but it may still fail, later, for other reasons.
542 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,const TemplateSpecializationType * Param,QualType Arg,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)543 DeduceTemplateArguments(Sema &S,
544 TemplateParameterList *TemplateParams,
545 const TemplateSpecializationType *Param,
546 QualType Arg,
547 TemplateDeductionInfo &Info,
548 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
549 assert(Arg.isCanonical() && "Argument type must be canonical");
550
551 // Treat an injected-class-name as its underlying template-id.
552 if (auto *Injected = dyn_cast<InjectedClassNameType>(Arg))
553 Arg = Injected->getInjectedSpecializationType();
554
555 // Check whether the template argument is a dependent template-id.
556 if (const TemplateSpecializationType *SpecArg
557 = dyn_cast<TemplateSpecializationType>(Arg)) {
558 // Perform template argument deduction for the template name.
559 if (Sema::TemplateDeductionResult Result
560 = DeduceTemplateArguments(S, TemplateParams,
561 Param->getTemplateName(),
562 SpecArg->getTemplateName(),
563 Info, Deduced))
564 return Result;
565
566
567 // Perform template argument deduction on each template
568 // argument. Ignore any missing/extra arguments, since they could be
569 // filled in by default arguments.
570 return DeduceTemplateArguments(S, TemplateParams,
571 Param->template_arguments(),
572 SpecArg->template_arguments(), Info, Deduced,
573 /*NumberOfArgumentsMustMatch=*/false);
574 }
575
576 // If the argument type is a class template specialization, we
577 // perform template argument deduction using its template
578 // arguments.
579 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
580 if (!RecordArg) {
581 Info.FirstArg = TemplateArgument(QualType(Param, 0));
582 Info.SecondArg = TemplateArgument(Arg);
583 return Sema::TDK_NonDeducedMismatch;
584 }
585
586 ClassTemplateSpecializationDecl *SpecArg
587 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
588 if (!SpecArg) {
589 Info.FirstArg = TemplateArgument(QualType(Param, 0));
590 Info.SecondArg = TemplateArgument(Arg);
591 return Sema::TDK_NonDeducedMismatch;
592 }
593
594 // Perform template argument deduction for the template name.
595 if (Sema::TemplateDeductionResult Result
596 = DeduceTemplateArguments(S,
597 TemplateParams,
598 Param->getTemplateName(),
599 TemplateName(SpecArg->getSpecializedTemplate()),
600 Info, Deduced))
601 return Result;
602
603 // Perform template argument deduction for the template arguments.
604 return DeduceTemplateArguments(S, TemplateParams, Param->template_arguments(),
605 SpecArg->getTemplateArgs().asArray(), Info,
606 Deduced, /*NumberOfArgumentsMustMatch=*/true);
607 }
608
609 /// Determines whether the given type is an opaque type that
610 /// might be more qualified when instantiated.
IsPossiblyOpaquelyQualifiedType(QualType T)611 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
612 switch (T->getTypeClass()) {
613 case Type::TypeOfExpr:
614 case Type::TypeOf:
615 case Type::DependentName:
616 case Type::Decltype:
617 case Type::UnresolvedUsing:
618 case Type::TemplateTypeParm:
619 return true;
620
621 case Type::ConstantArray:
622 case Type::IncompleteArray:
623 case Type::VariableArray:
624 case Type::DependentSizedArray:
625 return IsPossiblyOpaquelyQualifiedType(
626 cast<ArrayType>(T)->getElementType());
627
628 default:
629 return false;
630 }
631 }
632
633 /// Helper function to build a TemplateParameter when we don't
634 /// know its type statically.
makeTemplateParameter(Decl * D)635 static TemplateParameter makeTemplateParameter(Decl *D) {
636 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
637 return TemplateParameter(TTP);
638 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
639 return TemplateParameter(NTTP);
640
641 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
642 }
643
644 /// If \p Param is an expanded parameter pack, get the number of expansions.
getExpandedPackSize(NamedDecl * Param)645 static Optional<unsigned> getExpandedPackSize(NamedDecl *Param) {
646 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param))
647 if (NTTP->isExpandedParameterPack())
648 return NTTP->getNumExpansionTypes();
649
650 if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param))
651 if (TTP->isExpandedParameterPack())
652 return TTP->getNumExpansionTemplateParameters();
653
654 return None;
655 }
656
657 /// A pack that we're currently deducing.
658 struct clang::DeducedPack {
659 // The index of the pack.
660 unsigned Index;
661
662 // The old value of the pack before we started deducing it.
663 DeducedTemplateArgument Saved;
664
665 // A deferred value of this pack from an inner deduction, that couldn't be
666 // deduced because this deduction hadn't happened yet.
667 DeducedTemplateArgument DeferredDeduction;
668
669 // The new value of the pack.
670 SmallVector<DeducedTemplateArgument, 4> New;
671
672 // The outer deduction for this pack, if any.
673 DeducedPack *Outer = nullptr;
674
DeducedPackclang::DeducedPack675 DeducedPack(unsigned Index) : Index(Index) {}
676 };
677
678 namespace {
679
680 /// A scope in which we're performing pack deduction.
681 class PackDeductionScope {
682 public:
683 /// Prepare to deduce the packs named within Pattern.
PackDeductionScope(Sema & S,TemplateParameterList * TemplateParams,SmallVectorImpl<DeducedTemplateArgument> & Deduced,TemplateDeductionInfo & Info,TemplateArgument Pattern)684 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
685 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
686 TemplateDeductionInfo &Info, TemplateArgument Pattern)
687 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
688 unsigned NumNamedPacks = addPacks(Pattern);
689 finishConstruction(NumNamedPacks);
690 }
691
692 /// Prepare to directly deduce arguments of the parameter with index \p Index.
PackDeductionScope(Sema & S,TemplateParameterList * TemplateParams,SmallVectorImpl<DeducedTemplateArgument> & Deduced,TemplateDeductionInfo & Info,unsigned Index)693 PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
694 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
695 TemplateDeductionInfo &Info, unsigned Index)
696 : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
697 addPack(Index);
698 finishConstruction(1);
699 }
700
701 private:
addPack(unsigned Index)702 void addPack(unsigned Index) {
703 // Save the deduced template argument for the parameter pack expanded
704 // by this pack expansion, then clear out the deduction.
705 DeducedPack Pack(Index);
706 Pack.Saved = Deduced[Index];
707 Deduced[Index] = TemplateArgument();
708
709 // FIXME: What if we encounter multiple packs with different numbers of
710 // pre-expanded expansions? (This should already have been diagnosed
711 // during substitution.)
712 if (Optional<unsigned> ExpandedPackExpansions =
713 getExpandedPackSize(TemplateParams->getParam(Index)))
714 FixedNumExpansions = ExpandedPackExpansions;
715
716 Packs.push_back(Pack);
717 }
718
addPacks(TemplateArgument Pattern)719 unsigned addPacks(TemplateArgument Pattern) {
720 // Compute the set of template parameter indices that correspond to
721 // parameter packs expanded by the pack expansion.
722 llvm::SmallBitVector SawIndices(TemplateParams->size());
723
724 auto AddPack = [&](unsigned Index) {
725 if (SawIndices[Index])
726 return;
727 SawIndices[Index] = true;
728 addPack(Index);
729 };
730
731 // First look for unexpanded packs in the pattern.
732 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
733 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
734 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
735 unsigned Depth, Index;
736 std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
737 if (Depth == Info.getDeducedDepth())
738 AddPack(Index);
739 }
740 assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
741
742 unsigned NumNamedPacks = Packs.size();
743
744 // We can also have deduced template parameters that do not actually
745 // appear in the pattern, but can be deduced by it (the type of a non-type
746 // template parameter pack, in particular). These won't have prevented us
747 // from partially expanding the pack.
748 llvm::SmallBitVector Used(TemplateParams->size());
749 MarkUsedTemplateParameters(S.Context, Pattern, /*OnlyDeduced*/true,
750 Info.getDeducedDepth(), Used);
751 for (int Index = Used.find_first(); Index != -1;
752 Index = Used.find_next(Index))
753 if (TemplateParams->getParam(Index)->isParameterPack())
754 AddPack(Index);
755
756 return NumNamedPacks;
757 }
758
finishConstruction(unsigned NumNamedPacks)759 void finishConstruction(unsigned NumNamedPacks) {
760 // Dig out the partially-substituted pack, if there is one.
761 const TemplateArgument *PartialPackArgs = nullptr;
762 unsigned NumPartialPackArgs = 0;
763 std::pair<unsigned, unsigned> PartialPackDepthIndex(-1u, -1u);
764 if (auto *Scope = S.CurrentInstantiationScope)
765 if (auto *Partial = Scope->getPartiallySubstitutedPack(
766 &PartialPackArgs, &NumPartialPackArgs))
767 PartialPackDepthIndex = getDepthAndIndex(Partial);
768
769 // This pack expansion will have been partially or fully expanded if
770 // it only names explicitly-specified parameter packs (including the
771 // partially-substituted one, if any).
772 bool IsExpanded = true;
773 for (unsigned I = 0; I != NumNamedPacks; ++I) {
774 if (Packs[I].Index >= Info.getNumExplicitArgs()) {
775 IsExpanded = false;
776 IsPartiallyExpanded = false;
777 break;
778 }
779 if (PartialPackDepthIndex ==
780 std::make_pair(Info.getDeducedDepth(), Packs[I].Index)) {
781 IsPartiallyExpanded = true;
782 }
783 }
784
785 // Skip over the pack elements that were expanded into separate arguments.
786 // If we partially expanded, this is the number of partial arguments.
787 if (IsPartiallyExpanded)
788 PackElements += NumPartialPackArgs;
789 else if (IsExpanded)
790 PackElements += *FixedNumExpansions;
791
792 for (auto &Pack : Packs) {
793 if (Info.PendingDeducedPacks.size() > Pack.Index)
794 Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
795 else
796 Info.PendingDeducedPacks.resize(Pack.Index + 1);
797 Info.PendingDeducedPacks[Pack.Index] = &Pack;
798
799 if (PartialPackDepthIndex ==
800 std::make_pair(Info.getDeducedDepth(), Pack.Index)) {
801 Pack.New.append(PartialPackArgs, PartialPackArgs + NumPartialPackArgs);
802 // We pre-populate the deduced value of the partially-substituted
803 // pack with the specified value. This is not entirely correct: the
804 // value is supposed to have been substituted, not deduced, but the
805 // cases where this is observable require an exact type match anyway.
806 //
807 // FIXME: If we could represent a "depth i, index j, pack elem k"
808 // parameter, we could substitute the partially-substituted pack
809 // everywhere and avoid this.
810 if (!IsPartiallyExpanded)
811 Deduced[Pack.Index] = Pack.New[PackElements];
812 }
813 }
814 }
815
816 public:
~PackDeductionScope()817 ~PackDeductionScope() {
818 for (auto &Pack : Packs)
819 Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
820 }
821
822 /// Determine whether this pack has already been partially expanded into a
823 /// sequence of (prior) function parameters / template arguments.
isPartiallyExpanded()824 bool isPartiallyExpanded() { return IsPartiallyExpanded; }
825
826 /// Determine whether this pack expansion scope has a known, fixed arity.
827 /// This happens if it involves a pack from an outer template that has
828 /// (notionally) already been expanded.
hasFixedArity()829 bool hasFixedArity() { return FixedNumExpansions.hasValue(); }
830
831 /// Determine whether the next element of the argument is still part of this
832 /// pack. This is the case unless the pack is already expanded to a fixed
833 /// length.
hasNextElement()834 bool hasNextElement() {
835 return !FixedNumExpansions || *FixedNumExpansions > PackElements;
836 }
837
838 /// Move to deducing the next element in each pack that is being deduced.
nextPackElement()839 void nextPackElement() {
840 // Capture the deduced template arguments for each parameter pack expanded
841 // by this pack expansion, add them to the list of arguments we've deduced
842 // for that pack, then clear out the deduced argument.
843 for (auto &Pack : Packs) {
844 DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
845 if (!Pack.New.empty() || !DeducedArg.isNull()) {
846 while (Pack.New.size() < PackElements)
847 Pack.New.push_back(DeducedTemplateArgument());
848 if (Pack.New.size() == PackElements)
849 Pack.New.push_back(DeducedArg);
850 else
851 Pack.New[PackElements] = DeducedArg;
852 DeducedArg = Pack.New.size() > PackElements + 1
853 ? Pack.New[PackElements + 1]
854 : DeducedTemplateArgument();
855 }
856 }
857 ++PackElements;
858 }
859
860 /// Finish template argument deduction for a set of argument packs,
861 /// producing the argument packs and checking for consistency with prior
862 /// deductions.
863 Sema::TemplateDeductionResult
finish(bool TreatNoDeductionsAsNonDeduced=true)864 finish(bool TreatNoDeductionsAsNonDeduced = true) {
865 // Build argument packs for each of the parameter packs expanded by this
866 // pack expansion.
867 for (auto &Pack : Packs) {
868 // Put back the old value for this pack.
869 Deduced[Pack.Index] = Pack.Saved;
870
871 // If we are deducing the size of this pack even if we didn't deduce any
872 // values for it, then make sure we build a pack of the right size.
873 // FIXME: Should we always deduce the size, even if the pack appears in
874 // a non-deduced context?
875 if (!TreatNoDeductionsAsNonDeduced)
876 Pack.New.resize(PackElements);
877
878 // Build or find a new value for this pack.
879 DeducedTemplateArgument NewPack;
880 if (PackElements && Pack.New.empty()) {
881 if (Pack.DeferredDeduction.isNull()) {
882 // We were not able to deduce anything for this parameter pack
883 // (because it only appeared in non-deduced contexts), so just
884 // restore the saved argument pack.
885 continue;
886 }
887
888 NewPack = Pack.DeferredDeduction;
889 Pack.DeferredDeduction = TemplateArgument();
890 } else if (Pack.New.empty()) {
891 // If we deduced an empty argument pack, create it now.
892 NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
893 } else {
894 TemplateArgument *ArgumentPack =
895 new (S.Context) TemplateArgument[Pack.New.size()];
896 std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
897 NewPack = DeducedTemplateArgument(
898 TemplateArgument(llvm::makeArrayRef(ArgumentPack, Pack.New.size())),
899 // FIXME: This is wrong, it's possible that some pack elements are
900 // deduced from an array bound and others are not:
901 // template<typename ...T, T ...V> void g(const T (&...p)[V]);
902 // g({1, 2, 3}, {{}, {}});
903 // ... should deduce T = {int, size_t (from array bound)}.
904 Pack.New[0].wasDeducedFromArrayBound());
905 }
906
907 // Pick where we're going to put the merged pack.
908 DeducedTemplateArgument *Loc;
909 if (Pack.Outer) {
910 if (Pack.Outer->DeferredDeduction.isNull()) {
911 // Defer checking this pack until we have a complete pack to compare
912 // it against.
913 Pack.Outer->DeferredDeduction = NewPack;
914 continue;
915 }
916 Loc = &Pack.Outer->DeferredDeduction;
917 } else {
918 Loc = &Deduced[Pack.Index];
919 }
920
921 // Check the new pack matches any previous value.
922 DeducedTemplateArgument OldPack = *Loc;
923 DeducedTemplateArgument Result =
924 checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
925
926 // If we deferred a deduction of this pack, check that one now too.
927 if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
928 OldPack = Result;
929 NewPack = Pack.DeferredDeduction;
930 Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
931 }
932
933 NamedDecl *Param = TemplateParams->getParam(Pack.Index);
934 if (Result.isNull()) {
935 Info.Param = makeTemplateParameter(Param);
936 Info.FirstArg = OldPack;
937 Info.SecondArg = NewPack;
938 return Sema::TDK_Inconsistent;
939 }
940
941 // If we have a pre-expanded pack and we didn't deduce enough elements
942 // for it, fail deduction.
943 if (Optional<unsigned> Expansions = getExpandedPackSize(Param)) {
944 if (*Expansions != PackElements) {
945 Info.Param = makeTemplateParameter(Param);
946 Info.FirstArg = Result;
947 return Sema::TDK_IncompletePack;
948 }
949 }
950
951 *Loc = Result;
952 }
953
954 return Sema::TDK_Success;
955 }
956
957 private:
958 Sema &S;
959 TemplateParameterList *TemplateParams;
960 SmallVectorImpl<DeducedTemplateArgument> &Deduced;
961 TemplateDeductionInfo &Info;
962 unsigned PackElements = 0;
963 bool IsPartiallyExpanded = false;
964 /// The number of expansions, if we have a fully-expanded pack in this scope.
965 Optional<unsigned> FixedNumExpansions;
966
967 SmallVector<DeducedPack, 2> Packs;
968 };
969
970 } // namespace
971
972 /// Deduce the template arguments by comparing the list of parameter
973 /// types to the list of argument types, as in the parameter-type-lists of
974 /// function types (C++ [temp.deduct.type]p10).
975 ///
976 /// \param S The semantic analysis object within which we are deducing
977 ///
978 /// \param TemplateParams The template parameters that we are deducing
979 ///
980 /// \param Params The list of parameter types
981 ///
982 /// \param NumParams The number of types in \c Params
983 ///
984 /// \param Args The list of argument types
985 ///
986 /// \param NumArgs The number of types in \c Args
987 ///
988 /// \param Info information about the template argument deduction itself
989 ///
990 /// \param Deduced the deduced template arguments
991 ///
992 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
993 /// how template argument deduction is performed.
994 ///
995 /// \param PartialOrdering If true, we are performing template argument
996 /// deduction for during partial ordering for a call
997 /// (C++0x [temp.deduct.partial]).
998 ///
999 /// \returns the result of template argument deduction so far. Note that a
1000 /// "success" result means that template argument deduction has not yet failed,
1001 /// but it may still fail, later, for other reasons.
1002 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,const QualType * Params,unsigned NumParams,const QualType * Args,unsigned NumArgs,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced,unsigned TDF,bool PartialOrdering=false)1003 DeduceTemplateArguments(Sema &S,
1004 TemplateParameterList *TemplateParams,
1005 const QualType *Params, unsigned NumParams,
1006 const QualType *Args, unsigned NumArgs,
1007 TemplateDeductionInfo &Info,
1008 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1009 unsigned TDF,
1010 bool PartialOrdering = false) {
1011 // C++0x [temp.deduct.type]p10:
1012 // Similarly, if P has a form that contains (T), then each parameter type
1013 // Pi of the respective parameter-type- list of P is compared with the
1014 // corresponding parameter type Ai of the corresponding parameter-type-list
1015 // of A. [...]
1016 unsigned ArgIdx = 0, ParamIdx = 0;
1017 for (; ParamIdx != NumParams; ++ParamIdx) {
1018 // Check argument types.
1019 const PackExpansionType *Expansion
1020 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
1021 if (!Expansion) {
1022 // Simple case: compare the parameter and argument types at this point.
1023
1024 // Make sure we have an argument.
1025 if (ArgIdx >= NumArgs)
1026 return Sema::TDK_MiscellaneousDeductionFailure;
1027
1028 if (isa<PackExpansionType>(Args[ArgIdx])) {
1029 // C++0x [temp.deduct.type]p22:
1030 // If the original function parameter associated with A is a function
1031 // parameter pack and the function parameter associated with P is not
1032 // a function parameter pack, then template argument deduction fails.
1033 return Sema::TDK_MiscellaneousDeductionFailure;
1034 }
1035
1036 if (Sema::TemplateDeductionResult Result
1037 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1038 Params[ParamIdx], Args[ArgIdx],
1039 Info, Deduced, TDF,
1040 PartialOrdering))
1041 return Result;
1042
1043 ++ArgIdx;
1044 continue;
1045 }
1046
1047 // C++0x [temp.deduct.type]p10:
1048 // If the parameter-declaration corresponding to Pi is a function
1049 // parameter pack, then the type of its declarator- id is compared with
1050 // each remaining parameter type in the parameter-type-list of A. Each
1051 // comparison deduces template arguments for subsequent positions in the
1052 // template parameter packs expanded by the function parameter pack.
1053
1054 QualType Pattern = Expansion->getPattern();
1055 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1056
1057 // A pack scope with fixed arity is not really a pack any more, so is not
1058 // a non-deduced context.
1059 if (ParamIdx + 1 == NumParams || PackScope.hasFixedArity()) {
1060 for (; ArgIdx < NumArgs && PackScope.hasNextElement(); ++ArgIdx) {
1061 // Deduce template arguments from the pattern.
1062 if (Sema::TemplateDeductionResult Result
1063 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
1064 Args[ArgIdx], Info, Deduced,
1065 TDF, PartialOrdering))
1066 return Result;
1067
1068 PackScope.nextPackElement();
1069 }
1070 } else {
1071 // C++0x [temp.deduct.type]p5:
1072 // The non-deduced contexts are:
1073 // - A function parameter pack that does not occur at the end of the
1074 // parameter-declaration-clause.
1075 //
1076 // FIXME: There is no wording to say what we should do in this case. We
1077 // choose to resolve this by applying the same rule that is applied for a
1078 // function call: that is, deduce all contained packs to their
1079 // explicitly-specified values (or to <> if there is no such value).
1080 //
1081 // This is seemingly-arbitrarily different from the case of a template-id
1082 // with a non-trailing pack-expansion in its arguments, which renders the
1083 // entire template-argument-list a non-deduced context.
1084
1085 // If the parameter type contains an explicitly-specified pack that we
1086 // could not expand, skip the number of parameters notionally created
1087 // by the expansion.
1088 Optional<unsigned> NumExpansions = Expansion->getNumExpansions();
1089 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
1090 for (unsigned I = 0; I != *NumExpansions && ArgIdx < NumArgs;
1091 ++I, ++ArgIdx)
1092 PackScope.nextPackElement();
1093 }
1094 }
1095
1096 // Build argument packs for each of the parameter packs expanded by this
1097 // pack expansion.
1098 if (auto Result = PackScope.finish())
1099 return Result;
1100 }
1101
1102 // Make sure we don't have any extra arguments.
1103 if (ArgIdx < NumArgs)
1104 return Sema::TDK_MiscellaneousDeductionFailure;
1105
1106 return Sema::TDK_Success;
1107 }
1108
1109 /// Determine whether the parameter has qualifiers that the argument
1110 /// lacks. Put another way, determine whether there is no way to add
1111 /// a deduced set of qualifiers to the ParamType that would result in
1112 /// its qualifiers matching those of the ArgType.
hasInconsistentOrSupersetQualifiersOf(QualType ParamType,QualType ArgType)1113 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
1114 QualType ArgType) {
1115 Qualifiers ParamQs = ParamType.getQualifiers();
1116 Qualifiers ArgQs = ArgType.getQualifiers();
1117
1118 if (ParamQs == ArgQs)
1119 return false;
1120
1121 // Mismatched (but not missing) Objective-C GC attributes.
1122 if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
1123 ParamQs.hasObjCGCAttr())
1124 return true;
1125
1126 // Mismatched (but not missing) address spaces.
1127 if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
1128 ParamQs.hasAddressSpace())
1129 return true;
1130
1131 // Mismatched (but not missing) Objective-C lifetime qualifiers.
1132 if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
1133 ParamQs.hasObjCLifetime())
1134 return true;
1135
1136 // CVR qualifiers inconsistent or a superset.
1137 return (ParamQs.getCVRQualifiers() & ~ArgQs.getCVRQualifiers()) != 0;
1138 }
1139
1140 /// Compare types for equality with respect to possibly compatible
1141 /// function types (noreturn adjustment, implicit calling conventions). If any
1142 /// of parameter and argument is not a function, just perform type comparison.
1143 ///
1144 /// \param Param the template parameter type.
1145 ///
1146 /// \param Arg the argument type.
isSameOrCompatibleFunctionType(CanQualType Param,CanQualType Arg)1147 bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
1148 CanQualType Arg) {
1149 const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
1150 *ArgFunction = Arg->getAs<FunctionType>();
1151
1152 // Just compare if not functions.
1153 if (!ParamFunction || !ArgFunction)
1154 return Param == Arg;
1155
1156 // Noreturn and noexcept adjustment.
1157 QualType AdjustedParam;
1158 if (IsFunctionConversion(Param, Arg, AdjustedParam))
1159 return Arg == Context.getCanonicalType(AdjustedParam);
1160
1161 // FIXME: Compatible calling conventions.
1162
1163 return Param == Arg;
1164 }
1165
1166 /// Get the index of the first template parameter that was originally from the
1167 /// innermost template-parameter-list. This is 0 except when we concatenate
1168 /// the template parameter lists of a class template and a constructor template
1169 /// when forming an implicit deduction guide.
getFirstInnerIndex(FunctionTemplateDecl * FTD)1170 static unsigned getFirstInnerIndex(FunctionTemplateDecl *FTD) {
1171 auto *Guide = dyn_cast<CXXDeductionGuideDecl>(FTD->getTemplatedDecl());
1172 if (!Guide || !Guide->isImplicit())
1173 return 0;
1174 return Guide->getDeducedTemplate()->getTemplateParameters()->size();
1175 }
1176
1177 /// Determine whether a type denotes a forwarding reference.
isForwardingReference(QualType Param,unsigned FirstInnerIndex)1178 static bool isForwardingReference(QualType Param, unsigned FirstInnerIndex) {
1179 // C++1z [temp.deduct.call]p3:
1180 // A forwarding reference is an rvalue reference to a cv-unqualified
1181 // template parameter that does not represent a template parameter of a
1182 // class template.
1183 if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
1184 if (ParamRef->getPointeeType().getQualifiers())
1185 return false;
1186 auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
1187 return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
1188 }
1189 return false;
1190 }
1191
1192 /// Deduce the template arguments by comparing the parameter type and
1193 /// the argument type (C++ [temp.deduct.type]).
1194 ///
1195 /// \param S the semantic analysis object within which we are deducing
1196 ///
1197 /// \param TemplateParams the template parameters that we are deducing
1198 ///
1199 /// \param ParamIn the parameter type
1200 ///
1201 /// \param ArgIn the argument type
1202 ///
1203 /// \param Info information about the template argument deduction itself
1204 ///
1205 /// \param Deduced the deduced template arguments
1206 ///
1207 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
1208 /// how template argument deduction is performed.
1209 ///
1210 /// \param PartialOrdering Whether we're performing template argument deduction
1211 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
1212 ///
1213 /// \returns the result of template argument deduction so far. Note that a
1214 /// "success" result means that template argument deduction has not yet failed,
1215 /// but it may still fail, later, for other reasons.
1216 static Sema::TemplateDeductionResult
DeduceTemplateArgumentsByTypeMatch(Sema & S,TemplateParameterList * TemplateParams,QualType ParamIn,QualType ArgIn,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced,unsigned TDF,bool PartialOrdering,bool DeducedFromArrayBound)1217 DeduceTemplateArgumentsByTypeMatch(Sema &S,
1218 TemplateParameterList *TemplateParams,
1219 QualType ParamIn, QualType ArgIn,
1220 TemplateDeductionInfo &Info,
1221 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1222 unsigned TDF,
1223 bool PartialOrdering,
1224 bool DeducedFromArrayBound) {
1225 // We only want to look at the canonical types, since typedefs and
1226 // sugar are not part of template argument deduction.
1227 QualType Param = S.Context.getCanonicalType(ParamIn);
1228 QualType Arg = S.Context.getCanonicalType(ArgIn);
1229
1230 // If the argument type is a pack expansion, look at its pattern.
1231 // This isn't explicitly called out
1232 if (const PackExpansionType *ArgExpansion
1233 = dyn_cast<PackExpansionType>(Arg))
1234 Arg = ArgExpansion->getPattern();
1235
1236 if (PartialOrdering) {
1237 // C++11 [temp.deduct.partial]p5:
1238 // Before the partial ordering is done, certain transformations are
1239 // performed on the types used for partial ordering:
1240 // - If P is a reference type, P is replaced by the type referred to.
1241 const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
1242 if (ParamRef)
1243 Param = ParamRef->getPointeeType();
1244
1245 // - If A is a reference type, A is replaced by the type referred to.
1246 const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
1247 if (ArgRef)
1248 Arg = ArgRef->getPointeeType();
1249
1250 if (ParamRef && ArgRef && S.Context.hasSameUnqualifiedType(Param, Arg)) {
1251 // C++11 [temp.deduct.partial]p9:
1252 // If, for a given type, deduction succeeds in both directions (i.e.,
1253 // the types are identical after the transformations above) and both
1254 // P and A were reference types [...]:
1255 // - if [one type] was an lvalue reference and [the other type] was
1256 // not, [the other type] is not considered to be at least as
1257 // specialized as [the first type]
1258 // - if [one type] is more cv-qualified than [the other type],
1259 // [the other type] is not considered to be at least as specialized
1260 // as [the first type]
1261 // Objective-C ARC adds:
1262 // - [one type] has non-trivial lifetime, [the other type] has
1263 // __unsafe_unretained lifetime, and the types are otherwise
1264 // identical
1265 //
1266 // A is "considered to be at least as specialized" as P iff deduction
1267 // succeeds, so we model this as a deduction failure. Note that
1268 // [the first type] is P and [the other type] is A here; the standard
1269 // gets this backwards.
1270 Qualifiers ParamQuals = Param.getQualifiers();
1271 Qualifiers ArgQuals = Arg.getQualifiers();
1272 if ((ParamRef->isLValueReferenceType() &&
1273 !ArgRef->isLValueReferenceType()) ||
1274 ParamQuals.isStrictSupersetOf(ArgQuals) ||
1275 (ParamQuals.hasNonTrivialObjCLifetime() &&
1276 ArgQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1277 ParamQuals.withoutObjCLifetime() ==
1278 ArgQuals.withoutObjCLifetime())) {
1279 Info.FirstArg = TemplateArgument(ParamIn);
1280 Info.SecondArg = TemplateArgument(ArgIn);
1281 return Sema::TDK_NonDeducedMismatch;
1282 }
1283 }
1284
1285 // C++11 [temp.deduct.partial]p7:
1286 // Remove any top-level cv-qualifiers:
1287 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
1288 // version of P.
1289 Param = Param.getUnqualifiedType();
1290 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
1291 // version of A.
1292 Arg = Arg.getUnqualifiedType();
1293 } else {
1294 // C++0x [temp.deduct.call]p4 bullet 1:
1295 // - If the original P is a reference type, the deduced A (i.e., the type
1296 // referred to by the reference) can be more cv-qualified than the
1297 // transformed A.
1298 if (TDF & TDF_ParamWithReferenceType) {
1299 Qualifiers Quals;
1300 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1301 Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1302 Arg.getCVRQualifiers());
1303 Param = S.Context.getQualifiedType(UnqualParam, Quals);
1304 }
1305
1306 if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1307 // C++0x [temp.deduct.type]p10:
1308 // If P and A are function types that originated from deduction when
1309 // taking the address of a function template (14.8.2.2) or when deducing
1310 // template arguments from a function declaration (14.8.2.6) and Pi and
1311 // Ai are parameters of the top-level parameter-type-list of P and A,
1312 // respectively, Pi is adjusted if it is a forwarding reference and Ai
1313 // is an lvalue reference, in
1314 // which case the type of Pi is changed to be the template parameter
1315 // type (i.e., T&& is changed to simply T). [ Note: As a result, when
1316 // Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1317 // deduced as X&. - end note ]
1318 TDF &= ~TDF_TopLevelParameterTypeList;
1319 if (isForwardingReference(Param, 0) && Arg->isLValueReferenceType())
1320 Param = Param->getPointeeType();
1321 }
1322 }
1323
1324 // C++ [temp.deduct.type]p9:
1325 // A template type argument T, a template template argument TT or a
1326 // template non-type argument i can be deduced if P and A have one of
1327 // the following forms:
1328 //
1329 // T
1330 // cv-list T
1331 if (const TemplateTypeParmType *TemplateTypeParm
1332 = Param->getAs<TemplateTypeParmType>()) {
1333 // Just skip any attempts to deduce from a placeholder type or a parameter
1334 // at a different depth.
1335 if (Arg->isPlaceholderType() ||
1336 Info.getDeducedDepth() != TemplateTypeParm->getDepth())
1337 return Sema::TDK_Success;
1338
1339 unsigned Index = TemplateTypeParm->getIndex();
1340 bool RecanonicalizeArg = false;
1341
1342 // If the argument type is an array type, move the qualifiers up to the
1343 // top level, so they can be matched with the qualifiers on the parameter.
1344 if (isa<ArrayType>(Arg)) {
1345 Qualifiers Quals;
1346 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1347 if (Quals) {
1348 Arg = S.Context.getQualifiedType(Arg, Quals);
1349 RecanonicalizeArg = true;
1350 }
1351 }
1352
1353 // The argument type can not be less qualified than the parameter
1354 // type.
1355 if (!(TDF & TDF_IgnoreQualifiers) &&
1356 hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1357 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1358 Info.FirstArg = TemplateArgument(Param);
1359 Info.SecondArg = TemplateArgument(Arg);
1360 return Sema::TDK_Underqualified;
1361 }
1362
1363 // Do not match a function type with a cv-qualified type.
1364 // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1584
1365 if (Arg->isFunctionType() && Param.hasQualifiers()) {
1366 return Sema::TDK_NonDeducedMismatch;
1367 }
1368
1369 assert(TemplateTypeParm->getDepth() == Info.getDeducedDepth() &&
1370 "saw template type parameter with wrong depth");
1371 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1372 QualType DeducedType = Arg;
1373
1374 // Remove any qualifiers on the parameter from the deduced type.
1375 // We checked the qualifiers for consistency above.
1376 Qualifiers DeducedQs = DeducedType.getQualifiers();
1377 Qualifiers ParamQs = Param.getQualifiers();
1378 DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1379 if (ParamQs.hasObjCGCAttr())
1380 DeducedQs.removeObjCGCAttr();
1381 if (ParamQs.hasAddressSpace())
1382 DeducedQs.removeAddressSpace();
1383 if (ParamQs.hasObjCLifetime())
1384 DeducedQs.removeObjCLifetime();
1385
1386 // Objective-C ARC:
1387 // If template deduction would produce a lifetime qualifier on a type
1388 // that is not a lifetime type, template argument deduction fails.
1389 if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1390 !DeducedType->isDependentType()) {
1391 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1392 Info.FirstArg = TemplateArgument(Param);
1393 Info.SecondArg = TemplateArgument(Arg);
1394 return Sema::TDK_Underqualified;
1395 }
1396
1397 // Objective-C ARC:
1398 // If template deduction would produce an argument type with lifetime type
1399 // but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1400 if (S.getLangOpts().ObjCAutoRefCount &&
1401 DeducedType->isObjCLifetimeType() &&
1402 !DeducedQs.hasObjCLifetime())
1403 DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1404
1405 DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1406 DeducedQs);
1407
1408 if (RecanonicalizeArg)
1409 DeducedType = S.Context.getCanonicalType(DeducedType);
1410
1411 DeducedTemplateArgument NewDeduced(DeducedType, DeducedFromArrayBound);
1412 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1413 Deduced[Index],
1414 NewDeduced);
1415 if (Result.isNull()) {
1416 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1417 Info.FirstArg = Deduced[Index];
1418 Info.SecondArg = NewDeduced;
1419 return Sema::TDK_Inconsistent;
1420 }
1421
1422 Deduced[Index] = Result;
1423 return Sema::TDK_Success;
1424 }
1425
1426 // Set up the template argument deduction information for a failure.
1427 Info.FirstArg = TemplateArgument(ParamIn);
1428 Info.SecondArg = TemplateArgument(ArgIn);
1429
1430 // If the parameter is an already-substituted template parameter
1431 // pack, do nothing: we don't know which of its arguments to look
1432 // at, so we have to wait until all of the parameter packs in this
1433 // expansion have arguments.
1434 if (isa<SubstTemplateTypeParmPackType>(Param))
1435 return Sema::TDK_Success;
1436
1437 // Check the cv-qualifiers on the parameter and argument types.
1438 CanQualType CanParam = S.Context.getCanonicalType(Param);
1439 CanQualType CanArg = S.Context.getCanonicalType(Arg);
1440 if (!(TDF & TDF_IgnoreQualifiers)) {
1441 if (TDF & TDF_ParamWithReferenceType) {
1442 if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1443 return Sema::TDK_NonDeducedMismatch;
1444 } else if (TDF & TDF_ArgWithReferenceType) {
1445 // C++ [temp.deduct.conv]p4:
1446 // If the original A is a reference type, A can be more cv-qualified
1447 // than the deduced A
1448 if (!Arg.getQualifiers().compatiblyIncludes(Param.getQualifiers()))
1449 return Sema::TDK_NonDeducedMismatch;
1450
1451 // Strip out all extra qualifiers from the argument to figure out the
1452 // type we're converting to, prior to the qualification conversion.
1453 Qualifiers Quals;
1454 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1455 Arg = S.Context.getQualifiedType(Arg, Param.getQualifiers());
1456 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1457 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1458 return Sema::TDK_NonDeducedMismatch;
1459 }
1460
1461 // If the parameter type is not dependent, there is nothing to deduce.
1462 if (!Param->isDependentType()) {
1463 if (!(TDF & TDF_SkipNonDependent)) {
1464 bool NonDeduced =
1465 (TDF & TDF_AllowCompatibleFunctionType)
1466 ? !S.isSameOrCompatibleFunctionType(CanParam, CanArg)
1467 : Param != Arg;
1468 if (NonDeduced) {
1469 return Sema::TDK_NonDeducedMismatch;
1470 }
1471 }
1472 return Sema::TDK_Success;
1473 }
1474 } else if (!Param->isDependentType()) {
1475 CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1476 ArgUnqualType = CanArg.getUnqualifiedType();
1477 bool Success =
1478 (TDF & TDF_AllowCompatibleFunctionType)
1479 ? S.isSameOrCompatibleFunctionType(ParamUnqualType, ArgUnqualType)
1480 : ParamUnqualType == ArgUnqualType;
1481 if (Success)
1482 return Sema::TDK_Success;
1483 }
1484
1485 switch (Param->getTypeClass()) {
1486 // Non-canonical types cannot appear here.
1487 #define NON_CANONICAL_TYPE(Class, Base) \
1488 case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1489 #define TYPE(Class, Base)
1490 #include "clang/AST/TypeNodes.def"
1491
1492 case Type::TemplateTypeParm:
1493 case Type::SubstTemplateTypeParmPack:
1494 llvm_unreachable("Type nodes handled above");
1495
1496 // These types cannot be dependent, so simply check whether the types are
1497 // the same.
1498 case Type::Builtin:
1499 case Type::VariableArray:
1500 case Type::Vector:
1501 case Type::FunctionNoProto:
1502 case Type::Record:
1503 case Type::Enum:
1504 case Type::ObjCObject:
1505 case Type::ObjCInterface:
1506 case Type::ObjCObjectPointer:
1507 if (TDF & TDF_SkipNonDependent)
1508 return Sema::TDK_Success;
1509
1510 if (TDF & TDF_IgnoreQualifiers) {
1511 Param = Param.getUnqualifiedType();
1512 Arg = Arg.getUnqualifiedType();
1513 }
1514
1515 return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1516
1517 // _Complex T [placeholder extension]
1518 case Type::Complex:
1519 if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1520 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1521 cast<ComplexType>(Param)->getElementType(),
1522 ComplexArg->getElementType(),
1523 Info, Deduced, TDF);
1524
1525 return Sema::TDK_NonDeducedMismatch;
1526
1527 // _Atomic T [extension]
1528 case Type::Atomic:
1529 if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1530 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1531 cast<AtomicType>(Param)->getValueType(),
1532 AtomicArg->getValueType(),
1533 Info, Deduced, TDF);
1534
1535 return Sema::TDK_NonDeducedMismatch;
1536
1537 // T *
1538 case Type::Pointer: {
1539 QualType PointeeType;
1540 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1541 PointeeType = PointerArg->getPointeeType();
1542 } else if (const ObjCObjectPointerType *PointerArg
1543 = Arg->getAs<ObjCObjectPointerType>()) {
1544 PointeeType = PointerArg->getPointeeType();
1545 } else {
1546 return Sema::TDK_NonDeducedMismatch;
1547 }
1548
1549 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1550 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1551 cast<PointerType>(Param)->getPointeeType(),
1552 PointeeType,
1553 Info, Deduced, SubTDF);
1554 }
1555
1556 // T &
1557 case Type::LValueReference: {
1558 const LValueReferenceType *ReferenceArg =
1559 Arg->getAs<LValueReferenceType>();
1560 if (!ReferenceArg)
1561 return Sema::TDK_NonDeducedMismatch;
1562
1563 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1564 cast<LValueReferenceType>(Param)->getPointeeType(),
1565 ReferenceArg->getPointeeType(), Info, Deduced, 0);
1566 }
1567
1568 // T && [C++0x]
1569 case Type::RValueReference: {
1570 const RValueReferenceType *ReferenceArg =
1571 Arg->getAs<RValueReferenceType>();
1572 if (!ReferenceArg)
1573 return Sema::TDK_NonDeducedMismatch;
1574
1575 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1576 cast<RValueReferenceType>(Param)->getPointeeType(),
1577 ReferenceArg->getPointeeType(),
1578 Info, Deduced, 0);
1579 }
1580
1581 // T [] (implied, but not stated explicitly)
1582 case Type::IncompleteArray: {
1583 const IncompleteArrayType *IncompleteArrayArg =
1584 S.Context.getAsIncompleteArrayType(Arg);
1585 if (!IncompleteArrayArg)
1586 return Sema::TDK_NonDeducedMismatch;
1587
1588 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1589 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1590 S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1591 IncompleteArrayArg->getElementType(),
1592 Info, Deduced, SubTDF);
1593 }
1594
1595 // T [integer-constant]
1596 case Type::ConstantArray: {
1597 const ConstantArrayType *ConstantArrayArg =
1598 S.Context.getAsConstantArrayType(Arg);
1599 if (!ConstantArrayArg)
1600 return Sema::TDK_NonDeducedMismatch;
1601
1602 const ConstantArrayType *ConstantArrayParm =
1603 S.Context.getAsConstantArrayType(Param);
1604 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1605 return Sema::TDK_NonDeducedMismatch;
1606
1607 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1608 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1609 ConstantArrayParm->getElementType(),
1610 ConstantArrayArg->getElementType(),
1611 Info, Deduced, SubTDF);
1612 }
1613
1614 // type [i]
1615 case Type::DependentSizedArray: {
1616 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1617 if (!ArrayArg)
1618 return Sema::TDK_NonDeducedMismatch;
1619
1620 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1621
1622 // Check the element type of the arrays
1623 const DependentSizedArrayType *DependentArrayParm
1624 = S.Context.getAsDependentSizedArrayType(Param);
1625 if (Sema::TemplateDeductionResult Result
1626 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1627 DependentArrayParm->getElementType(),
1628 ArrayArg->getElementType(),
1629 Info, Deduced, SubTDF))
1630 return Result;
1631
1632 // Determine the array bound is something we can deduce.
1633 NonTypeTemplateParmDecl *NTTP
1634 = getDeducedParameterFromExpr(Info, DependentArrayParm->getSizeExpr());
1635 if (!NTTP)
1636 return Sema::TDK_Success;
1637
1638 // We can perform template argument deduction for the given non-type
1639 // template parameter.
1640 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1641 "saw non-type template parameter with wrong depth");
1642 if (const ConstantArrayType *ConstantArrayArg
1643 = dyn_cast<ConstantArrayType>(ArrayArg)) {
1644 llvm::APSInt Size(ConstantArrayArg->getSize());
1645 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, Size,
1646 S.Context.getSizeType(),
1647 /*ArrayBound=*/true,
1648 Info, Deduced);
1649 }
1650 if (const DependentSizedArrayType *DependentArrayArg
1651 = dyn_cast<DependentSizedArrayType>(ArrayArg))
1652 if (DependentArrayArg->getSizeExpr())
1653 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
1654 DependentArrayArg->getSizeExpr(),
1655 Info, Deduced);
1656
1657 // Incomplete type does not match a dependently-sized array type
1658 return Sema::TDK_NonDeducedMismatch;
1659 }
1660
1661 // type(*)(T)
1662 // T(*)()
1663 // T(*)(T)
1664 case Type::FunctionProto: {
1665 unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1666 const FunctionProtoType *FunctionProtoArg =
1667 dyn_cast<FunctionProtoType>(Arg);
1668 if (!FunctionProtoArg)
1669 return Sema::TDK_NonDeducedMismatch;
1670
1671 const FunctionProtoType *FunctionProtoParam =
1672 cast<FunctionProtoType>(Param);
1673
1674 if (FunctionProtoParam->getTypeQuals()
1675 != FunctionProtoArg->getTypeQuals() ||
1676 FunctionProtoParam->getRefQualifier()
1677 != FunctionProtoArg->getRefQualifier() ||
1678 FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1679 return Sema::TDK_NonDeducedMismatch;
1680
1681 // Check return types.
1682 if (auto Result = DeduceTemplateArgumentsByTypeMatch(
1683 S, TemplateParams, FunctionProtoParam->getReturnType(),
1684 FunctionProtoArg->getReturnType(), Info, Deduced, 0))
1685 return Result;
1686
1687 // Check parameter types.
1688 if (auto Result = DeduceTemplateArguments(
1689 S, TemplateParams, FunctionProtoParam->param_type_begin(),
1690 FunctionProtoParam->getNumParams(),
1691 FunctionProtoArg->param_type_begin(),
1692 FunctionProtoArg->getNumParams(), Info, Deduced, SubTDF))
1693 return Result;
1694
1695 if (TDF & TDF_AllowCompatibleFunctionType)
1696 return Sema::TDK_Success;
1697
1698 // FIXME: Per core-2016/10/1019 (no corresponding core issue yet), permit
1699 // deducing through the noexcept-specifier if it's part of the canonical
1700 // type. libstdc++ relies on this.
1701 Expr *NoexceptExpr = FunctionProtoParam->getNoexceptExpr();
1702 if (NonTypeTemplateParmDecl *NTTP =
1703 NoexceptExpr ? getDeducedParameterFromExpr(Info, NoexceptExpr)
1704 : nullptr) {
1705 assert(NTTP->getDepth() == Info.getDeducedDepth() &&
1706 "saw non-type template parameter with wrong depth");
1707
1708 llvm::APSInt Noexcept(1);
1709 switch (FunctionProtoArg->canThrow()) {
1710 case CT_Cannot:
1711 Noexcept = 1;
1712 LLVM_FALLTHROUGH;
1713
1714 case CT_Can:
1715 // We give E in noexcept(E) the "deduced from array bound" treatment.
1716 // FIXME: Should we?
1717 return DeduceNonTypeTemplateArgument(
1718 S, TemplateParams, NTTP, Noexcept, S.Context.BoolTy,
1719 /*ArrayBound*/true, Info, Deduced);
1720
1721 case CT_Dependent:
1722 if (Expr *ArgNoexceptExpr = FunctionProtoArg->getNoexceptExpr())
1723 return DeduceNonTypeTemplateArgument(
1724 S, TemplateParams, NTTP, ArgNoexceptExpr, Info, Deduced);
1725 // Can't deduce anything from throw(T...).
1726 break;
1727 }
1728 }
1729 // FIXME: Detect non-deduced exception specification mismatches?
1730 //
1731 // Careful about [temp.deduct.call] and [temp.deduct.conv], which allow
1732 // top-level differences in noexcept-specifications.
1733
1734 return Sema::TDK_Success;
1735 }
1736
1737 case Type::InjectedClassName:
1738 // Treat a template's injected-class-name as if the template
1739 // specialization type had been used.
1740 Param = cast<InjectedClassNameType>(Param)
1741 ->getInjectedSpecializationType();
1742 assert(isa<TemplateSpecializationType>(Param) &&
1743 "injected class name is not a template specialization type");
1744 LLVM_FALLTHROUGH;
1745
1746 // template-name<T> (where template-name refers to a class template)
1747 // template-name<i>
1748 // TT<T>
1749 // TT<i>
1750 // TT<>
1751 case Type::TemplateSpecialization: {
1752 const TemplateSpecializationType *SpecParam =
1753 cast<TemplateSpecializationType>(Param);
1754
1755 // When Arg cannot be a derived class, we can just try to deduce template
1756 // arguments from the template-id.
1757 const RecordType *RecordT = Arg->getAs<RecordType>();
1758 if (!(TDF & TDF_DerivedClass) || !RecordT)
1759 return DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg, Info,
1760 Deduced);
1761
1762 SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1763 Deduced.end());
1764
1765 Sema::TemplateDeductionResult Result = DeduceTemplateArguments(
1766 S, TemplateParams, SpecParam, Arg, Info, Deduced);
1767
1768 if (Result == Sema::TDK_Success)
1769 return Result;
1770
1771 // We cannot inspect base classes as part of deduction when the type
1772 // is incomplete, so either instantiate any templates necessary to
1773 // complete the type, or skip over it if it cannot be completed.
1774 if (!S.isCompleteType(Info.getLocation(), Arg))
1775 return Result;
1776
1777 // C++14 [temp.deduct.call] p4b3:
1778 // If P is a class and P has the form simple-template-id, then the
1779 // transformed A can be a derived class of the deduced A. Likewise if
1780 // P is a pointer to a class of the form simple-template-id, the
1781 // transformed A can be a pointer to a derived class pointed to by the
1782 // deduced A.
1783 //
1784 // These alternatives are considered only if type deduction would
1785 // otherwise fail. If they yield more than one possible deduced A, the
1786 // type deduction fails.
1787
1788 // Reset the incorrectly deduced argument from above.
1789 Deduced = DeducedOrig;
1790
1791 // Use data recursion to crawl through the list of base classes.
1792 // Visited contains the set of nodes we have already visited, while
1793 // ToVisit is our stack of records that we still need to visit.
1794 llvm::SmallPtrSet<const RecordType *, 8> Visited;
1795 SmallVector<const RecordType *, 8> ToVisit;
1796 ToVisit.push_back(RecordT);
1797 bool Successful = false;
1798 SmallVector<DeducedTemplateArgument, 8> SuccessfulDeduced;
1799 while (!ToVisit.empty()) {
1800 // Retrieve the next class in the inheritance hierarchy.
1801 const RecordType *NextT = ToVisit.pop_back_val();
1802
1803 // If we have already seen this type, skip it.
1804 if (!Visited.insert(NextT).second)
1805 continue;
1806
1807 // If this is a base class, try to perform template argument
1808 // deduction from it.
1809 if (NextT != RecordT) {
1810 TemplateDeductionInfo BaseInfo(Info.getLocation());
1811 Sema::TemplateDeductionResult BaseResult =
1812 DeduceTemplateArguments(S, TemplateParams, SpecParam,
1813 QualType(NextT, 0), BaseInfo, Deduced);
1814
1815 // If template argument deduction for this base was successful,
1816 // note that we had some success. Otherwise, ignore any deductions
1817 // from this base class.
1818 if (BaseResult == Sema::TDK_Success) {
1819 // If we've already seen some success, then deduction fails due to
1820 // an ambiguity (temp.deduct.call p5).
1821 if (Successful)
1822 return Sema::TDK_MiscellaneousDeductionFailure;
1823
1824 Successful = true;
1825 std::swap(SuccessfulDeduced, Deduced);
1826
1827 Info.Param = BaseInfo.Param;
1828 Info.FirstArg = BaseInfo.FirstArg;
1829 Info.SecondArg = BaseInfo.SecondArg;
1830 }
1831
1832 Deduced = DeducedOrig;
1833 }
1834
1835 // Visit base classes
1836 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1837 for (const auto &Base : Next->bases()) {
1838 assert(Base.getType()->isRecordType() &&
1839 "Base class that isn't a record?");
1840 ToVisit.push_back(Base.getType()->getAs<RecordType>());
1841 }
1842 }
1843
1844 if (Successful) {
1845 std::swap(SuccessfulDeduced, Deduced);
1846 return Sema::TDK_Success;
1847 }
1848
1849 return Result;
1850 }
1851
1852 // T type::*
1853 // T T::*
1854 // T (type::*)()
1855 // type (T::*)()
1856 // type (type::*)(T)
1857 // type (T::*)(T)
1858 // T (type::*)(T)
1859 // T (T::*)()
1860 // T (T::*)(T)
1861 case Type::MemberPointer: {
1862 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1863 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1864 if (!MemPtrArg)
1865 return Sema::TDK_NonDeducedMismatch;
1866
1867 QualType ParamPointeeType = MemPtrParam->getPointeeType();
1868 if (ParamPointeeType->isFunctionType())
1869 S.adjustMemberFunctionCC(ParamPointeeType, /*IsStatic=*/true,
1870 /*IsCtorOrDtor=*/false, Info.getLocation());
1871 QualType ArgPointeeType = MemPtrArg->getPointeeType();
1872 if (ArgPointeeType->isFunctionType())
1873 S.adjustMemberFunctionCC(ArgPointeeType, /*IsStatic=*/true,
1874 /*IsCtorOrDtor=*/false, Info.getLocation());
1875
1876 if (Sema::TemplateDeductionResult Result
1877 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1878 ParamPointeeType,
1879 ArgPointeeType,
1880 Info, Deduced,
1881 TDF & TDF_IgnoreQualifiers))
1882 return Result;
1883
1884 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1885 QualType(MemPtrParam->getClass(), 0),
1886 QualType(MemPtrArg->getClass(), 0),
1887 Info, Deduced,
1888 TDF & TDF_IgnoreQualifiers);
1889 }
1890
1891 // (clang extension)
1892 //
1893 // type(^)(T)
1894 // T(^)()
1895 // T(^)(T)
1896 case Type::BlockPointer: {
1897 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1898 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1899
1900 if (!BlockPtrArg)
1901 return Sema::TDK_NonDeducedMismatch;
1902
1903 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1904 BlockPtrParam->getPointeeType(),
1905 BlockPtrArg->getPointeeType(),
1906 Info, Deduced, 0);
1907 }
1908
1909 // (clang extension)
1910 //
1911 // T __attribute__(((ext_vector_type(<integral constant>))))
1912 case Type::ExtVector: {
1913 const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1914 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1915 // Make sure that the vectors have the same number of elements.
1916 if (VectorParam->getNumElements() != VectorArg->getNumElements())
1917 return Sema::TDK_NonDeducedMismatch;
1918
1919 // Perform deduction on the element types.
1920 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1921 VectorParam->getElementType(),
1922 VectorArg->getElementType(),
1923 Info, Deduced, TDF);
1924 }
1925
1926 if (const DependentSizedExtVectorType *VectorArg
1927 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1928 // We can't check the number of elements, since the argument has a
1929 // dependent number of elements. This can only occur during partial
1930 // ordering.
1931
1932 // Perform deduction on the element types.
1933 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1934 VectorParam->getElementType(),
1935 VectorArg->getElementType(),
1936 Info, Deduced, TDF);
1937 }
1938
1939 return Sema::TDK_NonDeducedMismatch;
1940 }
1941
1942 case Type::DependentVector: {
1943 const auto *VectorParam = cast<DependentVectorType>(Param);
1944
1945 if (const auto *VectorArg = dyn_cast<VectorType>(Arg)) {
1946 // Perform deduction on the element types.
1947 if (Sema::TemplateDeductionResult Result =
1948 DeduceTemplateArgumentsByTypeMatch(
1949 S, TemplateParams, VectorParam->getElementType(),
1950 VectorArg->getElementType(), Info, Deduced, TDF))
1951 return Result;
1952
1953 // Perform deduction on the vector size, if we can.
1954 NonTypeTemplateParmDecl *NTTP =
1955 getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
1956 if (!NTTP)
1957 return Sema::TDK_Success;
1958
1959 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1960 ArgSize = VectorArg->getNumElements();
1961 // Note that we use the "array bound" rules here; just like in that
1962 // case, we don't have any particular type for the vector size, but
1963 // we can provide one if necessary.
1964 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
1965 S.Context.UnsignedIntTy, true,
1966 Info, Deduced);
1967 }
1968
1969 if (const auto *VectorArg = dyn_cast<DependentVectorType>(Arg)) {
1970 // Perform deduction on the element types.
1971 if (Sema::TemplateDeductionResult Result =
1972 DeduceTemplateArgumentsByTypeMatch(
1973 S, TemplateParams, VectorParam->getElementType(),
1974 VectorArg->getElementType(), Info, Deduced, TDF))
1975 return Result;
1976
1977 // Perform deduction on the vector size, if we can.
1978 NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
1979 Info, VectorParam->getSizeExpr());
1980 if (!NTTP)
1981 return Sema::TDK_Success;
1982
1983 return DeduceNonTypeTemplateArgument(
1984 S, TemplateParams, NTTP, VectorArg->getSizeExpr(), Info, Deduced);
1985 }
1986
1987 return Sema::TDK_NonDeducedMismatch;
1988 }
1989
1990 // (clang extension)
1991 //
1992 // T __attribute__(((ext_vector_type(N))))
1993 case Type::DependentSizedExtVector: {
1994 const DependentSizedExtVectorType *VectorParam
1995 = cast<DependentSizedExtVectorType>(Param);
1996
1997 if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1998 // Perform deduction on the element types.
1999 if (Sema::TemplateDeductionResult Result
2000 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2001 VectorParam->getElementType(),
2002 VectorArg->getElementType(),
2003 Info, Deduced, TDF))
2004 return Result;
2005
2006 // Perform deduction on the vector size, if we can.
2007 NonTypeTemplateParmDecl *NTTP
2008 = getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
2009 if (!NTTP)
2010 return Sema::TDK_Success;
2011
2012 llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
2013 ArgSize = VectorArg->getNumElements();
2014 // Note that we use the "array bound" rules here; just like in that
2015 // case, we don't have any particular type for the vector size, but
2016 // we can provide one if necessary.
2017 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP, ArgSize,
2018 S.Context.IntTy, true, Info,
2019 Deduced);
2020 }
2021
2022 if (const DependentSizedExtVectorType *VectorArg
2023 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
2024 // Perform deduction on the element types.
2025 if (Sema::TemplateDeductionResult Result
2026 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2027 VectorParam->getElementType(),
2028 VectorArg->getElementType(),
2029 Info, Deduced, TDF))
2030 return Result;
2031
2032 // Perform deduction on the vector size, if we can.
2033 NonTypeTemplateParmDecl *NTTP
2034 = getDeducedParameterFromExpr(Info, VectorParam->getSizeExpr());
2035 if (!NTTP)
2036 return Sema::TDK_Success;
2037
2038 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2039 VectorArg->getSizeExpr(),
2040 Info, Deduced);
2041 }
2042
2043 return Sema::TDK_NonDeducedMismatch;
2044 }
2045
2046 // (clang extension)
2047 //
2048 // T __attribute__(((address_space(N))))
2049 case Type::DependentAddressSpace: {
2050 const DependentAddressSpaceType *AddressSpaceParam =
2051 cast<DependentAddressSpaceType>(Param);
2052
2053 if (const DependentAddressSpaceType *AddressSpaceArg =
2054 dyn_cast<DependentAddressSpaceType>(Arg)) {
2055 // Perform deduction on the pointer type.
2056 if (Sema::TemplateDeductionResult Result =
2057 DeduceTemplateArgumentsByTypeMatch(
2058 S, TemplateParams, AddressSpaceParam->getPointeeType(),
2059 AddressSpaceArg->getPointeeType(), Info, Deduced, TDF))
2060 return Result;
2061
2062 // Perform deduction on the address space, if we can.
2063 NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
2064 Info, AddressSpaceParam->getAddrSpaceExpr());
2065 if (!NTTP)
2066 return Sema::TDK_Success;
2067
2068 return DeduceNonTypeTemplateArgument(
2069 S, TemplateParams, NTTP, AddressSpaceArg->getAddrSpaceExpr(), Info,
2070 Deduced);
2071 }
2072
2073 if (isTargetAddressSpace(Arg.getAddressSpace())) {
2074 llvm::APSInt ArgAddressSpace(S.Context.getTypeSize(S.Context.IntTy),
2075 false);
2076 ArgAddressSpace = toTargetAddressSpace(Arg.getAddressSpace());
2077
2078 // Perform deduction on the pointer types.
2079 if (Sema::TemplateDeductionResult Result =
2080 DeduceTemplateArgumentsByTypeMatch(
2081 S, TemplateParams, AddressSpaceParam->getPointeeType(),
2082 S.Context.removeAddrSpaceQualType(Arg), Info, Deduced, TDF))
2083 return Result;
2084
2085 // Perform deduction on the address space, if we can.
2086 NonTypeTemplateParmDecl *NTTP = getDeducedParameterFromExpr(
2087 Info, AddressSpaceParam->getAddrSpaceExpr());
2088 if (!NTTP)
2089 return Sema::TDK_Success;
2090
2091 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2092 ArgAddressSpace, S.Context.IntTy,
2093 true, Info, Deduced);
2094 }
2095
2096 return Sema::TDK_NonDeducedMismatch;
2097 }
2098
2099 case Type::TypeOfExpr:
2100 case Type::TypeOf:
2101 case Type::DependentName:
2102 case Type::UnresolvedUsing:
2103 case Type::Decltype:
2104 case Type::UnaryTransform:
2105 case Type::Auto:
2106 case Type::DeducedTemplateSpecialization:
2107 case Type::DependentTemplateSpecialization:
2108 case Type::PackExpansion:
2109 case Type::Pipe:
2110 // No template argument deduction for these types
2111 return Sema::TDK_Success;
2112 }
2113
2114 llvm_unreachable("Invalid Type Class!");
2115 }
2116
2117 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,const TemplateArgument & Param,TemplateArgument Arg,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)2118 DeduceTemplateArguments(Sema &S,
2119 TemplateParameterList *TemplateParams,
2120 const TemplateArgument &Param,
2121 TemplateArgument Arg,
2122 TemplateDeductionInfo &Info,
2123 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2124 // If the template argument is a pack expansion, perform template argument
2125 // deduction against the pattern of that expansion. This only occurs during
2126 // partial ordering.
2127 if (Arg.isPackExpansion())
2128 Arg = Arg.getPackExpansionPattern();
2129
2130 switch (Param.getKind()) {
2131 case TemplateArgument::Null:
2132 llvm_unreachable("Null template argument in parameter list");
2133
2134 case TemplateArgument::Type:
2135 if (Arg.getKind() == TemplateArgument::Type)
2136 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
2137 Param.getAsType(),
2138 Arg.getAsType(),
2139 Info, Deduced, 0);
2140 Info.FirstArg = Param;
2141 Info.SecondArg = Arg;
2142 return Sema::TDK_NonDeducedMismatch;
2143
2144 case TemplateArgument::Template:
2145 if (Arg.getKind() == TemplateArgument::Template)
2146 return DeduceTemplateArguments(S, TemplateParams,
2147 Param.getAsTemplate(),
2148 Arg.getAsTemplate(), Info, Deduced);
2149 Info.FirstArg = Param;
2150 Info.SecondArg = Arg;
2151 return Sema::TDK_NonDeducedMismatch;
2152
2153 case TemplateArgument::TemplateExpansion:
2154 llvm_unreachable("caller should handle pack expansions");
2155
2156 case TemplateArgument::Declaration:
2157 if (Arg.getKind() == TemplateArgument::Declaration &&
2158 isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
2159 return Sema::TDK_Success;
2160
2161 Info.FirstArg = Param;
2162 Info.SecondArg = Arg;
2163 return Sema::TDK_NonDeducedMismatch;
2164
2165 case TemplateArgument::NullPtr:
2166 if (Arg.getKind() == TemplateArgument::NullPtr &&
2167 S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
2168 return Sema::TDK_Success;
2169
2170 Info.FirstArg = Param;
2171 Info.SecondArg = Arg;
2172 return Sema::TDK_NonDeducedMismatch;
2173
2174 case TemplateArgument::Integral:
2175 if (Arg.getKind() == TemplateArgument::Integral) {
2176 if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
2177 return Sema::TDK_Success;
2178
2179 Info.FirstArg = Param;
2180 Info.SecondArg = Arg;
2181 return Sema::TDK_NonDeducedMismatch;
2182 }
2183
2184 if (Arg.getKind() == TemplateArgument::Expression) {
2185 Info.FirstArg = Param;
2186 Info.SecondArg = Arg;
2187 return Sema::TDK_NonDeducedMismatch;
2188 }
2189
2190 Info.FirstArg = Param;
2191 Info.SecondArg = Arg;
2192 return Sema::TDK_NonDeducedMismatch;
2193
2194 case TemplateArgument::Expression:
2195 if (NonTypeTemplateParmDecl *NTTP
2196 = getDeducedParameterFromExpr(Info, Param.getAsExpr())) {
2197 if (Arg.getKind() == TemplateArgument::Integral)
2198 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2199 Arg.getAsIntegral(),
2200 Arg.getIntegralType(),
2201 /*ArrayBound=*/false,
2202 Info, Deduced);
2203 if (Arg.getKind() == TemplateArgument::NullPtr)
2204 return DeduceNullPtrTemplateArgument(S, TemplateParams, NTTP,
2205 Arg.getNullPtrType(),
2206 Info, Deduced);
2207 if (Arg.getKind() == TemplateArgument::Expression)
2208 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2209 Arg.getAsExpr(), Info, Deduced);
2210 if (Arg.getKind() == TemplateArgument::Declaration)
2211 return DeduceNonTypeTemplateArgument(S, TemplateParams, NTTP,
2212 Arg.getAsDecl(),
2213 Arg.getParamTypeForDecl(),
2214 Info, Deduced);
2215
2216 Info.FirstArg = Param;
2217 Info.SecondArg = Arg;
2218 return Sema::TDK_NonDeducedMismatch;
2219 }
2220
2221 // Can't deduce anything, but that's okay.
2222 return Sema::TDK_Success;
2223
2224 case TemplateArgument::Pack:
2225 llvm_unreachable("Argument packs should be expanded by the caller!");
2226 }
2227
2228 llvm_unreachable("Invalid TemplateArgument Kind!");
2229 }
2230
2231 /// Determine whether there is a template argument to be used for
2232 /// deduction.
2233 ///
2234 /// This routine "expands" argument packs in-place, overriding its input
2235 /// parameters so that \c Args[ArgIdx] will be the available template argument.
2236 ///
2237 /// \returns true if there is another template argument (which will be at
2238 /// \c Args[ArgIdx]), false otherwise.
hasTemplateArgumentForDeduction(ArrayRef<TemplateArgument> & Args,unsigned & ArgIdx)2239 static bool hasTemplateArgumentForDeduction(ArrayRef<TemplateArgument> &Args,
2240 unsigned &ArgIdx) {
2241 if (ArgIdx == Args.size())
2242 return false;
2243
2244 const TemplateArgument &Arg = Args[ArgIdx];
2245 if (Arg.getKind() != TemplateArgument::Pack)
2246 return true;
2247
2248 assert(ArgIdx == Args.size() - 1 && "Pack not at the end of argument list?");
2249 Args = Arg.pack_elements();
2250 ArgIdx = 0;
2251 return ArgIdx < Args.size();
2252 }
2253
2254 /// Determine whether the given set of template arguments has a pack
2255 /// expansion that is not the last template argument.
hasPackExpansionBeforeEnd(ArrayRef<TemplateArgument> Args)2256 static bool hasPackExpansionBeforeEnd(ArrayRef<TemplateArgument> Args) {
2257 bool FoundPackExpansion = false;
2258 for (const auto &A : Args) {
2259 if (FoundPackExpansion)
2260 return true;
2261
2262 if (A.getKind() == TemplateArgument::Pack)
2263 return hasPackExpansionBeforeEnd(A.pack_elements());
2264
2265 // FIXME: If this is a fixed-arity pack expansion from an outer level of
2266 // templates, it should not be treated as a pack expansion.
2267 if (A.isPackExpansion())
2268 FoundPackExpansion = true;
2269 }
2270
2271 return false;
2272 }
2273
2274 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,ArrayRef<TemplateArgument> Params,ArrayRef<TemplateArgument> Args,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced,bool NumberOfArgumentsMustMatch)2275 DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
2276 ArrayRef<TemplateArgument> Params,
2277 ArrayRef<TemplateArgument> Args,
2278 TemplateDeductionInfo &Info,
2279 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2280 bool NumberOfArgumentsMustMatch) {
2281 // C++0x [temp.deduct.type]p9:
2282 // If the template argument list of P contains a pack expansion that is not
2283 // the last template argument, the entire template argument list is a
2284 // non-deduced context.
2285 if (hasPackExpansionBeforeEnd(Params))
2286 return Sema::TDK_Success;
2287
2288 // C++0x [temp.deduct.type]p9:
2289 // If P has a form that contains <T> or <i>, then each argument Pi of the
2290 // respective template argument list P is compared with the corresponding
2291 // argument Ai of the corresponding template argument list of A.
2292 unsigned ArgIdx = 0, ParamIdx = 0;
2293 for (; hasTemplateArgumentForDeduction(Params, ParamIdx); ++ParamIdx) {
2294 if (!Params[ParamIdx].isPackExpansion()) {
2295 // The simple case: deduce template arguments by matching Pi and Ai.
2296
2297 // Check whether we have enough arguments.
2298 if (!hasTemplateArgumentForDeduction(Args, ArgIdx))
2299 return NumberOfArgumentsMustMatch
2300 ? Sema::TDK_MiscellaneousDeductionFailure
2301 : Sema::TDK_Success;
2302
2303 // C++1z [temp.deduct.type]p9:
2304 // During partial ordering, if Ai was originally a pack expansion [and]
2305 // Pi is not a pack expansion, template argument deduction fails.
2306 if (Args[ArgIdx].isPackExpansion())
2307 return Sema::TDK_MiscellaneousDeductionFailure;
2308
2309 // Perform deduction for this Pi/Ai pair.
2310 if (Sema::TemplateDeductionResult Result
2311 = DeduceTemplateArguments(S, TemplateParams,
2312 Params[ParamIdx], Args[ArgIdx],
2313 Info, Deduced))
2314 return Result;
2315
2316 // Move to the next argument.
2317 ++ArgIdx;
2318 continue;
2319 }
2320
2321 // The parameter is a pack expansion.
2322
2323 // C++0x [temp.deduct.type]p9:
2324 // If Pi is a pack expansion, then the pattern of Pi is compared with
2325 // each remaining argument in the template argument list of A. Each
2326 // comparison deduces template arguments for subsequent positions in the
2327 // template parameter packs expanded by Pi.
2328 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
2329
2330 // Prepare to deduce the packs within the pattern.
2331 PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
2332
2333 // Keep track of the deduced template arguments for each parameter pack
2334 // expanded by this pack expansion (the outer index) and for each
2335 // template argument (the inner SmallVectors).
2336 for (; hasTemplateArgumentForDeduction(Args, ArgIdx) &&
2337 PackScope.hasNextElement();
2338 ++ArgIdx) {
2339 // Deduce template arguments from the pattern.
2340 if (Sema::TemplateDeductionResult Result
2341 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
2342 Info, Deduced))
2343 return Result;
2344
2345 PackScope.nextPackElement();
2346 }
2347
2348 // Build argument packs for each of the parameter packs expanded by this
2349 // pack expansion.
2350 if (auto Result = PackScope.finish())
2351 return Result;
2352 }
2353
2354 return Sema::TDK_Success;
2355 }
2356
2357 static Sema::TemplateDeductionResult
DeduceTemplateArguments(Sema & S,TemplateParameterList * TemplateParams,const TemplateArgumentList & ParamList,const TemplateArgumentList & ArgList,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced)2358 DeduceTemplateArguments(Sema &S,
2359 TemplateParameterList *TemplateParams,
2360 const TemplateArgumentList &ParamList,
2361 const TemplateArgumentList &ArgList,
2362 TemplateDeductionInfo &Info,
2363 SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
2364 return DeduceTemplateArguments(S, TemplateParams, ParamList.asArray(),
2365 ArgList.asArray(), Info, Deduced,
2366 /*NumberOfArgumentsMustMatch*/false);
2367 }
2368
2369 /// Determine whether two template arguments are the same.
isSameTemplateArg(ASTContext & Context,TemplateArgument X,const TemplateArgument & Y,bool PackExpansionMatchesPack=false)2370 static bool isSameTemplateArg(ASTContext &Context,
2371 TemplateArgument X,
2372 const TemplateArgument &Y,
2373 bool PackExpansionMatchesPack = false) {
2374 // If we're checking deduced arguments (X) against original arguments (Y),
2375 // we will have flattened packs to non-expansions in X.
2376 if (PackExpansionMatchesPack && X.isPackExpansion() && !Y.isPackExpansion())
2377 X = X.getPackExpansionPattern();
2378
2379 if (X.getKind() != Y.getKind())
2380 return false;
2381
2382 switch (X.getKind()) {
2383 case TemplateArgument::Null:
2384 llvm_unreachable("Comparing NULL template argument");
2385
2386 case TemplateArgument::Type:
2387 return Context.getCanonicalType(X.getAsType()) ==
2388 Context.getCanonicalType(Y.getAsType());
2389
2390 case TemplateArgument::Declaration:
2391 return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
2392
2393 case TemplateArgument::NullPtr:
2394 return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
2395
2396 case TemplateArgument::Template:
2397 case TemplateArgument::TemplateExpansion:
2398 return Context.getCanonicalTemplateName(
2399 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
2400 Context.getCanonicalTemplateName(
2401 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
2402
2403 case TemplateArgument::Integral:
2404 return hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral());
2405
2406 case TemplateArgument::Expression: {
2407 llvm::FoldingSetNodeID XID, YID;
2408 X.getAsExpr()->Profile(XID, Context, true);
2409 Y.getAsExpr()->Profile(YID, Context, true);
2410 return XID == YID;
2411 }
2412
2413 case TemplateArgument::Pack:
2414 if (X.pack_size() != Y.pack_size())
2415 return false;
2416
2417 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
2418 XPEnd = X.pack_end(),
2419 YP = Y.pack_begin();
2420 XP != XPEnd; ++XP, ++YP)
2421 if (!isSameTemplateArg(Context, *XP, *YP, PackExpansionMatchesPack))
2422 return false;
2423
2424 return true;
2425 }
2426
2427 llvm_unreachable("Invalid TemplateArgument Kind!");
2428 }
2429
2430 /// Allocate a TemplateArgumentLoc where all locations have
2431 /// been initialized to the given location.
2432 ///
2433 /// \param Arg The template argument we are producing template argument
2434 /// location information for.
2435 ///
2436 /// \param NTTPType For a declaration template argument, the type of
2437 /// the non-type template parameter that corresponds to this template
2438 /// argument. Can be null if no type sugar is available to add to the
2439 /// type from the template argument.
2440 ///
2441 /// \param Loc The source location to use for the resulting template
2442 /// argument.
2443 TemplateArgumentLoc
getTrivialTemplateArgumentLoc(const TemplateArgument & Arg,QualType NTTPType,SourceLocation Loc)2444 Sema::getTrivialTemplateArgumentLoc(const TemplateArgument &Arg,
2445 QualType NTTPType, SourceLocation Loc) {
2446 switch (Arg.getKind()) {
2447 case TemplateArgument::Null:
2448 llvm_unreachable("Can't get a NULL template argument here");
2449
2450 case TemplateArgument::Type:
2451 return TemplateArgumentLoc(
2452 Arg, Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2453
2454 case TemplateArgument::Declaration: {
2455 if (NTTPType.isNull())
2456 NTTPType = Arg.getParamTypeForDecl();
2457 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2458 .getAs<Expr>();
2459 return TemplateArgumentLoc(TemplateArgument(E), E);
2460 }
2461
2462 case TemplateArgument::NullPtr: {
2463 if (NTTPType.isNull())
2464 NTTPType = Arg.getNullPtrType();
2465 Expr *E = BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2466 .getAs<Expr>();
2467 return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2468 E);
2469 }
2470
2471 case TemplateArgument::Integral: {
2472 Expr *E =
2473 BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2474 return TemplateArgumentLoc(TemplateArgument(E), E);
2475 }
2476
2477 case TemplateArgument::Template:
2478 case TemplateArgument::TemplateExpansion: {
2479 NestedNameSpecifierLocBuilder Builder;
2480 TemplateName Template = Arg.getAsTemplate();
2481 if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2482 Builder.MakeTrivial(Context, DTN->getQualifier(), Loc);
2483 else if (QualifiedTemplateName *QTN =
2484 Template.getAsQualifiedTemplateName())
2485 Builder.MakeTrivial(Context, QTN->getQualifier(), Loc);
2486
2487 if (Arg.getKind() == TemplateArgument::Template)
2488 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(Context),
2489 Loc);
2490
2491 return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(Context),
2492 Loc, Loc);
2493 }
2494
2495 case TemplateArgument::Expression:
2496 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2497
2498 case TemplateArgument::Pack:
2499 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2500 }
2501
2502 llvm_unreachable("Invalid TemplateArgument Kind!");
2503 }
2504
2505 /// Convert the given deduced template argument and add it to the set of
2506 /// fully-converted template arguments.
2507 static bool
ConvertDeducedTemplateArgument(Sema & S,NamedDecl * Param,DeducedTemplateArgument Arg,NamedDecl * Template,TemplateDeductionInfo & Info,bool IsDeduced,SmallVectorImpl<TemplateArgument> & Output)2508 ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2509 DeducedTemplateArgument Arg,
2510 NamedDecl *Template,
2511 TemplateDeductionInfo &Info,
2512 bool IsDeduced,
2513 SmallVectorImpl<TemplateArgument> &Output) {
2514 auto ConvertArg = [&](DeducedTemplateArgument Arg,
2515 unsigned ArgumentPackIndex) {
2516 // Convert the deduced template argument into a template
2517 // argument that we can check, almost as if the user had written
2518 // the template argument explicitly.
2519 TemplateArgumentLoc ArgLoc =
2520 S.getTrivialTemplateArgumentLoc(Arg, QualType(), Info.getLocation());
2521
2522 // Check the template argument, converting it as necessary.
2523 return S.CheckTemplateArgument(
2524 Param, ArgLoc, Template, Template->getLocation(),
2525 Template->getSourceRange().getEnd(), ArgumentPackIndex, Output,
2526 IsDeduced
2527 ? (Arg.wasDeducedFromArrayBound() ? Sema::CTAK_DeducedFromArrayBound
2528 : Sema::CTAK_Deduced)
2529 : Sema::CTAK_Specified);
2530 };
2531
2532 if (Arg.getKind() == TemplateArgument::Pack) {
2533 // This is a template argument pack, so check each of its arguments against
2534 // the template parameter.
2535 SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2536 for (const auto &P : Arg.pack_elements()) {
2537 // When converting the deduced template argument, append it to the
2538 // general output list. We need to do this so that the template argument
2539 // checking logic has all of the prior template arguments available.
2540 DeducedTemplateArgument InnerArg(P);
2541 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2542 assert(InnerArg.getKind() != TemplateArgument::Pack &&
2543 "deduced nested pack");
2544 if (P.isNull()) {
2545 // We deduced arguments for some elements of this pack, but not for
2546 // all of them. This happens if we get a conditionally-non-deduced
2547 // context in a pack expansion (such as an overload set in one of the
2548 // arguments).
2549 S.Diag(Param->getLocation(),
2550 diag::err_template_arg_deduced_incomplete_pack)
2551 << Arg << Param;
2552 return true;
2553 }
2554 if (ConvertArg(InnerArg, PackedArgsBuilder.size()))
2555 return true;
2556
2557 // Move the converted template argument into our argument pack.
2558 PackedArgsBuilder.push_back(Output.pop_back_val());
2559 }
2560
2561 // If the pack is empty, we still need to substitute into the parameter
2562 // itself, in case that substitution fails.
2563 if (PackedArgsBuilder.empty()) {
2564 LocalInstantiationScope Scope(S);
2565 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack, Output);
2566 MultiLevelTemplateArgumentList Args(TemplateArgs);
2567
2568 if (auto *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2569 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2570 NTTP, Output,
2571 Template->getSourceRange());
2572 if (Inst.isInvalid() ||
2573 S.SubstType(NTTP->getType(), Args, NTTP->getLocation(),
2574 NTTP->getDeclName()).isNull())
2575 return true;
2576 } else if (auto *TTP = dyn_cast<TemplateTemplateParmDecl>(Param)) {
2577 Sema::InstantiatingTemplate Inst(S, Template->getLocation(), Template,
2578 TTP, Output,
2579 Template->getSourceRange());
2580 if (Inst.isInvalid() || !S.SubstDecl(TTP, S.CurContext, Args))
2581 return true;
2582 }
2583 // For type parameters, no substitution is ever required.
2584 }
2585
2586 // Create the resulting argument pack.
2587 Output.push_back(
2588 TemplateArgument::CreatePackCopy(S.Context, PackedArgsBuilder));
2589 return false;
2590 }
2591
2592 return ConvertArg(Arg, 0);
2593 }
2594
2595 // FIXME: This should not be a template, but
2596 // ClassTemplatePartialSpecializationDecl sadly does not derive from
2597 // TemplateDecl.
2598 template<typename TemplateDeclT>
ConvertDeducedTemplateArguments(Sema & S,TemplateDeclT * Template,bool IsDeduced,SmallVectorImpl<DeducedTemplateArgument> & Deduced,TemplateDeductionInfo & Info,SmallVectorImpl<TemplateArgument> & Builder,LocalInstantiationScope * CurrentInstantiationScope=nullptr,unsigned NumAlreadyConverted=0,bool PartialOverloading=false)2599 static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments(
2600 Sema &S, TemplateDeclT *Template, bool IsDeduced,
2601 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2602 TemplateDeductionInfo &Info, SmallVectorImpl<TemplateArgument> &Builder,
2603 LocalInstantiationScope *CurrentInstantiationScope = nullptr,
2604 unsigned NumAlreadyConverted = 0, bool PartialOverloading = false) {
2605 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2606
2607 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2608 NamedDecl *Param = TemplateParams->getParam(I);
2609
2610 // C++0x [temp.arg.explicit]p3:
2611 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2612 // be deduced to an empty sequence of template arguments.
2613 // FIXME: Where did the word "trailing" come from?
2614 if (Deduced[I].isNull() && Param->isTemplateParameterPack()) {
2615 if (auto Result = PackDeductionScope(S, TemplateParams, Deduced, Info, I)
2616 .finish(/*TreatNoDeductionsAsNonDeduced*/false))
2617 return Result;
2618 }
2619
2620 if (!Deduced[I].isNull()) {
2621 if (I < NumAlreadyConverted) {
2622 // We may have had explicitly-specified template arguments for a
2623 // template parameter pack (that may or may not have been extended
2624 // via additional deduced arguments).
2625 if (Param->isParameterPack() && CurrentInstantiationScope &&
2626 CurrentInstantiationScope->getPartiallySubstitutedPack() == Param) {
2627 // Forget the partially-substituted pack; its substitution is now
2628 // complete.
2629 CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2630 // We still need to check the argument in case it was extended by
2631 // deduction.
2632 } else {
2633 // We have already fully type-checked and converted this
2634 // argument, because it was explicitly-specified. Just record the
2635 // presence of this argument.
2636 Builder.push_back(Deduced[I]);
2637 continue;
2638 }
2639 }
2640
2641 // We may have deduced this argument, so it still needs to be
2642 // checked and converted.
2643 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Template, Info,
2644 IsDeduced, Builder)) {
2645 Info.Param = makeTemplateParameter(Param);
2646 // FIXME: These template arguments are temporary. Free them!
2647 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2648 return Sema::TDK_SubstitutionFailure;
2649 }
2650
2651 continue;
2652 }
2653
2654 // Substitute into the default template argument, if available.
2655 bool HasDefaultArg = false;
2656 TemplateDecl *TD = dyn_cast<TemplateDecl>(Template);
2657 if (!TD) {
2658 assert(isa<ClassTemplatePartialSpecializationDecl>(Template) ||
2659 isa<VarTemplatePartialSpecializationDecl>(Template));
2660 return Sema::TDK_Incomplete;
2661 }
2662
2663 TemplateArgumentLoc DefArg = S.SubstDefaultTemplateArgumentIfAvailable(
2664 TD, TD->getLocation(), TD->getSourceRange().getEnd(), Param, Builder,
2665 HasDefaultArg);
2666
2667 // If there was no default argument, deduction is incomplete.
2668 if (DefArg.getArgument().isNull()) {
2669 Info.Param = makeTemplateParameter(
2670 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2671 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2672 if (PartialOverloading) break;
2673
2674 return HasDefaultArg ? Sema::TDK_SubstitutionFailure
2675 : Sema::TDK_Incomplete;
2676 }
2677
2678 // Check whether we can actually use the default argument.
2679 if (S.CheckTemplateArgument(Param, DefArg, TD, TD->getLocation(),
2680 TD->getSourceRange().getEnd(), 0, Builder,
2681 Sema::CTAK_Specified)) {
2682 Info.Param = makeTemplateParameter(
2683 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2684 // FIXME: These template arguments are temporary. Free them!
2685 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder));
2686 return Sema::TDK_SubstitutionFailure;
2687 }
2688
2689 // If we get here, we successfully used the default template argument.
2690 }
2691
2692 return Sema::TDK_Success;
2693 }
2694
getAsDeclContextOrEnclosing(Decl * D)2695 static DeclContext *getAsDeclContextOrEnclosing(Decl *D) {
2696 if (auto *DC = dyn_cast<DeclContext>(D))
2697 return DC;
2698 return D->getDeclContext();
2699 }
2700
2701 template<typename T> struct IsPartialSpecialization {
2702 static constexpr bool value = false;
2703 };
2704 template<>
2705 struct IsPartialSpecialization<ClassTemplatePartialSpecializationDecl> {
2706 static constexpr bool value = true;
2707 };
2708 template<>
2709 struct IsPartialSpecialization<VarTemplatePartialSpecializationDecl> {
2710 static constexpr bool value = true;
2711 };
2712
2713 /// Complete template argument deduction for a partial specialization.
2714 template <typename T>
2715 static typename std::enable_if<IsPartialSpecialization<T>::value,
2716 Sema::TemplateDeductionResult>::type
FinishTemplateArgumentDeduction(Sema & S,T * Partial,bool IsPartialOrdering,const TemplateArgumentList & TemplateArgs,SmallVectorImpl<DeducedTemplateArgument> & Deduced,TemplateDeductionInfo & Info)2717 FinishTemplateArgumentDeduction(
2718 Sema &S, T *Partial, bool IsPartialOrdering,
2719 const TemplateArgumentList &TemplateArgs,
2720 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2721 TemplateDeductionInfo &Info) {
2722 // Unevaluated SFINAE context.
2723 EnterExpressionEvaluationContext Unevaluated(
2724 S, Sema::ExpressionEvaluationContext::Unevaluated);
2725 Sema::SFINAETrap Trap(S);
2726
2727 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Partial));
2728
2729 // C++ [temp.deduct.type]p2:
2730 // [...] or if any template argument remains neither deduced nor
2731 // explicitly specified, template argument deduction fails.
2732 SmallVector<TemplateArgument, 4> Builder;
2733 if (auto Result = ConvertDeducedTemplateArguments(
2734 S, Partial, IsPartialOrdering, Deduced, Info, Builder))
2735 return Result;
2736
2737 // Form the template argument list from the deduced template arguments.
2738 TemplateArgumentList *DeducedArgumentList
2739 = TemplateArgumentList::CreateCopy(S.Context, Builder);
2740
2741 Info.reset(DeducedArgumentList);
2742
2743 // Substitute the deduced template arguments into the template
2744 // arguments of the class template partial specialization, and
2745 // verify that the instantiated template arguments are both valid
2746 // and are equivalent to the template arguments originally provided
2747 // to the class template.
2748 LocalInstantiationScope InstScope(S);
2749 auto *Template = Partial->getSpecializedTemplate();
2750 const ASTTemplateArgumentListInfo *PartialTemplArgInfo =
2751 Partial->getTemplateArgsAsWritten();
2752 const TemplateArgumentLoc *PartialTemplateArgs =
2753 PartialTemplArgInfo->getTemplateArgs();
2754
2755 TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2756 PartialTemplArgInfo->RAngleLoc);
2757
2758 if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2759 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2760 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2761 if (ParamIdx >= Partial->getTemplateParameters()->size())
2762 ParamIdx = Partial->getTemplateParameters()->size() - 1;
2763
2764 Decl *Param = const_cast<NamedDecl *>(
2765 Partial->getTemplateParameters()->getParam(ParamIdx));
2766 Info.Param = makeTemplateParameter(Param);
2767 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2768 return Sema::TDK_SubstitutionFailure;
2769 }
2770
2771 SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2772 if (S.CheckTemplateArgumentList(Template, Partial->getLocation(), InstArgs,
2773 false, ConvertedInstArgs))
2774 return Sema::TDK_SubstitutionFailure;
2775
2776 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2777 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2778 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2779 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2780 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2781 Info.FirstArg = TemplateArgs[I];
2782 Info.SecondArg = InstArg;
2783 return Sema::TDK_NonDeducedMismatch;
2784 }
2785 }
2786
2787 if (Trap.hasErrorOccurred())
2788 return Sema::TDK_SubstitutionFailure;
2789
2790 return Sema::TDK_Success;
2791 }
2792
2793 /// Complete template argument deduction for a class or variable template,
2794 /// when partial ordering against a partial specialization.
2795 // FIXME: Factor out duplication with partial specialization version above.
FinishTemplateArgumentDeduction(Sema & S,TemplateDecl * Template,bool PartialOrdering,const TemplateArgumentList & TemplateArgs,SmallVectorImpl<DeducedTemplateArgument> & Deduced,TemplateDeductionInfo & Info)2796 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2797 Sema &S, TemplateDecl *Template, bool PartialOrdering,
2798 const TemplateArgumentList &TemplateArgs,
2799 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2800 TemplateDeductionInfo &Info) {
2801 // Unevaluated SFINAE context.
2802 EnterExpressionEvaluationContext Unevaluated(
2803 S, Sema::ExpressionEvaluationContext::Unevaluated);
2804 Sema::SFINAETrap Trap(S);
2805
2806 Sema::ContextRAII SavedContext(S, getAsDeclContextOrEnclosing(Template));
2807
2808 // C++ [temp.deduct.type]p2:
2809 // [...] or if any template argument remains neither deduced nor
2810 // explicitly specified, template argument deduction fails.
2811 SmallVector<TemplateArgument, 4> Builder;
2812 if (auto Result = ConvertDeducedTemplateArguments(
2813 S, Template, /*IsDeduced*/PartialOrdering, Deduced, Info, Builder))
2814 return Result;
2815
2816 // Check that we produced the correct argument list.
2817 TemplateParameterList *TemplateParams = Template->getTemplateParameters();
2818 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2819 TemplateArgument InstArg = Builder[I];
2820 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg,
2821 /*PackExpansionMatchesPack*/true)) {
2822 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2823 Info.FirstArg = TemplateArgs[I];
2824 Info.SecondArg = InstArg;
2825 return Sema::TDK_NonDeducedMismatch;
2826 }
2827 }
2828
2829 if (Trap.hasErrorOccurred())
2830 return Sema::TDK_SubstitutionFailure;
2831
2832 return Sema::TDK_Success;
2833 }
2834
2835
2836 /// Perform template argument deduction to determine whether
2837 /// the given template arguments match the given class template
2838 /// partial specialization per C++ [temp.class.spec.match].
2839 Sema::TemplateDeductionResult
DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl * Partial,const TemplateArgumentList & TemplateArgs,TemplateDeductionInfo & Info)2840 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2841 const TemplateArgumentList &TemplateArgs,
2842 TemplateDeductionInfo &Info) {
2843 if (Partial->isInvalidDecl())
2844 return TDK_Invalid;
2845
2846 // C++ [temp.class.spec.match]p2:
2847 // A partial specialization matches a given actual template
2848 // argument list if the template arguments of the partial
2849 // specialization can be deduced from the actual template argument
2850 // list (14.8.2).
2851
2852 // Unevaluated SFINAE context.
2853 EnterExpressionEvaluationContext Unevaluated(
2854 *this, Sema::ExpressionEvaluationContext::Unevaluated);
2855 SFINAETrap Trap(*this);
2856
2857 SmallVector<DeducedTemplateArgument, 4> Deduced;
2858 Deduced.resize(Partial->getTemplateParameters()->size());
2859 if (TemplateDeductionResult Result
2860 = ::DeduceTemplateArguments(*this,
2861 Partial->getTemplateParameters(),
2862 Partial->getTemplateArgs(),
2863 TemplateArgs, Info, Deduced))
2864 return Result;
2865
2866 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2867 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2868 Info);
2869 if (Inst.isInvalid())
2870 return TDK_InstantiationDepth;
2871
2872 if (Trap.hasErrorOccurred())
2873 return Sema::TDK_SubstitutionFailure;
2874
2875 return ::FinishTemplateArgumentDeduction(
2876 *this, Partial, /*PartialOrdering=*/false, TemplateArgs, Deduced, Info);
2877 }
2878
2879 /// Perform template argument deduction to determine whether
2880 /// the given template arguments match the given variable template
2881 /// partial specialization per C++ [temp.class.spec.match].
2882 Sema::TemplateDeductionResult
DeduceTemplateArguments(VarTemplatePartialSpecializationDecl * Partial,const TemplateArgumentList & TemplateArgs,TemplateDeductionInfo & Info)2883 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2884 const TemplateArgumentList &TemplateArgs,
2885 TemplateDeductionInfo &Info) {
2886 if (Partial->isInvalidDecl())
2887 return TDK_Invalid;
2888
2889 // C++ [temp.class.spec.match]p2:
2890 // A partial specialization matches a given actual template
2891 // argument list if the template arguments of the partial
2892 // specialization can be deduced from the actual template argument
2893 // list (14.8.2).
2894
2895 // Unevaluated SFINAE context.
2896 EnterExpressionEvaluationContext Unevaluated(
2897 *this, Sema::ExpressionEvaluationContext::Unevaluated);
2898 SFINAETrap Trap(*this);
2899
2900 SmallVector<DeducedTemplateArgument, 4> Deduced;
2901 Deduced.resize(Partial->getTemplateParameters()->size());
2902 if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2903 *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2904 TemplateArgs, Info, Deduced))
2905 return Result;
2906
2907 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2908 InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2909 Info);
2910 if (Inst.isInvalid())
2911 return TDK_InstantiationDepth;
2912
2913 if (Trap.hasErrorOccurred())
2914 return Sema::TDK_SubstitutionFailure;
2915
2916 return ::FinishTemplateArgumentDeduction(
2917 *this, Partial, /*PartialOrdering=*/false, TemplateArgs, Deduced, Info);
2918 }
2919
2920 /// Determine whether the given type T is a simple-template-id type.
isSimpleTemplateIdType(QualType T)2921 static bool isSimpleTemplateIdType(QualType T) {
2922 if (const TemplateSpecializationType *Spec
2923 = T->getAs<TemplateSpecializationType>())
2924 return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2925
2926 // C++17 [temp.local]p2:
2927 // the injected-class-name [...] is equivalent to the template-name followed
2928 // by the template-arguments of the class template specialization or partial
2929 // specialization enclosed in <>
2930 // ... which means it's equivalent to a simple-template-id.
2931 //
2932 // This only arises during class template argument deduction for a copy
2933 // deduction candidate, where it permits slicing.
2934 if (T->getAs<InjectedClassNameType>())
2935 return true;
2936
2937 return false;
2938 }
2939
2940 /// Substitute the explicitly-provided template arguments into the
2941 /// given function template according to C++ [temp.arg.explicit].
2942 ///
2943 /// \param FunctionTemplate the function template into which the explicit
2944 /// template arguments will be substituted.
2945 ///
2946 /// \param ExplicitTemplateArgs the explicitly-specified template
2947 /// arguments.
2948 ///
2949 /// \param Deduced the deduced template arguments, which will be populated
2950 /// with the converted and checked explicit template arguments.
2951 ///
2952 /// \param ParamTypes will be populated with the instantiated function
2953 /// parameters.
2954 ///
2955 /// \param FunctionType if non-NULL, the result type of the function template
2956 /// will also be instantiated and the pointed-to value will be updated with
2957 /// the instantiated function type.
2958 ///
2959 /// \param Info if substitution fails for any reason, this object will be
2960 /// populated with more information about the failure.
2961 ///
2962 /// \returns TDK_Success if substitution was successful, or some failure
2963 /// condition.
2964 Sema::TemplateDeductionResult
SubstituteExplicitTemplateArguments(FunctionTemplateDecl * FunctionTemplate,TemplateArgumentListInfo & ExplicitTemplateArgs,SmallVectorImpl<DeducedTemplateArgument> & Deduced,SmallVectorImpl<QualType> & ParamTypes,QualType * FunctionType,TemplateDeductionInfo & Info)2965 Sema::SubstituteExplicitTemplateArguments(
2966 FunctionTemplateDecl *FunctionTemplate,
2967 TemplateArgumentListInfo &ExplicitTemplateArgs,
2968 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2969 SmallVectorImpl<QualType> &ParamTypes,
2970 QualType *FunctionType,
2971 TemplateDeductionInfo &Info) {
2972 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2973 TemplateParameterList *TemplateParams
2974 = FunctionTemplate->getTemplateParameters();
2975
2976 if (ExplicitTemplateArgs.size() == 0) {
2977 // No arguments to substitute; just copy over the parameter types and
2978 // fill in the function type.
2979 for (auto P : Function->parameters())
2980 ParamTypes.push_back(P->getType());
2981
2982 if (FunctionType)
2983 *FunctionType = Function->getType();
2984 return TDK_Success;
2985 }
2986
2987 // Unevaluated SFINAE context.
2988 EnterExpressionEvaluationContext Unevaluated(
2989 *this, Sema::ExpressionEvaluationContext::Unevaluated);
2990 SFINAETrap Trap(*this);
2991
2992 // C++ [temp.arg.explicit]p3:
2993 // Template arguments that are present shall be specified in the
2994 // declaration order of their corresponding template-parameters. The
2995 // template argument list shall not specify more template-arguments than
2996 // there are corresponding template-parameters.
2997 SmallVector<TemplateArgument, 4> Builder;
2998
2999 // Enter a new template instantiation context where we check the
3000 // explicitly-specified template arguments against this function template,
3001 // and then substitute them into the function parameter types.
3002 SmallVector<TemplateArgument, 4> DeducedArgs;
3003 InstantiatingTemplate Inst(
3004 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3005 CodeSynthesisContext::ExplicitTemplateArgumentSubstitution, Info);
3006 if (Inst.isInvalid())
3007 return TDK_InstantiationDepth;
3008
3009 if (CheckTemplateArgumentList(FunctionTemplate, SourceLocation(),
3010 ExplicitTemplateArgs, true, Builder, false) ||
3011 Trap.hasErrorOccurred()) {
3012 unsigned Index = Builder.size();
3013 if (Index >= TemplateParams->size())
3014 return TDK_SubstitutionFailure;
3015 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
3016 return TDK_InvalidExplicitArguments;
3017 }
3018
3019 // Form the template argument list from the explicitly-specified
3020 // template arguments.
3021 TemplateArgumentList *ExplicitArgumentList
3022 = TemplateArgumentList::CreateCopy(Context, Builder);
3023 Info.setExplicitArgs(ExplicitArgumentList);
3024
3025 // Template argument deduction and the final substitution should be
3026 // done in the context of the templated declaration. Explicit
3027 // argument substitution, on the other hand, needs to happen in the
3028 // calling context.
3029 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3030
3031 // If we deduced template arguments for a template parameter pack,
3032 // note that the template argument pack is partially substituted and record
3033 // the explicit template arguments. They'll be used as part of deduction
3034 // for this template parameter pack.
3035 unsigned PartiallySubstitutedPackIndex = -1u;
3036 if (!Builder.empty()) {
3037 const TemplateArgument &Arg = Builder.back();
3038 if (Arg.getKind() == TemplateArgument::Pack) {
3039 auto *Param = TemplateParams->getParam(Builder.size() - 1);
3040 // If this is a fully-saturated fixed-size pack, it should be
3041 // fully-substituted, not partially-substituted.
3042 Optional<unsigned> Expansions = getExpandedPackSize(Param);
3043 if (!Expansions || Arg.pack_size() < *Expansions) {
3044 PartiallySubstitutedPackIndex = Builder.size() - 1;
3045 CurrentInstantiationScope->SetPartiallySubstitutedPack(
3046 Param, Arg.pack_begin(), Arg.pack_size());
3047 }
3048 }
3049 }
3050
3051 const FunctionProtoType *Proto
3052 = Function->getType()->getAs<FunctionProtoType>();
3053 assert(Proto && "Function template does not have a prototype?");
3054
3055 // Isolate our substituted parameters from our caller.
3056 LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
3057
3058 ExtParameterInfoBuilder ExtParamInfos;
3059
3060 // Instantiate the types of each of the function parameters given the
3061 // explicitly-specified template arguments. If the function has a trailing
3062 // return type, substitute it after the arguments to ensure we substitute
3063 // in lexical order.
3064 if (Proto->hasTrailingReturn()) {
3065 if (SubstParmTypes(Function->getLocation(), Function->parameters(),
3066 Proto->getExtParameterInfosOrNull(),
3067 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3068 ParamTypes, /*params*/ nullptr, ExtParamInfos))
3069 return TDK_SubstitutionFailure;
3070 }
3071
3072 // Instantiate the return type.
3073 QualType ResultType;
3074 {
3075 // C++11 [expr.prim.general]p3:
3076 // If a declaration declares a member function or member function
3077 // template of a class X, the expression this is a prvalue of type
3078 // "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
3079 // and the end of the function-definition, member-declarator, or
3080 // declarator.
3081 Qualifiers ThisTypeQuals;
3082 CXXRecordDecl *ThisContext = nullptr;
3083 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
3084 ThisContext = Method->getParent();
3085 ThisTypeQuals = Method->getTypeQualifiers();
3086 }
3087
3088 CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
3089 getLangOpts().CPlusPlus11);
3090
3091 ResultType =
3092 SubstType(Proto->getReturnType(),
3093 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3094 Function->getTypeSpecStartLoc(), Function->getDeclName());
3095 if (ResultType.isNull() || Trap.hasErrorOccurred())
3096 return TDK_SubstitutionFailure;
3097 }
3098
3099 // Instantiate the types of each of the function parameters given the
3100 // explicitly-specified template arguments if we didn't do so earlier.
3101 if (!Proto->hasTrailingReturn() &&
3102 SubstParmTypes(Function->getLocation(), Function->parameters(),
3103 Proto->getExtParameterInfosOrNull(),
3104 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
3105 ParamTypes, /*params*/ nullptr, ExtParamInfos))
3106 return TDK_SubstitutionFailure;
3107
3108 if (FunctionType) {
3109 auto EPI = Proto->getExtProtoInfo();
3110 EPI.ExtParameterInfos = ExtParamInfos.getPointerOrNull(ParamTypes.size());
3111
3112 // In C++1z onwards, exception specifications are part of the function type,
3113 // so substitution into the type must also substitute into the exception
3114 // specification.
3115 SmallVector<QualType, 4> ExceptionStorage;
3116 if (getLangOpts().CPlusPlus17 &&
3117 SubstExceptionSpec(
3118 Function->getLocation(), EPI.ExceptionSpec, ExceptionStorage,
3119 MultiLevelTemplateArgumentList(*ExplicitArgumentList)))
3120 return TDK_SubstitutionFailure;
3121
3122 *FunctionType = BuildFunctionType(ResultType, ParamTypes,
3123 Function->getLocation(),
3124 Function->getDeclName(),
3125 EPI);
3126 if (FunctionType->isNull() || Trap.hasErrorOccurred())
3127 return TDK_SubstitutionFailure;
3128 }
3129
3130 // C++ [temp.arg.explicit]p2:
3131 // Trailing template arguments that can be deduced (14.8.2) may be
3132 // omitted from the list of explicit template-arguments. If all of the
3133 // template arguments can be deduced, they may all be omitted; in this
3134 // case, the empty template argument list <> itself may also be omitted.
3135 //
3136 // Take all of the explicitly-specified arguments and put them into
3137 // the set of deduced template arguments. The partially-substituted
3138 // parameter pack, however, will be set to NULL since the deduction
3139 // mechanism handles the partially-substituted argument pack directly.
3140 Deduced.reserve(TemplateParams->size());
3141 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
3142 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
3143 if (I == PartiallySubstitutedPackIndex)
3144 Deduced.push_back(DeducedTemplateArgument());
3145 else
3146 Deduced.push_back(Arg);
3147 }
3148
3149 return TDK_Success;
3150 }
3151
3152 /// Check whether the deduced argument type for a call to a function
3153 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
3154 static Sema::TemplateDeductionResult
CheckOriginalCallArgDeduction(Sema & S,TemplateDeductionInfo & Info,Sema::OriginalCallArg OriginalArg,QualType DeducedA)3155 CheckOriginalCallArgDeduction(Sema &S, TemplateDeductionInfo &Info,
3156 Sema::OriginalCallArg OriginalArg,
3157 QualType DeducedA) {
3158 ASTContext &Context = S.Context;
3159
3160 auto Failed = [&]() -> Sema::TemplateDeductionResult {
3161 Info.FirstArg = TemplateArgument(DeducedA);
3162 Info.SecondArg = TemplateArgument(OriginalArg.OriginalArgType);
3163 Info.CallArgIndex = OriginalArg.ArgIdx;
3164 return OriginalArg.DecomposedParam ? Sema::TDK_DeducedMismatchNested
3165 : Sema::TDK_DeducedMismatch;
3166 };
3167
3168 QualType A = OriginalArg.OriginalArgType;
3169 QualType OriginalParamType = OriginalArg.OriginalParamType;
3170
3171 // Check for type equality (top-level cv-qualifiers are ignored).
3172 if (Context.hasSameUnqualifiedType(A, DeducedA))
3173 return Sema::TDK_Success;
3174
3175 // Strip off references on the argument types; they aren't needed for
3176 // the following checks.
3177 if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
3178 DeducedA = DeducedARef->getPointeeType();
3179 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3180 A = ARef->getPointeeType();
3181
3182 // C++ [temp.deduct.call]p4:
3183 // [...] However, there are three cases that allow a difference:
3184 // - If the original P is a reference type, the deduced A (i.e., the
3185 // type referred to by the reference) can be more cv-qualified than
3186 // the transformed A.
3187 if (const ReferenceType *OriginalParamRef
3188 = OriginalParamType->getAs<ReferenceType>()) {
3189 // We don't want to keep the reference around any more.
3190 OriginalParamType = OriginalParamRef->getPointeeType();
3191
3192 // FIXME: Resolve core issue (no number yet): if the original P is a
3193 // reference type and the transformed A is function type "noexcept F",
3194 // the deduced A can be F.
3195 QualType Tmp;
3196 if (A->isFunctionType() && S.IsFunctionConversion(A, DeducedA, Tmp))
3197 return Sema::TDK_Success;
3198
3199 Qualifiers AQuals = A.getQualifiers();
3200 Qualifiers DeducedAQuals = DeducedA.getQualifiers();
3201
3202 // Under Objective-C++ ARC, the deduced type may have implicitly
3203 // been given strong or (when dealing with a const reference)
3204 // unsafe_unretained lifetime. If so, update the original
3205 // qualifiers to include this lifetime.
3206 if (S.getLangOpts().ObjCAutoRefCount &&
3207 ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
3208 AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
3209 (DeducedAQuals.hasConst() &&
3210 DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
3211 AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
3212 }
3213
3214 if (AQuals == DeducedAQuals) {
3215 // Qualifiers match; there's nothing to do.
3216 } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
3217 return Failed();
3218 } else {
3219 // Qualifiers are compatible, so have the argument type adopt the
3220 // deduced argument type's qualifiers as if we had performed the
3221 // qualification conversion.
3222 A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
3223 }
3224 }
3225
3226 // - The transformed A can be another pointer or pointer to member
3227 // type that can be converted to the deduced A via a function pointer
3228 // conversion and/or a qualification conversion.
3229 //
3230 // Also allow conversions which merely strip __attribute__((noreturn)) from
3231 // function types (recursively).
3232 bool ObjCLifetimeConversion = false;
3233 QualType ResultTy;
3234 if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
3235 (S.IsQualificationConversion(A, DeducedA, false,
3236 ObjCLifetimeConversion) ||
3237 S.IsFunctionConversion(A, DeducedA, ResultTy)))
3238 return Sema::TDK_Success;
3239
3240 // - If P is a class and P has the form simple-template-id, then the
3241 // transformed A can be a derived class of the deduced A. [...]
3242 // [...] Likewise, if P is a pointer to a class of the form
3243 // simple-template-id, the transformed A can be a pointer to a
3244 // derived class pointed to by the deduced A.
3245 if (const PointerType *OriginalParamPtr
3246 = OriginalParamType->getAs<PointerType>()) {
3247 if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
3248 if (const PointerType *APtr = A->getAs<PointerType>()) {
3249 if (A->getPointeeType()->isRecordType()) {
3250 OriginalParamType = OriginalParamPtr->getPointeeType();
3251 DeducedA = DeducedAPtr->getPointeeType();
3252 A = APtr->getPointeeType();
3253 }
3254 }
3255 }
3256 }
3257
3258 if (Context.hasSameUnqualifiedType(A, DeducedA))
3259 return Sema::TDK_Success;
3260
3261 if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
3262 S.IsDerivedFrom(Info.getLocation(), A, DeducedA))
3263 return Sema::TDK_Success;
3264
3265 return Failed();
3266 }
3267
3268 /// Find the pack index for a particular parameter index in an instantiation of
3269 /// a function template with specific arguments.
3270 ///
3271 /// \return The pack index for whichever pack produced this parameter, or -1
3272 /// if this was not produced by a parameter. Intended to be used as the
3273 /// ArgumentPackSubstitutionIndex for further substitutions.
3274 // FIXME: We should track this in OriginalCallArgs so we don't need to
3275 // reconstruct it here.
getPackIndexForParam(Sema & S,FunctionTemplateDecl * FunctionTemplate,const MultiLevelTemplateArgumentList & Args,unsigned ParamIdx)3276 static unsigned getPackIndexForParam(Sema &S,
3277 FunctionTemplateDecl *FunctionTemplate,
3278 const MultiLevelTemplateArgumentList &Args,
3279 unsigned ParamIdx) {
3280 unsigned Idx = 0;
3281 for (auto *PD : FunctionTemplate->getTemplatedDecl()->parameters()) {
3282 if (PD->isParameterPack()) {
3283 unsigned NumExpansions =
3284 S.getNumArgumentsInExpansion(PD->getType(), Args).getValueOr(1);
3285 if (Idx + NumExpansions > ParamIdx)
3286 return ParamIdx - Idx;
3287 Idx += NumExpansions;
3288 } else {
3289 if (Idx == ParamIdx)
3290 return -1; // Not a pack expansion
3291 ++Idx;
3292 }
3293 }
3294
3295 llvm_unreachable("parameter index would not be produced from template");
3296 }
3297
3298 /// Finish template argument deduction for a function template,
3299 /// checking the deduced template arguments for completeness and forming
3300 /// the function template specialization.
3301 ///
3302 /// \param OriginalCallArgs If non-NULL, the original call arguments against
3303 /// which the deduced argument types should be compared.
FinishTemplateArgumentDeduction(FunctionTemplateDecl * FunctionTemplate,SmallVectorImpl<DeducedTemplateArgument> & Deduced,unsigned NumExplicitlySpecified,FunctionDecl * & Specialization,TemplateDeductionInfo & Info,SmallVectorImpl<OriginalCallArg> const * OriginalCallArgs,bool PartialOverloading,llvm::function_ref<bool ()> CheckNonDependent)3304 Sema::TemplateDeductionResult Sema::FinishTemplateArgumentDeduction(
3305 FunctionTemplateDecl *FunctionTemplate,
3306 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3307 unsigned NumExplicitlySpecified, FunctionDecl *&Specialization,
3308 TemplateDeductionInfo &Info,
3309 SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
3310 bool PartialOverloading, llvm::function_ref<bool()> CheckNonDependent) {
3311 // Unevaluated SFINAE context.
3312 EnterExpressionEvaluationContext Unevaluated(
3313 *this, Sema::ExpressionEvaluationContext::Unevaluated);
3314 SFINAETrap Trap(*this);
3315
3316 // Enter a new template instantiation context while we instantiate the
3317 // actual function declaration.
3318 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
3319 InstantiatingTemplate Inst(
3320 *this, Info.getLocation(), FunctionTemplate, DeducedArgs,
3321 CodeSynthesisContext::DeducedTemplateArgumentSubstitution, Info);
3322 if (Inst.isInvalid())
3323 return TDK_InstantiationDepth;
3324
3325 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
3326
3327 // C++ [temp.deduct.type]p2:
3328 // [...] or if any template argument remains neither deduced nor
3329 // explicitly specified, template argument deduction fails.
3330 SmallVector<TemplateArgument, 4> Builder;
3331 if (auto Result = ConvertDeducedTemplateArguments(
3332 *this, FunctionTemplate, /*IsDeduced*/true, Deduced, Info, Builder,
3333 CurrentInstantiationScope, NumExplicitlySpecified,
3334 PartialOverloading))
3335 return Result;
3336
3337 // C++ [temp.deduct.call]p10: [DR1391]
3338 // If deduction succeeds for all parameters that contain
3339 // template-parameters that participate in template argument deduction,
3340 // and all template arguments are explicitly specified, deduced, or
3341 // obtained from default template arguments, remaining parameters are then
3342 // compared with the corresponding arguments. For each remaining parameter
3343 // P with a type that was non-dependent before substitution of any
3344 // explicitly-specified template arguments, if the corresponding argument
3345 // A cannot be implicitly converted to P, deduction fails.
3346 if (CheckNonDependent())
3347 return TDK_NonDependentConversionFailure;
3348
3349 // Form the template argument list from the deduced template arguments.
3350 TemplateArgumentList *DeducedArgumentList
3351 = TemplateArgumentList::CreateCopy(Context, Builder);
3352 Info.reset(DeducedArgumentList);
3353
3354 // Substitute the deduced template arguments into the function template
3355 // declaration to produce the function template specialization.
3356 DeclContext *Owner = FunctionTemplate->getDeclContext();
3357 if (FunctionTemplate->getFriendObjectKind())
3358 Owner = FunctionTemplate->getLexicalDeclContext();
3359 MultiLevelTemplateArgumentList SubstArgs(*DeducedArgumentList);
3360 Specialization = cast_or_null<FunctionDecl>(
3361 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner, SubstArgs));
3362 if (!Specialization || Specialization->isInvalidDecl())
3363 return TDK_SubstitutionFailure;
3364
3365 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
3366 FunctionTemplate->getCanonicalDecl());
3367
3368 // If the template argument list is owned by the function template
3369 // specialization, release it.
3370 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
3371 !Trap.hasErrorOccurred())
3372 Info.take();
3373
3374 // There may have been an error that did not prevent us from constructing a
3375 // declaration. Mark the declaration invalid and return with a substitution
3376 // failure.
3377 if (Trap.hasErrorOccurred()) {
3378 Specialization->setInvalidDecl(true);
3379 return TDK_SubstitutionFailure;
3380 }
3381
3382 if (OriginalCallArgs) {
3383 // C++ [temp.deduct.call]p4:
3384 // In general, the deduction process attempts to find template argument
3385 // values that will make the deduced A identical to A (after the type A
3386 // is transformed as described above). [...]
3387 llvm::SmallDenseMap<std::pair<unsigned, QualType>, QualType> DeducedATypes;
3388 for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
3389 OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
3390
3391 auto ParamIdx = OriginalArg.ArgIdx;
3392 if (ParamIdx >= Specialization->getNumParams())
3393 // FIXME: This presumably means a pack ended up smaller than we
3394 // expected while deducing. Should this not result in deduction
3395 // failure? Can it even happen?
3396 continue;
3397
3398 QualType DeducedA;
3399 if (!OriginalArg.DecomposedParam) {
3400 // P is one of the function parameters, just look up its substituted
3401 // type.
3402 DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
3403 } else {
3404 // P is a decomposed element of a parameter corresponding to a
3405 // braced-init-list argument. Substitute back into P to find the
3406 // deduced A.
3407 QualType &CacheEntry =
3408 DeducedATypes[{ParamIdx, OriginalArg.OriginalParamType}];
3409 if (CacheEntry.isNull()) {
3410 ArgumentPackSubstitutionIndexRAII PackIndex(
3411 *this, getPackIndexForParam(*this, FunctionTemplate, SubstArgs,
3412 ParamIdx));
3413 CacheEntry =
3414 SubstType(OriginalArg.OriginalParamType, SubstArgs,
3415 Specialization->getTypeSpecStartLoc(),
3416 Specialization->getDeclName());
3417 }
3418 DeducedA = CacheEntry;
3419 }
3420
3421 if (auto TDK =
3422 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA))
3423 return TDK;
3424 }
3425 }
3426
3427 // If we suppressed any diagnostics while performing template argument
3428 // deduction, and if we haven't already instantiated this declaration,
3429 // keep track of these diagnostics. They'll be emitted if this specialization
3430 // is actually used.
3431 if (Info.diag_begin() != Info.diag_end()) {
3432 SuppressedDiagnosticsMap::iterator
3433 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
3434 if (Pos == SuppressedDiagnostics.end())
3435 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
3436 .append(Info.diag_begin(), Info.diag_end());
3437 }
3438
3439 return TDK_Success;
3440 }
3441
3442 /// Gets the type of a function for template-argument-deducton
3443 /// purposes when it's considered as part of an overload set.
GetTypeOfFunction(Sema & S,const OverloadExpr::FindResult & R,FunctionDecl * Fn)3444 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
3445 FunctionDecl *Fn) {
3446 // We may need to deduce the return type of the function now.
3447 if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
3448 S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
3449 return {};
3450
3451 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
3452 if (Method->isInstance()) {
3453 // An instance method that's referenced in a form that doesn't
3454 // look like a member pointer is just invalid.
3455 if (!R.HasFormOfMemberPointer)
3456 return {};
3457
3458 return S.Context.getMemberPointerType(Fn->getType(),
3459 S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
3460 }
3461
3462 if (!R.IsAddressOfOperand) return Fn->getType();
3463 return S.Context.getPointerType(Fn->getType());
3464 }
3465
3466 /// Apply the deduction rules for overload sets.
3467 ///
3468 /// \return the null type if this argument should be treated as an
3469 /// undeduced context
3470 static QualType
ResolveOverloadForDeduction(Sema & S,TemplateParameterList * TemplateParams,Expr * Arg,QualType ParamType,bool ParamWasReference)3471 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
3472 Expr *Arg, QualType ParamType,
3473 bool ParamWasReference) {
3474
3475 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3476
3477 OverloadExpr *Ovl = R.Expression;
3478
3479 // C++0x [temp.deduct.call]p4
3480 unsigned TDF = 0;
3481 if (ParamWasReference)
3482 TDF |= TDF_ParamWithReferenceType;
3483 if (R.IsAddressOfOperand)
3484 TDF |= TDF_IgnoreQualifiers;
3485
3486 // C++0x [temp.deduct.call]p6:
3487 // When P is a function type, pointer to function type, or pointer
3488 // to member function type:
3489
3490 if (!ParamType->isFunctionType() &&
3491 !ParamType->isFunctionPointerType() &&
3492 !ParamType->isMemberFunctionPointerType()) {
3493 if (Ovl->hasExplicitTemplateArgs()) {
3494 // But we can still look for an explicit specialization.
3495 if (FunctionDecl *ExplicitSpec
3496 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3497 return GetTypeOfFunction(S, R, ExplicitSpec);
3498 }
3499
3500 DeclAccessPair DAP;
3501 if (FunctionDecl *Viable =
3502 S.resolveAddressOfOnlyViableOverloadCandidate(Arg, DAP))
3503 return GetTypeOfFunction(S, R, Viable);
3504
3505 return {};
3506 }
3507
3508 // Gather the explicit template arguments, if any.
3509 TemplateArgumentListInfo ExplicitTemplateArgs;
3510 if (Ovl->hasExplicitTemplateArgs())
3511 Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3512 QualType Match;
3513 for (UnresolvedSetIterator I = Ovl->decls_begin(),
3514 E = Ovl->decls_end(); I != E; ++I) {
3515 NamedDecl *D = (*I)->getUnderlyingDecl();
3516
3517 if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3518 // - If the argument is an overload set containing one or more
3519 // function templates, the parameter is treated as a
3520 // non-deduced context.
3521 if (!Ovl->hasExplicitTemplateArgs())
3522 return {};
3523
3524 // Otherwise, see if we can resolve a function type
3525 FunctionDecl *Specialization = nullptr;
3526 TemplateDeductionInfo Info(Ovl->getNameLoc());
3527 if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3528 Specialization, Info))
3529 continue;
3530
3531 D = Specialization;
3532 }
3533
3534 FunctionDecl *Fn = cast<FunctionDecl>(D);
3535 QualType ArgType = GetTypeOfFunction(S, R, Fn);
3536 if (ArgType.isNull()) continue;
3537
3538 // Function-to-pointer conversion.
3539 if (!ParamWasReference && ParamType->isPointerType() &&
3540 ArgType->isFunctionType())
3541 ArgType = S.Context.getPointerType(ArgType);
3542
3543 // - If the argument is an overload set (not containing function
3544 // templates), trial argument deduction is attempted using each
3545 // of the members of the set. If deduction succeeds for only one
3546 // of the overload set members, that member is used as the
3547 // argument value for the deduction. If deduction succeeds for
3548 // more than one member of the overload set the parameter is
3549 // treated as a non-deduced context.
3550
3551 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3552 // Type deduction is done independently for each P/A pair, and
3553 // the deduced template argument values are then combined.
3554 // So we do not reject deductions which were made elsewhere.
3555 SmallVector<DeducedTemplateArgument, 8>
3556 Deduced(TemplateParams->size());
3557 TemplateDeductionInfo Info(Ovl->getNameLoc());
3558 Sema::TemplateDeductionResult Result
3559 = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3560 ArgType, Info, Deduced, TDF);
3561 if (Result) continue;
3562 if (!Match.isNull())
3563 return {};
3564 Match = ArgType;
3565 }
3566
3567 return Match;
3568 }
3569
3570 /// Perform the adjustments to the parameter and argument types
3571 /// described in C++ [temp.deduct.call].
3572 ///
3573 /// \returns true if the caller should not attempt to perform any template
3574 /// argument deduction based on this P/A pair because the argument is an
3575 /// overloaded function set that could not be resolved.
AdjustFunctionParmAndArgTypesForDeduction(Sema & S,TemplateParameterList * TemplateParams,unsigned FirstInnerIndex,QualType & ParamType,QualType & ArgType,Expr * Arg,unsigned & TDF)3576 static bool AdjustFunctionParmAndArgTypesForDeduction(
3577 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3578 QualType &ParamType, QualType &ArgType, Expr *Arg, unsigned &TDF) {
3579 // C++0x [temp.deduct.call]p3:
3580 // If P is a cv-qualified type, the top level cv-qualifiers of P's type
3581 // are ignored for type deduction.
3582 if (ParamType.hasQualifiers())
3583 ParamType = ParamType.getUnqualifiedType();
3584
3585 // [...] If P is a reference type, the type referred to by P is
3586 // used for type deduction.
3587 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3588 if (ParamRefType)
3589 ParamType = ParamRefType->getPointeeType();
3590
3591 // Overload sets usually make this parameter an undeduced context,
3592 // but there are sometimes special circumstances. Typically
3593 // involving a template-id-expr.
3594 if (ArgType == S.Context.OverloadTy) {
3595 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3596 Arg, ParamType,
3597 ParamRefType != nullptr);
3598 if (ArgType.isNull())
3599 return true;
3600 }
3601
3602 if (ParamRefType) {
3603 // If the argument has incomplete array type, try to complete its type.
3604 if (ArgType->isIncompleteArrayType()) {
3605 S.completeExprArrayBound(Arg);
3606 ArgType = Arg->getType();
3607 }
3608
3609 // C++1z [temp.deduct.call]p3:
3610 // If P is a forwarding reference and the argument is an lvalue, the type
3611 // "lvalue reference to A" is used in place of A for type deduction.
3612 if (isForwardingReference(QualType(ParamRefType, 0), FirstInnerIndex) &&
3613 Arg->isLValue())
3614 ArgType = S.Context.getLValueReferenceType(ArgType);
3615 } else {
3616 // C++ [temp.deduct.call]p2:
3617 // If P is not a reference type:
3618 // - If A is an array type, the pointer type produced by the
3619 // array-to-pointer standard conversion (4.2) is used in place of
3620 // A for type deduction; otherwise,
3621 if (ArgType->isArrayType())
3622 ArgType = S.Context.getArrayDecayedType(ArgType);
3623 // - If A is a function type, the pointer type produced by the
3624 // function-to-pointer standard conversion (4.3) is used in place
3625 // of A for type deduction; otherwise,
3626 else if (ArgType->isFunctionType())
3627 ArgType = S.Context.getPointerType(ArgType);
3628 else {
3629 // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3630 // type are ignored for type deduction.
3631 ArgType = ArgType.getUnqualifiedType();
3632 }
3633 }
3634
3635 // C++0x [temp.deduct.call]p4:
3636 // In general, the deduction process attempts to find template argument
3637 // values that will make the deduced A identical to A (after the type A
3638 // is transformed as described above). [...]
3639 TDF = TDF_SkipNonDependent;
3640
3641 // - If the original P is a reference type, the deduced A (i.e., the
3642 // type referred to by the reference) can be more cv-qualified than
3643 // the transformed A.
3644 if (ParamRefType)
3645 TDF |= TDF_ParamWithReferenceType;
3646 // - The transformed A can be another pointer or pointer to member
3647 // type that can be converted to the deduced A via a qualification
3648 // conversion (4.4).
3649 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3650 ArgType->isObjCObjectPointerType())
3651 TDF |= TDF_IgnoreQualifiers;
3652 // - If P is a class and P has the form simple-template-id, then the
3653 // transformed A can be a derived class of the deduced A. Likewise,
3654 // if P is a pointer to a class of the form simple-template-id, the
3655 // transformed A can be a pointer to a derived class pointed to by
3656 // the deduced A.
3657 if (isSimpleTemplateIdType(ParamType) ||
3658 (isa<PointerType>(ParamType) &&
3659 isSimpleTemplateIdType(
3660 ParamType->getAs<PointerType>()->getPointeeType())))
3661 TDF |= TDF_DerivedClass;
3662
3663 return false;
3664 }
3665
3666 static bool
3667 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3668 QualType T);
3669
3670 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3671 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3672 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3673 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3674 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3675 bool DecomposedParam, unsigned ArgIdx, unsigned TDF);
3676
3677 /// Attempt template argument deduction from an initializer list
3678 /// deemed to be an argument in a function call.
DeduceFromInitializerList(Sema & S,TemplateParameterList * TemplateParams,QualType AdjustedParamType,InitListExpr * ILE,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced,SmallVectorImpl<Sema::OriginalCallArg> & OriginalCallArgs,unsigned ArgIdx,unsigned TDF)3679 static Sema::TemplateDeductionResult DeduceFromInitializerList(
3680 Sema &S, TemplateParameterList *TemplateParams, QualType AdjustedParamType,
3681 InitListExpr *ILE, TemplateDeductionInfo &Info,
3682 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3683 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs, unsigned ArgIdx,
3684 unsigned TDF) {
3685 // C++ [temp.deduct.call]p1: (CWG 1591)
3686 // If removing references and cv-qualifiers from P gives
3687 // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is
3688 // a non-empty initializer list, then deduction is performed instead for
3689 // each element of the initializer list, taking P0 as a function template
3690 // parameter type and the initializer element as its argument
3691 //
3692 // We've already removed references and cv-qualifiers here.
3693 if (!ILE->getNumInits())
3694 return Sema::TDK_Success;
3695
3696 QualType ElTy;
3697 auto *ArrTy = S.Context.getAsArrayType(AdjustedParamType);
3698 if (ArrTy)
3699 ElTy = ArrTy->getElementType();
3700 else if (!S.isStdInitializerList(AdjustedParamType, &ElTy)) {
3701 // Otherwise, an initializer list argument causes the parameter to be
3702 // considered a non-deduced context
3703 return Sema::TDK_Success;
3704 }
3705
3706 // Deduction only needs to be done for dependent types.
3707 if (ElTy->isDependentType()) {
3708 for (Expr *E : ILE->inits()) {
3709 if (auto Result = DeduceTemplateArgumentsFromCallArgument(
3710 S, TemplateParams, 0, ElTy, E, Info, Deduced, OriginalCallArgs, true,
3711 ArgIdx, TDF))
3712 return Result;
3713 }
3714 }
3715
3716 // in the P0[N] case, if N is a non-type template parameter, N is deduced
3717 // from the length of the initializer list.
3718 if (auto *DependentArrTy = dyn_cast_or_null<DependentSizedArrayType>(ArrTy)) {
3719 // Determine the array bound is something we can deduce.
3720 if (NonTypeTemplateParmDecl *NTTP =
3721 getDeducedParameterFromExpr(Info, DependentArrTy->getSizeExpr())) {
3722 // We can perform template argument deduction for the given non-type
3723 // template parameter.
3724 // C++ [temp.deduct.type]p13:
3725 // The type of N in the type T[N] is std::size_t.
3726 QualType T = S.Context.getSizeType();
3727 llvm::APInt Size(S.Context.getIntWidth(T), ILE->getNumInits());
3728 if (auto Result = DeduceNonTypeTemplateArgument(
3729 S, TemplateParams, NTTP, llvm::APSInt(Size), T,
3730 /*ArrayBound=*/true, Info, Deduced))
3731 return Result;
3732 }
3733 }
3734
3735 return Sema::TDK_Success;
3736 }
3737
3738 /// Perform template argument deduction per [temp.deduct.call] for a
3739 /// single parameter / argument pair.
DeduceTemplateArgumentsFromCallArgument(Sema & S,TemplateParameterList * TemplateParams,unsigned FirstInnerIndex,QualType ParamType,Expr * Arg,TemplateDeductionInfo & Info,SmallVectorImpl<DeducedTemplateArgument> & Deduced,SmallVectorImpl<Sema::OriginalCallArg> & OriginalCallArgs,bool DecomposedParam,unsigned ArgIdx,unsigned TDF)3740 static Sema::TemplateDeductionResult DeduceTemplateArgumentsFromCallArgument(
3741 Sema &S, TemplateParameterList *TemplateParams, unsigned FirstInnerIndex,
3742 QualType ParamType, Expr *Arg, TemplateDeductionInfo &Info,
3743 SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3744 SmallVectorImpl<Sema::OriginalCallArg> &OriginalCallArgs,
3745 bool DecomposedParam, unsigned ArgIdx, unsigned TDF) {
3746 QualType ArgType = Arg->getType();
3747 QualType OrigParamType = ParamType;
3748
3749 // If P is a reference type [...]
3750 // If P is a cv-qualified type [...]
3751 if (AdjustFunctionParmAndArgTypesForDeduction(
3752 S, TemplateParams, FirstInnerIndex, ParamType, ArgType, Arg, TDF))
3753 return Sema::TDK_Success;
3754
3755 // If [...] the argument is a non-empty initializer list [...]
3756 if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg))
3757 return DeduceFromInitializerList(S, TemplateParams, ParamType, ILE, Info,
3758 Deduced, OriginalCallArgs, ArgIdx, TDF);
3759
3760 // [...] the deduction process attempts to find template argument values
3761 // that will make the deduced A identical to A
3762 //
3763 // Keep track of the argument type and corresponding parameter index,
3764 // so we can check for compatibility between the deduced A and A.
3765 OriginalCallArgs.push_back(
3766 Sema::OriginalCallArg(OrigParamType, DecomposedParam, ArgIdx, ArgType));
3767 return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3768 ArgType, Info, Deduced, TDF);
3769 }
3770
3771 /// Perform template argument deduction from a function call
3772 /// (C++ [temp.deduct.call]).
3773 ///
3774 /// \param FunctionTemplate the function template for which we are performing
3775 /// template argument deduction.
3776 ///
3777 /// \param ExplicitTemplateArgs the explicit template arguments provided
3778 /// for this call.
3779 ///
3780 /// \param Args the function call arguments
3781 ///
3782 /// \param Specialization if template argument deduction was successful,
3783 /// this will be set to the function template specialization produced by
3784 /// template argument deduction.
3785 ///
3786 /// \param Info the argument will be updated to provide additional information
3787 /// about template argument deduction.
3788 ///
3789 /// \param CheckNonDependent A callback to invoke to check conversions for
3790 /// non-dependent parameters, between deduction and substitution, per DR1391.
3791 /// If this returns true, substitution will be skipped and we return
3792 /// TDK_NonDependentConversionFailure. The callback is passed the parameter
3793 /// types (after substituting explicit template arguments).
3794 ///
3795 /// \returns the result of template argument deduction.
DeduceTemplateArguments(FunctionTemplateDecl * FunctionTemplate,TemplateArgumentListInfo * ExplicitTemplateArgs,ArrayRef<Expr * > Args,FunctionDecl * & Specialization,TemplateDeductionInfo & Info,bool PartialOverloading,llvm::function_ref<bool (ArrayRef<QualType>)> CheckNonDependent)3796 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
3797 FunctionTemplateDecl *FunctionTemplate,
3798 TemplateArgumentListInfo *ExplicitTemplateArgs, ArrayRef<Expr *> Args,
3799 FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
3800 bool PartialOverloading,
3801 llvm::function_ref<bool(ArrayRef<QualType>)> CheckNonDependent) {
3802 if (FunctionTemplate->isInvalidDecl())
3803 return TDK_Invalid;
3804
3805 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3806 unsigned NumParams = Function->getNumParams();
3807
3808 unsigned FirstInnerIndex = getFirstInnerIndex(FunctionTemplate);
3809
3810 // C++ [temp.deduct.call]p1:
3811 // Template argument deduction is done by comparing each function template
3812 // parameter type (call it P) with the type of the corresponding argument
3813 // of the call (call it A) as described below.
3814 if (Args.size() < Function->getMinRequiredArguments() && !PartialOverloading)
3815 return TDK_TooFewArguments;
3816 else if (TooManyArguments(NumParams, Args.size(), PartialOverloading)) {
3817 const FunctionProtoType *Proto
3818 = Function->getType()->getAs<FunctionProtoType>();
3819 if (Proto->isTemplateVariadic())
3820 /* Do nothing */;
3821 else if (!Proto->isVariadic())
3822 return TDK_TooManyArguments;
3823 }
3824
3825 // The types of the parameters from which we will perform template argument
3826 // deduction.
3827 LocalInstantiationScope InstScope(*this);
3828 TemplateParameterList *TemplateParams
3829 = FunctionTemplate->getTemplateParameters();
3830 SmallVector<DeducedTemplateArgument, 4> Deduced;
3831 SmallVector<QualType, 8> ParamTypes;
3832 unsigned NumExplicitlySpecified = 0;
3833 if (ExplicitTemplateArgs) {
3834 TemplateDeductionResult Result =
3835 SubstituteExplicitTemplateArguments(FunctionTemplate,
3836 *ExplicitTemplateArgs,
3837 Deduced,
3838 ParamTypes,
3839 nullptr,
3840 Info);
3841 if (Result)
3842 return Result;
3843
3844 NumExplicitlySpecified = Deduced.size();
3845 } else {
3846 // Just fill in the parameter types from the function declaration.
3847 for (unsigned I = 0; I != NumParams; ++I)
3848 ParamTypes.push_back(Function->getParamDecl(I)->getType());
3849 }
3850
3851 SmallVector<OriginalCallArg, 8> OriginalCallArgs;
3852
3853 // Deduce an argument of type ParamType from an expression with index ArgIdx.
3854 auto DeduceCallArgument = [&](QualType ParamType, unsigned ArgIdx) {
3855 // C++ [demp.deduct.call]p1: (DR1391)
3856 // Template argument deduction is done by comparing each function template
3857 // parameter that contains template-parameters that participate in
3858 // template argument deduction ...
3859 if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3860 return Sema::TDK_Success;
3861
3862 // ... with the type of the corresponding argument
3863 return DeduceTemplateArgumentsFromCallArgument(
3864 *this, TemplateParams, FirstInnerIndex, ParamType, Args[ArgIdx], Info, Deduced,
3865 OriginalCallArgs, /*Decomposed*/false, ArgIdx, /*TDF*/ 0);
3866 };
3867
3868 // Deduce template arguments from the function parameters.
3869 Deduced.resize(TemplateParams->size());
3870 SmallVector<QualType, 8> ParamTypesForArgChecking;
3871 for (unsigned ParamIdx = 0, NumParamTypes = ParamTypes.size(), ArgIdx = 0;
3872 ParamIdx != NumParamTypes; ++ParamIdx) {
3873 QualType ParamType = ParamTypes[ParamIdx];
3874
3875 const PackExpansionType *ParamExpansion =
3876 dyn_cast<PackExpansionType>(ParamType);
3877 if (!ParamExpansion) {
3878 // Simple case: matching a function parameter to a function argument.
3879 if (ArgIdx >= Args.size())
3880 break;
3881
3882 ParamTypesForArgChecking.push_back(ParamType);
3883 if (auto Result = DeduceCallArgument(ParamType, ArgIdx++))
3884 return Result;
3885
3886 continue;
3887 }
3888
3889 QualType ParamPattern = ParamExpansion->getPattern();
3890 PackDeductionScope PackScope(*this, TemplateParams, Deduced, Info,
3891 ParamPattern);
3892
3893 // C++0x [temp.deduct.call]p1:
3894 // For a function parameter pack that occurs at the end of the
3895 // parameter-declaration-list, the type A of each remaining argument of
3896 // the call is compared with the type P of the declarator-id of the
3897 // function parameter pack. Each comparison deduces template arguments
3898 // for subsequent positions in the template parameter packs expanded by
3899 // the function parameter pack. When a function parameter pack appears
3900 // in a non-deduced context [not at the end of the list], the type of
3901 // that parameter pack is never deduced.
3902 //
3903 // FIXME: The above rule allows the size of the parameter pack to change
3904 // after we skip it (in the non-deduced case). That makes no sense, so
3905 // we instead notionally deduce the pack against N arguments, where N is
3906 // the length of the explicitly-specified pack if it's expanded by the
3907 // parameter pack and 0 otherwise, and we treat each deduction as a
3908 // non-deduced context.
3909 if (ParamIdx + 1 == NumParamTypes || PackScope.hasFixedArity()) {
3910 for (; ArgIdx < Args.size() && PackScope.hasNextElement();
3911 PackScope.nextPackElement(), ++ArgIdx) {
3912 ParamTypesForArgChecking.push_back(ParamPattern);
3913 if (auto Result = DeduceCallArgument(ParamPattern, ArgIdx))
3914 return Result;
3915 }
3916 } else {
3917 // If the parameter type contains an explicitly-specified pack that we
3918 // could not expand, skip the number of parameters notionally created
3919 // by the expansion.
3920 Optional<unsigned> NumExpansions = ParamExpansion->getNumExpansions();
3921 if (NumExpansions && !PackScope.isPartiallyExpanded()) {
3922 for (unsigned I = 0; I != *NumExpansions && ArgIdx < Args.size();
3923 ++I, ++ArgIdx) {
3924 ParamTypesForArgChecking.push_back(ParamPattern);
3925 // FIXME: Should we add OriginalCallArgs for these? What if the
3926 // corresponding argument is a list?
3927 PackScope.nextPackElement();
3928 }
3929 }
3930 }
3931
3932 // Build argument packs for each of the parameter packs expanded by this
3933 // pack expansion.
3934 if (auto Result = PackScope.finish())
3935 return Result;
3936 }
3937
3938 // Capture the context in which the function call is made. This is the context
3939 // that is needed when the accessibility of template arguments is checked.
3940 DeclContext *CallingCtx = CurContext;
3941
3942 return FinishTemplateArgumentDeduction(
3943 FunctionTemplate, Deduced, NumExplicitlySpecified, Specialization, Info,
3944 &OriginalCallArgs, PartialOverloading, [&, CallingCtx]() {
3945 ContextRAII SavedContext(*this, CallingCtx);
3946 return CheckNonDependent(ParamTypesForArgChecking);
3947 });
3948 }
3949
adjustCCAndNoReturn(QualType ArgFunctionType,QualType FunctionType,bool AdjustExceptionSpec)3950 QualType Sema::adjustCCAndNoReturn(QualType ArgFunctionType,
3951 QualType FunctionType,
3952 bool AdjustExceptionSpec) {
3953 if (ArgFunctionType.isNull())
3954 return ArgFunctionType;
3955
3956 const FunctionProtoType *FunctionTypeP =
3957 FunctionType->castAs<FunctionProtoType>();
3958 const FunctionProtoType *ArgFunctionTypeP =
3959 ArgFunctionType->getAs<FunctionProtoType>();
3960
3961 FunctionProtoType::ExtProtoInfo EPI = ArgFunctionTypeP->getExtProtoInfo();
3962 bool Rebuild = false;
3963
3964 CallingConv CC = FunctionTypeP->getCallConv();
3965 if (EPI.ExtInfo.getCC() != CC) {
3966 EPI.ExtInfo = EPI.ExtInfo.withCallingConv(CC);
3967 Rebuild = true;
3968 }
3969
3970 bool NoReturn = FunctionTypeP->getNoReturnAttr();
3971 if (EPI.ExtInfo.getNoReturn() != NoReturn) {
3972 EPI.ExtInfo = EPI.ExtInfo.withNoReturn(NoReturn);
3973 Rebuild = true;
3974 }
3975
3976 if (AdjustExceptionSpec && (FunctionTypeP->hasExceptionSpec() ||
3977 ArgFunctionTypeP->hasExceptionSpec())) {
3978 EPI.ExceptionSpec = FunctionTypeP->getExtProtoInfo().ExceptionSpec;
3979 Rebuild = true;
3980 }
3981
3982 if (!Rebuild)
3983 return ArgFunctionType;
3984
3985 return Context.getFunctionType(ArgFunctionTypeP->getReturnType(),
3986 ArgFunctionTypeP->getParamTypes(), EPI);
3987 }
3988
3989 /// Deduce template arguments when taking the address of a function
3990 /// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3991 /// a template.
3992 ///
3993 /// \param FunctionTemplate the function template for which we are performing
3994 /// template argument deduction.
3995 ///
3996 /// \param ExplicitTemplateArgs the explicitly-specified template
3997 /// arguments.
3998 ///
3999 /// \param ArgFunctionType the function type that will be used as the
4000 /// "argument" type (A) when performing template argument deduction from the
4001 /// function template's function type. This type may be NULL, if there is no
4002 /// argument type to compare against, in C++0x [temp.arg.explicit]p3.
4003 ///
4004 /// \param Specialization if template argument deduction was successful,
4005 /// this will be set to the function template specialization produced by
4006 /// template argument deduction.
4007 ///
4008 /// \param Info the argument will be updated to provide additional information
4009 /// about template argument deduction.
4010 ///
4011 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4012 /// the address of a function template per [temp.deduct.funcaddr] and
4013 /// [over.over]. If \c false, we are looking up a function template
4014 /// specialization based on its signature, per [temp.deduct.decl].
4015 ///
4016 /// \returns the result of template argument deduction.
DeduceTemplateArguments(FunctionTemplateDecl * FunctionTemplate,TemplateArgumentListInfo * ExplicitTemplateArgs,QualType ArgFunctionType,FunctionDecl * & Specialization,TemplateDeductionInfo & Info,bool IsAddressOfFunction)4017 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4018 FunctionTemplateDecl *FunctionTemplate,
4019 TemplateArgumentListInfo *ExplicitTemplateArgs, QualType ArgFunctionType,
4020 FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4021 bool IsAddressOfFunction) {
4022 if (FunctionTemplate->isInvalidDecl())
4023 return TDK_Invalid;
4024
4025 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4026 TemplateParameterList *TemplateParams
4027 = FunctionTemplate->getTemplateParameters();
4028 QualType FunctionType = Function->getType();
4029
4030 // Substitute any explicit template arguments.
4031 LocalInstantiationScope InstScope(*this);
4032 SmallVector<DeducedTemplateArgument, 4> Deduced;
4033 unsigned NumExplicitlySpecified = 0;
4034 SmallVector<QualType, 4> ParamTypes;
4035 if (ExplicitTemplateArgs) {
4036 if (TemplateDeductionResult Result
4037 = SubstituteExplicitTemplateArguments(FunctionTemplate,
4038 *ExplicitTemplateArgs,
4039 Deduced, ParamTypes,
4040 &FunctionType, Info))
4041 return Result;
4042
4043 NumExplicitlySpecified = Deduced.size();
4044 }
4045
4046 // When taking the address of a function, we require convertibility of
4047 // the resulting function type. Otherwise, we allow arbitrary mismatches
4048 // of calling convention and noreturn.
4049 if (!IsAddressOfFunction)
4050 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, FunctionType,
4051 /*AdjustExceptionSpec*/false);
4052
4053 // Unevaluated SFINAE context.
4054 EnterExpressionEvaluationContext Unevaluated(
4055 *this, Sema::ExpressionEvaluationContext::Unevaluated);
4056 SFINAETrap Trap(*this);
4057
4058 Deduced.resize(TemplateParams->size());
4059
4060 // If the function has a deduced return type, substitute it for a dependent
4061 // type so that we treat it as a non-deduced context in what follows. If we
4062 // are looking up by signature, the signature type should also have a deduced
4063 // return type, which we instead expect to exactly match.
4064 bool HasDeducedReturnType = false;
4065 if (getLangOpts().CPlusPlus14 && IsAddressOfFunction &&
4066 Function->getReturnType()->getContainedAutoType()) {
4067 FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
4068 HasDeducedReturnType = true;
4069 }
4070
4071 if (!ArgFunctionType.isNull()) {
4072 unsigned TDF =
4073 TDF_TopLevelParameterTypeList | TDF_AllowCompatibleFunctionType;
4074 // Deduce template arguments from the function type.
4075 if (TemplateDeductionResult Result
4076 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4077 FunctionType, ArgFunctionType,
4078 Info, Deduced, TDF))
4079 return Result;
4080 }
4081
4082 if (TemplateDeductionResult Result
4083 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
4084 NumExplicitlySpecified,
4085 Specialization, Info))
4086 return Result;
4087
4088 // If the function has a deduced return type, deduce it now, so we can check
4089 // that the deduced function type matches the requested type.
4090 if (HasDeducedReturnType &&
4091 Specialization->getReturnType()->isUndeducedType() &&
4092 DeduceReturnType(Specialization, Info.getLocation(), false))
4093 return TDK_MiscellaneousDeductionFailure;
4094
4095 // If the function has a dependent exception specification, resolve it now,
4096 // so we can check that the exception specification matches.
4097 auto *SpecializationFPT =
4098 Specialization->getType()->castAs<FunctionProtoType>();
4099 if (getLangOpts().CPlusPlus17 &&
4100 isUnresolvedExceptionSpec(SpecializationFPT->getExceptionSpecType()) &&
4101 !ResolveExceptionSpec(Info.getLocation(), SpecializationFPT))
4102 return TDK_MiscellaneousDeductionFailure;
4103
4104 // Adjust the exception specification of the argument to match the
4105 // substituted and resolved type we just formed. (Calling convention and
4106 // noreturn can't be dependent, so we don't actually need this for them
4107 // right now.)
4108 QualType SpecializationType = Specialization->getType();
4109 if (!IsAddressOfFunction)
4110 ArgFunctionType = adjustCCAndNoReturn(ArgFunctionType, SpecializationType,
4111 /*AdjustExceptionSpec*/true);
4112
4113 // If the requested function type does not match the actual type of the
4114 // specialization with respect to arguments of compatible pointer to function
4115 // types, template argument deduction fails.
4116 if (!ArgFunctionType.isNull()) {
4117 if (IsAddressOfFunction &&
4118 !isSameOrCompatibleFunctionType(
4119 Context.getCanonicalType(SpecializationType),
4120 Context.getCanonicalType(ArgFunctionType)))
4121 return TDK_MiscellaneousDeductionFailure;
4122
4123 if (!IsAddressOfFunction &&
4124 !Context.hasSameType(SpecializationType, ArgFunctionType))
4125 return TDK_MiscellaneousDeductionFailure;
4126 }
4127
4128 return TDK_Success;
4129 }
4130
4131 /// Deduce template arguments for a templated conversion
4132 /// function (C++ [temp.deduct.conv]) and, if successful, produce a
4133 /// conversion function template specialization.
4134 Sema::TemplateDeductionResult
DeduceTemplateArguments(FunctionTemplateDecl * ConversionTemplate,QualType ToType,CXXConversionDecl * & Specialization,TemplateDeductionInfo & Info)4135 Sema::DeduceTemplateArguments(FunctionTemplateDecl *ConversionTemplate,
4136 QualType ToType,
4137 CXXConversionDecl *&Specialization,
4138 TemplateDeductionInfo &Info) {
4139 if (ConversionTemplate->isInvalidDecl())
4140 return TDK_Invalid;
4141
4142 CXXConversionDecl *ConversionGeneric
4143 = cast<CXXConversionDecl>(ConversionTemplate->getTemplatedDecl());
4144
4145 QualType FromType = ConversionGeneric->getConversionType();
4146
4147 // Canonicalize the types for deduction.
4148 QualType P = Context.getCanonicalType(FromType);
4149 QualType A = Context.getCanonicalType(ToType);
4150
4151 // C++0x [temp.deduct.conv]p2:
4152 // If P is a reference type, the type referred to by P is used for
4153 // type deduction.
4154 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
4155 P = PRef->getPointeeType();
4156
4157 // C++0x [temp.deduct.conv]p4:
4158 // [...] If A is a reference type, the type referred to by A is used
4159 // for type deduction.
4160 if (const ReferenceType *ARef = A->getAs<ReferenceType>()) {
4161 A = ARef->getPointeeType();
4162 // We work around a defect in the standard here: cv-qualifiers are also
4163 // removed from P and A in this case, unless P was a reference type. This
4164 // seems to mostly match what other compilers are doing.
4165 if (!FromType->getAs<ReferenceType>()) {
4166 A = A.getUnqualifiedType();
4167 P = P.getUnqualifiedType();
4168 }
4169
4170 // C++ [temp.deduct.conv]p3:
4171 //
4172 // If A is not a reference type:
4173 } else {
4174 assert(!A->isReferenceType() && "Reference types were handled above");
4175
4176 // - If P is an array type, the pointer type produced by the
4177 // array-to-pointer standard conversion (4.2) is used in place
4178 // of P for type deduction; otherwise,
4179 if (P->isArrayType())
4180 P = Context.getArrayDecayedType(P);
4181 // - If P is a function type, the pointer type produced by the
4182 // function-to-pointer standard conversion (4.3) is used in
4183 // place of P for type deduction; otherwise,
4184 else if (P->isFunctionType())
4185 P = Context.getPointerType(P);
4186 // - If P is a cv-qualified type, the top level cv-qualifiers of
4187 // P's type are ignored for type deduction.
4188 else
4189 P = P.getUnqualifiedType();
4190
4191 // C++0x [temp.deduct.conv]p4:
4192 // If A is a cv-qualified type, the top level cv-qualifiers of A's
4193 // type are ignored for type deduction. If A is a reference type, the type
4194 // referred to by A is used for type deduction.
4195 A = A.getUnqualifiedType();
4196 }
4197
4198 // Unevaluated SFINAE context.
4199 EnterExpressionEvaluationContext Unevaluated(
4200 *this, Sema::ExpressionEvaluationContext::Unevaluated);
4201 SFINAETrap Trap(*this);
4202
4203 // C++ [temp.deduct.conv]p1:
4204 // Template argument deduction is done by comparing the return
4205 // type of the template conversion function (call it P) with the
4206 // type that is required as the result of the conversion (call it
4207 // A) as described in 14.8.2.4.
4208 TemplateParameterList *TemplateParams
4209 = ConversionTemplate->getTemplateParameters();
4210 SmallVector<DeducedTemplateArgument, 4> Deduced;
4211 Deduced.resize(TemplateParams->size());
4212
4213 // C++0x [temp.deduct.conv]p4:
4214 // In general, the deduction process attempts to find template
4215 // argument values that will make the deduced A identical to
4216 // A. However, there are two cases that allow a difference:
4217 unsigned TDF = 0;
4218 // - If the original A is a reference type, A can be more
4219 // cv-qualified than the deduced A (i.e., the type referred to
4220 // by the reference)
4221 if (ToType->isReferenceType())
4222 TDF |= TDF_ArgWithReferenceType;
4223 // - The deduced A can be another pointer or pointer to member
4224 // type that can be converted to A via a qualification
4225 // conversion.
4226 //
4227 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
4228 // both P and A are pointers or member pointers. In this case, we
4229 // just ignore cv-qualifiers completely).
4230 if ((P->isPointerType() && A->isPointerType()) ||
4231 (P->isMemberPointerType() && A->isMemberPointerType()))
4232 TDF |= TDF_IgnoreQualifiers;
4233 if (TemplateDeductionResult Result
4234 = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
4235 P, A, Info, Deduced, TDF))
4236 return Result;
4237
4238 // Create an Instantiation Scope for finalizing the operator.
4239 LocalInstantiationScope InstScope(*this);
4240 // Finish template argument deduction.
4241 FunctionDecl *ConversionSpecialized = nullptr;
4242 TemplateDeductionResult Result
4243 = FinishTemplateArgumentDeduction(ConversionTemplate, Deduced, 0,
4244 ConversionSpecialized, Info);
4245 Specialization = cast_or_null<CXXConversionDecl>(ConversionSpecialized);
4246 return Result;
4247 }
4248
4249 /// Deduce template arguments for a function template when there is
4250 /// nothing to deduce against (C++0x [temp.arg.explicit]p3).
4251 ///
4252 /// \param FunctionTemplate the function template for which we are performing
4253 /// template argument deduction.
4254 ///
4255 /// \param ExplicitTemplateArgs the explicitly-specified template
4256 /// arguments.
4257 ///
4258 /// \param Specialization if template argument deduction was successful,
4259 /// this will be set to the function template specialization produced by
4260 /// template argument deduction.
4261 ///
4262 /// \param Info the argument will be updated to provide additional information
4263 /// about template argument deduction.
4264 ///
4265 /// \param IsAddressOfFunction If \c true, we are deducing as part of taking
4266 /// the address of a function template in a context where we do not have a
4267 /// target type, per [over.over]. If \c false, we are looking up a function
4268 /// template specialization based on its signature, which only happens when
4269 /// deducing a function parameter type from an argument that is a template-id
4270 /// naming a function template specialization.
4271 ///
4272 /// \returns the result of template argument deduction.
DeduceTemplateArguments(FunctionTemplateDecl * FunctionTemplate,TemplateArgumentListInfo * ExplicitTemplateArgs,FunctionDecl * & Specialization,TemplateDeductionInfo & Info,bool IsAddressOfFunction)4273 Sema::TemplateDeductionResult Sema::DeduceTemplateArguments(
4274 FunctionTemplateDecl *FunctionTemplate,
4275 TemplateArgumentListInfo *ExplicitTemplateArgs,
4276 FunctionDecl *&Specialization, TemplateDeductionInfo &Info,
4277 bool IsAddressOfFunction) {
4278 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
4279 QualType(), Specialization, Info,
4280 IsAddressOfFunction);
4281 }
4282
4283 namespace {
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 UseTypeSugar;
4291
4292 public:
SubstituteDeducedTypeTransform(Sema & SemaRef,QualType Replacement,bool UseTypeSugar=true)4293 SubstituteDeducedTypeTransform(Sema &SemaRef, QualType Replacement,
4294 bool UseTypeSugar = true)
4295 : TreeTransform<SubstituteDeducedTypeTransform>(SemaRef),
4296 Replacement(Replacement), UseTypeSugar(UseTypeSugar) {}
4297
TransformDesugared(TypeLocBuilder & TLB,DeducedTypeLoc TL)4298 QualType TransformDesugared(TypeLocBuilder &TLB, DeducedTypeLoc TL) {
4299 assert(isa<TemplateTypeParmType>(Replacement) &&
4300 "unexpected unsugared replacement kind");
4301 QualType Result = Replacement;
4302 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
4303 NewTL.setNameLoc(TL.getNameLoc());
4304 return Result;
4305 }
4306
TransformAutoType(TypeLocBuilder & TLB,AutoTypeLoc TL)4307 QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
4308 // If we're building the type pattern to deduce against, don't wrap the
4309 // substituted type in an AutoType. Certain template deduction rules
4310 // apply only when a template type parameter appears directly (and not if
4311 // the parameter is found through desugaring). For instance:
4312 // auto &&lref = lvalue;
4313 // must transform into "rvalue reference to T" not "rvalue reference to
4314 // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
4315 //
4316 // FIXME: Is this still necessary?
4317 if (!UseTypeSugar)
4318 return TransformDesugared(TLB, TL);
4319
4320 QualType Result = SemaRef.Context.getAutoType(
4321 Replacement, TL.getTypePtr()->getKeyword(), Replacement.isNull());
4322 auto NewTL = TLB.push<AutoTypeLoc>(Result);
4323 NewTL.setNameLoc(TL.getNameLoc());
4324 return Result;
4325 }
4326
TransformDeducedTemplateSpecializationType(TypeLocBuilder & TLB,DeducedTemplateSpecializationTypeLoc TL)4327 QualType TransformDeducedTemplateSpecializationType(
4328 TypeLocBuilder &TLB, DeducedTemplateSpecializationTypeLoc TL) {
4329 if (!UseTypeSugar)
4330 return TransformDesugared(TLB, TL);
4331
4332 QualType Result = SemaRef.Context.getDeducedTemplateSpecializationType(
4333 TL.getTypePtr()->getTemplateName(),
4334 Replacement, Replacement.isNull());
4335 auto NewTL = TLB.push<DeducedTemplateSpecializationTypeLoc>(Result);
4336 NewTL.setNameLoc(TL.getNameLoc());
4337 return Result;
4338 }
4339
TransformLambdaExpr(LambdaExpr * E)4340 ExprResult TransformLambdaExpr(LambdaExpr *E) {
4341 // Lambdas never need to be transformed.
4342 return E;
4343 }
4344
Apply(TypeLoc TL)4345 QualType Apply(TypeLoc TL) {
4346 // Create some scratch storage for the transformed type locations.
4347 // FIXME: We're just going to throw this information away. Don't build it.
4348 TypeLocBuilder TLB;
4349 TLB.reserve(TL.getFullDataSize());
4350 return TransformType(TLB, TL);
4351 }
4352 };
4353
4354 } // namespace
4355
4356 Sema::DeduceAutoResult
DeduceAutoType(TypeSourceInfo * Type,Expr * & Init,QualType & Result,Optional<unsigned> DependentDeductionDepth)4357 Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result,
4358 Optional<unsigned> DependentDeductionDepth) {
4359 return DeduceAutoType(Type->getTypeLoc(), Init, Result,
4360 DependentDeductionDepth);
4361 }
4362
4363 /// Attempt to produce an informative diagostic explaining why auto deduction
4364 /// failed.
4365 /// \return \c true if diagnosed, \c false if not.
diagnoseAutoDeductionFailure(Sema & S,Sema::TemplateDeductionResult TDK,TemplateDeductionInfo & Info,ArrayRef<SourceRange> Ranges)4366 static bool diagnoseAutoDeductionFailure(Sema &S,
4367 Sema::TemplateDeductionResult TDK,
4368 TemplateDeductionInfo &Info,
4369 ArrayRef<SourceRange> Ranges) {
4370 switch (TDK) {
4371 case Sema::TDK_Inconsistent: {
4372 // Inconsistent deduction means we were deducing from an initializer list.
4373 auto D = S.Diag(Info.getLocation(), diag::err_auto_inconsistent_deduction);
4374 D << Info.FirstArg << Info.SecondArg;
4375 for (auto R : Ranges)
4376 D << R;
4377 return true;
4378 }
4379
4380 // FIXME: Are there other cases for which a custom diagnostic is more useful
4381 // than the basic "types don't match" diagnostic?
4382
4383 default:
4384 return false;
4385 }
4386 }
4387
4388 /// Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
4389 ///
4390 /// Note that this is done even if the initializer is dependent. (This is
4391 /// necessary to support partial ordering of templates using 'auto'.)
4392 /// A dependent type will be produced when deducing from a dependent type.
4393 ///
4394 /// \param Type the type pattern using the auto type-specifier.
4395 /// \param Init the initializer for the variable whose type is to be deduced.
4396 /// \param Result if type deduction was successful, this will be set to the
4397 /// deduced type.
4398 /// \param DependentDeductionDepth Set if we should permit deduction in
4399 /// dependent cases. This is necessary for template partial ordering with
4400 /// 'auto' template parameters. The value specified is the template
4401 /// parameter depth at which we should perform 'auto' deduction.
4402 Sema::DeduceAutoResult
DeduceAutoType(TypeLoc Type,Expr * & Init,QualType & Result,Optional<unsigned> DependentDeductionDepth)4403 Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result,
4404 Optional<unsigned> DependentDeductionDepth) {
4405 if (Init->getType()->isNonOverloadPlaceholderType()) {
4406 ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
4407 if (NonPlaceholder.isInvalid())
4408 return DAR_FailedAlreadyDiagnosed;
4409 Init = NonPlaceholder.get();
4410 }
4411
4412 if (!DependentDeductionDepth &&
4413 (Type.getType()->isDependentType() || Init->isTypeDependent())) {
4414 Result = SubstituteDeducedTypeTransform(*this, QualType()).Apply(Type);
4415 assert(!Result.isNull() && "substituting DependentTy can't fail");
4416 return DAR_Succeeded;
4417 }
4418
4419 // Find the depth of template parameter to synthesize.
4420 unsigned Depth = DependentDeductionDepth.getValueOr(0);
4421
4422 // If this is a 'decltype(auto)' specifier, do the decltype dance.
4423 // Since 'decltype(auto)' can only occur at the top of the type, we
4424 // don't need to go digging for it.
4425 if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
4426 if (AT->isDecltypeAuto()) {
4427 if (isa<InitListExpr>(Init)) {
4428 Diag(Init->getBeginLoc(), diag::err_decltype_auto_initializer_list);
4429 return DAR_FailedAlreadyDiagnosed;
4430 }
4431
4432 ExprResult ER = CheckPlaceholderExpr(Init);
4433 if (ER.isInvalid())
4434 return DAR_FailedAlreadyDiagnosed;
4435 Init = ER.get();
4436 QualType Deduced = BuildDecltypeType(Init, Init->getBeginLoc(), false);
4437 if (Deduced.isNull())
4438 return DAR_FailedAlreadyDiagnosed;
4439 // FIXME: Support a non-canonical deduced type for 'auto'.
4440 Deduced = Context.getCanonicalType(Deduced);
4441 Result = SubstituteDeducedTypeTransform(*this, Deduced).Apply(Type);
4442 if (Result.isNull())
4443 return DAR_FailedAlreadyDiagnosed;
4444 return DAR_Succeeded;
4445 } else if (!getLangOpts().CPlusPlus) {
4446 if (isa<InitListExpr>(Init)) {
4447 Diag(Init->getBeginLoc(), diag::err_auto_init_list_from_c);
4448 return DAR_FailedAlreadyDiagnosed;
4449 }
4450 }
4451 }
4452
4453 SourceLocation Loc = Init->getExprLoc();
4454
4455 LocalInstantiationScope InstScope(*this);
4456
4457 // Build template<class TemplParam> void Func(FuncParam);
4458 TemplateTypeParmDecl *TemplParam = TemplateTypeParmDecl::Create(
4459 Context, nullptr, SourceLocation(), Loc, Depth, 0, nullptr, false, false);
4460 QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
4461 NamedDecl *TemplParamPtr = TemplParam;
4462 FixedSizeTemplateParameterListStorage<1, false> TemplateParamsSt(
4463 Loc, Loc, TemplParamPtr, Loc, nullptr);
4464
4465 QualType FuncParam =
4466 SubstituteDeducedTypeTransform(*this, TemplArg, /*UseTypeSugar*/false)
4467 .Apply(Type);
4468 assert(!FuncParam.isNull() &&
4469 "substituting template parameter for 'auto' failed");
4470
4471 // Deduce type of TemplParam in Func(Init)
4472 SmallVector<DeducedTemplateArgument, 1> Deduced;
4473 Deduced.resize(1);
4474
4475 TemplateDeductionInfo Info(Loc, Depth);
4476
4477 // If deduction failed, don't diagnose if the initializer is dependent; it
4478 // might acquire a matching type in the instantiation.
4479 auto DeductionFailed = [&](TemplateDeductionResult TDK,
4480 ArrayRef<SourceRange> Ranges) -> DeduceAutoResult {
4481 if (Init->isTypeDependent()) {
4482 Result = SubstituteDeducedTypeTransform(*this, QualType()).Apply(Type);
4483 assert(!Result.isNull() && "substituting DependentTy can't fail");
4484 return DAR_Succeeded;
4485 }
4486 if (diagnoseAutoDeductionFailure(*this, TDK, Info, Ranges))
4487 return DAR_FailedAlreadyDiagnosed;
4488 return DAR_Failed;
4489 };
4490
4491 SmallVector<OriginalCallArg, 4> OriginalCallArgs;
4492
4493 InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
4494 if (InitList) {
4495 // Notionally, we substitute std::initializer_list<T> for 'auto' and deduce
4496 // against that. Such deduction only succeeds if removing cv-qualifiers and
4497 // references results in std::initializer_list<T>.
4498 if (!Type.getType().getNonReferenceType()->getAs<AutoType>())
4499 return DAR_Failed;
4500
4501 SourceRange DeducedFromInitRange;
4502 for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
4503 Expr *Init = InitList->getInit(i);
4504
4505 if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
4506 *this, TemplateParamsSt.get(), 0, TemplArg, Init,
4507 Info, Deduced, OriginalCallArgs, /*Decomposed*/ true,
4508 /*ArgIdx*/ 0, /*TDF*/ 0))
4509 return DeductionFailed(TDK, {DeducedFromInitRange,
4510 Init->getSourceRange()});
4511
4512 if (DeducedFromInitRange.isInvalid() &&
4513 Deduced[0].getKind() != TemplateArgument::Null)
4514 DeducedFromInitRange = Init->getSourceRange();
4515 }
4516 } else {
4517 if (!getLangOpts().CPlusPlus && Init->refersToBitField()) {
4518 Diag(Loc, diag::err_auto_bitfield);
4519 return DAR_FailedAlreadyDiagnosed;
4520 }
4521
4522 if (auto TDK = DeduceTemplateArgumentsFromCallArgument(
4523 *this, TemplateParamsSt.get(), 0, FuncParam, Init, Info, Deduced,
4524 OriginalCallArgs, /*Decomposed*/ false, /*ArgIdx*/ 0, /*TDF*/ 0))
4525 return DeductionFailed(TDK, {});
4526 }
4527
4528 // Could be null if somehow 'auto' appears in a non-deduced context.
4529 if (Deduced[0].getKind() != TemplateArgument::Type)
4530 return DeductionFailed(TDK_Incomplete, {});
4531
4532 QualType DeducedType = Deduced[0].getAsType();
4533
4534 if (InitList) {
4535 DeducedType = BuildStdInitializerList(DeducedType, Loc);
4536 if (DeducedType.isNull())
4537 return DAR_FailedAlreadyDiagnosed;
4538 }
4539
4540 Result = SubstituteDeducedTypeTransform(*this, DeducedType).Apply(Type);
4541 if (Result.isNull())
4542 return DAR_FailedAlreadyDiagnosed;
4543
4544 // Check that the deduced argument type is compatible with the original
4545 // argument type per C++ [temp.deduct.call]p4.
4546 QualType DeducedA = InitList ? Deduced[0].getAsType() : Result;
4547 for (const OriginalCallArg &OriginalArg : OriginalCallArgs) {
4548 assert((bool)InitList == OriginalArg.DecomposedParam &&
4549 "decomposed non-init-list in auto deduction?");
4550 if (auto TDK =
4551 CheckOriginalCallArgDeduction(*this, Info, OriginalArg, DeducedA)) {
4552 Result = QualType();
4553 return DeductionFailed(TDK, {});
4554 }
4555 }
4556
4557 return DAR_Succeeded;
4558 }
4559
SubstAutoType(QualType TypeWithAuto,QualType TypeToReplaceAuto)4560 QualType Sema::SubstAutoType(QualType TypeWithAuto,
4561 QualType TypeToReplaceAuto) {
4562 if (TypeToReplaceAuto->isDependentType())
4563 TypeToReplaceAuto = QualType();
4564 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4565 .TransformType(TypeWithAuto);
4566 }
4567
SubstAutoTypeSourceInfo(TypeSourceInfo * TypeWithAuto,QualType TypeToReplaceAuto)4568 TypeSourceInfo *Sema::SubstAutoTypeSourceInfo(TypeSourceInfo *TypeWithAuto,
4569 QualType TypeToReplaceAuto) {
4570 if (TypeToReplaceAuto->isDependentType())
4571 TypeToReplaceAuto = QualType();
4572 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto)
4573 .TransformType(TypeWithAuto);
4574 }
4575
ReplaceAutoType(QualType TypeWithAuto,QualType TypeToReplaceAuto)4576 QualType Sema::ReplaceAutoType(QualType TypeWithAuto,
4577 QualType TypeToReplaceAuto) {
4578 return SubstituteDeducedTypeTransform(*this, TypeToReplaceAuto,
4579 /*UseTypeSugar*/ false)
4580 .TransformType(TypeWithAuto);
4581 }
4582
DiagnoseAutoDeductionFailure(VarDecl * VDecl,Expr * Init)4583 void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
4584 if (isa<InitListExpr>(Init))
4585 Diag(VDecl->getLocation(),
4586 VDecl->isInitCapture()
4587 ? diag::err_init_capture_deduction_failure_from_init_list
4588 : diag::err_auto_var_deduction_failure_from_init_list)
4589 << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
4590 else
4591 Diag(VDecl->getLocation(),
4592 VDecl->isInitCapture() ? diag::err_init_capture_deduction_failure
4593 : diag::err_auto_var_deduction_failure)
4594 << VDecl->getDeclName() << VDecl->getType() << Init->getType()
4595 << Init->getSourceRange();
4596 }
4597
DeduceReturnType(FunctionDecl * FD,SourceLocation Loc,bool Diagnose)4598 bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
4599 bool Diagnose) {
4600 assert(FD->getReturnType()->isUndeducedType());
4601
4602 // For a lambda's conversion operator, deduce any 'auto' or 'decltype(auto)'
4603 // within the return type from the call operator's type.
4604 if (isLambdaConversionOperator(FD)) {
4605 CXXRecordDecl *Lambda = cast<CXXMethodDecl>(FD)->getParent();
4606 FunctionDecl *CallOp = Lambda->getLambdaCallOperator();
4607
4608 // For a generic lambda, instantiate the call operator if needed.
4609 if (auto *Args = FD->getTemplateSpecializationArgs()) {
4610 CallOp = InstantiateFunctionDeclaration(
4611 CallOp->getDescribedFunctionTemplate(), Args, Loc);
4612 if (!CallOp || CallOp->isInvalidDecl())
4613 return true;
4614
4615 // We might need to deduce the return type by instantiating the definition
4616 // of the operator() function.
4617 if (CallOp->getReturnType()->isUndeducedType())
4618 InstantiateFunctionDefinition(Loc, CallOp);
4619 }
4620
4621 if (CallOp->isInvalidDecl())
4622 return true;
4623 assert(!CallOp->getReturnType()->isUndeducedType() &&
4624 "failed to deduce lambda return type");
4625
4626 // Build the new return type from scratch.
4627 QualType RetType = getLambdaConversionFunctionResultType(
4628 CallOp->getType()->castAs<FunctionProtoType>());
4629 if (FD->getReturnType()->getAs<PointerType>())
4630 RetType = Context.getPointerType(RetType);
4631 else {
4632 assert(FD->getReturnType()->getAs<BlockPointerType>());
4633 RetType = Context.getBlockPointerType(RetType);
4634 }
4635 Context.adjustDeducedFunctionResultType(FD, RetType);
4636 return false;
4637 }
4638
4639 if (FD->getTemplateInstantiationPattern())
4640 InstantiateFunctionDefinition(Loc, FD);
4641
4642 bool StillUndeduced = FD->getReturnType()->isUndeducedType();
4643 if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
4644 Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
4645 Diag(FD->getLocation(), diag::note_callee_decl) << FD;
4646 }
4647
4648 return StillUndeduced;
4649 }
4650
4651 /// If this is a non-static member function,
4652 static void
AddImplicitObjectParameterType(ASTContext & Context,CXXMethodDecl * Method,SmallVectorImpl<QualType> & ArgTypes)4653 AddImplicitObjectParameterType(ASTContext &Context,
4654 CXXMethodDecl *Method,
4655 SmallVectorImpl<QualType> &ArgTypes) {
4656 // C++11 [temp.func.order]p3:
4657 // [...] The new parameter is of type "reference to cv A," where cv are
4658 // the cv-qualifiers of the function template (if any) and A is
4659 // the class of which the function template is a member.
4660 //
4661 // The standard doesn't say explicitly, but we pick the appropriate kind of
4662 // reference type based on [over.match.funcs]p4.
4663 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
4664 ArgTy = Context.getQualifiedType(ArgTy, Method->getTypeQualifiers());
4665 if (Method->getRefQualifier() == RQ_RValue)
4666 ArgTy = Context.getRValueReferenceType(ArgTy);
4667 else
4668 ArgTy = Context.getLValueReferenceType(ArgTy);
4669 ArgTypes.push_back(ArgTy);
4670 }
4671
4672 /// Determine whether the function template \p FT1 is at least as
4673 /// specialized as \p FT2.
isAtLeastAsSpecializedAs(Sema & S,SourceLocation Loc,FunctionTemplateDecl * FT1,FunctionTemplateDecl * FT2,TemplatePartialOrderingContext TPOC,unsigned NumCallArguments1)4674 static bool isAtLeastAsSpecializedAs(Sema &S,
4675 SourceLocation Loc,
4676 FunctionTemplateDecl *FT1,
4677 FunctionTemplateDecl *FT2,
4678 TemplatePartialOrderingContext TPOC,
4679 unsigned NumCallArguments1) {
4680 FunctionDecl *FD1 = FT1->getTemplatedDecl();
4681 FunctionDecl *FD2 = FT2->getTemplatedDecl();
4682 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
4683 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
4684
4685 assert(Proto1 && Proto2 && "Function templates must have prototypes");
4686 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
4687 SmallVector<DeducedTemplateArgument, 4> Deduced;
4688 Deduced.resize(TemplateParams->size());
4689
4690 // C++0x [temp.deduct.partial]p3:
4691 // The types used to determine the ordering depend on the context in which
4692 // the partial ordering is done:
4693 TemplateDeductionInfo Info(Loc);
4694 SmallVector<QualType, 4> Args2;
4695 switch (TPOC) {
4696 case TPOC_Call: {
4697 // - In the context of a function call, the function parameter types are
4698 // used.
4699 CXXMethodDecl *Method1 = dyn_cast<CXXMethodDecl>(FD1);
4700 CXXMethodDecl *Method2 = dyn_cast<CXXMethodDecl>(FD2);
4701
4702 // C++11 [temp.func.order]p3:
4703 // [...] If only one of the function templates is a non-static
4704 // member, that function template is considered to have a new
4705 // first parameter inserted in its function parameter list. The
4706 // new parameter is of type "reference to cv A," where cv are
4707 // the cv-qualifiers of the function template (if any) and A is
4708 // the class of which the function template is a member.
4709 //
4710 // Note that we interpret this to mean "if one of the function
4711 // templates is a non-static member and the other is a non-member";
4712 // otherwise, the ordering rules for static functions against non-static
4713 // functions don't make any sense.
4714 //
4715 // C++98/03 doesn't have this provision but we've extended DR532 to cover
4716 // it as wording was broken prior to it.
4717 SmallVector<QualType, 4> Args1;
4718
4719 unsigned NumComparedArguments = NumCallArguments1;
4720
4721 if (!Method2 && Method1 && !Method1->isStatic()) {
4722 // Compare 'this' from Method1 against first parameter from Method2.
4723 AddImplicitObjectParameterType(S.Context, Method1, Args1);
4724 ++NumComparedArguments;
4725 } else if (!Method1 && Method2 && !Method2->isStatic()) {
4726 // Compare 'this' from Method2 against first parameter from Method1.
4727 AddImplicitObjectParameterType(S.Context, Method2, Args2);
4728 }
4729
4730 Args1.insert(Args1.end(), Proto1->param_type_begin(),
4731 Proto1->param_type_end());
4732 Args2.insert(Args2.end(), Proto2->param_type_begin(),
4733 Proto2->param_type_end());
4734
4735 // C++ [temp.func.order]p5:
4736 // The presence of unused ellipsis and default arguments has no effect on
4737 // the partial ordering of function templates.
4738 if (Args1.size() > NumComparedArguments)
4739 Args1.resize(NumComparedArguments);
4740 if (Args2.size() > NumComparedArguments)
4741 Args2.resize(NumComparedArguments);
4742 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4743 Args1.data(), Args1.size(), Info, Deduced,
4744 TDF_None, /*PartialOrdering=*/true))
4745 return false;
4746
4747 break;
4748 }
4749
4750 case TPOC_Conversion:
4751 // - In the context of a call to a conversion operator, the return types
4752 // of the conversion function templates are used.
4753 if (DeduceTemplateArgumentsByTypeMatch(
4754 S, TemplateParams, Proto2->getReturnType(), Proto1->getReturnType(),
4755 Info, Deduced, TDF_None,
4756 /*PartialOrdering=*/true))
4757 return false;
4758 break;
4759
4760 case TPOC_Other:
4761 // - In other contexts (14.6.6.2) the function template's function type
4762 // is used.
4763 if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4764 FD2->getType(), FD1->getType(),
4765 Info, Deduced, TDF_None,
4766 /*PartialOrdering=*/true))
4767 return false;
4768 break;
4769 }
4770
4771 // C++0x [temp.deduct.partial]p11:
4772 // In most cases, all template parameters must have values in order for
4773 // deduction to succeed, but for partial ordering purposes a template
4774 // parameter may remain without a value provided it is not used in the
4775 // types being used for partial ordering. [ Note: a template parameter used
4776 // in a non-deduced context is considered used. -end note]
4777 unsigned ArgIdx = 0, NumArgs = Deduced.size();
4778 for (; ArgIdx != NumArgs; ++ArgIdx)
4779 if (Deduced[ArgIdx].isNull())
4780 break;
4781
4782 // FIXME: We fail to implement [temp.deduct.type]p1 along this path. We need
4783 // to substitute the deduced arguments back into the template and check that
4784 // we get the right type.
4785
4786 if (ArgIdx == NumArgs) {
4787 // All template arguments were deduced. FT1 is at least as specialized
4788 // as FT2.
4789 return true;
4790 }
4791
4792 // Figure out which template parameters were used.
4793 llvm::SmallBitVector UsedParameters(TemplateParams->size());
4794 switch (TPOC) {
4795 case TPOC_Call:
4796 for (unsigned I = 0, N = Args2.size(); I != N; ++I)
4797 ::MarkUsedTemplateParameters(S.Context, Args2[I], false,
4798 TemplateParams->getDepth(),
4799 UsedParameters);
4800 break;
4801
4802 case TPOC_Conversion:
4803 ::MarkUsedTemplateParameters(S.Context, Proto2->getReturnType(), false,
4804 TemplateParams->getDepth(), UsedParameters);
4805 break;
4806
4807 case TPOC_Other:
4808 ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4809 TemplateParams->getDepth(),
4810 UsedParameters);
4811 break;
4812 }
4813
4814 for (; ArgIdx != NumArgs; ++ArgIdx)
4815 // If this argument had no value deduced but was used in one of the types
4816 // used for partial ordering, then deduction fails.
4817 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4818 return false;
4819
4820 return true;
4821 }
4822
4823 /// Determine whether this a function template whose parameter-type-list
4824 /// ends with a function parameter pack.
isVariadicFunctionTemplate(FunctionTemplateDecl * FunTmpl)4825 static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4826 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4827 unsigned NumParams = Function->getNumParams();
4828 if (NumParams == 0)
4829 return false;
4830
4831 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4832 if (!Last->isParameterPack())
4833 return false;
4834
4835 // Make sure that no previous parameter is a parameter pack.
4836 while (--NumParams > 0) {
4837 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4838 return false;
4839 }
4840
4841 return true;
4842 }
4843
4844 /// Returns the more specialized function template according
4845 /// to the rules of function template partial ordering (C++ [temp.func.order]).
4846 ///
4847 /// \param FT1 the first function template
4848 ///
4849 /// \param FT2 the second function template
4850 ///
4851 /// \param TPOC the context in which we are performing partial ordering of
4852 /// function templates.
4853 ///
4854 /// \param NumCallArguments1 The number of arguments in the call to FT1, used
4855 /// only when \c TPOC is \c TPOC_Call.
4856 ///
4857 /// \param NumCallArguments2 The number of arguments in the call to FT2, used
4858 /// only when \c TPOC is \c TPOC_Call.
4859 ///
4860 /// \returns the more specialized function template. If neither
4861 /// template is more specialized, returns NULL.
4862 FunctionTemplateDecl *
getMoreSpecializedTemplate(FunctionTemplateDecl * FT1,FunctionTemplateDecl * FT2,SourceLocation Loc,TemplatePartialOrderingContext TPOC,unsigned NumCallArguments1,unsigned NumCallArguments2)4863 Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4864 FunctionTemplateDecl *FT2,
4865 SourceLocation Loc,
4866 TemplatePartialOrderingContext TPOC,
4867 unsigned NumCallArguments1,
4868 unsigned NumCallArguments2) {
4869 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4870 NumCallArguments1);
4871 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4872 NumCallArguments2);
4873
4874 if (Better1 != Better2) // We have a clear winner
4875 return Better1 ? FT1 : FT2;
4876
4877 if (!Better1 && !Better2) // Neither is better than the other
4878 return nullptr;
4879
4880 // FIXME: This mimics what GCC implements, but doesn't match up with the
4881 // proposed resolution for core issue 692. This area needs to be sorted out,
4882 // but for now we attempt to maintain compatibility.
4883 bool Variadic1 = isVariadicFunctionTemplate(FT1);
4884 bool Variadic2 = isVariadicFunctionTemplate(FT2);
4885 if (Variadic1 != Variadic2)
4886 return Variadic1? FT2 : FT1;
4887
4888 return nullptr;
4889 }
4890
4891 /// Determine if the two templates are equivalent.
isSameTemplate(TemplateDecl * T1,TemplateDecl * T2)4892 static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4893 if (T1 == T2)
4894 return true;
4895
4896 if (!T1 || !T2)
4897 return false;
4898
4899 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4900 }
4901
4902 /// Retrieve the most specialized of the given function template
4903 /// specializations.
4904 ///
4905 /// \param SpecBegin the start iterator of the function template
4906 /// specializations that we will be comparing.
4907 ///
4908 /// \param SpecEnd the end iterator of the function template
4909 /// specializations, paired with \p SpecBegin.
4910 ///
4911 /// \param Loc the location where the ambiguity or no-specializations
4912 /// diagnostic should occur.
4913 ///
4914 /// \param NoneDiag partial diagnostic used to diagnose cases where there are
4915 /// no matching candidates.
4916 ///
4917 /// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4918 /// occurs.
4919 ///
4920 /// \param CandidateDiag partial diagnostic used for each function template
4921 /// specialization that is a candidate in the ambiguous ordering. One parameter
4922 /// in this diagnostic should be unbound, which will correspond to the string
4923 /// describing the template arguments for the function template specialization.
4924 ///
4925 /// \returns the most specialized function template specialization, if
4926 /// found. Otherwise, returns SpecEnd.
getMostSpecialized(UnresolvedSetIterator SpecBegin,UnresolvedSetIterator SpecEnd,TemplateSpecCandidateSet & FailedCandidates,SourceLocation Loc,const PartialDiagnostic & NoneDiag,const PartialDiagnostic & AmbigDiag,const PartialDiagnostic & CandidateDiag,bool Complain,QualType TargetType)4927 UnresolvedSetIterator Sema::getMostSpecialized(
4928 UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4929 TemplateSpecCandidateSet &FailedCandidates,
4930 SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4931 const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4932 bool Complain, QualType TargetType) {
4933 if (SpecBegin == SpecEnd) {
4934 if (Complain) {
4935 Diag(Loc, NoneDiag);
4936 FailedCandidates.NoteCandidates(*this, Loc);
4937 }
4938 return SpecEnd;
4939 }
4940
4941 if (SpecBegin + 1 == SpecEnd)
4942 return SpecBegin;
4943
4944 // Find the function template that is better than all of the templates it
4945 // has been compared to.
4946 UnresolvedSetIterator Best = SpecBegin;
4947 FunctionTemplateDecl *BestTemplate
4948 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4949 assert(BestTemplate && "Not a function template specialization?");
4950 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4951 FunctionTemplateDecl *Challenger
4952 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4953 assert(Challenger && "Not a function template specialization?");
4954 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4955 Loc, TPOC_Other, 0, 0),
4956 Challenger)) {
4957 Best = I;
4958 BestTemplate = Challenger;
4959 }
4960 }
4961
4962 // Make sure that the "best" function template is more specialized than all
4963 // of the others.
4964 bool Ambiguous = false;
4965 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4966 FunctionTemplateDecl *Challenger
4967 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4968 if (I != Best &&
4969 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4970 Loc, TPOC_Other, 0, 0),
4971 BestTemplate)) {
4972 Ambiguous = true;
4973 break;
4974 }
4975 }
4976
4977 if (!Ambiguous) {
4978 // We found an answer. Return it.
4979 return Best;
4980 }
4981
4982 // Diagnose the ambiguity.
4983 if (Complain) {
4984 Diag(Loc, AmbigDiag);
4985
4986 // FIXME: Can we order the candidates in some sane way?
4987 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4988 PartialDiagnostic PD = CandidateDiag;
4989 const auto *FD = cast<FunctionDecl>(*I);
4990 PD << FD << getTemplateArgumentBindingsText(
4991 FD->getPrimaryTemplate()->getTemplateParameters(),
4992 *FD->getTemplateSpecializationArgs());
4993 if (!TargetType.isNull())
4994 HandleFunctionTypeMismatch(PD, FD->getType(), TargetType);
4995 Diag((*I)->getLocation(), PD);
4996 }
4997 }
4998
4999 return SpecEnd;
5000 }
5001
5002 /// Determine whether one partial specialization, P1, is at least as
5003 /// specialized than another, P2.
5004 ///
5005 /// \tparam TemplateLikeDecl The kind of P2, which must be a
5006 /// TemplateDecl or {Class,Var}TemplatePartialSpecializationDecl.
5007 /// \param T1 The injected-class-name of P1 (faked for a variable template).
5008 /// \param T2 The injected-class-name of P2 (faked for a variable template).
5009 template<typename TemplateLikeDecl>
isAtLeastAsSpecializedAs(Sema & S,QualType T1,QualType T2,TemplateLikeDecl * P2,TemplateDeductionInfo & Info)5010 static bool isAtLeastAsSpecializedAs(Sema &S, QualType T1, QualType T2,
5011 TemplateLikeDecl *P2,
5012 TemplateDeductionInfo &Info) {
5013 // C++ [temp.class.order]p1:
5014 // For two class template partial specializations, the first is at least as
5015 // specialized as the second if, given the following rewrite to two
5016 // function templates, the first function template is at least as
5017 // specialized as the second according to the ordering rules for function
5018 // templates (14.6.6.2):
5019 // - the first function template has the same template parameters as the
5020 // first partial specialization and has a single function parameter
5021 // whose type is a class template specialization with the template
5022 // arguments of the first partial specialization, and
5023 // - the second function template has the same template parameters as the
5024 // second partial specialization and has a single function parameter
5025 // whose type is a class template specialization with the template
5026 // arguments of the second partial specialization.
5027 //
5028 // Rather than synthesize function templates, we merely perform the
5029 // equivalent partial ordering by performing deduction directly on
5030 // the template arguments of the class template partial
5031 // specializations. This computation is slightly simpler than the
5032 // general problem of function template partial ordering, because
5033 // class template partial specializations are more constrained. We
5034 // know that every template parameter is deducible from the class
5035 // template partial specialization's template arguments, for
5036 // example.
5037 SmallVector<DeducedTemplateArgument, 4> Deduced;
5038
5039 // Determine whether P1 is at least as specialized as P2.
5040 Deduced.resize(P2->getTemplateParameters()->size());
5041 if (DeduceTemplateArgumentsByTypeMatch(S, P2->getTemplateParameters(),
5042 T2, T1, Info, Deduced, TDF_None,
5043 /*PartialOrdering=*/true))
5044 return false;
5045
5046 SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
5047 Deduced.end());
5048 Sema::InstantiatingTemplate Inst(S, Info.getLocation(), P2, DeducedArgs,
5049 Info);
5050 auto *TST1 = T1->castAs<TemplateSpecializationType>();
5051 if (FinishTemplateArgumentDeduction(
5052 S, P2, /*PartialOrdering=*/true,
5053 TemplateArgumentList(TemplateArgumentList::OnStack,
5054 TST1->template_arguments()),
5055 Deduced, Info))
5056 return false;
5057
5058 return true;
5059 }
5060
5061 /// Returns the more specialized class template partial specialization
5062 /// according to the rules of partial ordering of class template partial
5063 /// specializations (C++ [temp.class.order]).
5064 ///
5065 /// \param PS1 the first class template partial specialization
5066 ///
5067 /// \param PS2 the second class template partial specialization
5068 ///
5069 /// \returns the more specialized class template partial specialization. If
5070 /// neither partial specialization is more specialized, returns NULL.
5071 ClassTemplatePartialSpecializationDecl *
getMoreSpecializedPartialSpecialization(ClassTemplatePartialSpecializationDecl * PS1,ClassTemplatePartialSpecializationDecl * PS2,SourceLocation Loc)5072 Sema::getMoreSpecializedPartialSpecialization(
5073 ClassTemplatePartialSpecializationDecl *PS1,
5074 ClassTemplatePartialSpecializationDecl *PS2,
5075 SourceLocation Loc) {
5076 QualType PT1 = PS1->getInjectedSpecializationType();
5077 QualType PT2 = PS2->getInjectedSpecializationType();
5078
5079 TemplateDeductionInfo Info(Loc);
5080 bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info);
5081 bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info);
5082
5083 if (Better1 == Better2)
5084 return nullptr;
5085
5086 return Better1 ? PS1 : PS2;
5087 }
5088
isMoreSpecializedThanPrimary(ClassTemplatePartialSpecializationDecl * Spec,TemplateDeductionInfo & Info)5089 bool Sema::isMoreSpecializedThanPrimary(
5090 ClassTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) {
5091 ClassTemplateDecl *Primary = Spec->getSpecializedTemplate();
5092 QualType PrimaryT = Primary->getInjectedClassNameSpecialization();
5093 QualType PartialT = Spec->getInjectedSpecializationType();
5094 if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info))
5095 return false;
5096 if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) {
5097 Info.clearSFINAEDiagnostic();
5098 return false;
5099 }
5100 return true;
5101 }
5102
5103 VarTemplatePartialSpecializationDecl *
getMoreSpecializedPartialSpecialization(VarTemplatePartialSpecializationDecl * PS1,VarTemplatePartialSpecializationDecl * PS2,SourceLocation Loc)5104 Sema::getMoreSpecializedPartialSpecialization(
5105 VarTemplatePartialSpecializationDecl *PS1,
5106 VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
5107 // Pretend the variable template specializations are class template
5108 // specializations and form a fake injected class name type for comparison.
5109 assert(PS1->getSpecializedTemplate() == PS2->getSpecializedTemplate() &&
5110 "the partial specializations being compared should specialize"
5111 " the same template.");
5112 TemplateName Name(PS1->getSpecializedTemplate());
5113 TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
5114 QualType PT1 = Context.getTemplateSpecializationType(
5115 CanonTemplate, PS1->getTemplateArgs().asArray());
5116 QualType PT2 = Context.getTemplateSpecializationType(
5117 CanonTemplate, PS2->getTemplateArgs().asArray());
5118
5119 TemplateDeductionInfo Info(Loc);
5120 bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info);
5121 bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info);
5122
5123 if (Better1 == Better2)
5124 return nullptr;
5125
5126 return Better1 ? PS1 : PS2;
5127 }
5128
isMoreSpecializedThanPrimary(VarTemplatePartialSpecializationDecl * Spec,TemplateDeductionInfo & Info)5129 bool Sema::isMoreSpecializedThanPrimary(
5130 VarTemplatePartialSpecializationDecl *Spec, TemplateDeductionInfo &Info) {
5131 TemplateDecl *Primary = Spec->getSpecializedTemplate();
5132 // FIXME: Cache the injected template arguments rather than recomputing
5133 // them for each partial specialization.
5134 SmallVector<TemplateArgument, 8> PrimaryArgs;
5135 Context.getInjectedTemplateArgs(Primary->getTemplateParameters(),
5136 PrimaryArgs);
5137
5138 TemplateName CanonTemplate =
5139 Context.getCanonicalTemplateName(TemplateName(Primary));
5140 QualType PrimaryT = Context.getTemplateSpecializationType(
5141 CanonTemplate, PrimaryArgs);
5142 QualType PartialT = Context.getTemplateSpecializationType(
5143 CanonTemplate, Spec->getTemplateArgs().asArray());
5144 if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info))
5145 return false;
5146 if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) {
5147 Info.clearSFINAEDiagnostic();
5148 return false;
5149 }
5150 return true;
5151 }
5152
isTemplateTemplateParameterAtLeastAsSpecializedAs(TemplateParameterList * P,TemplateDecl * AArg,SourceLocation Loc)5153 bool Sema::isTemplateTemplateParameterAtLeastAsSpecializedAs(
5154 TemplateParameterList *P, TemplateDecl *AArg, SourceLocation Loc) {
5155 // C++1z [temp.arg.template]p4: (DR 150)
5156 // A template template-parameter P is at least as specialized as a
5157 // template template-argument A if, given the following rewrite to two
5158 // function templates...
5159
5160 // Rather than synthesize function templates, we merely perform the
5161 // equivalent partial ordering by performing deduction directly on
5162 // the template parameter lists of the template template parameters.
5163 //
5164 // Given an invented class template X with the template parameter list of
5165 // A (including default arguments):
5166 TemplateName X = Context.getCanonicalTemplateName(TemplateName(AArg));
5167 TemplateParameterList *A = AArg->getTemplateParameters();
5168
5169 // - Each function template has a single function parameter whose type is
5170 // a specialization of X with template arguments corresponding to the
5171 // template parameters from the respective function template
5172 SmallVector<TemplateArgument, 8> AArgs;
5173 Context.getInjectedTemplateArgs(A, AArgs);
5174
5175 // Check P's arguments against A's parameter list. This will fill in default
5176 // template arguments as needed. AArgs are already correct by construction.
5177 // We can't just use CheckTemplateIdType because that will expand alias
5178 // templates.
5179 SmallVector<TemplateArgument, 4> PArgs;
5180 {
5181 SFINAETrap Trap(*this);
5182
5183 Context.getInjectedTemplateArgs(P, PArgs);
5184 TemplateArgumentListInfo PArgList(P->getLAngleLoc(), P->getRAngleLoc());
5185 for (unsigned I = 0, N = P->size(); I != N; ++I) {
5186 // Unwrap packs that getInjectedTemplateArgs wrapped around pack
5187 // expansions, to form an "as written" argument list.
5188 TemplateArgument Arg = PArgs[I];
5189 if (Arg.getKind() == TemplateArgument::Pack) {
5190 assert(Arg.pack_size() == 1 && Arg.pack_begin()->isPackExpansion());
5191 Arg = *Arg.pack_begin();
5192 }
5193 PArgList.addArgument(getTrivialTemplateArgumentLoc(
5194 Arg, QualType(), P->getParam(I)->getLocation()));
5195 }
5196 PArgs.clear();
5197
5198 // C++1z [temp.arg.template]p3:
5199 // If the rewrite produces an invalid type, then P is not at least as
5200 // specialized as A.
5201 if (CheckTemplateArgumentList(AArg, Loc, PArgList, false, PArgs) ||
5202 Trap.hasErrorOccurred())
5203 return false;
5204 }
5205
5206 QualType AType = Context.getTemplateSpecializationType(X, AArgs);
5207 QualType PType = Context.getTemplateSpecializationType(X, PArgs);
5208
5209 // ... the function template corresponding to P is at least as specialized
5210 // as the function template corresponding to A according to the partial
5211 // ordering rules for function templates.
5212 TemplateDeductionInfo Info(Loc, A->getDepth());
5213 return isAtLeastAsSpecializedAs(*this, PType, AType, AArg, Info);
5214 }
5215
5216 /// Mark the template parameters that are used by the given
5217 /// expression.
5218 static void
MarkUsedTemplateParameters(ASTContext & Ctx,const Expr * E,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5219 MarkUsedTemplateParameters(ASTContext &Ctx,
5220 const Expr *E,
5221 bool OnlyDeduced,
5222 unsigned Depth,
5223 llvm::SmallBitVector &Used) {
5224 // We can deduce from a pack expansion.
5225 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
5226 E = Expansion->getPattern();
5227
5228 // Skip through any implicit casts we added while type-checking, and any
5229 // substitutions performed by template alias expansion.
5230 while (true) {
5231 if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
5232 E = ICE->getSubExpr();
5233 else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(E))
5234 E = CE->getSubExpr();
5235 else if (const SubstNonTypeTemplateParmExpr *Subst =
5236 dyn_cast<SubstNonTypeTemplateParmExpr>(E))
5237 E = Subst->getReplacement();
5238 else
5239 break;
5240 }
5241
5242 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
5243 // find other occurrences of template parameters.
5244 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
5245 if (!DRE)
5246 return;
5247
5248 const NonTypeTemplateParmDecl *NTTP
5249 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
5250 if (!NTTP)
5251 return;
5252
5253 if (NTTP->getDepth() == Depth)
5254 Used[NTTP->getIndex()] = true;
5255
5256 // In C++17 mode, additional arguments may be deduced from the type of a
5257 // non-type argument.
5258 if (Ctx.getLangOpts().CPlusPlus17)
5259 MarkUsedTemplateParameters(Ctx, NTTP->getType(), OnlyDeduced, Depth, Used);
5260 }
5261
5262 /// Mark the template parameters that are used by the given
5263 /// nested name specifier.
5264 static void
MarkUsedTemplateParameters(ASTContext & Ctx,NestedNameSpecifier * NNS,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5265 MarkUsedTemplateParameters(ASTContext &Ctx,
5266 NestedNameSpecifier *NNS,
5267 bool OnlyDeduced,
5268 unsigned Depth,
5269 llvm::SmallBitVector &Used) {
5270 if (!NNS)
5271 return;
5272
5273 MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
5274 Used);
5275 MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
5276 OnlyDeduced, Depth, Used);
5277 }
5278
5279 /// Mark the template parameters that are used by the given
5280 /// template name.
5281 static void
MarkUsedTemplateParameters(ASTContext & Ctx,TemplateName Name,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5282 MarkUsedTemplateParameters(ASTContext &Ctx,
5283 TemplateName Name,
5284 bool OnlyDeduced,
5285 unsigned Depth,
5286 llvm::SmallBitVector &Used) {
5287 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
5288 if (TemplateTemplateParmDecl *TTP
5289 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
5290 if (TTP->getDepth() == Depth)
5291 Used[TTP->getIndex()] = true;
5292 }
5293 return;
5294 }
5295
5296 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
5297 MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
5298 Depth, Used);
5299 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
5300 MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
5301 Depth, Used);
5302 }
5303
5304 /// Mark the template parameters that are used by the given
5305 /// type.
5306 static void
MarkUsedTemplateParameters(ASTContext & Ctx,QualType T,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5307 MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
5308 bool OnlyDeduced,
5309 unsigned Depth,
5310 llvm::SmallBitVector &Used) {
5311 if (T.isNull())
5312 return;
5313
5314 // Non-dependent types have nothing deducible
5315 if (!T->isDependentType())
5316 return;
5317
5318 T = Ctx.getCanonicalType(T);
5319 switch (T->getTypeClass()) {
5320 case Type::Pointer:
5321 MarkUsedTemplateParameters(Ctx,
5322 cast<PointerType>(T)->getPointeeType(),
5323 OnlyDeduced,
5324 Depth,
5325 Used);
5326 break;
5327
5328 case Type::BlockPointer:
5329 MarkUsedTemplateParameters(Ctx,
5330 cast<BlockPointerType>(T)->getPointeeType(),
5331 OnlyDeduced,
5332 Depth,
5333 Used);
5334 break;
5335
5336 case Type::LValueReference:
5337 case Type::RValueReference:
5338 MarkUsedTemplateParameters(Ctx,
5339 cast<ReferenceType>(T)->getPointeeType(),
5340 OnlyDeduced,
5341 Depth,
5342 Used);
5343 break;
5344
5345 case Type::MemberPointer: {
5346 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
5347 MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
5348 Depth, Used);
5349 MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
5350 OnlyDeduced, Depth, Used);
5351 break;
5352 }
5353
5354 case Type::DependentSizedArray:
5355 MarkUsedTemplateParameters(Ctx,
5356 cast<DependentSizedArrayType>(T)->getSizeExpr(),
5357 OnlyDeduced, Depth, Used);
5358 // Fall through to check the element type
5359 LLVM_FALLTHROUGH;
5360
5361 case Type::ConstantArray:
5362 case Type::IncompleteArray:
5363 MarkUsedTemplateParameters(Ctx,
5364 cast<ArrayType>(T)->getElementType(),
5365 OnlyDeduced, Depth, Used);
5366 break;
5367
5368 case Type::Vector:
5369 case Type::ExtVector:
5370 MarkUsedTemplateParameters(Ctx,
5371 cast<VectorType>(T)->getElementType(),
5372 OnlyDeduced, Depth, Used);
5373 break;
5374
5375 case Type::DependentVector: {
5376 const auto *VecType = cast<DependentVectorType>(T);
5377 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
5378 Depth, Used);
5379 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced, Depth,
5380 Used);
5381 break;
5382 }
5383 case Type::DependentSizedExtVector: {
5384 const DependentSizedExtVectorType *VecType
5385 = cast<DependentSizedExtVectorType>(T);
5386 MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
5387 Depth, Used);
5388 MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
5389 Depth, Used);
5390 break;
5391 }
5392
5393 case Type::DependentAddressSpace: {
5394 const DependentAddressSpaceType *DependentASType =
5395 cast<DependentAddressSpaceType>(T);
5396 MarkUsedTemplateParameters(Ctx, DependentASType->getPointeeType(),
5397 OnlyDeduced, Depth, Used);
5398 MarkUsedTemplateParameters(Ctx,
5399 DependentASType->getAddrSpaceExpr(),
5400 OnlyDeduced, Depth, Used);
5401 break;
5402 }
5403
5404 case Type::FunctionProto: {
5405 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
5406 MarkUsedTemplateParameters(Ctx, Proto->getReturnType(), OnlyDeduced, Depth,
5407 Used);
5408 for (unsigned I = 0, N = Proto->getNumParams(); I != N; ++I) {
5409 // C++17 [temp.deduct.type]p5:
5410 // The non-deduced contexts are: [...]
5411 // -- A function parameter pack that does not occur at the end of the
5412 // parameter-declaration-list.
5413 if (!OnlyDeduced || I + 1 == N ||
5414 !Proto->getParamType(I)->getAs<PackExpansionType>()) {
5415 MarkUsedTemplateParameters(Ctx, Proto->getParamType(I), OnlyDeduced,
5416 Depth, Used);
5417 } else {
5418 // FIXME: C++17 [temp.deduct.call]p1:
5419 // When a function parameter pack appears in a non-deduced context,
5420 // the type of that pack is never deduced.
5421 //
5422 // We should also track a set of "never deduced" parameters, and
5423 // subtract that from the list of deduced parameters after marking.
5424 }
5425 }
5426 if (auto *E = Proto->getNoexceptExpr())
5427 MarkUsedTemplateParameters(Ctx, E, OnlyDeduced, Depth, Used);
5428 break;
5429 }
5430
5431 case Type::TemplateTypeParm: {
5432 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
5433 if (TTP->getDepth() == Depth)
5434 Used[TTP->getIndex()] = true;
5435 break;
5436 }
5437
5438 case Type::SubstTemplateTypeParmPack: {
5439 const SubstTemplateTypeParmPackType *Subst
5440 = cast<SubstTemplateTypeParmPackType>(T);
5441 MarkUsedTemplateParameters(Ctx,
5442 QualType(Subst->getReplacedParameter(), 0),
5443 OnlyDeduced, Depth, Used);
5444 MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
5445 OnlyDeduced, Depth, Used);
5446 break;
5447 }
5448
5449 case Type::InjectedClassName:
5450 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
5451 LLVM_FALLTHROUGH;
5452
5453 case Type::TemplateSpecialization: {
5454 const TemplateSpecializationType *Spec
5455 = cast<TemplateSpecializationType>(T);
5456 MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
5457 Depth, Used);
5458
5459 // C++0x [temp.deduct.type]p9:
5460 // If the template argument list of P contains a pack expansion that is
5461 // not the last template argument, the entire template argument list is a
5462 // non-deduced context.
5463 if (OnlyDeduced &&
5464 hasPackExpansionBeforeEnd(Spec->template_arguments()))
5465 break;
5466
5467 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
5468 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
5469 Used);
5470 break;
5471 }
5472
5473 case Type::Complex:
5474 if (!OnlyDeduced)
5475 MarkUsedTemplateParameters(Ctx,
5476 cast<ComplexType>(T)->getElementType(),
5477 OnlyDeduced, Depth, Used);
5478 break;
5479
5480 case Type::Atomic:
5481 if (!OnlyDeduced)
5482 MarkUsedTemplateParameters(Ctx,
5483 cast<AtomicType>(T)->getValueType(),
5484 OnlyDeduced, Depth, Used);
5485 break;
5486
5487 case Type::DependentName:
5488 if (!OnlyDeduced)
5489 MarkUsedTemplateParameters(Ctx,
5490 cast<DependentNameType>(T)->getQualifier(),
5491 OnlyDeduced, Depth, Used);
5492 break;
5493
5494 case Type::DependentTemplateSpecialization: {
5495 // C++14 [temp.deduct.type]p5:
5496 // The non-deduced contexts are:
5497 // -- The nested-name-specifier of a type that was specified using a
5498 // qualified-id
5499 //
5500 // C++14 [temp.deduct.type]p6:
5501 // When a type name is specified in a way that includes a non-deduced
5502 // context, all of the types that comprise that type name are also
5503 // non-deduced.
5504 if (OnlyDeduced)
5505 break;
5506
5507 const DependentTemplateSpecializationType *Spec
5508 = cast<DependentTemplateSpecializationType>(T);
5509
5510 MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
5511 OnlyDeduced, Depth, Used);
5512
5513 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
5514 MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
5515 Used);
5516 break;
5517 }
5518
5519 case Type::TypeOf:
5520 if (!OnlyDeduced)
5521 MarkUsedTemplateParameters(Ctx,
5522 cast<TypeOfType>(T)->getUnderlyingType(),
5523 OnlyDeduced, Depth, Used);
5524 break;
5525
5526 case Type::TypeOfExpr:
5527 if (!OnlyDeduced)
5528 MarkUsedTemplateParameters(Ctx,
5529 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
5530 OnlyDeduced, Depth, Used);
5531 break;
5532
5533 case Type::Decltype:
5534 if (!OnlyDeduced)
5535 MarkUsedTemplateParameters(Ctx,
5536 cast<DecltypeType>(T)->getUnderlyingExpr(),
5537 OnlyDeduced, Depth, Used);
5538 break;
5539
5540 case Type::UnaryTransform:
5541 if (!OnlyDeduced)
5542 MarkUsedTemplateParameters(Ctx,
5543 cast<UnaryTransformType>(T)->getUnderlyingType(),
5544 OnlyDeduced, Depth, Used);
5545 break;
5546
5547 case Type::PackExpansion:
5548 MarkUsedTemplateParameters(Ctx,
5549 cast<PackExpansionType>(T)->getPattern(),
5550 OnlyDeduced, Depth, Used);
5551 break;
5552
5553 case Type::Auto:
5554 case Type::DeducedTemplateSpecialization:
5555 MarkUsedTemplateParameters(Ctx,
5556 cast<DeducedType>(T)->getDeducedType(),
5557 OnlyDeduced, Depth, Used);
5558 break;
5559
5560 // None of these types have any template parameters in them.
5561 case Type::Builtin:
5562 case Type::VariableArray:
5563 case Type::FunctionNoProto:
5564 case Type::Record:
5565 case Type::Enum:
5566 case Type::ObjCInterface:
5567 case Type::ObjCObject:
5568 case Type::ObjCObjectPointer:
5569 case Type::UnresolvedUsing:
5570 case Type::Pipe:
5571 #define TYPE(Class, Base)
5572 #define ABSTRACT_TYPE(Class, Base)
5573 #define DEPENDENT_TYPE(Class, Base)
5574 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
5575 #include "clang/AST/TypeNodes.def"
5576 break;
5577 }
5578 }
5579
5580 /// Mark the template parameters that are used by this
5581 /// template argument.
5582 static void
MarkUsedTemplateParameters(ASTContext & Ctx,const TemplateArgument & TemplateArg,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5583 MarkUsedTemplateParameters(ASTContext &Ctx,
5584 const TemplateArgument &TemplateArg,
5585 bool OnlyDeduced,
5586 unsigned Depth,
5587 llvm::SmallBitVector &Used) {
5588 switch (TemplateArg.getKind()) {
5589 case TemplateArgument::Null:
5590 case TemplateArgument::Integral:
5591 case TemplateArgument::Declaration:
5592 break;
5593
5594 case TemplateArgument::NullPtr:
5595 MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
5596 Depth, Used);
5597 break;
5598
5599 case TemplateArgument::Type:
5600 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
5601 Depth, Used);
5602 break;
5603
5604 case TemplateArgument::Template:
5605 case TemplateArgument::TemplateExpansion:
5606 MarkUsedTemplateParameters(Ctx,
5607 TemplateArg.getAsTemplateOrTemplatePattern(),
5608 OnlyDeduced, Depth, Used);
5609 break;
5610
5611 case TemplateArgument::Expression:
5612 MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
5613 Depth, Used);
5614 break;
5615
5616 case TemplateArgument::Pack:
5617 for (const auto &P : TemplateArg.pack_elements())
5618 MarkUsedTemplateParameters(Ctx, P, OnlyDeduced, Depth, Used);
5619 break;
5620 }
5621 }
5622
5623 /// Mark which template parameters can be deduced from a given
5624 /// template argument list.
5625 ///
5626 /// \param TemplateArgs the template argument list from which template
5627 /// parameters will be deduced.
5628 ///
5629 /// \param Used a bit vector whose elements will be set to \c true
5630 /// to indicate when the corresponding template parameter will be
5631 /// deduced.
5632 void
MarkUsedTemplateParameters(const TemplateArgumentList & TemplateArgs,bool OnlyDeduced,unsigned Depth,llvm::SmallBitVector & Used)5633 Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
5634 bool OnlyDeduced, unsigned Depth,
5635 llvm::SmallBitVector &Used) {
5636 // C++0x [temp.deduct.type]p9:
5637 // If the template argument list of P contains a pack expansion that is not
5638 // the last template argument, the entire template argument list is a
5639 // non-deduced context.
5640 if (OnlyDeduced &&
5641 hasPackExpansionBeforeEnd(TemplateArgs.asArray()))
5642 return;
5643
5644 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
5645 ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
5646 Depth, Used);
5647 }
5648
5649 /// Marks all of the template parameters that will be deduced by a
5650 /// call to the given function template.
MarkDeducedTemplateParameters(ASTContext & Ctx,const FunctionTemplateDecl * FunctionTemplate,llvm::SmallBitVector & Deduced)5651 void Sema::MarkDeducedTemplateParameters(
5652 ASTContext &Ctx, const FunctionTemplateDecl *FunctionTemplate,
5653 llvm::SmallBitVector &Deduced) {
5654 TemplateParameterList *TemplateParams
5655 = FunctionTemplate->getTemplateParameters();
5656 Deduced.clear();
5657 Deduced.resize(TemplateParams->size());
5658
5659 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
5660 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
5661 ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
5662 true, TemplateParams->getDepth(), Deduced);
5663 }
5664
hasDeducibleTemplateParameters(Sema & S,FunctionTemplateDecl * FunctionTemplate,QualType T)5665 bool hasDeducibleTemplateParameters(Sema &S,
5666 FunctionTemplateDecl *FunctionTemplate,
5667 QualType T) {
5668 if (!T->isDependentType())
5669 return false;
5670
5671 TemplateParameterList *TemplateParams
5672 = FunctionTemplate->getTemplateParameters();
5673 llvm::SmallBitVector Deduced(TemplateParams->size());
5674 ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
5675 Deduced);
5676
5677 return Deduced.any();
5678 }
5679