SemaTemplateDeduction.cpp revision c1efb3faefa7d42f974fe384dfd45e5127f8afa6
1//===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/ 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7//===----------------------------------------------------------------------===/ 8// 9// 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" 21using namespace clang; 22 23static Sema::TemplateDeductionResult 24DeduceTemplateArguments(ASTContext &Context, 25 TemplateParameterList *TemplateParams, 26 const TemplateArgument &Param, 27 const TemplateArgument &Arg, 28 Sema::TemplateDeductionInfo &Info, 29 llvm::SmallVectorImpl<TemplateArgument> &Deduced); 30 31/// \brief If the given expression is of a form that permits the deduction 32/// of a non-type template parameter, return the declaration of that 33/// non-type template parameter. 34static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) { 35 if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 36 E = IC->getSubExpr(); 37 38 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) 39 return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 40 41 return 0; 42} 43 44/// \brief Deduce the value of the given non-type template parameter 45/// from the given constant. 46static Sema::TemplateDeductionResult 47DeduceNonTypeTemplateArgument(ASTContext &Context, 48 NonTypeTemplateParmDecl *NTTP, 49 llvm::APInt Value, 50 Sema::TemplateDeductionInfo &Info, 51 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 52 assert(NTTP->getDepth() == 0 && 53 "Cannot deduce non-type template argument with depth > 0"); 54 55 if (Deduced[NTTP->getIndex()].isNull()) { 56 Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(), 57 llvm::APSInt(Value), 58 NTTP->getType()); 59 return Sema::TDK_Success; 60 } 61 62 assert(Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral); 63 64 // If the template argument was previously deduced to a negative value, 65 // then our deduction fails. 66 const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral(); 67 if (PrevValuePtr->isSigned() && PrevValuePtr->isNegative()) { 68 // FIXME: This is wacky; we should be dealing with APSInts and 69 // checking the actual signs. 70 Info.Param = NTTP; 71 Info.FirstArg = Deduced[NTTP->getIndex()]; 72 Info.SecondArg = TemplateArgument(SourceLocation(), 73 llvm::APSInt(Value), 74 NTTP->getType()); 75 return Sema::TDK_Inconsistent; 76 } 77 78 llvm::APInt PrevValue = *PrevValuePtr; 79 if (Value.getBitWidth() > PrevValue.getBitWidth()) 80 PrevValue.zext(Value.getBitWidth()); 81 else if (Value.getBitWidth() < PrevValue.getBitWidth()) 82 Value.zext(PrevValue.getBitWidth()); 83 84 if (Value != PrevValue) { 85 Info.Param = NTTP; 86 Info.FirstArg = Deduced[NTTP->getIndex()]; 87 Info.SecondArg = TemplateArgument(SourceLocation(), 88 llvm::APSInt(Value), 89 NTTP->getType()); 90 return Sema::TDK_Inconsistent; 91 } 92 93 return Sema::TDK_Success; 94} 95 96/// \brief Deduce the value of the given non-type template parameter 97/// from the given type- or value-dependent expression. 98/// 99/// \returns true if deduction succeeded, false otherwise. 100 101static Sema::TemplateDeductionResult 102DeduceNonTypeTemplateArgument(ASTContext &Context, 103 NonTypeTemplateParmDecl *NTTP, 104 Expr *Value, 105 Sema::TemplateDeductionInfo &Info, 106 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 107 assert(NTTP->getDepth() == 0 && 108 "Cannot deduce non-type template argument with depth > 0"); 109 assert((Value->isTypeDependent() || Value->isValueDependent()) && 110 "Expression template argument must be type- or value-dependent."); 111 112 if (Deduced[NTTP->getIndex()].isNull()) { 113 // FIXME: Clone the Value? 114 Deduced[NTTP->getIndex()] = TemplateArgument(Value); 115 return Sema::TDK_Success; 116 } 117 118 if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) { 119 // Okay, we deduced a constant in one case and a dependent expression 120 // in another case. FIXME: Later, we will check that instantiating the 121 // dependent expression gives us the constant value. 122 return Sema::TDK_Success; 123 } 124 125 // FIXME: Compare the expressions for equality! 126 return Sema::TDK_Success; 127} 128 129static Sema::TemplateDeductionResult 130DeduceTemplateArguments(ASTContext &Context, 131 TemplateName Param, 132 TemplateName Arg, 133 Sema::TemplateDeductionInfo &Info, 134 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 135 // FIXME: Implement template argument deduction for template 136 // template parameters. 137 138 // FIXME: this routine does not have enough information to produce 139 // good diagnostics. 140 141 TemplateDecl *ParamDecl = Param.getAsTemplateDecl(); 142 TemplateDecl *ArgDecl = Arg.getAsTemplateDecl(); 143 144 if (!ParamDecl || !ArgDecl) { 145 // FIXME: fill in Info.Param/Info.FirstArg 146 return Sema::TDK_Inconsistent; 147 } 148 149 ParamDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ParamDecl)); 150 ArgDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ArgDecl)); 151 if (ParamDecl != ArgDecl) { 152 // FIXME: fill in Info.Param/Info.FirstArg 153 return Sema::TDK_Inconsistent; 154 } 155 156 return Sema::TDK_Success; 157} 158 159static Sema::TemplateDeductionResult 160DeduceTemplateArguments(ASTContext &Context, 161 TemplateParameterList *TemplateParams, 162 QualType ParamIn, QualType ArgIn, 163 Sema::TemplateDeductionInfo &Info, 164 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 165 // We only want to look at the canonical types, since typedefs and 166 // sugar are not part of template argument deduction. 167 QualType Param = Context.getCanonicalType(ParamIn); 168 QualType Arg = Context.getCanonicalType(ArgIn); 169 170 // If the parameter type is not dependent, just compare the types 171 // directly. 172 if (!Param->isDependentType()) { 173 if (Param == Arg) 174 return Sema::TDK_Success; 175 176 Info.FirstArg = TemplateArgument(SourceLocation(), ParamIn); 177 Info.SecondArg = TemplateArgument(SourceLocation(), ArgIn); 178 return Sema::TDK_NonDeducedMismatch; 179 } 180 181 // C++ [temp.deduct.type]p9: 182 // A template type argument T, a template template argument TT or a 183 // template non-type argument i can be deduced if P and A have one of 184 // the following forms: 185 // 186 // T 187 // cv-list T 188 if (const TemplateTypeParmType *TemplateTypeParm 189 = Param->getAsTemplateTypeParmType()) { 190 unsigned Index = TemplateTypeParm->getIndex(); 191 192 // The argument type can not be less qualified than the parameter 193 // type. 194 if (Param.isMoreQualifiedThan(Arg)) { 195 Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 196 Info.FirstArg = Deduced[Index]; 197 Info.SecondArg = TemplateArgument(SourceLocation(), Arg); 198 return Sema::TDK_InconsistentQuals; 199 } 200 201 assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 202 203 unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers(); 204 QualType DeducedType = Arg.getQualifiedType(Quals); 205 206 if (Deduced[Index].isNull()) 207 Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType); 208 else { 209 // C++ [temp.deduct.type]p2: 210 // [...] If type deduction cannot be done for any P/A pair, or if for 211 // any pair the deduction leads to more than one possible set of 212 // deduced values, or if different pairs yield different deduced 213 // values, or if any template argument remains neither deduced nor 214 // explicitly specified, template argument deduction fails. 215 if (Deduced[Index].getAsType() != DeducedType) { 216 Info.Param 217 = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index)); 218 Info.FirstArg = Deduced[Index]; 219 Info.SecondArg = TemplateArgument(SourceLocation(), Arg); 220 return Sema::TDK_Inconsistent; 221 } 222 } 223 return Sema::TDK_Success; 224 } 225 226 // Set up the template argument deduction information for a failure. 227 Info.FirstArg = TemplateArgument(SourceLocation(), ParamIn); 228 Info.SecondArg = TemplateArgument(SourceLocation(), ArgIn); 229 230 if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 231 return Sema::TDK_NonDeducedMismatch; 232 233 switch (Param->getTypeClass()) { 234 // No deduction possible for these types 235 case Type::Builtin: 236 return Sema::TDK_NonDeducedMismatch; 237 238 // T * 239 case Type::Pointer: { 240 const PointerType *PointerArg = Arg->getAsPointerType(); 241 if (!PointerArg) 242 return Sema::TDK_NonDeducedMismatch; 243 244 return DeduceTemplateArguments(Context, TemplateParams, 245 cast<PointerType>(Param)->getPointeeType(), 246 PointerArg->getPointeeType(), 247 Info, Deduced); 248 } 249 250 // T & 251 case Type::LValueReference: { 252 const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType(); 253 if (!ReferenceArg) 254 return Sema::TDK_NonDeducedMismatch; 255 256 return DeduceTemplateArguments(Context, TemplateParams, 257 cast<LValueReferenceType>(Param)->getPointeeType(), 258 ReferenceArg->getPointeeType(), 259 Info, Deduced); 260 } 261 262 // T && [C++0x] 263 case Type::RValueReference: { 264 const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType(); 265 if (!ReferenceArg) 266 return Sema::TDK_NonDeducedMismatch; 267 268 return DeduceTemplateArguments(Context, TemplateParams, 269 cast<RValueReferenceType>(Param)->getPointeeType(), 270 ReferenceArg->getPointeeType(), 271 Info, Deduced); 272 } 273 274 // T [] (implied, but not stated explicitly) 275 case Type::IncompleteArray: { 276 const IncompleteArrayType *IncompleteArrayArg = 277 Context.getAsIncompleteArrayType(Arg); 278 if (!IncompleteArrayArg) 279 return Sema::TDK_NonDeducedMismatch; 280 281 return DeduceTemplateArguments(Context, TemplateParams, 282 Context.getAsIncompleteArrayType(Param)->getElementType(), 283 IncompleteArrayArg->getElementType(), 284 Info, Deduced); 285 } 286 287 // T [integer-constant] 288 case Type::ConstantArray: { 289 const ConstantArrayType *ConstantArrayArg = 290 Context.getAsConstantArrayType(Arg); 291 if (!ConstantArrayArg) 292 return Sema::TDK_NonDeducedMismatch; 293 294 const ConstantArrayType *ConstantArrayParm = 295 Context.getAsConstantArrayType(Param); 296 if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 297 return Sema::TDK_NonDeducedMismatch; 298 299 return DeduceTemplateArguments(Context, TemplateParams, 300 ConstantArrayParm->getElementType(), 301 ConstantArrayArg->getElementType(), 302 Info, Deduced); 303 } 304 305 // type [i] 306 case Type::DependentSizedArray: { 307 const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg); 308 if (!ArrayArg) 309 return Sema::TDK_NonDeducedMismatch; 310 311 // Check the element type of the arrays 312 const DependentSizedArrayType *DependentArrayParm 313 = cast<DependentSizedArrayType>(Param); 314 if (Sema::TemplateDeductionResult Result 315 = DeduceTemplateArguments(Context, TemplateParams, 316 DependentArrayParm->getElementType(), 317 ArrayArg->getElementType(), 318 Info, Deduced)) 319 return Result; 320 321 // Determine the array bound is something we can deduce. 322 NonTypeTemplateParmDecl *NTTP 323 = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 324 if (!NTTP) 325 return Sema::TDK_Success; 326 327 // We can perform template argument deduction for the given non-type 328 // template parameter. 329 assert(NTTP->getDepth() == 0 && 330 "Cannot deduce non-type template argument at depth > 0"); 331 if (const ConstantArrayType *ConstantArrayArg 332 = dyn_cast<ConstantArrayType>(ArrayArg)) 333 return DeduceNonTypeTemplateArgument(Context, NTTP, 334 ConstantArrayArg->getSize(), 335 Info, Deduced); 336 if (const DependentSizedArrayType *DependentArrayArg 337 = dyn_cast<DependentSizedArrayType>(ArrayArg)) 338 return DeduceNonTypeTemplateArgument(Context, NTTP, 339 DependentArrayArg->getSizeExpr(), 340 Info, Deduced); 341 342 // Incomplete type does not match a dependently-sized array type 343 return Sema::TDK_NonDeducedMismatch; 344 } 345 346 // type(*)(T) 347 // T(*)() 348 // T(*)(T) 349 case Type::FunctionProto: { 350 const FunctionProtoType *FunctionProtoArg = 351 dyn_cast<FunctionProtoType>(Arg); 352 if (!FunctionProtoArg) 353 return Sema::TDK_NonDeducedMismatch; 354 355 const FunctionProtoType *FunctionProtoParam = 356 cast<FunctionProtoType>(Param); 357 358 if (FunctionProtoParam->getTypeQuals() != 359 FunctionProtoArg->getTypeQuals()) 360 return Sema::TDK_NonDeducedMismatch; 361 362 if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs()) 363 return Sema::TDK_NonDeducedMismatch; 364 365 if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic()) 366 return Sema::TDK_NonDeducedMismatch; 367 368 // Check return types. 369 if (Sema::TemplateDeductionResult Result 370 = DeduceTemplateArguments(Context, TemplateParams, 371 FunctionProtoParam->getResultType(), 372 FunctionProtoArg->getResultType(), 373 Info, Deduced)) 374 return Result; 375 376 for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) { 377 // Check argument types. 378 if (Sema::TemplateDeductionResult Result 379 = DeduceTemplateArguments(Context, TemplateParams, 380 FunctionProtoParam->getArgType(I), 381 FunctionProtoArg->getArgType(I), 382 Info, Deduced)) 383 return Result; 384 } 385 386 return Sema::TDK_Success; 387 } 388 389 // template-name<T> (wheretemplate-name refers to a class template) 390 // template-name<i> 391 // TT<T> (TODO) 392 // TT<i> (TODO) 393 // TT<> (TODO) 394 case Type::TemplateSpecialization: { 395 const TemplateSpecializationType *SpecParam 396 = cast<TemplateSpecializationType>(Param); 397 398 // Check whether the template argument is a dependent template-id. 399 // FIXME: This is untested code; it can be tested when we implement 400 // partial ordering of class template partial specializations. 401 if (const TemplateSpecializationType *SpecArg 402 = dyn_cast<TemplateSpecializationType>(Arg)) { 403 // Perform template argument deduction for the template name. 404 if (Sema::TemplateDeductionResult Result 405 = DeduceTemplateArguments(Context, 406 SpecParam->getTemplateName(), 407 SpecArg->getTemplateName(), 408 Info, Deduced)) 409 return Result; 410 411 unsigned NumArgs = SpecParam->getNumArgs(); 412 413 // FIXME: When one of the template-names refers to a 414 // declaration with default template arguments, do we need to 415 // fill in those default template arguments here? Most likely, 416 // the answer is "yes", but I don't see any references. This 417 // issue may be resolved elsewhere, because we may want to 418 // instantiate default template arguments when 419 if (SpecArg->getNumArgs() != NumArgs) 420 return Sema::TDK_NonDeducedMismatch; 421 422 // Perform template argument deduction on each template 423 // argument. 424 for (unsigned I = 0; I != NumArgs; ++I) 425 if (Sema::TemplateDeductionResult Result 426 = DeduceTemplateArguments(Context, TemplateParams, 427 SpecParam->getArg(I), 428 SpecArg->getArg(I), 429 Info, Deduced)) 430 return Result; 431 432 return Sema::TDK_Success; 433 } 434 435 // If the argument type is a class template specialization, we 436 // perform template argument deduction using its template 437 // arguments. 438 const RecordType *RecordArg = dyn_cast<RecordType>(Arg); 439 if (!RecordArg) 440 return Sema::TDK_NonDeducedMismatch; 441 442 ClassTemplateSpecializationDecl *SpecArg 443 = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl()); 444 if (!SpecArg) 445 return Sema::TDK_NonDeducedMismatch; 446 447 // Perform template argument deduction for the template name. 448 if (Sema::TemplateDeductionResult Result 449 = DeduceTemplateArguments(Context, 450 SpecParam->getTemplateName(), 451 TemplateName(SpecArg->getSpecializedTemplate()), 452 Info, Deduced)) 453 return Result; 454 455 // FIXME: Can the # of arguments in the parameter and the argument differ? 456 unsigned NumArgs = SpecParam->getNumArgs(); 457 const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs(); 458 if (NumArgs != ArgArgs.size()) 459 return Sema::TDK_NonDeducedMismatch; 460 461 for (unsigned I = 0; I != NumArgs; ++I) 462 if (Sema::TemplateDeductionResult Result 463 = DeduceTemplateArguments(Context, TemplateParams, 464 SpecParam->getArg(I), 465 ArgArgs.get(I), 466 Info, Deduced)) 467 return Result; 468 469 return Sema::TDK_Success; 470 } 471 472 // T type::* 473 // T T::* 474 // T (type::*)() 475 // type (T::*)() 476 // type (type::*)(T) 477 // type (T::*)(T) 478 // T (type::*)(T) 479 // T (T::*)() 480 // T (T::*)(T) 481 case Type::MemberPointer: { 482 const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param); 483 const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg); 484 if (!MemPtrArg) 485 return Sema::TDK_NonDeducedMismatch; 486 487 if (Sema::TemplateDeductionResult Result 488 = DeduceTemplateArguments(Context, TemplateParams, 489 MemPtrParam->getPointeeType(), 490 MemPtrArg->getPointeeType(), 491 Info, Deduced)) 492 return Result; 493 494 return DeduceTemplateArguments(Context, TemplateParams, 495 QualType(MemPtrParam->getClass(), 0), 496 QualType(MemPtrArg->getClass(), 0), 497 Info, Deduced); 498 } 499 500 // type(^)(T) 501 // T(^)() 502 // T(^)(T) 503 case Type::BlockPointer: { 504 const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param); 505 const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg); 506 507 if (!BlockPtrArg) 508 return Sema::TDK_NonDeducedMismatch; 509 510 return DeduceTemplateArguments(Context, TemplateParams, 511 BlockPtrParam->getPointeeType(), 512 BlockPtrArg->getPointeeType(), Info, 513 Deduced); 514 } 515 516 case Type::TypeOfExpr: 517 case Type::TypeOf: 518 case Type::Typename: 519 // No template argument deduction for these types 520 return Sema::TDK_Success; 521 522 default: 523 break; 524 } 525 526 // FIXME: Many more cases to go (to go). 527 return Sema::TDK_NonDeducedMismatch; 528} 529 530static Sema::TemplateDeductionResult 531DeduceTemplateArguments(ASTContext &Context, 532 TemplateParameterList *TemplateParams, 533 const TemplateArgument &Param, 534 const TemplateArgument &Arg, 535 Sema::TemplateDeductionInfo &Info, 536 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 537 switch (Param.getKind()) { 538 case TemplateArgument::Null: 539 assert(false && "Null template argument in parameter list"); 540 break; 541 542 case TemplateArgument::Type: 543 assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch"); 544 return DeduceTemplateArguments(Context, TemplateParams, 545 Param.getAsType(), 546 Arg.getAsType(), Info, Deduced); 547 548 case TemplateArgument::Declaration: 549 // FIXME: Implement this check 550 assert(false && "Unimplemented template argument deduction case"); 551 Info.FirstArg = Param; 552 Info.SecondArg = Arg; 553 return Sema::TDK_NonDeducedMismatch; 554 555 case TemplateArgument::Integral: 556 if (Arg.getKind() == TemplateArgument::Integral) { 557 // FIXME: Zero extension + sign checking here? 558 if (*Param.getAsIntegral() == *Arg.getAsIntegral()) 559 return Sema::TDK_Success; 560 561 Info.FirstArg = Param; 562 Info.SecondArg = Arg; 563 return Sema::TDK_NonDeducedMismatch; 564 } 565 566 if (Arg.getKind() == TemplateArgument::Expression) { 567 Info.FirstArg = Param; 568 Info.SecondArg = Arg; 569 return Sema::TDK_NonDeducedMismatch; 570 } 571 572 assert(false && "Type/value mismatch"); 573 Info.FirstArg = Param; 574 Info.SecondArg = Arg; 575 return Sema::TDK_NonDeducedMismatch; 576 577 case TemplateArgument::Expression: { 578 if (NonTypeTemplateParmDecl *NTTP 579 = getDeducedParameterFromExpr(Param.getAsExpr())) { 580 if (Arg.getKind() == TemplateArgument::Integral) 581 // FIXME: Sign problems here 582 return DeduceNonTypeTemplateArgument(Context, NTTP, 583 *Arg.getAsIntegral(), 584 Info, Deduced); 585 if (Arg.getKind() == TemplateArgument::Expression) 586 return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(), 587 Info, Deduced); 588 589 assert(false && "Type/value mismatch"); 590 Info.FirstArg = Param; 591 Info.SecondArg = Arg; 592 return Sema::TDK_NonDeducedMismatch; 593 } 594 595 // Can't deduce anything, but that's okay. 596 return Sema::TDK_Success; 597 } 598 } 599 600 return Sema::TDK_Success; 601} 602 603static Sema::TemplateDeductionResult 604DeduceTemplateArguments(ASTContext &Context, 605 TemplateParameterList *TemplateParams, 606 const TemplateArgumentList &ParamList, 607 const TemplateArgumentList &ArgList, 608 Sema::TemplateDeductionInfo &Info, 609 llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 610 assert(ParamList.size() == ArgList.size()); 611 for (unsigned I = 0, N = ParamList.size(); I != N; ++I) { 612 if (Sema::TemplateDeductionResult Result 613 = DeduceTemplateArguments(Context, TemplateParams, 614 ParamList[I], ArgList[I], 615 Info, Deduced)) 616 return Result; 617 } 618 return Sema::TDK_Success; 619} 620 621/// \brief Perform template argument deduction to determine whether 622/// the given template arguments match the given class template 623/// partial specialization per C++ [temp.class.spec.match]. 624Sema::TemplateDeductionResult 625Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 626 const TemplateArgumentList &TemplateArgs, 627 TemplateDeductionInfo &Info) { 628 // C++ [temp.class.spec.match]p2: 629 // A partial specialization matches a given actual template 630 // argument list if the template arguments of the partial 631 // specialization can be deduced from the actual template argument 632 // list (14.8.2). 633 llvm::SmallVector<TemplateArgument, 4> Deduced; 634 Deduced.resize(Partial->getTemplateParameters()->size()); 635 if (TemplateDeductionResult Result 636 = ::DeduceTemplateArguments(Context, 637 Partial->getTemplateParameters(), 638 Partial->getTemplateArgs(), 639 TemplateArgs, Info, Deduced)) 640 return Result; 641 642 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 643 Deduced.data(), Deduced.size()); 644 if (Inst) 645 return TDK_InstantiationDepth; 646 647 // C++ [temp.deduct.type]p2: 648 // [...] or if any template argument remains neither deduced nor 649 // explicitly specified, template argument deduction fails. 650 TemplateArgumentListBuilder Builder(Context); 651 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 652 if (Deduced[I].isNull()) { 653 Decl *Param 654 = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I)); 655 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 656 Info.Param = TTP; 657 else if (NonTypeTemplateParmDecl *NTTP 658 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 659 Info.Param = NTTP; 660 else 661 Info.Param = cast<TemplateTemplateParmDecl>(Param); 662 return TDK_Incomplete; 663 } 664 665 Builder.push_back(Deduced[I]); 666 } 667 668 // Form the template argument list from the deduced template arguments. 669 TemplateArgumentList *DeducedArgumentList 670 = new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true, 671 /*FlattenArgs=*/true); 672 Info.reset(DeducedArgumentList); 673 674 // Now that we have all of the deduced template arguments, take 675 // another pass through them to convert any integral template 676 // arguments to the appropriate type. 677 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 678 TemplateArgument &Arg = Deduced[I]; 679 if (Arg.getKind() == TemplateArgument::Integral) { 680 const NonTypeTemplateParmDecl *Parm 681 = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters() 682 ->getParam(I)); 683 QualType T = InstantiateType(Parm->getType(), *DeducedArgumentList, 684 Parm->getLocation(), Parm->getDeclName()); 685 if (T.isNull()) { 686 Info.Param = const_cast<NonTypeTemplateParmDecl*>(Parm); 687 Info.FirstArg = TemplateArgument(Parm->getLocation(), Parm->getType()); 688 return TDK_SubstitutionFailure; 689 } 690 691 // FIXME: Make sure we didn't overflow our data type! 692 llvm::APSInt &Value = *Arg.getAsIntegral(); 693 unsigned AllowedBits = Context.getTypeSize(T); 694 if (Value.getBitWidth() != AllowedBits) 695 Value.extOrTrunc(AllowedBits); 696 Value.setIsSigned(T->isSignedIntegerType()); 697 Arg.setIntegralType(T); 698 } 699 700 (*DeducedArgumentList)[I] = Arg; 701 } 702 703 // Substitute the deduced template arguments into the template 704 // arguments of the class template partial specialization, and 705 // verify that the instantiated template arguments are both valid 706 // and are equivalent to the template arguments originally provided 707 // to the class template. 708 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 709 const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs(); 710 for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) { 711 TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I], 712 *DeducedArgumentList); 713 if (InstArg.isNull()) { 714 Decl *Param = const_cast<Decl *>( 715 ClassTemplate->getTemplateParameters()->getParam(I)); 716 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 717 Info.Param = TTP; 718 else if (NonTypeTemplateParmDecl *NTTP 719 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 720 Info.Param = NTTP; 721 else 722 Info.Param = cast<TemplateTemplateParmDecl>(Param); 723 Info.FirstArg = PartialTemplateArgs[I]; 724 return TDK_SubstitutionFailure; 725 } 726 727 Decl *Param 728 = const_cast<Decl *>(ClassTemplate->getTemplateParameters()->getParam(I)); 729 if (isa<TemplateTypeParmDecl>(Param)) { 730 if (InstArg.getKind() != TemplateArgument::Type || 731 Context.getCanonicalType(InstArg.getAsType()) 732 != Context.getCanonicalType(TemplateArgs[I].getAsType())) { 733 Info.Param = cast<TemplateTypeParmDecl>(Param); 734 Info.FirstArg = TemplateArgs[I]; 735 Info.SecondArg = InstArg; 736 return TDK_NonDeducedMismatch; 737 } 738 } else if (NonTypeTemplateParmDecl *NTTP 739 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 740 QualType T = InstantiateType(NTTP->getType(), TemplateArgs, 741 NTTP->getLocation(), NTTP->getDeclName()); 742 if (T.isNull()) { 743 Info.Param = NTTP; 744 Info.FirstArg = TemplateArgs[I]; 745 Info.SecondArg = InstArg; 746 return TDK_NonDeducedMismatch; 747 } 748 749 if (InstArg.getKind() == TemplateArgument::Declaration || 750 InstArg.getKind() == TemplateArgument::Expression) { 751 // Turn the template argument into an expression, so that we can 752 // perform type checking on it and convert it to the type of the 753 // non-type template parameter. FIXME: Will this expression be 754 // leaked? It's hard to tell, since our ownership model for 755 // expressions in template arguments is so poor. 756 Expr *E = 0; 757 if (InstArg.getKind() == TemplateArgument::Declaration) { 758 NamedDecl *D = cast<NamedDecl>(InstArg.getAsDecl()); 759 QualType T = Context.OverloadTy; 760 if (ValueDecl *VD = dyn_cast<ValueDecl>(D)) 761 T = VD->getType().getNonReferenceType(); 762 E = new (Context) DeclRefExpr(D, T, InstArg.getLocation()); 763 } else { 764 E = InstArg.getAsExpr(); 765 } 766 767 // Check that the template argument can be used to initialize 768 // the corresponding template parameter. 769 if (CheckTemplateArgument(NTTP, T, E, InstArg)) { 770 // FIXME: This isn't precisely the problem, but since it 771 // can't actually happen in well-formed C++ we don't care at 772 // the moment. Revisit this when we have template argument 773 // deduction for function templates. 774 Info.Param = NTTP; 775 Info.FirstArg = TemplateArgs[I]; 776 Info.SecondArg = InstArg; 777 return TDK_NonDeducedMismatch; 778 } 779 } 780 781 switch (InstArg.getKind()) { 782 case TemplateArgument::Null: 783 assert(false && "Null template arguments cannot get here"); 784 return TDK_NonDeducedMismatch; 785 786 case TemplateArgument::Type: 787 assert(false && "Type/value mismatch"); 788 return TDK_NonDeducedMismatch; 789 790 case TemplateArgument::Integral: { 791 llvm::APSInt &Value = *InstArg.getAsIntegral(); 792 if (T->isIntegralType() || T->isEnumeralType()) { 793 QualType IntegerType = Context.getCanonicalType(T); 794 if (const EnumType *Enum = dyn_cast<EnumType>(IntegerType)) 795 IntegerType = Context.getCanonicalType( 796 Enum->getDecl()->getIntegerType()); 797 798 // Check that an unsigned parameter does not receive a negative 799 // value. 800 if (IntegerType->isUnsignedIntegerType() 801 && (Value.isSigned() && Value.isNegative())) { 802 Info.Param = NTTP; 803 Info.FirstArg = TemplateArgs[I]; 804 Info.SecondArg = InstArg; 805 return TDK_NonDeducedMismatch; 806 } 807 808 // Check for truncation. If the number of bits in the 809 // instantiated template argument exceeds what is allowed by 810 // the type, template argument deduction fails. 811 unsigned AllowedBits = Context.getTypeSize(IntegerType); 812 if (Value.getActiveBits() > AllowedBits) { 813 Info.Param = NTTP; 814 Info.FirstArg = TemplateArgs[I]; 815 Info.SecondArg = InstArg; 816 return TDK_NonDeducedMismatch; 817 } 818 819 if (Value.getBitWidth() != AllowedBits) 820 Value.extOrTrunc(AllowedBits); 821 Value.setIsSigned(IntegerType->isSignedIntegerType()); 822 823 // Check that the instantiated value is the same as the 824 // value provided as a template argument. 825 if (Value != *TemplateArgs[I].getAsIntegral()) { 826 Info.Param = NTTP; 827 Info.FirstArg = TemplateArgs[I]; 828 Info.SecondArg = InstArg; 829 return TDK_NonDeducedMismatch; 830 } 831 } else if (T->isPointerType() || T->isMemberPointerType()) { 832 // Deal with NULL pointers that are used to initialize 833 // pointer and pointer-to-member non-type template 834 // parameters (C++0x). 835 if (TemplateArgs[I].getAsDecl()) { 836 // Not a NULL declaration 837 Info.Param = NTTP; 838 Info.FirstArg = TemplateArgs[I]; 839 Info.SecondArg = InstArg; 840 return TDK_NonDeducedMismatch; 841 } 842 // Check that the integral value is 0, the NULL pointer 843 // constant. 844 if (Value != 0) { 845 Info.Param = NTTP; 846 Info.FirstArg = TemplateArgs[I]; 847 Info.SecondArg = InstArg; 848 return TDK_NonDeducedMismatch; 849 } 850 } else { 851 Info.Param = NTTP; 852 Info.FirstArg = TemplateArgs[I]; 853 Info.SecondArg = InstArg; 854 return TDK_NonDeducedMismatch; 855 } 856 857 break; 858 } 859 860 case TemplateArgument::Declaration: 861 if (Context.getCanonicalDecl(InstArg.getAsDecl()) 862 != Context.getCanonicalDecl(TemplateArgs[I].getAsDecl())) { 863 Info.Param = NTTP; 864 Info.FirstArg = TemplateArgs[I]; 865 Info.SecondArg = InstArg; 866 return TDK_NonDeducedMismatch; 867 } 868 break; 869 870 case TemplateArgument::Expression: 871 // FIXME: Check equality of expressions 872 break; 873 } 874 } else { 875 assert(isa<TemplateTemplateParmDecl>(Param)); 876 // FIXME: Check template template arguments 877 } 878 } 879 880 return TDK_Success; 881} 882