blob: 3d909bb26a79d6ac3cbc2e411811e85a0d1c3812 [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
13#include "Sema.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/DeclTemplate.h"
16#include "clang/AST/StmtVisitor.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/ExprCXX.h"
19#include "clang/Parse/DeclSpec.h"
20#include "llvm/Support/Compiler.h"
Douglas Gregor508f1c82009-06-26 23:10:12 +000021
22namespace clang {
23 /// \brief Various flags that control template argument deduction.
24 ///
25 /// These flags can be bitwise-OR'd together.
26 enum TemplateDeductionFlags {
27 /// \brief No template argument deduction flags, which indicates the
28 /// strictest results for template argument deduction (as used for, e.g.,
29 /// matching class template partial specializations).
30 TDF_None = 0,
31 /// \brief Within template argument deduction from a function call, we are
32 /// matching with a parameter type for which the original parameter was
33 /// a reference.
34 TDF_ParamWithReferenceType = 0x1,
35 /// \brief Within template argument deduction from a function call, we
36 /// are matching in a case where we ignore cv-qualifiers.
37 TDF_IgnoreQualifiers = 0x02,
38 /// \brief Within template argument deduction from a function call,
39 /// we are matching in a case where we can perform template argument
Douglas Gregor41128772009-06-26 23:27:24 +000040 /// deduction from a template-id of a derived class of the argument type.
Douglas Gregor508f1c82009-06-26 23:10:12 +000041 TDF_DerivedClass = 0x04
42 };
43}
44
Douglas Gregor0b9247f2009-06-04 00:03:07 +000045using namespace clang;
46
Douglas Gregorf67875d2009-06-12 18:26:56 +000047static Sema::TemplateDeductionResult
48DeduceTemplateArguments(ASTContext &Context,
49 TemplateParameterList *TemplateParams,
50 const TemplateArgument &Param,
Douglas Gregord708c722009-06-09 16:35:58 +000051 const TemplateArgument &Arg,
Douglas Gregorf67875d2009-06-12 18:26:56 +000052 Sema::TemplateDeductionInfo &Info,
Douglas Gregord708c722009-06-09 16:35:58 +000053 llvm::SmallVectorImpl<TemplateArgument> &Deduced);
54
Douglas Gregor199d9912009-06-05 00:53:49 +000055/// \brief If the given expression is of a form that permits the deduction
56/// of a non-type template parameter, return the declaration of that
57/// non-type template parameter.
58static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
59 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
60 E = IC->getSubExpr();
61
62 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
63 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
64
65 return 0;
66}
67
68/// \brief Deduce the value of the given non-type template parameter
69/// from the given constant.
Douglas Gregorf67875d2009-06-12 18:26:56 +000070static Sema::TemplateDeductionResult
71DeduceNonTypeTemplateArgument(ASTContext &Context,
72 NonTypeTemplateParmDecl *NTTP,
Anders Carlsson335e24a2009-06-16 22:44:31 +000073 llvm::APSInt Value,
Douglas Gregorf67875d2009-06-12 18:26:56 +000074 Sema::TemplateDeductionInfo &Info,
75 llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
Douglas Gregor199d9912009-06-05 00:53:49 +000076 assert(NTTP->getDepth() == 0 &&
77 "Cannot deduce non-type template argument with depth > 0");
78
79 if (Deduced[NTTP->getIndex()].isNull()) {
Anders Carlsson25af1ed2009-06-16 23:08:29 +000080 QualType T = NTTP->getType();
81
82 // FIXME: Make sure we didn't overflow our data type!
83 unsigned AllowedBits = Context.getTypeSize(T);
84 if (Value.getBitWidth() != AllowedBits)
85 Value.extOrTrunc(AllowedBits);
86 Value.setIsSigned(T->isSignedIntegerType());
87
88 Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(), Value, T);
Douglas Gregorf67875d2009-06-12 18:26:56 +000089 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +000090 }
91
Douglas Gregorf67875d2009-06-12 18:26:56 +000092 assert(Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral);
Douglas Gregor199d9912009-06-05 00:53:49 +000093
94 // If the template argument was previously deduced to a negative value,
95 // then our deduction fails.
96 const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral();
Anders Carlsson335e24a2009-06-16 22:44:31 +000097 if (PrevValuePtr->isNegative()) {
Douglas Gregorf67875d2009-06-12 18:26:56 +000098 Info.Param = NTTP;
99 Info.FirstArg = Deduced[NTTP->getIndex()];
Anders Carlsson335e24a2009-06-16 22:44:31 +0000100 Info.SecondArg = TemplateArgument(SourceLocation(), Value, NTTP->getType());
Douglas Gregorf67875d2009-06-12 18:26:56 +0000101 return Sema::TDK_Inconsistent;
102 }
103
Anders Carlsson335e24a2009-06-16 22:44:31 +0000104 llvm::APSInt PrevValue = *PrevValuePtr;
Douglas Gregor199d9912009-06-05 00:53:49 +0000105 if (Value.getBitWidth() > PrevValue.getBitWidth())
106 PrevValue.zext(Value.getBitWidth());
107 else if (Value.getBitWidth() < PrevValue.getBitWidth())
108 Value.zext(PrevValue.getBitWidth());
Douglas Gregorf67875d2009-06-12 18:26:56 +0000109
110 if (Value != PrevValue) {
111 Info.Param = NTTP;
112 Info.FirstArg = Deduced[NTTP->getIndex()];
Anders Carlsson335e24a2009-06-16 22:44:31 +0000113 Info.SecondArg = TemplateArgument(SourceLocation(), Value, NTTP->getType());
Douglas Gregorf67875d2009-06-12 18:26:56 +0000114 return Sema::TDK_Inconsistent;
115 }
116
117 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000118}
119
120/// \brief Deduce the value of the given non-type template parameter
121/// from the given type- or value-dependent expression.
122///
123/// \returns true if deduction succeeded, false otherwise.
124
Douglas Gregorf67875d2009-06-12 18:26:56 +0000125static Sema::TemplateDeductionResult
126DeduceNonTypeTemplateArgument(ASTContext &Context,
127 NonTypeTemplateParmDecl *NTTP,
128 Expr *Value,
129 Sema::TemplateDeductionInfo &Info,
130 llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
Douglas Gregor199d9912009-06-05 00:53:49 +0000131 assert(NTTP->getDepth() == 0 &&
132 "Cannot deduce non-type template argument with depth > 0");
133 assert((Value->isTypeDependent() || Value->isValueDependent()) &&
134 "Expression template argument must be type- or value-dependent.");
135
136 if (Deduced[NTTP->getIndex()].isNull()) {
137 // FIXME: Clone the Value?
138 Deduced[NTTP->getIndex()] = TemplateArgument(Value);
Douglas Gregorf67875d2009-06-12 18:26:56 +0000139 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000140 }
141
142 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) {
143 // Okay, we deduced a constant in one case and a dependent expression
144 // in another case. FIXME: Later, we will check that instantiating the
145 // dependent expression gives us the constant value.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000146 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000147 }
148
149 // FIXME: Compare the expressions for equality!
Douglas Gregorf67875d2009-06-12 18:26:56 +0000150 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000151}
152
Douglas Gregorf67875d2009-06-12 18:26:56 +0000153static Sema::TemplateDeductionResult
154DeduceTemplateArguments(ASTContext &Context,
155 TemplateName Param,
156 TemplateName Arg,
157 Sema::TemplateDeductionInfo &Info,
158 llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
Douglas Gregord708c722009-06-09 16:35:58 +0000159 // FIXME: Implement template argument deduction for template
160 // template parameters.
161
Douglas Gregorf67875d2009-06-12 18:26:56 +0000162 // FIXME: this routine does not have enough information to produce
163 // good diagnostics.
164
Douglas Gregord708c722009-06-09 16:35:58 +0000165 TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
166 TemplateDecl *ArgDecl = Arg.getAsTemplateDecl();
167
Douglas Gregorf67875d2009-06-12 18:26:56 +0000168 if (!ParamDecl || !ArgDecl) {
169 // FIXME: fill in Info.Param/Info.FirstArg
170 return Sema::TDK_Inconsistent;
171 }
Douglas Gregord708c722009-06-09 16:35:58 +0000172
173 ParamDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ParamDecl));
174 ArgDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ArgDecl));
Douglas Gregorf67875d2009-06-12 18:26:56 +0000175 if (ParamDecl != ArgDecl) {
176 // FIXME: fill in Info.Param/Info.FirstArg
177 return Sema::TDK_Inconsistent;
178 }
179
180 return Sema::TDK_Success;
Douglas Gregord708c722009-06-09 16:35:58 +0000181}
182
Douglas Gregor500d3312009-06-26 18:27:22 +0000183/// \brief Deduce the template arguments by comparing the parameter type and
184/// the argument type (C++ [temp.deduct.type]).
185///
186/// \param Context the AST context in which this deduction occurs.
187///
188/// \param TemplateParams the template parameters that we are deducing
189///
190/// \param ParamIn the parameter type
191///
192/// \param ArgIn the argument type
193///
194/// \param Info information about the template argument deduction itself
195///
196/// \param Deduced the deduced template arguments
197///
Douglas Gregor508f1c82009-06-26 23:10:12 +0000198/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
199/// how template argument deduction is performed.
Douglas Gregor500d3312009-06-26 18:27:22 +0000200///
201/// \returns the result of template argument deduction so far. Note that a
202/// "success" result means that template argument deduction has not yet failed,
203/// but it may still fail, later, for other reasons.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000204static Sema::TemplateDeductionResult
205DeduceTemplateArguments(ASTContext &Context,
206 TemplateParameterList *TemplateParams,
207 QualType ParamIn, QualType ArgIn,
208 Sema::TemplateDeductionInfo &Info,
Douglas Gregor500d3312009-06-26 18:27:22 +0000209 llvm::SmallVectorImpl<TemplateArgument> &Deduced,
Douglas Gregor508f1c82009-06-26 23:10:12 +0000210 unsigned TDF) {
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000211 // We only want to look at the canonical types, since typedefs and
212 // sugar are not part of template argument deduction.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000213 QualType Param = Context.getCanonicalType(ParamIn);
214 QualType Arg = Context.getCanonicalType(ArgIn);
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000215
Douglas Gregor500d3312009-06-26 18:27:22 +0000216 // C++0x [temp.deduct.call]p4 bullet 1:
217 // - If the original P is a reference type, the deduced A (i.e., the type
218 // referred to by the reference) can be more cv-qualified than the
219 // transformed A.
Douglas Gregor508f1c82009-06-26 23:10:12 +0000220 if (TDF & TDF_ParamWithReferenceType) {
Douglas Gregor500d3312009-06-26 18:27:22 +0000221 unsigned ExtraQualsOnParam
222 = Param.getCVRQualifiers() & ~Arg.getCVRQualifiers();
223 Param.setCVRQualifiers(Param.getCVRQualifiers() & ~ExtraQualsOnParam);
224 }
225
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000226 // If the parameter type is not dependent, there is nothing to deduce.
227 if (!Param->isDependentType())
228 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000229
Douglas Gregor199d9912009-06-05 00:53:49 +0000230 // C++ [temp.deduct.type]p9:
Douglas Gregor199d9912009-06-05 00:53:49 +0000231 // A template type argument T, a template template argument TT or a
232 // template non-type argument i can be deduced if P and A have one of
233 // the following forms:
234 //
235 // T
236 // cv-list T
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000237 if (const TemplateTypeParmType *TemplateTypeParm
238 = Param->getAsTemplateTypeParmType()) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000239 unsigned Index = TemplateTypeParm->getIndex();
240
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000241 // The argument type can not be less qualified than the parameter
242 // type.
Douglas Gregor508f1c82009-06-26 23:10:12 +0000243 if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000244 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
245 Info.FirstArg = Deduced[Index];
246 Info.SecondArg = TemplateArgument(SourceLocation(), Arg);
247 return Sema::TDK_InconsistentQuals;
248 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000249
250 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
251
252 unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers();
253 QualType DeducedType = Arg.getQualifiedType(Quals);
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000254
255 if (Deduced[Index].isNull())
256 Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType);
257 else {
258 // C++ [temp.deduct.type]p2:
259 // [...] If type deduction cannot be done for any P/A pair, or if for
260 // any pair the deduction leads to more than one possible set of
261 // deduced values, or if different pairs yield different deduced
262 // values, or if any template argument remains neither deduced nor
263 // explicitly specified, template argument deduction fails.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000264 if (Deduced[Index].getAsType() != DeducedType) {
265 Info.Param
266 = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
267 Info.FirstArg = Deduced[Index];
268 Info.SecondArg = TemplateArgument(SourceLocation(), Arg);
269 return Sema::TDK_Inconsistent;
270 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000271 }
Douglas Gregorf67875d2009-06-12 18:26:56 +0000272 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000273 }
274
Douglas Gregorf67875d2009-06-12 18:26:56 +0000275 // Set up the template argument deduction information for a failure.
276 Info.FirstArg = TemplateArgument(SourceLocation(), ParamIn);
277 Info.SecondArg = TemplateArgument(SourceLocation(), ArgIn);
278
Douglas Gregor508f1c82009-06-26 23:10:12 +0000279 // Check the cv-qualifiers on the parameter and argument types.
280 if (!(TDF & TDF_IgnoreQualifiers)) {
281 if (TDF & TDF_ParamWithReferenceType) {
282 if (Param.isMoreQualifiedThan(Arg))
283 return Sema::TDK_NonDeducedMismatch;
284 } else {
285 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
286 return Sema::TDK_NonDeducedMismatch;
287 }
288 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000289
Douglas Gregord560d502009-06-04 00:21:18 +0000290 switch (Param->getTypeClass()) {
Douglas Gregor199d9912009-06-05 00:53:49 +0000291 // No deduction possible for these types
292 case Type::Builtin:
Douglas Gregorf67875d2009-06-12 18:26:56 +0000293 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000294
295 // T *
Douglas Gregord560d502009-06-04 00:21:18 +0000296 case Type::Pointer: {
297 const PointerType *PointerArg = Arg->getAsPointerType();
298 if (!PointerArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000299 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord560d502009-06-04 00:21:18 +0000300
Douglas Gregor41128772009-06-26 23:27:24 +0000301 unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
Douglas Gregorf67875d2009-06-12 18:26:56 +0000302 return DeduceTemplateArguments(Context, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +0000303 cast<PointerType>(Param)->getPointeeType(),
304 PointerArg->getPointeeType(),
Douglas Gregor41128772009-06-26 23:27:24 +0000305 Info, Deduced, SubTDF);
Douglas Gregord560d502009-06-04 00:21:18 +0000306 }
307
Douglas Gregor199d9912009-06-05 00:53:49 +0000308 // T &
Douglas Gregord560d502009-06-04 00:21:18 +0000309 case Type::LValueReference: {
310 const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType();
311 if (!ReferenceArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000312 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord560d502009-06-04 00:21:18 +0000313
Douglas Gregorf67875d2009-06-12 18:26:56 +0000314 return DeduceTemplateArguments(Context, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +0000315 cast<LValueReferenceType>(Param)->getPointeeType(),
316 ReferenceArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000317 Info, Deduced, 0);
Douglas Gregord560d502009-06-04 00:21:18 +0000318 }
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000319
Douglas Gregor199d9912009-06-05 00:53:49 +0000320 // T && [C++0x]
Douglas Gregord560d502009-06-04 00:21:18 +0000321 case Type::RValueReference: {
322 const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType();
323 if (!ReferenceArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000324 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord560d502009-06-04 00:21:18 +0000325
Douglas Gregorf67875d2009-06-12 18:26:56 +0000326 return DeduceTemplateArguments(Context, TemplateParams,
Douglas Gregord560d502009-06-04 00:21:18 +0000327 cast<RValueReferenceType>(Param)->getPointeeType(),
328 ReferenceArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000329 Info, Deduced, 0);
Douglas Gregord560d502009-06-04 00:21:18 +0000330 }
331
Douglas Gregor199d9912009-06-05 00:53:49 +0000332 // T [] (implied, but not stated explicitly)
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000333 case Type::IncompleteArray: {
334 const IncompleteArrayType *IncompleteArrayArg =
335 Context.getAsIncompleteArrayType(Arg);
336 if (!IncompleteArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000337 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000338
Douglas Gregorf67875d2009-06-12 18:26:56 +0000339 return DeduceTemplateArguments(Context, TemplateParams,
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000340 Context.getAsIncompleteArrayType(Param)->getElementType(),
341 IncompleteArrayArg->getElementType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000342 Info, Deduced, 0);
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000343 }
Douglas Gregor199d9912009-06-05 00:53:49 +0000344
345 // T [integer-constant]
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000346 case Type::ConstantArray: {
347 const ConstantArrayType *ConstantArrayArg =
348 Context.getAsConstantArrayType(Arg);
349 if (!ConstantArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000350 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000351
352 const ConstantArrayType *ConstantArrayParm =
353 Context.getAsConstantArrayType(Param);
354 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
Douglas Gregorf67875d2009-06-12 18:26:56 +0000355 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000356
Douglas Gregorf67875d2009-06-12 18:26:56 +0000357 return DeduceTemplateArguments(Context, TemplateParams,
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000358 ConstantArrayParm->getElementType(),
359 ConstantArrayArg->getElementType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000360 Info, Deduced, 0);
Anders Carlsson4d6fb502009-06-04 04:11:30 +0000361 }
362
Douglas Gregor199d9912009-06-05 00:53:49 +0000363 // type [i]
364 case Type::DependentSizedArray: {
365 const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg);
366 if (!ArrayArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000367 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000368
369 // Check the element type of the arrays
370 const DependentSizedArrayType *DependentArrayParm
371 = cast<DependentSizedArrayType>(Param);
Douglas Gregorf67875d2009-06-12 18:26:56 +0000372 if (Sema::TemplateDeductionResult Result
373 = DeduceTemplateArguments(Context, TemplateParams,
374 DependentArrayParm->getElementType(),
375 ArrayArg->getElementType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000376 Info, Deduced, 0))
Douglas Gregorf67875d2009-06-12 18:26:56 +0000377 return Result;
Douglas Gregor199d9912009-06-05 00:53:49 +0000378
379 // Determine the array bound is something we can deduce.
380 NonTypeTemplateParmDecl *NTTP
381 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
382 if (!NTTP)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000383 return Sema::TDK_Success;
Douglas Gregor199d9912009-06-05 00:53:49 +0000384
385 // We can perform template argument deduction for the given non-type
386 // template parameter.
387 assert(NTTP->getDepth() == 0 &&
388 "Cannot deduce non-type template argument at depth > 0");
389 if (const ConstantArrayType *ConstantArrayArg
Anders Carlsson335e24a2009-06-16 22:44:31 +0000390 = dyn_cast<ConstantArrayType>(ArrayArg)) {
391 llvm::APSInt Size(ConstantArrayArg->getSize());
392 return DeduceNonTypeTemplateArgument(Context, NTTP, Size,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000393 Info, Deduced);
Anders Carlsson335e24a2009-06-16 22:44:31 +0000394 }
Douglas Gregor199d9912009-06-05 00:53:49 +0000395 if (const DependentSizedArrayType *DependentArrayArg
396 = dyn_cast<DependentSizedArrayType>(ArrayArg))
397 return DeduceNonTypeTemplateArgument(Context, NTTP,
398 DependentArrayArg->getSizeExpr(),
Douglas Gregorf67875d2009-06-12 18:26:56 +0000399 Info, Deduced);
Douglas Gregor199d9912009-06-05 00:53:49 +0000400
401 // Incomplete type does not match a dependently-sized array type
Douglas Gregorf67875d2009-06-12 18:26:56 +0000402 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000403 }
404
Douglas Gregor0fce0ae2009-06-08 15:59:14 +0000405 // type(*)(T)
406 // T(*)()
407 // T(*)(T)
Anders Carlssona27fad52009-06-08 15:19:08 +0000408 case Type::FunctionProto: {
409 const FunctionProtoType *FunctionProtoArg =
410 dyn_cast<FunctionProtoType>(Arg);
411 if (!FunctionProtoArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000412 return Sema::TDK_NonDeducedMismatch;
Anders Carlssona27fad52009-06-08 15:19:08 +0000413
414 const FunctionProtoType *FunctionProtoParam =
415 cast<FunctionProtoType>(Param);
Anders Carlsson994b6cb2009-06-08 19:22:23 +0000416
417 if (FunctionProtoParam->getTypeQuals() !=
418 FunctionProtoArg->getTypeQuals())
Douglas Gregorf67875d2009-06-12 18:26:56 +0000419 return Sema::TDK_NonDeducedMismatch;
Anders Carlssona27fad52009-06-08 15:19:08 +0000420
Anders Carlsson994b6cb2009-06-08 19:22:23 +0000421 if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs())
Douglas Gregorf67875d2009-06-12 18:26:56 +0000422 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson994b6cb2009-06-08 19:22:23 +0000423
424 if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
Douglas Gregorf67875d2009-06-12 18:26:56 +0000425 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson994b6cb2009-06-08 19:22:23 +0000426
Anders Carlssona27fad52009-06-08 15:19:08 +0000427 // Check return types.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000428 if (Sema::TemplateDeductionResult Result
429 = DeduceTemplateArguments(Context, TemplateParams,
430 FunctionProtoParam->getResultType(),
431 FunctionProtoArg->getResultType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000432 Info, Deduced, 0))
Douglas Gregorf67875d2009-06-12 18:26:56 +0000433 return Result;
Anders Carlssona27fad52009-06-08 15:19:08 +0000434
Anders Carlssona27fad52009-06-08 15:19:08 +0000435 for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) {
436 // Check argument types.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000437 if (Sema::TemplateDeductionResult Result
438 = DeduceTemplateArguments(Context, TemplateParams,
439 FunctionProtoParam->getArgType(I),
440 FunctionProtoArg->getArgType(I),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000441 Info, Deduced, 0))
Douglas Gregorf67875d2009-06-12 18:26:56 +0000442 return Result;
Anders Carlssona27fad52009-06-08 15:19:08 +0000443 }
444
Douglas Gregorf67875d2009-06-12 18:26:56 +0000445 return Sema::TDK_Success;
Anders Carlssona27fad52009-06-08 15:19:08 +0000446 }
Douglas Gregord708c722009-06-09 16:35:58 +0000447
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000448 // template-name<T> (where template-name refers to a class template)
Douglas Gregord708c722009-06-09 16:35:58 +0000449 // template-name<i>
450 // TT<T> (TODO)
451 // TT<i> (TODO)
452 // TT<> (TODO)
453 case Type::TemplateSpecialization: {
454 const TemplateSpecializationType *SpecParam
455 = cast<TemplateSpecializationType>(Param);
456
457 // Check whether the template argument is a dependent template-id.
458 // FIXME: This is untested code; it can be tested when we implement
459 // partial ordering of class template partial specializations.
460 if (const TemplateSpecializationType *SpecArg
461 = dyn_cast<TemplateSpecializationType>(Arg)) {
462 // Perform template argument deduction for the template name.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000463 if (Sema::TemplateDeductionResult Result
464 = DeduceTemplateArguments(Context,
465 SpecParam->getTemplateName(),
466 SpecArg->getTemplateName(),
467 Info, Deduced))
468 return Result;
Douglas Gregord708c722009-06-09 16:35:58 +0000469
470 unsigned NumArgs = SpecParam->getNumArgs();
471
472 // FIXME: When one of the template-names refers to a
473 // declaration with default template arguments, do we need to
474 // fill in those default template arguments here? Most likely,
475 // the answer is "yes", but I don't see any references. This
476 // issue may be resolved elsewhere, because we may want to
477 // instantiate default template arguments when
478 if (SpecArg->getNumArgs() != NumArgs)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000479 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord708c722009-06-09 16:35:58 +0000480
481 // Perform template argument deduction on each template
482 // argument.
483 for (unsigned I = 0; I != NumArgs; ++I)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000484 if (Sema::TemplateDeductionResult Result
485 = DeduceTemplateArguments(Context, TemplateParams,
486 SpecParam->getArg(I),
487 SpecArg->getArg(I),
488 Info, Deduced))
489 return Result;
Douglas Gregord708c722009-06-09 16:35:58 +0000490
Douglas Gregorf67875d2009-06-12 18:26:56 +0000491 return Sema::TDK_Success;
Douglas Gregord708c722009-06-09 16:35:58 +0000492 }
493
494 // If the argument type is a class template specialization, we
495 // perform template argument deduction using its template
496 // arguments.
497 const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
498 if (!RecordArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000499 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord708c722009-06-09 16:35:58 +0000500
Douglas Gregor41128772009-06-26 23:27:24 +0000501 // FIXME: Check TDF_DerivedClass here. When this flag is set, we need
502 // to troll through the base classes of the argument and try matching
503 // all of them. Failure to match does not mean that there is a problem,
504 // of course.
505
Douglas Gregord708c722009-06-09 16:35:58 +0000506 ClassTemplateSpecializationDecl *SpecArg
507 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
508 if (!SpecArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000509 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord708c722009-06-09 16:35:58 +0000510
511 // Perform template argument deduction for the template name.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000512 if (Sema::TemplateDeductionResult Result
513 = DeduceTemplateArguments(Context,
514 SpecParam->getTemplateName(),
515 TemplateName(SpecArg->getSpecializedTemplate()),
516 Info, Deduced))
517 return Result;
Douglas Gregord708c722009-06-09 16:35:58 +0000518
519 // FIXME: Can the # of arguments in the parameter and the argument differ?
520 unsigned NumArgs = SpecParam->getNumArgs();
521 const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs();
522 if (NumArgs != ArgArgs.size())
Douglas Gregorf67875d2009-06-12 18:26:56 +0000523 return Sema::TDK_NonDeducedMismatch;
Douglas Gregord708c722009-06-09 16:35:58 +0000524
525 for (unsigned I = 0; I != NumArgs; ++I)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000526 if (Sema::TemplateDeductionResult Result
527 = DeduceTemplateArguments(Context, TemplateParams,
528 SpecParam->getArg(I),
529 ArgArgs.get(I),
530 Info, Deduced))
531 return Result;
Anders Carlssona27fad52009-06-08 15:19:08 +0000532
Douglas Gregorf67875d2009-06-12 18:26:56 +0000533 return Sema::TDK_Success;
Douglas Gregord708c722009-06-09 16:35:58 +0000534 }
535
Douglas Gregor637a4092009-06-10 23:47:09 +0000536 // T type::*
537 // T T::*
538 // T (type::*)()
539 // type (T::*)()
540 // type (type::*)(T)
541 // type (T::*)(T)
542 // T (type::*)(T)
543 // T (T::*)()
544 // T (T::*)(T)
545 case Type::MemberPointer: {
546 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
547 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
548 if (!MemPtrArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000549 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor637a4092009-06-10 23:47:09 +0000550
Douglas Gregorf67875d2009-06-12 18:26:56 +0000551 if (Sema::TemplateDeductionResult Result
552 = DeduceTemplateArguments(Context, TemplateParams,
553 MemPtrParam->getPointeeType(),
554 MemPtrArg->getPointeeType(),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000555 Info, Deduced,
556 TDF & TDF_IgnoreQualifiers))
Douglas Gregorf67875d2009-06-12 18:26:56 +0000557 return Result;
558
559 return DeduceTemplateArguments(Context, TemplateParams,
560 QualType(MemPtrParam->getClass(), 0),
561 QualType(MemPtrArg->getClass(), 0),
Douglas Gregor508f1c82009-06-26 23:10:12 +0000562 Info, Deduced, 0);
Douglas Gregor637a4092009-06-10 23:47:09 +0000563 }
564
Anders Carlsson9a917e42009-06-12 22:56:54 +0000565 // (clang extension)
566 //
Anders Carlsson859ba502009-06-12 16:23:10 +0000567 // type(^)(T)
568 // T(^)()
569 // T(^)(T)
570 case Type::BlockPointer: {
571 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
572 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
573
574 if (!BlockPtrArg)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000575 return Sema::TDK_NonDeducedMismatch;
Anders Carlsson859ba502009-06-12 16:23:10 +0000576
Douglas Gregorf67875d2009-06-12 18:26:56 +0000577 return DeduceTemplateArguments(Context, TemplateParams,
Anders Carlsson859ba502009-06-12 16:23:10 +0000578 BlockPtrParam->getPointeeType(),
Douglas Gregorf67875d2009-06-12 18:26:56 +0000579 BlockPtrArg->getPointeeType(), Info,
Douglas Gregor508f1c82009-06-26 23:10:12 +0000580 Deduced, 0);
Anders Carlsson859ba502009-06-12 16:23:10 +0000581 }
582
Douglas Gregor637a4092009-06-10 23:47:09 +0000583 case Type::TypeOfExpr:
584 case Type::TypeOf:
585 case Type::Typename:
586 // No template argument deduction for these types
Douglas Gregorf67875d2009-06-12 18:26:56 +0000587 return Sema::TDK_Success;
Douglas Gregor637a4092009-06-10 23:47:09 +0000588
Douglas Gregord560d502009-06-04 00:21:18 +0000589 default:
590 break;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000591 }
592
593 // FIXME: Many more cases to go (to go).
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000594 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000595}
596
Douglas Gregorf67875d2009-06-12 18:26:56 +0000597static Sema::TemplateDeductionResult
598DeduceTemplateArguments(ASTContext &Context,
599 TemplateParameterList *TemplateParams,
600 const TemplateArgument &Param,
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000601 const TemplateArgument &Arg,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000602 Sema::TemplateDeductionInfo &Info,
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000603 llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000604 switch (Param.getKind()) {
Douglas Gregor199d9912009-06-05 00:53:49 +0000605 case TemplateArgument::Null:
606 assert(false && "Null template argument in parameter list");
607 break;
608
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000609 case TemplateArgument::Type:
Douglas Gregor199d9912009-06-05 00:53:49 +0000610 assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
Douglas Gregor508f1c82009-06-26 23:10:12 +0000611 return DeduceTemplateArguments(Context, TemplateParams, Param.getAsType(),
612 Arg.getAsType(), Info, Deduced, 0);
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000613
Douglas Gregor199d9912009-06-05 00:53:49 +0000614 case TemplateArgument::Declaration:
615 // FIXME: Implement this check
616 assert(false && "Unimplemented template argument deduction case");
Douglas Gregorf67875d2009-06-12 18:26:56 +0000617 Info.FirstArg = Param;
618 Info.SecondArg = Arg;
619 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000620
621 case TemplateArgument::Integral:
622 if (Arg.getKind() == TemplateArgument::Integral) {
623 // FIXME: Zero extension + sign checking here?
Douglas Gregorf67875d2009-06-12 18:26:56 +0000624 if (*Param.getAsIntegral() == *Arg.getAsIntegral())
625 return Sema::TDK_Success;
626
627 Info.FirstArg = Param;
628 Info.SecondArg = Arg;
629 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000630 }
Douglas Gregorf67875d2009-06-12 18:26:56 +0000631
632 if (Arg.getKind() == TemplateArgument::Expression) {
633 Info.FirstArg = Param;
634 Info.SecondArg = Arg;
635 return Sema::TDK_NonDeducedMismatch;
636 }
Douglas Gregor199d9912009-06-05 00:53:49 +0000637
638 assert(false && "Type/value mismatch");
Douglas Gregorf67875d2009-06-12 18:26:56 +0000639 Info.FirstArg = Param;
640 Info.SecondArg = Arg;
641 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000642
643 case TemplateArgument::Expression: {
644 if (NonTypeTemplateParmDecl *NTTP
645 = getDeducedParameterFromExpr(Param.getAsExpr())) {
646 if (Arg.getKind() == TemplateArgument::Integral)
647 // FIXME: Sign problems here
648 return DeduceNonTypeTemplateArgument(Context, NTTP,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000649 *Arg.getAsIntegral(),
650 Info, Deduced);
Douglas Gregor199d9912009-06-05 00:53:49 +0000651 if (Arg.getKind() == TemplateArgument::Expression)
652 return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
Douglas Gregorf67875d2009-06-12 18:26:56 +0000653 Info, Deduced);
Douglas Gregor199d9912009-06-05 00:53:49 +0000654
655 assert(false && "Type/value mismatch");
Douglas Gregorf67875d2009-06-12 18:26:56 +0000656 Info.FirstArg = Param;
657 Info.SecondArg = Arg;
658 return Sema::TDK_NonDeducedMismatch;
Douglas Gregor199d9912009-06-05 00:53:49 +0000659 }
660
661 // Can't deduce anything, but that's okay.
Douglas Gregorf67875d2009-06-12 18:26:56 +0000662 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000663 }
Anders Carlssond01b1da2009-06-15 17:04:53 +0000664 case TemplateArgument::Pack:
665 assert(0 && "FIXME: Implement!");
666 break;
Douglas Gregor199d9912009-06-05 00:53:49 +0000667 }
668
Douglas Gregorf67875d2009-06-12 18:26:56 +0000669 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000670}
671
Douglas Gregorf67875d2009-06-12 18:26:56 +0000672static Sema::TemplateDeductionResult
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000673DeduceTemplateArguments(ASTContext &Context,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000674 TemplateParameterList *TemplateParams,
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000675 const TemplateArgumentList &ParamList,
676 const TemplateArgumentList &ArgList,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000677 Sema::TemplateDeductionInfo &Info,
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000678 llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
679 assert(ParamList.size() == ArgList.size());
680 for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000681 if (Sema::TemplateDeductionResult Result
682 = DeduceTemplateArguments(Context, TemplateParams,
683 ParamList[I], ArgList[I],
684 Info, Deduced))
685 return Result;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000686 }
Douglas Gregorf67875d2009-06-12 18:26:56 +0000687 return Sema::TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000688}
689
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000690/// \brief Determine whether two template arguments are the same.
691static bool isSameTemplateArg(ASTContext &Context,
692 const TemplateArgument &X,
693 const TemplateArgument &Y) {
694 if (X.getKind() != Y.getKind())
695 return false;
696
697 switch (X.getKind()) {
698 case TemplateArgument::Null:
699 assert(false && "Comparing NULL template argument");
700 break;
701
702 case TemplateArgument::Type:
703 return Context.getCanonicalType(X.getAsType()) ==
704 Context.getCanonicalType(Y.getAsType());
705
706 case TemplateArgument::Declaration:
707 return Context.getCanonicalDecl(X.getAsDecl()) ==
708 Context.getCanonicalDecl(Y.getAsDecl());
709
710 case TemplateArgument::Integral:
711 return *X.getAsIntegral() == *Y.getAsIntegral();
712
713 case TemplateArgument::Expression:
714 // FIXME: We assume that all expressions are distinct, but we should
715 // really check their canonical forms.
716 return false;
717
718 case TemplateArgument::Pack:
719 if (X.pack_size() != Y.pack_size())
720 return false;
721
722 for (TemplateArgument::pack_iterator XP = X.pack_begin(),
723 XPEnd = X.pack_end(),
724 YP = Y.pack_begin();
725 XP != XPEnd; ++XP, ++YP)
726 if (!isSameTemplateArg(Context, *XP, *YP))
727 return false;
728
729 return true;
730 }
731
732 return false;
733}
734
735/// \brief Helper function to build a TemplateParameter when we don't
736/// know its type statically.
737static TemplateParameter makeTemplateParameter(Decl *D) {
738 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
739 return TemplateParameter(TTP);
740 else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
741 return TemplateParameter(NTTP);
742
743 return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
744}
745
Douglas Gregorc1efb3f2009-06-12 22:31:52 +0000746/// \brief Perform template argument deduction to determine whether
747/// the given template arguments match the given class template
748/// partial specialization per C++ [temp.class.spec.match].
Douglas Gregorf67875d2009-06-12 18:26:56 +0000749Sema::TemplateDeductionResult
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000750Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
Douglas Gregorf67875d2009-06-12 18:26:56 +0000751 const TemplateArgumentList &TemplateArgs,
752 TemplateDeductionInfo &Info) {
Douglas Gregorc1efb3f2009-06-12 22:31:52 +0000753 // C++ [temp.class.spec.match]p2:
754 // A partial specialization matches a given actual template
755 // argument list if the template arguments of the partial
756 // specialization can be deduced from the actual template argument
757 // list (14.8.2).
Douglas Gregorbb260412009-06-14 08:02:22 +0000758 SFINAETrap Trap(*this);
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000759 llvm::SmallVector<TemplateArgument, 4> Deduced;
760 Deduced.resize(Partial->getTemplateParameters()->size());
Douglas Gregorf67875d2009-06-12 18:26:56 +0000761 if (TemplateDeductionResult Result
762 = ::DeduceTemplateArguments(Context,
763 Partial->getTemplateParameters(),
764 Partial->getTemplateArgs(),
765 TemplateArgs, Info, Deduced))
766 return Result;
Douglas Gregor637a4092009-06-10 23:47:09 +0000767
Douglas Gregor637a4092009-06-10 23:47:09 +0000768 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
769 Deduced.data(), Deduced.size());
770 if (Inst)
Douglas Gregorf67875d2009-06-12 18:26:56 +0000771 return TDK_InstantiationDepth;
Douglas Gregor199d9912009-06-05 00:53:49 +0000772
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000773 // C++ [temp.deduct.type]p2:
774 // [...] or if any template argument remains neither deduced nor
775 // explicitly specified, template argument deduction fails.
Anders Carlssonfb250522009-06-23 01:26:57 +0000776 TemplateArgumentListBuilder Builder(Partial->getTemplateParameters(),
777 Deduced.size());
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000778 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
Douglas Gregorf67875d2009-06-12 18:26:56 +0000779 if (Deduced[I].isNull()) {
780 Decl *Param
781 = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I));
782 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
783 Info.Param = TTP;
784 else if (NonTypeTemplateParmDecl *NTTP
785 = dyn_cast<NonTypeTemplateParmDecl>(Param))
786 Info.Param = NTTP;
787 else
788 Info.Param = cast<TemplateTemplateParmDecl>(Param);
789 return TDK_Incomplete;
790 }
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000791
Anders Carlssonfb250522009-06-23 01:26:57 +0000792 Builder.Append(Deduced[I]);
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000793 }
794
795 // Form the template argument list from the deduced template arguments.
796 TemplateArgumentList *DeducedArgumentList
Anders Carlssonfb250522009-06-23 01:26:57 +0000797 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
Douglas Gregorf67875d2009-06-12 18:26:56 +0000798 Info.reset(DeducedArgumentList);
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000799
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000800 // Substitute the deduced template arguments into the template
801 // arguments of the class template partial specialization, and
802 // verify that the instantiated template arguments are both valid
803 // and are equivalent to the template arguments originally provided
Douglas Gregorc9e5d252009-06-13 00:59:32 +0000804 // to the class template.
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000805 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
806 const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs();
807 for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) {
Douglas Gregorc9e5d252009-06-13 00:59:32 +0000808 Decl *Param = const_cast<Decl *>(
809 ClassTemplate->getTemplateParameters()->getParam(I));
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000810 TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I],
811 *DeducedArgumentList);
812 if (InstArg.isNull()) {
813 Info.Param = makeTemplateParameter(Param);
814 Info.FirstArg = PartialTemplateArgs[I];
815 return TDK_SubstitutionFailure;
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000816 }
Douglas Gregorf670c8c2009-06-26 20:57:09 +0000817
818 if (InstArg.getKind() == TemplateArgument::Expression) {
819 // When the argument is an expression, check the expression result
820 // against the actual template parameter to get down to the canonical
821 // template argument.
822 Expr *InstExpr = InstArg.getAsExpr();
823 if (NonTypeTemplateParmDecl *NTTP
824 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
825 if (CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) {
826 Info.Param = makeTemplateParameter(Param);
827 Info.FirstArg = PartialTemplateArgs[I];
828 return TDK_SubstitutionFailure;
829 }
830 } else if (TemplateTemplateParmDecl *TTP
831 = dyn_cast<TemplateTemplateParmDecl>(Param)) {
832 // FIXME: template template arguments should really resolve to decls
833 DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(InstExpr);
834 if (!DRE || CheckTemplateArgument(TTP, DRE)) {
835 Info.Param = makeTemplateParameter(Param);
836 Info.FirstArg = PartialTemplateArgs[I];
837 return TDK_SubstitutionFailure;
838 }
839 }
840 }
841
842 if (!isSameTemplateArg(Context, TemplateArgs[I], InstArg)) {
843 Info.Param = makeTemplateParameter(Param);
844 Info.FirstArg = TemplateArgs[I];
845 Info.SecondArg = InstArg;
846 return TDK_NonDeducedMismatch;
847 }
Douglas Gregor02cbbd22009-06-11 18:10:32 +0000848 }
849
Douglas Gregorbb260412009-06-14 08:02:22 +0000850 if (Trap.hasErrorOccurred())
851 return TDK_SubstitutionFailure;
852
Douglas Gregorf67875d2009-06-12 18:26:56 +0000853 return TDK_Success;
Douglas Gregor0b9247f2009-06-04 00:03:07 +0000854}
Douglas Gregor031a5882009-06-13 00:26:55 +0000855
Douglas Gregor41128772009-06-26 23:27:24 +0000856/// \brief Determine whether the given type T is a simple-template-id type.
857static bool isSimpleTemplateIdType(QualType T) {
858 if (const TemplateSpecializationType *Spec
859 = T->getAsTemplateSpecializationType())
860 return Spec->getTemplateName().getAsTemplateDecl() != 0;
861
862 return false;
863}
864
Douglas Gregore53060f2009-06-25 22:08:12 +0000865/// \brief Perform template argument deduction from a function call
866/// (C++ [temp.deduct.call]).
867///
868/// \param FunctionTemplate the function template for which we are performing
869/// template argument deduction.
870///
871/// \param Args the function call arguments
872///
873/// \param NumArgs the number of arguments in Args
874///
875/// \param Specialization if template argument deduction was successful,
876/// this will be set to the function template specialization produced by
877/// template argument deduction.
878///
879/// \param Info the argument will be updated to provide additional information
880/// about template argument deduction.
881///
882/// \returns the result of template argument deduction.
883///
884/// FIXME: We will also need to pass in any explicitly-specified template
885/// arguments.
886Sema::TemplateDeductionResult
887Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
888 Expr **Args, unsigned NumArgs,
889 FunctionDecl *&Specialization,
890 TemplateDeductionInfo &Info) {
891 FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
892
893 // C++ [temp.deduct.call]p1:
894 // Template argument deduction is done by comparing each function template
895 // parameter type (call it P) with the type of the corresponding argument
896 // of the call (call it A) as described below.
897 unsigned CheckArgs = NumArgs;
898 if (NumArgs < Function->getNumParams())
899 return TDK_TooFewArguments;
900 else if (NumArgs > Function->getNumParams()) {
901 const FunctionProtoType *Proto
902 = Function->getType()->getAsFunctionProtoType();
903 if (!Proto->isVariadic())
904 return TDK_TooManyArguments;
905
906 CheckArgs = Function->getNumParams();
907 }
908
Douglas Gregor500d3312009-06-26 18:27:22 +0000909 // Template argument deduction for function templates in a SFINAE context.
910 // Trap any errors that might occur.
Douglas Gregore53060f2009-06-25 22:08:12 +0000911 SFINAETrap Trap(*this);
Douglas Gregor500d3312009-06-26 18:27:22 +0000912
913 // Deduce template arguments from the function parameters.
Douglas Gregore53060f2009-06-25 22:08:12 +0000914 llvm::SmallVector<TemplateArgument, 4> Deduced;
915 Deduced.resize(FunctionTemplate->getTemplateParameters()->size());
916 TemplateParameterList *TemplateParams
917 = FunctionTemplate->getTemplateParameters();
918 for (unsigned I = 0; I != CheckArgs; ++I) {
919 QualType ParamType = Function->getParamDecl(I)->getType();
920 QualType ArgType = Args[I]->getType();
Douglas Gregor500d3312009-06-26 18:27:22 +0000921
Douglas Gregore53060f2009-06-25 22:08:12 +0000922 // C++ [temp.deduct.call]p2:
923 // If P is not a reference type:
924 QualType CanonParamType = Context.getCanonicalType(ParamType);
Douglas Gregor500d3312009-06-26 18:27:22 +0000925 bool ParamWasReference = isa<ReferenceType>(CanonParamType);
926 if (!ParamWasReference) {
Douglas Gregore53060f2009-06-25 22:08:12 +0000927 // - If A is an array type, the pointer type produced by the
928 // array-to-pointer standard conversion (4.2) is used in place of
929 // A for type deduction; otherwise,
930 if (ArgType->isArrayType())
931 ArgType = Context.getArrayDecayedType(ArgType);
932 // - If A is a function type, the pointer type produced by the
933 // function-to-pointer standard conversion (4.3) is used in place
934 // of A for type deduction; otherwise,
935 else if (ArgType->isFunctionType())
936 ArgType = Context.getPointerType(ArgType);
937 else {
938 // - If A is a cv-qualified type, the top level cv-qualifiers of A’s
939 // type are ignored for type deduction.
940 QualType CanonArgType = Context.getCanonicalType(ArgType);
941 if (CanonArgType.getCVRQualifiers())
942 ArgType = CanonArgType.getUnqualifiedType();
943 }
944 }
945
946 // C++0x [temp.deduct.call]p3:
947 // If P is a cv-qualified type, the top level cv-qualifiers of P’s type
948 // are ignored for type deduction.
949 if (CanonParamType.getCVRQualifiers())
950 ParamType = CanonParamType.getUnqualifiedType();
951 if (const ReferenceType *ParamRefType = ParamType->getAsReferenceType()) {
952 // [...] If P is a reference type, the type referred to by P is used
953 // for type deduction.
954 ParamType = ParamRefType->getPointeeType();
955
956 // [...] If P is of the form T&&, where T is a template parameter, and
957 // the argument is an lvalue, the type A& is used in place of A for
958 // type deduction.
959 if (isa<RValueReferenceType>(ParamRefType) &&
960 ParamRefType->getAsTemplateTypeParmType() &&
961 Args[I]->isLvalue(Context) == Expr::LV_Valid)
962 ArgType = Context.getLValueReferenceType(ArgType);
963 }
964
965 // C++0x [temp.deduct.call]p4:
966 // In general, the deduction process attempts to find template argument
967 // values that will make the deduced A identical to A (after the type A
968 // is transformed as described above). [...]
Douglas Gregor508f1c82009-06-26 23:10:12 +0000969 unsigned TDF = 0;
970
971 // - If the original P is a reference type, the deduced A (i.e., the
972 // type referred to by the reference) can be more cv-qualified than
973 // the transformed A.
974 if (ParamWasReference)
975 TDF |= TDF_ParamWithReferenceType;
976 // - The transformed A can be another pointer or pointer to member
977 // type that can be converted to the deduced A via a qualification
978 // conversion (4.4).
979 if (ArgType->isPointerType() || ArgType->isMemberPointerType())
980 TDF |= TDF_IgnoreQualifiers;
Douglas Gregor41128772009-06-26 23:27:24 +0000981 // - If P is a class and P has the form simple-template-id, then the
982 // transformed A can be a derived class of the deduced A. Likewise,
983 // if P is a pointer to a class of the form simple-template-id, the
984 // transformed A can be a pointer to a derived class pointed to by
985 // the deduced A.
986 if (isSimpleTemplateIdType(ParamType) ||
987 (isa<PointerType>(ParamType) &&
988 isSimpleTemplateIdType(
989 ParamType->getAsPointerType()->getPointeeType())))
990 TDF |= TDF_DerivedClass;
991
Douglas Gregore53060f2009-06-25 22:08:12 +0000992 if (TemplateDeductionResult Result
993 = ::DeduceTemplateArguments(Context, TemplateParams,
Douglas Gregor500d3312009-06-26 18:27:22 +0000994 ParamType, ArgType, Info, Deduced,
Douglas Gregor508f1c82009-06-26 23:10:12 +0000995 TDF))
Douglas Gregore53060f2009-06-25 22:08:12 +0000996 return Result;
997
998 // FIXME: C++ [temp.deduct.call] paragraphs 6-9 deal with function
999 // pointer parameters.
1000 }
1001
1002 InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
1003 FunctionTemplate, Deduced.data(), Deduced.size());
1004 if (Inst)
1005 return TDK_InstantiationDepth;
1006
1007 // C++ [temp.deduct.type]p2:
1008 // [...] or if any template argument remains neither deduced nor
1009 // explicitly specified, template argument deduction fails.
1010 TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size());
1011 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
1012 if (Deduced[I].isNull()) {
1013 Decl *Param
1014 = const_cast<Decl *>(TemplateParams->getParam(I));
1015 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
1016 Info.Param = TTP;
1017 else if (NonTypeTemplateParmDecl *NTTP
1018 = dyn_cast<NonTypeTemplateParmDecl>(Param))
1019 Info.Param = NTTP;
1020 else
1021 Info.Param = cast<TemplateTemplateParmDecl>(Param);
1022 return TDK_Incomplete;
1023 }
1024
1025 Builder.Append(Deduced[I]);
1026 }
1027
1028 // Form the template argument list from the deduced template arguments.
1029 TemplateArgumentList *DeducedArgumentList
1030 = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
1031 Info.reset(DeducedArgumentList);
1032
1033 // Substitute the deduced template arguments into the function template
1034 // declaration to produce the function template specialization.
1035 Specialization = cast_or_null<FunctionDecl>(
1036 InstantiateDecl(FunctionTemplate->getTemplatedDecl(),
1037 FunctionTemplate->getDeclContext(),
1038 *DeducedArgumentList));
1039
1040 if (!Specialization || Trap.hasErrorOccurred())
1041 return TDK_SubstitutionFailure;
1042
Douglas Gregor1637be72009-06-26 00:10:03 +00001043 // Turn the specialization into an actual function template specialization.
1044 Specialization->setFunctionTemplateSpecialization(Context,
1045 FunctionTemplate,
1046 Info.take());
Douglas Gregore53060f2009-06-25 22:08:12 +00001047 return TDK_Success;
1048}
1049
Douglas Gregor031a5882009-06-13 00:26:55 +00001050static void
1051MarkDeducedTemplateParameters(Sema &SemaRef,
1052 const TemplateArgument &TemplateArg,
1053 llvm::SmallVectorImpl<bool> &Deduced);
1054
1055/// \brief Mark the template arguments that are deduced by the given
1056/// expression.
1057static void
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001058MarkDeducedTemplateParameters(const Expr *E,
1059 llvm::SmallVectorImpl<bool> &Deduced) {
1060 const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
Douglas Gregor031a5882009-06-13 00:26:55 +00001061 if (!E)
1062 return;
1063
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001064 const NonTypeTemplateParmDecl *NTTP
Douglas Gregor031a5882009-06-13 00:26:55 +00001065 = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
1066 if (!NTTP)
1067 return;
1068
1069 Deduced[NTTP->getIndex()] = true;
1070}
1071
1072/// \brief Mark the template parameters that are deduced by the given
1073/// type.
1074static void
1075MarkDeducedTemplateParameters(Sema &SemaRef, QualType T,
1076 llvm::SmallVectorImpl<bool> &Deduced) {
1077 // Non-dependent types have nothing deducible
1078 if (!T->isDependentType())
1079 return;
1080
1081 T = SemaRef.Context.getCanonicalType(T);
1082 switch (T->getTypeClass()) {
1083 case Type::ExtQual:
1084 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001085 QualType(cast<ExtQualType>(T)->getBaseType(), 0),
Douglas Gregor031a5882009-06-13 00:26:55 +00001086 Deduced);
1087 break;
1088
1089 case Type::Pointer:
1090 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001091 cast<PointerType>(T)->getPointeeType(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001092 Deduced);
1093 break;
1094
1095 case Type::BlockPointer:
1096 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001097 cast<BlockPointerType>(T)->getPointeeType(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001098 Deduced);
1099 break;
1100
1101 case Type::LValueReference:
1102 case Type::RValueReference:
1103 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001104 cast<ReferenceType>(T)->getPointeeType(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001105 Deduced);
1106 break;
1107
1108 case Type::MemberPointer: {
1109 const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
1110 MarkDeducedTemplateParameters(SemaRef, MemPtr->getPointeeType(), Deduced);
1111 MarkDeducedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
1112 Deduced);
1113 break;
1114 }
1115
1116 case Type::DependentSizedArray:
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001117 MarkDeducedTemplateParameters(cast<DependentSizedArrayType>(T)->getSizeExpr(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001118 Deduced);
1119 // Fall through to check the element type
1120
1121 case Type::ConstantArray:
1122 case Type::IncompleteArray:
1123 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001124 cast<ArrayType>(T)->getElementType(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001125 Deduced);
1126 break;
1127
1128 case Type::Vector:
1129 case Type::ExtVector:
1130 MarkDeducedTemplateParameters(SemaRef,
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001131 cast<VectorType>(T)->getElementType(),
Douglas Gregor031a5882009-06-13 00:26:55 +00001132 Deduced);
1133 break;
1134
Douglas Gregor9cdda0c2009-06-17 21:51:59 +00001135 case Type::DependentSizedExtVector: {
1136 const DependentSizedExtVectorType *VecType
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001137 = cast<DependentSizedExtVectorType>(T);
Douglas Gregor9cdda0c2009-06-17 21:51:59 +00001138 MarkDeducedTemplateParameters(SemaRef, VecType->getElementType(), Deduced);
1139 MarkDeducedTemplateParameters(VecType->getSizeExpr(), Deduced);
1140 break;
1141 }
1142
Douglas Gregor031a5882009-06-13 00:26:55 +00001143 case Type::FunctionProto: {
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001144 const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
Douglas Gregor031a5882009-06-13 00:26:55 +00001145 MarkDeducedTemplateParameters(SemaRef, Proto->getResultType(), Deduced);
1146 for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
1147 MarkDeducedTemplateParameters(SemaRef, Proto->getArgType(I), Deduced);
1148 break;
1149 }
1150
1151 case Type::TemplateTypeParm:
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001152 Deduced[cast<TemplateTypeParmType>(T)->getIndex()] = true;
Douglas Gregor031a5882009-06-13 00:26:55 +00001153 break;
1154
1155 case Type::TemplateSpecialization: {
1156 const TemplateSpecializationType *Spec
Douglas Gregorf6ddb732009-06-18 18:45:36 +00001157 = cast<TemplateSpecializationType>(T);
Douglas Gregor031a5882009-06-13 00:26:55 +00001158 if (TemplateDecl *Template = Spec->getTemplateName().getAsTemplateDecl())
1159 if (TemplateTemplateParmDecl *TTP
1160 = dyn_cast<TemplateTemplateParmDecl>(Template))
1161 Deduced[TTP->getIndex()] = true;
1162
1163 for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
1164 MarkDeducedTemplateParameters(SemaRef, Spec->getArg(I), Deduced);
1165
1166 break;
1167 }
1168
1169 // None of these types have any deducible parts.
1170 case Type::Builtin:
1171 case Type::FixedWidthInt:
1172 case Type::Complex:
1173 case Type::VariableArray:
1174 case Type::FunctionNoProto:
1175 case Type::Record:
1176 case Type::Enum:
1177 case Type::Typename:
1178 case Type::ObjCInterface:
1179 case Type::ObjCQualifiedInterface:
Steve Naroffd1b3c2d2009-06-17 22:40:22 +00001180 case Type::ObjCObjectPointer:
Douglas Gregor031a5882009-06-13 00:26:55 +00001181#define TYPE(Class, Base)
1182#define ABSTRACT_TYPE(Class, Base)
1183#define DEPENDENT_TYPE(Class, Base)
1184#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
1185#include "clang/AST/TypeNodes.def"
1186 break;
1187 }
1188}
1189
1190/// \brief Mark the template parameters that are deduced by this
1191/// template argument.
1192static void
1193MarkDeducedTemplateParameters(Sema &SemaRef,
1194 const TemplateArgument &TemplateArg,
1195 llvm::SmallVectorImpl<bool> &Deduced) {
1196 switch (TemplateArg.getKind()) {
1197 case TemplateArgument::Null:
1198 case TemplateArgument::Integral:
1199 break;
1200
1201 case TemplateArgument::Type:
1202 MarkDeducedTemplateParameters(SemaRef, TemplateArg.getAsType(), Deduced);
1203 break;
1204
1205 case TemplateArgument::Declaration:
1206 if (TemplateTemplateParmDecl *TTP
1207 = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl()))
1208 Deduced[TTP->getIndex()] = true;
1209 break;
1210
1211 case TemplateArgument::Expression:
1212 MarkDeducedTemplateParameters(TemplateArg.getAsExpr(), Deduced);
1213 break;
Anders Carlssond01b1da2009-06-15 17:04:53 +00001214 case TemplateArgument::Pack:
1215 assert(0 && "FIXME: Implement!");
1216 break;
Douglas Gregor031a5882009-06-13 00:26:55 +00001217 }
1218}
1219
1220/// \brief Mark the template parameters can be deduced by the given
1221/// template argument list.
1222///
1223/// \param TemplateArgs the template argument list from which template
1224/// parameters will be deduced.
1225///
1226/// \param Deduced a bit vector whose elements will be set to \c true
1227/// to indicate when the corresponding template parameter will be
1228/// deduced.
1229void
1230Sema::MarkDeducedTemplateParameters(const TemplateArgumentList &TemplateArgs,
1231 llvm::SmallVectorImpl<bool> &Deduced) {
1232 for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
1233 ::MarkDeducedTemplateParameters(*this, TemplateArgs[I], Deduced);
1234}