SemaTemplateDeduction.cpp revision 97fbaa2a38804268a024f1a104b43fcf8b4411b0 
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
22namespace clang {
23  /// \brief Various flags that control template argument deduction.
24  ///
25  /// These flags can be bitwise-OR'd together.
26  enum TemplateDeductionFlags {
27    /// \brief No template argument deduction flags, which indicates the
28    /// strictest results for template argument deduction (as used for, e.g.,
29    /// matching class template partial specializations).
30    TDF_None = 0,
31    /// \brief Within template argument deduction from a function call, we are
32    /// matching with a parameter type for which the original parameter was
33    /// a reference.
34    TDF_ParamWithReferenceType = 0x1,
35    /// \brief Within template argument deduction from a function call, we
36    /// are matching in a case where we ignore cv-qualifiers.
37    TDF_IgnoreQualifiers = 0x02,
38    /// \brief Within template argument deduction from a function call,
39    /// we are matching in a case where we can perform template argument
40    /// deduction from a template-id of a derived class of the argument type.
41    TDF_DerivedClass = 0x04
42  };
43}
44
45using namespace clang;
46
47static Sema::TemplateDeductionResult
48DeduceTemplateArguments(ASTContext &Context,
49                        TemplateParameterList *TemplateParams,
50                        const TemplateArgument &Param,
51                        const TemplateArgument &Arg,
52                        Sema::TemplateDeductionInfo &Info,
53                        llvm::SmallVectorImpl<TemplateArgument> &Deduced);
54
55/// \brief If the given expression is of a form that permits the deduction
56/// of a non-type template parameter, return the declaration of that
57/// non-type template parameter.
58static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
59  if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
60    E = IC->getSubExpr();
61
62  if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
63    return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
64
65  return 0;
66}
67
68/// \brief Deduce the value of the given non-type template parameter
69/// from the given constant.
70static Sema::TemplateDeductionResult
71DeduceNonTypeTemplateArgument(ASTContext &Context,
72                              NonTypeTemplateParmDecl *NTTP,
73                              llvm::APSInt Value,
74                              Sema::TemplateDeductionInfo &Info,
75                              llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
76  assert(NTTP->getDepth() == 0 &&
77         "Cannot deduce non-type template argument with depth > 0");
78
79  if (Deduced[NTTP->getIndex()].isNull()) {
80    QualType T = NTTP->getType();
81
82    // FIXME: Make sure we didn't overflow our data type!
83    unsigned AllowedBits = Context.getTypeSize(T);
84    if (Value.getBitWidth() != AllowedBits)
85      Value.extOrTrunc(AllowedBits);
86    Value.setIsSigned(T->isSignedIntegerType());
87
88    Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(), Value, T);
89    return Sema::TDK_Success;
90  }
91
92  assert(Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral);
93
94  // If the template argument was previously deduced to a negative value,
95  // then our deduction fails.
96  const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral();
97  if (PrevValuePtr->isNegative()) {
98    Info.Param = NTTP;
99    Info.FirstArg = Deduced[NTTP->getIndex()];
100    Info.SecondArg = TemplateArgument(SourceLocation(), Value, NTTP->getType());
101    return Sema::TDK_Inconsistent;
102  }
103
104  llvm::APSInt PrevValue = *PrevValuePtr;
105  if (Value.getBitWidth() > PrevValue.getBitWidth())
106    PrevValue.zext(Value.getBitWidth());
107  else if (Value.getBitWidth() < PrevValue.getBitWidth())
108    Value.zext(PrevValue.getBitWidth());
109
110  if (Value != PrevValue) {
111    Info.Param = NTTP;
112    Info.FirstArg = Deduced[NTTP->getIndex()];
113    Info.SecondArg = TemplateArgument(SourceLocation(), Value, NTTP->getType());
114    return Sema::TDK_Inconsistent;
115  }
116
117  return Sema::TDK_Success;
118}
119
120/// \brief Deduce the value of the given non-type template parameter
121/// from the given type- or value-dependent expression.
122///
123/// \returns true if deduction succeeded, false otherwise.
124
125static Sema::TemplateDeductionResult
126DeduceNonTypeTemplateArgument(ASTContext &Context,
127                              NonTypeTemplateParmDecl *NTTP,
128                              Expr *Value,
129                              Sema::TemplateDeductionInfo &Info,
130                           llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
131  assert(NTTP->getDepth() == 0 &&
132         "Cannot deduce non-type template argument with depth > 0");
133  assert((Value->isTypeDependent() || Value->isValueDependent()) &&
134         "Expression template argument must be type- or value-dependent.");
135
136  if (Deduced[NTTP->getIndex()].isNull()) {
137    // FIXME: Clone the Value?
138    Deduced[NTTP->getIndex()] = TemplateArgument(Value);
139    return Sema::TDK_Success;
140  }
141
142  if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) {
143    // Okay, we deduced a constant in one case and a dependent expression
144    // in another case. FIXME: Later, we will check that instantiating the
145    // dependent expression gives us the constant value.
146    return Sema::TDK_Success;
147  }
148
149  // FIXME: Compare the expressions for equality!
150  return Sema::TDK_Success;
151}
152
153static Sema::TemplateDeductionResult
154DeduceTemplateArguments(ASTContext &Context,
155                        TemplateName Param,
156                        TemplateName Arg,
157                        Sema::TemplateDeductionInfo &Info,
158                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
159  // FIXME: Implement template argument deduction for template
160  // template parameters.
161
162  // FIXME: this routine does not have enough information to produce
163  // good diagnostics.
164
165  TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
166  TemplateDecl *ArgDecl = Arg.getAsTemplateDecl();
167
168  if (!ParamDecl || !ArgDecl) {
169    // FIXME: fill in Info.Param/Info.FirstArg
170    return Sema::TDK_Inconsistent;
171  }
172
173  ParamDecl = cast<TemplateDecl>(ParamDecl->getCanonicalDecl());
174  ArgDecl = cast<TemplateDecl>(ArgDecl->getCanonicalDecl());
175  if (ParamDecl != ArgDecl) {
176    // FIXME: fill in Info.Param/Info.FirstArg
177    return Sema::TDK_Inconsistent;
178  }
179
180  return Sema::TDK_Success;
181}
182
183/// \brief Deduce the template arguments by comparing the template parameter
184/// type (which is a template-id) with the template argument type.
185///
186/// \param Context the AST context in which this deduction occurs.
187///
188/// \param TemplateParams the template parameters that we are deducing
189///
190/// \param Param the parameter type
191///
192/// \param Arg the argument type
193///
194/// \param Info information about the template argument deduction itself
195///
196/// \param Deduced the deduced template arguments
197///
198/// \returns the result of template argument deduction so far. Note that a
199/// "success" result means that template argument deduction has not yet failed,
200/// but it may still fail, later, for other reasons.
201static Sema::TemplateDeductionResult
202DeduceTemplateArguments(ASTContext &Context,
203                        TemplateParameterList *TemplateParams,
204                        const TemplateSpecializationType *Param,
205                        QualType Arg,
206                        Sema::TemplateDeductionInfo &Info,
207                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
208  assert(Arg->isCanonical() && "Argument type must be canonical");
209
210  // Check whether the template argument is a dependent template-id.
211  // FIXME: This is untested code; it can be tested when we implement
212  // partial ordering of class template partial specializations.
213  if (const TemplateSpecializationType *SpecArg
214        = dyn_cast<TemplateSpecializationType>(Arg)) {
215    // Perform template argument deduction for the template name.
216    if (Sema::TemplateDeductionResult Result
217          = DeduceTemplateArguments(Context,
218                                    Param->getTemplateName(),
219                                    SpecArg->getTemplateName(),
220                                    Info, Deduced))
221      return Result;
222
223    unsigned NumArgs = Param->getNumArgs();
224
225    // FIXME: When one of the template-names refers to a
226    // declaration with default template arguments, do we need to
227    // fill in those default template arguments here? Most likely,
228    // the answer is "yes", but I don't see any references. This
229    // issue may be resolved elsewhere, because we may want to
230    // instantiate default template arguments when we actually write
231    // the template-id.
232    if (SpecArg->getNumArgs() != NumArgs)
233      return Sema::TDK_NonDeducedMismatch;
234
235    // Perform template argument deduction on each template
236    // argument.
237    for (unsigned I = 0; I != NumArgs; ++I)
238      if (Sema::TemplateDeductionResult Result
239            = DeduceTemplateArguments(Context, TemplateParams,
240                                      Param->getArg(I),
241                                      SpecArg->getArg(I),
242                                      Info, Deduced))
243        return Result;
244
245    return Sema::TDK_Success;
246  }
247
248  // If the argument type is a class template specialization, we
249  // perform template argument deduction using its template
250  // arguments.
251  const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
252  if (!RecordArg)
253    return Sema::TDK_NonDeducedMismatch;
254
255  ClassTemplateSpecializationDecl *SpecArg
256    = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
257  if (!SpecArg)
258    return Sema::TDK_NonDeducedMismatch;
259
260  // Perform template argument deduction for the template name.
261  if (Sema::TemplateDeductionResult Result
262        = DeduceTemplateArguments(Context,
263                                  Param->getTemplateName(),
264                               TemplateName(SpecArg->getSpecializedTemplate()),
265                                  Info, Deduced))
266    return Result;
267
268  // FIXME: Can the # of arguments in the parameter and the argument
269  // differ due to default arguments?
270  unsigned NumArgs = Param->getNumArgs();
271  const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs();
272  if (NumArgs != ArgArgs.size())
273    return Sema::TDK_NonDeducedMismatch;
274
275  for (unsigned I = 0; I != NumArgs; ++I)
276    if (Sema::TemplateDeductionResult Result
277          = DeduceTemplateArguments(Context, TemplateParams,
278                                    Param->getArg(I),
279                                    ArgArgs.get(I),
280                                    Info, Deduced))
281      return Result;
282
283  return Sema::TDK_Success;
284}
285
286/// \brief Deduce the template arguments by comparing the parameter type and
287/// the argument type (C++ [temp.deduct.type]).
288///
289/// \param Context the AST context in which this deduction occurs.
290///
291/// \param TemplateParams the template parameters that we are deducing
292///
293/// \param ParamIn the parameter type
294///
295/// \param ArgIn the argument type
296///
297/// \param Info information about the template argument deduction itself
298///
299/// \param Deduced the deduced template arguments
300///
301/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
302/// how template argument deduction is performed.
303///
304/// \returns the result of template argument deduction so far. Note that a
305/// "success" result means that template argument deduction has not yet failed,
306/// but it may still fail, later, for other reasons.
307static Sema::TemplateDeductionResult
308DeduceTemplateArguments(ASTContext &Context,
309                        TemplateParameterList *TemplateParams,
310                        QualType ParamIn, QualType ArgIn,
311                        Sema::TemplateDeductionInfo &Info,
312                        llvm::SmallVectorImpl<TemplateArgument> &Deduced,
313                        unsigned TDF) {
314  // We only want to look at the canonical types, since typedefs and
315  // sugar are not part of template argument deduction.
316  QualType Param = Context.getCanonicalType(ParamIn);
317  QualType Arg = Context.getCanonicalType(ArgIn);
318
319  // C++0x [temp.deduct.call]p4 bullet 1:
320  //   - If the original P is a reference type, the deduced A (i.e., the type
321  //     referred to by the reference) can be more cv-qualified than the
322  //     transformed A.
323  if (TDF & TDF_ParamWithReferenceType) {
324    unsigned ExtraQualsOnParam
325      = Param.getCVRQualifiers() & ~Arg.getCVRQualifiers();
326    Param.setCVRQualifiers(Param.getCVRQualifiers() & ~ExtraQualsOnParam);
327  }
328
329  // If the parameter type is not dependent, there is nothing to deduce.
330  if (!Param->isDependentType())
331    return Sema::TDK_Success;
332
333  // C++ [temp.deduct.type]p9:
334  //   A template type argument T, a template template argument TT or a
335  //   template non-type argument i can be deduced if P and A have one of
336  //   the following forms:
337  //
338  //     T
339  //     cv-list T
340  if (const TemplateTypeParmType *TemplateTypeParm
341        = Param->getAsTemplateTypeParmType()) {
342    unsigned Index = TemplateTypeParm->getIndex();
343
344    // The argument type can not be less qualified than the parameter
345    // type.
346    if (Param.isMoreQualifiedThan(Arg) && !(TDF & TDF_IgnoreQualifiers)) {
347      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
348      Info.FirstArg = Deduced[Index];
349      Info.SecondArg = TemplateArgument(SourceLocation(), Arg);
350      return Sema::TDK_InconsistentQuals;
351    }
352
353    assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
354
355    unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers();
356    QualType DeducedType = Arg.getQualifiedType(Quals);
357
358    if (Deduced[Index].isNull())
359      Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType);
360    else {
361      // C++ [temp.deduct.type]p2:
362      //   [...] If type deduction cannot be done for any P/A pair, or if for
363      //   any pair the deduction leads to more than one possible set of
364      //   deduced values, or if different pairs yield different deduced
365      //   values, or if any template argument remains neither deduced nor
366      //   explicitly specified, template argument deduction fails.
367      if (Deduced[Index].getAsType() != DeducedType) {
368        Info.Param
369          = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
370        Info.FirstArg = Deduced[Index];
371        Info.SecondArg = TemplateArgument(SourceLocation(), Arg);
372        return Sema::TDK_Inconsistent;
373      }
374    }
375    return Sema::TDK_Success;
376  }
377
378  // Set up the template argument deduction information for a failure.
379  Info.FirstArg = TemplateArgument(SourceLocation(), ParamIn);
380  Info.SecondArg = TemplateArgument(SourceLocation(), ArgIn);
381
382  // Check the cv-qualifiers on the parameter and argument types.
383  if (!(TDF & TDF_IgnoreQualifiers)) {
384    if (TDF & TDF_ParamWithReferenceType) {
385      if (Param.isMoreQualifiedThan(Arg))
386        return Sema::TDK_NonDeducedMismatch;
387    } else {
388      if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
389        return Sema::TDK_NonDeducedMismatch;
390    }
391  }
392
393  switch (Param->getTypeClass()) {
394    // No deduction possible for these types
395    case Type::Builtin:
396      return Sema::TDK_NonDeducedMismatch;
397
398    //     T *
399    case Type::Pointer: {
400      const PointerType *PointerArg = Arg->getAsPointerType();
401      if (!PointerArg)
402        return Sema::TDK_NonDeducedMismatch;
403
404      unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
405      return DeduceTemplateArguments(Context, TemplateParams,
406                                   cast<PointerType>(Param)->getPointeeType(),
407                                     PointerArg->getPointeeType(),
408                                     Info, Deduced, SubTDF);
409    }
410
411    //     T &
412    case Type::LValueReference: {
413      const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType();
414      if (!ReferenceArg)
415        return Sema::TDK_NonDeducedMismatch;
416
417      return DeduceTemplateArguments(Context, TemplateParams,
418                           cast<LValueReferenceType>(Param)->getPointeeType(),
419                                     ReferenceArg->getPointeeType(),
420                                     Info, Deduced, 0);
421    }
422
423    //     T && [C++0x]
424    case Type::RValueReference: {
425      const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType();
426      if (!ReferenceArg)
427        return Sema::TDK_NonDeducedMismatch;
428
429      return DeduceTemplateArguments(Context, TemplateParams,
430                           cast<RValueReferenceType>(Param)->getPointeeType(),
431                                     ReferenceArg->getPointeeType(),
432                                     Info, Deduced, 0);
433    }
434
435    //     T [] (implied, but not stated explicitly)
436    case Type::IncompleteArray: {
437      const IncompleteArrayType *IncompleteArrayArg =
438        Context.getAsIncompleteArrayType(Arg);
439      if (!IncompleteArrayArg)
440        return Sema::TDK_NonDeducedMismatch;
441
442      return DeduceTemplateArguments(Context, TemplateParams,
443                     Context.getAsIncompleteArrayType(Param)->getElementType(),
444                                     IncompleteArrayArg->getElementType(),
445                                     Info, Deduced, 0);
446    }
447
448    //     T [integer-constant]
449    case Type::ConstantArray: {
450      const ConstantArrayType *ConstantArrayArg =
451        Context.getAsConstantArrayType(Arg);
452      if (!ConstantArrayArg)
453        return Sema::TDK_NonDeducedMismatch;
454
455      const ConstantArrayType *ConstantArrayParm =
456        Context.getAsConstantArrayType(Param);
457      if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
458        return Sema::TDK_NonDeducedMismatch;
459
460      return DeduceTemplateArguments(Context, TemplateParams,
461                                     ConstantArrayParm->getElementType(),
462                                     ConstantArrayArg->getElementType(),
463                                     Info, Deduced, 0);
464    }
465
466    //     type [i]
467    case Type::DependentSizedArray: {
468      const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg);
469      if (!ArrayArg)
470        return Sema::TDK_NonDeducedMismatch;
471
472      // Check the element type of the arrays
473      const DependentSizedArrayType *DependentArrayParm
474        = cast<DependentSizedArrayType>(Param);
475      if (Sema::TemplateDeductionResult Result
476            = DeduceTemplateArguments(Context, TemplateParams,
477                                      DependentArrayParm->getElementType(),
478                                      ArrayArg->getElementType(),
479                                      Info, Deduced, 0))
480        return Result;
481
482      // Determine the array bound is something we can deduce.
483      NonTypeTemplateParmDecl *NTTP
484        = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
485      if (!NTTP)
486        return Sema::TDK_Success;
487
488      // We can perform template argument deduction for the given non-type
489      // template parameter.
490      assert(NTTP->getDepth() == 0 &&
491             "Cannot deduce non-type template argument at depth > 0");
492      if (const ConstantArrayType *ConstantArrayArg
493            = dyn_cast<ConstantArrayType>(ArrayArg)) {
494        llvm::APSInt Size(ConstantArrayArg->getSize());
495        return DeduceNonTypeTemplateArgument(Context, NTTP, Size,
496                                             Info, Deduced);
497      }
498      if (const DependentSizedArrayType *DependentArrayArg
499            = dyn_cast<DependentSizedArrayType>(ArrayArg))
500        return DeduceNonTypeTemplateArgument(Context, NTTP,
501                                             DependentArrayArg->getSizeExpr(),
502                                             Info, Deduced);
503
504      // Incomplete type does not match a dependently-sized array type
505      return Sema::TDK_NonDeducedMismatch;
506    }
507
508    //     type(*)(T)
509    //     T(*)()
510    //     T(*)(T)
511    case Type::FunctionProto: {
512      const FunctionProtoType *FunctionProtoArg =
513        dyn_cast<FunctionProtoType>(Arg);
514      if (!FunctionProtoArg)
515        return Sema::TDK_NonDeducedMismatch;
516
517      const FunctionProtoType *FunctionProtoParam =
518        cast<FunctionProtoType>(Param);
519
520      if (FunctionProtoParam->getTypeQuals() !=
521          FunctionProtoArg->getTypeQuals())
522        return Sema::TDK_NonDeducedMismatch;
523
524      if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs())
525        return Sema::TDK_NonDeducedMismatch;
526
527      if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
528        return Sema::TDK_NonDeducedMismatch;
529
530      // Check return types.
531      if (Sema::TemplateDeductionResult Result
532            = DeduceTemplateArguments(Context, TemplateParams,
533                                      FunctionProtoParam->getResultType(),
534                                      FunctionProtoArg->getResultType(),
535                                      Info, Deduced, 0))
536        return Result;
537
538      for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) {
539        // Check argument types.
540        if (Sema::TemplateDeductionResult Result
541              = DeduceTemplateArguments(Context, TemplateParams,
542                                        FunctionProtoParam->getArgType(I),
543                                        FunctionProtoArg->getArgType(I),
544                                        Info, Deduced, 0))
545          return Result;
546      }
547
548      return Sema::TDK_Success;
549    }
550
551    //     template-name<T> (where template-name refers to a class template)
552    //     template-name<i>
553    //     TT<T> (TODO)
554    //     TT<i> (TODO)
555    //     TT<> (TODO)
556    case Type::TemplateSpecialization: {
557      const TemplateSpecializationType *SpecParam
558        = cast<TemplateSpecializationType>(Param);
559
560      // Try to deduce template arguments from the template-id.
561      Sema::TemplateDeductionResult Result
562        = DeduceTemplateArguments(Context, TemplateParams, SpecParam, Arg,
563                                  Info, Deduced);
564
565      if (Result && (TDF & TDF_DerivedClass) &&
566          Result != Sema::TDK_Inconsistent) {
567        // C++ [temp.deduct.call]p3b3:
568        //   If P is a class, and P has the form template-id, then A can be a
569        //   derived class of the deduced A. Likewise, if P is a pointer to a
570        //   class of the form template-id, A can be a pointer to a derived
571        //   class pointed to by the deduced A.
572        //
573        // More importantly:
574        //   These alternatives are considered only if type deduction would
575        //   otherwise fail.
576        if (const RecordType *RecordT = dyn_cast<RecordType>(Arg)) {
577          // Use data recursion to crawl through the list of base classes.
578          // Visited contains the set of nodes we have already visited, while
579          // ToVisit is our stack of records that we still need to visit.
580          llvm::SmallPtrSet<const RecordType *, 8> Visited;
581          llvm::SmallVector<const RecordType *, 8> ToVisit;
582          ToVisit.push_back(RecordT);
583          bool Successful = false;
584          while (!ToVisit.empty()) {
585            // Retrieve the next class in the inheritance hierarchy.
586            const RecordType *NextT = ToVisit.back();
587            ToVisit.pop_back();
588
589            // If we have already seen this type, skip it.
590            if (!Visited.insert(NextT))
591              continue;
592
593            // If this is a base class, try to perform template argument
594            // deduction from it.
595            if (NextT != RecordT) {
596              Sema::TemplateDeductionResult BaseResult
597                = DeduceTemplateArguments(Context, TemplateParams, SpecParam,
598                                          QualType(NextT, 0), Info, Deduced);
599
600              // If template argument deduction for this base was successful,
601              // note that we had some success.
602              if (BaseResult == Sema::TDK_Success)
603                Successful = true;
604              // If deduction against this base resulted in an inconsistent
605              // set of deduced template arguments, template argument
606              // deduction fails.
607              else if (BaseResult == Sema::TDK_Inconsistent)
608                return BaseResult;
609            }
610
611            // Visit base classes
612            CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
613            for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
614                                                 BaseEnd = Next->bases_end();
615               Base != BaseEnd; ++Base) {
616              assert(Base->getType()->isRecordType() &&
617                     "Base class that isn't a record?");
618              ToVisit.push_back(Base->getType()->getAsRecordType());
619            }
620          }
621
622          if (Successful)
623            return Sema::TDK_Success;
624        }
625
626      }
627
628      return Result;
629    }
630
631    //     T type::*
632    //     T T::*
633    //     T (type::*)()
634    //     type (T::*)()
635    //     type (type::*)(T)
636    //     type (T::*)(T)
637    //     T (type::*)(T)
638    //     T (T::*)()
639    //     T (T::*)(T)
640    case Type::MemberPointer: {
641      const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
642      const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
643      if (!MemPtrArg)
644        return Sema::TDK_NonDeducedMismatch;
645
646      if (Sema::TemplateDeductionResult Result
647            = DeduceTemplateArguments(Context, TemplateParams,
648                                      MemPtrParam->getPointeeType(),
649                                      MemPtrArg->getPointeeType(),
650                                      Info, Deduced,
651                                      TDF & TDF_IgnoreQualifiers))
652        return Result;
653
654      return DeduceTemplateArguments(Context, TemplateParams,
655                                     QualType(MemPtrParam->getClass(), 0),
656                                     QualType(MemPtrArg->getClass(), 0),
657                                     Info, Deduced, 0);
658    }
659
660    //     (clang extension)
661    //
662    //     type(^)(T)
663    //     T(^)()
664    //     T(^)(T)
665    case Type::BlockPointer: {
666      const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
667      const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
668
669      if (!BlockPtrArg)
670        return Sema::TDK_NonDeducedMismatch;
671
672      return DeduceTemplateArguments(Context, TemplateParams,
673                                     BlockPtrParam->getPointeeType(),
674                                     BlockPtrArg->getPointeeType(), Info,
675                                     Deduced, 0);
676    }
677
678    case Type::TypeOfExpr:
679    case Type::TypeOf:
680    case Type::Typename:
681      // No template argument deduction for these types
682      return Sema::TDK_Success;
683
684    default:
685      break;
686  }
687
688  // FIXME: Many more cases to go (to go).
689  return Sema::TDK_Success;
690}
691
692static Sema::TemplateDeductionResult
693DeduceTemplateArguments(ASTContext &Context,
694                        TemplateParameterList *TemplateParams,
695                        const TemplateArgument &Param,
696                        const TemplateArgument &Arg,
697                        Sema::TemplateDeductionInfo &Info,
698                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
699  switch (Param.getKind()) {
700  case TemplateArgument::Null:
701    assert(false && "Null template argument in parameter list");
702    break;
703
704  case TemplateArgument::Type:
705    assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
706    return DeduceTemplateArguments(Context, TemplateParams, Param.getAsType(),
707                                   Arg.getAsType(), Info, Deduced, 0);
708
709  case TemplateArgument::Declaration:
710    // FIXME: Implement this check
711    assert(false && "Unimplemented template argument deduction case");
712    Info.FirstArg = Param;
713    Info.SecondArg = Arg;
714    return Sema::TDK_NonDeducedMismatch;
715
716  case TemplateArgument::Integral:
717    if (Arg.getKind() == TemplateArgument::Integral) {
718      // FIXME: Zero extension + sign checking here?
719      if (*Param.getAsIntegral() == *Arg.getAsIntegral())
720        return Sema::TDK_Success;
721
722      Info.FirstArg = Param;
723      Info.SecondArg = Arg;
724      return Sema::TDK_NonDeducedMismatch;
725    }
726
727    if (Arg.getKind() == TemplateArgument::Expression) {
728      Info.FirstArg = Param;
729      Info.SecondArg = Arg;
730      return Sema::TDK_NonDeducedMismatch;
731    }
732
733    assert(false && "Type/value mismatch");
734    Info.FirstArg = Param;
735    Info.SecondArg = Arg;
736    return Sema::TDK_NonDeducedMismatch;
737
738  case TemplateArgument::Expression: {
739    if (NonTypeTemplateParmDecl *NTTP
740          = getDeducedParameterFromExpr(Param.getAsExpr())) {
741      if (Arg.getKind() == TemplateArgument::Integral)
742        // FIXME: Sign problems here
743        return DeduceNonTypeTemplateArgument(Context, NTTP,
744                                             *Arg.getAsIntegral(),
745                                             Info, Deduced);
746      if (Arg.getKind() == TemplateArgument::Expression)
747        return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
748                                             Info, Deduced);
749
750      assert(false && "Type/value mismatch");
751      Info.FirstArg = Param;
752      Info.SecondArg = Arg;
753      return Sema::TDK_NonDeducedMismatch;
754    }
755
756    // Can't deduce anything, but that's okay.
757    return Sema::TDK_Success;
758  }
759  case TemplateArgument::Pack:
760    assert(0 && "FIXME: Implement!");
761    break;
762  }
763
764  return Sema::TDK_Success;
765}
766
767static Sema::TemplateDeductionResult
768DeduceTemplateArguments(ASTContext &Context,
769                        TemplateParameterList *TemplateParams,
770                        const TemplateArgumentList &ParamList,
771                        const TemplateArgumentList &ArgList,
772                        Sema::TemplateDeductionInfo &Info,
773                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
774  assert(ParamList.size() == ArgList.size());
775  for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
776    if (Sema::TemplateDeductionResult Result
777          = DeduceTemplateArguments(Context, TemplateParams,
778                                    ParamList[I], ArgList[I],
779                                    Info, Deduced))
780      return Result;
781  }
782  return Sema::TDK_Success;
783}
784
785/// \brief Determine whether two template arguments are the same.
786static bool isSameTemplateArg(ASTContext &Context,
787                              const TemplateArgument &X,
788                              const TemplateArgument &Y) {
789  if (X.getKind() != Y.getKind())
790    return false;
791
792  switch (X.getKind()) {
793    case TemplateArgument::Null:
794      assert(false && "Comparing NULL template argument");
795      break;
796
797    case TemplateArgument::Type:
798      return Context.getCanonicalType(X.getAsType()) ==
799             Context.getCanonicalType(Y.getAsType());
800
801    case TemplateArgument::Declaration:
802      return X.getAsDecl()->getCanonicalDecl() ==
803             Y.getAsDecl()->getCanonicalDecl();
804
805    case TemplateArgument::Integral:
806      return *X.getAsIntegral() == *Y.getAsIntegral();
807
808    case TemplateArgument::Expression:
809      // FIXME: We assume that all expressions are distinct, but we should
810      // really check their canonical forms.
811      return false;
812
813    case TemplateArgument::Pack:
814      if (X.pack_size() != Y.pack_size())
815        return false;
816
817      for (TemplateArgument::pack_iterator XP = X.pack_begin(),
818                                        XPEnd = X.pack_end(),
819                                           YP = Y.pack_begin();
820           XP != XPEnd; ++XP, ++YP)
821        if (!isSameTemplateArg(Context, *XP, *YP))
822          return false;
823
824      return true;
825  }
826
827  return false;
828}
829
830/// \brief Helper function to build a TemplateParameter when we don't
831/// know its type statically.
832static TemplateParameter makeTemplateParameter(Decl *D) {
833  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
834    return TemplateParameter(TTP);
835  else if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
836    return TemplateParameter(NTTP);
837
838  return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
839}
840
841/// \brief Perform template argument deduction to determine whether
842/// the given template arguments match the given class template
843/// partial specialization per C++ [temp.class.spec.match].
844Sema::TemplateDeductionResult
845Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
846                              const TemplateArgumentList &TemplateArgs,
847                              TemplateDeductionInfo &Info) {
848  // C++ [temp.class.spec.match]p2:
849  //   A partial specialization matches a given actual template
850  //   argument list if the template arguments of the partial
851  //   specialization can be deduced from the actual template argument
852  //   list (14.8.2).
853  SFINAETrap Trap(*this);
854  llvm::SmallVector<TemplateArgument, 4> Deduced;
855  Deduced.resize(Partial->getTemplateParameters()->size());
856  if (TemplateDeductionResult Result
857        = ::DeduceTemplateArguments(Context,
858                                    Partial->getTemplateParameters(),
859                                    Partial->getTemplateArgs(),
860                                    TemplateArgs, Info, Deduced))
861    return Result;
862
863  InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
864                             Deduced.data(), Deduced.size());
865  if (Inst)
866    return TDK_InstantiationDepth;
867
868  // C++ [temp.deduct.type]p2:
869  //   [...] or if any template argument remains neither deduced nor
870  //   explicitly specified, template argument deduction fails.
871  TemplateArgumentListBuilder Builder(Partial->getTemplateParameters(),
872                                      Deduced.size());
873  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
874    if (Deduced[I].isNull()) {
875      Decl *Param
876        = const_cast<Decl *>(Partial->getTemplateParameters()->getParam(I));
877      if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
878        Info.Param = TTP;
879      else if (NonTypeTemplateParmDecl *NTTP
880                 = dyn_cast<NonTypeTemplateParmDecl>(Param))
881        Info.Param = NTTP;
882      else
883        Info.Param = cast<TemplateTemplateParmDecl>(Param);
884      return TDK_Incomplete;
885    }
886
887    Builder.Append(Deduced[I]);
888  }
889
890  // Form the template argument list from the deduced template arguments.
891  TemplateArgumentList *DeducedArgumentList
892    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
893  Info.reset(DeducedArgumentList);
894
895  // Substitute the deduced template arguments into the template
896  // arguments of the class template partial specialization, and
897  // verify that the instantiated template arguments are both valid
898  // and are equivalent to the template arguments originally provided
899  // to the class template.
900  ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
901  const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs();
902  for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) {
903    Decl *Param = const_cast<Decl *>(
904                    ClassTemplate->getTemplateParameters()->getParam(I));
905    TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I],
906                                           *DeducedArgumentList);
907    if (InstArg.isNull()) {
908      Info.Param = makeTemplateParameter(Param);
909      Info.FirstArg = PartialTemplateArgs[I];
910      return TDK_SubstitutionFailure;
911    }
912
913    if (InstArg.getKind() == TemplateArgument::Expression) {
914      // When the argument is an expression, check the expression result
915      // against the actual template parameter to get down to the canonical
916      // template argument.
917      Expr *InstExpr = InstArg.getAsExpr();
918      if (NonTypeTemplateParmDecl *NTTP
919            = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
920        if (CheckTemplateArgument(NTTP, NTTP->getType(), InstExpr, InstArg)) {
921          Info.Param = makeTemplateParameter(Param);
922          Info.FirstArg = PartialTemplateArgs[I];
923          return TDK_SubstitutionFailure;
924        }
925      } else if (TemplateTemplateParmDecl *TTP
926                   = dyn_cast<TemplateTemplateParmDecl>(Param)) {
927        // FIXME: template template arguments should really resolve to decls
928        DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(InstExpr);
929        if (!DRE || CheckTemplateArgument(TTP, DRE)) {
930          Info.Param = makeTemplateParameter(Param);
931          Info.FirstArg = PartialTemplateArgs[I];
932          return TDK_SubstitutionFailure;
933        }
934      }
935    }
936
937    if (!isSameTemplateArg(Context, TemplateArgs[I], InstArg)) {
938      Info.Param = makeTemplateParameter(Param);
939      Info.FirstArg = TemplateArgs[I];
940      Info.SecondArg = InstArg;
941      return TDK_NonDeducedMismatch;
942    }
943  }
944
945  if (Trap.hasErrorOccurred())
946    return TDK_SubstitutionFailure;
947
948  return TDK_Success;
949}
950
951/// \brief Determine whether the given type T is a simple-template-id type.
952static bool isSimpleTemplateIdType(QualType T) {
953  if (const TemplateSpecializationType *Spec
954        = T->getAsTemplateSpecializationType())
955    return Spec->getTemplateName().getAsTemplateDecl() != 0;
956
957  return false;
958}
959
960/// \brief Substitute the explicitly-provided template arguments into the
961/// given function template according to C++ [temp.arg.explicit].
962///
963/// \param FunctionTemplate the function template into which the explicit
964/// template arguments will be substituted.
965///
966/// \param ExplicitTemplateArguments the explicitly-specified template
967/// arguments.
968///
969/// \param NumExplicitTemplateArguments the number of explicitly-specified
970/// template arguments in @p ExplicitTemplateArguments. This value may be zero.
971///
972/// \param Deduced the deduced template arguments, which will be populated
973/// with the converted and checked explicit template arguments.
974///
975/// \param ParamTypes will be populated with the instantiated function
976/// parameters.
977///
978/// \param FunctionType if non-NULL, the result type of the function template
979/// will also be instantiated and the pointed-to value will be updated with
980/// the instantiated function type.
981///
982/// \param Info if substitution fails for any reason, this object will be
983/// populated with more information about the failure.
984///
985/// \returns TDK_Success if substitution was successful, or some failure
986/// condition.
987Sema::TemplateDeductionResult
988Sema::SubstituteExplicitTemplateArguments(
989                                      FunctionTemplateDecl *FunctionTemplate,
990                                const TemplateArgument *ExplicitTemplateArgs,
991                                          unsigned NumExplicitTemplateArgs,
992                            llvm::SmallVectorImpl<TemplateArgument> &Deduced,
993                                 llvm::SmallVectorImpl<QualType> &ParamTypes,
994                                          QualType *FunctionType,
995                                          TemplateDeductionInfo &Info) {
996  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
997  TemplateParameterList *TemplateParams
998    = FunctionTemplate->getTemplateParameters();
999
1000  if (NumExplicitTemplateArgs == 0) {
1001    // No arguments to substitute; just copy over the parameter types and
1002    // fill in the function type.
1003    for (FunctionDecl::param_iterator P = Function->param_begin(),
1004                                   PEnd = Function->param_end();
1005         P != PEnd;
1006         ++P)
1007      ParamTypes.push_back((*P)->getType());
1008
1009    if (FunctionType)
1010      *FunctionType = Function->getType();
1011    return TDK_Success;
1012  }
1013
1014  // Substitution of the explicit template arguments into a function template
1015  /// is a SFINAE context. Trap any errors that might occur.
1016  SFINAETrap Trap(*this);
1017
1018  // C++ [temp.arg.explicit]p3:
1019  //   Template arguments that are present shall be specified in the
1020  //   declaration order of their corresponding template-parameters. The
1021  //   template argument list shall not specify more template-arguments than
1022  //   there are corresponding template-parameters.
1023  TemplateArgumentListBuilder Builder(TemplateParams,
1024                                      NumExplicitTemplateArgs);
1025
1026  // Enter a new template instantiation context where we check the
1027  // explicitly-specified template arguments against this function template,
1028  // and then substitute them into the function parameter types.
1029  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
1030                             FunctionTemplate, Deduced.data(), Deduced.size(),
1031           ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution);
1032  if (Inst)
1033    return TDK_InstantiationDepth;
1034
1035  if (CheckTemplateArgumentList(FunctionTemplate,
1036                                SourceLocation(), SourceLocation(),
1037                                ExplicitTemplateArgs,
1038                                NumExplicitTemplateArgs,
1039                                SourceLocation(),
1040                                true,
1041                                Builder) || Trap.hasErrorOccurred())
1042    return TDK_InvalidExplicitArguments;
1043
1044  // Form the template argument list from the explicitly-specified
1045  // template arguments.
1046  TemplateArgumentList *ExplicitArgumentList
1047    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
1048  Info.reset(ExplicitArgumentList);
1049
1050  // Instantiate the types of each of the function parameters given the
1051  // explicitly-specified template arguments.
1052  for (FunctionDecl::param_iterator P = Function->param_begin(),
1053                                PEnd = Function->param_end();
1054       P != PEnd;
1055       ++P) {
1056    QualType ParamType = InstantiateType((*P)->getType(),
1057                                         *ExplicitArgumentList,
1058                                         (*P)->getLocation(),
1059                                         (*P)->getDeclName());
1060    if (ParamType.isNull() || Trap.hasErrorOccurred())
1061      return TDK_SubstitutionFailure;
1062
1063    ParamTypes.push_back(ParamType);
1064  }
1065
1066  // If the caller wants a full function type back, instantiate the return
1067  // type and form that function type.
1068  if (FunctionType) {
1069    // FIXME: exception-specifications?
1070    const FunctionProtoType *Proto
1071      = Function->getType()->getAsFunctionProtoType();
1072    assert(Proto && "Function template does not have a prototype?");
1073
1074    QualType ResultType = InstantiateType(Proto->getResultType(),
1075                                          *ExplicitArgumentList,
1076                                          Function->getTypeSpecStartLoc(),
1077                                          Function->getDeclName());
1078    if (ResultType.isNull() || Trap.hasErrorOccurred())
1079      return TDK_SubstitutionFailure;
1080
1081    *FunctionType = BuildFunctionType(ResultType,
1082                                      ParamTypes.data(), ParamTypes.size(),
1083                                      Proto->isVariadic(),
1084                                      Proto->getTypeQuals(),
1085                                      Function->getLocation(),
1086                                      Function->getDeclName());
1087    if (FunctionType->isNull() || Trap.hasErrorOccurred())
1088      return TDK_SubstitutionFailure;
1089  }
1090
1091  // C++ [temp.arg.explicit]p2:
1092  //   Trailing template arguments that can be deduced (14.8.2) may be
1093  //   omitted from the list of explicit template-arguments. If all of the
1094  //   template arguments can be deduced, they may all be omitted; in this
1095  //   case, the empty template argument list <> itself may also be omitted.
1096  //
1097  // Take all of the explicitly-specified arguments and put them into the
1098  // set of deduced template arguments.
1099  Deduced.reserve(TemplateParams->size());
1100  for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I)
1101    Deduced.push_back(ExplicitArgumentList->get(I));
1102
1103  return TDK_Success;
1104}
1105
1106/// \brief Finish template argument deduction for a function template,
1107/// checking the deduced template arguments for completeness and forming
1108/// the function template specialization.
1109Sema::TemplateDeductionResult
1110Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
1111                            llvm::SmallVectorImpl<TemplateArgument> &Deduced,
1112                                      FunctionDecl *&Specialization,
1113                                      TemplateDeductionInfo &Info) {
1114  TemplateParameterList *TemplateParams
1115    = FunctionTemplate->getTemplateParameters();
1116
1117  // C++ [temp.deduct.type]p2:
1118  //   [...] or if any template argument remains neither deduced nor
1119  //   explicitly specified, template argument deduction fails.
1120  TemplateArgumentListBuilder Builder(TemplateParams, Deduced.size());
1121  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
1122    if (Deduced[I].isNull()) {
1123      Info.Param = makeTemplateParameter(
1124                            const_cast<Decl *>(TemplateParams->getParam(I)));
1125      return TDK_Incomplete;
1126    }
1127
1128    Builder.Append(Deduced[I]);
1129  }
1130
1131  // Form the template argument list from the deduced template arguments.
1132  TemplateArgumentList *DeducedArgumentList
1133    = new (Context) TemplateArgumentList(Context, Builder, /*TakeArgs=*/true);
1134  Info.reset(DeducedArgumentList);
1135
1136  // Template argument deduction for function templates in a SFINAE context.
1137  // Trap any errors that might occur.
1138  SFINAETrap Trap(*this);
1139
1140  // Enter a new template instantiation context while we instantiate the
1141  // actual function declaration.
1142  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
1143                             FunctionTemplate, Deduced.data(), Deduced.size(),
1144              ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution);
1145  if (Inst)
1146    return TDK_InstantiationDepth;
1147
1148  // Substitute the deduced template arguments into the function template
1149  // declaration to produce the function template specialization.
1150  Specialization = cast_or_null<FunctionDecl>(
1151                      InstantiateDecl(FunctionTemplate->getTemplatedDecl(),
1152                                      FunctionTemplate->getDeclContext(),
1153                                      *DeducedArgumentList));
1154  if (!Specialization)
1155    return TDK_SubstitutionFailure;
1156
1157  // If the template argument list is owned by the function template
1158  // specialization, release it.
1159  if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList)
1160    Info.take();
1161
1162  // There may have been an error that did not prevent us from constructing a
1163  // declaration. Mark the declaration invalid and return with a substitution
1164  // failure.
1165  if (Trap.hasErrorOccurred()) {
1166    Specialization->setInvalidDecl(true);
1167    return TDK_SubstitutionFailure;
1168  }
1169
1170  return TDK_Success;
1171}
1172
1173/// \brief Perform template argument deduction from a function call
1174/// (C++ [temp.deduct.call]).
1175///
1176/// \param FunctionTemplate the function template for which we are performing
1177/// template argument deduction.
1178///
1179/// \param HasExplicitTemplateArgs whether any template arguments were
1180/// explicitly specified.
1181///
1182/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true,
1183/// the explicitly-specified template arguments.
1184///
1185/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true,
1186/// the number of explicitly-specified template arguments in
1187/// @p ExplicitTemplateArguments. This value may be zero.
1188///
1189/// \param Args the function call arguments
1190///
1191/// \param NumArgs the number of arguments in Args
1192///
1193/// \param Specialization if template argument deduction was successful,
1194/// this will be set to the function template specialization produced by
1195/// template argument deduction.
1196///
1197/// \param Info the argument will be updated to provide additional information
1198/// about template argument deduction.
1199///
1200/// \returns the result of template argument deduction.
1201Sema::TemplateDeductionResult
1202Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
1203                              bool HasExplicitTemplateArgs,
1204                              const TemplateArgument *ExplicitTemplateArgs,
1205                              unsigned NumExplicitTemplateArgs,
1206                              Expr **Args, unsigned NumArgs,
1207                              FunctionDecl *&Specialization,
1208                              TemplateDeductionInfo &Info) {
1209  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
1210
1211  // C++ [temp.deduct.call]p1:
1212  //   Template argument deduction is done by comparing each function template
1213  //   parameter type (call it P) with the type of the corresponding argument
1214  //   of the call (call it A) as described below.
1215  unsigned CheckArgs = NumArgs;
1216  if (NumArgs < Function->getMinRequiredArguments())
1217    return TDK_TooFewArguments;
1218  else if (NumArgs > Function->getNumParams()) {
1219    const FunctionProtoType *Proto
1220      = Function->getType()->getAsFunctionProtoType();
1221    if (!Proto->isVariadic())
1222      return TDK_TooManyArguments;
1223
1224    CheckArgs = Function->getNumParams();
1225  }
1226
1227  // The types of the parameters from which we will perform template argument
1228  // deduction.
1229  TemplateParameterList *TemplateParams
1230    = FunctionTemplate->getTemplateParameters();
1231  llvm::SmallVector<TemplateArgument, 4> Deduced;
1232  llvm::SmallVector<QualType, 4> ParamTypes;
1233  if (NumExplicitTemplateArgs) {
1234    TemplateDeductionResult Result =
1235      SubstituteExplicitTemplateArguments(FunctionTemplate,
1236                                          ExplicitTemplateArgs,
1237                                          NumExplicitTemplateArgs,
1238                                          Deduced,
1239                                          ParamTypes,
1240                                          0,
1241                                          Info);
1242    if (Result)
1243      return Result;
1244  } else {
1245    // Just fill in the parameter types from the function declaration.
1246    for (unsigned I = 0; I != CheckArgs; ++I)
1247      ParamTypes.push_back(Function->getParamDecl(I)->getType());
1248  }
1249
1250  // Deduce template arguments from the function parameters.
1251  Deduced.resize(TemplateParams->size());
1252  for (unsigned I = 0; I != CheckArgs; ++I) {
1253    QualType ParamType = ParamTypes[I];
1254    QualType ArgType = Args[I]->getType();
1255
1256    // C++ [temp.deduct.call]p2:
1257    //   If P is not a reference type:
1258    QualType CanonParamType = Context.getCanonicalType(ParamType);
1259    bool ParamWasReference = isa<ReferenceType>(CanonParamType);
1260    if (!ParamWasReference) {
1261      //   - If A is an array type, the pointer type produced by the
1262      //     array-to-pointer standard conversion (4.2) is used in place of
1263      //     A for type deduction; otherwise,
1264      if (ArgType->isArrayType())
1265        ArgType = Context.getArrayDecayedType(ArgType);
1266      //   - If A is a function type, the pointer type produced by the
1267      //     function-to-pointer standard conversion (4.3) is used in place
1268      //     of A for type deduction; otherwise,
1269      else if (ArgType->isFunctionType())
1270        ArgType = Context.getPointerType(ArgType);
1271      else {
1272        // - If A is a cv-qualified type, the top level cv-qualifiers of A’s
1273        //   type are ignored for type deduction.
1274        QualType CanonArgType = Context.getCanonicalType(ArgType);
1275        if (CanonArgType.getCVRQualifiers())
1276          ArgType = CanonArgType.getUnqualifiedType();
1277      }
1278    }
1279
1280    // C++0x [temp.deduct.call]p3:
1281    //   If P is a cv-qualified type, the top level cv-qualifiers of P’s type
1282    //   are ignored for type deduction.
1283    if (CanonParamType.getCVRQualifiers())
1284      ParamType = CanonParamType.getUnqualifiedType();
1285    if (const ReferenceType *ParamRefType = ParamType->getAsReferenceType()) {
1286      //   [...] If P is a reference type, the type referred to by P is used
1287      //   for type deduction.
1288      ParamType = ParamRefType->getPointeeType();
1289
1290      //   [...] If P is of the form T&&, where T is a template parameter, and
1291      //   the argument is an lvalue, the type A& is used in place of A for
1292      //   type deduction.
1293      if (isa<RValueReferenceType>(ParamRefType) &&
1294          ParamRefType->getAsTemplateTypeParmType() &&
1295          Args[I]->isLvalue(Context) == Expr::LV_Valid)
1296        ArgType = Context.getLValueReferenceType(ArgType);
1297    }
1298
1299    // C++0x [temp.deduct.call]p4:
1300    //   In general, the deduction process attempts to find template argument
1301    //   values that will make the deduced A identical to A (after the type A
1302    //   is transformed as described above). [...]
1303    unsigned TDF = 0;
1304
1305    //     - If the original P is a reference type, the deduced A (i.e., the
1306    //       type referred to by the reference) can be more cv-qualified than
1307    //       the transformed A.
1308    if (ParamWasReference)
1309      TDF |= TDF_ParamWithReferenceType;
1310    //     - The transformed A can be another pointer or pointer to member
1311    //       type that can be converted to the deduced A via a qualification
1312    //       conversion (4.4).
1313    if (ArgType->isPointerType() || ArgType->isMemberPointerType())
1314      TDF |= TDF_IgnoreQualifiers;
1315    //     - If P is a class and P has the form simple-template-id, then the
1316    //       transformed A can be a derived class of the deduced A. Likewise,
1317    //       if P is a pointer to a class of the form simple-template-id, the
1318    //       transformed A can be a pointer to a derived class pointed to by
1319    //       the deduced A.
1320    if (isSimpleTemplateIdType(ParamType) ||
1321        (isa<PointerType>(ParamType) &&
1322         isSimpleTemplateIdType(
1323                              ParamType->getAsPointerType()->getPointeeType())))
1324      TDF |= TDF_DerivedClass;
1325
1326    if (TemplateDeductionResult Result
1327        = ::DeduceTemplateArguments(Context, TemplateParams,
1328                                    ParamType, ArgType, Info, Deduced,
1329                                    TDF))
1330      return Result;
1331
1332    // FIXME: C++0x [temp.deduct.call] paragraphs 6-9 deal with function
1333    // pointer parameters.
1334  }
1335
1336  return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
1337                                         Specialization, Info);
1338}
1339
1340/// \brief Deduce template arguments when taking the address of a function
1341/// template (C++ [temp.deduct.funcaddr]).
1342///
1343/// \param FunctionTemplate the function template for which we are performing
1344/// template argument deduction.
1345///
1346/// \param HasExplicitTemplateArgs whether any template arguments were
1347/// explicitly specified.
1348///
1349/// \param ExplicitTemplateArguments when @p HasExplicitTemplateArgs is true,
1350/// the explicitly-specified template arguments.
1351///
1352/// \param NumExplicitTemplateArguments when @p HasExplicitTemplateArgs is true,
1353/// the number of explicitly-specified template arguments in
1354/// @p ExplicitTemplateArguments. This value may be zero.
1355///
1356/// \param ArgFunctionType the function type that will be used as the
1357/// "argument" type (A) when performing template argument deduction from the
1358/// function template's function type.
1359///
1360/// \param Specialization if template argument deduction was successful,
1361/// this will be set to the function template specialization produced by
1362/// template argument deduction.
1363///
1364/// \param Info the argument will be updated to provide additional information
1365/// about template argument deduction.
1366///
1367/// \returns the result of template argument deduction.
1368Sema::TemplateDeductionResult
1369Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
1370                              bool HasExplicitTemplateArgs,
1371                              const TemplateArgument *ExplicitTemplateArgs,
1372                              unsigned NumExplicitTemplateArgs,
1373                              QualType ArgFunctionType,
1374                              FunctionDecl *&Specialization,
1375                              TemplateDeductionInfo &Info) {
1376  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
1377  TemplateParameterList *TemplateParams
1378    = FunctionTemplate->getTemplateParameters();
1379  QualType FunctionType = Function->getType();
1380
1381  // Substitute any explicit template arguments.
1382  llvm::SmallVector<TemplateArgument, 4> Deduced;
1383  llvm::SmallVector<QualType, 4> ParamTypes;
1384  if (HasExplicitTemplateArgs) {
1385    if (TemplateDeductionResult Result
1386          = SubstituteExplicitTemplateArguments(FunctionTemplate,
1387                                                ExplicitTemplateArgs,
1388                                                NumExplicitTemplateArgs,
1389                                                Deduced, ParamTypes,
1390                                                &FunctionType, Info))
1391      return Result;
1392  }
1393
1394  // Template argument deduction for function templates in a SFINAE context.
1395  // Trap any errors that might occur.
1396  SFINAETrap Trap(*this);
1397
1398  // Deduce template arguments from the function type.
1399  Deduced.resize(TemplateParams->size());
1400  if (TemplateDeductionResult Result
1401        = ::DeduceTemplateArguments(Context, TemplateParams,
1402                                    FunctionType, ArgFunctionType, Info,
1403                                    Deduced, 0))
1404    return Result;
1405
1406  return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
1407                                         Specialization, Info);
1408}
1409
1410
1411static void
1412MarkDeducedTemplateParameters(Sema &SemaRef,
1413                              const TemplateArgument &TemplateArg,
1414                              llvm::SmallVectorImpl<bool> &Deduced);
1415
1416/// \brief Mark the template arguments that are deduced by the given
1417/// expression.
1418static void
1419MarkDeducedTemplateParameters(const Expr *E,
1420                              llvm::SmallVectorImpl<bool> &Deduced) {
1421  const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
1422  if (!E)
1423    return;
1424
1425  const NonTypeTemplateParmDecl *NTTP
1426    = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
1427  if (!NTTP)
1428    return;
1429
1430  Deduced[NTTP->getIndex()] = true;
1431}
1432
1433/// \brief Mark the template parameters that are deduced by the given
1434/// type.
1435static void
1436MarkDeducedTemplateParameters(Sema &SemaRef, QualType T,
1437                              llvm::SmallVectorImpl<bool> &Deduced) {
1438  // Non-dependent types have nothing deducible
1439  if (!T->isDependentType())
1440    return;
1441
1442  T = SemaRef.Context.getCanonicalType(T);
1443  switch (T->getTypeClass()) {
1444  case Type::ExtQual:
1445    MarkDeducedTemplateParameters(SemaRef,
1446                              QualType(cast<ExtQualType>(T)->getBaseType(), 0),
1447                                  Deduced);
1448    break;
1449
1450  case Type::Pointer:
1451    MarkDeducedTemplateParameters(SemaRef,
1452                                  cast<PointerType>(T)->getPointeeType(),
1453                                  Deduced);
1454    break;
1455
1456  case Type::BlockPointer:
1457    MarkDeducedTemplateParameters(SemaRef,
1458                                  cast<BlockPointerType>(T)->getPointeeType(),
1459                                  Deduced);
1460    break;
1461
1462  case Type::LValueReference:
1463  case Type::RValueReference:
1464    MarkDeducedTemplateParameters(SemaRef,
1465                                  cast<ReferenceType>(T)->getPointeeType(),
1466                                  Deduced);
1467    break;
1468
1469  case Type::MemberPointer: {
1470    const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
1471    MarkDeducedTemplateParameters(SemaRef, MemPtr->getPointeeType(), Deduced);
1472    MarkDeducedTemplateParameters(SemaRef, QualType(MemPtr->getClass(), 0),
1473                                  Deduced);
1474    break;
1475  }
1476
1477  case Type::DependentSizedArray:
1478    MarkDeducedTemplateParameters(cast<DependentSizedArrayType>(T)->getSizeExpr(),
1479                                  Deduced);
1480    // Fall through to check the element type
1481
1482  case Type::ConstantArray:
1483  case Type::IncompleteArray:
1484    MarkDeducedTemplateParameters(SemaRef,
1485                                  cast<ArrayType>(T)->getElementType(),
1486                                  Deduced);
1487    break;
1488
1489  case Type::Vector:
1490  case Type::ExtVector:
1491    MarkDeducedTemplateParameters(SemaRef,
1492                                  cast<VectorType>(T)->getElementType(),
1493                                  Deduced);
1494    break;
1495
1496  case Type::DependentSizedExtVector: {
1497    const DependentSizedExtVectorType *VecType
1498      = cast<DependentSizedExtVectorType>(T);
1499    MarkDeducedTemplateParameters(SemaRef, VecType->getElementType(), Deduced);
1500    MarkDeducedTemplateParameters(VecType->getSizeExpr(), Deduced);
1501    break;
1502  }
1503
1504  case Type::FunctionProto: {
1505    const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
1506    MarkDeducedTemplateParameters(SemaRef, Proto->getResultType(), Deduced);
1507    for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
1508      MarkDeducedTemplateParameters(SemaRef, Proto->getArgType(I), Deduced);
1509    break;
1510  }
1511
1512  case Type::TemplateTypeParm:
1513    Deduced[cast<TemplateTypeParmType>(T)->getIndex()] = true;
1514    break;
1515
1516  case Type::TemplateSpecialization: {
1517    const TemplateSpecializationType *Spec
1518      = cast<TemplateSpecializationType>(T);
1519    if (TemplateDecl *Template = Spec->getTemplateName().getAsTemplateDecl())
1520      if (TemplateTemplateParmDecl *TTP
1521            = dyn_cast<TemplateTemplateParmDecl>(Template))
1522        Deduced[TTP->getIndex()] = true;
1523
1524      for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
1525        MarkDeducedTemplateParameters(SemaRef, Spec->getArg(I), Deduced);
1526
1527    break;
1528  }
1529
1530  // None of these types have any deducible parts.
1531  case Type::Builtin:
1532  case Type::FixedWidthInt:
1533  case Type::Complex:
1534  case Type::VariableArray:
1535  case Type::FunctionNoProto:
1536  case Type::Record:
1537  case Type::Enum:
1538  case Type::Typename:
1539  case Type::ObjCInterface:
1540  case Type::ObjCQualifiedInterface:
1541  case Type::ObjCObjectPointer:
1542#define TYPE(Class, Base)
1543#define ABSTRACT_TYPE(Class, Base)
1544#define DEPENDENT_TYPE(Class, Base)
1545#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
1546#include "clang/AST/TypeNodes.def"
1547    break;
1548  }
1549}
1550
1551/// \brief Mark the template parameters that are deduced by this
1552/// template argument.
1553static void
1554MarkDeducedTemplateParameters(Sema &SemaRef,
1555                              const TemplateArgument &TemplateArg,
1556                              llvm::SmallVectorImpl<bool> &Deduced) {
1557  switch (TemplateArg.getKind()) {
1558  case TemplateArgument::Null:
1559  case TemplateArgument::Integral:
1560    break;
1561
1562  case TemplateArgument::Type:
1563    MarkDeducedTemplateParameters(SemaRef, TemplateArg.getAsType(), Deduced);
1564    break;
1565
1566  case TemplateArgument::Declaration:
1567    if (TemplateTemplateParmDecl *TTP
1568        = dyn_cast<TemplateTemplateParmDecl>(TemplateArg.getAsDecl()))
1569      Deduced[TTP->getIndex()] = true;
1570    break;
1571
1572  case TemplateArgument::Expression:
1573    MarkDeducedTemplateParameters(TemplateArg.getAsExpr(), Deduced);
1574    break;
1575  case TemplateArgument::Pack:
1576    assert(0 && "FIXME: Implement!");
1577    break;
1578  }
1579}
1580
1581/// \brief Mark the template parameters can be deduced by the given
1582/// template argument list.
1583///
1584/// \param TemplateArgs the template argument list from which template
1585/// parameters will be deduced.
1586///
1587/// \param Deduced a bit vector whose elements will be set to \c true
1588/// to indicate when the corresponding template parameter will be
1589/// deduced.
1590void
1591Sema::MarkDeducedTemplateParameters(const TemplateArgumentList &TemplateArgs,
1592                                    llvm::SmallVectorImpl<bool> &Deduced) {
1593  for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
1594    ::MarkDeducedTemplateParameters(*this, TemplateArgs[I], Deduced);
1595}
1596