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