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 "clang/Sema/TemplateDeduction.h"
14#include "TreeTransform.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/DeclObjC.h"
17#include "clang/AST/DeclTemplate.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/ExprCXX.h"
20#include "clang/AST/StmtVisitor.h"
21#include "clang/Sema/DeclSpec.h"
22#include "clang/Sema/Sema.h"
23#include "clang/Sema/Template.h"
24#include "llvm/ADT/SmallBitVector.h"
25#include <algorithm>
26
27namespace clang {
28  using namespace sema;
29
30  /// \brief Various flags that control template argument deduction.
31  ///
32  /// These flags can be bitwise-OR'd together.
33  enum TemplateDeductionFlags {
34    /// \brief No template argument deduction flags, which indicates the
35    /// strictest results for template argument deduction (as used for, e.g.,
36    /// matching class template partial specializations).
37    TDF_None = 0,
38    /// \brief Within template argument deduction from a function call, we are
39    /// matching with a parameter type for which the original parameter was
40    /// a reference.
41    TDF_ParamWithReferenceType = 0x1,
42    /// \brief Within template argument deduction from a function call, we
43    /// are matching in a case where we ignore cv-qualifiers.
44    TDF_IgnoreQualifiers = 0x02,
45    /// \brief Within template argument deduction from a function call,
46    /// we are matching in a case where we can perform template argument
47    /// deduction from a template-id of a derived class of the argument type.
48    TDF_DerivedClass = 0x04,
49    /// \brief Allow non-dependent types to differ, e.g., when performing
50    /// template argument deduction from a function call where conversions
51    /// may apply.
52    TDF_SkipNonDependent = 0x08,
53    /// \brief Whether we are performing template argument deduction for
54    /// parameters and arguments in a top-level template argument
55    TDF_TopLevelParameterTypeList = 0x10,
56    /// \brief Within template argument deduction from overload resolution per
57    /// C++ [over.over] allow matching function types that are compatible in
58    /// terms of noreturn and default calling convention adjustments.
59    TDF_InOverloadResolution = 0x20
60  };
61}
62
63using namespace clang;
64
65/// \brief Compare two APSInts, extending and switching the sign as
66/// necessary to compare their values regardless of underlying type.
67static bool hasSameExtendedValue(llvm::APSInt X, llvm::APSInt Y) {
68  if (Y.getBitWidth() > X.getBitWidth())
69    X = X.extend(Y.getBitWidth());
70  else if (Y.getBitWidth() < X.getBitWidth())
71    Y = Y.extend(X.getBitWidth());
72
73  // If there is a signedness mismatch, correct it.
74  if (X.isSigned() != Y.isSigned()) {
75    // If the signed value is negative, then the values cannot be the same.
76    if ((Y.isSigned() && Y.isNegative()) || (X.isSigned() && X.isNegative()))
77      return false;
78
79    Y.setIsSigned(true);
80    X.setIsSigned(true);
81  }
82
83  return X == Y;
84}
85
86static Sema::TemplateDeductionResult
87DeduceTemplateArguments(Sema &S,
88                        TemplateParameterList *TemplateParams,
89                        const TemplateArgument &Param,
90                        TemplateArgument Arg,
91                        TemplateDeductionInfo &Info,
92                        SmallVectorImpl<DeducedTemplateArgument> &Deduced);
93
94/// \brief Whether template argument deduction for two reference parameters
95/// resulted in the argument type, parameter type, or neither type being more
96/// qualified than the other.
97enum DeductionQualifierComparison {
98  NeitherMoreQualified = 0,
99  ParamMoreQualified,
100  ArgMoreQualified
101};
102
103/// \brief Stores the result of comparing two reference parameters while
104/// performing template argument deduction for partial ordering of function
105/// templates.
106struct RefParamPartialOrderingComparison {
107  /// \brief Whether the parameter type is an rvalue reference type.
108  bool ParamIsRvalueRef;
109  /// \brief Whether the argument type is an rvalue reference type.
110  bool ArgIsRvalueRef;
111
112  /// \brief Whether the parameter or argument (or neither) is more qualified.
113  DeductionQualifierComparison Qualifiers;
114};
115
116
117
118static Sema::TemplateDeductionResult
119DeduceTemplateArgumentsByTypeMatch(Sema &S,
120                                   TemplateParameterList *TemplateParams,
121                                   QualType Param,
122                                   QualType Arg,
123                                   TemplateDeductionInfo &Info,
124                                   SmallVectorImpl<DeducedTemplateArgument> &
125                                                      Deduced,
126                                   unsigned TDF,
127                                   bool PartialOrdering = false,
128                            SmallVectorImpl<RefParamPartialOrderingComparison> *
129                                                      RefParamComparisons = 0);
130
131static Sema::TemplateDeductionResult
132DeduceTemplateArguments(Sema &S,
133                        TemplateParameterList *TemplateParams,
134                        const TemplateArgument *Params, unsigned NumParams,
135                        const TemplateArgument *Args, unsigned NumArgs,
136                        TemplateDeductionInfo &Info,
137                        SmallVectorImpl<DeducedTemplateArgument> &Deduced);
138
139/// \brief If the given expression is of a form that permits the deduction
140/// of a non-type template parameter, return the declaration of that
141/// non-type template parameter.
142static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
143  // If we are within an alias template, the expression may have undergone
144  // any number of parameter substitutions already.
145  while (1) {
146    if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
147      E = IC->getSubExpr();
148    else if (SubstNonTypeTemplateParmExpr *Subst =
149               dyn_cast<SubstNonTypeTemplateParmExpr>(E))
150      E = Subst->getReplacement();
151    else
152      break;
153  }
154
155  if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
156    return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
157
158  return 0;
159}
160
161/// \brief Determine whether two declaration pointers refer to the same
162/// declaration.
163static bool isSameDeclaration(Decl *X, Decl *Y) {
164  if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
165    X = NX->getUnderlyingDecl();
166  if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
167    Y = NY->getUnderlyingDecl();
168
169  return X->getCanonicalDecl() == Y->getCanonicalDecl();
170}
171
172/// \brief Verify that the given, deduced template arguments are compatible.
173///
174/// \returns The deduced template argument, or a NULL template argument if
175/// the deduced template arguments were incompatible.
176static DeducedTemplateArgument
177checkDeducedTemplateArguments(ASTContext &Context,
178                              const DeducedTemplateArgument &X,
179                              const DeducedTemplateArgument &Y) {
180  // We have no deduction for one or both of the arguments; they're compatible.
181  if (X.isNull())
182    return Y;
183  if (Y.isNull())
184    return X;
185
186  switch (X.getKind()) {
187  case TemplateArgument::Null:
188    llvm_unreachable("Non-deduced template arguments handled above");
189
190  case TemplateArgument::Type:
191    // If two template type arguments have the same type, they're compatible.
192    if (Y.getKind() == TemplateArgument::Type &&
193        Context.hasSameType(X.getAsType(), Y.getAsType()))
194      return X;
195
196    return DeducedTemplateArgument();
197
198  case TemplateArgument::Integral:
199    // If we deduced a constant in one case and either a dependent expression or
200    // declaration in another case, keep the integral constant.
201    // If both are integral constants with the same value, keep that value.
202    if (Y.getKind() == TemplateArgument::Expression ||
203        Y.getKind() == TemplateArgument::Declaration ||
204        (Y.getKind() == TemplateArgument::Integral &&
205         hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
206      return DeducedTemplateArgument(X,
207                                     X.wasDeducedFromArrayBound() &&
208                                     Y.wasDeducedFromArrayBound());
209
210    // All other combinations are incompatible.
211    return DeducedTemplateArgument();
212
213  case TemplateArgument::Template:
214    if (Y.getKind() == TemplateArgument::Template &&
215        Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
216      return X;
217
218    // All other combinations are incompatible.
219    return DeducedTemplateArgument();
220
221  case TemplateArgument::TemplateExpansion:
222    if (Y.getKind() == TemplateArgument::TemplateExpansion &&
223        Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
224                                    Y.getAsTemplateOrTemplatePattern()))
225      return X;
226
227    // All other combinations are incompatible.
228    return DeducedTemplateArgument();
229
230  case TemplateArgument::Expression:
231    // If we deduced a dependent expression in one case and either an integral
232    // constant or a declaration in another case, keep the integral constant
233    // or declaration.
234    if (Y.getKind() == TemplateArgument::Integral ||
235        Y.getKind() == TemplateArgument::Declaration)
236      return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
237                                     Y.wasDeducedFromArrayBound());
238
239    if (Y.getKind() == TemplateArgument::Expression) {
240      // Compare the expressions for equality
241      llvm::FoldingSetNodeID ID1, ID2;
242      X.getAsExpr()->Profile(ID1, Context, true);
243      Y.getAsExpr()->Profile(ID2, Context, true);
244      if (ID1 == ID2)
245        return X;
246    }
247
248    // All other combinations are incompatible.
249    return DeducedTemplateArgument();
250
251  case TemplateArgument::Declaration:
252    // If we deduced a declaration and a dependent expression, keep the
253    // declaration.
254    if (Y.getKind() == TemplateArgument::Expression)
255      return X;
256
257    // If we deduced a declaration and an integral constant, keep the
258    // integral constant.
259    if (Y.getKind() == TemplateArgument::Integral)
260      return Y;
261
262    // If we deduced two declarations, make sure they they refer to the
263    // same declaration.
264    if (Y.getKind() == TemplateArgument::Declaration &&
265        isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) &&
266        X.isDeclForReferenceParam() == Y.isDeclForReferenceParam())
267      return X;
268
269    // All other combinations are incompatible.
270    return DeducedTemplateArgument();
271
272  case TemplateArgument::NullPtr:
273    // If we deduced a null pointer and a dependent expression, keep the
274    // null pointer.
275    if (Y.getKind() == TemplateArgument::Expression)
276      return X;
277
278    // If we deduced a null pointer and an integral constant, keep the
279    // integral constant.
280    if (Y.getKind() == TemplateArgument::Integral)
281      return Y;
282
283    // If we deduced two null pointers, make sure they have the same type.
284    if (Y.getKind() == TemplateArgument::NullPtr &&
285        Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()))
286      return X;
287
288    // All other combinations are incompatible.
289    return DeducedTemplateArgument();
290
291  case TemplateArgument::Pack:
292    if (Y.getKind() != TemplateArgument::Pack ||
293        X.pack_size() != Y.pack_size())
294      return DeducedTemplateArgument();
295
296    for (TemplateArgument::pack_iterator XA = X.pack_begin(),
297                                      XAEnd = X.pack_end(),
298                                         YA = Y.pack_begin();
299         XA != XAEnd; ++XA, ++YA) {
300      if (checkDeducedTemplateArguments(Context,
301                    DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
302                    DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
303            .isNull())
304        return DeducedTemplateArgument();
305    }
306
307    return X;
308  }
309
310  llvm_unreachable("Invalid TemplateArgument Kind!");
311}
312
313/// \brief Deduce the value of the given non-type template parameter
314/// from the given constant.
315static Sema::TemplateDeductionResult
316DeduceNonTypeTemplateArgument(Sema &S,
317                              NonTypeTemplateParmDecl *NTTP,
318                              llvm::APSInt Value, QualType ValueType,
319                              bool DeducedFromArrayBound,
320                              TemplateDeductionInfo &Info,
321                    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
322  assert(NTTP->getDepth() == 0 &&
323         "Cannot deduce non-type template argument with depth > 0");
324
325  DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType,
326                                     DeducedFromArrayBound);
327  DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
328                                                     Deduced[NTTP->getIndex()],
329                                                                 NewDeduced);
330  if (Result.isNull()) {
331    Info.Param = NTTP;
332    Info.FirstArg = Deduced[NTTP->getIndex()];
333    Info.SecondArg = NewDeduced;
334    return Sema::TDK_Inconsistent;
335  }
336
337  Deduced[NTTP->getIndex()] = Result;
338  return Sema::TDK_Success;
339}
340
341/// \brief Deduce the value of the given non-type template parameter
342/// from the given type- or value-dependent expression.
343///
344/// \returns true if deduction succeeded, false otherwise.
345static Sema::TemplateDeductionResult
346DeduceNonTypeTemplateArgument(Sema &S,
347                              NonTypeTemplateParmDecl *NTTP,
348                              Expr *Value,
349                              TemplateDeductionInfo &Info,
350                    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
351  assert(NTTP->getDepth() == 0 &&
352         "Cannot deduce non-type template argument with depth > 0");
353  assert((Value->isTypeDependent() || Value->isValueDependent()) &&
354         "Expression template argument must be type- or value-dependent.");
355
356  DeducedTemplateArgument NewDeduced(Value);
357  DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
358                                                     Deduced[NTTP->getIndex()],
359                                                                 NewDeduced);
360
361  if (Result.isNull()) {
362    Info.Param = NTTP;
363    Info.FirstArg = Deduced[NTTP->getIndex()];
364    Info.SecondArg = NewDeduced;
365    return Sema::TDK_Inconsistent;
366  }
367
368  Deduced[NTTP->getIndex()] = Result;
369  return Sema::TDK_Success;
370}
371
372/// \brief Deduce the value of the given non-type template parameter
373/// from the given declaration.
374///
375/// \returns true if deduction succeeded, false otherwise.
376static Sema::TemplateDeductionResult
377DeduceNonTypeTemplateArgument(Sema &S,
378                            NonTypeTemplateParmDecl *NTTP,
379                            ValueDecl *D,
380                            TemplateDeductionInfo &Info,
381                            SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
382  assert(NTTP->getDepth() == 0 &&
383         "Cannot deduce non-type template argument with depth > 0");
384
385  D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : 0;
386  TemplateArgument New(D, NTTP->getType()->isReferenceType());
387  DeducedTemplateArgument NewDeduced(New);
388  DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
389                                                     Deduced[NTTP->getIndex()],
390                                                                 NewDeduced);
391  if (Result.isNull()) {
392    Info.Param = NTTP;
393    Info.FirstArg = Deduced[NTTP->getIndex()];
394    Info.SecondArg = NewDeduced;
395    return Sema::TDK_Inconsistent;
396  }
397
398  Deduced[NTTP->getIndex()] = Result;
399  return Sema::TDK_Success;
400}
401
402static Sema::TemplateDeductionResult
403DeduceTemplateArguments(Sema &S,
404                        TemplateParameterList *TemplateParams,
405                        TemplateName Param,
406                        TemplateName Arg,
407                        TemplateDeductionInfo &Info,
408                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
409  TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
410  if (!ParamDecl) {
411    // The parameter type is dependent and is not a template template parameter,
412    // so there is nothing that we can deduce.
413    return Sema::TDK_Success;
414  }
415
416  if (TemplateTemplateParmDecl *TempParam
417        = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
418    DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
419    DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
420                                                 Deduced[TempParam->getIndex()],
421                                                                   NewDeduced);
422    if (Result.isNull()) {
423      Info.Param = TempParam;
424      Info.FirstArg = Deduced[TempParam->getIndex()];
425      Info.SecondArg = NewDeduced;
426      return Sema::TDK_Inconsistent;
427    }
428
429    Deduced[TempParam->getIndex()] = Result;
430    return Sema::TDK_Success;
431  }
432
433  // Verify that the two template names are equivalent.
434  if (S.Context.hasSameTemplateName(Param, Arg))
435    return Sema::TDK_Success;
436
437  // Mismatch of non-dependent template parameter to argument.
438  Info.FirstArg = TemplateArgument(Param);
439  Info.SecondArg = TemplateArgument(Arg);
440  return Sema::TDK_NonDeducedMismatch;
441}
442
443/// \brief Deduce the template arguments by comparing the template parameter
444/// type (which is a template-id) with the template argument type.
445///
446/// \param S the Sema
447///
448/// \param TemplateParams the template parameters that we are deducing
449///
450/// \param Param the parameter type
451///
452/// \param Arg the argument type
453///
454/// \param Info information about the template argument deduction itself
455///
456/// \param Deduced the deduced template arguments
457///
458/// \returns the result of template argument deduction so far. Note that a
459/// "success" result means that template argument deduction has not yet failed,
460/// but it may still fail, later, for other reasons.
461static Sema::TemplateDeductionResult
462DeduceTemplateArguments(Sema &S,
463                        TemplateParameterList *TemplateParams,
464                        const TemplateSpecializationType *Param,
465                        QualType Arg,
466                        TemplateDeductionInfo &Info,
467                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
468  assert(Arg.isCanonical() && "Argument type must be canonical");
469
470  // Check whether the template argument is a dependent template-id.
471  if (const TemplateSpecializationType *SpecArg
472        = dyn_cast<TemplateSpecializationType>(Arg)) {
473    // Perform template argument deduction for the template name.
474    if (Sema::TemplateDeductionResult Result
475          = DeduceTemplateArguments(S, TemplateParams,
476                                    Param->getTemplateName(),
477                                    SpecArg->getTemplateName(),
478                                    Info, Deduced))
479      return Result;
480
481
482    // Perform template argument deduction on each template
483    // argument. Ignore any missing/extra arguments, since they could be
484    // filled in by default arguments.
485    return DeduceTemplateArguments(S, TemplateParams,
486                                   Param->getArgs(), Param->getNumArgs(),
487                                   SpecArg->getArgs(), SpecArg->getNumArgs(),
488                                   Info, Deduced);
489  }
490
491  // If the argument type is a class template specialization, we
492  // perform template argument deduction using its template
493  // arguments.
494  const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
495  if (!RecordArg) {
496    Info.FirstArg = TemplateArgument(QualType(Param, 0));
497    Info.SecondArg = TemplateArgument(Arg);
498    return Sema::TDK_NonDeducedMismatch;
499  }
500
501  ClassTemplateSpecializationDecl *SpecArg
502    = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
503  if (!SpecArg) {
504    Info.FirstArg = TemplateArgument(QualType(Param, 0));
505    Info.SecondArg = TemplateArgument(Arg);
506    return Sema::TDK_NonDeducedMismatch;
507  }
508
509  // Perform template argument deduction for the template name.
510  if (Sema::TemplateDeductionResult Result
511        = DeduceTemplateArguments(S,
512                                  TemplateParams,
513                                  Param->getTemplateName(),
514                               TemplateName(SpecArg->getSpecializedTemplate()),
515                                  Info, Deduced))
516    return Result;
517
518  // Perform template argument deduction for the template arguments.
519  return DeduceTemplateArguments(S, TemplateParams,
520                                 Param->getArgs(), Param->getNumArgs(),
521                                 SpecArg->getTemplateArgs().data(),
522                                 SpecArg->getTemplateArgs().size(),
523                                 Info, Deduced);
524}
525
526/// \brief Determines whether the given type is an opaque type that
527/// might be more qualified when instantiated.
528static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
529  switch (T->getTypeClass()) {
530  case Type::TypeOfExpr:
531  case Type::TypeOf:
532  case Type::DependentName:
533  case Type::Decltype:
534  case Type::UnresolvedUsing:
535  case Type::TemplateTypeParm:
536    return true;
537
538  case Type::ConstantArray:
539  case Type::IncompleteArray:
540  case Type::VariableArray:
541  case Type::DependentSizedArray:
542    return IsPossiblyOpaquelyQualifiedType(
543                                      cast<ArrayType>(T)->getElementType());
544
545  default:
546    return false;
547  }
548}
549
550/// \brief Retrieve the depth and index of a template parameter.
551static std::pair<unsigned, unsigned>
552getDepthAndIndex(NamedDecl *ND) {
553  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
554    return std::make_pair(TTP->getDepth(), TTP->getIndex());
555
556  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
557    return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
558
559  TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
560  return std::make_pair(TTP->getDepth(), TTP->getIndex());
561}
562
563/// \brief Retrieve the depth and index of an unexpanded parameter pack.
564static std::pair<unsigned, unsigned>
565getDepthAndIndex(UnexpandedParameterPack UPP) {
566  if (const TemplateTypeParmType *TTP
567                          = UPP.first.dyn_cast<const TemplateTypeParmType *>())
568    return std::make_pair(TTP->getDepth(), TTP->getIndex());
569
570  return getDepthAndIndex(UPP.first.get<NamedDecl *>());
571}
572
573/// \brief Helper function to build a TemplateParameter when we don't
574/// know its type statically.
575static TemplateParameter makeTemplateParameter(Decl *D) {
576  if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
577    return TemplateParameter(TTP);
578  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
579    return TemplateParameter(NTTP);
580
581  return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
582}
583
584typedef SmallVector<SmallVector<DeducedTemplateArgument, 4>, 2>
585  NewlyDeducedPacksType;
586
587/// \brief Prepare to perform template argument deduction for all of the
588/// arguments in a set of argument packs.
589static void
590PrepareArgumentPackDeduction(Sema &S,
591                           SmallVectorImpl<DeducedTemplateArgument> &Deduced,
592                           ArrayRef<unsigned> PackIndices,
593                           SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
594                           NewlyDeducedPacksType &NewlyDeducedPacks) {
595  // Save the deduced template arguments for each parameter pack expanded
596  // by this pack expansion, then clear out the deduction.
597  for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
598    // Save the previously-deduced argument pack, then clear it out so that we
599    // can deduce a new argument pack.
600    SavedPacks[I] = Deduced[PackIndices[I]];
601    Deduced[PackIndices[I]] = TemplateArgument();
602
603    if (!S.CurrentInstantiationScope)
604      continue;
605
606    // If the template argument pack was explicitly specified, add that to
607    // the set of deduced arguments.
608    const TemplateArgument *ExplicitArgs;
609    unsigned NumExplicitArgs;
610    if (NamedDecl *PartiallySubstitutedPack
611        = S.CurrentInstantiationScope->getPartiallySubstitutedPack(
612                                                           &ExplicitArgs,
613                                                           &NumExplicitArgs)) {
614      if (getDepthAndIndex(PartiallySubstitutedPack).second == PackIndices[I])
615        NewlyDeducedPacks[I].append(ExplicitArgs,
616                                    ExplicitArgs + NumExplicitArgs);
617    }
618  }
619}
620
621/// \brief Finish template argument deduction for a set of argument packs,
622/// producing the argument packs and checking for consistency with prior
623/// deductions.
624static Sema::TemplateDeductionResult
625FinishArgumentPackDeduction(Sema &S,
626                           TemplateParameterList *TemplateParams,
627                           bool HasAnyArguments,
628                           SmallVectorImpl<DeducedTemplateArgument> &Deduced,
629                           ArrayRef<unsigned> PackIndices,
630                           SmallVectorImpl<DeducedTemplateArgument> &SavedPacks,
631                           NewlyDeducedPacksType &NewlyDeducedPacks,
632                           TemplateDeductionInfo &Info) {
633  // Build argument packs for each of the parameter packs expanded by this
634  // pack expansion.
635  for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
636    if (HasAnyArguments && NewlyDeducedPacks[I].empty()) {
637      // We were not able to deduce anything for this parameter pack,
638      // so just restore the saved argument pack.
639      Deduced[PackIndices[I]] = SavedPacks[I];
640      continue;
641    }
642
643    DeducedTemplateArgument NewPack;
644
645    if (NewlyDeducedPacks[I].empty()) {
646      // If we deduced an empty argument pack, create it now.
647      NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
648    } else {
649      TemplateArgument *ArgumentPack
650        = new (S.Context) TemplateArgument [NewlyDeducedPacks[I].size()];
651      std::copy(NewlyDeducedPacks[I].begin(), NewlyDeducedPacks[I].end(),
652                ArgumentPack);
653      NewPack
654        = DeducedTemplateArgument(TemplateArgument(ArgumentPack,
655                                                   NewlyDeducedPacks[I].size()),
656                            NewlyDeducedPacks[I][0].wasDeducedFromArrayBound());
657    }
658
659    DeducedTemplateArgument Result
660      = checkDeducedTemplateArguments(S.Context, SavedPacks[I], NewPack);
661    if (Result.isNull()) {
662      Info.Param
663        = makeTemplateParameter(TemplateParams->getParam(PackIndices[I]));
664      Info.FirstArg = SavedPacks[I];
665      Info.SecondArg = NewPack;
666      return Sema::TDK_Inconsistent;
667    }
668
669    Deduced[PackIndices[I]] = Result;
670  }
671
672  return Sema::TDK_Success;
673}
674
675/// \brief Deduce the template arguments by comparing the list of parameter
676/// types to the list of argument types, as in the parameter-type-lists of
677/// function types (C++ [temp.deduct.type]p10).
678///
679/// \param S The semantic analysis object within which we are deducing
680///
681/// \param TemplateParams The template parameters that we are deducing
682///
683/// \param Params The list of parameter types
684///
685/// \param NumParams The number of types in \c Params
686///
687/// \param Args The list of argument types
688///
689/// \param NumArgs The number of types in \c Args
690///
691/// \param Info information about the template argument deduction itself
692///
693/// \param Deduced the deduced template arguments
694///
695/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
696/// how template argument deduction is performed.
697///
698/// \param PartialOrdering If true, we are performing template argument
699/// deduction for during partial ordering for a call
700/// (C++0x [temp.deduct.partial]).
701///
702/// \param RefParamComparisons If we're performing template argument deduction
703/// in the context of partial ordering, the set of qualifier comparisons.
704///
705/// \returns the result of template argument deduction so far. Note that a
706/// "success" result means that template argument deduction has not yet failed,
707/// but it may still fail, later, for other reasons.
708static Sema::TemplateDeductionResult
709DeduceTemplateArguments(Sema &S,
710                        TemplateParameterList *TemplateParams,
711                        const QualType *Params, unsigned NumParams,
712                        const QualType *Args, unsigned NumArgs,
713                        TemplateDeductionInfo &Info,
714                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
715                        unsigned TDF,
716                        bool PartialOrdering = false,
717                        SmallVectorImpl<RefParamPartialOrderingComparison> *
718                                                     RefParamComparisons = 0) {
719  // Fast-path check to see if we have too many/too few arguments.
720  if (NumParams != NumArgs &&
721      !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
722      !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
723    return Sema::TDK_MiscellaneousDeductionFailure;
724
725  // C++0x [temp.deduct.type]p10:
726  //   Similarly, if P has a form that contains (T), then each parameter type
727  //   Pi of the respective parameter-type- list of P is compared with the
728  //   corresponding parameter type Ai of the corresponding parameter-type-list
729  //   of A. [...]
730  unsigned ArgIdx = 0, ParamIdx = 0;
731  for (; ParamIdx != NumParams; ++ParamIdx) {
732    // Check argument types.
733    const PackExpansionType *Expansion
734                                = dyn_cast<PackExpansionType>(Params[ParamIdx]);
735    if (!Expansion) {
736      // Simple case: compare the parameter and argument types at this point.
737
738      // Make sure we have an argument.
739      if (ArgIdx >= NumArgs)
740        return Sema::TDK_MiscellaneousDeductionFailure;
741
742      if (isa<PackExpansionType>(Args[ArgIdx])) {
743        // C++0x [temp.deduct.type]p22:
744        //   If the original function parameter associated with A is a function
745        //   parameter pack and the function parameter associated with P is not
746        //   a function parameter pack, then template argument deduction fails.
747        return Sema::TDK_MiscellaneousDeductionFailure;
748      }
749
750      if (Sema::TemplateDeductionResult Result
751            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
752                                                 Params[ParamIdx], Args[ArgIdx],
753                                                 Info, Deduced, TDF,
754                                                 PartialOrdering,
755                                                 RefParamComparisons))
756        return Result;
757
758      ++ArgIdx;
759      continue;
760    }
761
762    // C++0x [temp.deduct.type]p5:
763    //   The non-deduced contexts are:
764    //     - A function parameter pack that does not occur at the end of the
765    //       parameter-declaration-clause.
766    if (ParamIdx + 1 < NumParams)
767      return Sema::TDK_Success;
768
769    // C++0x [temp.deduct.type]p10:
770    //   If the parameter-declaration corresponding to Pi is a function
771    //   parameter pack, then the type of its declarator- id is compared with
772    //   each remaining parameter type in the parameter-type-list of A. Each
773    //   comparison deduces template arguments for subsequent positions in the
774    //   template parameter packs expanded by the function parameter pack.
775
776    // Compute the set of template parameter indices that correspond to
777    // parameter packs expanded by the pack expansion.
778    SmallVector<unsigned, 2> PackIndices;
779    QualType Pattern = Expansion->getPattern();
780    {
781      llvm::SmallBitVector SawIndices(TemplateParams->size());
782      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
783      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
784      for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
785        unsigned Depth, Index;
786        llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
787        if (Depth == 0 && !SawIndices[Index]) {
788          SawIndices[Index] = true;
789          PackIndices.push_back(Index);
790        }
791      }
792    }
793    assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
794
795    // Keep track of the deduced template arguments for each parameter pack
796    // expanded by this pack expansion (the outer index) and for each
797    // template argument (the inner SmallVectors).
798    NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size());
799    SmallVector<DeducedTemplateArgument, 2>
800      SavedPacks(PackIndices.size());
801    PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
802                                 NewlyDeducedPacks);
803
804    bool HasAnyArguments = false;
805    for (; ArgIdx < NumArgs; ++ArgIdx) {
806      HasAnyArguments = true;
807
808      // Deduce template arguments from the pattern.
809      if (Sema::TemplateDeductionResult Result
810            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
811                                                 Args[ArgIdx], Info, Deduced,
812                                                 TDF, PartialOrdering,
813                                                 RefParamComparisons))
814        return Result;
815
816      // Capture the deduced template arguments for each parameter pack expanded
817      // by this pack expansion, add them to the list of arguments we've deduced
818      // for that pack, then clear out the deduced argument.
819      for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
820        DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
821        if (!DeducedArg.isNull()) {
822          NewlyDeducedPacks[I].push_back(DeducedArg);
823          DeducedArg = DeducedTemplateArgument();
824        }
825      }
826    }
827
828    // Build argument packs for each of the parameter packs expanded by this
829    // pack expansion.
830    if (Sema::TemplateDeductionResult Result
831          = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
832                                        Deduced, PackIndices, SavedPacks,
833                                        NewlyDeducedPacks, Info))
834      return Result;
835  }
836
837  // Make sure we don't have any extra arguments.
838  if (ArgIdx < NumArgs)
839    return Sema::TDK_MiscellaneousDeductionFailure;
840
841  return Sema::TDK_Success;
842}
843
844/// \brief Determine whether the parameter has qualifiers that are either
845/// inconsistent with or a superset of the argument's qualifiers.
846static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
847                                                  QualType ArgType) {
848  Qualifiers ParamQs = ParamType.getQualifiers();
849  Qualifiers ArgQs = ArgType.getQualifiers();
850
851  if (ParamQs == ArgQs)
852    return false;
853
854  // Mismatched (but not missing) Objective-C GC attributes.
855  if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() &&
856      ParamQs.hasObjCGCAttr())
857    return true;
858
859  // Mismatched (but not missing) address spaces.
860  if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
861      ParamQs.hasAddressSpace())
862    return true;
863
864  // Mismatched (but not missing) Objective-C lifetime qualifiers.
865  if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
866      ParamQs.hasObjCLifetime())
867    return true;
868
869  // CVR qualifier superset.
870  return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) &&
871      ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers())
872                                                == ParamQs.getCVRQualifiers());
873}
874
875/// \brief Compare types for equality with respect to possibly compatible
876/// function types (noreturn adjustment, implicit calling conventions). If any
877/// of parameter and argument is not a function, just perform type comparison.
878///
879/// \param Param the template parameter type.
880///
881/// \param Arg the argument type.
882bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
883                                          CanQualType Arg) {
884  const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
885                     *ArgFunction   = Arg->getAs<FunctionType>();
886
887  // Just compare if not functions.
888  if (!ParamFunction || !ArgFunction)
889    return Param == Arg;
890
891  // Noreturn adjustment.
892  QualType AdjustedParam;
893  if (IsNoReturnConversion(Param, Arg, AdjustedParam))
894    return Arg == Context.getCanonicalType(AdjustedParam);
895
896  // FIXME: Compatible calling conventions.
897
898  return Param == Arg;
899}
900
901/// \brief Deduce the template arguments by comparing the parameter type and
902/// the argument type (C++ [temp.deduct.type]).
903///
904/// \param S the semantic analysis object within which we are deducing
905///
906/// \param TemplateParams the template parameters that we are deducing
907///
908/// \param ParamIn the parameter type
909///
910/// \param ArgIn the argument type
911///
912/// \param Info information about the template argument deduction itself
913///
914/// \param Deduced the deduced template arguments
915///
916/// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
917/// how template argument deduction is performed.
918///
919/// \param PartialOrdering Whether we're performing template argument deduction
920/// in the context of partial ordering (C++0x [temp.deduct.partial]).
921///
922/// \param RefParamComparisons If we're performing template argument deduction
923/// in the context of partial ordering, the set of qualifier comparisons.
924///
925/// \returns the result of template argument deduction so far. Note that a
926/// "success" result means that template argument deduction has not yet failed,
927/// but it may still fail, later, for other reasons.
928static Sema::TemplateDeductionResult
929DeduceTemplateArgumentsByTypeMatch(Sema &S,
930                                   TemplateParameterList *TemplateParams,
931                                   QualType ParamIn, QualType ArgIn,
932                                   TemplateDeductionInfo &Info,
933                            SmallVectorImpl<DeducedTemplateArgument> &Deduced,
934                                   unsigned TDF,
935                                   bool PartialOrdering,
936                            SmallVectorImpl<RefParamPartialOrderingComparison> *
937                                                          RefParamComparisons) {
938  // We only want to look at the canonical types, since typedefs and
939  // sugar are not part of template argument deduction.
940  QualType Param = S.Context.getCanonicalType(ParamIn);
941  QualType Arg = S.Context.getCanonicalType(ArgIn);
942
943  // If the argument type is a pack expansion, look at its pattern.
944  // This isn't explicitly called out
945  if (const PackExpansionType *ArgExpansion
946                                            = dyn_cast<PackExpansionType>(Arg))
947    Arg = ArgExpansion->getPattern();
948
949  if (PartialOrdering) {
950    // C++0x [temp.deduct.partial]p5:
951    //   Before the partial ordering is done, certain transformations are
952    //   performed on the types used for partial ordering:
953    //     - If P is a reference type, P is replaced by the type referred to.
954    const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
955    if (ParamRef)
956      Param = ParamRef->getPointeeType();
957
958    //     - If A is a reference type, A is replaced by the type referred to.
959    const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
960    if (ArgRef)
961      Arg = ArgRef->getPointeeType();
962
963    if (RefParamComparisons && ParamRef && ArgRef) {
964      // C++0x [temp.deduct.partial]p6:
965      //   If both P and A were reference types (before being replaced with the
966      //   type referred to above), determine which of the two types (if any) is
967      //   more cv-qualified than the other; otherwise the types are considered
968      //   to be equally cv-qualified for partial ordering purposes. The result
969      //   of this determination will be used below.
970      //
971      // We save this information for later, using it only when deduction
972      // succeeds in both directions.
973      RefParamPartialOrderingComparison Comparison;
974      Comparison.ParamIsRvalueRef = ParamRef->getAs<RValueReferenceType>();
975      Comparison.ArgIsRvalueRef = ArgRef->getAs<RValueReferenceType>();
976      Comparison.Qualifiers = NeitherMoreQualified;
977
978      Qualifiers ParamQuals = Param.getQualifiers();
979      Qualifiers ArgQuals = Arg.getQualifiers();
980      if (ParamQuals.isStrictSupersetOf(ArgQuals))
981        Comparison.Qualifiers = ParamMoreQualified;
982      else if (ArgQuals.isStrictSupersetOf(ParamQuals))
983        Comparison.Qualifiers = ArgMoreQualified;
984      RefParamComparisons->push_back(Comparison);
985    }
986
987    // C++0x [temp.deduct.partial]p7:
988    //   Remove any top-level cv-qualifiers:
989    //     - If P is a cv-qualified type, P is replaced by the cv-unqualified
990    //       version of P.
991    Param = Param.getUnqualifiedType();
992    //     - If A is a cv-qualified type, A is replaced by the cv-unqualified
993    //       version of A.
994    Arg = Arg.getUnqualifiedType();
995  } else {
996    // C++0x [temp.deduct.call]p4 bullet 1:
997    //   - If the original P is a reference type, the deduced A (i.e., the type
998    //     referred to by the reference) can be more cv-qualified than the
999    //     transformed A.
1000    if (TDF & TDF_ParamWithReferenceType) {
1001      Qualifiers Quals;
1002      QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1003      Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1004                             Arg.getCVRQualifiers());
1005      Param = S.Context.getQualifiedType(UnqualParam, Quals);
1006    }
1007
1008    if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1009      // C++0x [temp.deduct.type]p10:
1010      //   If P and A are function types that originated from deduction when
1011      //   taking the address of a function template (14.8.2.2) or when deducing
1012      //   template arguments from a function declaration (14.8.2.6) and Pi and
1013      //   Ai are parameters of the top-level parameter-type-list of P and A,
1014      //   respectively, Pi is adjusted if it is an rvalue reference to a
1015      //   cv-unqualified template parameter and Ai is an lvalue reference, in
1016      //   which case the type of Pi is changed to be the template parameter
1017      //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
1018      //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1019      //   deduced as X&. - end note ]
1020      TDF &= ~TDF_TopLevelParameterTypeList;
1021
1022      if (const RValueReferenceType *ParamRef
1023                                        = Param->getAs<RValueReferenceType>()) {
1024        if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
1025            !ParamRef->getPointeeType().getQualifiers())
1026          if (Arg->isLValueReferenceType())
1027            Param = ParamRef->getPointeeType();
1028      }
1029    }
1030  }
1031
1032  // C++ [temp.deduct.type]p9:
1033  //   A template type argument T, a template template argument TT or a
1034  //   template non-type argument i can be deduced if P and A have one of
1035  //   the following forms:
1036  //
1037  //     T
1038  //     cv-list T
1039  if (const TemplateTypeParmType *TemplateTypeParm
1040        = Param->getAs<TemplateTypeParmType>()) {
1041    // Just skip any attempts to deduce from a placeholder type.
1042    if (Arg->isPlaceholderType())
1043      return Sema::TDK_Success;
1044
1045    unsigned Index = TemplateTypeParm->getIndex();
1046    bool RecanonicalizeArg = false;
1047
1048    // If the argument type is an array type, move the qualifiers up to the
1049    // top level, so they can be matched with the qualifiers on the parameter.
1050    if (isa<ArrayType>(Arg)) {
1051      Qualifiers Quals;
1052      Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1053      if (Quals) {
1054        Arg = S.Context.getQualifiedType(Arg, Quals);
1055        RecanonicalizeArg = true;
1056      }
1057    }
1058
1059    // The argument type can not be less qualified than the parameter
1060    // type.
1061    if (!(TDF & TDF_IgnoreQualifiers) &&
1062        hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1063      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1064      Info.FirstArg = TemplateArgument(Param);
1065      Info.SecondArg = TemplateArgument(Arg);
1066      return Sema::TDK_Underqualified;
1067    }
1068
1069    assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
1070    assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1071    QualType DeducedType = Arg;
1072
1073    // Remove any qualifiers on the parameter from the deduced type.
1074    // We checked the qualifiers for consistency above.
1075    Qualifiers DeducedQs = DeducedType.getQualifiers();
1076    Qualifiers ParamQs = Param.getQualifiers();
1077    DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1078    if (ParamQs.hasObjCGCAttr())
1079      DeducedQs.removeObjCGCAttr();
1080    if (ParamQs.hasAddressSpace())
1081      DeducedQs.removeAddressSpace();
1082    if (ParamQs.hasObjCLifetime())
1083      DeducedQs.removeObjCLifetime();
1084
1085    // Objective-C ARC:
1086    //   If template deduction would produce a lifetime qualifier on a type
1087    //   that is not a lifetime type, template argument deduction fails.
1088    if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1089        !DeducedType->isDependentType()) {
1090      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1091      Info.FirstArg = TemplateArgument(Param);
1092      Info.SecondArg = TemplateArgument(Arg);
1093      return Sema::TDK_Underqualified;
1094    }
1095
1096    // Objective-C ARC:
1097    //   If template deduction would produce an argument type with lifetime type
1098    //   but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1099    if (S.getLangOpts().ObjCAutoRefCount &&
1100        DeducedType->isObjCLifetimeType() &&
1101        !DeducedQs.hasObjCLifetime())
1102      DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1103
1104    DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1105                                             DeducedQs);
1106
1107    if (RecanonicalizeArg)
1108      DeducedType = S.Context.getCanonicalType(DeducedType);
1109
1110    DeducedTemplateArgument NewDeduced(DeducedType);
1111    DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1112                                                                 Deduced[Index],
1113                                                                   NewDeduced);
1114    if (Result.isNull()) {
1115      Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1116      Info.FirstArg = Deduced[Index];
1117      Info.SecondArg = NewDeduced;
1118      return Sema::TDK_Inconsistent;
1119    }
1120
1121    Deduced[Index] = Result;
1122    return Sema::TDK_Success;
1123  }
1124
1125  // Set up the template argument deduction information for a failure.
1126  Info.FirstArg = TemplateArgument(ParamIn);
1127  Info.SecondArg = TemplateArgument(ArgIn);
1128
1129  // If the parameter is an already-substituted template parameter
1130  // pack, do nothing: we don't know which of its arguments to look
1131  // at, so we have to wait until all of the parameter packs in this
1132  // expansion have arguments.
1133  if (isa<SubstTemplateTypeParmPackType>(Param))
1134    return Sema::TDK_Success;
1135
1136  // Check the cv-qualifiers on the parameter and argument types.
1137  CanQualType CanParam = S.Context.getCanonicalType(Param);
1138  CanQualType CanArg = S.Context.getCanonicalType(Arg);
1139  if (!(TDF & TDF_IgnoreQualifiers)) {
1140    if (TDF & TDF_ParamWithReferenceType) {
1141      if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1142        return Sema::TDK_NonDeducedMismatch;
1143    } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1144      if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1145        return Sema::TDK_NonDeducedMismatch;
1146    }
1147
1148    // If the parameter type is not dependent, there is nothing to deduce.
1149    if (!Param->isDependentType()) {
1150      if (!(TDF & TDF_SkipNonDependent)) {
1151        bool NonDeduced = (TDF & TDF_InOverloadResolution)?
1152                          !S.isSameOrCompatibleFunctionType(CanParam, CanArg) :
1153                          Param != Arg;
1154        if (NonDeduced) {
1155          return Sema::TDK_NonDeducedMismatch;
1156        }
1157      }
1158      return Sema::TDK_Success;
1159    }
1160  } else if (!Param->isDependentType()) {
1161    CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1162                ArgUnqualType = CanArg.getUnqualifiedType();
1163    bool Success = (TDF & TDF_InOverloadResolution)?
1164                   S.isSameOrCompatibleFunctionType(ParamUnqualType,
1165                                                    ArgUnqualType) :
1166                   ParamUnqualType == ArgUnqualType;
1167    if (Success)
1168      return Sema::TDK_Success;
1169  }
1170
1171  switch (Param->getTypeClass()) {
1172    // Non-canonical types cannot appear here.
1173#define NON_CANONICAL_TYPE(Class, Base) \
1174  case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1175#define TYPE(Class, Base)
1176#include "clang/AST/TypeNodes.def"
1177
1178    case Type::TemplateTypeParm:
1179    case Type::SubstTemplateTypeParmPack:
1180      llvm_unreachable("Type nodes handled above");
1181
1182    // These types cannot be dependent, so simply check whether the types are
1183    // the same.
1184    case Type::Builtin:
1185    case Type::VariableArray:
1186    case Type::Vector:
1187    case Type::FunctionNoProto:
1188    case Type::Record:
1189    case Type::Enum:
1190    case Type::ObjCObject:
1191    case Type::ObjCInterface:
1192    case Type::ObjCObjectPointer: {
1193      if (TDF & TDF_SkipNonDependent)
1194        return Sema::TDK_Success;
1195
1196      if (TDF & TDF_IgnoreQualifiers) {
1197        Param = Param.getUnqualifiedType();
1198        Arg = Arg.getUnqualifiedType();
1199      }
1200
1201      return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1202    }
1203
1204    //     _Complex T   [placeholder extension]
1205    case Type::Complex:
1206      if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1207        return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1208                                    cast<ComplexType>(Param)->getElementType(),
1209                                    ComplexArg->getElementType(),
1210                                    Info, Deduced, TDF);
1211
1212      return Sema::TDK_NonDeducedMismatch;
1213
1214    //     _Atomic T   [extension]
1215    case Type::Atomic:
1216      if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1217        return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1218                                       cast<AtomicType>(Param)->getValueType(),
1219                                       AtomicArg->getValueType(),
1220                                       Info, Deduced, TDF);
1221
1222      return Sema::TDK_NonDeducedMismatch;
1223
1224    //     T *
1225    case Type::Pointer: {
1226      QualType PointeeType;
1227      if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1228        PointeeType = PointerArg->getPointeeType();
1229      } else if (const ObjCObjectPointerType *PointerArg
1230                   = Arg->getAs<ObjCObjectPointerType>()) {
1231        PointeeType = PointerArg->getPointeeType();
1232      } else {
1233        return Sema::TDK_NonDeducedMismatch;
1234      }
1235
1236      unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1237      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1238                                     cast<PointerType>(Param)->getPointeeType(),
1239                                     PointeeType,
1240                                     Info, Deduced, SubTDF);
1241    }
1242
1243    //     T &
1244    case Type::LValueReference: {
1245      const LValueReferenceType *ReferenceArg = Arg->getAs<LValueReferenceType>();
1246      if (!ReferenceArg)
1247        return Sema::TDK_NonDeducedMismatch;
1248
1249      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1250                           cast<LValueReferenceType>(Param)->getPointeeType(),
1251                           ReferenceArg->getPointeeType(), Info, Deduced, 0);
1252    }
1253
1254    //     T && [C++0x]
1255    case Type::RValueReference: {
1256      const RValueReferenceType *ReferenceArg = Arg->getAs<RValueReferenceType>();
1257      if (!ReferenceArg)
1258        return Sema::TDK_NonDeducedMismatch;
1259
1260      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1261                             cast<RValueReferenceType>(Param)->getPointeeType(),
1262                             ReferenceArg->getPointeeType(),
1263                             Info, Deduced, 0);
1264    }
1265
1266    //     T [] (implied, but not stated explicitly)
1267    case Type::IncompleteArray: {
1268      const IncompleteArrayType *IncompleteArrayArg =
1269        S.Context.getAsIncompleteArrayType(Arg);
1270      if (!IncompleteArrayArg)
1271        return Sema::TDK_NonDeducedMismatch;
1272
1273      unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1274      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1275                    S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1276                    IncompleteArrayArg->getElementType(),
1277                    Info, Deduced, SubTDF);
1278    }
1279
1280    //     T [integer-constant]
1281    case Type::ConstantArray: {
1282      const ConstantArrayType *ConstantArrayArg =
1283        S.Context.getAsConstantArrayType(Arg);
1284      if (!ConstantArrayArg)
1285        return Sema::TDK_NonDeducedMismatch;
1286
1287      const ConstantArrayType *ConstantArrayParm =
1288        S.Context.getAsConstantArrayType(Param);
1289      if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1290        return Sema::TDK_NonDeducedMismatch;
1291
1292      unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1293      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1294                                           ConstantArrayParm->getElementType(),
1295                                           ConstantArrayArg->getElementType(),
1296                                           Info, Deduced, SubTDF);
1297    }
1298
1299    //     type [i]
1300    case Type::DependentSizedArray: {
1301      const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1302      if (!ArrayArg)
1303        return Sema::TDK_NonDeducedMismatch;
1304
1305      unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1306
1307      // Check the element type of the arrays
1308      const DependentSizedArrayType *DependentArrayParm
1309        = S.Context.getAsDependentSizedArrayType(Param);
1310      if (Sema::TemplateDeductionResult Result
1311            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1312                                          DependentArrayParm->getElementType(),
1313                                          ArrayArg->getElementType(),
1314                                          Info, Deduced, SubTDF))
1315        return Result;
1316
1317      // Determine the array bound is something we can deduce.
1318      NonTypeTemplateParmDecl *NTTP
1319        = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1320      if (!NTTP)
1321        return Sema::TDK_Success;
1322
1323      // We can perform template argument deduction for the given non-type
1324      // template parameter.
1325      assert(NTTP->getDepth() == 0 &&
1326             "Cannot deduce non-type template argument at depth > 0");
1327      if (const ConstantArrayType *ConstantArrayArg
1328            = dyn_cast<ConstantArrayType>(ArrayArg)) {
1329        llvm::APSInt Size(ConstantArrayArg->getSize());
1330        return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1331                                             S.Context.getSizeType(),
1332                                             /*ArrayBound=*/true,
1333                                             Info, Deduced);
1334      }
1335      if (const DependentSizedArrayType *DependentArrayArg
1336            = dyn_cast<DependentSizedArrayType>(ArrayArg))
1337        if (DependentArrayArg->getSizeExpr())
1338          return DeduceNonTypeTemplateArgument(S, NTTP,
1339                                               DependentArrayArg->getSizeExpr(),
1340                                               Info, Deduced);
1341
1342      // Incomplete type does not match a dependently-sized array type
1343      return Sema::TDK_NonDeducedMismatch;
1344    }
1345
1346    //     type(*)(T)
1347    //     T(*)()
1348    //     T(*)(T)
1349    case Type::FunctionProto: {
1350      unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1351      const FunctionProtoType *FunctionProtoArg =
1352        dyn_cast<FunctionProtoType>(Arg);
1353      if (!FunctionProtoArg)
1354        return Sema::TDK_NonDeducedMismatch;
1355
1356      const FunctionProtoType *FunctionProtoParam =
1357        cast<FunctionProtoType>(Param);
1358
1359      if (FunctionProtoParam->getTypeQuals()
1360            != FunctionProtoArg->getTypeQuals() ||
1361          FunctionProtoParam->getRefQualifier()
1362            != FunctionProtoArg->getRefQualifier() ||
1363          FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1364        return Sema::TDK_NonDeducedMismatch;
1365
1366      // Check return types.
1367      if (Sema::TemplateDeductionResult Result
1368            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1369                                            FunctionProtoParam->getResultType(),
1370                                            FunctionProtoArg->getResultType(),
1371                                            Info, Deduced, 0))
1372        return Result;
1373
1374      return DeduceTemplateArguments(S, TemplateParams,
1375                                     FunctionProtoParam->arg_type_begin(),
1376                                     FunctionProtoParam->getNumArgs(),
1377                                     FunctionProtoArg->arg_type_begin(),
1378                                     FunctionProtoArg->getNumArgs(),
1379                                     Info, Deduced, SubTDF);
1380    }
1381
1382    case Type::InjectedClassName: {
1383      // Treat a template's injected-class-name as if the template
1384      // specialization type had been used.
1385      Param = cast<InjectedClassNameType>(Param)
1386        ->getInjectedSpecializationType();
1387      assert(isa<TemplateSpecializationType>(Param) &&
1388             "injected class name is not a template specialization type");
1389      // fall through
1390    }
1391
1392    //     template-name<T> (where template-name refers to a class template)
1393    //     template-name<i>
1394    //     TT<T>
1395    //     TT<i>
1396    //     TT<>
1397    case Type::TemplateSpecialization: {
1398      const TemplateSpecializationType *SpecParam
1399        = cast<TemplateSpecializationType>(Param);
1400
1401      // Try to deduce template arguments from the template-id.
1402      Sema::TemplateDeductionResult Result
1403        = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1404                                  Info, Deduced);
1405
1406      if (Result && (TDF & TDF_DerivedClass)) {
1407        // C++ [temp.deduct.call]p3b3:
1408        //   If P is a class, and P has the form template-id, then A can be a
1409        //   derived class of the deduced A. Likewise, if P is a pointer to a
1410        //   class of the form template-id, A can be a pointer to a derived
1411        //   class pointed to by the deduced A.
1412        //
1413        // More importantly:
1414        //   These alternatives are considered only if type deduction would
1415        //   otherwise fail.
1416        if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1417          // We cannot inspect base classes as part of deduction when the type
1418          // is incomplete, so either instantiate any templates necessary to
1419          // complete the type, or skip over it if it cannot be completed.
1420          if (S.RequireCompleteType(Info.getLocation(), Arg, 0))
1421            return Result;
1422
1423          // Use data recursion to crawl through the list of base classes.
1424          // Visited contains the set of nodes we have already visited, while
1425          // ToVisit is our stack of records that we still need to visit.
1426          llvm::SmallPtrSet<const RecordType *, 8> Visited;
1427          SmallVector<const RecordType *, 8> ToVisit;
1428          ToVisit.push_back(RecordT);
1429          bool Successful = false;
1430          SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1431                                                              Deduced.end());
1432          while (!ToVisit.empty()) {
1433            // Retrieve the next class in the inheritance hierarchy.
1434            const RecordType *NextT = ToVisit.back();
1435            ToVisit.pop_back();
1436
1437            // If we have already seen this type, skip it.
1438            if (!Visited.insert(NextT))
1439              continue;
1440
1441            // If this is a base class, try to perform template argument
1442            // deduction from it.
1443            if (NextT != RecordT) {
1444              TemplateDeductionInfo BaseInfo(Info.getLocation());
1445              Sema::TemplateDeductionResult BaseResult
1446                = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1447                                          QualType(NextT, 0), BaseInfo,
1448                                          Deduced);
1449
1450              // If template argument deduction for this base was successful,
1451              // note that we had some success. Otherwise, ignore any deductions
1452              // from this base class.
1453              if (BaseResult == Sema::TDK_Success) {
1454                Successful = true;
1455                DeducedOrig.clear();
1456                DeducedOrig.append(Deduced.begin(), Deduced.end());
1457                Info.Param = BaseInfo.Param;
1458                Info.FirstArg = BaseInfo.FirstArg;
1459                Info.SecondArg = BaseInfo.SecondArg;
1460              }
1461              else
1462                Deduced = DeducedOrig;
1463            }
1464
1465            // Visit base classes
1466            CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1467            for (CXXRecordDecl::base_class_iterator Base = Next->bases_begin(),
1468                                                 BaseEnd = Next->bases_end();
1469                 Base != BaseEnd; ++Base) {
1470              assert(Base->getType()->isRecordType() &&
1471                     "Base class that isn't a record?");
1472              ToVisit.push_back(Base->getType()->getAs<RecordType>());
1473            }
1474          }
1475
1476          if (Successful)
1477            return Sema::TDK_Success;
1478        }
1479
1480      }
1481
1482      return Result;
1483    }
1484
1485    //     T type::*
1486    //     T T::*
1487    //     T (type::*)()
1488    //     type (T::*)()
1489    //     type (type::*)(T)
1490    //     type (T::*)(T)
1491    //     T (type::*)(T)
1492    //     T (T::*)()
1493    //     T (T::*)(T)
1494    case Type::MemberPointer: {
1495      const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1496      const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1497      if (!MemPtrArg)
1498        return Sema::TDK_NonDeducedMismatch;
1499
1500      if (Sema::TemplateDeductionResult Result
1501            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1502                                                 MemPtrParam->getPointeeType(),
1503                                                 MemPtrArg->getPointeeType(),
1504                                                 Info, Deduced,
1505                                                 TDF & TDF_IgnoreQualifiers))
1506        return Result;
1507
1508      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1509                                           QualType(MemPtrParam->getClass(), 0),
1510                                           QualType(MemPtrArg->getClass(), 0),
1511                                           Info, Deduced,
1512                                           TDF & TDF_IgnoreQualifiers);
1513    }
1514
1515    //     (clang extension)
1516    //
1517    //     type(^)(T)
1518    //     T(^)()
1519    //     T(^)(T)
1520    case Type::BlockPointer: {
1521      const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1522      const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1523
1524      if (!BlockPtrArg)
1525        return Sema::TDK_NonDeducedMismatch;
1526
1527      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1528                                                BlockPtrParam->getPointeeType(),
1529                                                BlockPtrArg->getPointeeType(),
1530                                                Info, Deduced, 0);
1531    }
1532
1533    //     (clang extension)
1534    //
1535    //     T __attribute__(((ext_vector_type(<integral constant>))))
1536    case Type::ExtVector: {
1537      const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1538      if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1539        // Make sure that the vectors have the same number of elements.
1540        if (VectorParam->getNumElements() != VectorArg->getNumElements())
1541          return Sema::TDK_NonDeducedMismatch;
1542
1543        // Perform deduction on the element types.
1544        return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1545                                                  VectorParam->getElementType(),
1546                                                  VectorArg->getElementType(),
1547                                                  Info, Deduced, TDF);
1548      }
1549
1550      if (const DependentSizedExtVectorType *VectorArg
1551                                = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1552        // We can't check the number of elements, since the argument has a
1553        // dependent number of elements. This can only occur during partial
1554        // ordering.
1555
1556        // Perform deduction on the element types.
1557        return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1558                                                  VectorParam->getElementType(),
1559                                                  VectorArg->getElementType(),
1560                                                  Info, Deduced, TDF);
1561      }
1562
1563      return Sema::TDK_NonDeducedMismatch;
1564    }
1565
1566    //     (clang extension)
1567    //
1568    //     T __attribute__(((ext_vector_type(N))))
1569    case Type::DependentSizedExtVector: {
1570      const DependentSizedExtVectorType *VectorParam
1571        = cast<DependentSizedExtVectorType>(Param);
1572
1573      if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1574        // Perform deduction on the element types.
1575        if (Sema::TemplateDeductionResult Result
1576              = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1577                                                  VectorParam->getElementType(),
1578                                                   VectorArg->getElementType(),
1579                                                   Info, Deduced, TDF))
1580          return Result;
1581
1582        // Perform deduction on the vector size, if we can.
1583        NonTypeTemplateParmDecl *NTTP
1584          = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1585        if (!NTTP)
1586          return Sema::TDK_Success;
1587
1588        llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1589        ArgSize = VectorArg->getNumElements();
1590        return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1591                                             false, Info, Deduced);
1592      }
1593
1594      if (const DependentSizedExtVectorType *VectorArg
1595                                = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1596        // Perform deduction on the element types.
1597        if (Sema::TemplateDeductionResult Result
1598            = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1599                                                 VectorParam->getElementType(),
1600                                                 VectorArg->getElementType(),
1601                                                 Info, Deduced, TDF))
1602          return Result;
1603
1604        // Perform deduction on the vector size, if we can.
1605        NonTypeTemplateParmDecl *NTTP
1606          = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1607        if (!NTTP)
1608          return Sema::TDK_Success;
1609
1610        return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1611                                             Info, Deduced);
1612      }
1613
1614      return Sema::TDK_NonDeducedMismatch;
1615    }
1616
1617    case Type::TypeOfExpr:
1618    case Type::TypeOf:
1619    case Type::DependentName:
1620    case Type::UnresolvedUsing:
1621    case Type::Decltype:
1622    case Type::UnaryTransform:
1623    case Type::Auto:
1624    case Type::DependentTemplateSpecialization:
1625    case Type::PackExpansion:
1626      // No template argument deduction for these types
1627      return Sema::TDK_Success;
1628  }
1629
1630  llvm_unreachable("Invalid Type Class!");
1631}
1632
1633static Sema::TemplateDeductionResult
1634DeduceTemplateArguments(Sema &S,
1635                        TemplateParameterList *TemplateParams,
1636                        const TemplateArgument &Param,
1637                        TemplateArgument Arg,
1638                        TemplateDeductionInfo &Info,
1639                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1640  // If the template argument is a pack expansion, perform template argument
1641  // deduction against the pattern of that expansion. This only occurs during
1642  // partial ordering.
1643  if (Arg.isPackExpansion())
1644    Arg = Arg.getPackExpansionPattern();
1645
1646  switch (Param.getKind()) {
1647  case TemplateArgument::Null:
1648    llvm_unreachable("Null template argument in parameter list");
1649
1650  case TemplateArgument::Type:
1651    if (Arg.getKind() == TemplateArgument::Type)
1652      return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1653                                                Param.getAsType(),
1654                                                Arg.getAsType(),
1655                                                Info, Deduced, 0);
1656    Info.FirstArg = Param;
1657    Info.SecondArg = Arg;
1658    return Sema::TDK_NonDeducedMismatch;
1659
1660  case TemplateArgument::Template:
1661    if (Arg.getKind() == TemplateArgument::Template)
1662      return DeduceTemplateArguments(S, TemplateParams,
1663                                     Param.getAsTemplate(),
1664                                     Arg.getAsTemplate(), Info, Deduced);
1665    Info.FirstArg = Param;
1666    Info.SecondArg = Arg;
1667    return Sema::TDK_NonDeducedMismatch;
1668
1669  case TemplateArgument::TemplateExpansion:
1670    llvm_unreachable("caller should handle pack expansions");
1671
1672  case TemplateArgument::Declaration:
1673    if (Arg.getKind() == TemplateArgument::Declaration &&
1674        isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()) &&
1675        Param.isDeclForReferenceParam() == Arg.isDeclForReferenceParam())
1676      return Sema::TDK_Success;
1677
1678    Info.FirstArg = Param;
1679    Info.SecondArg = Arg;
1680    return Sema::TDK_NonDeducedMismatch;
1681
1682  case TemplateArgument::NullPtr:
1683    if (Arg.getKind() == TemplateArgument::NullPtr &&
1684        S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1685      return Sema::TDK_Success;
1686
1687    Info.FirstArg = Param;
1688    Info.SecondArg = Arg;
1689    return Sema::TDK_NonDeducedMismatch;
1690
1691  case TemplateArgument::Integral:
1692    if (Arg.getKind() == TemplateArgument::Integral) {
1693      if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1694        return Sema::TDK_Success;
1695
1696      Info.FirstArg = Param;
1697      Info.SecondArg = Arg;
1698      return Sema::TDK_NonDeducedMismatch;
1699    }
1700
1701    if (Arg.getKind() == TemplateArgument::Expression) {
1702      Info.FirstArg = Param;
1703      Info.SecondArg = Arg;
1704      return Sema::TDK_NonDeducedMismatch;
1705    }
1706
1707    Info.FirstArg = Param;
1708    Info.SecondArg = Arg;
1709    return Sema::TDK_NonDeducedMismatch;
1710
1711  case TemplateArgument::Expression: {
1712    if (NonTypeTemplateParmDecl *NTTP
1713          = getDeducedParameterFromExpr(Param.getAsExpr())) {
1714      if (Arg.getKind() == TemplateArgument::Integral)
1715        return DeduceNonTypeTemplateArgument(S, NTTP,
1716                                             Arg.getAsIntegral(),
1717                                             Arg.getIntegralType(),
1718                                             /*ArrayBound=*/false,
1719                                             Info, Deduced);
1720      if (Arg.getKind() == TemplateArgument::Expression)
1721        return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1722                                             Info, Deduced);
1723      if (Arg.getKind() == TemplateArgument::Declaration)
1724        return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1725                                             Info, Deduced);
1726
1727      Info.FirstArg = Param;
1728      Info.SecondArg = Arg;
1729      return Sema::TDK_NonDeducedMismatch;
1730    }
1731
1732    // Can't deduce anything, but that's okay.
1733    return Sema::TDK_Success;
1734  }
1735  case TemplateArgument::Pack:
1736    llvm_unreachable("Argument packs should be expanded by the caller!");
1737  }
1738
1739  llvm_unreachable("Invalid TemplateArgument Kind!");
1740}
1741
1742/// \brief Determine whether there is a template argument to be used for
1743/// deduction.
1744///
1745/// This routine "expands" argument packs in-place, overriding its input
1746/// parameters so that \c Args[ArgIdx] will be the available template argument.
1747///
1748/// \returns true if there is another template argument (which will be at
1749/// \c Args[ArgIdx]), false otherwise.
1750static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1751                                            unsigned &ArgIdx,
1752                                            unsigned &NumArgs) {
1753  if (ArgIdx == NumArgs)
1754    return false;
1755
1756  const TemplateArgument &Arg = Args[ArgIdx];
1757  if (Arg.getKind() != TemplateArgument::Pack)
1758    return true;
1759
1760  assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1761  Args = Arg.pack_begin();
1762  NumArgs = Arg.pack_size();
1763  ArgIdx = 0;
1764  return ArgIdx < NumArgs;
1765}
1766
1767/// \brief Determine whether the given set of template arguments has a pack
1768/// expansion that is not the last template argument.
1769static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1770                                      unsigned NumArgs) {
1771  unsigned ArgIdx = 0;
1772  while (ArgIdx < NumArgs) {
1773    const TemplateArgument &Arg = Args[ArgIdx];
1774
1775    // Unwrap argument packs.
1776    if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1777      Args = Arg.pack_begin();
1778      NumArgs = Arg.pack_size();
1779      ArgIdx = 0;
1780      continue;
1781    }
1782
1783    ++ArgIdx;
1784    if (ArgIdx == NumArgs)
1785      return false;
1786
1787    if (Arg.isPackExpansion())
1788      return true;
1789  }
1790
1791  return false;
1792}
1793
1794static Sema::TemplateDeductionResult
1795DeduceTemplateArguments(Sema &S,
1796                        TemplateParameterList *TemplateParams,
1797                        const TemplateArgument *Params, unsigned NumParams,
1798                        const TemplateArgument *Args, unsigned NumArgs,
1799                        TemplateDeductionInfo &Info,
1800                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1801  // C++0x [temp.deduct.type]p9:
1802  //   If the template argument list of P contains a pack expansion that is not
1803  //   the last template argument, the entire template argument list is a
1804  //   non-deduced context.
1805  if (hasPackExpansionBeforeEnd(Params, NumParams))
1806    return Sema::TDK_Success;
1807
1808  // C++0x [temp.deduct.type]p9:
1809  //   If P has a form that contains <T> or <i>, then each argument Pi of the
1810  //   respective template argument list P is compared with the corresponding
1811  //   argument Ai of the corresponding template argument list of A.
1812  unsigned ArgIdx = 0, ParamIdx = 0;
1813  for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1814       ++ParamIdx) {
1815    if (!Params[ParamIdx].isPackExpansion()) {
1816      // The simple case: deduce template arguments by matching Pi and Ai.
1817
1818      // Check whether we have enough arguments.
1819      if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1820        return Sema::TDK_Success;
1821
1822      if (Args[ArgIdx].isPackExpansion()) {
1823        // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1824        // but applied to pack expansions that are template arguments.
1825        return Sema::TDK_MiscellaneousDeductionFailure;
1826      }
1827
1828      // Perform deduction for this Pi/Ai pair.
1829      if (Sema::TemplateDeductionResult Result
1830            = DeduceTemplateArguments(S, TemplateParams,
1831                                      Params[ParamIdx], Args[ArgIdx],
1832                                      Info, Deduced))
1833        return Result;
1834
1835      // Move to the next argument.
1836      ++ArgIdx;
1837      continue;
1838    }
1839
1840    // The parameter is a pack expansion.
1841
1842    // C++0x [temp.deduct.type]p9:
1843    //   If Pi is a pack expansion, then the pattern of Pi is compared with
1844    //   each remaining argument in the template argument list of A. Each
1845    //   comparison deduces template arguments for subsequent positions in the
1846    //   template parameter packs expanded by Pi.
1847    TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1848
1849    // Compute the set of template parameter indices that correspond to
1850    // parameter packs expanded by the pack expansion.
1851    SmallVector<unsigned, 2> PackIndices;
1852    {
1853      llvm::SmallBitVector SawIndices(TemplateParams->size());
1854      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1855      S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
1856      for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
1857        unsigned Depth, Index;
1858        llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
1859        if (Depth == 0 && !SawIndices[Index]) {
1860          SawIndices[Index] = true;
1861          PackIndices.push_back(Index);
1862        }
1863      }
1864    }
1865    assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
1866
1867    // FIXME: If there are no remaining arguments, we can bail out early
1868    // and set any deduced parameter packs to an empty argument pack.
1869    // The latter part of this is a (minor) correctness issue.
1870
1871    // Save the deduced template arguments for each parameter pack expanded
1872    // by this pack expansion, then clear out the deduction.
1873    SmallVector<DeducedTemplateArgument, 2>
1874      SavedPacks(PackIndices.size());
1875    NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size());
1876    PrepareArgumentPackDeduction(S, Deduced, PackIndices, SavedPacks,
1877                                 NewlyDeducedPacks);
1878
1879    // Keep track of the deduced template arguments for each parameter pack
1880    // expanded by this pack expansion (the outer index) and for each
1881    // template argument (the inner SmallVectors).
1882    bool HasAnyArguments = false;
1883    while (hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs)) {
1884      HasAnyArguments = true;
1885
1886      // Deduce template arguments from the pattern.
1887      if (Sema::TemplateDeductionResult Result
1888            = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1889                                      Info, Deduced))
1890        return Result;
1891
1892      // Capture the deduced template arguments for each parameter pack expanded
1893      // by this pack expansion, add them to the list of arguments we've deduced
1894      // for that pack, then clear out the deduced argument.
1895      for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
1896        DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
1897        if (!DeducedArg.isNull()) {
1898          NewlyDeducedPacks[I].push_back(DeducedArg);
1899          DeducedArg = DeducedTemplateArgument();
1900        }
1901      }
1902
1903      ++ArgIdx;
1904    }
1905
1906    // Build argument packs for each of the parameter packs expanded by this
1907    // pack expansion.
1908    if (Sema::TemplateDeductionResult Result
1909          = FinishArgumentPackDeduction(S, TemplateParams, HasAnyArguments,
1910                                        Deduced, PackIndices, SavedPacks,
1911                                        NewlyDeducedPacks, Info))
1912      return Result;
1913  }
1914
1915  return Sema::TDK_Success;
1916}
1917
1918static Sema::TemplateDeductionResult
1919DeduceTemplateArguments(Sema &S,
1920                        TemplateParameterList *TemplateParams,
1921                        const TemplateArgumentList &ParamList,
1922                        const TemplateArgumentList &ArgList,
1923                        TemplateDeductionInfo &Info,
1924                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1925  return DeduceTemplateArguments(S, TemplateParams,
1926                                 ParamList.data(), ParamList.size(),
1927                                 ArgList.data(), ArgList.size(),
1928                                 Info, Deduced);
1929}
1930
1931/// \brief Determine whether two template arguments are the same.
1932static bool isSameTemplateArg(ASTContext &Context,
1933                              const TemplateArgument &X,
1934                              const TemplateArgument &Y) {
1935  if (X.getKind() != Y.getKind())
1936    return false;
1937
1938  switch (X.getKind()) {
1939    case TemplateArgument::Null:
1940      llvm_unreachable("Comparing NULL template argument");
1941
1942    case TemplateArgument::Type:
1943      return Context.getCanonicalType(X.getAsType()) ==
1944             Context.getCanonicalType(Y.getAsType());
1945
1946    case TemplateArgument::Declaration:
1947      return isSameDeclaration(X.getAsDecl(), Y.getAsDecl()) &&
1948             X.isDeclForReferenceParam() == Y.isDeclForReferenceParam();
1949
1950    case TemplateArgument::NullPtr:
1951      return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1952
1953    case TemplateArgument::Template:
1954    case TemplateArgument::TemplateExpansion:
1955      return Context.getCanonicalTemplateName(
1956                    X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1957             Context.getCanonicalTemplateName(
1958                    Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1959
1960    case TemplateArgument::Integral:
1961      return X.getAsIntegral() == Y.getAsIntegral();
1962
1963    case TemplateArgument::Expression: {
1964      llvm::FoldingSetNodeID XID, YID;
1965      X.getAsExpr()->Profile(XID, Context, true);
1966      Y.getAsExpr()->Profile(YID, Context, true);
1967      return XID == YID;
1968    }
1969
1970    case TemplateArgument::Pack:
1971      if (X.pack_size() != Y.pack_size())
1972        return false;
1973
1974      for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1975                                        XPEnd = X.pack_end(),
1976                                           YP = Y.pack_begin();
1977           XP != XPEnd; ++XP, ++YP)
1978        if (!isSameTemplateArg(Context, *XP, *YP))
1979          return false;
1980
1981      return true;
1982  }
1983
1984  llvm_unreachable("Invalid TemplateArgument Kind!");
1985}
1986
1987/// \brief Allocate a TemplateArgumentLoc where all locations have
1988/// been initialized to the given location.
1989///
1990/// \param S The semantic analysis object.
1991///
1992/// \param Arg The template argument we are producing template argument
1993/// location information for.
1994///
1995/// \param NTTPType For a declaration template argument, the type of
1996/// the non-type template parameter that corresponds to this template
1997/// argument.
1998///
1999/// \param Loc The source location to use for the resulting template
2000/// argument.
2001static TemplateArgumentLoc
2002getTrivialTemplateArgumentLoc(Sema &S,
2003                              const TemplateArgument &Arg,
2004                              QualType NTTPType,
2005                              SourceLocation Loc) {
2006  switch (Arg.getKind()) {
2007  case TemplateArgument::Null:
2008    llvm_unreachable("Can't get a NULL template argument here");
2009
2010  case TemplateArgument::Type:
2011    return TemplateArgumentLoc(Arg,
2012                     S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2013
2014  case TemplateArgument::Declaration: {
2015    Expr *E
2016      = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2017          .takeAs<Expr>();
2018    return TemplateArgumentLoc(TemplateArgument(E), E);
2019  }
2020
2021  case TemplateArgument::NullPtr: {
2022    Expr *E
2023      = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2024          .takeAs<Expr>();
2025    return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2026                               E);
2027  }
2028
2029  case TemplateArgument::Integral: {
2030    Expr *E
2031      = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).takeAs<Expr>();
2032    return TemplateArgumentLoc(TemplateArgument(E), E);
2033  }
2034
2035    case TemplateArgument::Template:
2036    case TemplateArgument::TemplateExpansion: {
2037      NestedNameSpecifierLocBuilder Builder;
2038      TemplateName Template = Arg.getAsTemplate();
2039      if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2040        Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2041      else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
2042        Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2043
2044      if (Arg.getKind() == TemplateArgument::Template)
2045        return TemplateArgumentLoc(Arg,
2046                                   Builder.getWithLocInContext(S.Context),
2047                                   Loc);
2048
2049
2050      return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2051                                 Loc, Loc);
2052    }
2053
2054  case TemplateArgument::Expression:
2055    return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2056
2057  case TemplateArgument::Pack:
2058    return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2059  }
2060
2061  llvm_unreachable("Invalid TemplateArgument Kind!");
2062}
2063
2064
2065/// \brief Convert the given deduced template argument and add it to the set of
2066/// fully-converted template arguments.
2067static bool
2068ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2069                               DeducedTemplateArgument Arg,
2070                               NamedDecl *Template,
2071                               QualType NTTPType,
2072                               unsigned ArgumentPackIndex,
2073                               TemplateDeductionInfo &Info,
2074                               bool InFunctionTemplate,
2075                               SmallVectorImpl<TemplateArgument> &Output) {
2076  if (Arg.getKind() == TemplateArgument::Pack) {
2077    // This is a template argument pack, so check each of its arguments against
2078    // the template parameter.
2079    SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2080    for (TemplateArgument::pack_iterator PA = Arg.pack_begin(),
2081                                      PAEnd = Arg.pack_end();
2082         PA != PAEnd; ++PA) {
2083      // When converting the deduced template argument, append it to the
2084      // general output list. We need to do this so that the template argument
2085      // checking logic has all of the prior template arguments available.
2086      DeducedTemplateArgument InnerArg(*PA);
2087      InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2088      if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2089                                         NTTPType, PackedArgsBuilder.size(),
2090                                         Info, InFunctionTemplate, Output))
2091        return true;
2092
2093      // Move the converted template argument into our argument pack.
2094      PackedArgsBuilder.push_back(Output.back());
2095      Output.pop_back();
2096    }
2097
2098    // Create the resulting argument pack.
2099    Output.push_back(TemplateArgument::CreatePackCopy(S.Context,
2100                                                      PackedArgsBuilder.data(),
2101                                                     PackedArgsBuilder.size()));
2102    return false;
2103  }
2104
2105  // Convert the deduced template argument into a template
2106  // argument that we can check, almost as if the user had written
2107  // the template argument explicitly.
2108  TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2109                                                             Info.getLocation());
2110
2111  // Check the template argument, converting it as necessary.
2112  return S.CheckTemplateArgument(Param, ArgLoc,
2113                                 Template,
2114                                 Template->getLocation(),
2115                                 Template->getSourceRange().getEnd(),
2116                                 ArgumentPackIndex,
2117                                 Output,
2118                                 InFunctionTemplate
2119                                  ? (Arg.wasDeducedFromArrayBound()
2120                                       ? Sema::CTAK_DeducedFromArrayBound
2121                                       : Sema::CTAK_Deduced)
2122                                 : Sema::CTAK_Specified);
2123}
2124
2125/// Complete template argument deduction for a class template partial
2126/// specialization.
2127static Sema::TemplateDeductionResult
2128FinishTemplateArgumentDeduction(Sema &S,
2129                                ClassTemplatePartialSpecializationDecl *Partial,
2130                                const TemplateArgumentList &TemplateArgs,
2131                      SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2132                                TemplateDeductionInfo &Info) {
2133  // Unevaluated SFINAE context.
2134  EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2135  Sema::SFINAETrap Trap(S);
2136
2137  Sema::ContextRAII SavedContext(S, Partial);
2138
2139  // C++ [temp.deduct.type]p2:
2140  //   [...] or if any template argument remains neither deduced nor
2141  //   explicitly specified, template argument deduction fails.
2142  SmallVector<TemplateArgument, 4> Builder;
2143  TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2144  for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2145    NamedDecl *Param = PartialParams->getParam(I);
2146    if (Deduced[I].isNull()) {
2147      Info.Param = makeTemplateParameter(Param);
2148      return Sema::TDK_Incomplete;
2149    }
2150
2151    // We have deduced this argument, so it still needs to be
2152    // checked and converted.
2153
2154    // First, for a non-type template parameter type that is
2155    // initialized by a declaration, we need the type of the
2156    // corresponding non-type template parameter.
2157    QualType NTTPType;
2158    if (NonTypeTemplateParmDecl *NTTP
2159                                  = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2160      NTTPType = NTTP->getType();
2161      if (NTTPType->isDependentType()) {
2162        TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2163                                          Builder.data(), Builder.size());
2164        NTTPType = S.SubstType(NTTPType,
2165                               MultiLevelTemplateArgumentList(TemplateArgs),
2166                               NTTP->getLocation(),
2167                               NTTP->getDeclName());
2168        if (NTTPType.isNull()) {
2169          Info.Param = makeTemplateParameter(Param);
2170          // FIXME: These template arguments are temporary. Free them!
2171          Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2172                                                      Builder.data(),
2173                                                      Builder.size()));
2174          return Sema::TDK_SubstitutionFailure;
2175        }
2176      }
2177    }
2178
2179    if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2180                                       Partial, NTTPType, 0, Info, false,
2181                                       Builder)) {
2182      Info.Param = makeTemplateParameter(Param);
2183      // FIXME: These template arguments are temporary. Free them!
2184      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2185                                                  Builder.size()));
2186      return Sema::TDK_SubstitutionFailure;
2187    }
2188  }
2189
2190  // Form the template argument list from the deduced template arguments.
2191  TemplateArgumentList *DeducedArgumentList
2192    = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2193                                       Builder.size());
2194
2195  Info.reset(DeducedArgumentList);
2196
2197  // Substitute the deduced template arguments into the template
2198  // arguments of the class template partial specialization, and
2199  // verify that the instantiated template arguments are both valid
2200  // and are equivalent to the template arguments originally provided
2201  // to the class template.
2202  LocalInstantiationScope InstScope(S);
2203  ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2204  const TemplateArgumentLoc *PartialTemplateArgs
2205    = Partial->getTemplateArgsAsWritten();
2206
2207  // Note that we don't provide the langle and rangle locations.
2208  TemplateArgumentListInfo InstArgs;
2209
2210  if (S.Subst(PartialTemplateArgs,
2211              Partial->getNumTemplateArgsAsWritten(),
2212              InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2213    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2214    if (ParamIdx >= Partial->getTemplateParameters()->size())
2215      ParamIdx = Partial->getTemplateParameters()->size() - 1;
2216
2217    Decl *Param
2218      = const_cast<NamedDecl *>(
2219                          Partial->getTemplateParameters()->getParam(ParamIdx));
2220    Info.Param = makeTemplateParameter(Param);
2221    Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2222    return Sema::TDK_SubstitutionFailure;
2223  }
2224
2225  SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2226  if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2227                                  InstArgs, false, ConvertedInstArgs))
2228    return Sema::TDK_SubstitutionFailure;
2229
2230  TemplateParameterList *TemplateParams
2231    = ClassTemplate->getTemplateParameters();
2232  for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2233    TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2234    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2235      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2236      Info.FirstArg = TemplateArgs[I];
2237      Info.SecondArg = InstArg;
2238      return Sema::TDK_NonDeducedMismatch;
2239    }
2240  }
2241
2242  if (Trap.hasErrorOccurred())
2243    return Sema::TDK_SubstitutionFailure;
2244
2245  return Sema::TDK_Success;
2246}
2247
2248/// \brief Perform template argument deduction to determine whether
2249/// the given template arguments match the given class template
2250/// partial specialization per C++ [temp.class.spec.match].
2251Sema::TemplateDeductionResult
2252Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2253                              const TemplateArgumentList &TemplateArgs,
2254                              TemplateDeductionInfo &Info) {
2255  if (Partial->isInvalidDecl())
2256    return TDK_Invalid;
2257
2258  // C++ [temp.class.spec.match]p2:
2259  //   A partial specialization matches a given actual template
2260  //   argument list if the template arguments of the partial
2261  //   specialization can be deduced from the actual template argument
2262  //   list (14.8.2).
2263
2264  // Unevaluated SFINAE context.
2265  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2266  SFINAETrap Trap(*this);
2267
2268  SmallVector<DeducedTemplateArgument, 4> Deduced;
2269  Deduced.resize(Partial->getTemplateParameters()->size());
2270  if (TemplateDeductionResult Result
2271        = ::DeduceTemplateArguments(*this,
2272                                    Partial->getTemplateParameters(),
2273                                    Partial->getTemplateArgs(),
2274                                    TemplateArgs, Info, Deduced))
2275    return Result;
2276
2277  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2278  InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
2279                             DeducedArgs, Info);
2280  if (Inst)
2281    return TDK_InstantiationDepth;
2282
2283  if (Trap.hasErrorOccurred())
2284    return Sema::TDK_SubstitutionFailure;
2285
2286  return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2287                                           Deduced, Info);
2288}
2289
2290/// Complete template argument deduction for a variable template partial
2291/// specialization.
2292/// TODO: Unify with ClassTemplatePartialSpecializationDecl version.
2293static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2294    Sema &S, VarTemplatePartialSpecializationDecl *Partial,
2295    const TemplateArgumentList &TemplateArgs,
2296    SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2297    TemplateDeductionInfo &Info) {
2298  // Unevaluated SFINAE context.
2299  EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2300  Sema::SFINAETrap Trap(S);
2301
2302  // C++ [temp.deduct.type]p2:
2303  //   [...] or if any template argument remains neither deduced nor
2304  //   explicitly specified, template argument deduction fails.
2305  SmallVector<TemplateArgument, 4> Builder;
2306  TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2307  for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2308    NamedDecl *Param = PartialParams->getParam(I);
2309    if (Deduced[I].isNull()) {
2310      Info.Param = makeTemplateParameter(Param);
2311      return Sema::TDK_Incomplete;
2312    }
2313
2314    // We have deduced this argument, so it still needs to be
2315    // checked and converted.
2316
2317    // First, for a non-type template parameter type that is
2318    // initialized by a declaration, we need the type of the
2319    // corresponding non-type template parameter.
2320    QualType NTTPType;
2321    if (NonTypeTemplateParmDecl *NTTP =
2322            dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2323      NTTPType = NTTP->getType();
2324      if (NTTPType->isDependentType()) {
2325        TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2326                                          Builder.data(), Builder.size());
2327        NTTPType =
2328            S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs),
2329                        NTTP->getLocation(), NTTP->getDeclName());
2330        if (NTTPType.isNull()) {
2331          Info.Param = makeTemplateParameter(Param);
2332          // FIXME: These template arguments are temporary. Free them!
2333          Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2334                                                      Builder.size()));
2335          return Sema::TDK_SubstitutionFailure;
2336        }
2337      }
2338    }
2339
2340    if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType,
2341                                       0, Info, false, Builder)) {
2342      Info.Param = makeTemplateParameter(Param);
2343      // FIXME: These template arguments are temporary. Free them!
2344      Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2345                                                  Builder.size()));
2346      return Sema::TDK_SubstitutionFailure;
2347    }
2348  }
2349
2350  // Form the template argument list from the deduced template arguments.
2351  TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy(
2352      S.Context, Builder.data(), Builder.size());
2353
2354  Info.reset(DeducedArgumentList);
2355
2356  // Substitute the deduced template arguments into the template
2357  // arguments of the class template partial specialization, and
2358  // verify that the instantiated template arguments are both valid
2359  // and are equivalent to the template arguments originally provided
2360  // to the class template.
2361  LocalInstantiationScope InstScope(S);
2362  VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate();
2363  const TemplateArgumentLoc *PartialTemplateArgs =
2364      Partial->getTemplateArgsAsWritten();
2365
2366  // Note that we don't provide the langle and rangle locations.
2367  TemplateArgumentListInfo InstArgs;
2368
2369  if (S.Subst(PartialTemplateArgs, Partial->getNumTemplateArgsAsWritten(),
2370              InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2371    unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2372    if (ParamIdx >= Partial->getTemplateParameters()->size())
2373      ParamIdx = Partial->getTemplateParameters()->size() - 1;
2374
2375    Decl *Param = const_cast<NamedDecl *>(
2376        Partial->getTemplateParameters()->getParam(ParamIdx));
2377    Info.Param = makeTemplateParameter(Param);
2378    Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2379    return Sema::TDK_SubstitutionFailure;
2380  }
2381  SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2382  if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs,
2383                                  false, ConvertedInstArgs))
2384    return Sema::TDK_SubstitutionFailure;
2385
2386  TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters();
2387  for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2388    TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2389    if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2390      Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2391      Info.FirstArg = TemplateArgs[I];
2392      Info.SecondArg = InstArg;
2393      return Sema::TDK_NonDeducedMismatch;
2394    }
2395  }
2396
2397  if (Trap.hasErrorOccurred())
2398    return Sema::TDK_SubstitutionFailure;
2399
2400  return Sema::TDK_Success;
2401}
2402
2403/// \brief Perform template argument deduction to determine whether
2404/// the given template arguments match the given variable template
2405/// partial specialization per C++ [temp.class.spec.match].
2406/// TODO: Unify with ClassTemplatePartialSpecializationDecl version.
2407Sema::TemplateDeductionResult
2408Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2409                              const TemplateArgumentList &TemplateArgs,
2410                              TemplateDeductionInfo &Info) {
2411  if (Partial->isInvalidDecl())
2412    return TDK_Invalid;
2413
2414  // C++ [temp.class.spec.match]p2:
2415  //   A partial specialization matches a given actual template
2416  //   argument list if the template arguments of the partial
2417  //   specialization can be deduced from the actual template argument
2418  //   list (14.8.2).
2419
2420  // Unevaluated SFINAE context.
2421  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2422  SFINAETrap Trap(*this);
2423
2424  SmallVector<DeducedTemplateArgument, 4> Deduced;
2425  Deduced.resize(Partial->getTemplateParameters()->size());
2426  if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2427          *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2428          TemplateArgs, Info, Deduced))
2429    return Result;
2430
2431  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2432  InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
2433                             DeducedArgs, Info);
2434  if (Inst)
2435    return TDK_InstantiationDepth;
2436
2437  if (Trap.hasErrorOccurred())
2438    return Sema::TDK_SubstitutionFailure;
2439
2440  return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2441                                           Deduced, Info);
2442}
2443
2444/// \brief Determine whether the given type T is a simple-template-id type.
2445static bool isSimpleTemplateIdType(QualType T) {
2446  if (const TemplateSpecializationType *Spec
2447        = T->getAs<TemplateSpecializationType>())
2448    return Spec->getTemplateName().getAsTemplateDecl() != 0;
2449
2450  return false;
2451}
2452
2453/// \brief Substitute the explicitly-provided template arguments into the
2454/// given function template according to C++ [temp.arg.explicit].
2455///
2456/// \param FunctionTemplate the function template into which the explicit
2457/// template arguments will be substituted.
2458///
2459/// \param ExplicitTemplateArgs the explicitly-specified template
2460/// arguments.
2461///
2462/// \param Deduced the deduced template arguments, which will be populated
2463/// with the converted and checked explicit template arguments.
2464///
2465/// \param ParamTypes will be populated with the instantiated function
2466/// parameters.
2467///
2468/// \param FunctionType if non-NULL, the result type of the function template
2469/// will also be instantiated and the pointed-to value will be updated with
2470/// the instantiated function type.
2471///
2472/// \param Info if substitution fails for any reason, this object will be
2473/// populated with more information about the failure.
2474///
2475/// \returns TDK_Success if substitution was successful, or some failure
2476/// condition.
2477Sema::TemplateDeductionResult
2478Sema::SubstituteExplicitTemplateArguments(
2479                                      FunctionTemplateDecl *FunctionTemplate,
2480                               TemplateArgumentListInfo &ExplicitTemplateArgs,
2481                       SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2482                                 SmallVectorImpl<QualType> &ParamTypes,
2483                                          QualType *FunctionType,
2484                                          TemplateDeductionInfo &Info) {
2485  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2486  TemplateParameterList *TemplateParams
2487    = FunctionTemplate->getTemplateParameters();
2488
2489  if (ExplicitTemplateArgs.size() == 0) {
2490    // No arguments to substitute; just copy over the parameter types and
2491    // fill in the function type.
2492    for (FunctionDecl::param_iterator P = Function->param_begin(),
2493                                   PEnd = Function->param_end();
2494         P != PEnd;
2495         ++P)
2496      ParamTypes.push_back((*P)->getType());
2497
2498    if (FunctionType)
2499      *FunctionType = Function->getType();
2500    return TDK_Success;
2501  }
2502
2503  // Unevaluated SFINAE context.
2504  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2505  SFINAETrap Trap(*this);
2506
2507  // C++ [temp.arg.explicit]p3:
2508  //   Template arguments that are present shall be specified in the
2509  //   declaration order of their corresponding template-parameters. The
2510  //   template argument list shall not specify more template-arguments than
2511  //   there are corresponding template-parameters.
2512  SmallVector<TemplateArgument, 4> Builder;
2513
2514  // Enter a new template instantiation context where we check the
2515  // explicitly-specified template arguments against this function template,
2516  // and then substitute them into the function parameter types.
2517  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2518  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2519                             FunctionTemplate, DeducedArgs,
2520           ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2521                             Info);
2522  if (Inst)
2523    return TDK_InstantiationDepth;
2524
2525  if (CheckTemplateArgumentList(FunctionTemplate,
2526                                SourceLocation(),
2527                                ExplicitTemplateArgs,
2528                                true,
2529                                Builder) || Trap.hasErrorOccurred()) {
2530    unsigned Index = Builder.size();
2531    if (Index >= TemplateParams->size())
2532      Index = TemplateParams->size() - 1;
2533    Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2534    return TDK_InvalidExplicitArguments;
2535  }
2536
2537  // Form the template argument list from the explicitly-specified
2538  // template arguments.
2539  TemplateArgumentList *ExplicitArgumentList
2540    = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2541  Info.reset(ExplicitArgumentList);
2542
2543  // Template argument deduction and the final substitution should be
2544  // done in the context of the templated declaration.  Explicit
2545  // argument substitution, on the other hand, needs to happen in the
2546  // calling context.
2547  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2548
2549  // If we deduced template arguments for a template parameter pack,
2550  // note that the template argument pack is partially substituted and record
2551  // the explicit template arguments. They'll be used as part of deduction
2552  // for this template parameter pack.
2553  for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2554    const TemplateArgument &Arg = Builder[I];
2555    if (Arg.getKind() == TemplateArgument::Pack) {
2556      CurrentInstantiationScope->SetPartiallySubstitutedPack(
2557                                                 TemplateParams->getParam(I),
2558                                                             Arg.pack_begin(),
2559                                                             Arg.pack_size());
2560      break;
2561    }
2562  }
2563
2564  const FunctionProtoType *Proto
2565    = Function->getType()->getAs<FunctionProtoType>();
2566  assert(Proto && "Function template does not have a prototype?");
2567
2568  // Instantiate the types of each of the function parameters given the
2569  // explicitly-specified template arguments. If the function has a trailing
2570  // return type, substitute it after the arguments to ensure we substitute
2571  // in lexical order.
2572  if (Proto->hasTrailingReturn()) {
2573    if (SubstParmTypes(Function->getLocation(),
2574                       Function->param_begin(), Function->getNumParams(),
2575                       MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2576                       ParamTypes))
2577      return TDK_SubstitutionFailure;
2578  }
2579
2580  // Instantiate the return type.
2581  // FIXME: exception-specifications?
2582  QualType ResultType;
2583  {
2584    // C++11 [expr.prim.general]p3:
2585    //   If a declaration declares a member function or member function
2586    //   template of a class X, the expression this is a prvalue of type
2587    //   "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2588    //   and the end of the function-definition, member-declarator, or
2589    //   declarator.
2590    unsigned ThisTypeQuals = 0;
2591    CXXRecordDecl *ThisContext = 0;
2592    if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2593      ThisContext = Method->getParent();
2594      ThisTypeQuals = Method->getTypeQualifiers();
2595    }
2596
2597    CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2598                               getLangOpts().CPlusPlus11);
2599
2600    ResultType = SubstType(Proto->getResultType(),
2601                   MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2602                   Function->getTypeSpecStartLoc(),
2603                   Function->getDeclName());
2604    if (ResultType.isNull() || Trap.hasErrorOccurred())
2605      return TDK_SubstitutionFailure;
2606  }
2607
2608  // Instantiate the types of each of the function parameters given the
2609  // explicitly-specified template arguments if we didn't do so earlier.
2610  if (!Proto->hasTrailingReturn() &&
2611      SubstParmTypes(Function->getLocation(),
2612                     Function->param_begin(), Function->getNumParams(),
2613                     MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2614                     ParamTypes))
2615    return TDK_SubstitutionFailure;
2616
2617  if (FunctionType) {
2618    *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2619                                      Function->getLocation(),
2620                                      Function->getDeclName(),
2621                                      Proto->getExtProtoInfo());
2622    if (FunctionType->isNull() || Trap.hasErrorOccurred())
2623      return TDK_SubstitutionFailure;
2624  }
2625
2626  // C++ [temp.arg.explicit]p2:
2627  //   Trailing template arguments that can be deduced (14.8.2) may be
2628  //   omitted from the list of explicit template-arguments. If all of the
2629  //   template arguments can be deduced, they may all be omitted; in this
2630  //   case, the empty template argument list <> itself may also be omitted.
2631  //
2632  // Take all of the explicitly-specified arguments and put them into
2633  // the set of deduced template arguments. Explicitly-specified
2634  // parameter packs, however, will be set to NULL since the deduction
2635  // mechanisms handle explicitly-specified argument packs directly.
2636  Deduced.reserve(TemplateParams->size());
2637  for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2638    const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2639    if (Arg.getKind() == TemplateArgument::Pack)
2640      Deduced.push_back(DeducedTemplateArgument());
2641    else
2642      Deduced.push_back(Arg);
2643  }
2644
2645  return TDK_Success;
2646}
2647
2648/// \brief Check whether the deduced argument type for a call to a function
2649/// template matches the actual argument type per C++ [temp.deduct.call]p4.
2650static bool
2651CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg,
2652                              QualType DeducedA) {
2653  ASTContext &Context = S.Context;
2654
2655  QualType A = OriginalArg.OriginalArgType;
2656  QualType OriginalParamType = OriginalArg.OriginalParamType;
2657
2658  // Check for type equality (top-level cv-qualifiers are ignored).
2659  if (Context.hasSameUnqualifiedType(A, DeducedA))
2660    return false;
2661
2662  // Strip off references on the argument types; they aren't needed for
2663  // the following checks.
2664  if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2665    DeducedA = DeducedARef->getPointeeType();
2666  if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2667    A = ARef->getPointeeType();
2668
2669  // C++ [temp.deduct.call]p4:
2670  //   [...] However, there are three cases that allow a difference:
2671  //     - If the original P is a reference type, the deduced A (i.e., the
2672  //       type referred to by the reference) can be more cv-qualified than
2673  //       the transformed A.
2674  if (const ReferenceType *OriginalParamRef
2675      = OriginalParamType->getAs<ReferenceType>()) {
2676    // We don't want to keep the reference around any more.
2677    OriginalParamType = OriginalParamRef->getPointeeType();
2678
2679    Qualifiers AQuals = A.getQualifiers();
2680    Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2681
2682    // Under Objective-C++ ARC, the deduced type may have implicitly been
2683    // given strong lifetime. If so, update the original qualifiers to
2684    // include this strong lifetime.
2685    if (S.getLangOpts().ObjCAutoRefCount &&
2686        DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2687        AQuals.getObjCLifetime() == Qualifiers::OCL_None) {
2688      AQuals.setObjCLifetime(Qualifiers::OCL_Strong);
2689    }
2690
2691    if (AQuals == DeducedAQuals) {
2692      // Qualifiers match; there's nothing to do.
2693    } else if (!DeducedAQuals.compatiblyIncludes(AQuals)) {
2694      return true;
2695    } else {
2696      // Qualifiers are compatible, so have the argument type adopt the
2697      // deduced argument type's qualifiers as if we had performed the
2698      // qualification conversion.
2699      A = Context.getQualifiedType(A.getUnqualifiedType(), DeducedAQuals);
2700    }
2701  }
2702
2703  //    - The transformed A can be another pointer or pointer to member
2704  //      type that can be converted to the deduced A via a qualification
2705  //      conversion.
2706  //
2707  // Also allow conversions which merely strip [[noreturn]] from function types
2708  // (recursively) as an extension.
2709  // FIXME: Currently, this doesn't place nicely with qualfication conversions.
2710  bool ObjCLifetimeConversion = false;
2711  QualType ResultTy;
2712  if ((A->isAnyPointerType() || A->isMemberPointerType()) &&
2713      (S.IsQualificationConversion(A, DeducedA, false,
2714                                   ObjCLifetimeConversion) ||
2715       S.IsNoReturnConversion(A, DeducedA, ResultTy)))
2716    return false;
2717
2718
2719  //    - If P is a class and P has the form simple-template-id, then the
2720  //      transformed A can be a derived class of the deduced A. [...]
2721  //     [...] Likewise, if P is a pointer to a class of the form
2722  //      simple-template-id, the transformed A can be a pointer to a
2723  //      derived class pointed to by the deduced A.
2724  if (const PointerType *OriginalParamPtr
2725      = OriginalParamType->getAs<PointerType>()) {
2726    if (const PointerType *DeducedAPtr = DeducedA->getAs<PointerType>()) {
2727      if (const PointerType *APtr = A->getAs<PointerType>()) {
2728        if (A->getPointeeType()->isRecordType()) {
2729          OriginalParamType = OriginalParamPtr->getPointeeType();
2730          DeducedA = DeducedAPtr->getPointeeType();
2731          A = APtr->getPointeeType();
2732        }
2733      }
2734    }
2735  }
2736
2737  if (Context.hasSameUnqualifiedType(A, DeducedA))
2738    return false;
2739
2740  if (A->isRecordType() && isSimpleTemplateIdType(OriginalParamType) &&
2741      S.IsDerivedFrom(A, DeducedA))
2742    return false;
2743
2744  return true;
2745}
2746
2747/// \brief Finish template argument deduction for a function template,
2748/// checking the deduced template arguments for completeness and forming
2749/// the function template specialization.
2750///
2751/// \param OriginalCallArgs If non-NULL, the original call arguments against
2752/// which the deduced argument types should be compared.
2753Sema::TemplateDeductionResult
2754Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2755                       SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2756                                      unsigned NumExplicitlySpecified,
2757                                      FunctionDecl *&Specialization,
2758                                      TemplateDeductionInfo &Info,
2759        SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs) {
2760  TemplateParameterList *TemplateParams
2761    = FunctionTemplate->getTemplateParameters();
2762
2763  // Unevaluated SFINAE context.
2764  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2765  SFINAETrap Trap(*this);
2766
2767  // Enter a new template instantiation context while we instantiate the
2768  // actual function declaration.
2769  SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2770  InstantiatingTemplate Inst(*this, FunctionTemplate->getLocation(),
2771                             FunctionTemplate, DeducedArgs,
2772              ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2773                             Info);
2774  if (Inst)
2775    return TDK_InstantiationDepth;
2776
2777  ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2778
2779  // C++ [temp.deduct.type]p2:
2780  //   [...] or if any template argument remains neither deduced nor
2781  //   explicitly specified, template argument deduction fails.
2782  SmallVector<TemplateArgument, 4> Builder;
2783  for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2784    NamedDecl *Param = TemplateParams->getParam(I);
2785
2786    if (!Deduced[I].isNull()) {
2787      if (I < NumExplicitlySpecified) {
2788        // We have already fully type-checked and converted this
2789        // argument, because it was explicitly-specified. Just record the
2790        // presence of this argument.
2791        Builder.push_back(Deduced[I]);
2792        continue;
2793      }
2794
2795      // We have deduced this argument, so it still needs to be
2796      // checked and converted.
2797
2798      // First, for a non-type template parameter type that is
2799      // initialized by a declaration, we need the type of the
2800      // corresponding non-type template parameter.
2801      QualType NTTPType;
2802      if (NonTypeTemplateParmDecl *NTTP
2803                                = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2804        NTTPType = NTTP->getType();
2805        if (NTTPType->isDependentType()) {
2806          TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2807                                            Builder.data(), Builder.size());
2808          NTTPType = SubstType(NTTPType,
2809                               MultiLevelTemplateArgumentList(TemplateArgs),
2810                               NTTP->getLocation(),
2811                               NTTP->getDeclName());
2812          if (NTTPType.isNull()) {
2813            Info.Param = makeTemplateParameter(Param);
2814            // FIXME: These template arguments are temporary. Free them!
2815            Info.reset(TemplateArgumentList::CreateCopy(Context,
2816                                                        Builder.data(),
2817                                                        Builder.size()));
2818            return TDK_SubstitutionFailure;
2819          }
2820        }
2821      }
2822
2823      if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2824                                         FunctionTemplate, NTTPType, 0, Info,
2825                                         true, Builder)) {
2826        Info.Param = makeTemplateParameter(Param);
2827        // FIXME: These template arguments are temporary. Free them!
2828        Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2829                                                    Builder.size()));
2830        return TDK_SubstitutionFailure;
2831      }
2832
2833      continue;
2834    }
2835
2836    // C++0x [temp.arg.explicit]p3:
2837    //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2838    //    be deduced to an empty sequence of template arguments.
2839    // FIXME: Where did the word "trailing" come from?
2840    if (Param->isTemplateParameterPack()) {
2841      // We may have had explicitly-specified template arguments for this
2842      // template parameter pack. If so, our empty deduction extends the
2843      // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2844      const TemplateArgument *ExplicitArgs;
2845      unsigned NumExplicitArgs;
2846      if (CurrentInstantiationScope &&
2847          CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2848                                                             &NumExplicitArgs)
2849            == Param) {
2850        Builder.push_back(TemplateArgument(ExplicitArgs, NumExplicitArgs));
2851
2852        // Forget the partially-substituted pack; it's substitution is now
2853        // complete.
2854        CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2855      } else {
2856        Builder.push_back(TemplateArgument::getEmptyPack());
2857      }
2858      continue;
2859    }
2860
2861    // Substitute into the default template argument, if available.
2862    bool HasDefaultArg = false;
2863    TemplateArgumentLoc DefArg
2864      = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2865                                              FunctionTemplate->getLocation(),
2866                                  FunctionTemplate->getSourceRange().getEnd(),
2867                                                Param,
2868                                                Builder, HasDefaultArg);
2869
2870    // If there was no default argument, deduction is incomplete.
2871    if (DefArg.getArgument().isNull()) {
2872      Info.Param = makeTemplateParameter(
2873                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2874      Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2875                                                  Builder.size()));
2876      return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete;
2877    }
2878
2879    // Check whether we can actually use the default argument.
2880    if (CheckTemplateArgument(Param, DefArg,
2881                              FunctionTemplate,
2882                              FunctionTemplate->getLocation(),
2883                              FunctionTemplate->getSourceRange().getEnd(),
2884                              0, Builder,
2885                              CTAK_Specified)) {
2886      Info.Param = makeTemplateParameter(
2887                         const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2888      // FIXME: These template arguments are temporary. Free them!
2889      Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2890                                                  Builder.size()));
2891      return TDK_SubstitutionFailure;
2892    }
2893
2894    // If we get here, we successfully used the default template argument.
2895  }
2896
2897  // Form the template argument list from the deduced template arguments.
2898  TemplateArgumentList *DeducedArgumentList
2899    = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2900  Info.reset(DeducedArgumentList);
2901
2902  // Substitute the deduced template arguments into the function template
2903  // declaration to produce the function template specialization.
2904  DeclContext *Owner = FunctionTemplate->getDeclContext();
2905  if (FunctionTemplate->getFriendObjectKind())
2906    Owner = FunctionTemplate->getLexicalDeclContext();
2907  Specialization = cast_or_null<FunctionDecl>(
2908                      SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2909                         MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2910  if (!Specialization || Specialization->isInvalidDecl())
2911    return TDK_SubstitutionFailure;
2912
2913  assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2914         FunctionTemplate->getCanonicalDecl());
2915
2916  // If the template argument list is owned by the function template
2917  // specialization, release it.
2918  if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2919      !Trap.hasErrorOccurred())
2920    Info.take();
2921
2922  // There may have been an error that did not prevent us from constructing a
2923  // declaration. Mark the declaration invalid and return with a substitution
2924  // failure.
2925  if (Trap.hasErrorOccurred()) {
2926    Specialization->setInvalidDecl(true);
2927    return TDK_SubstitutionFailure;
2928  }
2929
2930  if (OriginalCallArgs) {
2931    // C++ [temp.deduct.call]p4:
2932    //   In general, the deduction process attempts to find template argument
2933    //   values that will make the deduced A identical to A (after the type A
2934    //   is transformed as described above). [...]
2935    for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2936      OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2937      unsigned ParamIdx = OriginalArg.ArgIdx;
2938
2939      if (ParamIdx >= Specialization->getNumParams())
2940        continue;
2941
2942      QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2943      if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2944        return Sema::TDK_SubstitutionFailure;
2945    }
2946  }
2947
2948  // If we suppressed any diagnostics while performing template argument
2949  // deduction, and if we haven't already instantiated this declaration,
2950  // keep track of these diagnostics. They'll be emitted if this specialization
2951  // is actually used.
2952  if (Info.diag_begin() != Info.diag_end()) {
2953    SuppressedDiagnosticsMap::iterator
2954      Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2955    if (Pos == SuppressedDiagnostics.end())
2956        SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2957          .append(Info.diag_begin(), Info.diag_end());
2958  }
2959
2960  return TDK_Success;
2961}
2962
2963/// Gets the type of a function for template-argument-deducton
2964/// purposes when it's considered as part of an overload set.
2965static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2966                                  FunctionDecl *Fn) {
2967  // We may need to deduce the return type of the function now.
2968  if (S.getLangOpts().CPlusPlus1y && Fn->getResultType()->isUndeducedType() &&
2969      S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/false))
2970    return QualType();
2971
2972  if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2973    if (Method->isInstance()) {
2974      // An instance method that's referenced in a form that doesn't
2975      // look like a member pointer is just invalid.
2976      if (!R.HasFormOfMemberPointer) return QualType();
2977
2978      return S.Context.getMemberPointerType(Fn->getType(),
2979               S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
2980    }
2981
2982  if (!R.IsAddressOfOperand) return Fn->getType();
2983  return S.Context.getPointerType(Fn->getType());
2984}
2985
2986/// Apply the deduction rules for overload sets.
2987///
2988/// \return the null type if this argument should be treated as an
2989/// undeduced context
2990static QualType
2991ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
2992                            Expr *Arg, QualType ParamType,
2993                            bool ParamWasReference) {
2994
2995  OverloadExpr::FindResult R = OverloadExpr::find(Arg);
2996
2997  OverloadExpr *Ovl = R.Expression;
2998
2999  // C++0x [temp.deduct.call]p4
3000  unsigned TDF = 0;
3001  if (ParamWasReference)
3002    TDF |= TDF_ParamWithReferenceType;
3003  if (R.IsAddressOfOperand)
3004    TDF |= TDF_IgnoreQualifiers;
3005
3006  // C++0x [temp.deduct.call]p6:
3007  //   When P is a function type, pointer to function type, or pointer
3008  //   to member function type:
3009
3010  if (!ParamType->isFunctionType() &&
3011      !ParamType->isFunctionPointerType() &&
3012      !ParamType->isMemberFunctionPointerType()) {
3013    if (Ovl->hasExplicitTemplateArgs()) {
3014      // But we can still look for an explicit specialization.
3015      if (FunctionDecl *ExplicitSpec
3016            = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3017        return GetTypeOfFunction(S, R, ExplicitSpec);
3018    }
3019
3020    return QualType();
3021  }
3022
3023  // Gather the explicit template arguments, if any.
3024  TemplateArgumentListInfo ExplicitTemplateArgs;
3025  if (Ovl->hasExplicitTemplateArgs())
3026    Ovl->getExplicitTemplateArgs().copyInto(ExplicitTemplateArgs);
3027  QualType Match;
3028  for (UnresolvedSetIterator I = Ovl->decls_begin(),
3029         E = Ovl->decls_end(); I != E; ++I) {
3030    NamedDecl *D = (*I)->getUnderlyingDecl();
3031
3032    if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3033      //   - If the argument is an overload set containing one or more
3034      //     function templates, the parameter is treated as a
3035      //     non-deduced context.
3036      if (!Ovl->hasExplicitTemplateArgs())
3037        return QualType();
3038
3039      // Otherwise, see if we can resolve a function type
3040      FunctionDecl *Specialization = 0;
3041      TemplateDeductionInfo Info(Ovl->getNameLoc());
3042      if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3043                                    Specialization, Info))
3044        continue;
3045
3046      D = Specialization;
3047    }
3048
3049    FunctionDecl *Fn = cast<FunctionDecl>(D);
3050    QualType ArgType = GetTypeOfFunction(S, R, Fn);
3051    if (ArgType.isNull()) continue;
3052
3053    // Function-to-pointer conversion.
3054    if (!ParamWasReference && ParamType->isPointerType() &&
3055        ArgType->isFunctionType())
3056      ArgType = S.Context.getPointerType(ArgType);
3057
3058    //   - If the argument is an overload set (not containing function
3059    //     templates), trial argument deduction is attempted using each
3060    //     of the members of the set. If deduction succeeds for only one
3061    //     of the overload set members, that member is used as the
3062    //     argument value for the deduction. If deduction succeeds for
3063    //     more than one member of the overload set the parameter is
3064    //     treated as a non-deduced context.
3065
3066    // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3067    //   Type deduction is done independently for each P/A pair, and
3068    //   the deduced template argument values are then combined.
3069    // So we do not reject deductions which were made elsewhere.
3070    SmallVector<DeducedTemplateArgument, 8>
3071      Deduced(TemplateParams->size());
3072    TemplateDeductionInfo Info(Ovl->getNameLoc());
3073    Sema::TemplateDeductionResult Result
3074      = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3075                                           ArgType, Info, Deduced, TDF);
3076    if (Result) continue;
3077    if (!Match.isNull()) return QualType();
3078    Match = ArgType;
3079  }
3080
3081  return Match;
3082}
3083
3084/// \brief Perform the adjustments to the parameter and argument types
3085/// described in C++ [temp.deduct.call].
3086///
3087/// \returns true if the caller should not attempt to perform any template
3088/// argument deduction based on this P/A pair because the argument is an
3089/// overloaded function set that could not be resolved.
3090static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
3091                                          TemplateParameterList *TemplateParams,
3092                                                      QualType &ParamType,
3093                                                      QualType &ArgType,
3094                                                      Expr *Arg,
3095                                                      unsigned &TDF) {
3096  // C++0x [temp.deduct.call]p3:
3097  //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
3098  //   are ignored for type deduction.
3099  if (ParamType.hasQualifiers())
3100    ParamType = ParamType.getUnqualifiedType();
3101  const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3102  if (ParamRefType) {
3103    QualType PointeeType = ParamRefType->getPointeeType();
3104
3105    // If the argument has incomplete array type, try to complete its type.
3106    if (ArgType->isIncompleteArrayType() && !S.RequireCompleteExprType(Arg, 0))
3107      ArgType = Arg->getType();
3108
3109    //   [C++0x] If P is an rvalue reference to a cv-unqualified
3110    //   template parameter and the argument is an lvalue, the type
3111    //   "lvalue reference to A" is used in place of A for type
3112    //   deduction.
3113    if (isa<RValueReferenceType>(ParamType)) {
3114      if (!PointeeType.getQualifiers() &&
3115          isa<TemplateTypeParmType>(PointeeType) &&
3116          Arg->Classify(S.Context).isLValue() &&
3117          Arg->getType() != S.Context.OverloadTy &&
3118          Arg->getType() != S.Context.BoundMemberTy)
3119        ArgType = S.Context.getLValueReferenceType(ArgType);
3120    }
3121
3122    //   [...] If P is a reference type, the type referred to by P is used
3123    //   for type deduction.
3124    ParamType = PointeeType;
3125  }
3126
3127  // Overload sets usually make this parameter an undeduced
3128  // context, but there are sometimes special circumstances.
3129  if (ArgType == S.Context.OverloadTy) {
3130    ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3131                                          Arg, ParamType,
3132                                          ParamRefType != 0);
3133    if (ArgType.isNull())
3134      return true;
3135  }
3136
3137  if (ParamRefType) {
3138    // C++0x [temp.deduct.call]p3:
3139    //   [...] If P is of the form T&&, where T is a template parameter, and
3140    //   the argument is an lvalue, the type A& is used in place of A for
3141    //   type deduction.
3142    if (ParamRefType->isRValueReferenceType() &&
3143        ParamRefType->getAs<TemplateTypeParmType>() &&
3144        Arg->isLValue())
3145      ArgType = S.Context.getLValueReferenceType(ArgType);
3146  } else {
3147    // C++ [temp.deduct.call]p2:
3148    //   If P is not a reference type:
3149    //   - If A is an array type, the pointer type produced by the
3150    //     array-to-pointer standard conversion (4.2) is used in place of
3151    //     A for type deduction; otherwise,
3152    if (ArgType->isArrayType())
3153      ArgType = S.Context.getArrayDecayedType(ArgType);
3154    //   - If A is a function type, the pointer type produced by the
3155    //     function-to-pointer standard conversion (4.3) is used in place
3156    //     of A for type deduction; otherwise,
3157    else if (ArgType->isFunctionType())
3158      ArgType = S.Context.getPointerType(ArgType);
3159    else {
3160      // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3161      //   type are ignored for type deduction.
3162      ArgType = ArgType.getUnqualifiedType();
3163    }
3164  }
3165
3166  // C++0x [temp.deduct.call]p4:
3167  //   In general, the deduction process attempts to find template argument
3168  //   values that will make the deduced A identical to A (after the type A
3169  //   is transformed as described above). [...]
3170  TDF = TDF_SkipNonDependent;
3171
3172  //     - If the original P is a reference type, the deduced A (i.e., the
3173  //       type referred to by the reference) can be more cv-qualified than
3174  //       the transformed A.
3175  if (ParamRefType)
3176    TDF |= TDF_ParamWithReferenceType;
3177  //     - The transformed A can be another pointer or pointer to member
3178  //       type that can be converted to the deduced A via a qualification
3179  //       conversion (4.4).
3180  if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3181      ArgType->isObjCObjectPointerType())
3182    TDF |= TDF_IgnoreQualifiers;
3183  //     - If P is a class and P has the form simple-template-id, then the
3184  //       transformed A can be a derived class of the deduced A. Likewise,
3185  //       if P is a pointer to a class of the form simple-template-id, the
3186  //       transformed A can be a pointer to a derived class pointed to by
3187  //       the deduced A.
3188  if (isSimpleTemplateIdType(ParamType) ||
3189      (isa<PointerType>(ParamType) &&
3190       isSimpleTemplateIdType(
3191                              ParamType->getAs<PointerType>()->getPointeeType())))
3192    TDF |= TDF_DerivedClass;
3193
3194  return false;
3195}
3196
3197static bool hasDeducibleTemplateParameters(Sema &S,
3198                                           FunctionTemplateDecl *FunctionTemplate,
3199                                           QualType T);
3200
3201/// \brief Perform template argument deduction by matching a parameter type
3202///        against a single expression, where the expression is an element of
3203///        an initializer list that was originally matched against a parameter
3204///        of type \c initializer_list\<ParamType\>.
3205static Sema::TemplateDeductionResult
3206DeduceTemplateArgumentByListElement(Sema &S,
3207                                    TemplateParameterList *TemplateParams,
3208                                    QualType ParamType, Expr *Arg,
3209                                    TemplateDeductionInfo &Info,
3210                              SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3211                                    unsigned TDF) {
3212  // Handle the case where an init list contains another init list as the
3213  // element.
3214  if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3215    QualType X;
3216    if (!S.isStdInitializerList(ParamType.getNonReferenceType(), &X))
3217      return Sema::TDK_Success; // Just ignore this expression.
3218
3219    // Recurse down into the init list.
3220    for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3221      if (Sema::TemplateDeductionResult Result =
3222            DeduceTemplateArgumentByListElement(S, TemplateParams, X,
3223                                                 ILE->getInit(i),
3224                                                 Info, Deduced, TDF))
3225        return Result;
3226    }
3227    return Sema::TDK_Success;
3228  }
3229
3230  // For all other cases, just match by type.
3231  QualType ArgType = Arg->getType();
3232  if (AdjustFunctionParmAndArgTypesForDeduction(S, TemplateParams, ParamType,
3233                                                ArgType, Arg, TDF)) {
3234    Info.Expression = Arg;
3235    return Sema::TDK_FailedOverloadResolution;
3236  }
3237  return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3238                                            ArgType, Info, Deduced, TDF);
3239}
3240
3241/// \brief Perform template argument deduction from a function call
3242/// (C++ [temp.deduct.call]).
3243///
3244/// \param FunctionTemplate the function template for which we are performing
3245/// template argument deduction.
3246///
3247/// \param ExplicitTemplateArgs the explicit template arguments provided
3248/// for this call.
3249///
3250/// \param Args the function call arguments
3251///
3252/// \param Specialization if template argument deduction was successful,
3253/// this will be set to the function template specialization produced by
3254/// template argument deduction.
3255///
3256/// \param Info the argument will be updated to provide additional information
3257/// about template argument deduction.
3258///
3259/// \returns the result of template argument deduction.
3260Sema::TemplateDeductionResult
3261Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3262                              TemplateArgumentListInfo *ExplicitTemplateArgs,
3263                              llvm::ArrayRef<Expr *> Args,
3264                              FunctionDecl *&Specialization,
3265                              TemplateDeductionInfo &Info) {
3266  if (FunctionTemplate->isInvalidDecl())
3267    return TDK_Invalid;
3268
3269  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3270
3271  // C++ [temp.deduct.call]p1:
3272  //   Template argument deduction is done by comparing each function template
3273  //   parameter type (call it P) with the type of the corresponding argument
3274  //   of the call (call it A) as described below.
3275  unsigned CheckArgs = Args.size();
3276  if (Args.size() < Function->getMinRequiredArguments())
3277    return TDK_TooFewArguments;
3278  else if (Args.size() > Function->getNumParams()) {
3279    const FunctionProtoType *Proto
3280      = Function->getType()->getAs<FunctionProtoType>();
3281    if (Proto->isTemplateVariadic())
3282      /* Do nothing */;
3283    else if (Proto->isVariadic())
3284      CheckArgs = Function->getNumParams();
3285    else
3286      return TDK_TooManyArguments;
3287  }
3288
3289  // The types of the parameters from which we will perform template argument
3290  // deduction.
3291  LocalInstantiationScope InstScope(*this);
3292  TemplateParameterList *TemplateParams
3293    = FunctionTemplate->getTemplateParameters();
3294  SmallVector<DeducedTemplateArgument, 4> Deduced;
3295  SmallVector<QualType, 4> ParamTypes;
3296  unsigned NumExplicitlySpecified = 0;
3297  if (ExplicitTemplateArgs) {
3298    TemplateDeductionResult Result =
3299      SubstituteExplicitTemplateArguments(FunctionTemplate,
3300                                          *ExplicitTemplateArgs,
3301                                          Deduced,
3302                                          ParamTypes,
3303                                          0,
3304                                          Info);
3305    if (Result)
3306      return Result;
3307
3308    NumExplicitlySpecified = Deduced.size();
3309  } else {
3310    // Just fill in the parameter types from the function declaration.
3311    for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
3312      ParamTypes.push_back(Function->getParamDecl(I)->getType());
3313  }
3314
3315  // Deduce template arguments from the function parameters.
3316  Deduced.resize(TemplateParams->size());
3317  unsigned ArgIdx = 0;
3318  SmallVector<OriginalCallArg, 4> OriginalCallArgs;
3319  for (unsigned ParamIdx = 0, NumParams = ParamTypes.size();
3320       ParamIdx != NumParams; ++ParamIdx) {
3321    QualType OrigParamType = ParamTypes[ParamIdx];
3322    QualType ParamType = OrigParamType;
3323
3324    const PackExpansionType *ParamExpansion
3325      = dyn_cast<PackExpansionType>(ParamType);
3326    if (!ParamExpansion) {
3327      // Simple case: matching a function parameter to a function argument.
3328      if (ArgIdx >= CheckArgs)
3329        break;
3330
3331      Expr *Arg = Args[ArgIdx++];
3332      QualType ArgType = Arg->getType();
3333
3334      unsigned TDF = 0;
3335      if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3336                                                    ParamType, ArgType, Arg,
3337                                                    TDF))
3338        continue;
3339
3340      // If we have nothing to deduce, we're done.
3341      if (!hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3342        continue;
3343
3344      // If the argument is an initializer list ...
3345      if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3346        // ... then the parameter is an undeduced context, unless the parameter
3347        // type is (reference to cv) std::initializer_list<P'>, in which case
3348        // deduction is done for each element of the initializer list, and the
3349        // result is the deduced type if it's the same for all elements.
3350        QualType X;
3351        // Removing references was already done.
3352        if (!isStdInitializerList(ParamType, &X))
3353          continue;
3354
3355        for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3356          if (TemplateDeductionResult Result =
3357                DeduceTemplateArgumentByListElement(*this, TemplateParams, X,
3358                                                     ILE->getInit(i),
3359                                                     Info, Deduced, TDF))
3360            return Result;
3361        }
3362        // Don't track the argument type, since an initializer list has none.
3363        continue;
3364      }
3365
3366      // Keep track of the argument type and corresponding parameter index,
3367      // so we can check for compatibility between the deduced A and A.
3368      OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx-1,
3369                                                 ArgType));
3370
3371      if (TemplateDeductionResult Result
3372            = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3373                                                 ParamType, ArgType,
3374                                                 Info, Deduced, TDF))
3375        return Result;
3376
3377      continue;
3378    }
3379
3380    // C++0x [temp.deduct.call]p1:
3381    //   For a function parameter pack that occurs at the end of the
3382    //   parameter-declaration-list, the type A of each remaining argument of
3383    //   the call is compared with the type P of the declarator-id of the
3384    //   function parameter pack. Each comparison deduces template arguments
3385    //   for subsequent positions in the template parameter packs expanded by
3386    //   the function parameter pack. For a function parameter pack that does
3387    //   not occur at the end of the parameter-declaration-list, the type of
3388    //   the parameter pack is a non-deduced context.
3389    if (ParamIdx + 1 < NumParams)
3390      break;
3391
3392    QualType ParamPattern = ParamExpansion->getPattern();
3393    SmallVector<unsigned, 2> PackIndices;
3394    {
3395      llvm::SmallBitVector SawIndices(TemplateParams->size());
3396      SmallVector<UnexpandedParameterPack, 2> Unexpanded;
3397      collectUnexpandedParameterPacks(ParamPattern, Unexpanded);
3398      for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
3399        unsigned Depth, Index;
3400        llvm::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
3401        if (Depth == 0 && !SawIndices[Index]) {
3402          SawIndices[Index] = true;
3403          PackIndices.push_back(Index);
3404        }
3405      }
3406    }
3407    assert(!PackIndices.empty() && "Pack expansion without unexpanded packs?");
3408
3409    // Keep track of the deduced template arguments for each parameter pack
3410    // expanded by this pack expansion (the outer index) and for each
3411    // template argument (the inner SmallVectors).
3412    NewlyDeducedPacksType NewlyDeducedPacks(PackIndices.size());
3413    SmallVector<DeducedTemplateArgument, 2>
3414      SavedPacks(PackIndices.size());
3415    PrepareArgumentPackDeduction(*this, Deduced, PackIndices, SavedPacks,
3416                                 NewlyDeducedPacks);
3417    bool HasAnyArguments = false;
3418    for (; ArgIdx < Args.size(); ++ArgIdx) {
3419      HasAnyArguments = true;
3420
3421      QualType OrigParamType = ParamPattern;
3422      ParamType = OrigParamType;
3423      Expr *Arg = Args[ArgIdx];
3424      QualType ArgType = Arg->getType();
3425
3426      unsigned TDF = 0;
3427      if (AdjustFunctionParmAndArgTypesForDeduction(*this, TemplateParams,
3428                                                    ParamType, ArgType, Arg,
3429                                                    TDF)) {
3430        // We can't actually perform any deduction for this argument, so stop
3431        // deduction at this point.
3432        ++ArgIdx;
3433        break;
3434      }
3435
3436      // As above, initializer lists need special handling.
3437      if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3438        QualType X;
3439        if (!isStdInitializerList(ParamType, &X)) {
3440          ++ArgIdx;
3441          break;
3442        }
3443
3444        for (unsigned i = 0, e = ILE->getNumInits(); i < e; ++i) {
3445          if (TemplateDeductionResult Result =
3446                DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams, X,
3447                                                   ILE->getInit(i)->getType(),
3448                                                   Info, Deduced, TDF))
3449            return Result;
3450        }
3451      } else {
3452
3453        // Keep track of the argument type and corresponding argument index,
3454        // so we can check for compatibility between the deduced A and A.
3455        if (hasDeducibleTemplateParameters(*this, FunctionTemplate, ParamType))
3456          OriginalCallArgs.push_back(OriginalCallArg(OrigParamType, ArgIdx,
3457                                                     ArgType));
3458
3459        if (TemplateDeductionResult Result
3460            = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3461                                                 ParamType, ArgType, Info,
3462                                                 Deduced, TDF))
3463          return Result;
3464      }
3465
3466      // Capture the deduced template arguments for each parameter pack expanded
3467      // by this pack expansion, add them to the list of arguments we've deduced
3468      // for that pack, then clear out the deduced argument.
3469      for (unsigned I = 0, N = PackIndices.size(); I != N; ++I) {
3470        DeducedTemplateArgument &DeducedArg = Deduced[PackIndices[I]];
3471        if (!DeducedArg.isNull()) {
3472          NewlyDeducedPacks[I].push_back(DeducedArg);
3473          DeducedArg = DeducedTemplateArgument();
3474        }
3475      }
3476    }
3477
3478    // Build argument packs for each of the parameter packs expanded by this
3479    // pack expansion.
3480    if (Sema::TemplateDeductionResult Result
3481          = FinishArgumentPackDeduction(*this, TemplateParams, HasAnyArguments,
3482                                        Deduced, PackIndices, SavedPacks,
3483                                        NewlyDeducedPacks, Info))
3484      return Result;
3485
3486    // After we've matching against a parameter pack, we're done.
3487    break;
3488  }
3489
3490  return FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3491                                         NumExplicitlySpecified,
3492                                         Specialization, Info, &OriginalCallArgs);
3493}
3494
3495/// \brief Deduce template arguments when taking the address of a function
3496/// template (C++ [temp.deduct.funcaddr]) or matching a specialization to
3497/// a template.
3498///
3499/// \param FunctionTemplate the function template for which we are performing
3500/// template argument deduction.
3501///
3502/// \param ExplicitTemplateArgs the explicitly-specified template
3503/// arguments.
3504///
3505/// \param ArgFunctionType the function type that will be used as the
3506/// "argument" type (A) when performing template argument deduction from the
3507/// function template's function type. This type may be NULL, if there is no
3508/// argument type to compare against, in C++0x [temp.arg.explicit]p3.
3509///
3510/// \param Specialization if template argument deduction was successful,
3511/// this will be set to the function template specialization produced by
3512/// template argument deduction.
3513///
3514/// \param Info the argument will be updated to provide additional information
3515/// about template argument deduction.
3516///
3517/// \returns the result of template argument deduction.
3518Sema::TemplateDeductionResult
3519Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3520                              TemplateArgumentListInfo *ExplicitTemplateArgs,
3521                              QualType ArgFunctionType,
3522                              FunctionDecl *&Specialization,
3523                              TemplateDeductionInfo &Info,
3524                              bool InOverloadResolution) {
3525  if (FunctionTemplate->isInvalidDecl())
3526    return TDK_Invalid;
3527
3528  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
3529  TemplateParameterList *TemplateParams
3530    = FunctionTemplate->getTemplateParameters();
3531  QualType FunctionType = Function->getType();
3532
3533  // Substitute any explicit template arguments.
3534  LocalInstantiationScope InstScope(*this);
3535  SmallVector<DeducedTemplateArgument, 4> Deduced;
3536  unsigned NumExplicitlySpecified = 0;
3537  SmallVector<QualType, 4> ParamTypes;
3538  if (ExplicitTemplateArgs) {
3539    if (TemplateDeductionResult Result
3540          = SubstituteExplicitTemplateArguments(FunctionTemplate,
3541                                                *ExplicitTemplateArgs,
3542                                                Deduced, ParamTypes,
3543                                                &FunctionType, Info))
3544      return Result;
3545
3546    NumExplicitlySpecified = Deduced.size();
3547  }
3548
3549  // Unevaluated SFINAE context.
3550  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3551  SFINAETrap Trap(*this);
3552
3553  Deduced.resize(TemplateParams->size());
3554
3555  // If the function has a deduced return type, substitute it for a dependent
3556  // type so that we treat it as a non-deduced context in what follows.
3557  bool HasUndeducedReturnType = false;
3558  if (getLangOpts().CPlusPlus1y && InOverloadResolution &&
3559      Function->getResultType()->isUndeducedType()) {
3560    FunctionType = SubstAutoType(FunctionType, Context.DependentTy);
3561    HasUndeducedReturnType = true;
3562  }
3563
3564  if (!ArgFunctionType.isNull()) {
3565    unsigned TDF = TDF_TopLevelParameterTypeList;
3566    if (InOverloadResolution) TDF |= TDF_InOverloadResolution;
3567    // Deduce template arguments from the function type.
3568    if (TemplateDeductionResult Result
3569          = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3570                                               FunctionType, ArgFunctionType,
3571                                               Info, Deduced, TDF))
3572      return Result;
3573  }
3574
3575  if (TemplateDeductionResult Result
3576        = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced,
3577                                          NumExplicitlySpecified,
3578                                          Specialization, Info))
3579    return Result;
3580
3581  // If the function has a deduced return type, deduce it now, so we can check
3582  // that the deduced function type matches the requested type.
3583  if (HasUndeducedReturnType &&
3584      Specialization->getResultType()->isUndeducedType() &&
3585      DeduceReturnType(Specialization, Info.getLocation(), false))
3586    return TDK_MiscellaneousDeductionFailure;
3587
3588  // If the requested function type does not match the actual type of the
3589  // specialization with respect to arguments of compatible pointer to function
3590  // types, template argument deduction fails.
3591  if (!ArgFunctionType.isNull()) {
3592    if (InOverloadResolution && !isSameOrCompatibleFunctionType(
3593                           Context.getCanonicalType(Specialization->getType()),
3594                           Context.getCanonicalType(ArgFunctionType)))
3595      return TDK_MiscellaneousDeductionFailure;
3596    else if(!InOverloadResolution &&
3597            !Context.hasSameType(Specialization->getType(), ArgFunctionType))
3598      return TDK_MiscellaneousDeductionFailure;
3599  }
3600
3601  return TDK_Success;
3602}
3603
3604/// \brief Deduce template arguments for a templated conversion
3605/// function (C++ [temp.deduct.conv]) and, if successful, produce a
3606/// conversion function template specialization.
3607Sema::TemplateDeductionResult
3608Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3609                              QualType ToType,
3610                              CXXConversionDecl *&Specialization,
3611                              TemplateDeductionInfo &Info) {
3612  if (FunctionTemplate->isInvalidDecl())
3613    return TDK_Invalid;
3614
3615  CXXConversionDecl *Conv
3616    = cast<CXXConversionDecl>(FunctionTemplate->getTemplatedDecl());
3617  QualType FromType = Conv->getConversionType();
3618
3619  // Canonicalize the types for deduction.
3620  QualType P = Context.getCanonicalType(FromType);
3621  QualType A = Context.getCanonicalType(ToType);
3622
3623  // C++0x [temp.deduct.conv]p2:
3624  //   If P is a reference type, the type referred to by P is used for
3625  //   type deduction.
3626  if (const ReferenceType *PRef = P->getAs<ReferenceType>())
3627    P = PRef->getPointeeType();
3628
3629  // C++0x [temp.deduct.conv]p4:
3630  //   [...] If A is a reference type, the type referred to by A is used
3631  //   for type deduction.
3632  if (const ReferenceType *ARef = A->getAs<ReferenceType>())
3633    A = ARef->getPointeeType().getUnqualifiedType();
3634  // C++ [temp.deduct.conv]p3:
3635  //
3636  //   If A is not a reference type:
3637  else {
3638    assert(!A->isReferenceType() && "Reference types were handled above");
3639
3640    //   - If P is an array type, the pointer type produced by the
3641    //     array-to-pointer standard conversion (4.2) is used in place
3642    //     of P for type deduction; otherwise,
3643    if (P->isArrayType())
3644      P = Context.getArrayDecayedType(P);
3645    //   - If P is a function type, the pointer type produced by the
3646    //     function-to-pointer standard conversion (4.3) is used in
3647    //     place of P for type deduction; otherwise,
3648    else if (P->isFunctionType())
3649      P = Context.getPointerType(P);
3650    //   - If P is a cv-qualified type, the top level cv-qualifiers of
3651    //     P's type are ignored for type deduction.
3652    else
3653      P = P.getUnqualifiedType();
3654
3655    // C++0x [temp.deduct.conv]p4:
3656    //   If A is a cv-qualified type, the top level cv-qualifiers of A's
3657    //   type are ignored for type deduction. If A is a reference type, the type
3658    //   referred to by A is used for type deduction.
3659    A = A.getUnqualifiedType();
3660  }
3661
3662  // Unevaluated SFINAE context.
3663  EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
3664  SFINAETrap Trap(*this);
3665
3666  // C++ [temp.deduct.conv]p1:
3667  //   Template argument deduction is done by comparing the return
3668  //   type of the template conversion function (call it P) with the
3669  //   type that is required as the result of the conversion (call it
3670  //   A) as described in 14.8.2.4.
3671  TemplateParameterList *TemplateParams
3672    = FunctionTemplate->getTemplateParameters();
3673  SmallVector<DeducedTemplateArgument, 4> Deduced;
3674  Deduced.resize(TemplateParams->size());
3675
3676  // C++0x [temp.deduct.conv]p4:
3677  //   In general, the deduction process attempts to find template
3678  //   argument values that will make the deduced A identical to
3679  //   A. However, there are two cases that allow a difference:
3680  unsigned TDF = 0;
3681  //     - If the original A is a reference type, A can be more
3682  //       cv-qualified than the deduced A (i.e., the type referred to
3683  //       by the reference)
3684  if (ToType->isReferenceType())
3685    TDF |= TDF_ParamWithReferenceType;
3686  //     - The deduced A can be another pointer or pointer to member
3687  //       type that can be converted to A via a qualification
3688  //       conversion.
3689  //
3690  // (C++0x [temp.deduct.conv]p6 clarifies that this only happens when
3691  // both P and A are pointers or member pointers. In this case, we
3692  // just ignore cv-qualifiers completely).
3693  if ((P->isPointerType() && A->isPointerType()) ||
3694      (P->isMemberPointerType() && A->isMemberPointerType()))
3695    TDF |= TDF_IgnoreQualifiers;
3696  if (TemplateDeductionResult Result
3697        = DeduceTemplateArgumentsByTypeMatch(*this, TemplateParams,
3698                                             P, A, Info, Deduced, TDF))
3699    return Result;
3700
3701  // Finish template argument deduction.
3702  LocalInstantiationScope InstScope(*this);
3703  FunctionDecl *Spec = 0;
3704  TemplateDeductionResult Result
3705    = FinishTemplateArgumentDeduction(FunctionTemplate, Deduced, 0, Spec,
3706                                      Info);
3707  Specialization = cast_or_null<CXXConversionDecl>(Spec);
3708  return Result;
3709}
3710
3711/// \brief Deduce template arguments for a function template when there is
3712/// nothing to deduce against (C++0x [temp.arg.explicit]p3).
3713///
3714/// \param FunctionTemplate the function template for which we are performing
3715/// template argument deduction.
3716///
3717/// \param ExplicitTemplateArgs the explicitly-specified template
3718/// arguments.
3719///
3720/// \param Specialization if template argument deduction was successful,
3721/// this will be set to the function template specialization produced by
3722/// template argument deduction.
3723///
3724/// \param Info the argument will be updated to provide additional information
3725/// about template argument deduction.
3726///
3727/// \returns the result of template argument deduction.
3728Sema::TemplateDeductionResult
3729Sema::DeduceTemplateArguments(FunctionTemplateDecl *FunctionTemplate,
3730                              TemplateArgumentListInfo *ExplicitTemplateArgs,
3731                              FunctionDecl *&Specialization,
3732                              TemplateDeductionInfo &Info,
3733                              bool InOverloadResolution) {
3734  return DeduceTemplateArguments(FunctionTemplate, ExplicitTemplateArgs,
3735                                 QualType(), Specialization, Info,
3736                                 InOverloadResolution);
3737}
3738
3739namespace {
3740  /// Substitute the 'auto' type specifier within a type for a given replacement
3741  /// type.
3742  class SubstituteAutoTransform :
3743    public TreeTransform<SubstituteAutoTransform> {
3744    QualType Replacement;
3745  public:
3746    SubstituteAutoTransform(Sema &SemaRef, QualType Replacement) :
3747      TreeTransform<SubstituteAutoTransform>(SemaRef), Replacement(Replacement) {
3748    }
3749    QualType TransformAutoType(TypeLocBuilder &TLB, AutoTypeLoc TL) {
3750      // If we're building the type pattern to deduce against, don't wrap the
3751      // substituted type in an AutoType. Certain template deduction rules
3752      // apply only when a template type parameter appears directly (and not if
3753      // the parameter is found through desugaring). For instance:
3754      //   auto &&lref = lvalue;
3755      // must transform into "rvalue reference to T" not "rvalue reference to
3756      // auto type deduced as T" in order for [temp.deduct.call]p3 to apply.
3757      if (!Replacement.isNull() && isa<TemplateTypeParmType>(Replacement)) {
3758        QualType Result = Replacement;
3759        TemplateTypeParmTypeLoc NewTL =
3760          TLB.push<TemplateTypeParmTypeLoc>(Result);
3761        NewTL.setNameLoc(TL.getNameLoc());
3762        return Result;
3763      } else {
3764        bool Dependent =
3765          !Replacement.isNull() && Replacement->isDependentType();
3766        QualType Result =
3767          SemaRef.Context.getAutoType(Dependent ? QualType() : Replacement,
3768                                      TL.getTypePtr()->isDecltypeAuto(),
3769                                      Dependent);
3770        AutoTypeLoc NewTL = TLB.push<AutoTypeLoc>(Result);
3771        NewTL.setNameLoc(TL.getNameLoc());
3772        return Result;
3773      }
3774    }
3775
3776    ExprResult TransformLambdaExpr(LambdaExpr *E) {
3777      // Lambdas never need to be transformed.
3778      return E;
3779    }
3780
3781    QualType Apply(TypeLoc TL) {
3782      // Create some scratch storage for the transformed type locations.
3783      // FIXME: We're just going to throw this information away. Don't build it.
3784      TypeLocBuilder TLB;
3785      TLB.reserve(TL.getFullDataSize());
3786      return TransformType(TLB, TL);
3787    }
3788  };
3789}
3790
3791Sema::DeduceAutoResult
3792Sema::DeduceAutoType(TypeSourceInfo *Type, Expr *&Init, QualType &Result) {
3793  return DeduceAutoType(Type->getTypeLoc(), Init, Result);
3794}
3795
3796/// \brief Deduce the type for an auto type-specifier (C++11 [dcl.spec.auto]p6)
3797///
3798/// \param Type the type pattern using the auto type-specifier.
3799/// \param Init the initializer for the variable whose type is to be deduced.
3800/// \param Result if type deduction was successful, this will be set to the
3801///        deduced type.
3802Sema::DeduceAutoResult
3803Sema::DeduceAutoType(TypeLoc Type, Expr *&Init, QualType &Result) {
3804  if (Init->getType()->isNonOverloadPlaceholderType()) {
3805    ExprResult NonPlaceholder = CheckPlaceholderExpr(Init);
3806    if (NonPlaceholder.isInvalid())
3807      return DAR_FailedAlreadyDiagnosed;
3808    Init = NonPlaceholder.take();
3809  }
3810
3811  if (Init->isTypeDependent() || Type.getType()->isDependentType()) {
3812    Result = SubstituteAutoTransform(*this, Context.DependentTy).Apply(Type);
3813    assert(!Result.isNull() && "substituting DependentTy can't fail");
3814    return DAR_Succeeded;
3815  }
3816
3817  // If this is a 'decltype(auto)' specifier, do the decltype dance.
3818  // Since 'decltype(auto)' can only occur at the top of the type, we
3819  // don't need to go digging for it.
3820  if (const AutoType *AT = Type.getType()->getAs<AutoType>()) {
3821    if (AT->isDecltypeAuto()) {
3822      if (isa<InitListExpr>(Init)) {
3823        Diag(Init->getLocStart(), diag::err_decltype_auto_initializer_list);
3824        return DAR_FailedAlreadyDiagnosed;
3825      }
3826
3827      QualType Deduced = BuildDecltypeType(Init, Init->getLocStart());
3828      // FIXME: Support a non-canonical deduced type for 'auto'.
3829      Deduced = Context.getCanonicalType(Deduced);
3830      Result = SubstituteAutoTransform(*this, Deduced).Apply(Type);
3831      if (Result.isNull())
3832        return DAR_FailedAlreadyDiagnosed;
3833      return DAR_Succeeded;
3834    }
3835  }
3836
3837  SourceLocation Loc = Init->getExprLoc();
3838
3839  LocalInstantiationScope InstScope(*this);
3840
3841  // Build template<class TemplParam> void Func(FuncParam);
3842  TemplateTypeParmDecl *TemplParam =
3843    TemplateTypeParmDecl::Create(Context, 0, SourceLocation(), Loc, 0, 0, 0,
3844                                 false, false);
3845  QualType TemplArg = QualType(TemplParam->getTypeForDecl(), 0);
3846  NamedDecl *TemplParamPtr = TemplParam;
3847  FixedSizeTemplateParameterList<1> TemplateParams(Loc, Loc, &TemplParamPtr,
3848                                                   Loc);
3849
3850  QualType FuncParam = SubstituteAutoTransform(*this, TemplArg).Apply(Type);
3851  assert(!FuncParam.isNull() &&
3852         "substituting template parameter for 'auto' failed");
3853
3854  // Deduce type of TemplParam in Func(Init)
3855  SmallVector<DeducedTemplateArgument, 1> Deduced;
3856  Deduced.resize(1);
3857  QualType InitType = Init->getType();
3858  unsigned TDF = 0;
3859
3860  TemplateDeductionInfo Info(Loc);
3861
3862  InitListExpr *InitList = dyn_cast<InitListExpr>(Init);
3863  if (InitList) {
3864    for (unsigned i = 0, e = InitList->getNumInits(); i < e; ++i) {
3865      if (DeduceTemplateArgumentByListElement(*this, &TemplateParams,
3866                                              TemplArg,
3867                                              InitList->getInit(i),
3868                                              Info, Deduced, TDF))
3869        return DAR_Failed;
3870    }
3871  } else {
3872    if (AdjustFunctionParmAndArgTypesForDeduction(*this, &TemplateParams,
3873                                                  FuncParam, InitType, Init,
3874                                                  TDF))
3875      return DAR_Failed;
3876
3877    if (DeduceTemplateArgumentsByTypeMatch(*this, &TemplateParams, FuncParam,
3878                                           InitType, Info, Deduced, TDF))
3879      return DAR_Failed;
3880  }
3881
3882  if (Deduced[0].getKind() != TemplateArgument::Type)
3883    return DAR_Failed;
3884
3885  QualType DeducedType = Deduced[0].getAsType();
3886
3887  if (InitList) {
3888    DeducedType = BuildStdInitializerList(DeducedType, Loc);
3889    if (DeducedType.isNull())
3890      return DAR_FailedAlreadyDiagnosed;
3891  }
3892
3893  Result = SubstituteAutoTransform(*this, DeducedType).Apply(Type);
3894  if (Result.isNull())
3895   return DAR_FailedAlreadyDiagnosed;
3896
3897  // Check that the deduced argument type is compatible with the original
3898  // argument type per C++ [temp.deduct.call]p4.
3899  if (!InitList && !Result.isNull() &&
3900      CheckOriginalCallArgDeduction(*this,
3901                                    Sema::OriginalCallArg(FuncParam,0,InitType),
3902                                    Result)) {
3903    Result = QualType();
3904    return DAR_Failed;
3905  }
3906
3907  return DAR_Succeeded;
3908}
3909
3910QualType Sema::SubstAutoType(QualType Type, QualType Deduced) {
3911  return SubstituteAutoTransform(*this, Deduced).TransformType(Type);
3912}
3913
3914void Sema::DiagnoseAutoDeductionFailure(VarDecl *VDecl, Expr *Init) {
3915  if (isa<InitListExpr>(Init))
3916    Diag(VDecl->getLocation(),
3917         diag::err_auto_var_deduction_failure_from_init_list)
3918      << VDecl->getDeclName() << VDecl->getType() << Init->getSourceRange();
3919  else
3920    Diag(VDecl->getLocation(), diag::err_auto_var_deduction_failure)
3921      << VDecl->getDeclName() << VDecl->getType() << Init->getType()
3922      << Init->getSourceRange();
3923}
3924
3925bool Sema::DeduceReturnType(FunctionDecl *FD, SourceLocation Loc,
3926                            bool Diagnose) {
3927  assert(FD->getResultType()->isUndeducedType());
3928
3929  if (FD->getTemplateInstantiationPattern())
3930    InstantiateFunctionDefinition(Loc, FD);
3931
3932  bool StillUndeduced = FD->getResultType()->isUndeducedType();
3933  if (StillUndeduced && Diagnose && !FD->isInvalidDecl()) {
3934    Diag(Loc, diag::err_auto_fn_used_before_defined) << FD;
3935    Diag(FD->getLocation(), diag::note_callee_decl) << FD;
3936  }
3937
3938  return StillUndeduced;
3939}
3940
3941static void
3942MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
3943                           bool OnlyDeduced,
3944                           unsigned Level,
3945                           llvm::SmallBitVector &Deduced);
3946
3947/// \brief If this is a non-static member function,
3948static void
3949AddImplicitObjectParameterType(ASTContext &Context,
3950                               CXXMethodDecl *Method,
3951                               SmallVectorImpl<QualType> &ArgTypes) {
3952  // C++11 [temp.func.order]p3:
3953  //   [...] The new parameter is of type "reference to cv A," where cv are
3954  //   the cv-qualifiers of the function template (if any) and A is
3955  //   the class of which the function template is a member.
3956  //
3957  // The standard doesn't say explicitly, but we pick the appropriate kind of
3958  // reference type based on [over.match.funcs]p4.
3959  QualType ArgTy = Context.getTypeDeclType(Method->getParent());
3960  ArgTy = Context.getQualifiedType(ArgTy,
3961                        Qualifiers::fromCVRMask(Method->getTypeQualifiers()));
3962  if (Method->getRefQualifier() == RQ_RValue)
3963    ArgTy = Context.getRValueReferenceType(ArgTy);
3964  else
3965    ArgTy = Context.getLValueReferenceType(ArgTy);
3966  ArgTypes.push_back(ArgTy);
3967}
3968
3969/// \brief Determine whether the function template \p FT1 is at least as
3970/// specialized as \p FT2.
3971static bool isAtLeastAsSpecializedAs(Sema &S,
3972                                     SourceLocation Loc,
3973                                     FunctionTemplateDecl *FT1,
3974                                     FunctionTemplateDecl *FT2,
3975                                     TemplatePartialOrderingContext TPOC,
3976                                     unsigned NumCallArguments,
3977    SmallVectorImpl<RefParamPartialOrderingComparison> *RefParamComparisons) {
3978  FunctionDecl *FD1 = FT1->getTemplatedDecl();
3979  FunctionDecl *FD2 = FT2->getTemplatedDecl();
3980  const FunctionProtoType *Proto1 = FD1->getType()->getAs<FunctionProtoType>();
3981  const FunctionProtoType *Proto2 = FD2->getType()->getAs<FunctionProtoType>();
3982
3983  assert(Proto1 && Proto2 && "Function templates must have prototypes");
3984  TemplateParameterList *TemplateParams = FT2->getTemplateParameters();
3985  SmallVector<DeducedTemplateArgument, 4> Deduced;
3986  Deduced.resize(TemplateParams->size());
3987
3988  // C++0x [temp.deduct.partial]p3:
3989  //   The types used to determine the ordering depend on the context in which
3990  //   the partial ordering is done:
3991  TemplateDeductionInfo Info(Loc);
3992  CXXMethodDecl *Method1 = 0;
3993  CXXMethodDecl *Method2 = 0;
3994  bool IsNonStatic2 = false;
3995  bool IsNonStatic1 = false;
3996  unsigned Skip2 = 0;
3997  switch (TPOC) {
3998  case TPOC_Call: {
3999    //   - In the context of a function call, the function parameter types are
4000    //     used.
4001    Method1 = dyn_cast<CXXMethodDecl>(FD1);
4002    Method2 = dyn_cast<CXXMethodDecl>(FD2);
4003    IsNonStatic1 = Method1 && !Method1->isStatic();
4004    IsNonStatic2 = Method2 && !Method2->isStatic();
4005
4006    // C++11 [temp.func.order]p3:
4007    //   [...] If only one of the function templates is a non-static
4008    //   member, that function template is considered to have a new
4009    //   first parameter inserted in its function parameter list. The
4010    //   new parameter is of type "reference to cv A," where cv are
4011    //   the cv-qualifiers of the function template (if any) and A is
4012    //   the class of which the function template is a member.
4013    //
4014    // Note that we interpret this to mean "if one of the function
4015    // templates is a non-static member and the other is a non-member";
4016    // otherwise, the ordering rules for static functions against non-static
4017    // functions don't make any sense.
4018    //
4019    // C++98/03 doesn't have this provision, so instead we drop the
4020    // first argument of the free function, which seems to match
4021    // existing practice.
4022    SmallVector<QualType, 4> Args1;
4023    unsigned Skip1 = !S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1;
4024    if (S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2)
4025      AddImplicitObjectParameterType(S.Context, Method1, Args1);
4026    Args1.insert(Args1.end(),
4027                 Proto1->arg_type_begin() + Skip1, Proto1->arg_type_end());
4028
4029    SmallVector<QualType, 4> Args2;
4030    Skip2 = !S.getLangOpts().CPlusPlus11 && IsNonStatic1 && !Method2;
4031    if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !Method1)
4032      AddImplicitObjectParameterType(S.Context, Method2, Args2);
4033    Args2.insert(Args2.end(),
4034                 Proto2->arg_type_begin() + Skip2, Proto2->arg_type_end());
4035
4036    // C++ [temp.func.order]p5:
4037    //   The presence of unused ellipsis and default arguments has no effect on
4038    //   the partial ordering of function templates.
4039    if (Args1.size() > NumCallArguments)
4040      Args1.resize(NumCallArguments);
4041    if (Args2.size() > NumCallArguments)
4042      Args2.resize(NumCallArguments);
4043    if (DeduceTemplateArguments(S, TemplateParams, Args2.data(), Args2.size(),
4044                                Args1.data(), Args1.size(), Info, Deduced,
4045                                TDF_None, /*PartialOrdering=*/true,
4046                                RefParamComparisons))
4047        return false;
4048
4049    break;
4050  }
4051
4052  case TPOC_Conversion:
4053    //   - In the context of a call to a conversion operator, the return types
4054    //     of the conversion function templates are used.
4055    if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4056                                           Proto2->getResultType(),
4057                                           Proto1->getResultType(),
4058                                           Info, Deduced, TDF_None,
4059                                           /*PartialOrdering=*/true,
4060                                           RefParamComparisons))
4061      return false;
4062    break;
4063
4064  case TPOC_Other:
4065    //   - In other contexts (14.6.6.2) the function template's function type
4066    //     is used.
4067    if (DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
4068                                           FD2->getType(), FD1->getType(),
4069                                           Info, Deduced, TDF_None,
4070                                           /*PartialOrdering=*/true,
4071                                           RefParamComparisons))
4072      return false;
4073    break;
4074  }
4075
4076  // C++0x [temp.deduct.partial]p11:
4077  //   In most cases, all template parameters must have values in order for
4078  //   deduction to succeed, but for partial ordering purposes a template
4079  //   parameter may remain without a value provided it is not used in the
4080  //   types being used for partial ordering. [ Note: a template parameter used
4081  //   in a non-deduced context is considered used. -end note]
4082  unsigned ArgIdx = 0, NumArgs = Deduced.size();
4083  for (; ArgIdx != NumArgs; ++ArgIdx)
4084    if (Deduced[ArgIdx].isNull())
4085      break;
4086
4087  if (ArgIdx == NumArgs) {
4088    // All template arguments were deduced. FT1 is at least as specialized
4089    // as FT2.
4090    return true;
4091  }
4092
4093  // Figure out which template parameters were used.
4094  llvm::SmallBitVector UsedParameters(TemplateParams->size());
4095  switch (TPOC) {
4096  case TPOC_Call: {
4097    unsigned NumParams = std::min(NumCallArguments,
4098                                  std::min(Proto1->getNumArgs(),
4099                                           Proto2->getNumArgs()));
4100    if (S.getLangOpts().CPlusPlus11 && IsNonStatic2 && !IsNonStatic1)
4101      ::MarkUsedTemplateParameters(S.Context, Method2->getThisType(S.Context),
4102                                   false,
4103                                   TemplateParams->getDepth(), UsedParameters);
4104    for (unsigned I = Skip2; I < NumParams; ++I)
4105      ::MarkUsedTemplateParameters(S.Context, Proto2->getArgType(I), false,
4106                                   TemplateParams->getDepth(),
4107                                   UsedParameters);
4108    break;
4109  }
4110
4111  case TPOC_Conversion:
4112    ::MarkUsedTemplateParameters(S.Context, Proto2->getResultType(), false,
4113                                 TemplateParams->getDepth(),
4114                                 UsedParameters);
4115    break;
4116
4117  case TPOC_Other:
4118    ::MarkUsedTemplateParameters(S.Context, FD2->getType(), false,
4119                                 TemplateParams->getDepth(),
4120                                 UsedParameters);
4121    break;
4122  }
4123
4124  for (; ArgIdx != NumArgs; ++ArgIdx)
4125    // If this argument had no value deduced but was used in one of the types
4126    // used for partial ordering, then deduction fails.
4127    if (Deduced[ArgIdx].isNull() && UsedParameters[ArgIdx])
4128      return false;
4129
4130  return true;
4131}
4132
4133/// \brief Determine whether this a function template whose parameter-type-list
4134/// ends with a function parameter pack.
4135static bool isVariadicFunctionTemplate(FunctionTemplateDecl *FunTmpl) {
4136  FunctionDecl *Function = FunTmpl->getTemplatedDecl();
4137  unsigned NumParams = Function->getNumParams();
4138  if (NumParams == 0)
4139    return false;
4140
4141  ParmVarDecl *Last = Function->getParamDecl(NumParams - 1);
4142  if (!Last->isParameterPack())
4143    return false;
4144
4145  // Make sure that no previous parameter is a parameter pack.
4146  while (--NumParams > 0) {
4147    if (Function->getParamDecl(NumParams - 1)->isParameterPack())
4148      return false;
4149  }
4150
4151  return true;
4152}
4153
4154/// \brief Returns the more specialized function template according
4155/// to the rules of function template partial ordering (C++ [temp.func.order]).
4156///
4157/// \param FT1 the first function template
4158///
4159/// \param FT2 the second function template
4160///
4161/// \param TPOC the context in which we are performing partial ordering of
4162/// function templates.
4163///
4164/// \param NumCallArguments The number of arguments in a call, used only
4165/// when \c TPOC is \c TPOC_Call.
4166///
4167/// \returns the more specialized function template. If neither
4168/// template is more specialized, returns NULL.
4169FunctionTemplateDecl *
4170Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1,
4171                                 FunctionTemplateDecl *FT2,
4172                                 SourceLocation Loc,
4173                                 TemplatePartialOrderingContext TPOC,
4174                                 unsigned NumCallArguments) {
4175  SmallVector<RefParamPartialOrderingComparison, 4> RefParamComparisons;
4176  bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC,
4177                                          NumCallArguments, 0);
4178  bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC,
4179                                          NumCallArguments,
4180                                          &RefParamComparisons);
4181
4182  if (Better1 != Better2) // We have a clear winner
4183    return Better1? FT1 : FT2;
4184
4185  if (!Better1 && !Better2) // Neither is better than the other
4186    return 0;
4187
4188  // C++0x [temp.deduct.partial]p10:
4189  //   If for each type being considered a given template is at least as
4190  //   specialized for all types and more specialized for some set of types and
4191  //   the other template is not more specialized for any types or is not at
4192  //   least as specialized for any types, then the given template is more
4193  //   specialized than the other template. Otherwise, neither template is more
4194  //   specialized than the other.
4195  Better1 = false;
4196  Better2 = false;
4197  for (unsigned I = 0, N = RefParamComparisons.size(); I != N; ++I) {
4198    // C++0x [temp.deduct.partial]p9:
4199    //   If, for a given type, deduction succeeds in both directions (i.e., the
4200    //   types are identical after the transformations above) and both P and A
4201    //   were reference types (before being replaced with the type referred to
4202    //   above):
4203
4204    //     -- if the type from the argument template was an lvalue reference
4205    //        and the type from the parameter template was not, the argument
4206    //        type is considered to be more specialized than the other;
4207    //        otherwise,
4208    if (!RefParamComparisons[I].ArgIsRvalueRef &&
4209        RefParamComparisons[I].ParamIsRvalueRef) {
4210      Better2 = true;
4211      if (Better1)
4212        return 0;
4213      continue;
4214    } else if (!RefParamComparisons[I].ParamIsRvalueRef &&
4215               RefParamComparisons[I].ArgIsRvalueRef) {
4216      Better1 = true;
4217      if (Better2)
4218        return 0;
4219      continue;
4220    }
4221
4222    //     -- if the type from the argument template is more cv-qualified than
4223    //        the type from the parameter template (as described above), the
4224    //        argument type is considered to be more specialized than the
4225    //        other; otherwise,
4226    switch (RefParamComparisons[I].Qualifiers) {
4227    case NeitherMoreQualified:
4228      break;
4229
4230    case ParamMoreQualified:
4231      Better1 = true;
4232      if (Better2)
4233        return 0;
4234      continue;
4235
4236    case ArgMoreQualified:
4237      Better2 = true;
4238      if (Better1)
4239        return 0;
4240      continue;
4241    }
4242
4243    //     -- neither type is more specialized than the other.
4244  }
4245
4246  assert(!(Better1 && Better2) && "Should have broken out in the loop above");
4247  if (Better1)
4248    return FT1;
4249  else if (Better2)
4250    return FT2;
4251
4252  // FIXME: This mimics what GCC implements, but doesn't match up with the
4253  // proposed resolution for core issue 692. This area needs to be sorted out,
4254  // but for now we attempt to maintain compatibility.
4255  bool Variadic1 = isVariadicFunctionTemplate(FT1);
4256  bool Variadic2 = isVariadicFunctionTemplate(FT2);
4257  if (Variadic1 != Variadic2)
4258    return Variadic1? FT2 : FT1;
4259
4260  return 0;
4261}
4262
4263/// \brief Determine if the two templates are equivalent.
4264static bool isSameTemplate(TemplateDecl *T1, TemplateDecl *T2) {
4265  if (T1 == T2)
4266    return true;
4267
4268  if (!T1 || !T2)
4269    return false;
4270
4271  return T1->getCanonicalDecl() == T2->getCanonicalDecl();
4272}
4273
4274/// \brief Retrieve the most specialized of the given function template
4275/// specializations.
4276///
4277/// \param SpecBegin the start iterator of the function template
4278/// specializations that we will be comparing.
4279///
4280/// \param SpecEnd the end iterator of the function template
4281/// specializations, paired with \p SpecBegin.
4282///
4283/// \param TPOC the partial ordering context to use to compare the function
4284/// template specializations.
4285///
4286/// \param NumCallArguments The number of arguments in a call, used only
4287/// when \c TPOC is \c TPOC_Call.
4288///
4289/// \param Loc the location where the ambiguity or no-specializations
4290/// diagnostic should occur.
4291///
4292/// \param NoneDiag partial diagnostic used to diagnose cases where there are
4293/// no matching candidates.
4294///
4295/// \param AmbigDiag partial diagnostic used to diagnose an ambiguity, if one
4296/// occurs.
4297///
4298/// \param CandidateDiag partial diagnostic used for each function template
4299/// specialization that is a candidate in the ambiguous ordering. One parameter
4300/// in this diagnostic should be unbound, which will correspond to the string
4301/// describing the template arguments for the function template specialization.
4302///
4303/// \returns the most specialized function template specialization, if
4304/// found. Otherwise, returns SpecEnd.
4305UnresolvedSetIterator Sema::getMostSpecialized(
4306    UnresolvedSetIterator SpecBegin, UnresolvedSetIterator SpecEnd,
4307    TemplateSpecCandidateSet &FailedCandidates,
4308    TemplatePartialOrderingContext TPOC, unsigned NumCallArguments,
4309    SourceLocation Loc, const PartialDiagnostic &NoneDiag,
4310    const PartialDiagnostic &AmbigDiag, const PartialDiagnostic &CandidateDiag,
4311    bool Complain, QualType TargetType) {
4312  if (SpecBegin == SpecEnd) {
4313    if (Complain) {
4314      Diag(Loc, NoneDiag);
4315      FailedCandidates.NoteCandidates(*this, Loc);
4316    }
4317    return SpecEnd;
4318  }
4319
4320  if (SpecBegin + 1 == SpecEnd)
4321    return SpecBegin;
4322
4323  // Find the function template that is better than all of the templates it
4324  // has been compared to.
4325  UnresolvedSetIterator Best = SpecBegin;
4326  FunctionTemplateDecl *BestTemplate
4327    = cast<FunctionDecl>(*Best)->getPrimaryTemplate();
4328  assert(BestTemplate && "Not a function template specialization?");
4329  for (UnresolvedSetIterator I = SpecBegin + 1; I != SpecEnd; ++I) {
4330    FunctionTemplateDecl *Challenger
4331      = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4332    assert(Challenger && "Not a function template specialization?");
4333    if (isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4334                                                  Loc, TPOC, NumCallArguments),
4335                       Challenger)) {
4336      Best = I;
4337      BestTemplate = Challenger;
4338    }
4339  }
4340
4341  // Make sure that the "best" function template is more specialized than all
4342  // of the others.
4343  bool Ambiguous = false;
4344  for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4345    FunctionTemplateDecl *Challenger
4346      = cast<FunctionDecl>(*I)->getPrimaryTemplate();
4347    if (I != Best &&
4348        !isSameTemplate(getMoreSpecializedTemplate(BestTemplate, Challenger,
4349                                                   Loc, TPOC, NumCallArguments),
4350                        BestTemplate)) {
4351      Ambiguous = true;
4352      break;
4353    }
4354  }
4355
4356  if (!Ambiguous) {
4357    // We found an answer. Return it.
4358    return Best;
4359  }
4360
4361  // Diagnose the ambiguity.
4362  if (Complain) {
4363    Diag(Loc, AmbigDiag);
4364
4365    // FIXME: Can we order the candidates in some sane way?
4366    for (UnresolvedSetIterator I = SpecBegin; I != SpecEnd; ++I) {
4367      PartialDiagnostic PD = CandidateDiag;
4368      PD << getTemplateArgumentBindingsText(
4369          cast<FunctionDecl>(*I)->getPrimaryTemplate()->getTemplateParameters(),
4370                    *cast<FunctionDecl>(*I)->getTemplateSpecializationArgs());
4371      if (!TargetType.isNull())
4372        HandleFunctionTypeMismatch(PD, cast<FunctionDecl>(*I)->getType(),
4373                                   TargetType);
4374      Diag((*I)->getLocation(), PD);
4375    }
4376  }
4377
4378  return SpecEnd;
4379}
4380
4381/// \brief Returns the more specialized class template partial specialization
4382/// according to the rules of partial ordering of class template partial
4383/// specializations (C++ [temp.class.order]).
4384///
4385/// \param PS1 the first class template partial specialization
4386///
4387/// \param PS2 the second class template partial specialization
4388///
4389/// \returns the more specialized class template partial specialization. If
4390/// neither partial specialization is more specialized, returns NULL.
4391ClassTemplatePartialSpecializationDecl *
4392Sema::getMoreSpecializedPartialSpecialization(
4393                                  ClassTemplatePartialSpecializationDecl *PS1,
4394                                  ClassTemplatePartialSpecializationDecl *PS2,
4395                                              SourceLocation Loc) {
4396  // C++ [temp.class.order]p1:
4397  //   For two class template partial specializations, the first is at least as
4398  //   specialized as the second if, given the following rewrite to two
4399  //   function templates, the first function template is at least as
4400  //   specialized as the second according to the ordering rules for function
4401  //   templates (14.6.6.2):
4402  //     - the first function template has the same template parameters as the
4403  //       first partial specialization and has a single function parameter
4404  //       whose type is a class template specialization with the template
4405  //       arguments of the first partial specialization, and
4406  //     - the second function template has the same template parameters as the
4407  //       second partial specialization and has a single function parameter
4408  //       whose type is a class template specialization with the template
4409  //       arguments of the second partial specialization.
4410  //
4411  // Rather than synthesize function templates, we merely perform the
4412  // equivalent partial ordering by performing deduction directly on
4413  // the template arguments of the class template partial
4414  // specializations. This computation is slightly simpler than the
4415  // general problem of function template partial ordering, because
4416  // class template partial specializations are more constrained. We
4417  // know that every template parameter is deducible from the class
4418  // template partial specialization's template arguments, for
4419  // example.
4420  SmallVector<DeducedTemplateArgument, 4> Deduced;
4421  TemplateDeductionInfo Info(Loc);
4422
4423  QualType PT1 = PS1->getInjectedSpecializationType();
4424  QualType PT2 = PS2->getInjectedSpecializationType();
4425
4426  // Determine whether PS1 is at least as specialized as PS2
4427  Deduced.resize(PS2->getTemplateParameters()->size());
4428  bool Better1 = !DeduceTemplateArgumentsByTypeMatch(*this,
4429                                            PS2->getTemplateParameters(),
4430                                            PT2, PT1, Info, Deduced, TDF_None,
4431                                            /*PartialOrdering=*/true,
4432                                            /*RefParamComparisons=*/0);
4433  if (Better1) {
4434    SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4435    InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2, DeducedArgs,
4436                               Info);
4437    Better1 = !::FinishTemplateArgumentDeduction(
4438        *this, PS2, PS1->getTemplateArgs(), Deduced, Info);
4439  }
4440
4441  // Determine whether PS2 is at least as specialized as PS1
4442  Deduced.clear();
4443  Deduced.resize(PS1->getTemplateParameters()->size());
4444  bool Better2 = !DeduceTemplateArgumentsByTypeMatch(
4445      *this, PS1->getTemplateParameters(), PT1, PT2, Info, Deduced, TDF_None,
4446      /*PartialOrdering=*/true,
4447      /*RefParamComparisons=*/0);
4448  if (Better2) {
4449    SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4450                                                 Deduced.end());
4451    InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1, DeducedArgs,
4452                               Info);
4453    Better2 = !::FinishTemplateArgumentDeduction(
4454        *this, PS1, PS2->getTemplateArgs(), Deduced, Info);
4455  }
4456
4457  if (Better1 == Better2)
4458    return 0;
4459
4460  return Better1 ? PS1 : PS2;
4461}
4462
4463/// TODO: Unify with ClassTemplatePartialSpecializationDecl version.
4464VarTemplatePartialSpecializationDecl *
4465Sema::getMoreSpecializedPartialSpecialization(
4466    VarTemplatePartialSpecializationDecl *PS1,
4467    VarTemplatePartialSpecializationDecl *PS2, SourceLocation Loc) {
4468  SmallVector<DeducedTemplateArgument, 4> Deduced;
4469  TemplateDeductionInfo Info(Loc);
4470
4471  assert(PS1->getSpecializedTemplate() == PS1->getSpecializedTemplate() &&
4472         "the partial specializations being compared should specialize"
4473         " the same template.");
4474  TemplateName Name(PS1->getSpecializedTemplate());
4475  TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
4476  QualType PT1 = Context.getTemplateSpecializationType(
4477      CanonTemplate, PS1->getTemplateArgs().data(),
4478      PS1->getTemplateArgs().size());
4479  QualType PT2 = Context.getTemplateSpecializationType(
4480      CanonTemplate, PS2->getTemplateArgs().data(),
4481      PS2->getTemplateArgs().size());
4482
4483  // Determine whether PS1 is at least as specialized as PS2
4484  Deduced.resize(PS2->getTemplateParameters()->size());
4485  bool Better1 = !DeduceTemplateArgumentsByTypeMatch(
4486      *this, PS2->getTemplateParameters(), PT2, PT1, Info, Deduced, TDF_None,
4487      /*PartialOrdering=*/true,
4488      /*RefParamComparisons=*/0);
4489  if (Better1) {
4490    SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),
4491                                                 Deduced.end());
4492    InstantiatingTemplate Inst(*this, PS2->getLocation(), PS2,
4493                               DeducedArgs, Info);
4494    Better1 = !::FinishTemplateArgumentDeduction(*this, PS2,
4495                                                 PS1->getTemplateArgs(),
4496                                                 Deduced, Info);
4497  }
4498
4499  // Determine whether PS2 is at least as specialized as PS1
4500  Deduced.clear();
4501  Deduced.resize(PS1->getTemplateParameters()->size());
4502  bool Better2 = !DeduceTemplateArgumentsByTypeMatch(*this,
4503                                            PS1->getTemplateParameters(),
4504                                            PT1, PT2, Info, Deduced, TDF_None,
4505                                            /*PartialOrdering=*/true,
4506                                            /*RefParamComparisons=*/0);
4507  if (Better2) {
4508    SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(),Deduced.end());
4509    InstantiatingTemplate Inst(*this, PS1->getLocation(), PS1,
4510                               DeducedArgs, Info);
4511    Better2 = !::FinishTemplateArgumentDeduction(*this, PS1,
4512                                                 PS2->getTemplateArgs(),
4513                                                 Deduced, Info);
4514  }
4515
4516  if (Better1 == Better2)
4517    return 0;
4518
4519  return Better1? PS1 : PS2;
4520}
4521
4522static void
4523MarkUsedTemplateParameters(ASTContext &Ctx,
4524                           const TemplateArgument &TemplateArg,
4525                           bool OnlyDeduced,
4526                           unsigned Depth,
4527                           llvm::SmallBitVector &Used);
4528
4529/// \brief Mark the template parameters that are used by the given
4530/// expression.
4531static void
4532MarkUsedTemplateParameters(ASTContext &Ctx,
4533                           const Expr *E,
4534                           bool OnlyDeduced,
4535                           unsigned Depth,
4536                           llvm::SmallBitVector &Used) {
4537  // We can deduce from a pack expansion.
4538  if (const PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(E))
4539    E = Expansion->getPattern();
4540
4541  // Skip through any implicit casts we added while type-checking, and any
4542  // substitutions performed by template alias expansion.
4543  while (1) {
4544    if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E))
4545      E = ICE->getSubExpr();
4546    else if (const SubstNonTypeTemplateParmExpr *Subst =
4547               dyn_cast<SubstNonTypeTemplateParmExpr>(E))
4548      E = Subst->getReplacement();
4549    else
4550      break;
4551  }
4552
4553  // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
4554  // find other occurrences of template parameters.
4555  const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E);
4556  if (!DRE)
4557    return;
4558
4559  const NonTypeTemplateParmDecl *NTTP
4560    = dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
4561  if (!NTTP)
4562    return;
4563
4564  if (NTTP->getDepth() == Depth)
4565    Used[NTTP->getIndex()] = true;
4566}
4567
4568/// \brief Mark the template parameters that are used by the given
4569/// nested name specifier.
4570static void
4571MarkUsedTemplateParameters(ASTContext &Ctx,
4572                           NestedNameSpecifier *NNS,
4573                           bool OnlyDeduced,
4574                           unsigned Depth,
4575                           llvm::SmallBitVector &Used) {
4576  if (!NNS)
4577    return;
4578
4579  MarkUsedTemplateParameters(Ctx, NNS->getPrefix(), OnlyDeduced, Depth,
4580                             Used);
4581  MarkUsedTemplateParameters(Ctx, QualType(NNS->getAsType(), 0),
4582                             OnlyDeduced, Depth, Used);
4583}
4584
4585/// \brief Mark the template parameters that are used by the given
4586/// template name.
4587static void
4588MarkUsedTemplateParameters(ASTContext &Ctx,
4589                           TemplateName Name,
4590                           bool OnlyDeduced,
4591                           unsigned Depth,
4592                           llvm::SmallBitVector &Used) {
4593  if (TemplateDecl *Template = Name.getAsTemplateDecl()) {
4594    if (TemplateTemplateParmDecl *TTP
4595          = dyn_cast<TemplateTemplateParmDecl>(Template)) {
4596      if (TTP->getDepth() == Depth)
4597        Used[TTP->getIndex()] = true;
4598    }
4599    return;
4600  }
4601
4602  if (QualifiedTemplateName *QTN = Name.getAsQualifiedTemplateName())
4603    MarkUsedTemplateParameters(Ctx, QTN->getQualifier(), OnlyDeduced,
4604                               Depth, Used);
4605  if (DependentTemplateName *DTN = Name.getAsDependentTemplateName())
4606    MarkUsedTemplateParameters(Ctx, DTN->getQualifier(), OnlyDeduced,
4607                               Depth, Used);
4608}
4609
4610/// \brief Mark the template parameters that are used by the given
4611/// type.
4612static void
4613MarkUsedTemplateParameters(ASTContext &Ctx, QualType T,
4614                           bool OnlyDeduced,
4615                           unsigned Depth,
4616                           llvm::SmallBitVector &Used) {
4617  if (T.isNull())
4618    return;
4619
4620  // Non-dependent types have nothing deducible
4621  if (!T->isDependentType())
4622    return;
4623
4624  T = Ctx.getCanonicalType(T);
4625  switch (T->getTypeClass()) {
4626  case Type::Pointer:
4627    MarkUsedTemplateParameters(Ctx,
4628                               cast<PointerType>(T)->getPointeeType(),
4629                               OnlyDeduced,
4630                               Depth,
4631                               Used);
4632    break;
4633
4634  case Type::BlockPointer:
4635    MarkUsedTemplateParameters(Ctx,
4636                               cast<BlockPointerType>(T)->getPointeeType(),
4637                               OnlyDeduced,
4638                               Depth,
4639                               Used);
4640    break;
4641
4642  case Type::LValueReference:
4643  case Type::RValueReference:
4644    MarkUsedTemplateParameters(Ctx,
4645                               cast<ReferenceType>(T)->getPointeeType(),
4646                               OnlyDeduced,
4647                               Depth,
4648                               Used);
4649    break;
4650
4651  case Type::MemberPointer: {
4652    const MemberPointerType *MemPtr = cast<MemberPointerType>(T.getTypePtr());
4653    MarkUsedTemplateParameters(Ctx, MemPtr->getPointeeType(), OnlyDeduced,
4654                               Depth, Used);
4655    MarkUsedTemplateParameters(Ctx, QualType(MemPtr->getClass(), 0),
4656                               OnlyDeduced, Depth, Used);
4657    break;
4658  }
4659
4660  case Type::DependentSizedArray:
4661    MarkUsedTemplateParameters(Ctx,
4662                               cast<DependentSizedArrayType>(T)->getSizeExpr(),
4663                               OnlyDeduced, Depth, Used);
4664    // Fall through to check the element type
4665
4666  case Type::ConstantArray:
4667  case Type::IncompleteArray:
4668    MarkUsedTemplateParameters(Ctx,
4669                               cast<ArrayType>(T)->getElementType(),
4670                               OnlyDeduced, Depth, Used);
4671    break;
4672
4673  case Type::Vector:
4674  case Type::ExtVector:
4675    MarkUsedTemplateParameters(Ctx,
4676                               cast<VectorType>(T)->getElementType(),
4677                               OnlyDeduced, Depth, Used);
4678    break;
4679
4680  case Type::DependentSizedExtVector: {
4681    const DependentSizedExtVectorType *VecType
4682      = cast<DependentSizedExtVectorType>(T);
4683    MarkUsedTemplateParameters(Ctx, VecType->getElementType(), OnlyDeduced,
4684                               Depth, Used);
4685    MarkUsedTemplateParameters(Ctx, VecType->getSizeExpr(), OnlyDeduced,
4686                               Depth, Used);
4687    break;
4688  }
4689
4690  case Type::FunctionProto: {
4691    const FunctionProtoType *Proto = cast<FunctionProtoType>(T);
4692    MarkUsedTemplateParameters(Ctx, Proto->getResultType(), OnlyDeduced,
4693                               Depth, Used);
4694    for (unsigned I = 0, N = Proto->getNumArgs(); I != N; ++I)
4695      MarkUsedTemplateParameters(Ctx, Proto->getArgType(I), OnlyDeduced,
4696                                 Depth, Used);
4697    break;
4698  }
4699
4700  case Type::TemplateTypeParm: {
4701    const TemplateTypeParmType *TTP = cast<TemplateTypeParmType>(T);
4702    if (TTP->getDepth() == Depth)
4703      Used[TTP->getIndex()] = true;
4704    break;
4705  }
4706
4707  case Type::SubstTemplateTypeParmPack: {
4708    const SubstTemplateTypeParmPackType *Subst
4709      = cast<SubstTemplateTypeParmPackType>(T);
4710    MarkUsedTemplateParameters(Ctx,
4711                               QualType(Subst->getReplacedParameter(), 0),
4712                               OnlyDeduced, Depth, Used);
4713    MarkUsedTemplateParameters(Ctx, Subst->getArgumentPack(),
4714                               OnlyDeduced, Depth, Used);
4715    break;
4716  }
4717
4718  case Type::InjectedClassName:
4719    T = cast<InjectedClassNameType>(T)->getInjectedSpecializationType();
4720    // fall through
4721
4722  case Type::TemplateSpecialization: {
4723    const TemplateSpecializationType *Spec
4724      = cast<TemplateSpecializationType>(T);
4725    MarkUsedTemplateParameters(Ctx, Spec->getTemplateName(), OnlyDeduced,
4726                               Depth, Used);
4727
4728    // C++0x [temp.deduct.type]p9:
4729    //   If the template argument list of P contains a pack expansion that is not
4730    //   the last template argument, the entire template argument list is a
4731    //   non-deduced context.
4732    if (OnlyDeduced &&
4733        hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4734      break;
4735
4736    for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4737      MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4738                                 Used);
4739    break;
4740  }
4741
4742  case Type::Complex:
4743    if (!OnlyDeduced)
4744      MarkUsedTemplateParameters(Ctx,
4745                                 cast<ComplexType>(T)->getElementType(),
4746                                 OnlyDeduced, Depth, Used);
4747    break;
4748
4749  case Type::Atomic:
4750    if (!OnlyDeduced)
4751      MarkUsedTemplateParameters(Ctx,
4752                                 cast<AtomicType>(T)->getValueType(),
4753                                 OnlyDeduced, Depth, Used);
4754    break;
4755
4756  case Type::DependentName:
4757    if (!OnlyDeduced)
4758      MarkUsedTemplateParameters(Ctx,
4759                                 cast<DependentNameType>(T)->getQualifier(),
4760                                 OnlyDeduced, Depth, Used);
4761    break;
4762
4763  case Type::DependentTemplateSpecialization: {
4764    const DependentTemplateSpecializationType *Spec
4765      = cast<DependentTemplateSpecializationType>(T);
4766    if (!OnlyDeduced)
4767      MarkUsedTemplateParameters(Ctx, Spec->getQualifier(),
4768                                 OnlyDeduced, Depth, Used);
4769
4770    // C++0x [temp.deduct.type]p9:
4771    //   If the template argument list of P contains a pack expansion that is not
4772    //   the last template argument, the entire template argument list is a
4773    //   non-deduced context.
4774    if (OnlyDeduced &&
4775        hasPackExpansionBeforeEnd(Spec->getArgs(), Spec->getNumArgs()))
4776      break;
4777
4778    for (unsigned I = 0, N = Spec->getNumArgs(); I != N; ++I)
4779      MarkUsedTemplateParameters(Ctx, Spec->getArg(I), OnlyDeduced, Depth,
4780                                 Used);
4781    break;
4782  }
4783
4784  case Type::TypeOf:
4785    if (!OnlyDeduced)
4786      MarkUsedTemplateParameters(Ctx,
4787                                 cast<TypeOfType>(T)->getUnderlyingType(),
4788                                 OnlyDeduced, Depth, Used);
4789    break;
4790
4791  case Type::TypeOfExpr:
4792    if (!OnlyDeduced)
4793      MarkUsedTemplateParameters(Ctx,
4794                                 cast<TypeOfExprType>(T)->getUnderlyingExpr(),
4795                                 OnlyDeduced, Depth, Used);
4796    break;
4797
4798  case Type::Decltype:
4799    if (!OnlyDeduced)
4800      MarkUsedTemplateParameters(Ctx,
4801                                 cast<DecltypeType>(T)->getUnderlyingExpr(),
4802                                 OnlyDeduced, Depth, Used);
4803    break;
4804
4805  case Type::UnaryTransform:
4806    if (!OnlyDeduced)
4807      MarkUsedTemplateParameters(Ctx,
4808                               cast<UnaryTransformType>(T)->getUnderlyingType(),
4809                                 OnlyDeduced, Depth, Used);
4810    break;
4811
4812  case Type::PackExpansion:
4813    MarkUsedTemplateParameters(Ctx,
4814                               cast<PackExpansionType>(T)->getPattern(),
4815                               OnlyDeduced, Depth, Used);
4816    break;
4817
4818  case Type::Auto:
4819    MarkUsedTemplateParameters(Ctx,
4820                               cast<AutoType>(T)->getDeducedType(),
4821                               OnlyDeduced, Depth, Used);
4822
4823  // None of these types have any template parameters in them.
4824  case Type::Builtin:
4825  case Type::VariableArray:
4826  case Type::FunctionNoProto:
4827  case Type::Record:
4828  case Type::Enum:
4829  case Type::ObjCInterface:
4830  case Type::ObjCObject:
4831  case Type::ObjCObjectPointer:
4832  case Type::UnresolvedUsing:
4833#define TYPE(Class, Base)
4834#define ABSTRACT_TYPE(Class, Base)
4835#define DEPENDENT_TYPE(Class, Base)
4836#define NON_CANONICAL_TYPE(Class, Base) case Type::Class:
4837#include "clang/AST/TypeNodes.def"
4838    break;
4839  }
4840}
4841
4842/// \brief Mark the template parameters that are used by this
4843/// template argument.
4844static void
4845MarkUsedTemplateParameters(ASTContext &Ctx,
4846                           const TemplateArgument &TemplateArg,
4847                           bool OnlyDeduced,
4848                           unsigned Depth,
4849                           llvm::SmallBitVector &Used) {
4850  switch (TemplateArg.getKind()) {
4851  case TemplateArgument::Null:
4852  case TemplateArgument::Integral:
4853  case TemplateArgument::Declaration:
4854    break;
4855
4856  case TemplateArgument::NullPtr:
4857    MarkUsedTemplateParameters(Ctx, TemplateArg.getNullPtrType(), OnlyDeduced,
4858                               Depth, Used);
4859    break;
4860
4861  case TemplateArgument::Type:
4862    MarkUsedTemplateParameters(Ctx, TemplateArg.getAsType(), OnlyDeduced,
4863                               Depth, Used);
4864    break;
4865
4866  case TemplateArgument::Template:
4867  case TemplateArgument::TemplateExpansion:
4868    MarkUsedTemplateParameters(Ctx,
4869                               TemplateArg.getAsTemplateOrTemplatePattern(),
4870                               OnlyDeduced, Depth, Used);
4871    break;
4872
4873  case TemplateArgument::Expression:
4874    MarkUsedTemplateParameters(Ctx, TemplateArg.getAsExpr(), OnlyDeduced,
4875                               Depth, Used);
4876    break;
4877
4878  case TemplateArgument::Pack:
4879    for (TemplateArgument::pack_iterator P = TemplateArg.pack_begin(),
4880                                      PEnd = TemplateArg.pack_end();
4881         P != PEnd; ++P)
4882      MarkUsedTemplateParameters(Ctx, *P, OnlyDeduced, Depth, Used);
4883    break;
4884  }
4885}
4886
4887/// \brief Mark which template parameters can be deduced from a given
4888/// template argument list.
4889///
4890/// \param TemplateArgs the template argument list from which template
4891/// parameters will be deduced.
4892///
4893/// \param Used a bit vector whose elements will be set to \c true
4894/// to indicate when the corresponding template parameter will be
4895/// deduced.
4896void
4897Sema::MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs,
4898                                 bool OnlyDeduced, unsigned Depth,
4899                                 llvm::SmallBitVector &Used) {
4900  // C++0x [temp.deduct.type]p9:
4901  //   If the template argument list of P contains a pack expansion that is not
4902  //   the last template argument, the entire template argument list is a
4903  //   non-deduced context.
4904  if (OnlyDeduced &&
4905      hasPackExpansionBeforeEnd(TemplateArgs.data(), TemplateArgs.size()))
4906    return;
4907
4908  for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4909    ::MarkUsedTemplateParameters(Context, TemplateArgs[I], OnlyDeduced,
4910                                 Depth, Used);
4911}
4912
4913/// \brief Marks all of the template parameters that will be deduced by a
4914/// call to the given function template.
4915void
4916Sema::MarkDeducedTemplateParameters(ASTContext &Ctx,
4917                                    const FunctionTemplateDecl *FunctionTemplate,
4918                                    llvm::SmallBitVector &Deduced) {
4919  TemplateParameterList *TemplateParams
4920    = FunctionTemplate->getTemplateParameters();
4921  Deduced.clear();
4922  Deduced.resize(TemplateParams->size());
4923
4924  FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
4925  for (unsigned I = 0, N = Function->getNumParams(); I != N; ++I)
4926    ::MarkUsedTemplateParameters(Ctx, Function->getParamDecl(I)->getType(),
4927                                 true, TemplateParams->getDepth(), Deduced);
4928}
4929
4930bool hasDeducibleTemplateParameters(Sema &S,
4931                                    FunctionTemplateDecl *FunctionTemplate,
4932                                    QualType T) {
4933  if (!T->isDependentType())
4934    return false;
4935
4936  TemplateParameterList *TemplateParams
4937    = FunctionTemplate->getTemplateParameters();
4938  llvm::SmallBitVector Deduced(TemplateParams->size());
4939  ::MarkUsedTemplateParameters(S.Context, T, true, TemplateParams->getDepth(),
4940                               Deduced);
4941
4942  return Deduced.any();
4943}
4944