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