blob: 0d074e03333b4f8f069305e0abc2d16a2bc63995 [file] [log] [blame]
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001//===------- 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// This file implements C++ template argument deduction.
10//
11//===----------------------------------------------------------------------===/
12
Douglas Gregore737f502010-08-12 20:07:10 +000013#include "clang/Sema/Sema.h"
John McCall19510852010-08-20 18:27:03 +000014#include "clang/Sema/DeclSpec.h"
Douglas Gregor20a55e22010-12-22 18:17:10 +000015#include "clang/Sema/SemaDiagnostic.h" // FIXME: temporary!
John McCall7cd088e2010-08-24 07:21:54 +000016#include "clang/Sema/Template.h"
John McCall2a7fb272010-08-25 05:32:35 +000017#include "clang/Sema/TemplateDeduction.h"
Douglas Gregor0b9247f2009-06-04 00:03:07 +000018#include "clang/AST/ASTContext.h"
John McCall7cd088e2010-08-24 07:21:54 +000019#include "clang/AST/DeclObjC.h"
Douglas Gregor0b9247f2009-06-04 00:03:07 +000020#include "clang/AST/DeclTemplate.h"
21#include "clang/AST/StmtVisitor.h"
22#include "clang/AST/Expr.h"
23#include "clang/AST/ExprCXX.h"
Douglas Gregore02e2622010-12-22 21:19:48 +000024#include "llvm/ADT/BitVector.h"
Douglas Gregor8a514912009-09-14 18:39:43 +000025#include <algorithm>
Douglas Gregor508f1c82009-06-26 23:10:12 +000026
27namespace clang {
John McCall2a7fb272010-08-25 05:32:35 +000028 using namespace sema;
29
Douglas Gregor508f1c82009-06-26 23:10:12 +000030 /// \brief Various flags that control template argument deduction.
31 ///
32 /// These flags can be bitwise-OR'd together.
33 enum TemplateDeductionFlags {
34 /// \brief No template argument deduction flags, which indicates the
35 /// strictest results for template argument deduction (as used for, e.g.,
36 /// matching class template partial specializations).
37 TDF_None = 0,
38 /// \brief Within template argument deduction from a function call, we are
39 /// matching with a parameter type for which the original parameter was
40 /// a reference.
41 TDF_ParamWithReferenceType = 0x1,
42 /// \brief Within template argument deduction from a function call, we
43 /// are matching in a case where we ignore cv-qualifiers.
44 TDF_IgnoreQualifiers = 0x02,
45 /// \brief Within template argument deduction from a function call,
46 /// we are matching in a case where we can perform template argument
Douglas Gregor41128772009-06-26 23:27:24 +000047 /// deduction from a template-id of a derived class of the argument type.
Douglas Gregor12820292009-09-14 20:00:47 +000048 TDF_DerivedClass = 0x04,
49 /// \brief Allow non-dependent types to differ, e.g., when performing
50 /// template argument deduction from a function call where conversions
51 /// may apply.
52 TDF_SkipNonDependent = 0x08
Douglas Gregor508f1c82009-06-26 23:10:12 +000053 };
54}
55
Douglas Gregor0b9247f2009-06-04 00:03:07 +000056using namespace clang;
57
Douglas Gregor9d0e4412010-03-26 05:50:28 +000058/// \brief Compare two APSInts, extending and switching the sign as
59/// necessary to compare their values regardless of underlying type.
60static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
61 if (Y.getBitWidth() > X.getBitWidth())
Jay Foad9f71a8f2010-12-07 08:25:34 +000062 X = X.extend(Y.getBitWidth());
Douglas Gregor9d0e4412010-03-26 05:50:28 +000063 else if (Y.getBitWidth() < X.getBitWidth())
Jay Foad9f71a8f2010-12-07 08:25:34 +000064 Y = Y.extend(X.getBitWidth());
Douglas Gregor9d0e4412010-03-26 05:50:28 +000065
66 // If there is a signedness mismatch, correct it.
67 if (X.isSigned() != Y.isSigned()) {
68 // If the signed value is negative, then the values cannot be the same.
69 if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
70 return false;
71
72 Y.setIsSigned(true);
73 X.setIsSigned(true);
74 }
75
76 return X == Y;
77}
78
Douglas Gregorf67875d2009-06-12 18:26:56 +000079static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +000080DeduceTemplateArguments(Sema &S,
Douglas Gregorf67875d2009-06-12 18:26:56 +000081 TemplateParameterList *TemplateParams,
82 const TemplateArgument &Param,
Douglas Gregor77d6bb92011-01-11 22:21:24 +000083 TemplateArgument Arg,
John McCall2a7fb272010-08-25 05:32:35 +000084 TemplateDeductionInfo &Info,
Douglas Gregor0972c862010-12-22 18:55:49 +000085 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced);
Douglas Gregord708c722009-06-09 16:35:58 +000086
Douglas Gregor5c7bf422011-01-11 17:34:58 +000087/// \brief Stores the result of comparing the qualifiers of two types, used
88/// when
89enum DeductionQualifierComparison {
90 NeitherMoreQualified = 0,
91 ParamMoreQualified,
92 ArgMoreQualified
93};
94
95
Douglas Gregor20a55e22010-12-22 18:17:10 +000096static Sema::TemplateDeductionResult
97DeduceTemplateArguments(Sema &S,
98 TemplateParameterList *TemplateParams,
Douglas Gregor603cfb42011-01-05 23:12:31 +000099 QualType Param,
100 QualType Arg,
101 TemplateDeductionInfo &Info,
102 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000103 unsigned TDF,
104 bool PartialOrdering = false,
105 llvm::SmallVectorImpl<DeductionQualifierComparison> *
106 QualifierComparisons = 0);
Douglas Gregor603cfb42011-01-05 23:12:31 +0000107
108static Sema::TemplateDeductionResult
109DeduceTemplateArguments(Sema &S,
110 TemplateParameterList *TemplateParams,
Douglas Gregor20a55e22010-12-22 18:17:10 +0000111 const TemplateArgument *Params, unsigned NumParams,
112 const TemplateArgument *Args, unsigned NumArgs,
113 TemplateDeductionInfo &Info,
Douglas Gregor0972c862010-12-22 18:55:49 +0000114 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
115 bool NumberOfArgumentsMustMatch = true);
Douglas Gregor20a55e22010-12-22 18:17:10 +0000116
Douglas Gregor199d9912009-06-05 00:53:49 +0000117/// \brief If the given expression is of a form that permits the deduction
118/// of a non-type template parameter, return the declaration of that
119/// non-type template parameter.
120static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
121 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
122 E = IC->getSubExpr();
Mike Stump1eb44332009-09-09 15:08:12 +0000123
Douglas Gregor199d9912009-06-05 00:53:49 +0000124 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
125 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
Mike Stump1eb44332009-09-09 15:08:12 +0000126
Douglas Gregor199d9912009-06-05 00:53:49 +0000127 return 0;
128}
129
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000130/// \brief Determine whether two declaration pointers refer to the same
131/// declaration.
132static bool isSameDeclaration(Decl *X, Decl *Y) {
133 if (!X || !Y)
134 return !X && !Y;
135
136 if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
137 X = NX->getUnderlyingDecl();
138 if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
139 Y = NY->getUnderlyingDecl();
140
141 return X->getCanonicalDecl() == Y->getCanonicalDecl();
142}
143
144/// \brief Verify that the given, deduced template arguments are compatible.
145///
146/// \returns The deduced template argument, or a NULL template argument if
147/// the deduced template arguments were incompatible.
148static DeducedTemplateArgument
149checkDeducedTemplateArguments(ASTContext &Context,
150 const DeducedTemplateArgument &X,
151 const DeducedTemplateArgument &Y) {
152 // We have no deduction for one or both of the arguments; they're compatible.
153 if (X.isNull())
154 return Y;
155 if (Y.isNull())
156 return X;
157
158 switch (X.getKind()) {
159 case TemplateArgument::Null:
160 llvm_unreachable("Non-deduced template arguments handled above");
161
162 case TemplateArgument::Type:
163 // If two template type arguments have the same type, they're compatible.
164 if (Y.getKind() == TemplateArgument::Type &&
165 Context.hasSameType(X.getAsType(), Y.getAsType()))
166 return X;
167
168 return DeducedTemplateArgument();
169
170 case TemplateArgument::Integral:
171 // If we deduced a constant in one case and either a dependent expression or
172 // declaration in another case, keep the integral constant.
173 // If both are integral constants with the same value, keep that value.
174 if (Y.getKind() == TemplateArgument::Expression ||
175 Y.getKind() == TemplateArgument::Declaration ||
176 (Y.getKind() == TemplateArgument::Integral &&
177 hasSameExtendedValue(*X.getAsIntegral(), *Y.getAsIntegral())))
178 return DeducedTemplateArgument(X,
179 X.wasDeducedFromArrayBound() &&
180 Y.wasDeducedFromArrayBound());
181
182 // All other combinations are incompatible.
183 return DeducedTemplateArgument();
184
185 case TemplateArgument::Template:
186 if (Y.getKind() == TemplateArgument::Template &&
187 Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
188 return X;
189
190 // All other combinations are incompatible.
191 return DeducedTemplateArgument();
Douglas Gregora7fc9012011-01-05 18:58:31 +0000192
193 case TemplateArgument::TemplateExpansion:
194 if (Y.getKind() == TemplateArgument::TemplateExpansion &&
195 Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
196 Y.getAsTemplateOrTemplatePattern()))
197 return X;
198
199 // All other combinations are incompatible.
200 return DeducedTemplateArgument();
201
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000202 case TemplateArgument::Expression:
203 // If we deduced a dependent expression in one case and either an integral
204 // constant or a declaration in another case, keep the integral constant
205 // or declaration.
206 if (Y.getKind() == TemplateArgument::Integral ||
207 Y.getKind() == TemplateArgument::Declaration)
208 return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
209 Y.wasDeducedFromArrayBound());
210
211 if (Y.getKind() == TemplateArgument::Expression) {
212 // Compare the expressions for equality
213 llvm::FoldingSetNodeID ID1, ID2;
214 X.getAsExpr()->Profile(ID1, Context, true);
215 Y.getAsExpr()->Profile(ID2, Context, true);
216 if (ID1 == ID2)
217 return X;
218 }
219
220 // All other combinations are incompatible.
221 return DeducedTemplateArgument();
222
223 case TemplateArgument::Declaration:
224 // If we deduced a declaration and a dependent expression, keep the
225 // declaration.
226 if (Y.getKind() == TemplateArgument::Expression)
227 return X;
228
229 // If we deduced a declaration and an integral constant, keep the
230 // integral constant.
231 if (Y.getKind() == TemplateArgument::Integral)
232 return Y;
233
234 // If we deduced two declarations, make sure they they refer to the
235 // same declaration.
236 if (Y.getKind() == TemplateArgument::Declaration &&
237 isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
238 return X;
239
240 // All other combinations are incompatible.
241 return DeducedTemplateArgument();
242
243 case TemplateArgument::Pack:
244 if (Y.getKind() != TemplateArgument::Pack ||
245 X.pack_size() != Y.pack_size())
246 return DeducedTemplateArgument();
247
248 for (TemplateArgument::pack_iterator XA = X.pack_begin(),
249 XAEnd = X.pack_end(),
250 YA = Y.pack_begin();
251 XA != XAEnd; ++XA, ++YA) {
Douglas Gregor135ffa72011-01-05 21:00:53 +0000252 if (checkDeducedTemplateArguments(Context,
253 DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
254 DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
255 .isNull())
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000256 return DeducedTemplateArgument();
257 }
258
259 return X;
260 }
261
262 return DeducedTemplateArgument();
263}
264
Mike Stump1eb44332009-09-09 15:08:12 +0000265/// \brief Deduce the value of the given non-type template parameter
Douglas Gregor199d9912009-06-05 00:53:49 +0000266/// from the given constant.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000267static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000268DeduceNonTypeTemplateArgument(Sema &S,
Mike Stump1eb44332009-09-09 15:08:12 +0000269 NonTypeTemplateParmDecl *NTTP,
Douglas Gregor9d0e4412010-03-26 05:50:28 +0000270 llvm::APSInt Value, QualType ValueType,
Douglas Gregor02024a92010-03-28 02:42:43 +0000271 bool DeducedFromArrayBound,
John McCall2a7fb272010-08-25 05:32:35 +0000272 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000273 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Mike Stump1eb44332009-09-09 15:08:12 +0000274 assert(NTTP->getDepth() == 0 &&
Douglas Gregor199d9912009-06-05 00:53:49 +0000275 "Cannot deduce non-type template argument with depth > 0");
Mike Stump1eb44332009-09-09 15:08:12 +0000276
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000277 DeducedTemplateArgument NewDeduced(Value, ValueType, DeducedFromArrayBound);
278 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
279 Deduced[NTTP->getIndex()],
280 NewDeduced);
281 if (Result.isNull()) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000282 Info.Param = NTTP;
283 Info.FirstArg = Deduced[NTTP->getIndex()];
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000284 Info.SecondArg = NewDeduced;
285 return Sema::TDK_Inconsistent;
Douglas Gregorf67875d2009-06-12 18:26:56 +0000286 }
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000287
288 Deduced[NTTP->getIndex()] = Result;
Douglas Gregorf67875d2009-06-12 18:26:56 +0000289 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000290}
291
Mike Stump1eb44332009-09-09 15:08:12 +0000292/// \brief Deduce the value of the given non-type template parameter
Douglas Gregor199d9912009-06-05 00:53:49 +0000293/// from the given type- or value-dependent expression.
294///
295/// \returns true if deduction succeeded, false otherwise.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000296static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000297DeduceNonTypeTemplateArgument(Sema &S,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000298 NonTypeTemplateParmDecl *NTTP,
299 Expr *Value,
John McCall2a7fb272010-08-25 05:32:35 +0000300 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000301 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Mike Stump1eb44332009-09-09 15:08:12 +0000302 assert(NTTP->getDepth() == 0 &&
Douglas Gregor199d9912009-06-05 00:53:49 +0000303 "Cannot deduce non-type template argument with depth > 0");
304 assert((Value->isTypeDependent() || Value->isValueDependent()) &&
305 "Expression template argument must be type- or value-dependent.");
Mike Stump1eb44332009-09-09 15:08:12 +0000306
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000307 DeducedTemplateArgument NewDeduced(Value);
308 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
309 Deduced[NTTP->getIndex()],
310 NewDeduced);
311
312 if (Result.isNull()) {
313 Info.Param = NTTP;
314 Info.FirstArg = Deduced[NTTP->getIndex()];
315 Info.SecondArg = NewDeduced;
316 return Sema::TDK_Inconsistent;
Douglas Gregor199d9912009-06-05 00:53:49 +0000317 }
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000318
319 Deduced[NTTP->getIndex()] = Result;
Douglas Gregorf67875d2009-06-12 18:26:56 +0000320 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000321}
322
Douglas Gregor15755cb2009-11-13 23:45:44 +0000323/// \brief Deduce the value of the given non-type template parameter
324/// from the given declaration.
325///
326/// \returns true if deduction succeeded, false otherwise.
327static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000328DeduceNonTypeTemplateArgument(Sema &S,
Douglas Gregor15755cb2009-11-13 23:45:44 +0000329 NonTypeTemplateParmDecl *NTTP,
330 Decl *D,
John McCall2a7fb272010-08-25 05:32:35 +0000331 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000332 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Douglas Gregor15755cb2009-11-13 23:45:44 +0000333 assert(NTTP->getDepth() == 0 &&
334 "Cannot deduce non-type template argument with depth > 0");
335
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000336 DeducedTemplateArgument NewDeduced(D? D->getCanonicalDecl() : 0);
337 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
338 Deduced[NTTP->getIndex()],
339 NewDeduced);
340 if (Result.isNull()) {
341 Info.Param = NTTP;
342 Info.FirstArg = Deduced[NTTP->getIndex()];
343 Info.SecondArg = NewDeduced;
344 return Sema::TDK_Inconsistent;
Douglas Gregor15755cb2009-11-13 23:45:44 +0000345 }
346
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000347 Deduced[NTTP->getIndex()] = Result;
Douglas Gregor15755cb2009-11-13 23:45:44 +0000348 return Sema::TDK_Success;
349}
350
Douglas Gregorf67875d2009-06-12 18:26:56 +0000351static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000352DeduceTemplateArguments(Sema &S,
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000353 TemplateParameterList *TemplateParams,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000354 TemplateName Param,
355 TemplateName Arg,
John McCall2a7fb272010-08-25 05:32:35 +0000356 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000357 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Douglas Gregord708c722009-06-09 16:35:58 +0000358 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000359 if (!ParamDecl) {
360 // The parameter type is dependent and is not a template template parameter,
361 // so there is nothing that we can deduce.
362 return Sema::TDK_Success;
363 }
364
365 if (TemplateTemplateParmDecl *TempParam
366 = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000367 DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
368 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
369 Deduced[TempParam->getIndex()],
370 NewDeduced);
371 if (Result.isNull()) {
372 Info.Param = TempParam;
373 Info.FirstArg = Deduced[TempParam->getIndex()];
374 Info.SecondArg = NewDeduced;
375 return Sema::TDK_Inconsistent;
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000376 }
377
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000378 Deduced[TempParam->getIndex()] = Result;
379 return Sema::TDK_Success;
Douglas Gregorf67875d2009-06-12 18:26:56 +0000380 }
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000381
382 // Verify that the two template names are equivalent.
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000383 if (S.Context.hasSameTemplateName(Param, Arg))
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000384 return Sema::TDK_Success;
385
386 // Mismatch of non-dependent template parameter to argument.
387 Info.FirstArg = TemplateArgument(Param);
388 Info.SecondArg = TemplateArgument(Arg);
389 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord708c722009-06-09 16:35:58 +0000390}
391
Mike Stump1eb44332009-09-09 15:08:12 +0000392/// \brief Deduce the template arguments by comparing the template parameter
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000393/// type (which is a template-id) with the template argument type.
394///
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000395/// \param S the Sema
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000396///
397/// \param TemplateParams the template parameters that we are deducing
398///
399/// \param Param the parameter type
400///
401/// \param Arg the argument type
402///
403/// \param Info information about the template argument deduction itself
404///
405/// \param Deduced the deduced template arguments
406///
407/// \returns the result of template argument deduction so far. Note that a
408/// "success" result means that template argument deduction has not yet failed,
409/// but it may still fail, later, for other reasons.
410static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000411DeduceTemplateArguments(Sema &S,
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000412 TemplateParameterList *TemplateParams,
413 const TemplateSpecializationType *Param,
414 QualType Arg,
John McCall2a7fb272010-08-25 05:32:35 +0000415 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000416 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
John McCall467b27b2009-10-22 20:10:53 +0000417 assert(Arg.isCanonical() && "Argument type must be canonical");
Mike Stump1eb44332009-09-09 15:08:12 +0000418
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000419 // Check whether the template argument is a dependent template-id.
Mike Stump1eb44332009-09-09 15:08:12 +0000420 if (const TemplateSpecializationType *SpecArg
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000421 = dyn_cast<TemplateSpecializationType>(Arg)) {
422 // Perform template argument deduction for the template name.
423 if (Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000424 = DeduceTemplateArguments(S, TemplateParams,
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000425 Param->getTemplateName(),
426 SpecArg->getTemplateName(),
427 Info, Deduced))
428 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +0000429
Mike Stump1eb44332009-09-09 15:08:12 +0000430
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000431 // Perform template argument deduction on each template
Douglas Gregor0972c862010-12-22 18:55:49 +0000432 // argument. Ignore any missing/extra arguments, since they could be
433 // filled in by default arguments.
Douglas Gregor20a55e22010-12-22 18:17:10 +0000434 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregor0972c862010-12-22 18:55:49 +0000435 Param->getArgs(), Param->getNumArgs(),
436 SpecArg->getArgs(), SpecArg->getNumArgs(),
437 Info, Deduced,
438 /*NumberOfArgumentsMustMatch=*/false);
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000439 }
Mike Stump1eb44332009-09-09 15:08:12 +0000440
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000441 // If the argument type is a class template specialization, we
442 // perform template argument deduction using its template
443 // arguments.
444 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
445 if (!RecordArg)
446 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +0000447
448 ClassTemplateSpecializationDecl *SpecArg
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000449 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
450 if (!SpecArg)
451 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +0000452
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000453 // Perform template argument deduction for the template name.
454 if (Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000455 = DeduceTemplateArguments(S,
Douglas Gregordb0d4b72009-11-11 23:06:43 +0000456 TemplateParams,
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000457 Param->getTemplateName(),
458 TemplateName(SpecArg->getSpecializedTemplate()),
459 Info, Deduced))
460 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +0000461
Douglas Gregor20a55e22010-12-22 18:17:10 +0000462 // Perform template argument deduction for the template arguments.
463 return DeduceTemplateArguments(S, TemplateParams,
464 Param->getArgs(), Param->getNumArgs(),
465 SpecArg->getTemplateArgs().data(),
466 SpecArg->getTemplateArgs().size(),
467 Info, Deduced);
Douglas Gregorde0cb8b2009-07-07 23:09:34 +0000468}
469
John McCallcd05e812010-08-28 22:14:41 +0000470/// \brief Determines whether the given type is an opaque type that
471/// might be more qualified when instantiated.
472static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
473 switch (T->getTypeClass()) {
474 case Type::TypeOfExpr:
475 case Type::TypeOf:
476 case Type::DependentName:
477 case Type::Decltype:
478 case Type::UnresolvedUsing:
479 return true;
480
481 case Type::ConstantArray:
482 case Type::IncompleteArray:
483 case Type::VariableArray:
484 case Type::DependentSizedArray:
485 return IsPossiblyOpaquelyQualifiedType(
486 cast<ArrayType>(T)->getElementType());
487
488 default:
489 return false;
490 }
491}
492
Douglas Gregord3731192011-01-10 07:32:04 +0000493/// \brief Retrieve the depth and index of a template parameter.
Douglas Gregor603cfb42011-01-05 23:12:31 +0000494static std::pair<unsigned, unsigned>
Douglas Gregord3731192011-01-10 07:32:04 +0000495getDepthAndIndex(NamedDecl *ND) {
Douglas Gregor603cfb42011-01-05 23:12:31 +0000496 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
497 return std::make_pair(TTP->getDepth(), TTP->getIndex());
498
499 if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
500 return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
501
502 TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
503 return std::make_pair(TTP->getDepth(), TTP->getIndex());
504}
505
Douglas Gregord3731192011-01-10 07:32:04 +0000506/// \brief Retrieve the depth and index of an unexpanded parameter pack.
507static std::pair<unsigned, unsigned>
508getDepthAndIndex(UnexpandedParameterPack UPP) {
509 if (const TemplateTypeParmType *TTP
510 = UPP.first.dyn_cast<const TemplateTypeParmType *>())
511 return std::make_pair(TTP->getDepth(), TTP->getIndex());
512
513 return getDepthAndIndex(UPP.first.get<NamedDecl *>());
514}
515
Douglas Gregor603cfb42011-01-05 23:12:31 +0000516/// \brief Helper function to build a TemplateParameter when we don't
517/// know its type statically.
518static TemplateParameter makeTemplateParameter(Decl *D) {
519 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
520 return TemplateParameter(TTP);
521 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
522 return TemplateParameter(NTTP);
523
524 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
525}
526
Douglas Gregor54293852011-01-10 17:35:05 +0000527/// \brief Prepare to perform template argument deduction for all of the
528/// arguments in a set of argument packs.
529static void PrepareArgumentPackDeduction(Sema &S,
530 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
531 const llvm::SmallVectorImpl<unsigned> &PackIndices,
532 llvm::SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
533 llvm::SmallVectorImpl<
534 llvm::SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks) {
535 // Save the deduced template arguments for each parameter pack expanded
536 // by this pack expansion, then clear out the deduction.
537 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
538 // Save the previously-deduced argument pack, then clear it out so that we
539 // can deduce a new argument pack.
540 SavedPacks[I] = Deduced[PackIndices[I]];
541 Deduced[PackIndices[I]] = TemplateArgument();
542
543 // If the template arugment pack was explicitly specified, add that to
544 // the set of deduced arguments.
545 const TemplateArgument *ExplicitArgs;
546 unsigned NumExplicitArgs;
547 if (NamedDecl *PartiallySubstitutedPack
548 = S.CurrentInstantiationScope->getPartiallySubstitutedPack(
549 &ExplicitArgs,
550 &NumExplicitArgs)) {
551 if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I])
552 NewlyDeducedPacks[I].append(ExplicitArgs,
553 ExplicitArgs + NumExplicitArgs);
554 }
555 }
556}
557
Douglas Gregor0216f812011-01-10 17:53:52 +0000558/// \brief Finish template argument deduction for a set of argument packs,
559/// producing the argument packs and checking for consistency with prior
560/// deductions.
561static Sema::TemplateDeductionResult
562FinishArgumentPackDeduction(Sema &S,
563 TemplateParameterList *TemplateParams,
564 bool HasAnyArguments,
565 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
566 const llvm::SmallVectorImpl<unsigned> &PackIndices,
567 llvm::SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
568 llvm::SmallVectorImpl<
569 llvm::SmallVector<DeducedTemplateArgument, 4> > &NewlyDeducedPacks,
570 TemplateDeductionInfo &Info) {
571 // Build argument packs for each of the parameter packs expanded by this
572 // pack expansion.
573 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
574 if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
575 // We were not able to deduce anything for this parameter pack,
576 // so just restore the saved argument pack.
577 Deduced[PackIndices[I]] = SavedPacks[I];
578 continue;
579 }
580
581 DeducedTemplateArgument NewPack;
582
583 if (NewlyDeducedPacks[I].empty()) {
584 // If we deduced an empty argument pack, create it now.
585 NewPack = DeducedTemplateArgument(TemplateArgument(0, 0));
586 } else {
587 TemplateArgument *ArgumentPack
Douglas Gregor203e6a32011-01-11 23:09:57 +0000588 = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
Douglas Gregor0216f812011-01-10 17:53:52 +0000589 std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
590 ArgumentPack);
591 NewPack
Douglas Gregor203e6a32011-01-11 23:09:57 +0000592 = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
593 NewlyDeducedPacks[I].size()),
594 NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
Douglas Gregor0216f812011-01-10 17:53:52 +0000595 }
596
597 DeducedTemplateArgument Result
598 = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack);
599 if (Result.isNull()) {
600 Info.Param
601 = makeTemplateParameter(TemplateParams->getParam(PackIndices[I]));
602 Info.FirstArg = SavedPacks[I];
603 Info.SecondArg = NewPack;
604 return Sema::TDK_Inconsistent;
605 }
606
607 Deduced[PackIndices[I]] = Result;
608 }
609
610 return Sema::TDK_Success;
611}
612
Douglas Gregor603cfb42011-01-05 23:12:31 +0000613/// \brief Deduce the template arguments by comparing the list of parameter
614/// types to the list of argument types, as in the parameter-type-lists of
615/// function types (C++ [temp.deduct.type]p10).
616///
617/// \param S The semantic analysis object within which we are deducing
618///
619/// \param TemplateParams The template parameters that we are deducing
620///
621/// \param Params The list of parameter types
622///
623/// \param NumParams The number of types in \c Params
624///
625/// \param Args The list of argument types
626///
627/// \param NumArgs The number of types in \c Args
628///
629/// \param Info information about the template argument deduction itself
630///
631/// \param Deduced the deduced template arguments
632///
633/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
634/// how template argument deduction is performed.
635///
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000636/// \param PartialOrdering If true, we are performing template argument
637/// deduction for during partial ordering for a call
638/// (C++0x [temp.deduct.partial]).
639///
640/// \param QualifierComparisons If we're performing template argument deduction
641/// in the context of partial ordering, the set of qualifier comparisons.
642///
Douglas Gregor603cfb42011-01-05 23:12:31 +0000643/// \returns the result of template argument deduction so far. Note that a
644/// "success" result means that template argument deduction has not yet failed,
645/// but it may still fail, later, for other reasons.
646static Sema::TemplateDeductionResult
647DeduceTemplateArguments(Sema &S,
648 TemplateParameterList *TemplateParams,
649 const QualType *Params, unsigned NumParams,
650 const QualType *Args, unsigned NumArgs,
651 TemplateDeductionInfo &Info,
652 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000653 unsigned TDF,
654 bool PartialOrdering = false,
655 llvm::SmallVectorImpl<DeductionQualifierComparison> *
656 QualifierComparisons = 0) {
Douglas Gregor0bbacf82011-01-05 23:23:17 +0000657 // Fast-path check to see if we have too many/too few arguments.
658 if (NumParams != NumArgs &&
659 !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
660 !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
Douglas Gregor3cae5c92011-01-10 20:53:55 +0000661 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor603cfb42011-01-05 23:12:31 +0000662
663 // C++0x [temp.deduct.type]p10:
664 // Similarly, if P has a form that contains (T), then each parameter type
665 // Pi of the respective parameter-type- list of P is compared with the
666 // corresponding parameter type Ai of the corresponding parameter-type-list
667 // of A. [...]
668 unsigned ArgIdx = 0, ParamIdx = 0;
669 for (; ParamIdx != NumParams; ++ParamIdx) {
670 // Check argument types.
671 const PackExpansionType *Expansion
672 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
673 if (!Expansion) {
674 // Simple case: compare the parameter and argument types at this point.
675
676 // Make sure we have an argument.
677 if (ArgIdx >= NumArgs)
Douglas Gregor3cae5c92011-01-10 20:53:55 +0000678 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor603cfb42011-01-05 23:12:31 +0000679
Douglas Gregor77d6bb92011-01-11 22:21:24 +0000680 if (isa<PackExpansionType>(Args[ArgIdx])) {
681 // C++0x [temp.deduct.type]p22:
682 // If the original function parameter associated with A is a function
683 // parameter pack and the function parameter associated with P is not
684 // a function parameter pack, then template argument deduction fails.
685 return Sema::TDK_NonDeducedMismatch;
686 }
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000687
Douglas Gregor603cfb42011-01-05 23:12:31 +0000688 if (Sema::TemplateDeductionResult Result
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000689 = DeduceTemplateArguments(S, TemplateParams,
690 Params[ParamIdx],
691 Args[ArgIdx],
692 Info, Deduced, TDF,
693 PartialOrdering,
694 QualifierComparisons))
Douglas Gregor603cfb42011-01-05 23:12:31 +0000695 return Result;
696
697 ++ArgIdx;
698 continue;
699 }
700
Douglas Gregor7d5c0c12011-01-11 01:52:23 +0000701 // C++0x [temp.deduct.type]p5:
702 // The non-deduced contexts are:
703 // - A function parameter pack that does not occur at the end of the
704 // parameter-declaration-clause.
705 if (ParamIdx + 1 < NumParams)
706 return Sema::TDK_Success;
707
Douglas Gregor603cfb42011-01-05 23:12:31 +0000708 // C++0x [temp.deduct.type]p10:
709 // If the parameter-declaration corresponding to Pi is a function
710 // parameter pack, then the type of its declarator- id is compared with
711 // each remaining parameter type in the parameter-type-list of A. Each
712 // comparison deduces template arguments for subsequent positions in the
713 // template parameter packs expanded by the function parameter pack.
714
715 // Compute the set of template parameter indices that correspond to
716 // parameter packs expanded by the pack expansion.
717 llvm::SmallVector<unsigned, 2> PackIndices;
718 QualType Pattern = Expansion->getPattern();
719 {
720 llvm::BitVector SawIndices(TemplateParams->size());
721 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
722 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
723 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
724 unsigned Depth, Index;
725 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
726 if (Depth == 0 && !SawIndices[Index]) {
727 SawIndices[Index] = true;
728 PackIndices.push_back(Index);
729 }
730 }
731 }
732 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
733
Douglas Gregord3731192011-01-10 07:32:04 +0000734 // Keep track of the deduced template arguments for each parameter pack
735 // expanded by this pack expansion (the outer index) and for each
736 // template argument (the inner SmallVectors).
737 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
738 NewlyDeducedPacks(PackIndices.size());
Douglas Gregor603cfb42011-01-05 23:12:31 +0000739 llvm::SmallVector<DeducedTemplateArgument, 2>
Douglas Gregor54293852011-01-10 17:35:05 +0000740 SavedPacks(PackIndices.size());
741 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
742 NewlyDeducedPacks);
Douglas Gregor603cfb42011-01-05 23:12:31 +0000743
Douglas Gregor603cfb42011-01-05 23:12:31 +0000744 bool HasAnyArguments = false;
745 for (; ArgIdx < NumArgs; ++ArgIdx) {
746 HasAnyArguments = true;
747
748 // Deduce template arguments from the pattern.
749 if (Sema::TemplateDeductionResult Result
750 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000751 Info, Deduced, PartialOrdering,
752 QualifierComparisons))
Douglas Gregor603cfb42011-01-05 23:12:31 +0000753 return Result;
754
755 // Capture the deduced template arguments for each parameter pack expanded
756 // by this pack expansion, add them to the list of arguments we've deduced
757 // for that pack, then clear out the deduced argument.
758 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
759 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
760 if (!DeducedArg.isNull()) {
761 NewlyDeducedPacks[I].push_back(DeducedArg);
762 DeducedArg = DeducedTemplateArgument();
763 }
764 }
765 }
766
767 // Build argument packs for each of the parameter packs expanded by this
768 // pack expansion.
Douglas Gregor0216f812011-01-10 17:53:52 +0000769 if (Sema::TemplateDeductionResult Result
770 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
771 Deduced, PackIndices, SavedPacks,
772 NewlyDeducedPacks, Info))
773 return Result;
Douglas Gregor603cfb42011-01-05 23:12:31 +0000774 }
775
776 // Make sure we don't have any extra arguments.
777 if (ArgIdx < NumArgs)
Douglas Gregor3cae5c92011-01-10 20:53:55 +0000778 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor603cfb42011-01-05 23:12:31 +0000779
780 return Sema::TDK_Success;
781}
782
Douglas Gregor500d3312009-06-26 18:27:22 +0000783/// \brief Deduce the template arguments by comparing the parameter type and
784/// the argument type (C++ [temp.deduct.type]).
785///
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000786/// \param S the semantic analysis object within which we are deducing
Douglas Gregor500d3312009-06-26 18:27:22 +0000787///
788/// \param TemplateParams the template parameters that we are deducing
789///
790/// \param ParamIn the parameter type
791///
792/// \param ArgIn the argument type
793///
794/// \param Info information about the template argument deduction itself
795///
796/// \param Deduced the deduced template arguments
797///
Douglas Gregor508f1c82009-06-26 23:10:12 +0000798/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
Mike Stump1eb44332009-09-09 15:08:12 +0000799/// how template argument deduction is performed.
Douglas Gregor500d3312009-06-26 18:27:22 +0000800///
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000801/// \param PartialOrdering Whether we're performing template argument deduction
802/// in the context of partial ordering (C++0x [temp.deduct.partial]).
803///
804/// \param QualifierComparisons If we're performing template argument deduction
805/// in the context of partial ordering, the set of qualifier comparisons.
806///
Douglas Gregor500d3312009-06-26 18:27:22 +0000807/// \returns the result of template argument deduction so far. Note that a
808/// "success" result means that template argument deduction has not yet failed,
809/// but it may still fail, later, for other reasons.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000810static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000811DeduceTemplateArguments(Sema &S,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000812 TemplateParameterList *TemplateParams,
813 QualType ParamIn, QualType ArgIn,
John McCall2a7fb272010-08-25 05:32:35 +0000814 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +0000815 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000816 unsigned TDF,
817 bool PartialOrdering,
818 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) {
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000819 // We only want to look at the canonical types, since typedefs and
820 // sugar are not part of template argument deduction.
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000821 QualType Param = S.Context.getCanonicalType(ParamIn);
822 QualType Arg = S.Context.getCanonicalType(ArgIn);
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000823
Douglas Gregor77d6bb92011-01-11 22:21:24 +0000824 // If the argument type is a pack expansion, look at its pattern.
825 // This isn't explicitly called out
826 if (const PackExpansionType *ArgExpansion
827 = dyn_cast<PackExpansionType>(Arg))
828 Arg = ArgExpansion->getPattern();
829
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000830 if (PartialOrdering) {
831 // C++0x [temp.deduct.partial]p5:
832 // Before the partial ordering is done, certain transformations are
833 // performed on the types used for partial ordering:
834 // - If P is a reference type, P is replaced by the type referred to.
835 const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
836 if (ParamRef)
837 Param = ParamRef->getPointeeType();
838
839 // - If A is a reference type, A is replaced by the type referred to.
840 const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
841 if (ArgRef)
842 Arg = ArgRef->getPointeeType();
843
844 if (QualifierComparisons && ParamRef && ArgRef) {
845 // C++0x [temp.deduct.partial]p6:
846 // If both P and A were reference types (before being replaced with the
847 // type referred to above), determine which of the two types (if any) is
848 // more cv-qualified than the other; otherwise the types are considered
849 // to be equally cv-qualified for partial ordering purposes. The result
850 // of this determination will be used below.
851 //
852 // We save this information for later, using it only when deduction
853 // succeeds in both directions.
854 DeductionQualifierComparison QualifierResult = NeitherMoreQualified;
855 if (Param.isMoreQualifiedThan(Arg))
856 QualifierResult = ParamMoreQualified;
857 else if (Arg.isMoreQualifiedThan(Param))
858 QualifierResult = ArgMoreQualified;
859 QualifierComparisons->push_back(QualifierResult);
860 }
861
862 // C++0x [temp.deduct.partial]p7:
863 // Remove any top-level cv-qualifiers:
864 // - If P is a cv-qualified type, P is replaced by the cv-unqualified
865 // version of P.
866 Param = Param.getUnqualifiedType();
867 // - If A is a cv-qualified type, A is replaced by the cv-unqualified
868 // version of A.
869 Arg = Arg.getUnqualifiedType();
870 } else {
871 // C++0x [temp.deduct.call]p4 bullet 1:
872 // - If the original P is a reference type, the deduced A (i.e., the type
873 // referred to by the reference) can be more cv-qualified than the
874 // transformed A.
875 if (TDF & TDF_ParamWithReferenceType) {
876 Qualifiers Quals;
877 QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
878 Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
879 Arg.getCVRQualifiersThroughArrayTypes());
880 Param = S.Context.getQualifiedType(UnqualParam, Quals);
881 }
Douglas Gregor500d3312009-06-26 18:27:22 +0000882 }
Douglas Gregor5c7bf422011-01-11 17:34:58 +0000883
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000884 // If the parameter type is not dependent, there is nothing to deduce.
Douglas Gregor12820292009-09-14 20:00:47 +0000885 if (!Param->isDependentType()) {
Douglas Gregor3cae5c92011-01-10 20:53:55 +0000886 if (!(TDF & TDF_SkipNonDependent) && Param != Arg)
Douglas Gregor12820292009-09-14 20:00:47 +0000887 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor12820292009-09-14 20:00:47 +0000888
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000889 return Sema::TDK_Success;
Douglas Gregor12820292009-09-14 20:00:47 +0000890 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000891
Douglas Gregor199d9912009-06-05 00:53:49 +0000892 // C++ [temp.deduct.type]p9:
Mike Stump1eb44332009-09-09 15:08:12 +0000893 // A template type argument T, a template template argument TT or a
894 // template non-type argument i can be deduced if P and A have one of
Douglas Gregor199d9912009-06-05 00:53:49 +0000895 // the following forms:
896 //
897 // T
898 // cv-list T
Mike Stump1eb44332009-09-09 15:08:12 +0000899 if (const TemplateTypeParmType *TemplateTypeParm
John McCall183700f2009-09-21 23:43:11 +0000900 = Param->getAs<TemplateTypeParmType>()) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000901 unsigned Index = TemplateTypeParm->getIndex();
Douglas Gregorf290e0d2009-07-22 21:30:48 +0000902 bool RecanonicalizeArg = false;
Mike Stump1eb44332009-09-09 15:08:12 +0000903
Douglas Gregor9e9fae42009-07-22 20:02:25 +0000904 // If the argument type is an array type, move the qualifiers up to the
905 // top level, so they can be matched with the qualifiers on the parameter.
906 // FIXME: address spaces, ObjC GC qualifiers
Douglas Gregorf290e0d2009-07-22 21:30:48 +0000907 if (isa<ArrayType>(Arg)) {
John McCall0953e762009-09-24 19:53:00 +0000908 Qualifiers Quals;
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000909 Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
John McCall0953e762009-09-24 19:53:00 +0000910 if (Quals) {
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000911 Arg = S.Context.getQualifiedType(Arg, Quals);
Douglas Gregorf290e0d2009-07-22 21:30:48 +0000912 RecanonicalizeArg = true;
913 }
914 }
Mike Stump1eb44332009-09-09 15:08:12 +0000915
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000916 // The argument type can not be less qualified than the parameter
917 // type.
Douglas Gregor508f1c82009-06-26 23:10:12 +0000918 if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000919 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
John McCall57e97782010-08-05 09:05:08 +0000920 Info.FirstArg = TemplateArgument(Param);
John McCall833ca992009-10-29 08:12:44 +0000921 Info.SecondArg = TemplateArgument(Arg);
John McCall57e97782010-08-05 09:05:08 +0000922 return Sema::TDK_Underqualified;
Douglas Gregorf67875d2009-06-12 18:26:56 +0000923 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000924
925 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000926 assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
John McCall0953e762009-09-24 19:53:00 +0000927 QualType DeducedType = Arg;
John McCall49f4e1c2010-12-10 11:01:00 +0000928
929 // local manipulation is okay because it's canonical
930 DeducedType.removeLocalCVRQualifiers(Param.getCVRQualifiers());
Douglas Gregorf290e0d2009-07-22 21:30:48 +0000931 if (RecanonicalizeArg)
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000932 DeducedType = S.Context.getCanonicalType(DeducedType);
Mike Stump1eb44332009-09-09 15:08:12 +0000933
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000934 DeducedTemplateArgument NewDeduced(DeducedType);
935 DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
936 Deduced[Index],
937 NewDeduced);
938 if (Result.isNull()) {
939 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
940 Info.FirstArg = Deduced[Index];
941 Info.SecondArg = NewDeduced;
942 return Sema::TDK_Inconsistent;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000943 }
Douglas Gregor0d80abc2010-12-22 23:09:49 +0000944
945 Deduced[Index] = Result;
946 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000947 }
948
Douglas Gregorf67875d2009-06-12 18:26:56 +0000949 // Set up the template argument deduction information for a failure.
John McCall833ca992009-10-29 08:12:44 +0000950 Info.FirstArg = TemplateArgument(ParamIn);
951 Info.SecondArg = TemplateArgument(ArgIn);
Douglas Gregorf67875d2009-06-12 18:26:56 +0000952
Douglas Gregor0bc15d92011-01-14 05:11:40 +0000953 // If the parameter is an already-substituted template parameter
954 // pack, do nothing: we don't know which of its arguments to look
955 // at, so we have to wait until all of the parameter packs in this
956 // expansion have arguments.
957 if (isa<SubstTemplateTypeParmPackType>(Param))
958 return Sema::TDK_Success;
959
Douglas Gregor508f1c82009-06-26 23:10:12 +0000960 // Check the cv-qualifiers on the parameter and argument types.
961 if (!(TDF & TDF_IgnoreQualifiers)) {
962 if (TDF & TDF_ParamWithReferenceType) {
963 if (Param.isMoreQualifiedThan(Arg))
964 return Sema::TDK_NonDeducedMismatch;
John McCallcd05e812010-08-28 22:14:41 +0000965 } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
Douglas Gregor508f1c82009-06-26 23:10:12 +0000966 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
Mike Stump1eb44332009-09-09 15:08:12 +0000967 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor508f1c82009-06-26 23:10:12 +0000968 }
969 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000970
Douglas Gregord560d502009-06-04 00:21:18 +0000971 switch (Param->getTypeClass()) {
Douglas Gregor199d9912009-06-05 00:53:49 +0000972 // No deduction possible for these types
973 case Type::Builtin:
Douglas Gregorf67875d2009-06-12 18:26:56 +0000974 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +0000975
Douglas Gregor199d9912009-06-05 00:53:49 +0000976 // T *
Douglas Gregord560d502009-06-04 00:21:18 +0000977 case Type::Pointer: {
John McCallc0008342010-05-13 07:48:05 +0000978 QualType PointeeType;
979 if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
980 PointeeType = PointerArg->getPointeeType();
981 } else if (const ObjCObjectPointerType *PointerArg
982 = Arg->getAs<ObjCObjectPointerType>()) {
983 PointeeType = PointerArg->getPointeeType();
984 } else {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000985 return Sema::TDK_NonDeducedMismatch;
John McCallc0008342010-05-13 07:48:05 +0000986 }
Mike Stump1eb44332009-09-09 15:08:12 +0000987
Douglas Gregor41128772009-06-26 23:27:24 +0000988 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
Chandler Carrutha7ef1302010-02-07 21:33:28 +0000989 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +0000990 cast<PointerType>(Param)->getPointeeType(),
John McCallc0008342010-05-13 07:48:05 +0000991 PointeeType,
Douglas Gregor41128772009-06-26 23:27:24 +0000992 Info, Deduced, SubTDF);
Douglas Gregord560d502009-06-04 00:21:18 +0000993 }
Mike Stump1eb44332009-09-09 15:08:12 +0000994
Douglas Gregor199d9912009-06-05 00:53:49 +0000995 // T &
Douglas Gregord560d502009-06-04 00:21:18 +0000996 case Type::LValueReference: {
Ted Kremenek6217b802009-07-29 21:53:49 +0000997 const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>();
Douglas Gregord560d502009-06-04 00:21:18 +0000998 if (!ReferenceArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000999 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001000
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001001 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +00001002 cast<LValueReferenceType>(Param)->getPointeeType(),
1003 ReferenceArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +00001004 Info, Deduced, 0);
Douglas Gregord560d502009-06-04 00:21:18 +00001005 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001006
Douglas Gregor199d9912009-06-05 00:53:49 +00001007 // T && [C++0x]
Douglas Gregord560d502009-06-04 00:21:18 +00001008 case Type::RValueReference: {
Ted Kremenek6217b802009-07-29 21:53:49 +00001009 const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>();
Douglas Gregord560d502009-06-04 00:21:18 +00001010 if (!ReferenceArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001011 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001012
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001013 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +00001014 cast<RValueReferenceType>(Param)->getPointeeType(),
1015 ReferenceArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +00001016 Info, Deduced, 0);
Douglas Gregord560d502009-06-04 00:21:18 +00001017 }
Mike Stump1eb44332009-09-09 15:08:12 +00001018
Douglas Gregor199d9912009-06-05 00:53:49 +00001019 // T [] (implied, but not stated explicitly)
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001020 case Type::IncompleteArray: {
Mike Stump1eb44332009-09-09 15:08:12 +00001021 const IncompleteArrayType *IncompleteArrayArg =
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001022 S.Context.getAsIncompleteArrayType(Arg);
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001023 if (!IncompleteArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001024 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001025
John McCalle4f26e52010-08-19 00:20:19 +00001026 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001027 return DeduceTemplateArguments(S, TemplateParams,
1028 S.Context.getAsIncompleteArrayType(Param)->getElementType(),
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001029 IncompleteArrayArg->getElementType(),
John McCalle4f26e52010-08-19 00:20:19 +00001030 Info, Deduced, SubTDF);
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001031 }
Douglas Gregor199d9912009-06-05 00:53:49 +00001032
1033 // T [integer-constant]
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001034 case Type::ConstantArray: {
Mike Stump1eb44332009-09-09 15:08:12 +00001035 const ConstantArrayType *ConstantArrayArg =
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001036 S.Context.getAsConstantArrayType(Arg);
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001037 if (!ConstantArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001038 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001039
1040 const ConstantArrayType *ConstantArrayParm =
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001041 S.Context.getAsConstantArrayType(Param);
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001042 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
Douglas Gregorf67875d2009-06-12 18:26:56 +00001043 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001044
John McCalle4f26e52010-08-19 00:20:19 +00001045 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001046 return DeduceTemplateArguments(S, TemplateParams,
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001047 ConstantArrayParm->getElementType(),
1048 ConstantArrayArg->getElementType(),
John McCalle4f26e52010-08-19 00:20:19 +00001049 Info, Deduced, SubTDF);
Anders Carlsson4d6fb502009-06-04 04:11:30 +00001050 }
1051
Douglas Gregor199d9912009-06-05 00:53:49 +00001052 // type [i]
1053 case Type::DependentSizedArray: {
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001054 const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
Douglas Gregor199d9912009-06-05 00:53:49 +00001055 if (!ArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001056 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001057
John McCalle4f26e52010-08-19 00:20:19 +00001058 unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1059
Douglas Gregor199d9912009-06-05 00:53:49 +00001060 // Check the element type of the arrays
1061 const DependentSizedArrayType *DependentArrayParm
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001062 = S.Context.getAsDependentSizedArrayType(Param);
Douglas Gregorf67875d2009-06-12 18:26:56 +00001063 if (Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001064 = DeduceTemplateArguments(S, TemplateParams,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001065 DependentArrayParm->getElementType(),
1066 ArrayArg->getElementType(),
John McCalle4f26e52010-08-19 00:20:19 +00001067 Info, Deduced, SubTDF))
Douglas Gregorf67875d2009-06-12 18:26:56 +00001068 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +00001069
Douglas Gregor199d9912009-06-05 00:53:49 +00001070 // Determine the array bound is something we can deduce.
Mike Stump1eb44332009-09-09 15:08:12 +00001071 NonTypeTemplateParmDecl *NTTP
Douglas Gregor199d9912009-06-05 00:53:49 +00001072 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1073 if (!NTTP)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001074 return Sema::TDK_Success;
Mike Stump1eb44332009-09-09 15:08:12 +00001075
1076 // We can perform template argument deduction for the given non-type
Douglas Gregor199d9912009-06-05 00:53:49 +00001077 // template parameter.
Mike Stump1eb44332009-09-09 15:08:12 +00001078 assert(NTTP->getDepth() == 0 &&
Douglas Gregor199d9912009-06-05 00:53:49 +00001079 "Cannot deduce non-type template argument at depth > 0");
Mike Stump1eb44332009-09-09 15:08:12 +00001080 if (const ConstantArrayType *ConstantArrayArg
Anders Carlsson335e24a2009-06-16 22:44:31 +00001081 = dyn_cast<ConstantArrayType>(ArrayArg)) {
1082 llvm::APSInt Size(ConstantArrayArg->getSize());
Douglas Gregor9d0e4412010-03-26 05:50:28 +00001083 return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1084 S.Context.getSizeType(),
Douglas Gregor02024a92010-03-28 02:42:43 +00001085 /*ArrayBound=*/true,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001086 Info, Deduced);
Anders Carlsson335e24a2009-06-16 22:44:31 +00001087 }
Douglas Gregor199d9912009-06-05 00:53:49 +00001088 if (const DependentSizedArrayType *DependentArrayArg
1089 = dyn_cast<DependentSizedArrayType>(ArrayArg))
Douglas Gregor34c2f8c2010-12-22 23:15:38 +00001090 if (DependentArrayArg->getSizeExpr())
1091 return DeduceNonTypeTemplateArgument(S, NTTP,
1092 DependentArrayArg->getSizeExpr(),
1093 Info, Deduced);
Mike Stump1eb44332009-09-09 15:08:12 +00001094
Douglas Gregor199d9912009-06-05 00:53:49 +00001095 // Incomplete type does not match a dependently-sized array type
Douglas Gregorf67875d2009-06-12 18:26:56 +00001096 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +00001097 }
Mike Stump1eb44332009-09-09 15:08:12 +00001098
1099 // type(*)(T)
1100 // T(*)()
1101 // T(*)(T)
Anders Carlssona27fad52009-06-08 15:19:08 +00001102 case Type::FunctionProto: {
Mike Stump1eb44332009-09-09 15:08:12 +00001103 const FunctionProtoType *FunctionProtoArg =
Anders Carlssona27fad52009-06-08 15:19:08 +00001104 dyn_cast<FunctionProtoType>(Arg);
1105 if (!FunctionProtoArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001106 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001107
1108 const FunctionProtoType *FunctionProtoParam =
Anders Carlssona27fad52009-06-08 15:19:08 +00001109 cast<FunctionProtoType>(Param);
Anders Carlsson994b6cb2009-06-08 19:22:23 +00001110
Mike Stump1eb44332009-09-09 15:08:12 +00001111 if (FunctionProtoParam->getTypeQuals() !=
Anders Carlsson994b6cb2009-06-08 19:22:23 +00001112 FunctionProtoArg->getTypeQuals())
Douglas Gregorf67875d2009-06-12 18:26:56 +00001113 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001114
Anders Carlsson994b6cb2009-06-08 19:22:23 +00001115 if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
Douglas Gregorf67875d2009-06-12 18:26:56 +00001116 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson994b6cb2009-06-08 19:22:23 +00001117
Anders Carlssona27fad52009-06-08 15:19:08 +00001118 // Check return types.
Douglas Gregorf67875d2009-06-12 18:26:56 +00001119 if (Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001120 = DeduceTemplateArguments(S, TemplateParams,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001121 FunctionProtoParam->getResultType(),
1122 FunctionProtoArg->getResultType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +00001123 Info, Deduced, 0))
Douglas Gregorf67875d2009-06-12 18:26:56 +00001124 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +00001125
Douglas Gregor603cfb42011-01-05 23:12:31 +00001126 return DeduceTemplateArguments(S, TemplateParams,
1127 FunctionProtoParam->arg_type_begin(),
1128 FunctionProtoParam->getNumArgs(),
1129 FunctionProtoArg->arg_type_begin(),
1130 FunctionProtoArg->getNumArgs(),
1131 Info, Deduced, 0);
Anders Carlssona27fad52009-06-08 15:19:08 +00001132 }
Mike Stump1eb44332009-09-09 15:08:12 +00001133
John McCall3cb0ebd2010-03-10 03:28:59 +00001134 case Type::InjectedClassName: {
1135 // Treat a template's injected-class-name as if the template
1136 // specialization type had been used.
John McCall31f17ec2010-04-27 00:57:59 +00001137 Param = cast<InjectedClassNameType>(Param)
1138 ->getInjectedSpecializationType();
John McCall3cb0ebd2010-03-10 03:28:59 +00001139 assert(isa<TemplateSpecializationType>(Param) &&
1140 "injected class name is not a template specialization type");
1141 // fall through
1142 }
1143
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001144 // template-name<T> (where template-name refers to a class template)
Douglas Gregord708c722009-06-09 16:35:58 +00001145 // template-name<i>
Douglas Gregordb0d4b72009-11-11 23:06:43 +00001146 // TT<T>
1147 // TT<i>
1148 // TT<>
Douglas Gregord708c722009-06-09 16:35:58 +00001149 case Type::TemplateSpecialization: {
1150 const TemplateSpecializationType *SpecParam
1151 = cast<TemplateSpecializationType>(Param);
Mike Stump1eb44332009-09-09 15:08:12 +00001152
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001153 // Try to deduce template arguments from the template-id.
1154 Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001155 = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001156 Info, Deduced);
Mike Stump1eb44332009-09-09 15:08:12 +00001157
Douglas Gregor4a5c15f2009-09-30 22:13:51 +00001158 if (Result && (TDF & TDF_DerivedClass)) {
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001159 // C++ [temp.deduct.call]p3b3:
1160 // If P is a class, and P has the form template-id, then A can be a
1161 // derived class of the deduced A. Likewise, if P is a pointer to a
Mike Stump1eb44332009-09-09 15:08:12 +00001162 // class of the form template-id, A can be a pointer to a derived
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001163 // class pointed to by the deduced A.
1164 //
1165 // More importantly:
Mike Stump1eb44332009-09-09 15:08:12 +00001166 // These alternatives are considered only if type deduction would
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001167 // otherwise fail.
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001168 if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1169 // We cannot inspect base classes as part of deduction when the type
1170 // is incomplete, so either instantiate any templates necessary to
1171 // complete the type, or skip over it if it cannot be completed.
John McCall5769d612010-02-08 23:07:23 +00001172 if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001173 return Result;
1174
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001175 // Use data recursion to crawl through the list of base classes.
Mike Stump1eb44332009-09-09 15:08:12 +00001176 // Visited contains the set of nodes we have already visited, while
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001177 // ToVisit is our stack of records that we still need to visit.
1178 llvm::SmallPtrSet<const RecordType *, 8> Visited;
1179 llvm::SmallVector<const RecordType *, 8> ToVisit;
1180 ToVisit.push_back(RecordT);
1181 bool Successful = false;
Douglas Gregor053105d2010-11-02 00:02:34 +00001182 llvm::SmallVectorImpl<DeducedTemplateArgument> DeducedOrig(0);
1183 DeducedOrig = Deduced;
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001184 while (!ToVisit.empty()) {
1185 // Retrieve the next class in the inheritance hierarchy.
1186 const RecordType *NextT = ToVisit.back();
1187 ToVisit.pop_back();
Mike Stump1eb44332009-09-09 15:08:12 +00001188
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001189 // If we have already seen this type, skip it.
1190 if (!Visited.insert(NextT))
1191 continue;
Mike Stump1eb44332009-09-09 15:08:12 +00001192
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001193 // If this is a base class, try to perform template argument
1194 // deduction from it.
1195 if (NextT != RecordT) {
1196 Sema::TemplateDeductionResult BaseResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001197 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001198 QualType(NextT, 0), Info, Deduced);
Mike Stump1eb44332009-09-09 15:08:12 +00001199
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001200 // If template argument deduction for this base was successful,
Douglas Gregor053105d2010-11-02 00:02:34 +00001201 // note that we had some success. Otherwise, ignore any deductions
1202 // from this base class.
1203 if (BaseResult == Sema::TDK_Success) {
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001204 Successful = true;
Douglas Gregor053105d2010-11-02 00:02:34 +00001205 DeducedOrig = Deduced;
1206 }
1207 else
1208 Deduced = DeducedOrig;
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001209 }
Mike Stump1eb44332009-09-09 15:08:12 +00001210
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001211 // Visit base classes
1212 CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1213 for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
1214 BaseEnd = Next->bases_end();
Sebastian Redl9994a342009-10-25 17:03:50 +00001215 Base != BaseEnd; ++Base) {
Mike Stump1eb44332009-09-09 15:08:12 +00001216 assert(Base->getType()->isRecordType() &&
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001217 "Base class that isn't a record?");
Ted Kremenek6217b802009-07-29 21:53:49 +00001218 ToVisit.push_back(Base->getType()->getAs<RecordType>());
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001219 }
1220 }
Mike Stump1eb44332009-09-09 15:08:12 +00001221
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001222 if (Successful)
1223 return Sema::TDK_Success;
1224 }
Mike Stump1eb44332009-09-09 15:08:12 +00001225
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001226 }
Mike Stump1eb44332009-09-09 15:08:12 +00001227
Douglas Gregorde0cb8b2009-07-07 23:09:34 +00001228 return Result;
Douglas Gregord708c722009-06-09 16:35:58 +00001229 }
1230
Douglas Gregor637a4092009-06-10 23:47:09 +00001231 // T type::*
1232 // T T::*
1233 // T (type::*)()
1234 // type (T::*)()
1235 // type (type::*)(T)
1236 // type (T::*)(T)
1237 // T (type::*)(T)
1238 // T (T::*)()
1239 // T (T::*)(T)
1240 case Type::MemberPointer: {
1241 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1242 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1243 if (!MemPtrArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001244 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor637a4092009-06-10 23:47:09 +00001245
Douglas Gregorf67875d2009-06-12 18:26:56 +00001246 if (Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001247 = DeduceTemplateArguments(S, TemplateParams,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001248 MemPtrParam->getPointeeType(),
1249 MemPtrArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +00001250 Info, Deduced,
1251 TDF & TDF_IgnoreQualifiers))
Douglas Gregorf67875d2009-06-12 18:26:56 +00001252 return Result;
1253
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001254 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001255 QualType(MemPtrParam->getClass(), 0),
1256 QualType(MemPtrArg->getClass(), 0),
Douglas Gregor508f1c82009-06-26 23:10:12 +00001257 Info, Deduced, 0);
Douglas Gregor637a4092009-06-10 23:47:09 +00001258 }
1259
Anders Carlsson9a917e42009-06-12 22:56:54 +00001260 // (clang extension)
1261 //
Mike Stump1eb44332009-09-09 15:08:12 +00001262 // type(^)(T)
1263 // T(^)()
1264 // T(^)(T)
Anders Carlsson859ba502009-06-12 16:23:10 +00001265 case Type::BlockPointer: {
1266 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1267 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
Mike Stump1eb44332009-09-09 15:08:12 +00001268
Anders Carlsson859ba502009-06-12 16:23:10 +00001269 if (!BlockPtrArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001270 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001271
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001272 return DeduceTemplateArguments(S, TemplateParams,
Anders Carlsson859ba502009-06-12 16:23:10 +00001273 BlockPtrParam->getPointeeType(),
Douglas Gregorf67875d2009-06-12 18:26:56 +00001274 BlockPtrArg->getPointeeType(), Info,
Douglas Gregor508f1c82009-06-26 23:10:12 +00001275 Deduced, 0);
Anders Carlsson859ba502009-06-12 16:23:10 +00001276 }
1277
Douglas Gregor637a4092009-06-10 23:47:09 +00001278 case Type::TypeOfExpr:
1279 case Type::TypeOf:
Douglas Gregor4714c122010-03-31 17:34:00 +00001280 case Type::DependentName:
Douglas Gregor637a4092009-06-10 23:47:09 +00001281 // No template argument deduction for these types
Douglas Gregorf67875d2009-06-12 18:26:56 +00001282 return Sema::TDK_Success;
Douglas Gregor637a4092009-06-10 23:47:09 +00001283
Douglas Gregord560d502009-06-04 00:21:18 +00001284 default:
1285 break;
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001286 }
1287
1288 // FIXME: Many more cases to go (to go).
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001289 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001290}
1291
Douglas Gregorf67875d2009-06-12 18:26:56 +00001292static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001293DeduceTemplateArguments(Sema &S,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001294 TemplateParameterList *TemplateParams,
1295 const TemplateArgument &Param,
Douglas Gregor77d6bb92011-01-11 22:21:24 +00001296 TemplateArgument Arg,
John McCall2a7fb272010-08-25 05:32:35 +00001297 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +00001298 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Douglas Gregor77d6bb92011-01-11 22:21:24 +00001299 // If the template argument is a pack expansion, perform template argument
1300 // deduction against the pattern of that expansion. This only occurs during
1301 // partial ordering.
1302 if (Arg.isPackExpansion())
1303 Arg = Arg.getPackExpansionPattern();
1304
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001305 switch (Param.getKind()) {
Douglas Gregor199d9912009-06-05 00:53:49 +00001306 case TemplateArgument::Null:
1307 assert(false && "Null template argument in parameter list");
1308 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001309
1310 case TemplateArgument::Type:
Douglas Gregor788cd062009-11-11 01:00:40 +00001311 if (Arg.getKind() == TemplateArgument::Type)
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001312 return DeduceTemplateArguments(S, TemplateParams, Param.getAsType(),
Douglas Gregor788cd062009-11-11 01:00:40 +00001313 Arg.getAsType(), Info, Deduced, 0);
1314 Info.FirstArg = Param;
1315 Info.SecondArg = Arg;
1316 return Sema::TDK_NonDeducedMismatch;
Douglas Gregora7fc9012011-01-05 18:58:31 +00001317
Douglas Gregor788cd062009-11-11 01:00:40 +00001318 case TemplateArgument::Template:
Douglas Gregordb0d4b72009-11-11 23:06:43 +00001319 if (Arg.getKind() == TemplateArgument::Template)
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001320 return DeduceTemplateArguments(S, TemplateParams,
Douglas Gregor788cd062009-11-11 01:00:40 +00001321 Param.getAsTemplate(),
Douglas Gregordb0d4b72009-11-11 23:06:43 +00001322 Arg.getAsTemplate(), Info, Deduced);
Douglas Gregor788cd062009-11-11 01:00:40 +00001323 Info.FirstArg = Param;
1324 Info.SecondArg = Arg;
1325 return Sema::TDK_NonDeducedMismatch;
Douglas Gregora7fc9012011-01-05 18:58:31 +00001326
1327 case TemplateArgument::TemplateExpansion:
1328 llvm_unreachable("caller should handle pack expansions");
1329 break;
Douglas Gregor788cd062009-11-11 01:00:40 +00001330
Douglas Gregor199d9912009-06-05 00:53:49 +00001331 case TemplateArgument::Declaration:
Douglas Gregor788cd062009-11-11 01:00:40 +00001332 if (Arg.getKind() == TemplateArgument::Declaration &&
1333 Param.getAsDecl()->getCanonicalDecl() ==
1334 Arg.getAsDecl()->getCanonicalDecl())
1335 return Sema::TDK_Success;
1336
Douglas Gregorf67875d2009-06-12 18:26:56 +00001337 Info.FirstArg = Param;
1338 Info.SecondArg = Arg;
1339 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001340
Douglas Gregor199d9912009-06-05 00:53:49 +00001341 case TemplateArgument::Integral:
1342 if (Arg.getKind() == TemplateArgument::Integral) {
Douglas Gregor9d0e4412010-03-26 05:50:28 +00001343 if (hasSameExtendedValue(*Param.getAsIntegral(), *Arg.getAsIntegral()))
Douglas Gregorf67875d2009-06-12 18:26:56 +00001344 return Sema::TDK_Success;
1345
1346 Info.FirstArg = Param;
1347 Info.SecondArg = Arg;
1348 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +00001349 }
Douglas Gregorf67875d2009-06-12 18:26:56 +00001350
1351 if (Arg.getKind() == TemplateArgument::Expression) {
1352 Info.FirstArg = Param;
1353 Info.SecondArg = Arg;
1354 return Sema::TDK_NonDeducedMismatch;
1355 }
Douglas Gregor199d9912009-06-05 00:53:49 +00001356
Douglas Gregorf67875d2009-06-12 18:26:56 +00001357 Info.FirstArg = Param;
1358 Info.SecondArg = Arg;
1359 return Sema::TDK_NonDeducedMismatch;
Mike Stump1eb44332009-09-09 15:08:12 +00001360
Douglas Gregor199d9912009-06-05 00:53:49 +00001361 case TemplateArgument::Expression: {
Mike Stump1eb44332009-09-09 15:08:12 +00001362 if (NonTypeTemplateParmDecl *NTTP
Douglas Gregor199d9912009-06-05 00:53:49 +00001363 = getDeducedParameterFromExpr(Param.getAsExpr())) {
1364 if (Arg.getKind() == TemplateArgument::Integral)
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001365 return DeduceNonTypeTemplateArgument(S, NTTP,
Mike Stump1eb44332009-09-09 15:08:12 +00001366 *Arg.getAsIntegral(),
Douglas Gregor9d0e4412010-03-26 05:50:28 +00001367 Arg.getIntegralType(),
Douglas Gregor02024a92010-03-28 02:42:43 +00001368 /*ArrayBound=*/false,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001369 Info, Deduced);
Douglas Gregor199d9912009-06-05 00:53:49 +00001370 if (Arg.getKind() == TemplateArgument::Expression)
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001371 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
Douglas Gregorf67875d2009-06-12 18:26:56 +00001372 Info, Deduced);
Douglas Gregor15755cb2009-11-13 23:45:44 +00001373 if (Arg.getKind() == TemplateArgument::Declaration)
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001374 return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
Douglas Gregor15755cb2009-11-13 23:45:44 +00001375 Info, Deduced);
1376
Douglas Gregorf67875d2009-06-12 18:26:56 +00001377 Info.FirstArg = Param;
1378 Info.SecondArg = Arg;
1379 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +00001380 }
Mike Stump1eb44332009-09-09 15:08:12 +00001381
Douglas Gregor199d9912009-06-05 00:53:49 +00001382 // Can't deduce anything, but that's okay.
Douglas Gregorf67875d2009-06-12 18:26:56 +00001383 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001384 }
Anders Carlssond01b1da2009-06-15 17:04:53 +00001385 case TemplateArgument::Pack:
Douglas Gregor20a55e22010-12-22 18:17:10 +00001386 llvm_unreachable("Argument packs should be expanded by the caller!");
Douglas Gregor199d9912009-06-05 00:53:49 +00001387 }
Mike Stump1eb44332009-09-09 15:08:12 +00001388
Douglas Gregorf67875d2009-06-12 18:26:56 +00001389 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001390}
1391
Douglas Gregor20a55e22010-12-22 18:17:10 +00001392/// \brief Determine whether there is a template argument to be used for
1393/// deduction.
1394///
1395/// This routine "expands" argument packs in-place, overriding its input
1396/// parameters so that \c Args[ArgIdx] will be the available template argument.
1397///
1398/// \returns true if there is another template argument (which will be at
1399/// \c Args[ArgIdx]), false otherwise.
1400static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1401 unsigned &ArgIdx,
1402 unsigned &NumArgs) {
1403 if (ArgIdx == NumArgs)
1404 return false;
1405
1406 const TemplateArgument &Arg = Args[ArgIdx];
1407 if (Arg.getKind() != TemplateArgument::Pack)
1408 return true;
1409
1410 assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1411 Args = Arg.pack_begin();
1412 NumArgs = Arg.pack_size();
1413 ArgIdx = 0;
1414 return ArgIdx < NumArgs;
1415}
1416
Douglas Gregor7b976ec2010-12-23 01:24:45 +00001417/// \brief Determine whether the given set of template arguments has a pack
1418/// expansion that is not the last template argument.
1419static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1420 unsigned NumArgs) {
1421 unsigned ArgIdx = 0;
1422 while (ArgIdx < NumArgs) {
1423 const TemplateArgument &Arg = Args[ArgIdx];
1424
1425 // Unwrap argument packs.
1426 if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1427 Args = Arg.pack_begin();
1428 NumArgs = Arg.pack_size();
1429 ArgIdx = 0;
1430 continue;
1431 }
1432
1433 ++ArgIdx;
1434 if (ArgIdx == NumArgs)
1435 return false;
1436
1437 if (Arg.isPackExpansion())
1438 return true;
1439 }
1440
1441 return false;
1442}
1443
Douglas Gregor20a55e22010-12-22 18:17:10 +00001444static Sema::TemplateDeductionResult
1445DeduceTemplateArguments(Sema &S,
1446 TemplateParameterList *TemplateParams,
1447 const TemplateArgument *Params, unsigned NumParams,
1448 const TemplateArgument *Args, unsigned NumArgs,
1449 TemplateDeductionInfo &Info,
Douglas Gregor0972c862010-12-22 18:55:49 +00001450 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
1451 bool NumberOfArgumentsMustMatch) {
Douglas Gregore02e2622010-12-22 21:19:48 +00001452 // C++0x [temp.deduct.type]p9:
1453 // If the template argument list of P contains a pack expansion that is not
1454 // the last template argument, the entire template argument list is a
1455 // non-deduced context.
Douglas Gregor7b976ec2010-12-23 01:24:45 +00001456 if (hasPackExpansionBeforeEnd(Params, NumParams))
1457 return Sema::TDK_Success;
1458
Douglas Gregore02e2622010-12-22 21:19:48 +00001459 // C++0x [temp.deduct.type]p9:
1460 // If P has a form that contains <T> or <i>, then each argument Pi of the
1461 // respective template argument list P is compared with the corresponding
1462 // argument Ai of the corresponding template argument list of A.
Douglas Gregor20a55e22010-12-22 18:17:10 +00001463 unsigned ArgIdx = 0, ParamIdx = 0;
1464 for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1465 ++ParamIdx) {
1466 if (!Params[ParamIdx].isPackExpansion()) {
Douglas Gregore02e2622010-12-22 21:19:48 +00001467 // The simple case: deduce template arguments by matching Pi and Ai.
Douglas Gregor20a55e22010-12-22 18:17:10 +00001468
1469 // Check whether we have enough arguments.
1470 if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
Douglas Gregor3cae5c92011-01-10 20:53:55 +00001471 return NumberOfArgumentsMustMatch? Sema::TDK_NonDeducedMismatch
Douglas Gregor0972c862010-12-22 18:55:49 +00001472 : Sema::TDK_Success;
Douglas Gregor20a55e22010-12-22 18:17:10 +00001473
Douglas Gregor77d6bb92011-01-11 22:21:24 +00001474 if (Args[ArgIdx].isPackExpansion()) {
1475 // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1476 // but applied to pack expansions that are template arguments.
1477 return Sema::TDK_NonDeducedMismatch;
1478 }
1479
Douglas Gregore02e2622010-12-22 21:19:48 +00001480 // Perform deduction for this Pi/Ai pair.
Douglas Gregor20a55e22010-12-22 18:17:10 +00001481 if (Sema::TemplateDeductionResult Result
Douglas Gregor77d6bb92011-01-11 22:21:24 +00001482 = DeduceTemplateArguments(S, TemplateParams,
1483 Params[ParamIdx], Args[ArgIdx],
1484 Info, Deduced))
Douglas Gregor20a55e22010-12-22 18:17:10 +00001485 return Result;
1486
1487 // Move to the next argument.
1488 ++ArgIdx;
1489 continue;
1490 }
1491
Douglas Gregore02e2622010-12-22 21:19:48 +00001492 // The parameter is a pack expansion.
1493
1494 // C++0x [temp.deduct.type]p9:
1495 // If Pi is a pack expansion, then the pattern of Pi is compared with
1496 // each remaining argument in the template argument list of A. Each
1497 // comparison deduces template arguments for subsequent positions in the
1498 // template parameter packs expanded by Pi.
1499 TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1500
1501 // Compute the set of template parameter indices that correspond to
1502 // parameter packs expanded by the pack expansion.
1503 llvm::SmallVector<unsigned, 2> PackIndices;
1504 {
1505 llvm::BitVector SawIndices(TemplateParams->size());
1506 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1507 S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1508 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
1509 unsigned Depth, Index;
1510 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
1511 if (Depth == 0 && !SawIndices[Index]) {
1512 SawIndices[Index] = true;
1513 PackIndices.push_back(Index);
1514 }
1515 }
1516 }
1517 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
1518
1519 // FIXME: If there are no remaining arguments, we can bail out early
1520 // and set any deduced parameter packs to an empty argument pack.
1521 // The latter part of this is a (minor) correctness issue.
1522
1523 // Save the deduced template arguments for each parameter pack expanded
1524 // by this pack expansion, then clear out the deduction.
1525 llvm::SmallVector<DeducedTemplateArgument, 2>
1526 SavedPacks(PackIndices.size());
Douglas Gregor54293852011-01-10 17:35:05 +00001527 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
1528 NewlyDeducedPacks(PackIndices.size());
1529 PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
1530 NewlyDeducedPacks);
Douglas Gregore02e2622010-12-22 21:19:48 +00001531
1532 // Keep track of the deduced template arguments for each parameter pack
1533 // expanded by this pack expansion (the outer index) and for each
1534 // template argument (the inner SmallVectors).
Douglas Gregore02e2622010-12-22 21:19:48 +00001535 bool HasAnyArguments = false;
1536 while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
1537 HasAnyArguments = true;
1538
1539 // Deduce template arguments from the pattern.
1540 if (Sema::TemplateDeductionResult Result
1541 = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1542 Info, Deduced))
1543 return Result;
1544
1545 // Capture the deduced template arguments for each parameter pack expanded
1546 // by this pack expansion, add them to the list of arguments we've deduced
1547 // for that pack, then clear out the deduced argument.
1548 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
1549 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
1550 if (!DeducedArg.isNull()) {
1551 NewlyDeducedPacks[I].push_back(DeducedArg);
1552 DeducedArg = DeducedTemplateArgument();
1553 }
1554 }
1555
1556 ++ArgIdx;
1557 }
1558
1559 // Build argument packs for each of the parameter packs expanded by this
1560 // pack expansion.
Douglas Gregor0216f812011-01-10 17:53:52 +00001561 if (Sema::TemplateDeductionResult Result
1562 = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
1563 Deduced, PackIndices, SavedPacks,
1564 NewlyDeducedPacks, Info))
1565 return Result;
Douglas Gregor20a55e22010-12-22 18:17:10 +00001566 }
1567
1568 // If there is an argument remaining, then we had too many arguments.
Douglas Gregor0972c862010-12-22 18:55:49 +00001569 if (NumberOfArgumentsMustMatch &&
1570 hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
Douglas Gregor3cae5c92011-01-10 20:53:55 +00001571 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor20a55e22010-12-22 18:17:10 +00001572
1573 return Sema::TDK_Success;
1574}
1575
Mike Stump1eb44332009-09-09 15:08:12 +00001576static Sema::TemplateDeductionResult
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001577DeduceTemplateArguments(Sema &S,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001578 TemplateParameterList *TemplateParams,
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001579 const TemplateArgumentList &ParamList,
1580 const TemplateArgumentList &ArgList,
John McCall2a7fb272010-08-25 05:32:35 +00001581 TemplateDeductionInfo &Info,
Douglas Gregor02024a92010-03-28 02:42:43 +00001582 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
Douglas Gregor20a55e22010-12-22 18:17:10 +00001583 return DeduceTemplateArguments(S, TemplateParams,
1584 ParamList.data(), ParamList.size(),
1585 ArgList.data(), ArgList.size(),
1586 Info, Deduced);
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001587}
1588
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001589/// \brief Determine whether two template arguments are the same.
Mike Stump1eb44332009-09-09 15:08:12 +00001590static bool isSameTemplateArg(ASTContext &Context,
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001591 const TemplateArgument &X,
1592 const TemplateArgument &Y) {
1593 if (X.getKind() != Y.getKind())
1594 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001595
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001596 switch (X.getKind()) {
1597 case TemplateArgument::Null:
1598 assert(false && "Comparing NULL template argument");
1599 break;
Mike Stump1eb44332009-09-09 15:08:12 +00001600
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001601 case TemplateArgument::Type:
1602 return Context.getCanonicalType(X.getAsType()) ==
1603 Context.getCanonicalType(Y.getAsType());
Mike Stump1eb44332009-09-09 15:08:12 +00001604
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001605 case TemplateArgument::Declaration:
Argyrios Kyrtzidis97fbaa22009-07-18 00:34:25 +00001606 return X.getAsDecl()->getCanonicalDecl() ==
1607 Y.getAsDecl()->getCanonicalDecl();
Mike Stump1eb44332009-09-09 15:08:12 +00001608
Douglas Gregor788cd062009-11-11 01:00:40 +00001609 case TemplateArgument::Template:
Douglas Gregora7fc9012011-01-05 18:58:31 +00001610 case TemplateArgument::TemplateExpansion:
1611 return Context.getCanonicalTemplateName(
1612 X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1613 Context.getCanonicalTemplateName(
1614 Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
Douglas Gregor788cd062009-11-11 01:00:40 +00001615
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001616 case TemplateArgument::Integral:
1617 return *X.getAsIntegral() == *Y.getAsIntegral();
Mike Stump1eb44332009-09-09 15:08:12 +00001618
Douglas Gregor788cd062009-11-11 01:00:40 +00001619 case TemplateArgument::Expression: {
1620 llvm::FoldingSetNodeID XID, YID;
1621 X.getAsExpr()->Profile(XID, Context, true);
1622 Y.getAsExpr()->Profile(YID, Context, true);
1623 return XID == YID;
1624 }
Mike Stump1eb44332009-09-09 15:08:12 +00001625
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001626 case TemplateArgument::Pack:
1627 if (X.pack_size() != Y.pack_size())
1628 return false;
Mike Stump1eb44332009-09-09 15:08:12 +00001629
1630 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1631 XPEnd = X.pack_end(),
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001632 YP = Y.pack_begin();
Mike Stump1eb44332009-09-09 15:08:12 +00001633 XP != XPEnd; ++XP, ++YP)
Douglas Gregorf670c8c2009-06-26 20:57:09 +00001634 if (!isSameTemplateArg(Context, *XP, *YP))
1635 return false;
1636
1637 return true;
1638 }
1639
1640 return false;
1641}
1642
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001643/// \brief Allocate a TemplateArgumentLoc where all locations have
1644/// been initialized to the given location.
1645///
1646/// \param S The semantic analysis object.
1647///
1648/// \param The template argument we are producing template argument
1649/// location information for.
1650///
1651/// \param NTTPType For a declaration template argument, the type of
1652/// the non-type template parameter that corresponds to this template
1653/// argument.
1654///
1655/// \param Loc The source location to use for the resulting template
1656/// argument.
1657static TemplateArgumentLoc
1658getTrivialTemplateArgumentLoc(Sema &S,
1659 const TemplateArgument &Arg,
1660 QualType NTTPType,
1661 SourceLocation Loc) {
1662 switch (Arg.getKind()) {
1663 case TemplateArgument::Null:
1664 llvm_unreachable("Can't get a NULL template argument here");
1665 break;
1666
1667 case TemplateArgument::Type:
1668 return TemplateArgumentLoc(Arg,
1669 S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
1670
1671 case TemplateArgument::Declaration: {
1672 Expr *E
Douglas Gregorba68eca2011-01-05 17:40:24 +00001673 = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001674 .takeAs<Expr>();
1675 return TemplateArgumentLoc(TemplateArgument(E), E);
1676 }
1677
1678 case TemplateArgument::Integral: {
1679 Expr *E
Douglas Gregorba68eca2011-01-05 17:40:24 +00001680 = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>();
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001681 return TemplateArgumentLoc(TemplateArgument(E), E);
1682 }
1683
1684 case TemplateArgument::Template:
Douglas Gregora7fc9012011-01-05 18:58:31 +00001685 return TemplateArgumentLoc(Arg, SourceRange(), Loc);
1686
1687 case TemplateArgument::TemplateExpansion:
1688 return TemplateArgumentLoc(Arg, SourceRange(), Loc, Loc);
1689
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001690 case TemplateArgument::Expression:
1691 return TemplateArgumentLoc(Arg, Arg.getAsExpr());
1692
1693 case TemplateArgument::Pack:
1694 return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
1695 }
1696
1697 return TemplateArgumentLoc();
1698}
1699
1700
1701/// \brief Convert the given deduced template argument and add it to the set of
1702/// fully-converted template arguments.
1703static bool ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
1704 DeducedTemplateArgument Arg,
1705 NamedDecl *Template,
1706 QualType NTTPType,
1707 TemplateDeductionInfo &Info,
1708 bool InFunctionTemplate,
1709 llvm::SmallVectorImpl<TemplateArgument> &Output) {
1710 if (Arg.getKind() == TemplateArgument::Pack) {
1711 // This is a template argument pack, so check each of its arguments against
1712 // the template parameter.
1713 llvm::SmallVector<TemplateArgument, 2> PackedArgsBuilder;
1714 for (TemplateArgument::pack_iterator PA = Arg.pack_begin(),
Douglas Gregor135ffa72011-01-05 21:00:53 +00001715 PAEnd = Arg.pack_end();
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001716 PA != PAEnd; ++PA) {
Douglas Gregord53e16a2011-01-05 20:52:18 +00001717 // When converting the deduced template argument, append it to the
1718 // general output list. We need to do this so that the template argument
1719 // checking logic has all of the prior template arguments available.
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001720 DeducedTemplateArgument InnerArg(*PA);
1721 InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
1722 if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
1723 NTTPType, Info,
Douglas Gregord53e16a2011-01-05 20:52:18 +00001724 InFunctionTemplate, Output))
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001725 return true;
Douglas Gregord53e16a2011-01-05 20:52:18 +00001726
1727 // Move the converted template argument into our argument pack.
1728 PackedArgsBuilder.push_back(Output.back());
1729 Output.pop_back();
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001730 }
1731
1732 // Create the resulting argument pack.
Douglas Gregor203e6a32011-01-11 23:09:57 +00001733 Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
1734 PackedArgsBuilder.data(),
1735 PackedArgsBuilder.size()));
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001736 return false;
1737 }
1738
1739 // Convert the deduced template argument into a template
1740 // argument that we can check, almost as if the user had written
1741 // the template argument explicitly.
1742 TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
1743 Info.getLocation());
1744
1745 // Check the template argument, converting it as necessary.
1746 return S.CheckTemplateArgument(Param, ArgLoc,
1747 Template,
1748 Template->getLocation(),
1749 Template->getSourceRange().getEnd(),
1750 Output,
1751 InFunctionTemplate
1752 ? (Arg.wasDeducedFromArrayBound()
1753 ? Sema::CTAK_DeducedFromArrayBound
1754 : Sema::CTAK_Deduced)
1755 : Sema::CTAK_Specified);
1756}
1757
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001758/// Complete template argument deduction for a class template partial
1759/// specialization.
1760static Sema::TemplateDeductionResult
1761FinishTemplateArgumentDeduction(Sema &S,
1762 ClassTemplatePartialSpecializationDecl *Partial,
1763 const TemplateArgumentList &TemplateArgs,
1764 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
John McCall2a7fb272010-08-25 05:32:35 +00001765 TemplateDeductionInfo &Info) {
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001766 // Trap errors.
1767 Sema::SFINAETrap Trap(S);
1768
1769 Sema::ContextRAII SavedContext(S, Partial);
1770
1771 // C++ [temp.deduct.type]p2:
1772 // [...] or if any template argument remains neither deduced nor
1773 // explicitly specified, template argument deduction fails.
Douglas Gregor910f8002010-11-07 23:05:16 +00001774 llvm::SmallVector<TemplateArgument, 4> Builder;
Douglas Gregor033a3ca2011-01-04 22:23:38 +00001775 TemplateParameterList *PartialParams = Partial->getTemplateParameters();
1776 for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001777 NamedDecl *Param = PartialParams->getParam(I);
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001778 if (Deduced[I].isNull()) {
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001779 Info.Param = makeTemplateParameter(Param);
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001780 return Sema::TDK_Incomplete;
1781 }
1782
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001783 // We have deduced this argument, so it still needs to be
1784 // checked and converted.
1785
1786 // First, for a non-type template parameter type that is
1787 // initialized by a declaration, we need the type of the
1788 // corresponding non-type template parameter.
1789 QualType NTTPType;
1790 if (NonTypeTemplateParmDecl *NTTP
Douglas Gregord53e16a2011-01-05 20:52:18 +00001791 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001792 NTTPType = NTTP->getType();
Douglas Gregord53e16a2011-01-05 20:52:18 +00001793 if (NTTPType->isDependentType()) {
1794 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
1795 Builder.data(), Builder.size());
1796 NTTPType = S.SubstType(NTTPType,
1797 MultiLevelTemplateArgumentList(TemplateArgs),
1798 NTTP->getLocation(),
1799 NTTP->getDeclName());
1800 if (NTTPType.isNull()) {
1801 Info.Param = makeTemplateParameter(Param);
1802 // FIXME: These template arguments are temporary. Free them!
1803 Info.reset(TemplateArgumentList::CreateCopy(S.Context,
1804 Builder.data(),
1805 Builder.size()));
1806 return Sema::TDK_SubstitutionFailure;
1807 }
1808 }
1809 }
1810
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001811 if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
1812 Partial, NTTPType, Info, false,
1813 Builder)) {
1814 Info.Param = makeTemplateParameter(Param);
1815 // FIXME: These template arguments are temporary. Free them!
1816 Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
1817 Builder.size()));
1818 return Sema::TDK_SubstitutionFailure;
1819 }
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001820 }
Douglas Gregor77d6bb92011-01-11 22:21:24 +00001821
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001822 // Form the template argument list from the deduced template arguments.
1823 TemplateArgumentList *DeducedArgumentList
Douglas Gregor910f8002010-11-07 23:05:16 +00001824 = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
1825 Builder.size());
1826
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001827 Info.reset(DeducedArgumentList);
1828
1829 // Substitute the deduced template arguments into the template
1830 // arguments of the class template partial specialization, and
1831 // verify that the instantiated template arguments are both valid
1832 // and are equivalent to the template arguments originally provided
1833 // to the class template.
John McCall2a7fb272010-08-25 05:32:35 +00001834 LocalInstantiationScope InstScope(S);
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001835 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
1836 const TemplateArgumentLoc *PartialTemplateArgs
1837 = Partial->getTemplateArgsAsWritten();
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001838
1839 // Note that we don't provide the langle and rangle locations.
1840 TemplateArgumentListInfo InstArgs;
1841
Douglas Gregore02e2622010-12-22 21:19:48 +00001842 if (S.Subst(PartialTemplateArgs,
1843 Partial->getNumTemplateArgsAsWritten(),
1844 InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
1845 unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
1846 if (ParamIdx >= Partial->getTemplateParameters()->size())
1847 ParamIdx = Partial->getTemplateParameters()->size() - 1;
1848
1849 Decl *Param
1850 = const_cast<NamedDecl *>(
1851 Partial->getTemplateParameters()->getParam(ParamIdx));
1852 Info.Param = makeTemplateParameter(Param);
1853 Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
1854 return Sema::TDK_SubstitutionFailure;
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001855 }
1856
Douglas Gregor910f8002010-11-07 23:05:16 +00001857 llvm::SmallVector<TemplateArgument, 4> ConvertedInstArgs;
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001858 if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001859 InstArgs, false, ConvertedInstArgs))
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001860 return Sema::TDK_SubstitutionFailure;
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001861
Douglas Gregor54c53cc2011-01-04 23:35:54 +00001862 TemplateParameterList *TemplateParams
1863 = ClassTemplate->getTemplateParameters();
1864 for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
Douglas Gregor910f8002010-11-07 23:05:16 +00001865 TemplateArgument InstArg = ConvertedInstArgs.data()[I];
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001866 if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
Douglas Gregor2fdc5e82011-01-05 00:13:17 +00001867 Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001868 Info.FirstArg = TemplateArgs[I];
1869 Info.SecondArg = InstArg;
1870 return Sema::TDK_NonDeducedMismatch;
1871 }
1872 }
1873
1874 if (Trap.hasErrorOccurred())
1875 return Sema::TDK_SubstitutionFailure;
1876
1877 return Sema::TDK_Success;
1878}
1879
Douglas Gregorc1efb3f2009-06-12 22:31:52 +00001880/// \brief Perform template argument deduction to determine whether
1881/// the given template arguments match the given class template
1882/// partial specialization per C++ [temp.class.spec.match].
Douglas Gregorf67875d2009-06-12 18:26:56 +00001883Sema::TemplateDeductionResult
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001884Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001885 const TemplateArgumentList &TemplateArgs,
1886 TemplateDeductionInfo &Info) {
Douglas Gregorc1efb3f2009-06-12 22:31:52 +00001887 // C++ [temp.class.spec.match]p2:
1888 // A partial specialization matches a given actual template
1889 // argument list if the template arguments of the partial
1890 // specialization can be deduced from the actual template argument
1891 // list (14.8.2).
Douglas Gregorbb260412009-06-14 08:02:22 +00001892 SFINAETrap Trap(*this);
Douglas Gregor02024a92010-03-28 02:42:43 +00001893 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001894 Deduced.resize(Partial->getTemplateParameters()->size());
Douglas Gregorf67875d2009-06-12 18:26:56 +00001895 if (TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00001896 = ::DeduceTemplateArguments(*this,
Douglas Gregorf67875d2009-06-12 18:26:56 +00001897 Partial->getTemplateParameters(),
Mike Stump1eb44332009-09-09 15:08:12 +00001898 Partial->getTemplateArgs(),
Douglas Gregorf67875d2009-06-12 18:26:56 +00001899 TemplateArgs, Info, Deduced))
1900 return Result;
Douglas Gregor637a4092009-06-10 23:47:09 +00001901
Douglas Gregor637a4092009-06-10 23:47:09 +00001902 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
Douglas Gregor9b623632010-10-12 23:32:35 +00001903 Deduced.data(), Deduced.size(), Info);
Douglas Gregor637a4092009-06-10 23:47:09 +00001904 if (Inst)
Douglas Gregorf67875d2009-06-12 18:26:56 +00001905 return TDK_InstantiationDepth;
Douglas Gregor199d9912009-06-05 00:53:49 +00001906
Douglas Gregorbb260412009-06-14 08:02:22 +00001907 if (Trap.hasErrorOccurred())
Douglas Gregor31dce8f2010-04-29 06:21:43 +00001908 return Sema::TDK_SubstitutionFailure;
1909
1910 return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
1911 Deduced, Info);
Douglas Gregor0b9247f2009-06-04 00:03:07 +00001912}
Douglas Gregor031a5882009-06-13 00:26:55 +00001913
Douglas Gregor41128772009-06-26 23:27:24 +00001914/// \brief Determine whether the given type T is a simple-template-id type.
1915static bool isSimpleTemplateIdType(QualType T) {
Mike Stump1eb44332009-09-09 15:08:12 +00001916 if (const TemplateSpecializationType *Spec
John McCall183700f2009-09-21 23:43:11 +00001917 = T->getAs<TemplateSpecializationType>())
Douglas Gregor41128772009-06-26 23:27:24 +00001918 return Spec->getTemplateName().getAsTemplateDecl() != 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001919
Douglas Gregor41128772009-06-26 23:27:24 +00001920 return false;
1921}
Douglas Gregor83314aa2009-07-08 20:55:45 +00001922
1923/// \brief Substitute the explicitly-provided template arguments into the
1924/// given function template according to C++ [temp.arg.explicit].
1925///
1926/// \param FunctionTemplate the function template into which the explicit
1927/// template arguments will be substituted.
1928///
Mike Stump1eb44332009-09-09 15:08:12 +00001929/// \param ExplicitTemplateArguments the explicitly-specified template
Douglas Gregor83314aa2009-07-08 20:55:45 +00001930/// arguments.
1931///
Mike Stump1eb44332009-09-09 15:08:12 +00001932/// \param Deduced the deduced template arguments, which will be populated
Douglas Gregor83314aa2009-07-08 20:55:45 +00001933/// with the converted and checked explicit template arguments.
1934///
Mike Stump1eb44332009-09-09 15:08:12 +00001935/// \param ParamTypes will be populated with the instantiated function
Douglas Gregor83314aa2009-07-08 20:55:45 +00001936/// parameters.
1937///
1938/// \param FunctionType if non-NULL, the result type of the function template
1939/// will also be instantiated and the pointed-to value will be updated with
1940/// the instantiated function type.
1941///
1942/// \param Info if substitution fails for any reason, this object will be
1943/// populated with more information about the failure.
1944///
1945/// \returns TDK_Success if substitution was successful, or some failure
1946/// condition.
1947Sema::TemplateDeductionResult
1948Sema::SubstituteExplicitTemplateArguments(
1949 FunctionTemplateDecl *FunctionTemplate,
John McCalld5532b62009-11-23 01:53:49 +00001950 const TemplateArgumentListInfo &ExplicitTemplateArgs,
Douglas Gregor02024a92010-03-28 02:42:43 +00001951 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
Douglas Gregor83314aa2009-07-08 20:55:45 +00001952 llvm::SmallVectorImpl<QualType> &ParamTypes,
1953 QualType *FunctionType,
1954 TemplateDeductionInfo &Info) {
1955 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
1956 TemplateParameterList *TemplateParams
1957 = FunctionTemplate->getTemplateParameters();
1958
John McCalld5532b62009-11-23 01:53:49 +00001959 if (ExplicitTemplateArgs.size() == 0) {
Douglas Gregor83314aa2009-07-08 20:55:45 +00001960 // No arguments to substitute; just copy over the parameter types and
1961 // fill in the function type.
1962 for (FunctionDecl::param_iterator P = Function->param_begin(),
1963 PEnd = Function->param_end();
1964 P != PEnd;
1965 ++P)
1966 ParamTypes.push_back((*P)->getType());
Mike Stump1eb44332009-09-09 15:08:12 +00001967
Douglas Gregor83314aa2009-07-08 20:55:45 +00001968 if (FunctionType)
1969 *FunctionType = Function->getType();
1970 return TDK_Success;
1971 }
Mike Stump1eb44332009-09-09 15:08:12 +00001972
Douglas Gregor83314aa2009-07-08 20:55:45 +00001973 // Substitution of the explicit template arguments into a function template
1974 /// is a SFINAE context. Trap any errors that might occur.
Mike Stump1eb44332009-09-09 15:08:12 +00001975 SFINAETrap Trap(*this);
1976
Douglas Gregor83314aa2009-07-08 20:55:45 +00001977 // C++ [temp.arg.explicit]p3:
Mike Stump1eb44332009-09-09 15:08:12 +00001978 // Template arguments that are present shall be specified in the
1979 // declaration order of their corresponding template-parameters. The
Douglas Gregor83314aa2009-07-08 20:55:45 +00001980 // template argument list shall not specify more template-arguments than
Mike Stump1eb44332009-09-09 15:08:12 +00001981 // there are corresponding template-parameters.
Douglas Gregor910f8002010-11-07 23:05:16 +00001982 llvm::SmallVector<TemplateArgument, 4> Builder;
Mike Stump1eb44332009-09-09 15:08:12 +00001983
1984 // Enter a new template instantiation context where we check the
Douglas Gregor83314aa2009-07-08 20:55:45 +00001985 // explicitly-specified template arguments against this function template,
1986 // and then substitute them into the function parameter types.
Mike Stump1eb44332009-09-09 15:08:12 +00001987 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
Douglas Gregor83314aa2009-07-08 20:55:45 +00001988 FunctionTemplate, Deduced.data(), Deduced.size(),
Douglas Gregor9b623632010-10-12 23:32:35 +00001989 ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
1990 Info);
Douglas Gregor83314aa2009-07-08 20:55:45 +00001991 if (Inst)
1992 return TDK_InstantiationDepth;
Mike Stump1eb44332009-09-09 15:08:12 +00001993
Douglas Gregor83314aa2009-07-08 20:55:45 +00001994 if (CheckTemplateArgumentList(FunctionTemplate,
Douglas Gregor83314aa2009-07-08 20:55:45 +00001995 SourceLocation(),
John McCalld5532b62009-11-23 01:53:49 +00001996 ExplicitTemplateArgs,
Douglas Gregor83314aa2009-07-08 20:55:45 +00001997 true,
Douglas Gregorf1a84452010-05-08 19:15:54 +00001998 Builder) || Trap.hasErrorOccurred()) {
Douglas Gregor910f8002010-11-07 23:05:16 +00001999 unsigned Index = Builder.size();
Douglas Gregorfe52c912010-05-09 01:26:06 +00002000 if (Index >= TemplateParams->size())
2001 Index = TemplateParams->size() - 1;
2002 Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
Douglas Gregor83314aa2009-07-08 20:55:45 +00002003 return TDK_InvalidExplicitArguments;
Douglas Gregorf1a84452010-05-08 19:15:54 +00002004 }
Mike Stump1eb44332009-09-09 15:08:12 +00002005
Douglas Gregor83314aa2009-07-08 20:55:45 +00002006 // Form the template argument list from the explicitly-specified
2007 // template arguments.
Mike Stump1eb44332009-09-09 15:08:12 +00002008 TemplateArgumentList *ExplicitArgumentList
Douglas Gregor910f8002010-11-07 23:05:16 +00002009 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
Douglas Gregor83314aa2009-07-08 20:55:45 +00002010 Info.reset(ExplicitArgumentList);
Douglas Gregord3731192011-01-10 07:32:04 +00002011
John McCalldf41f182010-10-12 19:40:14 +00002012 // Template argument deduction and the final substitution should be
2013 // done in the context of the templated declaration. Explicit
2014 // argument substitution, on the other hand, needs to happen in the
2015 // calling context.
2016 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2017
Douglas Gregord3731192011-01-10 07:32:04 +00002018 // If we deduced template arguments for a template parameter pack,
2019 // note that the template argument pack is partially substituted and record
2020 // the explicit template arguments. They'll be used as part of deduction
2021 // for this template parameter pack.
Douglas Gregord3731192011-01-10 07:32:04 +00002022 for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2023 const TemplateArgument &Arg = Builder[I];
2024 if (Arg.getKind() == TemplateArgument::Pack) {
Douglas Gregord3731192011-01-10 07:32:04 +00002025 CurrentInstantiationScope->SetPartiallySubstitutedPack(
2026 TemplateParams->getParam(I),
2027 Arg.pack_begin(),
2028 Arg.pack_size());
2029 break;
2030 }
2031 }
2032
Douglas Gregor83314aa2009-07-08 20:55:45 +00002033 // Instantiate the types of each of the function parameters given the
2034 // explicitly-specified template arguments.
Douglas Gregora009b592011-01-07 00:20:55 +00002035 if (SubstParmTypes(Function->getLocation(),
2036 Function->param_begin(), Function->getNumParams(),
2037 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2038 ParamTypes))
2039 return TDK_SubstitutionFailure;
Douglas Gregor83314aa2009-07-08 20:55:45 +00002040
2041 // If the caller wants a full function type back, instantiate the return
2042 // type and form that function type.
2043 if (FunctionType) {
2044 // FIXME: exception-specifications?
Mike Stump1eb44332009-09-09 15:08:12 +00002045 const FunctionProtoType *Proto
John McCall183700f2009-09-21 23:43:11 +00002046 = Function->getType()->getAs<FunctionProtoType>();
Douglas Gregor83314aa2009-07-08 20:55:45 +00002047 assert(Proto && "Function template does not have a prototype?");
Mike Stump1eb44332009-09-09 15:08:12 +00002048
2049 QualType ResultType
Douglas Gregor357bbd02009-08-28 20:50:45 +00002050 = SubstType(Proto->getResultType(),
2051 MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2052 Function->getTypeSpecStartLoc(),
2053 Function->getDeclName());
Douglas Gregor83314aa2009-07-08 20:55:45 +00002054 if (ResultType.isNull() || Trap.hasErrorOccurred())
2055 return TDK_SubstitutionFailure;
Mike Stump1eb44332009-09-09 15:08:12 +00002056
2057 *FunctionType = BuildFunctionType(ResultType,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002058 ParamTypes.data(), ParamTypes.size(),
2059 Proto->isVariadic(),
2060 Proto->getTypeQuals(),
2061 Function->getLocation(),
Eli Friedmanfa869542010-08-05 02:54:05 +00002062 Function->getDeclName(),
2063 Proto->getExtInfo());
Douglas Gregor83314aa2009-07-08 20:55:45 +00002064 if (FunctionType->isNull() || Trap.hasErrorOccurred())
2065 return TDK_SubstitutionFailure;
2066 }
Mike Stump1eb44332009-09-09 15:08:12 +00002067
Douglas Gregor83314aa2009-07-08 20:55:45 +00002068 // C++ [temp.arg.explicit]p2:
Mike Stump1eb44332009-09-09 15:08:12 +00002069 // Trailing template arguments that can be deduced (14.8.2) may be
2070 // omitted from the list of explicit template-arguments. If all of the
Douglas Gregor83314aa2009-07-08 20:55:45 +00002071 // template arguments can be deduced, they may all be omitted; in this
2072 // case, the empty template argument list <> itself may also be omitted.
2073 //
Douglas Gregord3731192011-01-10 07:32:04 +00002074 // Take all of the explicitly-specified arguments and put them into
2075 // the set of deduced template arguments. Explicitly-specified
2076 // parameter packs, however, will be set to NULL since the deduction
2077 // mechanisms handle explicitly-specified argument packs directly.
Douglas Gregor83314aa2009-07-08 20:55:45 +00002078 Deduced.reserve(TemplateParams->size());
Douglas Gregord3731192011-01-10 07:32:04 +00002079 for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2080 const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2081 if (Arg.getKind() == TemplateArgument::Pack)
2082 Deduced.push_back(DeducedTemplateArgument());
2083 else
2084 Deduced.push_back(Arg);
2085 }
Mike Stump1eb44332009-09-09 15:08:12 +00002086
Douglas Gregor83314aa2009-07-08 20:55:45 +00002087 return TDK_Success;
2088}
2089
Mike Stump1eb44332009-09-09 15:08:12 +00002090/// \brief Finish template argument deduction for a function template,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002091/// checking the deduced template arguments for completeness and forming
2092/// the function template specialization.
Mike Stump1eb44332009-09-09 15:08:12 +00002093Sema::TemplateDeductionResult
Douglas Gregor83314aa2009-07-08 20:55:45 +00002094Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
Douglas Gregor02024a92010-03-28 02:42:43 +00002095 llvm::SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2096 unsigned NumExplicitlySpecified,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002097 FunctionDecl *&Specialization,
2098 TemplateDeductionInfo &Info) {
2099 TemplateParameterList *TemplateParams
2100 = FunctionTemplate->getTemplateParameters();
Mike Stump1eb44332009-09-09 15:08:12 +00002101
Douglas Gregor83314aa2009-07-08 20:55:45 +00002102 // Template argument deduction for function templates in a SFINAE context.
2103 // Trap any errors that might occur.
Mike Stump1eb44332009-09-09 15:08:12 +00002104 SFINAETrap Trap(*this);
2105
Douglas Gregor83314aa2009-07-08 20:55:45 +00002106 // Enter a new template instantiation context while we instantiate the
2107 // actual function declaration.
Mike Stump1eb44332009-09-09 15:08:12 +00002108 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
Douglas Gregor83314aa2009-07-08 20:55:45 +00002109 FunctionTemplate, Deduced.data(), Deduced.size(),
Douglas Gregor9b623632010-10-12 23:32:35 +00002110 ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2111 Info);
Douglas Gregor83314aa2009-07-08 20:55:45 +00002112 if (Inst)
Mike Stump1eb44332009-09-09 15:08:12 +00002113 return TDK_InstantiationDepth;
2114
John McCall96db3102010-04-29 01:18:58 +00002115 ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
John McCallf5813822010-04-29 00:35:03 +00002116
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002117 // C++ [temp.deduct.type]p2:
2118 // [...] or if any template argument remains neither deduced nor
2119 // explicitly specified, template argument deduction fails.
Douglas Gregor910f8002010-11-07 23:05:16 +00002120 llvm::SmallVector<TemplateArgument, 4> Builder;
Douglas Gregorb9a7d6f2011-01-04 22:13:36 +00002121 for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2122 NamedDecl *Param = TemplateParams->getParam(I);
Douglas Gregorea6c96f2010-12-23 01:52:01 +00002123
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002124 if (!Deduced[I].isNull()) {
Douglas Gregor3273b0c2010-10-12 18:51:08 +00002125 if (I < NumExplicitlySpecified) {
Douglas Gregor02024a92010-03-28 02:42:43 +00002126 // We have already fully type-checked and converted this
Douglas Gregor3273b0c2010-10-12 18:51:08 +00002127 // argument, because it was explicitly-specified. Just record the
2128 // presence of this argument.
Douglas Gregor910f8002010-11-07 23:05:16 +00002129 Builder.push_back(Deduced[I]);
Douglas Gregor02024a92010-03-28 02:42:43 +00002130 continue;
2131 }
2132
2133 // We have deduced this argument, so it still needs to be
2134 // checked and converted.
2135
2136 // First, for a non-type template parameter type that is
2137 // initialized by a declaration, we need the type of the
2138 // corresponding non-type template parameter.
2139 QualType NTTPType;
2140 if (NonTypeTemplateParmDecl *NTTP
2141 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
Douglas Gregorb9a7d6f2011-01-04 22:13:36 +00002142 NTTPType = NTTP->getType();
2143 if (NTTPType->isDependentType()) {
2144 TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2145 Builder.data(), Builder.size());
2146 NTTPType = SubstType(NTTPType,
2147 MultiLevelTemplateArgumentList(TemplateArgs),
2148 NTTP->getLocation(),
2149 NTTP->getDeclName());
2150 if (NTTPType.isNull()) {
2151 Info.Param = makeTemplateParameter(Param);
2152 // FIXME: These template arguments are temporary. Free them!
2153 Info.reset(TemplateArgumentList::CreateCopy(Context,
2154 Builder.data(),
2155 Builder.size()));
2156 return TDK_SubstitutionFailure;
Douglas Gregor02024a92010-03-28 02:42:43 +00002157 }
2158 }
2159 }
2160
Douglas Gregorb9a7d6f2011-01-04 22:13:36 +00002161 if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2162 FunctionTemplate, NTTPType, Info,
Douglas Gregor54c53cc2011-01-04 23:35:54 +00002163 true, Builder)) {
Douglas Gregorb9a7d6f2011-01-04 22:13:36 +00002164 Info.Param = makeTemplateParameter(Param);
Douglas Gregor910f8002010-11-07 23:05:16 +00002165 // FIXME: These template arguments are temporary. Free them!
2166 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
Douglas Gregorb9a7d6f2011-01-04 22:13:36 +00002167 Builder.size()));
Douglas Gregor02024a92010-03-28 02:42:43 +00002168 return TDK_SubstitutionFailure;
2169 }
2170
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002171 continue;
2172 }
Douglas Gregorea6c96f2010-12-23 01:52:01 +00002173
2174 // C++0x [temp.arg.explicit]p3:
2175 // A trailing template parameter pack (14.5.3) not otherwise deduced will
2176 // be deduced to an empty sequence of template arguments.
2177 // FIXME: Where did the word "trailing" come from?
2178 if (Param->isTemplateParameterPack()) {
Douglas Gregord3731192011-01-10 07:32:04 +00002179 // We may have had explicitly-specified template arguments for this
2180 // template parameter pack. If so, our empty deduction extends the
2181 // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2182 const TemplateArgument *ExplicitArgs;
2183 unsigned NumExplicitArgs;
2184 if (CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2185 &NumExplicitArgs)
2186 == Param)
2187 Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2188 else
2189 Builder.push_back(TemplateArgument(0, 0));
2190
Douglas Gregorea6c96f2010-12-23 01:52:01 +00002191 continue;
2192 }
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002193
2194 // Substitute into the default template argument, if available.
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002195 TemplateArgumentLoc DefArg
2196 = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2197 FunctionTemplate->getLocation(),
2198 FunctionTemplate->getSourceRange().getEnd(),
2199 Param,
2200 Builder);
2201
2202 // If there was no default argument, deduction is incomplete.
2203 if (DefArg.getArgument().isNull()) {
2204 Info.Param = makeTemplateParameter(
2205 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2206 return TDK_Incomplete;
2207 }
2208
2209 // Check whether we can actually use the default argument.
2210 if (CheckTemplateArgument(Param, DefArg,
2211 FunctionTemplate,
2212 FunctionTemplate->getLocation(),
2213 FunctionTemplate->getSourceRange().getEnd(),
Douglas Gregor02024a92010-03-28 02:42:43 +00002214 Builder,
2215 CTAK_Deduced)) {
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002216 Info.Param = makeTemplateParameter(
2217 const_cast<NamedDecl *>(TemplateParams->getParam(I)));
Douglas Gregor910f8002010-11-07 23:05:16 +00002218 // FIXME: These template arguments are temporary. Free them!
2219 Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2220 Builder.size()));
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002221 return TDK_SubstitutionFailure;
2222 }
2223
2224 // If we get here, we successfully used the default template argument.
2225 }
2226
2227 // Form the template argument list from the deduced template arguments.
2228 TemplateArgumentList *DeducedArgumentList
Douglas Gregor910f8002010-11-07 23:05:16 +00002229 = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
Douglas Gregor51ffb0c2009-11-25 18:55:14 +00002230 Info.reset(DeducedArgumentList);
2231
Mike Stump1eb44332009-09-09 15:08:12 +00002232 // Substitute the deduced template arguments into the function template
Douglas Gregor83314aa2009-07-08 20:55:45 +00002233 // declaration to produce the function template specialization.
Douglas Gregord4598a22010-04-28 04:52:24 +00002234 DeclContext *Owner = FunctionTemplate->getDeclContext();
2235 if (FunctionTemplate->getFriendObjectKind())
2236 Owner = FunctionTemplate->getLexicalDeclContext();
Douglas Gregor83314aa2009-07-08 20:55:45 +00002237 Specialization = cast_or_null<FunctionDecl>(
Douglas Gregord4598a22010-04-28 04:52:24 +00002238 SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
Douglas Gregor357bbd02009-08-28 20:50:45 +00002239 MultiLevelTemplateArgumentList(*DeducedArgumentList)));
Douglas Gregor83314aa2009-07-08 20:55:45 +00002240 if (!Specialization)
2241 return TDK_SubstitutionFailure;
Mike Stump1eb44332009-09-09 15:08:12 +00002242
Douglas Gregorf8825742009-09-15 18:26:13 +00002243 assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2244 FunctionTemplate->getCanonicalDecl());
2245
Mike Stump1eb44332009-09-09 15:08:12 +00002246 // If the template argument list is owned by the function template
Douglas Gregor83314aa2009-07-08 20:55:45 +00002247 // specialization, release it.
Douglas Gregorec20f462010-05-08 20:07:26 +00002248 if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2249 !Trap.hasErrorOccurred())
Douglas Gregor83314aa2009-07-08 20:55:45 +00002250 Info.take();
Mike Stump1eb44332009-09-09 15:08:12 +00002251
Douglas Gregor83314aa2009-07-08 20:55:45 +00002252 // There may have been an error that did not prevent us from constructing a
2253 // declaration. Mark the declaration invalid and return with a substitution
2254 // failure.
2255 if (Trap.hasErrorOccurred()) {
2256 Specialization->setInvalidDecl(true);
2257 return TDK_SubstitutionFailure;
2258 }
Mike Stump1eb44332009-09-09 15:08:12 +00002259
Douglas Gregor9b623632010-10-12 23:32:35 +00002260 // If we suppressed any diagnostics while performing template argument
2261 // deduction, and if we haven't already instantiated this declaration,
2262 // keep track of these diagnostics. They'll be emitted if this specialization
2263 // is actually used.
2264 if (Info.diag_begin() != Info.diag_end()) {
2265 llvm::DenseMap<Decl *, llvm::SmallVector<PartialDiagnosticAt, 1> >::iterator
2266 Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2267 if (Pos == SuppressedDiagnostics.end())
2268 SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2269 .append(Info.diag_begin(), Info.diag_end());
2270 }
2271
Mike Stump1eb44332009-09-09 15:08:12 +00002272 return TDK_Success;
Douglas Gregor83314aa2009-07-08 20:55:45 +00002273}
2274
John McCall9c72c602010-08-27 09:08:28 +00002275/// Gets the type of a function for template-argument-deducton
2276/// purposes when it's considered as part of an overload set.
John McCalleff92132010-02-02 02:21:27 +00002277static QualType GetTypeOfFunction(ASTContext &Context,
John McCall9c72c602010-08-27 09:08:28 +00002278 const OverloadExpr::FindResult &R,
John McCalleff92132010-02-02 02:21:27 +00002279 FunctionDecl *Fn) {
John McCalleff92132010-02-02 02:21:27 +00002280 if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
John McCall9c72c602010-08-27 09:08:28 +00002281 if (Method->isInstance()) {
2282 // An instance method that's referenced in a form that doesn't
2283 // look like a member pointer is just invalid.
2284 if (!R.HasFormOfMemberPointer) return QualType();
2285
John McCalleff92132010-02-02 02:21:27 +00002286 return Context.getMemberPointerType(Fn->getType(),
2287 Context.getTypeDeclType(Method->getParent()).getTypePtr());
John McCall9c72c602010-08-27 09:08:28 +00002288 }
2289
2290 if (!R.IsAddressOfOperand) return Fn->getType();
John McCalleff92132010-02-02 02:21:27 +00002291 return Context.getPointerType(Fn->getType());
2292}
2293
2294/// Apply the deduction rules for overload sets.
2295///
2296/// \return the null type if this argument should be treated as an
2297/// undeduced context
2298static QualType
2299ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
Douglas Gregor75f21af2010-08-30 21:04:23 +00002300 Expr *Arg, QualType ParamType,
2301 bool ParamWasReference) {
John McCall9c72c602010-08-27 09:08:28 +00002302
2303 OverloadExpr::FindResult R = OverloadExpr::find(Arg);
John McCalleff92132010-02-02 02:21:27 +00002304
John McCall9c72c602010-08-27 09:08:28 +00002305 OverloadExpr *Ovl = R.Expression;
John McCalleff92132010-02-02 02:21:27 +00002306
Douglas Gregor75f21af2010-08-30 21:04:23 +00002307 // C++0x [temp.deduct.call]p4
2308 unsigned TDF = 0;
2309 if (ParamWasReference)
2310 TDF |= TDF_ParamWithReferenceType;
2311 if (R.IsAddressOfOperand)
2312 TDF |= TDF_IgnoreQualifiers;
2313
John McCalleff92132010-02-02 02:21:27 +00002314 // If there were explicit template arguments, we can only find
2315 // something via C++ [temp.arg.explicit]p3, i.e. if the arguments
2316 // unambiguously name a full specialization.
John McCall7bb12da2010-02-02 06:20:04 +00002317 if (Ovl->hasExplicitTemplateArgs()) {
John McCalleff92132010-02-02 02:21:27 +00002318 // But we can still look for an explicit specialization.
2319 if (FunctionDecl *ExplicitSpec
John McCall7bb12da2010-02-02 06:20:04 +00002320 = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
John McCall9c72c602010-08-27 09:08:28 +00002321 return GetTypeOfFunction(S.Context, R, ExplicitSpec);
John McCalleff92132010-02-02 02:21:27 +00002322 return QualType();
2323 }
2324
2325 // C++0x [temp.deduct.call]p6:
2326 // When P is a function type, pointer to function type, or pointer
2327 // to member function type:
2328
2329 if (!ParamType->isFunctionType() &&
2330 !ParamType->isFunctionPointerType() &&
2331 !ParamType->isMemberFunctionPointerType())
2332 return QualType();
2333
2334 QualType Match;
John McCall7bb12da2010-02-02 06:20:04 +00002335 for (UnresolvedSetIterator I = Ovl->decls_begin(),
2336 E = Ovl->decls_end(); I != E; ++I) {
John McCalleff92132010-02-02 02:21:27 +00002337 NamedDecl *D = (*I)->getUnderlyingDecl();
2338
2339 // - If the argument is an overload set containing one or more
2340 // function templates, the parameter is treated as a
2341 // non-deduced context.
2342 if (isa<FunctionTemplateDecl>(D))
2343 return QualType();
2344
2345 FunctionDecl *Fn = cast<FunctionDecl>(D);
John McCall9c72c602010-08-27 09:08:28 +00002346 QualType ArgType = GetTypeOfFunction(S.Context, R, Fn);
2347 if (ArgType.isNull()) continue;
John McCalleff92132010-02-02 02:21:27 +00002348
Douglas Gregor75f21af2010-08-30 21:04:23 +00002349 // Function-to-pointer conversion.
2350 if (!ParamWasReference && ParamType->isPointerType() &&
2351 ArgType->isFunctionType())
2352 ArgType = S.Context.getPointerType(ArgType);
2353
John McCalleff92132010-02-02 02:21:27 +00002354 // - If the argument is an overload set (not containing function
2355 // templates), trial argument deduction is attempted using each
2356 // of the members of the set. If deduction succeeds for only one
2357 // of the overload set members, that member is used as the
2358 // argument value for the deduction. If deduction succeeds for
2359 // more than one member of the overload set the parameter is
2360 // treated as a non-deduced context.
2361
2362 // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
2363 // Type deduction is done independently for each P/A pair, and
2364 // the deduced template argument values are then combined.
2365 // So we do not reject deductions which were made elsewhere.
Douglas Gregor02024a92010-03-28 02:42:43 +00002366 llvm::SmallVector<DeducedTemplateArgument, 8>
2367 Deduced(TemplateParams->size());
John McCall2a7fb272010-08-25 05:32:35 +00002368 TemplateDeductionInfo Info(S.Context, Ovl->getNameLoc());
John McCalleff92132010-02-02 02:21:27 +00002369 Sema::TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00002370 = DeduceTemplateArguments(S, TemplateParams,
John McCalleff92132010-02-02 02:21:27 +00002371 ParamType, ArgType,
2372 Info, Deduced, TDF);
2373 if (Result) continue;
2374 if (!Match.isNull()) return QualType();
2375 Match = ArgType;
2376 }
2377
2378 return Match;
2379}
2380
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002381/// \brief Perform the adjustments to the parameter and argument types
2382/// described in C++ [temp.deduct.call].
2383///
2384/// \returns true if the caller should not attempt to perform any template
2385/// argument deduction based on this P/A pair.
2386static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
2387 TemplateParameterList *TemplateParams,
2388 QualType &ParamType,
2389 QualType &ArgType,
2390 Expr *Arg,
2391 unsigned &TDF) {
2392 // C++0x [temp.deduct.call]p3:
2393 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type
2394 // are ignored for type deduction.
2395 if (ParamType.getCVRQualifiers())
2396 ParamType = ParamType.getLocalUnqualifiedType();
2397 const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
2398 if (ParamRefType) {
2399 // [...] If P is a reference type, the type referred to by P is used
2400 // for type deduction.
2401 ParamType = ParamRefType->getPointeeType();
2402 }
Douglas Gregor5c7bf422011-01-11 17:34:58 +00002403
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002404 // Overload sets usually make this parameter an undeduced
2405 // context, but there are sometimes special circumstances.
2406 if (ArgType == S.Context.OverloadTy) {
2407 ArgType = ResolveOverloadForDeduction(S, TemplateParams,
2408 Arg, ParamType,
2409 ParamRefType != 0);
2410 if (ArgType.isNull())
2411 return true;
2412 }
2413
2414 if (ParamRefType) {
2415 // C++0x [temp.deduct.call]p3:
2416 // [...] If P is of the form T&&, where T is a template parameter, and
2417 // the argument is an lvalue, the type A& is used in place of A for
2418 // type deduction.
2419 if (ParamRefType->isRValueReferenceType() &&
2420 ParamRefType->getAs<TemplateTypeParmType>() &&
2421 Arg->isLValue())
2422 ArgType = S.Context.getLValueReferenceType(ArgType);
2423 } else {
2424 // C++ [temp.deduct.call]p2:
2425 // If P is not a reference type:
2426 // - If A is an array type, the pointer type produced by the
2427 // array-to-pointer standard conversion (4.2) is used in place of
2428 // A for type deduction; otherwise,
2429 if (ArgType->isArrayType())
2430 ArgType = S.Context.getArrayDecayedType(ArgType);
2431 // - If A is a function type, the pointer type produced by the
2432 // function-to-pointer standard conversion (4.3) is used in place
2433 // of A for type deduction; otherwise,
2434 else if (ArgType->isFunctionType())
2435 ArgType = S.Context.getPointerType(ArgType);
2436 else {
2437 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s
2438 // type are ignored for type deduction.
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002439 if (ArgType.getCVRQualifiers())
2440 ArgType = ArgType.getUnqualifiedType();
2441 }
2442 }
2443
2444 // C++0x [temp.deduct.call]p4:
2445 // In general, the deduction process attempts to find template argument
2446 // values that will make the deduced A identical to A (after the type A
2447 // is transformed as described above). [...]
2448 TDF = TDF_SkipNonDependent;
2449
2450 // - If the original P is a reference type, the deduced A (i.e., the
2451 // type referred to by the reference) can be more cv-qualified than
2452 // the transformed A.
2453 if (ParamRefType)
2454 TDF |= TDF_ParamWithReferenceType;
2455 // - The transformed A can be another pointer or pointer to member
2456 // type that can be converted to the deduced A via a qualification
2457 // conversion (4.4).
2458 if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
2459 ArgType->isObjCObjectPointerType())
2460 TDF |= TDF_IgnoreQualifiers;
2461 // - If P is a class and P has the form simple-template-id, then the
2462 // transformed A can be a derived class of the deduced A. Likewise,
2463 // if P is a pointer to a class of the form simple-template-id, the
2464 // transformed A can be a pointer to a derived class pointed to by
2465 // the deduced A.
2466 if (isSimpleTemplateIdType(ParamType) ||
2467 (isa<PointerType>(ParamType) &&
2468 isSimpleTemplateIdType(
2469 ParamType->getAs<PointerType>()->getPointeeType())))
2470 TDF |= TDF_DerivedClass;
2471
2472 return false;
2473}
2474
Douglas Gregore53060f2009-06-25 22:08:12 +00002475/// \brief Perform template argument deduction from a function call
2476/// (C++ [temp.deduct.call]).
2477///
2478/// \param FunctionTemplate the function template for which we are performing
2479/// template argument deduction.
2480///
Douglas Gregor48026d22010-01-11 18:40:55 +00002481/// \param ExplicitTemplateArguments the explicit template arguments provided
2482/// for this call.
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002483///
Douglas Gregore53060f2009-06-25 22:08:12 +00002484/// \param Args the function call arguments
2485///
2486/// \param NumArgs the number of arguments in Args
2487///
Douglas Gregor48026d22010-01-11 18:40:55 +00002488/// \param Name the name of the function being called. This is only significant
2489/// when the function template is a conversion function template, in which
2490/// case this routine will also perform template argument deduction based on
2491/// the function to which
2492///
Douglas Gregore53060f2009-06-25 22:08:12 +00002493/// \param Specialization if template argument deduction was successful,
Mike Stump1eb44332009-09-09 15:08:12 +00002494/// this will be set to the function template specialization produced by
Douglas Gregore53060f2009-06-25 22:08:12 +00002495/// template argument deduction.
2496///
2497/// \param Info the argument will be updated to provide additional information
2498/// about template argument deduction.
2499///
2500/// \returns the result of template argument deduction.
Douglas Gregore53060f2009-06-25 22:08:12 +00002501Sema::TemplateDeductionResult
2502Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
Douglas Gregor48026d22010-01-11 18:40:55 +00002503 const TemplateArgumentListInfo *ExplicitTemplateArgs,
Douglas Gregore53060f2009-06-25 22:08:12 +00002504 Expr **Args, unsigned NumArgs,
2505 FunctionDecl *&Specialization,
2506 TemplateDeductionInfo &Info) {
2507 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002508
Douglas Gregore53060f2009-06-25 22:08:12 +00002509 // C++ [temp.deduct.call]p1:
2510 // Template argument deduction is done by comparing each function template
2511 // parameter type (call it P) with the type of the corresponding argument
2512 // of the call (call it A) as described below.
2513 unsigned CheckArgs = NumArgs;
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002514 if (NumArgs < Function->getMinRequiredArguments())
Douglas Gregore53060f2009-06-25 22:08:12 +00002515 return TDK_TooFewArguments;
2516 else if (NumArgs > Function->getNumParams()) {
Mike Stump1eb44332009-09-09 15:08:12 +00002517 const FunctionProtoType *Proto
John McCall183700f2009-09-21 23:43:11 +00002518 = Function->getType()->getAs<FunctionProtoType>();
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002519 if (Proto->isTemplateVariadic())
2520 /* Do nothing */;
2521 else if (Proto->isVariadic())
2522 CheckArgs = Function->getNumParams();
2523 else
Douglas Gregore53060f2009-06-25 22:08:12 +00002524 return TDK_TooManyArguments;
Douglas Gregore53060f2009-06-25 22:08:12 +00002525 }
Mike Stump1eb44332009-09-09 15:08:12 +00002526
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002527 // The types of the parameters from which we will perform template argument
2528 // deduction.
John McCall2a7fb272010-08-25 05:32:35 +00002529 LocalInstantiationScope InstScope(*this);
Douglas Gregore53060f2009-06-25 22:08:12 +00002530 TemplateParameterList *TemplateParams
2531 = FunctionTemplate->getTemplateParameters();
Douglas Gregor02024a92010-03-28 02:42:43 +00002532 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002533 llvm::SmallVector<QualType, 4> ParamTypes;
Douglas Gregor02024a92010-03-28 02:42:43 +00002534 unsigned NumExplicitlySpecified = 0;
John McCalld5532b62009-11-23 01:53:49 +00002535 if (ExplicitTemplateArgs) {
Douglas Gregor83314aa2009-07-08 20:55:45 +00002536 TemplateDeductionResult Result =
2537 SubstituteExplicitTemplateArguments(FunctionTemplate,
John McCalld5532b62009-11-23 01:53:49 +00002538 *ExplicitTemplateArgs,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002539 Deduced,
2540 ParamTypes,
2541 0,
2542 Info);
2543 if (Result)
2544 return Result;
Douglas Gregor02024a92010-03-28 02:42:43 +00002545
2546 NumExplicitlySpecified = Deduced.size();
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002547 } else {
2548 // Just fill in the parameter types from the function declaration.
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002549 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002550 ParamTypes.push_back(Function->getParamDecl(I)->getType());
2551 }
Mike Stump1eb44332009-09-09 15:08:12 +00002552
Douglas Gregor6db8ed42009-06-30 23:57:56 +00002553 // Deduce template arguments from the function parameters.
Mike Stump1eb44332009-09-09 15:08:12 +00002554 Deduced.resize(TemplateParams->size());
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002555 unsigned ArgIdx = 0;
2556 for (unsigned ParamIdx = 0, NumParams = ParamTypes.size();
2557 ParamIdx != NumParams; ++ParamIdx) {
2558 QualType ParamType = ParamTypes[ParamIdx];
2559
2560 const PackExpansionType *ParamExpansion
2561 = dyn_cast<PackExpansionType>(ParamType);
2562 if (!ParamExpansion) {
2563 // Simple case: matching a function parameter to a function argument.
2564 if (ArgIdx >= CheckArgs)
2565 break;
2566
2567 Expr *Arg = Args[ArgIdx++];
2568 QualType ArgType = Arg->getType();
2569 unsigned TDF = 0;
2570 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
2571 ParamType, ArgType, Arg,
2572 TDF))
2573 continue;
2574
2575 if (TemplateDeductionResult Result
2576 = ::DeduceTemplateArguments(*this, TemplateParams,
2577 ParamType, ArgType, Info, Deduced,
2578 TDF))
2579 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002580
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002581 // FIXME: we need to check that the deduced A is the same as A,
2582 // modulo the various allowed differences.
2583 continue;
Douglas Gregor75f21af2010-08-30 21:04:23 +00002584 }
2585
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002586 // C++0x [temp.deduct.call]p1:
2587 // For a function parameter pack that occurs at the end of the
2588 // parameter-declaration-list, the type A of each remaining argument of
2589 // the call is compared with the type P of the declarator-id of the
2590 // function parameter pack. Each comparison deduces template arguments
2591 // for subsequent positions in the template parameter packs expanded by
Douglas Gregor7d5c0c12011-01-11 01:52:23 +00002592 // the function parameter pack. For a function parameter pack that does
2593 // not occur at the end of the parameter-declaration-list, the type of
2594 // the parameter pack is a non-deduced context.
2595 if (ParamIdx + 1 < NumParams)
2596 break;
2597
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002598 QualType ParamPattern = ParamExpansion->getPattern();
2599 llvm::SmallVector<unsigned, 2> PackIndices;
2600 {
2601 llvm::BitVector SawIndices(TemplateParams->size());
2602 llvm::SmallVector<UnexpandedParameterPack, 2> Unexpanded;
2603 collectUnexpandedParameterPacks(ParamPattern, Unexpanded);
2604 for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
2605 unsigned Depth, Index;
2606 llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
2607 if (Depth == 0 && !SawIndices[Index]) {
2608 SawIndices[Index] = true;
2609 PackIndices.push_back(Index);
2610 }
Douglas Gregore53060f2009-06-25 22:08:12 +00002611 }
2612 }
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002613 assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
2614
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002615 // Keep track of the deduced template arguments for each parameter pack
2616 // expanded by this pack expansion (the outer index) and for each
2617 // template argument (the inner SmallVectors).
2618 llvm::SmallVector<llvm::SmallVector<DeducedTemplateArgument, 4>, 2>
Douglas Gregord3731192011-01-10 07:32:04 +00002619 NewlyDeducedPacks(PackIndices.size());
Douglas Gregord3731192011-01-10 07:32:04 +00002620 llvm::SmallVector<DeducedTemplateArgument, 2>
2621 SavedPacks(PackIndices.size());
Douglas Gregor54293852011-01-10 17:35:05 +00002622 PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks,
2623 NewlyDeducedPacks);
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002624 bool HasAnyArguments = false;
2625 for (; ArgIdx < NumArgs; ++ArgIdx) {
2626 HasAnyArguments = true;
2627
2628 ParamType = ParamPattern;
2629 Expr *Arg = Args[ArgIdx];
2630 QualType ArgType = Arg->getType();
2631 unsigned TDF = 0;
2632 if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
2633 ParamType, ArgType, Arg,
2634 TDF)) {
2635 // We can't actually perform any deduction for this argument, so stop
2636 // deduction at this point.
2637 ++ArgIdx;
2638 break;
2639 }
2640
2641 if (TemplateDeductionResult Result
2642 = ::DeduceTemplateArguments(*this, TemplateParams,
2643 ParamType, ArgType, Info, Deduced,
2644 TDF))
2645 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002646
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002647 // Capture the deduced template arguments for each parameter pack expanded
2648 // by this pack expansion, add them to the list of arguments we've deduced
2649 // for that pack, then clear out the deduced argument.
2650 for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
2651 DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
2652 if (!DeducedArg.isNull()) {
2653 NewlyDeducedPacks[I].push_back(DeducedArg);
2654 DeducedArg = DeducedTemplateArgument();
2655 }
2656 }
2657 }
2658
2659 // Build argument packs for each of the parameter packs expanded by this
2660 // pack expansion.
Douglas Gregor0216f812011-01-10 17:53:52 +00002661 if (Sema::TemplateDeductionResult Result
2662 = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments,
2663 Deduced, PackIndices, SavedPacks,
2664 NewlyDeducedPacks, Info))
2665 return Result;
Mike Stump1eb44332009-09-09 15:08:12 +00002666
Douglas Gregorf5c65ff2011-01-06 22:09:01 +00002667 // After we've matching against a parameter pack, we're done.
2668 break;
Douglas Gregore53060f2009-06-25 22:08:12 +00002669 }
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002670
Mike Stump1eb44332009-09-09 15:08:12 +00002671 return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
Douglas Gregor02024a92010-03-28 02:42:43 +00002672 NumExplicitlySpecified,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002673 Specialization, Info);
Douglas Gregore53060f2009-06-25 22:08:12 +00002674}
2675
Douglas Gregor83314aa2009-07-08 20:55:45 +00002676/// \brief Deduce template arguments when taking the address of a function
Douglas Gregor4b52e252009-12-21 23:17:24 +00002677/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
2678/// a template.
Douglas Gregor83314aa2009-07-08 20:55:45 +00002679///
2680/// \param FunctionTemplate the function template for which we are performing
2681/// template argument deduction.
2682///
Douglas Gregor4b52e252009-12-21 23:17:24 +00002683/// \param ExplicitTemplateArguments the explicitly-specified template
2684/// arguments.
Douglas Gregor83314aa2009-07-08 20:55:45 +00002685///
2686/// \param ArgFunctionType the function type that will be used as the
2687/// "argument" type (A) when performing template argument deduction from the
Douglas Gregor4b52e252009-12-21 23:17:24 +00002688/// function template's function type. This type may be NULL, if there is no
2689/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
Douglas Gregor83314aa2009-07-08 20:55:45 +00002690///
2691/// \param Specialization if template argument deduction was successful,
Mike Stump1eb44332009-09-09 15:08:12 +00002692/// this will be set to the function template specialization produced by
Douglas Gregor83314aa2009-07-08 20:55:45 +00002693/// template argument deduction.
2694///
2695/// \param Info the argument will be updated to provide additional information
2696/// about template argument deduction.
2697///
2698/// \returns the result of template argument deduction.
2699Sema::TemplateDeductionResult
2700Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
John McCalld5532b62009-11-23 01:53:49 +00002701 const TemplateArgumentListInfo *ExplicitTemplateArgs,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002702 QualType ArgFunctionType,
2703 FunctionDecl *&Specialization,
2704 TemplateDeductionInfo &Info) {
2705 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2706 TemplateParameterList *TemplateParams
2707 = FunctionTemplate->getTemplateParameters();
2708 QualType FunctionType = Function->getType();
Mike Stump1eb44332009-09-09 15:08:12 +00002709
Douglas Gregor83314aa2009-07-08 20:55:45 +00002710 // Substitute any explicit template arguments.
John McCall2a7fb272010-08-25 05:32:35 +00002711 LocalInstantiationScope InstScope(*this);
Douglas Gregor02024a92010-03-28 02:42:43 +00002712 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
2713 unsigned NumExplicitlySpecified = 0;
Douglas Gregor83314aa2009-07-08 20:55:45 +00002714 llvm::SmallVector<QualType, 4> ParamTypes;
John McCalld5532b62009-11-23 01:53:49 +00002715 if (ExplicitTemplateArgs) {
Mike Stump1eb44332009-09-09 15:08:12 +00002716 if (TemplateDeductionResult Result
2717 = SubstituteExplicitTemplateArguments(FunctionTemplate,
John McCalld5532b62009-11-23 01:53:49 +00002718 *ExplicitTemplateArgs,
Mike Stump1eb44332009-09-09 15:08:12 +00002719 Deduced, ParamTypes,
Douglas Gregor83314aa2009-07-08 20:55:45 +00002720 &FunctionType, Info))
2721 return Result;
Douglas Gregor02024a92010-03-28 02:42:43 +00002722
2723 NumExplicitlySpecified = Deduced.size();
Douglas Gregor83314aa2009-07-08 20:55:45 +00002724 }
2725
2726 // Template argument deduction for function templates in a SFINAE context.
2727 // Trap any errors that might occur.
Mike Stump1eb44332009-09-09 15:08:12 +00002728 SFINAETrap Trap(*this);
2729
John McCalleff92132010-02-02 02:21:27 +00002730 Deduced.resize(TemplateParams->size());
2731
Douglas Gregor4b52e252009-12-21 23:17:24 +00002732 if (!ArgFunctionType.isNull()) {
2733 // Deduce template arguments from the function type.
Douglas Gregor4b52e252009-12-21 23:17:24 +00002734 if (TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00002735 = ::DeduceTemplateArguments(*this, TemplateParams,
Douglas Gregor4b52e252009-12-21 23:17:24 +00002736 FunctionType, ArgFunctionType, Info,
2737 Deduced, 0))
2738 return Result;
2739 }
Douglas Gregorfbb6fad2010-09-29 21:14:36 +00002740
2741 if (TemplateDeductionResult Result
2742 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
2743 NumExplicitlySpecified,
2744 Specialization, Info))
2745 return Result;
2746
2747 // If the requested function type does not match the actual type of the
2748 // specialization, template argument deduction fails.
2749 if (!ArgFunctionType.isNull() &&
2750 !Context.hasSameType(ArgFunctionType, Specialization->getType()))
2751 return TDK_NonDeducedMismatch;
2752
2753 return TDK_Success;
Douglas Gregor83314aa2009-07-08 20:55:45 +00002754}
2755
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002756/// \brief Deduce template arguments for a templated conversion
2757/// function (C++ [temp.deduct.conv]) and, if successful, produce a
2758/// conversion function template specialization.
2759Sema::TemplateDeductionResult
2760Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2761 QualType ToType,
2762 CXXConversionDecl *&Specialization,
2763 TemplateDeductionInfo &Info) {
Mike Stump1eb44332009-09-09 15:08:12 +00002764 CXXConversionDecl *Conv
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002765 = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl());
2766 QualType FromType = Conv->getConversionType();
2767
2768 // Canonicalize the types for deduction.
2769 QualType P = Context.getCanonicalType(FromType);
2770 QualType A = Context.getCanonicalType(ToType);
2771
2772 // C++0x [temp.deduct.conv]p3:
2773 // If P is a reference type, the type referred to by P is used for
2774 // type deduction.
2775 if (const ReferenceType *PRef = P->getAs<ReferenceType>())
2776 P = PRef->getPointeeType();
2777
2778 // C++0x [temp.deduct.conv]p3:
2779 // If A is a reference type, the type referred to by A is used
2780 // for type deduction.
2781 if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2782 A = ARef->getPointeeType();
2783 // C++ [temp.deduct.conv]p2:
2784 //
Mike Stump1eb44332009-09-09 15:08:12 +00002785 // If A is not a reference type:
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002786 else {
2787 assert(!A->isReferenceType() && "Reference types were handled above");
2788
2789 // - If P is an array type, the pointer type produced by the
Mike Stump1eb44332009-09-09 15:08:12 +00002790 // array-to-pointer standard conversion (4.2) is used in place
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002791 // of P for type deduction; otherwise,
2792 if (P->isArrayType())
2793 P = Context.getArrayDecayedType(P);
2794 // - If P is a function type, the pointer type produced by the
2795 // function-to-pointer standard conversion (4.3) is used in
2796 // place of P for type deduction; otherwise,
2797 else if (P->isFunctionType())
2798 P = Context.getPointerType(P);
2799 // - If P is a cv-qualified type, the top level cv-qualifiers of
2800 // P’s type are ignored for type deduction.
2801 else
2802 P = P.getUnqualifiedType();
2803
2804 // C++0x [temp.deduct.conv]p3:
2805 // If A is a cv-qualified type, the top level cv-qualifiers of A’s
2806 // type are ignored for type deduction.
2807 A = A.getUnqualifiedType();
2808 }
2809
2810 // Template argument deduction for function templates in a SFINAE context.
2811 // Trap any errors that might occur.
Mike Stump1eb44332009-09-09 15:08:12 +00002812 SFINAETrap Trap(*this);
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002813
2814 // C++ [temp.deduct.conv]p1:
2815 // Template argument deduction is done by comparing the return
2816 // type of the template conversion function (call it P) with the
2817 // type that is required as the result of the conversion (call it
2818 // A) as described in 14.8.2.4.
2819 TemplateParameterList *TemplateParams
2820 = FunctionTemplate->getTemplateParameters();
Douglas Gregor02024a92010-03-28 02:42:43 +00002821 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
Mike Stump1eb44332009-09-09 15:08:12 +00002822 Deduced.resize(TemplateParams->size());
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002823
2824 // C++0x [temp.deduct.conv]p4:
2825 // In general, the deduction process attempts to find template
2826 // argument values that will make the deduced A identical to
2827 // A. However, there are two cases that allow a difference:
2828 unsigned TDF = 0;
2829 // - If the original A is a reference type, A can be more
2830 // cv-qualified than the deduced A (i.e., the type referred to
2831 // by the reference)
2832 if (ToType->isReferenceType())
2833 TDF |= TDF_ParamWithReferenceType;
2834 // - The deduced A can be another pointer or pointer to member
2835 // type that can be converted to A via a qualification
2836 // conversion.
2837 //
2838 // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
2839 // both P and A are pointers or member pointers. In this case, we
2840 // just ignore cv-qualifiers completely).
2841 if ((P->isPointerType() && A->isPointerType()) ||
2842 (P->isMemberPointerType() && P->isMemberPointerType()))
2843 TDF |= TDF_IgnoreQualifiers;
2844 if (TemplateDeductionResult Result
Chandler Carrutha7ef1302010-02-07 21:33:28 +00002845 = ::DeduceTemplateArguments(*this, TemplateParams,
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002846 P, A, Info, Deduced, TDF))
2847 return Result;
2848
2849 // FIXME: we need to check that the deduced A is the same as A,
2850 // modulo the various allowed differences.
Mike Stump1eb44332009-09-09 15:08:12 +00002851
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002852 // Finish template argument deduction.
John McCall2a7fb272010-08-25 05:32:35 +00002853 LocalInstantiationScope InstScope(*this);
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002854 FunctionDecl *Spec = 0;
2855 TemplateDeductionResult Result
Douglas Gregor02024a92010-03-28 02:42:43 +00002856 = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec,
2857 Info);
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00002858 Specialization = cast_or_null<CXXConversionDecl>(Spec);
2859 return Result;
2860}
2861
Douglas Gregor4b52e252009-12-21 23:17:24 +00002862/// \brief Deduce template arguments for a function template when there is
2863/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
2864///
2865/// \param FunctionTemplate the function template for which we are performing
2866/// template argument deduction.
2867///
2868/// \param ExplicitTemplateArguments the explicitly-specified template
2869/// arguments.
2870///
2871/// \param Specialization if template argument deduction was successful,
2872/// this will be set to the function template specialization produced by
2873/// template argument deduction.
2874///
2875/// \param Info the argument will be updated to provide additional information
2876/// about template argument deduction.
2877///
2878/// \returns the result of template argument deduction.
2879Sema::TemplateDeductionResult
2880Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
2881 const TemplateArgumentListInfo *ExplicitTemplateArgs,
2882 FunctionDecl *&Specialization,
2883 TemplateDeductionInfo &Info) {
2884 return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
2885 QualType(), Specialization, Info);
2886}
2887
Douglas Gregor8a514912009-09-14 18:39:43 +00002888static void
Douglas Gregore73bb602009-09-14 21:25:05 +00002889MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
2890 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00002891 unsigned Level,
Douglas Gregore73bb602009-09-14 21:25:05 +00002892 llvm::SmallVectorImpl<bool> &Deduced);
Douglas Gregor77bc5722010-11-12 23:44:13 +00002893
2894/// \brief If this is a non-static member function,
2895static void MaybeAddImplicitObjectParameterType(ASTContext &Context,
2896 CXXMethodDecl *Method,
2897 llvm::SmallVectorImpl<QualType> &ArgTypes) {
2898 if (Method->isStatic())
2899 return;
2900
2901 // C++ [over.match.funcs]p4:
2902 //
2903 // For non-static member functions, the type of the implicit
2904 // object parameter is
2905 // — "lvalue reference to cv X" for functions declared without a
2906 // ref-qualifier or with the & ref-qualifier
2907 // - "rvalue reference to cv X" for functions declared with the
2908 // && ref-qualifier
2909 //
2910 // FIXME: We don't have ref-qualifiers yet, so we don't do that part.
2911 QualType ArgTy = Context.getTypeDeclType(Method->getParent());
2912 ArgTy = Context.getQualifiedType(ArgTy,
2913 Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
2914 ArgTy = Context.getLValueReferenceType(ArgTy);
2915 ArgTypes.push_back(ArgTy);
2916}
2917
Douglas Gregor8a514912009-09-14 18:39:43 +00002918/// \brief Determine whether the function template \p FT1 is at least as
2919/// specialized as \p FT2.
2920static bool isAtLeastAsSpecializedAs(Sema &S,
John McCall5769d612010-02-08 23:07:23 +00002921 SourceLocation Loc,
Douglas Gregor8a514912009-09-14 18:39:43 +00002922 FunctionTemplateDecl *FT1,
2923 FunctionTemplateDecl *FT2,
2924 TemplatePartialOrderingContext TPOC,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00002925 unsigned NumCallArguments,
Douglas Gregor8a514912009-09-14 18:39:43 +00002926 llvm::SmallVectorImpl<DeductionQualifierComparison> *QualifierComparisons) {
2927 FunctionDecl *FD1 = FT1->getTemplatedDecl();
2928 FunctionDecl *FD2 = FT2->getTemplatedDecl();
2929 const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
2930 const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
2931
2932 assert(Proto1 && Proto2 && "Function templates must have prototypes");
2933 TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
Douglas Gregor02024a92010-03-28 02:42:43 +00002934 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
Douglas Gregor8a514912009-09-14 18:39:43 +00002935 Deduced.resize(TemplateParams->size());
2936
2937 // C++0x [temp.deduct.partial]p3:
2938 // The types used to determine the ordering depend on the context in which
2939 // the partial ordering is done:
John McCall2a7fb272010-08-25 05:32:35 +00002940 TemplateDeductionInfo Info(S.Context, Loc);
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002941 CXXMethodDecl *Method1 = 0;
2942 CXXMethodDecl *Method2 = 0;
2943 bool IsNonStatic2 = false;
2944 bool IsNonStatic1 = false;
2945 unsigned Skip2 = 0;
Douglas Gregor8a514912009-09-14 18:39:43 +00002946 switch (TPOC) {
2947 case TPOC_Call: {
2948 // - In the context of a function call, the function parameter types are
2949 // used.
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002950 Method1 = dyn_cast<CXXMethodDecl>(FD1);
2951 Method2 = dyn_cast<CXXMethodDecl>(FD2);
2952 IsNonStatic1 = Method1 && !Method1->isStatic();
2953 IsNonStatic2 = Method2 && !Method2->isStatic();
2954
2955 // C++0x [temp.func.order]p3:
2956 // [...] If only one of the function templates is a non-static
2957 // member, that function template is considered to have a new
2958 // first parameter inserted in its function parameter list. The
2959 // new parameter is of type "reference to cv A," where cv are
2960 // the cv-qualifiers of the function template (if any) and A is
2961 // the class of which the function template is a member.
2962 //
2963 // C++98/03 doesn't have this provision, so instead we drop the
2964 // first argument of the free function or static member, which
2965 // seems to match existing practice.
Douglas Gregor77bc5722010-11-12 23:44:13 +00002966 llvm::SmallVector<QualType, 4> Args1;
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002967 unsigned Skip1 = !S.getLangOptions().CPlusPlus0x &&
2968 IsNonStatic2 && !IsNonStatic1;
2969 if (S.getLangOptions().CPlusPlus0x && IsNonStatic1 && !IsNonStatic2)
Douglas Gregor5c7bf422011-01-11 17:34:58 +00002970 MaybeAddImplicitObjectParameterType(S.Context, Method1, Args1);
Douglas Gregor77bc5722010-11-12 23:44:13 +00002971 Args1.insert(Args1.end(),
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002972 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end());
Douglas Gregor77bc5722010-11-12 23:44:13 +00002973
2974 llvm::SmallVector<QualType, 4> Args2;
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002975 Skip2 = !S.getLangOptions().CPlusPlus0x &&
2976 IsNonStatic1 && !IsNonStatic2;
2977 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
Douglas Gregor77bc5722010-11-12 23:44:13 +00002978 MaybeAddImplicitObjectParameterType(S.Context, Method2, Args2);
2979 Args2.insert(Args2.end(),
Douglas Gregor8d706ec2010-11-15 15:41:16 +00002980 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end());
Douglas Gregor5c7bf422011-01-11 17:34:58 +00002981
2982 // C++ [temp.func.order]p5:
2983 // The presence of unused ellipsis and default arguments has no effect on
2984 // the partial ordering of function templates.
2985 if (Args1.size() > NumCallArguments)
2986 Args1.resize(NumCallArguments);
2987 if (Args2.size() > NumCallArguments)
2988 Args2.resize(NumCallArguments);
2989 if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
2990 Args1.data(), Args1.size(), Info, Deduced,
2991 TDF_None, /*PartialOrdering=*/true,
2992 QualifierComparisons))
Douglas Gregor8a514912009-09-14 18:39:43 +00002993 return false;
2994
2995 break;
2996 }
2997
2998 case TPOC_Conversion:
2999 // - In the context of a call to a conversion operator, the return types
3000 // of the conversion function templates are used.
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003001 if (DeduceTemplateArguments(S, TemplateParams, Proto2->getResultType(),
3002 Proto1->getResultType(), Info, Deduced,
3003 TDF_None, /*PartialOrdering=*/true,
3004 QualifierComparisons))
Douglas Gregor8a514912009-09-14 18:39:43 +00003005 return false;
3006 break;
3007
3008 case TPOC_Other:
3009 // - In other contexts (14.6.6.2) the function template’s function type
3010 // is used.
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003011 // FIXME: Don't we actually want to perform the adjustments on the parameter
3012 // types?
3013 if (DeduceTemplateArguments(S, TemplateParams, FD2->getType(),
3014 FD1->getType(), Info, Deduced, TDF_None,
3015 /*PartialOrdering=*/true, QualifierComparisons))
Douglas Gregor8a514912009-09-14 18:39:43 +00003016 return false;
3017 break;
3018 }
3019
3020 // C++0x [temp.deduct.partial]p11:
3021 // In most cases, all template parameters must have values in order for
3022 // deduction to succeed, but for partial ordering purposes a template
3023 // parameter may remain without a value provided it is not used in the
3024 // types being used for partial ordering. [ Note: a template parameter used
3025 // in a non-deduced context is considered used. -end note]
3026 unsigned ArgIdx = 0, NumArgs = Deduced.size();
3027 for (; ArgIdx != NumArgs; ++ArgIdx)
3028 if (Deduced[ArgIdx].isNull())
3029 break;
3030
3031 if (ArgIdx == NumArgs) {
3032 // All template arguments were deduced. FT1 is at least as specialized
3033 // as FT2.
3034 return true;
3035 }
3036
Douglas Gregore73bb602009-09-14 21:25:05 +00003037 // Figure out which template parameters were used.
Douglas Gregor8a514912009-09-14 18:39:43 +00003038 llvm::SmallVector<bool, 4> UsedParameters;
3039 UsedParameters.resize(TemplateParams->size());
3040 switch (TPOC) {
3041 case TPOC_Call: {
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003042 unsigned NumParams = std::min(NumCallArguments,
3043 std::min(Proto1->getNumArgs(),
3044 Proto2->getNumArgs()));
Douglas Gregor8d706ec2010-11-15 15:41:16 +00003045 if (S.getLangOptions().CPlusPlus0x && IsNonStatic2 && !IsNonStatic1)
3046 ::MarkUsedTemplateParameters(S, Method2->getThisType(S.Context), false,
3047 TemplateParams->getDepth(), UsedParameters);
3048 for (unsigned I = Skip2; I < NumParams; ++I)
Douglas Gregored9c0f92009-10-29 00:04:11 +00003049 ::MarkUsedTemplateParameters(S, Proto2->getArgType(I), false,
3050 TemplateParams->getDepth(),
Douglas Gregore73bb602009-09-14 21:25:05 +00003051 UsedParameters);
Douglas Gregor8a514912009-09-14 18:39:43 +00003052 break;
3053 }
3054
3055 case TPOC_Conversion:
Douglas Gregored9c0f92009-10-29 00:04:11 +00003056 ::MarkUsedTemplateParameters(S, Proto2->getResultType(), false,
3057 TemplateParams->getDepth(),
Douglas Gregore73bb602009-09-14 21:25:05 +00003058 UsedParameters);
Douglas Gregor8a514912009-09-14 18:39:43 +00003059 break;
3060
3061 case TPOC_Other:
Douglas Gregored9c0f92009-10-29 00:04:11 +00003062 ::MarkUsedTemplateParameters(S, FD2->getType(), false,
3063 TemplateParams->getDepth(),
3064 UsedParameters);
Douglas Gregor8a514912009-09-14 18:39:43 +00003065 break;
3066 }
3067
3068 for (; ArgIdx != NumArgs; ++ArgIdx)
3069 // If this argument had no value deduced but was used in one of the types
3070 // used for partial ordering, then deduction fails.
3071 if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
3072 return false;
3073
3074 return true;
3075}
3076
Douglas Gregor9da95e62011-01-16 16:03:23 +00003077/// \brief Determine whether this a function template whose parameter-type-list
3078/// ends with a function parameter pack.
3079static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
3080 FunctionDecl *Function = FunTmpl->getTemplatedDecl();
3081 unsigned NumParams = Function->getNumParams();
3082 if (NumParams == 0)
3083 return false;
3084
3085 ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
3086 if (!Last->isParameterPack())
3087 return false;
3088
3089 // Make sure that no previous parameter is a parameter pack.
3090 while (--NumParams > 0) {
3091 if (Function->getParamDecl(NumParams - 1)->isParameterPack())
3092 return false;
3093 }
3094
3095 return true;
3096}
Douglas Gregor8a514912009-09-14 18:39:43 +00003097
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003098/// \brief Returns the more specialized function template according
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00003099/// to the rules of function template partial ordering (C++ [temp.func.order]).
3100///
3101/// \param FT1 the first function template
3102///
3103/// \param FT2 the second function template
3104///
Douglas Gregor8a514912009-09-14 18:39:43 +00003105/// \param TPOC the context in which we are performing partial ordering of
3106/// function templates.
Mike Stump1eb44332009-09-09 15:08:12 +00003107///
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003108/// \param NumCallArguments The number of arguments in a call, used only
3109/// when \c TPOC is \c TPOC_Call.
3110///
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003111/// \returns the more specialized function template. If neither
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00003112/// template is more specialized, returns NULL.
3113FunctionTemplateDecl *
3114Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
3115 FunctionTemplateDecl *FT2,
John McCall5769d612010-02-08 23:07:23 +00003116 SourceLocation Loc,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003117 TemplatePartialOrderingContext TPOC,
3118 unsigned NumCallArguments) {
Douglas Gregor8a514912009-09-14 18:39:43 +00003119 llvm::SmallVector<DeductionQualifierComparison, 4> QualifierComparisons;
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003120 bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
3121 NumCallArguments, 0);
John McCall5769d612010-02-08 23:07:23 +00003122 bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003123 NumCallArguments,
Douglas Gregor8a514912009-09-14 18:39:43 +00003124 &QualifierComparisons);
3125
3126 if (Better1 != Better2) // We have a clear winner
3127 return Better1? FT1 : FT2;
3128
3129 if (!Better1 && !Better2) // Neither is better than the other
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00003130 return 0;
Douglas Gregor8a514912009-09-14 18:39:43 +00003131
3132
3133 // C++0x [temp.deduct.partial]p10:
3134 // If for each type being considered a given template is at least as
3135 // specialized for all types and more specialized for some set of types and
3136 // the other template is not more specialized for any types or is not at
3137 // least as specialized for any types, then the given template is more
3138 // specialized than the other template. Otherwise, neither template is more
3139 // specialized than the other.
3140 Better1 = false;
3141 Better2 = false;
3142 for (unsigned I = 0, N = QualifierComparisons.size(); I != N; ++I) {
3143 // C++0x [temp.deduct.partial]p9:
3144 // If, for a given type, deduction succeeds in both directions (i.e., the
3145 // types are identical after the transformations above) and if the type
3146 // from the argument template is more cv-qualified than the type from the
3147 // parameter template (as described above) that type is considered to be
3148 // more specialized than the other. If neither type is more cv-qualified
3149 // than the other then neither type is more specialized than the other.
3150 switch (QualifierComparisons[I]) {
3151 case NeitherMoreQualified:
3152 break;
3153
3154 case ParamMoreQualified:
3155 Better1 = true;
3156 if (Better2)
3157 return 0;
3158 break;
3159
3160 case ArgMoreQualified:
3161 Better2 = true;
3162 if (Better1)
3163 return 0;
3164 break;
3165 }
3166 }
3167
3168 assert(!(Better1 && Better2) && "Should have broken out in the loop above");
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00003169 if (Better1)
3170 return FT1;
Douglas Gregor8a514912009-09-14 18:39:43 +00003171 else if (Better2)
3172 return FT2;
Douglas Gregor9da95e62011-01-16 16:03:23 +00003173
3174 // FIXME: This mimics what GCC implements, but doesn't match up with the
3175 // proposed resolution for core issue 692. This area needs to be sorted out,
3176 // but for now we attempt to maintain compatibility.
3177 bool Variadic1 = isVariadicFunctionTemplate(FT1);
3178 bool Variadic2 = isVariadicFunctionTemplate(FT2);
3179 if (Variadic1 != Variadic2)
3180 return Variadic1? FT2 : FT1;
3181
3182 return 0;
Douglas Gregor65ec1fd2009-08-21 23:19:43 +00003183}
Douglas Gregor83314aa2009-07-08 20:55:45 +00003184
Douglas Gregord5a423b2009-09-25 18:43:00 +00003185/// \brief Determine if the two templates are equivalent.
3186static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
3187 if (T1 == T2)
3188 return true;
3189
3190 if (!T1 || !T2)
3191 return false;
3192
3193 return T1->getCanonicalDecl() == T2->getCanonicalDecl();
3194}
3195
3196/// \brief Retrieve the most specialized of the given function template
3197/// specializations.
3198///
John McCallc373d482010-01-27 01:50:18 +00003199/// \param SpecBegin the start iterator of the function template
3200/// specializations that we will be comparing.
Douglas Gregord5a423b2009-09-25 18:43:00 +00003201///
John McCallc373d482010-01-27 01:50:18 +00003202/// \param SpecEnd the end iterator of the function template
3203/// specializations, paired with \p SpecBegin.
Douglas Gregord5a423b2009-09-25 18:43:00 +00003204///
3205/// \param TPOC the partial ordering context to use to compare the function
3206/// template specializations.
3207///
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003208/// \param NumCallArguments The number of arguments in a call, used only
3209/// when \c TPOC is \c TPOC_Call.
3210///
Douglas Gregord5a423b2009-09-25 18:43:00 +00003211/// \param Loc the location where the ambiguity or no-specializations
3212/// diagnostic should occur.
3213///
3214/// \param NoneDiag partial diagnostic used to diagnose cases where there are
3215/// no matching candidates.
3216///
3217/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
3218/// occurs.
3219///
3220/// \param CandidateDiag partial diagnostic used for each function template
3221/// specialization that is a candidate in the ambiguous ordering. One parameter
3222/// in this diagnostic should be unbound, which will correspond to the string
3223/// describing the template arguments for the function template specialization.
3224///
3225/// \param Index if non-NULL and the result of this function is non-nULL,
3226/// receives the index corresponding to the resulting function template
3227/// specialization.
3228///
3229/// \returns the most specialized function template specialization, if
John McCallc373d482010-01-27 01:50:18 +00003230/// found. Otherwise, returns SpecEnd.
Douglas Gregord5a423b2009-09-25 18:43:00 +00003231///
3232/// \todo FIXME: Consider passing in the "also-ran" candidates that failed
3233/// template argument deduction.
John McCallc373d482010-01-27 01:50:18 +00003234UnresolvedSetIterator
3235Sema::getMostSpecialized(UnresolvedSetIterator SpecBegin,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003236 UnresolvedSetIterator SpecEnd,
John McCallc373d482010-01-27 01:50:18 +00003237 TemplatePartialOrderingContext TPOC,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003238 unsigned NumCallArguments,
John McCallc373d482010-01-27 01:50:18 +00003239 SourceLocation Loc,
3240 const PartialDiagnostic &NoneDiag,
3241 const PartialDiagnostic &AmbigDiag,
3242 const PartialDiagnostic &CandidateDiag) {
3243 if (SpecBegin == SpecEnd) {
Douglas Gregord5a423b2009-09-25 18:43:00 +00003244 Diag(Loc, NoneDiag);
John McCallc373d482010-01-27 01:50:18 +00003245 return SpecEnd;
Douglas Gregord5a423b2009-09-25 18:43:00 +00003246 }
3247
John McCallc373d482010-01-27 01:50:18 +00003248 if (SpecBegin + 1 == SpecEnd)
3249 return SpecBegin;
Douglas Gregord5a423b2009-09-25 18:43:00 +00003250
3251 // Find the function template that is better than all of the templates it
3252 // has been compared to.
John McCallc373d482010-01-27 01:50:18 +00003253 UnresolvedSetIterator Best = SpecBegin;
Douglas Gregord5a423b2009-09-25 18:43:00 +00003254 FunctionTemplateDecl *BestTemplate
John McCallc373d482010-01-27 01:50:18 +00003255 = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
Douglas Gregord5a423b2009-09-25 18:43:00 +00003256 assert(BestTemplate && "Not a function template specialization?");
John McCallc373d482010-01-27 01:50:18 +00003257 for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
3258 FunctionTemplateDecl *Challenger
3259 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
Douglas Gregord5a423b2009-09-25 18:43:00 +00003260 assert(Challenger && "Not a function template specialization?");
John McCallc373d482010-01-27 01:50:18 +00003261 if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003262 Loc, TPOC, NumCallArguments),
Douglas Gregord5a423b2009-09-25 18:43:00 +00003263 Challenger)) {
3264 Best = I;
3265 BestTemplate = Challenger;
3266 }
3267 }
3268
3269 // Make sure that the "best" function template is more specialized than all
3270 // of the others.
3271 bool Ambiguous = false;
John McCallc373d482010-01-27 01:50:18 +00003272 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
3273 FunctionTemplateDecl *Challenger
3274 = cast<FunctionDecl>(*I)->getPrimaryTemplate();
Douglas Gregord5a423b2009-09-25 18:43:00 +00003275 if (I != Best &&
3276 !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003277 Loc, TPOC, NumCallArguments),
Douglas Gregord5a423b2009-09-25 18:43:00 +00003278 BestTemplate)) {
3279 Ambiguous = true;
3280 break;
3281 }
3282 }
3283
3284 if (!Ambiguous) {
3285 // We found an answer. Return it.
John McCallc373d482010-01-27 01:50:18 +00003286 return Best;
Douglas Gregord5a423b2009-09-25 18:43:00 +00003287 }
3288
3289 // Diagnose the ambiguity.
3290 Diag(Loc, AmbigDiag);
3291
3292 // FIXME: Can we order the candidates in some sane way?
John McCallc373d482010-01-27 01:50:18 +00003293 for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I)
3294 Diag((*I)->getLocation(), CandidateDiag)
Douglas Gregord5a423b2009-09-25 18:43:00 +00003295 << getTemplateArgumentBindingsText(
John McCallc373d482010-01-27 01:50:18 +00003296 cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
3297 *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
Douglas Gregord5a423b2009-09-25 18:43:00 +00003298
John McCallc373d482010-01-27 01:50:18 +00003299 return SpecEnd;
Douglas Gregord5a423b2009-09-25 18:43:00 +00003300}
3301
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003302/// \brief Returns the more specialized class template partial specialization
3303/// according to the rules of partial ordering of class template partial
3304/// specializations (C++ [temp.class.order]).
3305///
3306/// \param PS1 the first class template partial specialization
3307///
3308/// \param PS2 the second class template partial specialization
3309///
3310/// \returns the more specialized class template partial specialization. If
3311/// neither partial specialization is more specialized, returns NULL.
3312ClassTemplatePartialSpecializationDecl *
3313Sema::getMoreSpecializedPartialSpecialization(
3314 ClassTemplatePartialSpecializationDecl *PS1,
John McCall5769d612010-02-08 23:07:23 +00003315 ClassTemplatePartialSpecializationDecl *PS2,
3316 SourceLocation Loc) {
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003317 // C++ [temp.class.order]p1:
3318 // For two class template partial specializations, the first is at least as
3319 // specialized as the second if, given the following rewrite to two
3320 // function templates, the first function template is at least as
3321 // specialized as the second according to the ordering rules for function
3322 // templates (14.6.6.2):
3323 // - the first function template has the same template parameters as the
3324 // first partial specialization and has a single function parameter
3325 // whose type is a class template specialization with the template
3326 // arguments of the first partial specialization, and
3327 // - the second function template has the same template parameters as the
3328 // second partial specialization and has a single function parameter
3329 // whose type is a class template specialization with the template
3330 // arguments of the second partial specialization.
3331 //
Douglas Gregor31dce8f2010-04-29 06:21:43 +00003332 // Rather than synthesize function templates, we merely perform the
3333 // equivalent partial ordering by performing deduction directly on
3334 // the template arguments of the class template partial
3335 // specializations. This computation is slightly simpler than the
3336 // general problem of function template partial ordering, because
3337 // class template partial specializations are more constrained. We
3338 // know that every template parameter is deducible from the class
3339 // template partial specialization's template arguments, for
3340 // example.
Douglas Gregor02024a92010-03-28 02:42:43 +00003341 llvm::SmallVector<DeducedTemplateArgument, 4> Deduced;
John McCall2a7fb272010-08-25 05:32:35 +00003342 TemplateDeductionInfo Info(Context, Loc);
John McCall31f17ec2010-04-27 00:57:59 +00003343
3344 QualType PT1 = PS1->getInjectedSpecializationType();
3345 QualType PT2 = PS2->getInjectedSpecializationType();
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003346
3347 // Determine whether PS1 is at least as specialized as PS2
3348 Deduced.resize(PS2->getTemplateParameters()->size());
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003349 bool Better1 = !::DeduceTemplateArguments(*this, PS2->getTemplateParameters(),
3350 PT2, PT1, Info, Deduced, TDF_None,
3351 /*PartialOrdering=*/true,
3352 /*QualifierComparisons=*/0);
Argyrios Kyrtzidis2c4792c2010-11-05 23:25:18 +00003353 if (Better1) {
3354 InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2,
3355 Deduced.data(), Deduced.size(), Info);
Douglas Gregor516e6e02010-04-29 06:31:36 +00003356 Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
3357 PS1->getTemplateArgs(),
3358 Deduced, Info);
Argyrios Kyrtzidis2c4792c2010-11-05 23:25:18 +00003359 }
Douglas Gregor516e6e02010-04-29 06:31:36 +00003360
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003361 // Determine whether PS2 is at least as specialized as PS1
Douglas Gregordb0d4b72009-11-11 23:06:43 +00003362 Deduced.clear();
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003363 Deduced.resize(PS1->getTemplateParameters()->size());
Douglas Gregor5c7bf422011-01-11 17:34:58 +00003364 bool Better2 = !::DeduceTemplateArguments(*this, PS1->getTemplateParameters(),
3365 PT1, PT2, Info, Deduced, TDF_None,
3366 /*PartialOrdering=*/true,
3367 /*QualifierComparisons=*/0);
Argyrios Kyrtzidis2c4792c2010-11-05 23:25:18 +00003368 if (Better2) {
3369 InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1,
3370 Deduced.data(), Deduced.size(), Info);
Douglas Gregor516e6e02010-04-29 06:31:36 +00003371 Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
3372 PS2->getTemplateArgs(),
3373 Deduced, Info);
Argyrios Kyrtzidis2c4792c2010-11-05 23:25:18 +00003374 }
Douglas Gregorbf4ea562009-09-15 16:23:51 +00003375
3376 if (Better1 == Better2)
3377 return 0;
3378
3379 return Better1? PS1 : PS2;
3380}
3381
Mike Stump1eb44332009-09-09 15:08:12 +00003382static void
Douglas Gregore73bb602009-09-14 21:25:05 +00003383MarkUsedTemplateParameters(Sema &SemaRef,
3384 const TemplateArgument &TemplateArg,
3385 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003386 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003387 llvm::SmallVectorImpl<bool> &Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003388
Douglas Gregore73bb602009-09-14 21:25:05 +00003389/// \brief Mark the template parameters that are used by the given
Douglas Gregor031a5882009-06-13 00:26:55 +00003390/// expression.
Mike Stump1eb44332009-09-09 15:08:12 +00003391static void
Douglas Gregore73bb602009-09-14 21:25:05 +00003392MarkUsedTemplateParameters(Sema &SemaRef,
3393 const Expr *E,
3394 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003395 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003396 llvm::SmallVectorImpl<bool> &Used) {
Douglas Gregorbe230c32011-01-03 17:17:50 +00003397 // We can deduce from a pack expansion.
3398 if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
3399 E = Expansion->getPattern();
3400
Douglas Gregor54c53cc2011-01-04 23:35:54 +00003401 // Skip through any implicit casts we added while type-checking.
3402 while (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
3403 E = ICE->getSubExpr();
3404
Douglas Gregore73bb602009-09-14 21:25:05 +00003405 // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
3406 // find other occurrences of template parameters.
Douglas Gregorf6ddb732009-06-18 18:45:36 +00003407 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
Douglas Gregorc781f9c2010-01-14 18:13:22 +00003408 if (!DRE)
Douglas Gregor031a5882009-06-13 00:26:55 +00003409 return;
3410
Mike Stump1eb44332009-09-09 15:08:12 +00003411 const NonTypeTemplateParmDecl *NTTP
Douglas Gregor031a5882009-06-13 00:26:55 +00003412 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
3413 if (!NTTP)
3414 return;
3415
Douglas Gregored9c0f92009-10-29 00:04:11 +00003416 if (NTTP->getDepth() == Depth)
3417 Used[NTTP->getIndex()] = true;
Douglas Gregor031a5882009-06-13 00:26:55 +00003418}
3419
Douglas Gregore73bb602009-09-14 21:25:05 +00003420/// \brief Mark the template parameters that are used by the given
3421/// nested name specifier.
3422static void
3423MarkUsedTemplateParameters(Sema &SemaRef,
3424 NestedNameSpecifier *NNS,
3425 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003426 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003427 llvm::SmallVectorImpl<bool> &Used) {
3428 if (!NNS)
3429 return;
3430
Douglas Gregored9c0f92009-10-29 00:04:11 +00003431 MarkUsedTemplateParameters(SemaRef, NNS->getPrefix(), OnlyDeduced, Depth,
3432 Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003433 MarkUsedTemplateParameters(SemaRef, QualType(NNS->getAsType(), 0),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003434 OnlyDeduced, Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003435}
3436
3437/// \brief Mark the template parameters that are used by the given
3438/// template name.
3439static void
3440MarkUsedTemplateParameters(Sema &SemaRef,
3441 TemplateName Name,
3442 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003443 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003444 llvm::SmallVectorImpl<bool> &Used) {
3445 if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
3446 if (TemplateTemplateParmDecl *TTP
Douglas Gregored9c0f92009-10-29 00:04:11 +00003447 = dyn_cast<TemplateTemplateParmDecl>(Template)) {
3448 if (TTP->getDepth() == Depth)
3449 Used[TTP->getIndex()] = true;
3450 }
Douglas Gregore73bb602009-09-14 21:25:05 +00003451 return;
3452 }
3453
Douglas Gregor788cd062009-11-11 01:00:40 +00003454 if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
3455 MarkUsedTemplateParameters(SemaRef, QTN->getQualifier(), OnlyDeduced,
3456 Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003457 if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
Douglas Gregored9c0f92009-10-29 00:04:11 +00003458 MarkUsedTemplateParameters(SemaRef, DTN->getQualifier(), OnlyDeduced,
3459 Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003460}
3461
3462/// \brief Mark the template parameters that are used by the given
Douglas Gregor031a5882009-06-13 00:26:55 +00003463/// type.
Mike Stump1eb44332009-09-09 15:08:12 +00003464static void
Douglas Gregore73bb602009-09-14 21:25:05 +00003465MarkUsedTemplateParameters(Sema &SemaRef, QualType T,
3466 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003467 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003468 llvm::SmallVectorImpl<bool> &Used) {
3469 if (T.isNull())
3470 return;
3471
Douglas Gregor031a5882009-06-13 00:26:55 +00003472 // Non-dependent types have nothing deducible
3473 if (!T->isDependentType())
3474 return;
3475
3476 T = SemaRef.Context.getCanonicalType(T);
3477 switch (T->getTypeClass()) {
Douglas Gregor031a5882009-06-13 00:26:55 +00003478 case Type::Pointer:
Douglas Gregore73bb602009-09-14 21:25:05 +00003479 MarkUsedTemplateParameters(SemaRef,
3480 cast<PointerType>(T)->getPointeeType(),
3481 OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003482 Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003483 Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003484 break;
3485
3486 case Type::BlockPointer:
Douglas Gregore73bb602009-09-14 21:25:05 +00003487 MarkUsedTemplateParameters(SemaRef,
3488 cast<BlockPointerType>(T)->getPointeeType(),
3489 OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003490 Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003491 Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003492 break;
3493
3494 case Type::LValueReference:
3495 case Type::RValueReference:
Douglas Gregore73bb602009-09-14 21:25:05 +00003496 MarkUsedTemplateParameters(SemaRef,
3497 cast<ReferenceType>(T)->getPointeeType(),
3498 OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003499 Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003500 Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003501 break;
3502
3503 case Type::MemberPointer: {
3504 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
Douglas Gregore73bb602009-09-14 21:25:05 +00003505 MarkUsedTemplateParameters(SemaRef, MemPtr->getPointeeType(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003506 Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003507 MarkUsedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003508 OnlyDeduced, Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003509 break;
3510 }
3511
3512 case Type::DependentSizedArray:
Douglas Gregore73bb602009-09-14 21:25:05 +00003513 MarkUsedTemplateParameters(SemaRef,
3514 cast<DependentSizedArrayType>(T)->getSizeExpr(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003515 OnlyDeduced, Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003516 // Fall through to check the element type
3517
3518 case Type::ConstantArray:
3519 case Type::IncompleteArray:
Douglas Gregore73bb602009-09-14 21:25:05 +00003520 MarkUsedTemplateParameters(SemaRef,
3521 cast<ArrayType>(T)->getElementType(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003522 OnlyDeduced, Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003523 break;
3524
3525 case Type::Vector:
3526 case Type::ExtVector:
Douglas Gregore73bb602009-09-14 21:25:05 +00003527 MarkUsedTemplateParameters(SemaRef,
3528 cast<VectorType>(T)->getElementType(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003529 OnlyDeduced, Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003530 break;
3531
Douglas Gregor9cdda0c2009-06-17 21:51:59 +00003532 case Type::DependentSizedExtVector: {
3533 const DependentSizedExtVectorType *VecType
Douglas Gregorf6ddb732009-06-18 18:45:36 +00003534 = cast<DependentSizedExtVectorType>(T);
Douglas Gregore73bb602009-09-14 21:25:05 +00003535 MarkUsedTemplateParameters(SemaRef, VecType->getElementType(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003536 Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003537 MarkUsedTemplateParameters(SemaRef, VecType->getSizeExpr(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003538 Depth, Used);
Douglas Gregor9cdda0c2009-06-17 21:51:59 +00003539 break;
3540 }
3541
Douglas Gregor031a5882009-06-13 00:26:55 +00003542 case Type::FunctionProto: {
Douglas Gregorf6ddb732009-06-18 18:45:36 +00003543 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
Douglas Gregore73bb602009-09-14 21:25:05 +00003544 MarkUsedTemplateParameters(SemaRef, Proto->getResultType(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003545 Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003546 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
Douglas Gregore73bb602009-09-14 21:25:05 +00003547 MarkUsedTemplateParameters(SemaRef, Proto->getArgType(I), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003548 Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003549 break;
3550 }
3551
Douglas Gregored9c0f92009-10-29 00:04:11 +00003552 case Type::TemplateTypeParm: {
3553 const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
3554 if (TTP->getDepth() == Depth)
3555 Used[TTP->getIndex()] = true;
Douglas Gregor031a5882009-06-13 00:26:55 +00003556 break;
Douglas Gregored9c0f92009-10-29 00:04:11 +00003557 }
Douglas Gregor031a5882009-06-13 00:26:55 +00003558
Douglas Gregor0bc15d92011-01-14 05:11:40 +00003559 case Type::SubstTemplateTypeParmPack: {
3560 const SubstTemplateTypeParmPackType *Subst
3561 = cast<SubstTemplateTypeParmPackType>(T);
3562 MarkUsedTemplateParameters(SemaRef,
3563 QualType(Subst->getReplacedParameter(), 0),
3564 OnlyDeduced, Depth, Used);
3565 MarkUsedTemplateParameters(SemaRef, Subst->getArgumentPack(),
3566 OnlyDeduced, Depth, Used);
3567 break;
3568 }
3569
John McCall31f17ec2010-04-27 00:57:59 +00003570 case Type::InjectedClassName:
3571 T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
3572 // fall through
3573
Douglas Gregor031a5882009-06-13 00:26:55 +00003574 case Type::TemplateSpecialization: {
Mike Stump1eb44332009-09-09 15:08:12 +00003575 const TemplateSpecializationType *Spec
Douglas Gregorf6ddb732009-06-18 18:45:36 +00003576 = cast<TemplateSpecializationType>(T);
Douglas Gregore73bb602009-09-14 21:25:05 +00003577 MarkUsedTemplateParameters(SemaRef, Spec->getTemplateName(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003578 Depth, Used);
Douglas Gregor7b976ec2010-12-23 01:24:45 +00003579
3580 // C++0x [temp.deduct.type]p9:
3581 // If the template argument list of P contains a pack expansion that is not
3582 // the last template argument, the entire template argument list is a
3583 // non-deduced context.
3584 if (OnlyDeduced &&
3585 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
3586 break;
3587
Douglas Gregore73bb602009-09-14 21:25:05 +00003588 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
Douglas Gregored9c0f92009-10-29 00:04:11 +00003589 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
3590 Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003591 break;
3592 }
3593
Douglas Gregore73bb602009-09-14 21:25:05 +00003594 case Type::Complex:
3595 if (!OnlyDeduced)
3596 MarkUsedTemplateParameters(SemaRef,
3597 cast<ComplexType>(T)->getElementType(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003598 OnlyDeduced, Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003599 break;
3600
Douglas Gregor4714c122010-03-31 17:34:00 +00003601 case Type::DependentName:
Douglas Gregore73bb602009-09-14 21:25:05 +00003602 if (!OnlyDeduced)
3603 MarkUsedTemplateParameters(SemaRef,
Douglas Gregor4714c122010-03-31 17:34:00 +00003604 cast<DependentNameType>(T)->getQualifier(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003605 OnlyDeduced, Depth, Used);
Douglas Gregore73bb602009-09-14 21:25:05 +00003606 break;
3607
John McCall33500952010-06-11 00:33:02 +00003608 case Type::DependentTemplateSpecialization: {
3609 const DependentTemplateSpecializationType *Spec
3610 = cast<DependentTemplateSpecializationType>(T);
3611 if (!OnlyDeduced)
3612 MarkUsedTemplateParameters(SemaRef, Spec->getQualifier(),
3613 OnlyDeduced, Depth, Used);
Douglas Gregor7b976ec2010-12-23 01:24:45 +00003614
3615 // C++0x [temp.deduct.type]p9:
3616 // If the template argument list of P contains a pack expansion that is not
3617 // the last template argument, the entire template argument list is a
3618 // non-deduced context.
3619 if (OnlyDeduced &&
3620 hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
3621 break;
3622
John McCall33500952010-06-11 00:33:02 +00003623 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
3624 MarkUsedTemplateParameters(SemaRef, Spec->getArg(I), OnlyDeduced, Depth,
3625 Used);
3626 break;
3627 }
3628
John McCallad5e7382010-03-01 23:49:17 +00003629 case Type::TypeOf:
3630 if (!OnlyDeduced)
3631 MarkUsedTemplateParameters(SemaRef,
3632 cast<TypeOfType>(T)->getUnderlyingType(),
3633 OnlyDeduced, Depth, Used);
3634 break;
3635
3636 case Type::TypeOfExpr:
3637 if (!OnlyDeduced)
3638 MarkUsedTemplateParameters(SemaRef,
3639 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
3640 OnlyDeduced, Depth, Used);
3641 break;
3642
3643 case Type::Decltype:
3644 if (!OnlyDeduced)
3645 MarkUsedTemplateParameters(SemaRef,
3646 cast<DecltypeType>(T)->getUnderlyingExpr(),
3647 OnlyDeduced, Depth, Used);
3648 break;
3649
Douglas Gregor7536dd52010-12-20 02:24:11 +00003650 case Type::PackExpansion:
3651 MarkUsedTemplateParameters(SemaRef,
3652 cast<PackExpansionType>(T)->getPattern(),
3653 OnlyDeduced, Depth, Used);
3654 break;
3655
Douglas Gregore73bb602009-09-14 21:25:05 +00003656 // None of these types have any template parameters in them.
Douglas Gregor031a5882009-06-13 00:26:55 +00003657 case Type::Builtin:
Douglas Gregor031a5882009-06-13 00:26:55 +00003658 case Type::VariableArray:
3659 case Type::FunctionNoProto:
3660 case Type::Record:
3661 case Type::Enum:
Douglas Gregor031a5882009-06-13 00:26:55 +00003662 case Type::ObjCInterface:
John McCallc12c5bb2010-05-15 11:32:37 +00003663 case Type::ObjCObject:
Steve Naroffd1b3c2d2009-06-17 22:40:22 +00003664 case Type::ObjCObjectPointer:
John McCalled976492009-12-04 22:46:56 +00003665 case Type::UnresolvedUsing:
Douglas Gregor031a5882009-06-13 00:26:55 +00003666#define TYPE(Class, Base)
3667#define ABSTRACT_TYPE(Class, Base)
3668#define DEPENDENT_TYPE(Class, Base)
3669#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
3670#include "clang/AST/TypeNodes.def"
3671 break;
3672 }
3673}
3674
Douglas Gregore73bb602009-09-14 21:25:05 +00003675/// \brief Mark the template parameters that are used by this
Douglas Gregor031a5882009-06-13 00:26:55 +00003676/// template argument.
Mike Stump1eb44332009-09-09 15:08:12 +00003677static void
Douglas Gregore73bb602009-09-14 21:25:05 +00003678MarkUsedTemplateParameters(Sema &SemaRef,
3679 const TemplateArgument &TemplateArg,
3680 bool OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003681 unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003682 llvm::SmallVectorImpl<bool> &Used) {
Douglas Gregor031a5882009-06-13 00:26:55 +00003683 switch (TemplateArg.getKind()) {
3684 case TemplateArgument::Null:
3685 case TemplateArgument::Integral:
Douglas Gregor788cd062009-11-11 01:00:40 +00003686 case TemplateArgument::Declaration:
Douglas Gregor031a5882009-06-13 00:26:55 +00003687 break;
Mike Stump1eb44332009-09-09 15:08:12 +00003688
Douglas Gregor031a5882009-06-13 00:26:55 +00003689 case TemplateArgument::Type:
Douglas Gregore73bb602009-09-14 21:25:05 +00003690 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsType(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003691 Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003692 break;
3693
Douglas Gregor788cd062009-11-11 01:00:40 +00003694 case TemplateArgument::Template:
Douglas Gregora7fc9012011-01-05 18:58:31 +00003695 case TemplateArgument::TemplateExpansion:
3696 MarkUsedTemplateParameters(SemaRef,
3697 TemplateArg.getAsTemplateOrTemplatePattern(),
Douglas Gregor788cd062009-11-11 01:00:40 +00003698 OnlyDeduced, Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003699 break;
3700
3701 case TemplateArgument::Expression:
Douglas Gregore73bb602009-09-14 21:25:05 +00003702 MarkUsedTemplateParameters(SemaRef, TemplateArg.getAsExpr(), OnlyDeduced,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003703 Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003704 break;
Douglas Gregore73bb602009-09-14 21:25:05 +00003705
Anders Carlssond01b1da2009-06-15 17:04:53 +00003706 case TemplateArgument::Pack:
Douglas Gregore73bb602009-09-14 21:25:05 +00003707 for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(),
3708 PEnd = TemplateArg.pack_end();
3709 P != PEnd; ++P)
Douglas Gregored9c0f92009-10-29 00:04:11 +00003710 MarkUsedTemplateParameters(SemaRef, *P, OnlyDeduced, Depth, Used);
Anders Carlssond01b1da2009-06-15 17:04:53 +00003711 break;
Douglas Gregor031a5882009-06-13 00:26:55 +00003712 }
3713}
3714
3715/// \brief Mark the template parameters can be deduced by the given
3716/// template argument list.
3717///
3718/// \param TemplateArgs the template argument list from which template
3719/// parameters will be deduced.
3720///
3721/// \param Deduced a bit vector whose elements will be set to \c true
3722/// to indicate when the corresponding template parameter will be
3723/// deduced.
Mike Stump1eb44332009-09-09 15:08:12 +00003724void
Douglas Gregore73bb602009-09-14 21:25:05 +00003725Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
Douglas Gregored9c0f92009-10-29 00:04:11 +00003726 bool OnlyDeduced, unsigned Depth,
Douglas Gregore73bb602009-09-14 21:25:05 +00003727 llvm::SmallVectorImpl<bool> &Used) {
Douglas Gregor7b976ec2010-12-23 01:24:45 +00003728 // C++0x [temp.deduct.type]p9:
3729 // If the template argument list of P contains a pack expansion that is not
3730 // the last template argument, the entire template argument list is a
3731 // non-deduced context.
3732 if (OnlyDeduced &&
3733 hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
3734 return;
3735
Douglas Gregor031a5882009-06-13 00:26:55 +00003736 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
Douglas Gregored9c0f92009-10-29 00:04:11 +00003737 ::MarkUsedTemplateParameters(*this, TemplateArgs[I], OnlyDeduced,
3738 Depth, Used);
Douglas Gregor031a5882009-06-13 00:26:55 +00003739}
Douglas Gregor63f07c52009-09-18 23:21:38 +00003740
3741/// \brief Marks all of the template parameters that will be deduced by a
3742/// call to the given function template.
Douglas Gregor02024a92010-03-28 02:42:43 +00003743void
3744Sema::MarkDeducedTemplateParameters(FunctionTemplateDecl *FunctionTemplate,
3745 llvm::SmallVectorImpl<bool> &Deduced) {
Douglas Gregor63f07c52009-09-18 23:21:38 +00003746 TemplateParameterList *TemplateParams
3747 = FunctionTemplate->getTemplateParameters();
3748 Deduced.clear();
3749 Deduced.resize(TemplateParams->size());
3750
3751 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3752 for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
3753 ::MarkUsedTemplateParameters(*this, Function->getParamDecl(I)->getType(),
Douglas Gregored9c0f92009-10-29 00:04:11 +00003754 true, TemplateParams->getDepth(), Deduced);
Douglas Gregor63f07c52009-09-18 23:21:38 +00003755}