lib/Sema/SemaTemplateDeduction.cpp

   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"
  21 using namespace clang;
  22
  23 static Sema::TemplateDeductionResult
  24 DeduceTemplateArguments(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.
  34 static 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.
  46 static Sema::TemplateDeductionResult
  47 DeduceNonTypeTemplateArgument(ASTContext &Context,
  48                               NonTypeTemplateParmDecl *NTTP,
  49                               llvm::APSInt 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     QualType T = NTTP->getType();
  57
  58     // FIXME: Make sure we didn't overflow our data type!
  59     unsigned AllowedBits = Context.getTypeSize(T);
  60     if (Value.getBitWidth() != AllowedBits)
  61       Value.extOrTrunc(AllowedBits);
  62     Value.setIsSigned(T->isSignedIntegerType());
  63
  64     Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(), Value, T);
  65     return Sema::TDK_Success;
  66   }
  67
  68   assert(Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral);
  69
  70   // If the template argument was previously deduced to a negative value,
  71   // then our deduction fails.
  72   const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral();
  73   if (PrevValuePtr->isNegative()) {
  74     Info.Param = NTTP;
  75     Info.FirstArg = Deduced[NTTP->getIndex()];
  76     Info.SecondArg = TemplateArgument(SourceLocation(), Value, NTTP->getType());
  77     return Sema::TDK_Inconsistent;
  78   }
  79
  80   llvm::APSInt PrevValue = *PrevValuePtr;
  81   if (Value.getBitWidth() > PrevValue.getBitWidth())
  82     PrevValue.zext(Value.getBitWidth());
  83   else if (Value.getBitWidth() < PrevValue.getBitWidth())
  84     Value.zext(PrevValue.getBitWidth());
  85
  86   if (Value != PrevValue) {
  87     Info.Param = NTTP;
  88     Info.FirstArg = Deduced[NTTP->getIndex()];
  89     Info.SecondArg = TemplateArgument(SourceLocation(), Value, 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
 101 static Sema::TemplateDeductionResult
 102 DeduceNonTypeTemplateArgument(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
 129 static Sema::TemplateDeductionResult
 130 DeduceTemplateArguments(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
 159 static Sema::TemplateDeductionResult
 160 DeduceTemplateArguments(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         llvm::APSInt Size(ConstantArrayArg->getSize());
 334         return DeduceNonTypeTemplateArgument(Context, NTTP, Size,
 335                                              Info, Deduced);
 336       }
 337       if (const DependentSizedArrayType *DependentArrayArg
 338             = dyn_cast<DependentSizedArrayType>(ArrayArg))
 339         return DeduceNonTypeTemplateArgument(Context, NTTP,
 340                                              DependentArrayArg->getSizeExpr(),
 341                                              Info, Deduced);
 342
 343       // Incomplete type does not match a dependently-sized array type
 344       return Sema::TDK_NonDeducedMismatch;
 345     }
 346
 347     //     type(*)(T)
 348     //     T(*)()
 349     //     T(*)(T)
 350     case Type::FunctionProto: {
 351       const FunctionProtoType *FunctionProtoArg =
 352         dyn_cast<FunctionProtoType>(Arg);
 353       if (!FunctionProtoArg)
 354         return Sema::TDK_NonDeducedMismatch;
 355
 356       const FunctionProtoType *FunctionProtoParam =
 357         cast<FunctionProtoType>(Param);
 358
 359       if (FunctionProtoParam->getTypeQuals() !=
 360           FunctionProtoArg->getTypeQuals())
 361         return Sema::TDK_NonDeducedMismatch;
 362
 363       if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs())
 364         return Sema::TDK_NonDeducedMismatch;
 365
 366       if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
 367         return Sema::TDK_NonDeducedMismatch;
 368
 369       // Check return types.
 370       if (Sema::TemplateDeductionResult Result
 371             = DeduceTemplateArguments(Context, TemplateParams,
 372                                       FunctionProtoParam->getResultType(),
 373                                       FunctionProtoArg->getResultType(),
 374                                       Info, Deduced))
 375         return Result;
 376
 377       for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) {
 378         // Check argument types.
 379         if (Sema::TemplateDeductionResult Result
 380               = DeduceTemplateArguments(Context, TemplateParams,
 381                                         FunctionProtoParam->getArgType(I),
 382                                         FunctionProtoArg->getArgType(I),
 383                                         Info, Deduced))
 384           return Result;
 385       }
 386
 387       return Sema::TDK_Success;
 388     }
 389
 390     //     template-name<T> (wheretemplate-name refers to a class template)
 391     //     template-name<i>
 392     //     TT<T> (TODO)
 393     //     TT<i> (TODO)
 394     //     TT<> (TODO)
 395     case Type::TemplateSpecialization: {
 396       const TemplateSpecializationType *SpecParam
 397         = cast<TemplateSpecializationType>(Param);
 398
 399       // Check whether the template argument is a dependent template-id.
 400       // FIXME: This is untested code; it can be tested when we implement
 401       // partial ordering of class template partial specializations.
 402       if (const TemplateSpecializationType *SpecArg
 403             = dyn_cast<TemplateSpecializationType>(Arg)) {
 404         // Perform template argument deduction for the template name.
 405         if (Sema::TemplateDeductionResult Result
 406               = DeduceTemplateArguments(Context,
 407                                         SpecParam->getTemplateName(),
 408                                         SpecArg->getTemplateName(),
 409                                         Info, Deduced))
 410           return Result;
 411
 412         unsigned NumArgs = SpecParam->getNumArgs();
 413
 414         // FIXME: When one of the template-names refers to a
 415         // declaration with default template arguments, do we need to
 416         // fill in those default template arguments here? Most likely,
 417         // the answer is "yes", but I don't see any references. This
 418         // issue may be resolved elsewhere, because we may want to
 419         // instantiate default template arguments when
 420         if (SpecArg->getNumArgs() != NumArgs)
 421           return Sema::TDK_NonDeducedMismatch;
 422
 423         // Perform template argument deduction on each template
 424         // argument.
 425         for (unsigned I = 0; I != NumArgs; ++I)
 426           if (Sema::TemplateDeductionResult Result
 427                 = DeduceTemplateArguments(Context, TemplateParams,
 428                                           SpecParam->getArg(I),
 429                                           SpecArg->getArg(I),
 430                                           Info, Deduced))
 431             return Result;
 432
 433         return Sema::TDK_Success;
 434       }
 435
 436       // If the argument type is a class template specialization, we
 437       // perform template argument deduction using its template
 438       // arguments.
 439       const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
 440       if (!RecordArg)
 441         return Sema::TDK_NonDeducedMismatch;
 442
 443       ClassTemplateSpecializationDecl *SpecArg
 444         = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
 445       if (!SpecArg)
 446         return Sema::TDK_NonDeducedMismatch;
 447
 448       // Perform template argument deduction for the template name.
 449       if (Sema::TemplateDeductionResult Result
 450             = DeduceTemplateArguments(Context,
 451                                       SpecParam->getTemplateName(),
 452                               TemplateName(SpecArg->getSpecializedTemplate()),
 453                                       Info, Deduced))
 454           return Result;
 455
 456       // FIXME: Can the # of arguments in the parameter and the argument differ?
 457       unsigned NumArgs = SpecParam->getNumArgs();
 458       const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs();
 459       if (NumArgs != ArgArgs.size())
 460         return Sema::TDK_NonDeducedMismatch;
 461
 462       for (unsigned I = 0; I != NumArgs; ++I)
 463         if (Sema::TemplateDeductionResult Result
 464               = DeduceTemplateArguments(Context, TemplateParams,
 465                                         SpecParam->getArg(I),
 466                                         ArgArgs.get(I),
 467                                         Info, Deduced))
 468           return Result;
 469
 470       return Sema::TDK_Success;
 471     }
 472
 473     //     T type::*
 474     //     T T::*
 475     //     T (type::*)()
 476     //     type (T::*)()
 477     //     type (type::*)(T)
 478     //     type (T::*)(T)
 479     //     T (type::*)(T)
 480     //     T (T::*)()
 481     //     T (T::*)(T)
 482     case Type::MemberPointer: {
 483       const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
 484       const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
 485       if (!MemPtrArg)
 486         return Sema::TDK_NonDeducedMismatch;
 487
 488       if (Sema::TemplateDeductionResult Result
 489             = DeduceTemplateArguments(Context, TemplateParams,
 490                                       MemPtrParam->getPointeeType(),
 491                                       MemPtrArg->getPointeeType(),
 492                                       Info, Deduced))
 493         return Result;
 494
 495       return DeduceTemplateArguments(Context, TemplateParams,
 496                                      QualType(MemPtrParam->getClass(), 0),
 497                                      QualType(MemPtrArg->getClass(), 0),
 498                                      Info, Deduced);
 499     }
 500
 501     //     (clang extension)
 502     //
 503     //     type(^)(T)
 504     //     T(^)()
 505     //     T(^)(T)
 506     case Type::BlockPointer: {
 507       const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
 508       const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
 509
 510       if (!BlockPtrArg)
 511         return Sema::TDK_NonDeducedMismatch;
 512
 513       return DeduceTemplateArguments(Context, TemplateParams,
 514                                      BlockPtrParam->getPointeeType(),
 515                                      BlockPtrArg->getPointeeType(), Info,
 516                                      Deduced);
 517     }
 518
 519     case Type::TypeOfExpr:
 520     case Type::TypeOf:
 521     case Type::Typename:
 522       // No template argument deduction for these types
 523       return Sema::TDK_Success;
 524
 525     default:
 526       break;
 527   }
 528
 529   // FIXME: Many more cases to go (to go).
 530   return Sema::TDK_NonDeducedMismatch;
 531 }
 532
 533 static Sema::TemplateDeductionResult
 534 DeduceTemplateArguments(ASTContext &Context,
 535                         TemplateParameterList *TemplateParams,
 536                         const TemplateArgument &Param,
 537                         const TemplateArgument &Arg,
 538                         Sema::TemplateDeductionInfo &Info,
 539                         llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
 540   switch (Param.getKind()) {
 541   case TemplateArgument::Null:
 542     assert(false && "Null template argument in parameter list");
 543     break;
 544
 545   case TemplateArgument::Type:
 546     assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
 547     return DeduceTemplateArguments(Context, TemplateParams,
 548                                    Param.getAsType(),
 549                                    Arg.getAsType(), Info, Deduced);
 550
 551   case TemplateArgument::Declaration:
 552     // FIXME: Implement this check
 553     assert(false && "Unimplemented template argument deduction case");
 554     Info.FirstArg = Param;
 555     Info.SecondArg = Arg;
 556     return Sema::TDK_NonDeducedMismatch;
 557
 558   case TemplateArgument::Integral:
 559     if (Arg.getKind() == TemplateArgument::Integral) {
 560       // FIXME: Zero extension + sign checking here?
 561       if (*Param.getAsIntegral() == *Arg.getAsIntegral())
 562         return Sema::TDK_Success;
 563
 564       Info.FirstArg = Param;
 565       Info.SecondArg = Arg;
 566       return Sema::TDK_NonDeducedMismatch;
 567     }
 568
 569     if (Arg.getKind() == TemplateArgument::Expression) {
 570       Info.FirstArg = Param;
 571       Info.SecondArg = Arg;
 572       return Sema::TDK_NonDeducedMismatch;
 573     }
 574
 575     assert(false && "Type/value mismatch");
 576     Info.FirstArg = Param;
 577     Info.SecondArg = Arg;
 578     return Sema::TDK_NonDeducedMismatch;
 579
 580   case TemplateArgument::Expression: {
 581     if (NonTypeTemplateParmDecl *NTTP
 582           = getDeducedParameterFromExpr(Param.getAsExpr())) {
 583       if (Arg.getKind() == TemplateArgument::Integral)
 584         // FIXME: Sign problems here
 585         return DeduceNonTypeTemplateArgument(Context, NTTP,
 586                                              *Arg.getAsIntegral(),
 587                                              Info, Deduced);
 588       if (Arg.getKind() == TemplateArgument::Expression)
 589         return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
 590                                              Info, Deduced);
 591
 592       assert(false && "Type/value mismatch");
 593       Info.FirstArg = Param;
 594       Info.SecondArg = Arg;
 595       return Sema::TDK_NonDeducedMismatch;
 596     }
 597
 598     // Can't deduce anything, but that's okay.
 599     return Sema::TDK_Success;
 600   }
 601   case TemplateArgument::Pack:
 602     assert(0 && "FIXME: Implement!");
 603     break;
 604   }
 605
 606   return Sema::TDK_Success;
 607 }
 608
 609 static Sema::TemplateDeductionResult
 610 DeduceTemplateArguments(ASTContext &Context,
 611                         TemplateParameterList *TemplateParams,
 612                         const TemplateArgumentList &ParamList,
 613                         const TemplateArgumentList &ArgList,
 614                         Sema::TemplateDeductionInfo &Info,
 615                         llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
 616   assert(ParamList.size() == ArgList.size());
 617   for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
 618     if (Sema::TemplateDeductionResult Result
 619           = DeduceTemplateArguments(Context, TemplateParams,
 620                                     ParamList[I], ArgList[I],
 621                                     Info, Deduced))
 622       return Result;
 623   }
 624   return Sema::TDK_Success;
 625 }
 626
 627 /// \brief Perform template argument deduction to determine whether
 628 /// the given template arguments match the given class template
 629 /// partial specialization per C++ [temp.class.spec.match].
 630 Sema::TemplateDeductionResult
 631 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
 632                               const TemplateArgumentList &TemplateArgs,
 633                               TemplateDeductionInfo &Info) {
 634   // C++ [temp.class.spec.match]p2:
 635   //   A partial specialization matches a given actual template
 636   //   argument list if the template arguments of the partial
 637   //   specialization can be deduced from the actual template argument
 638   //   list (14.8.2).
 639   SFINAETrap Trap(*this);
 640   llvm::SmallVector<TemplateArgument, 4> Deduced;
 641   Deduced.resize(Partial->getTemplateParameters()->size());
 642   if (TemplateDeductionResult Result
 643         = ::DeduceTemplateArguments(Context,
 644                                     Partial->getTemplateParameters(),
 645                                     Partial->getTemplateArgs(),
 646                                     TemplateArgs, Info, Deduced))
 647     return Result;
 648
 649   InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
 650                              Deduced.data(), Deduced.size());
 651   if (Inst)
 652     return TDK_InstantiationDepth;
 653
 654   // C++ [temp.deduct.type]p2:
 655   //   [...] or if any template argument remains neither deduced nor
 656   //   explicitly specified, template argument deduction fails.
 657   TemplateArgumentListBuilder Builder(Context);
 658   for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
 659     if (Deduced[I].isNull()) {
 660       Decl *Param
 661         = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I));
 662       if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
 663         Info.Param = TTP;
 664       else if (NonTypeTemplateParmDecl *NTTP
 665                  = dyn_cast<NonTypeTemplateParmDecl>(Param))
 666         Info.Param = NTTP;
 667       else
 668         Info.Param = cast<TemplateTemplateParmDecl>(Param);
 669       return TDK_Incomplete;
 670     }
 671
 672     Builder.push_back(Deduced[I]);
 673   }
 674
 675   // Form the template argument list from the deduced template arguments.
 676   TemplateArgumentList *DeducedArgumentList
 677     = new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true,
 678                                          /*FlattenArgs=*/true);
 679   Info.reset(DeducedArgumentList);
 680
 681   // Substitute the deduced template arguments into the template
 682   // arguments of the class template partial specialization, and
 683   // verify that the instantiated template arguments are both valid
 684   // and are equivalent to the template arguments originally provided
 685   // to the class template.
 686   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
 687   const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs();
 688   for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) {
 689     Decl *Param = const_cast<Decl *>(
 690                     ClassTemplate->getTemplateParameters()->getParam(I));
 691     if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) {
 692       TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I],
 693                                              *DeducedArgumentList);
 694       if (InstArg.getKind() != TemplateArgument::Type) {
 695         Info.Param = TTP;
 696         Info.FirstArg = PartialTemplateArgs[I];
 697         return TDK_SubstitutionFailure;
 698       }
 699
 700       if (Context.getCanonicalType(InstArg.getAsType())
 701             != Context.getCanonicalType(TemplateArgs[I].getAsType())) {
 702         Info.Param = TTP;
 703         Info.FirstArg = TemplateArgs[I];
 704         Info.SecondArg = InstArg;
 705         return TDK_NonDeducedMismatch;
 706       }
 707
 708       continue;
 709     }
 710
 711     // FIXME: Check template template arguments?
 712   }
 713
 714   if (Trap.hasErrorOccurred())
 715     return TDK_SubstitutionFailure;
 716
 717   return TDK_Success;
 718 }
 719
 720 static void
 721 MarkDeducedTemplateParameters(Sema &SemaRef,
 722                               const TemplateArgument &TemplateArg,
 723                               llvm::SmallVectorImpl<bool> &Deduced);
 724
 725 /// \brief Mark the template arguments that are deduced by the given
 726 /// expression.
 727 static void
 728 MarkDeducedTemplateParameters(const Expr *E,
 729                               llvm::SmallVectorImpl<bool> &Deduced) {
 730   const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
 731   if (!E)
 732     return;
 733
 734   const NonTypeTemplateParmDecl *NTTP
 735     = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
 736   if (!NTTP)
 737     return;
 738
 739   Deduced[NTTP->getIndex()] = true;
 740 }
 741
 742 /// \brief Mark the template parameters that are deduced by the given
 743 /// type.
 744 static void
 745 MarkDeducedTemplateParameters(Sema &SemaRef, QualType T,
 746                               llvm::SmallVectorImpl<bool> &Deduced) {
 747   // Non-dependent types have nothing deducible
 748   if (!T->isDependentType())
 749     return;
 750
 751   T = SemaRef.Context.getCanonicalType(T);
 752   switch (T->getTypeClass()) {
 753   case Type::ExtQual:
 754     MarkDeducedTemplateParameters(SemaRef,
 755                               QualType(cast<ExtQualType>(T)->getBaseType(), 0),
 756                                   Deduced);
 757     break;
 758
 759   case Type::Pointer:
 760     MarkDeducedTemplateParameters(SemaRef,
 761                                   cast<PointerType>(T)->getPointeeType(),
 762                                   Deduced);
 763     break;
 764
 765   case Type::BlockPointer:
 766     MarkDeducedTemplateParameters(SemaRef,
 767                                   cast<BlockPointerType>(T)->getPointeeType(),
 768                                   Deduced);
 769     break;
 770
 771   case Type::LValueReference:
 772   case Type::RValueReference:
 773     MarkDeducedTemplateParameters(SemaRef,
 774                                   cast<ReferenceType>(T)->getPointeeType(),
 775                                   Deduced);
 776     break;
 777
 778   case Type::MemberPointer: {
 779     const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
 780     MarkDeducedTemplateParameters(SemaRef, MemPtr->getPointeeType(), Deduced);
 781     MarkDeducedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
 782                                   Deduced);
 783     break;
 784   }
 785
 786   case Type::DependentSizedArray:
 787     MarkDeducedTemplateParameters(cast<DependentSizedArrayType>(T)->getSizeExpr(),
 788                                   Deduced);
 789     // Fall through to check the element type
 790
 791   case Type::ConstantArray:
 792   case Type::IncompleteArray:
 793     MarkDeducedTemplateParameters(SemaRef,
 794                                   cast<ArrayType>(T)->getElementType(),
 795                                   Deduced);
 796     break;
 797
 798   case Type::Vector:
 799   case Type::ExtVector:
 800     MarkDeducedTemplateParameters(SemaRef,
 801                                   cast<VectorType>(T)->getElementType(),
 802                                   Deduced);
 803     break;
 804
 805   case Type::DependentSizedExtVector: {
 806     const DependentSizedExtVectorType *VecType
 807       = cast<DependentSizedExtVectorType>(T);
 808     MarkDeducedTemplateParameters(SemaRef, VecType->getElementType(), Deduced);
 809     MarkDeducedTemplateParameters(VecType->getSizeExpr(), Deduced);
 810     break;
 811   }
 812
 813   case Type::FunctionProto: {
 814     const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
 815     MarkDeducedTemplateParameters(SemaRef, Proto->getResultType(), Deduced);
 816     for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
 817       MarkDeducedTemplateParameters(SemaRef, Proto->getArgType(I), Deduced);
 818     break;
 819   }
 820
 821   case Type::TemplateTypeParm:
 822     Deduced[cast<TemplateTypeParmType>(T)->getIndex()] = true;
 823     break;
 824
 825   case Type::TemplateSpecialization: {
 826     const TemplateSpecializationType *Spec
 827       = cast<TemplateSpecializationType>(T);
 828     if (TemplateDecl *Template = Spec->getTemplateName().getAsTemplateDecl())
 829       if (TemplateTemplateParmDecl *TTP
 830             = dyn_cast<TemplateTemplateParmDecl>(Template))
 831         Deduced[TTP->getIndex()] = true;
 832
 833       for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
 834         MarkDeducedTemplateParameters(SemaRef, Spec->getArg(I), Deduced);
 835
 836     break;
 837   }
 838
 839   // None of these types have any deducible parts.
 840   case Type::Builtin:
 841   case Type::FixedWidthInt:
 842   case Type::Complex:
 843   case Type::VariableArray:
 844   case Type::FunctionNoProto:
 845   case Type::Record:
 846   case Type::Enum:
 847   case Type::Typename:
 848   case Type::ObjCInterface:
 849   case Type::ObjCQualifiedInterface:
 850   case Type::ObjCObjectPointer:
 851 #define TYPE(Class, Base)
 852 #define ABSTRACT_TYPE(Class, Base)
 853 #define DEPENDENT_TYPE(Class, Base)
 854 #define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
 855 #include "clang/AST/TypeNodes.def"
 856     break;
 857   }
 858 }
 859
 860 /// \brief Mark the template parameters that are deduced by this
 861 /// template argument.
 862 static void
 863 MarkDeducedTemplateParameters(Sema &SemaRef,
 864                               const TemplateArgument &TemplateArg,
 865                               llvm::SmallVectorImpl<bool> &Deduced) {
 866   switch (TemplateArg.getKind()) {
 867   case TemplateArgument::Null:
 868   case TemplateArgument::Integral:
 869     break;
 870
 871   case TemplateArgument::Type:
 872     MarkDeducedTemplateParameters(SemaRef, TemplateArg.getAsType(), Deduced);
 873     break;
 874
 875   case TemplateArgument::Declaration:
 876     if (TemplateTemplateParmDecl *TTP
 877         = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl()))
 878       Deduced[TTP->getIndex()] = true;
 879     break;
 880
 881   case TemplateArgument::Expression:
 882     MarkDeducedTemplateParameters(TemplateArg.getAsExpr(), Deduced);
 883     break;
 884   case TemplateArgument::Pack:
 885     assert(0 && "FIXME: Implement!");
 886     break;
 887   }
 888 }
 889
 890 /// \brief Mark the template parameters can be deduced by the given
 891 /// template argument list.
 892 ///
 893 /// \param TemplateArgs the template argument list from which template
 894 /// parameters will be deduced.
 895 ///
 896 /// \param Deduced a bit vector whose elements will be set to \c true
 897 /// to indicate when the corresponding template parameter will be
 898 /// deduced.
 899 void
 900 Sema::MarkDeducedTemplateParameters(const TemplateArgumentList &TemplateArgs,
 901                                     llvm::SmallVectorImpl<bool> &Deduced) {
 902   for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
 903     ::MarkDeducedTemplateParameters(*this, TemplateArgs[I], Deduced);
 904 }