SemaTemplateDeduction.cpp revision 6f5e054b35aed3e4d22d4bc29bc74e5003dd2038 
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::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
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        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
533static Sema::TemplateDeductionResult
534DeduceTemplateArguments(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
609static Sema::TemplateDeductionResult
610DeduceTemplateArguments(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].
630Sema::TemplateDeductionResult
631Sema::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(Partial->getTemplateParameters(),
658                                      Deduced.size());
659  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
660    if (Deduced[I].isNull()) {
661      Decl *Param
662        = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I));
663      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
664        Info.Param = TTP;
665      else if (NonTypeTemplateParmDecl *NTTP
666                 = dyn_cast<NonTypeTemplateParmDecl>(Param))
667        Info.Param = NTTP;
668      else
669        Info.Param = cast<TemplateTemplateParmDecl>(Param);
670      return TDK_Incomplete;
671    }
672
673    Builder.Append(Deduced[I]);
674  }
675
676  // Form the template argument list from the deduced template arguments.
677  TemplateArgumentList *DeducedArgumentList
678    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/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/// \brief Perform template argument deduction from a function call
721/// (C++ [temp.deduct.call]).
722///
723/// \param FunctionTemplate the function template for which we are performing
724/// template argument deduction.
725///
726/// \param Args the function call arguments
727///
728/// \param NumArgs the number of arguments in Args
729///
730/// \param Specialization if template argument deduction was successful,
731/// this will be set to the function template specialization produced by
732/// template argument deduction.
733///
734/// \param Info the argument will be updated to provide additional information
735/// about template argument deduction.
736///
737/// \returns the result of template argument deduction.
738///
739/// FIXME: We will also need to pass in any explicitly-specified template
740/// arguments.
741Sema::TemplateDeductionResult
742Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
743                              Expr **Args, unsigned NumArgs,
744                              FunctionDecl *&Specialization,
745                              TemplateDeductionInfo &Info) {
746  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
747
748  // C++ [temp.deduct.call]p1:
749  //   Template argument deduction is done by comparing each function template
750  //   parameter type (call it P) with the type of the corresponding argument
751  //   of the call (call it A) as described below.
752  unsigned CheckArgs = NumArgs;
753  if (NumArgs < Function->getNumParams())
754    return TDK_TooFewArguments;
755  else if (NumArgs > Function->getNumParams()) {
756    const FunctionProtoType *Proto
757      = Function->getType()->getAsFunctionProtoType();
758    if (!Proto->isVariadic())
759      return TDK_TooManyArguments;
760
761    CheckArgs = Function->getNumParams();
762  }
763
764  SFINAETrap Trap(*this);
765  llvm::SmallVector<TemplateArgument, 4> Deduced;
766  Deduced.resize(FunctionTemplate->getTemplateParameters()->size());
767  TemplateParameterList *TemplateParams
768    = FunctionTemplate->getTemplateParameters();
769  for (unsigned I = 0; I != CheckArgs; ++I) {
770    QualType ParamType = Function->getParamDecl(I)->getType();
771    QualType ArgType = Args[I]->getType();
772
773    // C++ [temp.deduct.call]p2:
774    //   If P is not a reference type:
775    QualType CanonParamType = Context.getCanonicalType(ParamType);
776    if (!isa<ReferenceType>(CanonParamType)) {
777      //   - If A is an array type, the pointer type produced by the
778      //     array-to-pointer standard conversion (4.2) is used in place of
779      //     A for type deduction; otherwise,
780      if (ArgType->isArrayType())
781        ArgType = Context.getArrayDecayedType(ArgType);
782      //   - If A is a function type, the pointer type produced by the
783      //     function-to-pointer standard conversion (4.3) is used in place
784      //     of A for type deduction; otherwise,
785      else if (ArgType->isFunctionType())
786        ArgType = Context.getPointerType(ArgType);
787      else {
788        // - If A is a cv-qualified type, the top level cv-qualifiers of A’s
789        //   type are ignored for type deduction.
790        QualType CanonArgType = Context.getCanonicalType(ArgType);
791        if (CanonArgType.getCVRQualifiers())
792          ArgType = CanonArgType.getUnqualifiedType();
793      }
794    }
795
796    // C++0x [temp.deduct.call]p3:
797    //   If P is a cv-qualified type, the top level cv-qualifiers of P’s type
798    //   are ignored for type deduction.
799    if (CanonParamType.getCVRQualifiers())
800      ParamType = CanonParamType.getUnqualifiedType();
801    if (const ReferenceType *ParamRefType = ParamType->getAsReferenceType()) {
802      //   [...] If P is a reference type, the type referred to by P is used
803      //   for type deduction.
804      ParamType = ParamRefType->getPointeeType();
805
806      //   [...] If P is of the form T&&, where T is a template parameter, and
807      //   the argument is an lvalue, the type A& is used in place of A for
808      //   type deduction.
809      if (isa<RValueReferenceType>(ParamRefType) &&
810          ParamRefType->getAsTemplateTypeParmType() &&
811          Args[I]->isLvalue(Context) == Expr::LV_Valid)
812        ArgType = Context.getLValueReferenceType(ArgType);
813    }
814
815    // C++0x [temp.deduct.call]p4:
816    //   In general, the deduction process attempts to find template argument
817    //   values that will make the deduced A identical to A (after the type A
818    //   is transformed as described above). [...]
819    //
820    // FIXME: we'll pass down a flag to indicate when these cases may apply,
821    // and then deal with them in the code that deduces template
822    // arguments from a type.
823    if (TemplateDeductionResult Result
824        = ::DeduceTemplateArguments(Context, TemplateParams,
825                                    ParamType, ArgType, Info, Deduced))
826      return Result;
827
828    // FIXME: C++ [temp.deduct.call] paragraphs 6-9 deal with function
829    // pointer parameters.
830  }
831
832  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
833                             FunctionTemplate, Deduced.data(), Deduced.size());
834  if (Inst)
835    return TDK_InstantiationDepth;
836
837  // C++ [temp.deduct.type]p2:
838  //   [...] or if any template argument remains neither deduced nor
839  //   explicitly specified, template argument deduction fails.
840  TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size());
841  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
842    if (Deduced[I].isNull()) {
843      Decl *Param
844      = const_cast<Decl *>(TemplateParams->getParam(I));
845      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
846        Info.Param = TTP;
847      else if (NonTypeTemplateParmDecl *NTTP
848               = dyn_cast<NonTypeTemplateParmDecl>(Param))
849        Info.Param = NTTP;
850      else
851        Info.Param = cast<TemplateTemplateParmDecl>(Param);
852      return TDK_Incomplete;
853    }
854
855    Builder.Append(Deduced[I]);
856  }
857
858  // Form the template argument list from the deduced template arguments.
859  TemplateArgumentList *DeducedArgumentList
860    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
861  Info.reset(DeducedArgumentList);
862
863  // Substitute the deduced template arguments into the function template
864  // declaration to produce the function template specialization.
865  Specialization = cast_or_null<FunctionDecl>(
866                         InstantiateDecl(FunctionTemplate->getTemplatedDecl(),
867                                         FunctionTemplate->getDeclContext(),
868                                         *DeducedArgumentList));
869
870  if (!Specialization || Trap.hasErrorOccurred())
871    return TDK_SubstitutionFailure;
872
873  // Turn the specialization into an actual function template specialization.
874  Specialization->setFunctionTemplateSpecialization(Context,
875                                                    FunctionTemplate,
876                                                    Info.take());
877  return TDK_Success;
878}
879
880static void
881MarkDeducedTemplateParameters(Sema &SemaRef,
882                              const TemplateArgument &TemplateArg,
883                              llvm::SmallVectorImpl<bool> &Deduced);
884
885/// \brief Mark the template arguments that are deduced by the given
886/// expression.
887static void
888MarkDeducedTemplateParameters(const Expr *E,
889                              llvm::SmallVectorImpl<bool> &Deduced) {
890  const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
891  if (!E)
892    return;
893
894  const NonTypeTemplateParmDecl *NTTP
895    = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
896  if (!NTTP)
897    return;
898
899  Deduced[NTTP->getIndex()] = true;
900}
901
902/// \brief Mark the template parameters that are deduced by the given
903/// type.
904static void
905MarkDeducedTemplateParameters(Sema &SemaRef, QualType T,
906                              llvm::SmallVectorImpl<bool> &Deduced) {
907  // Non-dependent types have nothing deducible
908  if (!T->isDependentType())
909    return;
910
911  T = SemaRef.Context.getCanonicalType(T);
912  switch (T->getTypeClass()) {
913  case Type::ExtQual:
914    MarkDeducedTemplateParameters(SemaRef,
915                              QualType(cast<ExtQualType>(T)->getBaseType(), 0),
916                                  Deduced);
917    break;
918
919  case Type::Pointer:
920    MarkDeducedTemplateParameters(SemaRef,
921                                  cast<PointerType>(T)->getPointeeType(),
922                                  Deduced);
923    break;
924
925  case Type::BlockPointer:
926    MarkDeducedTemplateParameters(SemaRef,
927                                  cast<BlockPointerType>(T)->getPointeeType(),
928                                  Deduced);
929    break;
930
931  case Type::LValueReference:
932  case Type::RValueReference:
933    MarkDeducedTemplateParameters(SemaRef,
934                                  cast<ReferenceType>(T)->getPointeeType(),
935                                  Deduced);
936    break;
937
938  case Type::MemberPointer: {
939    const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
940    MarkDeducedTemplateParameters(SemaRef, MemPtr->getPointeeType(), Deduced);
941    MarkDeducedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
942                                  Deduced);
943    break;
944  }
945
946  case Type::DependentSizedArray:
947    MarkDeducedTemplateParameters(cast<DependentSizedArrayType>(T)->getSizeExpr(),
948                                  Deduced);
949    // Fall through to check the element type
950
951  case Type::ConstantArray:
952  case Type::IncompleteArray:
953    MarkDeducedTemplateParameters(SemaRef,
954                                  cast<ArrayType>(T)->getElementType(),
955                                  Deduced);
956    break;
957
958  case Type::Vector:
959  case Type::ExtVector:
960    MarkDeducedTemplateParameters(SemaRef,
961                                  cast<VectorType>(T)->getElementType(),
962                                  Deduced);
963    break;
964
965  case Type::DependentSizedExtVector: {
966    const DependentSizedExtVectorType *VecType
967      = cast<DependentSizedExtVectorType>(T);
968    MarkDeducedTemplateParameters(SemaRef, VecType->getElementType(), Deduced);
969    MarkDeducedTemplateParameters(VecType->getSizeExpr(), Deduced);
970    break;
971  }
972
973  case Type::FunctionProto: {
974    const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
975    MarkDeducedTemplateParameters(SemaRef, Proto->getResultType(), Deduced);
976    for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
977      MarkDeducedTemplateParameters(SemaRef, Proto->getArgType(I), Deduced);
978    break;
979  }
980
981  case Type::TemplateTypeParm:
982    Deduced[cast<TemplateTypeParmType>(T)->getIndex()] = true;
983    break;
984
985  case Type::TemplateSpecialization: {
986    const TemplateSpecializationType *Spec
987      = cast<TemplateSpecializationType>(T);
988    if (TemplateDecl *Template = Spec->getTemplateName().getAsTemplateDecl())
989      if (TemplateTemplateParmDecl *TTP
990            = dyn_cast<TemplateTemplateParmDecl>(Template))
991        Deduced[TTP->getIndex()] = true;
992
993      for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
994        MarkDeducedTemplateParameters(SemaRef, Spec->getArg(I), Deduced);
995
996    break;
997  }
998
999  // None of these types have any deducible parts.
1000  case Type::Builtin:
1001  case Type::FixedWidthInt:
1002  case Type::Complex:
1003  case Type::VariableArray:
1004  case Type::FunctionNoProto:
1005  case Type::Record:
1006  case Type::Enum:
1007  case Type::Typename:
1008  case Type::ObjCInterface:
1009  case Type::ObjCQualifiedInterface:
1010  case Type::ObjCObjectPointer:
1011#define TYPE(Class, Base)
1012#define ABSTRACT_TYPE(Class, Base)
1013#define DEPENDENT_TYPE(Class, Base)
1014#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
1015#include "clang/AST/TypeNodes.def"
1016    break;
1017  }
1018}
1019
1020/// \brief Mark the template parameters that are deduced by this
1021/// template argument.
1022static void
1023MarkDeducedTemplateParameters(Sema &SemaRef,
1024                              const TemplateArgument &TemplateArg,
1025                              llvm::SmallVectorImpl<bool> &Deduced) {
1026  switch (TemplateArg.getKind()) {
1027  case TemplateArgument::Null:
1028  case TemplateArgument::Integral:
1029    break;
1030
1031  case TemplateArgument::Type:
1032    MarkDeducedTemplateParameters(SemaRef, TemplateArg.getAsType(), Deduced);
1033    break;
1034
1035  case TemplateArgument::Declaration:
1036    if (TemplateTemplateParmDecl *TTP
1037        = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl()))
1038      Deduced[TTP->getIndex()] = true;
1039    break;
1040
1041  case TemplateArgument::Expression:
1042    MarkDeducedTemplateParameters(TemplateArg.getAsExpr(), Deduced);
1043    break;
1044  case TemplateArgument::Pack:
1045    assert(0 && "FIXME: Implement!");
1046    break;
1047  }
1048}
1049
1050/// \brief Mark the template parameters can be deduced by the given
1051/// template argument list.
1052///
1053/// \param TemplateArgs the template argument list from which template
1054/// parameters will be deduced.
1055///
1056/// \param Deduced a bit vector whose elements will be set to \c true
1057/// to indicate when the corresponding template parameter will be
1058/// deduced.
1059void
1060Sema::MarkDeducedTemplateParameters(const TemplateArgumentList &TemplateArgs,
1061                                    llvm::SmallVectorImpl<bool> &Deduced) {
1062  for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
1063    ::MarkDeducedTemplateParameters(*this, TemplateArgs[I], Deduced);
1064}
1065