SemaTemplateDeduction.cpp revision f67875d5addf36b951ad37fb04509ab2b572c88a
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 622Sema::TemplateDeductionResult 623Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 624 const TemplateArgumentList &TemplateArgs, 625 TemplateDeductionInfo &Info) { 626 // Deduce the template arguments for the partial specialization 627 llvm::SmallVector<TemplateArgument, 4> Deduced; 628 Deduced.resize(Partial->getTemplateParameters()->size()); 629 if (TemplateDeductionResult Result 630 = ::DeduceTemplateArguments(Context, 631 Partial->getTemplateParameters(), 632 Partial->getTemplateArgs(), 633 TemplateArgs, Info, Deduced)) 634 return Result; 635 636 InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial, 637 Deduced.data(), Deduced.size()); 638 if (Inst) 639 return TDK_InstantiationDepth; 640 641 // C++ [temp.deduct.type]p2: 642 // [...] or if any template argument remains neither deduced nor 643 // explicitly specified, template argument deduction fails. 644 TemplateArgumentListBuilder Builder(Context); 645 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 646 if (Deduced[I].isNull()) { 647 Decl *Param 648 = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I)); 649 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 650 Info.Param = TTP; 651 else if (NonTypeTemplateParmDecl *NTTP 652 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 653 Info.Param = NTTP; 654 else 655 Info.Param = cast<TemplateTemplateParmDecl>(Param); 656 return TDK_Incomplete; 657 } 658 659 Builder.push_back(Deduced[I]); 660 } 661 662 // Form the template argument list from the deduced template arguments. 663 TemplateArgumentList *DeducedArgumentList 664 = new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true, 665 /*FlattenArgs=*/true); 666 Info.reset(DeducedArgumentList); 667 668 // Now that we have all of the deduced template arguments, take 669 // another pass through them to convert any integral template 670 // arguments to the appropriate type. 671 for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 672 TemplateArgument &Arg = Deduced[I]; 673 if (Arg.getKind() == TemplateArgument::Integral) { 674 const NonTypeTemplateParmDecl *Parm 675 = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters() 676 ->getParam(I)); 677 QualType T = InstantiateType(Parm->getType(), *DeducedArgumentList, 678 Parm->getLocation(), Parm->getDeclName()); 679 if (T.isNull()) { 680 Info.Param = const_cast<NonTypeTemplateParmDecl*>(Parm); 681 Info.FirstArg = TemplateArgument(Parm->getLocation(), Parm->getType()); 682 return TDK_SubstitutionFailure; 683 } 684 685 // FIXME: Make sure we didn't overflow our data type! 686 llvm::APSInt &Value = *Arg.getAsIntegral(); 687 unsigned AllowedBits = Context.getTypeSize(T); 688 if (Value.getBitWidth() != AllowedBits) 689 Value.extOrTrunc(AllowedBits); 690 Value.setIsSigned(T->isSignedIntegerType()); 691 Arg.setIntegralType(T); 692 } 693 694 (*DeducedArgumentList)[I] = Arg; 695 } 696 697 // Substitute the deduced template arguments into the template 698 // arguments of the class template partial specialization, and 699 // verify that the instantiated template arguments are both valid 700 // and are equivalent to the template arguments originally provided 701 // to the class template. 702 ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate(); 703 const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs(); 704 for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) { 705 TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I], 706 *DeducedArgumentList); 707 if (InstArg.isNull()) { 708 Decl *Param = const_cast<Decl *>( 709 ClassTemplate->getTemplateParameters()->getParam(I)); 710 if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) 711 Info.Param = TTP; 712 else if (NonTypeTemplateParmDecl *NTTP 713 = dyn_cast<NonTypeTemplateParmDecl>(Param)) 714 Info.Param = NTTP; 715 else 716 Info.Param = cast<TemplateTemplateParmDecl>(Param); 717 Info.FirstArg = PartialTemplateArgs[I]; 718 return TDK_SubstitutionFailure; 719 } 720 721 Decl *Param 722 = const_cast<Decl *>(ClassTemplate->getTemplateParameters()->getParam(I)); 723 if (isa<TemplateTypeParmDecl>(Param)) { 724 if (InstArg.getKind() != TemplateArgument::Type || 725 Context.getCanonicalType(InstArg.getAsType()) 726 != Context.getCanonicalType(TemplateArgs[I].getAsType())) { 727 Info.Param = cast<TemplateTypeParmDecl>(Param); 728 Info.FirstArg = TemplateArgs[I]; 729 Info.SecondArg = InstArg; 730 return TDK_NonDeducedMismatch; 731 } 732 } else if (NonTypeTemplateParmDecl *NTTP 733 = dyn_cast<NonTypeTemplateParmDecl>(Param)) { 734 QualType T = InstantiateType(NTTP->getType(), TemplateArgs, 735 NTTP->getLocation(), NTTP->getDeclName()); 736 if (T.isNull()) { 737 Info.Param = NTTP; 738 Info.FirstArg = TemplateArgs[I]; 739 Info.SecondArg = InstArg; 740 return TDK_NonDeducedMismatch; 741 } 742 743 if (InstArg.getKind() == TemplateArgument::Declaration || 744 InstArg.getKind() == TemplateArgument::Expression) { 745 // Turn the template argument into an expression, so that we can 746 // perform type checking on it and convert it to the type of the 747 // non-type template parameter. FIXME: Will this expression be 748 // leaked? It's hard to tell, since our ownership model for 749 // expressions in template arguments is so poor. 750 Expr *E = 0; 751 if (InstArg.getKind() == TemplateArgument::Declaration) { 752 NamedDecl *D = cast<NamedDecl>(InstArg.getAsDecl()); 753 QualType T = Context.OverloadTy; 754 if (ValueDecl *VD = dyn_cast<ValueDecl>(D)) 755 T = VD->getType().getNonReferenceType(); 756 E = new (Context) DeclRefExpr(D, T, InstArg.getLocation()); 757 } else { 758 E = InstArg.getAsExpr(); 759 } 760 761 // Check that the template argument can be used to initialize 762 // the corresponding template parameter. 763 if (CheckTemplateArgument(NTTP, T, E, InstArg)) { 764 // FIXME: This isn't precisely the problem, but since it 765 // can't actually happen in well-formed C++ we don't care at 766 // the moment. Revisit this when we have template argument 767 // deduction for function templates. 768 Info.Param = NTTP; 769 Info.FirstArg = TemplateArgs[I]; 770 Info.SecondArg = InstArg; 771 return TDK_NonDeducedMismatch; 772 } 773 } 774 775 switch (InstArg.getKind()) { 776 case TemplateArgument::Null: 777 assert(false && "Null template arguments cannot get here"); 778 return TDK_NonDeducedMismatch; 779 780 case TemplateArgument::Type: 781 assert(false && "Type/value mismatch"); 782 return TDK_NonDeducedMismatch; 783 784 case TemplateArgument::Integral: { 785 llvm::APSInt &Value = *InstArg.getAsIntegral(); 786 if (T->isIntegralType() || T->isEnumeralType()) { 787 QualType IntegerType = Context.getCanonicalType(T); 788 if (const EnumType *Enum = dyn_cast<EnumType>(IntegerType)) 789 IntegerType = Context.getCanonicalType( 790 Enum->getDecl()->getIntegerType()); 791 792 // Check that an unsigned parameter does not receive a negative 793 // value. 794 if (IntegerType->isUnsignedIntegerType() 795 && (Value.isSigned() && Value.isNegative())) { 796 Info.Param = NTTP; 797 Info.FirstArg = TemplateArgs[I]; 798 Info.SecondArg = InstArg; 799 return TDK_NonDeducedMismatch; 800 } 801 802 // Check for truncation. If the number of bits in the 803 // instantiated template argument exceeds what is allowed by 804 // the type, template argument deduction fails. 805 unsigned AllowedBits = Context.getTypeSize(IntegerType); 806 if (Value.getActiveBits() > AllowedBits) { 807 Info.Param = NTTP; 808 Info.FirstArg = TemplateArgs[I]; 809 Info.SecondArg = InstArg; 810 return TDK_NonDeducedMismatch; 811 } 812 813 if (Value.getBitWidth() != AllowedBits) 814 Value.extOrTrunc(AllowedBits); 815 Value.setIsSigned(IntegerType->isSignedIntegerType()); 816 817 // Check that the instantiated value is the same as the 818 // value provided as a template argument. 819 if (Value != *TemplateArgs[I].getAsIntegral()) { 820 Info.Param = NTTP; 821 Info.FirstArg = TemplateArgs[I]; 822 Info.SecondArg = InstArg; 823 return TDK_NonDeducedMismatch; 824 } 825 } else if (T->isPointerType() || T->isMemberPointerType()) { 826 // Deal with NULL pointers that are used to initialize 827 // pointer and pointer-to-member non-type template 828 // parameters (C++0x). 829 if (TemplateArgs[I].getAsDecl()) { 830 // Not a NULL declaration 831 Info.Param = NTTP; 832 Info.FirstArg = TemplateArgs[I]; 833 Info.SecondArg = InstArg; 834 return TDK_NonDeducedMismatch; 835 } 836 // Check that the integral value is 0, the NULL pointer 837 // constant. 838 if (Value != 0) { 839 Info.Param = NTTP; 840 Info.FirstArg = TemplateArgs[I]; 841 Info.SecondArg = InstArg; 842 return TDK_NonDeducedMismatch; 843 } 844 } else { 845 Info.Param = NTTP; 846 Info.FirstArg = TemplateArgs[I]; 847 Info.SecondArg = InstArg; 848 return TDK_NonDeducedMismatch; 849 } 850 851 break; 852 } 853 854 case TemplateArgument::Declaration: 855 if (Context.getCanonicalDecl(InstArg.getAsDecl()) 856 != Context.getCanonicalDecl(TemplateArgs[I].getAsDecl())) { 857 Info.Param = NTTP; 858 Info.FirstArg = TemplateArgs[I]; 859 Info.SecondArg = InstArg; 860 return TDK_NonDeducedMismatch; 861 } 862 break; 863 864 case TemplateArgument::Expression: 865 // FIXME: Check equality of expressions 866 break; 867 } 868 } else { 869 assert(isa<TemplateTemplateParmDecl>(Param)); 870 // FIXME: Check template template arguments 871 } 872 } 873 874 return TDK_Success; 875} 876