[TrailingObjects] Convert ASTTemplateKWAndArgsInfo and ASTTemplateArgumentListInfo.
[lldb.git] / clang / lib / Sema / SemaTemplateDeduction.cpp
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/ASTLambda.h"
17 #include "clang/AST/DeclObjC.h"
18 #include "clang/AST/DeclTemplate.h"
19 #include "clang/AST/Expr.h"
20 #include "clang/AST/ExprCXX.h"
21 #include "clang/AST/StmtVisitor.h"
22 #include "clang/Sema/DeclSpec.h"
23 #include "clang/Sema/Sema.h"
24 #include "clang/Sema/Template.h"
25 #include "llvm/ADT/SmallBitVector.h"
26 #include <algorithm>
27
28 namespace clang {
29   using namespace sema;
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
63 using namespace clang;
64
65 /// \brief Compare two APSInts, extending and switching the sign as
66 /// necessary to compare their values regardless of underlying type.
67 static 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
86 static Sema::TemplateDeductionResult
87 DeduceTemplateArguments(Sema &S,
88                         TemplateParameterList *TemplateParams,
89                         const TemplateArgument &Param,
90                         TemplateArgument Arg,
91                         TemplateDeductionInfo &Info,
92                         SmallVectorImpl<DeducedTemplateArgument> &Deduced);
93
94 static Sema::TemplateDeductionResult
95 DeduceTemplateArgumentsByTypeMatch(Sema &S,
96                                    TemplateParameterList *TemplateParams,
97                                    QualType Param,
98                                    QualType Arg,
99                                    TemplateDeductionInfo &Info,
100                                    SmallVectorImpl<DeducedTemplateArgument> &
101                                                       Deduced,
102                                    unsigned TDF,
103                                    bool PartialOrdering = false);
104
105 static Sema::TemplateDeductionResult
106 DeduceTemplateArguments(Sema &S,
107                         TemplateParameterList *TemplateParams,
108                         const TemplateArgument *Params, unsigned NumParams,
109                         const TemplateArgument *Args, unsigned NumArgs,
110                         TemplateDeductionInfo &Info,
111                         SmallVectorImpl<DeducedTemplateArgument> &Deduced);
112
113 /// \brief If the given expression is of a form that permits the deduction
114 /// of a non-type template parameter, return the declaration of that
115 /// non-type template parameter.
116 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
117   // If we are within an alias template, the expression may have undergone
118   // any number of parameter substitutions already.
119   while (1) {
120     if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
121       E = IC->getSubExpr();
122     else if (SubstNonTypeTemplateParmExpr *Subst =
123                dyn_cast<SubstNonTypeTemplateParmExpr>(E))
124       E = Subst->getReplacement();
125     else
126       break;
127   }
128
129   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
130     return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
131
132   return nullptr;
133 }
134
135 /// \brief Determine whether two declaration pointers refer to the same
136 /// declaration.
137 static bool isSameDeclaration(Decl *X, Decl *Y) {
138   if (NamedDecl *NX = dyn_cast<NamedDecl>(X))
139     X = NX->getUnderlyingDecl();
140   if (NamedDecl *NY = dyn_cast<NamedDecl>(Y))
141     Y = NY->getUnderlyingDecl();
142
143   return X->getCanonicalDecl() == Y->getCanonicalDecl();
144 }
145
146 /// \brief Verify that the given, deduced template arguments are compatible.
147 ///
148 /// \returns The deduced template argument, or a NULL template argument if
149 /// the deduced template arguments were incompatible.
150 static DeducedTemplateArgument
151 checkDeducedTemplateArguments(ASTContext &Context,
152                               const DeducedTemplateArgument &X,
153                               const DeducedTemplateArgument &Y) {
154   // We have no deduction for one or both of the arguments; they're compatible.
155   if (X.isNull())
156     return Y;
157   if (Y.isNull())
158     return X;
159
160   switch (X.getKind()) {
161   case TemplateArgument::Null:
162     llvm_unreachable("Non-deduced template arguments handled above");
163
164   case TemplateArgument::Type:
165     // If two template type arguments have the same type, they're compatible.
166     if (Y.getKind() == TemplateArgument::Type &&
167         Context.hasSameType(X.getAsType(), Y.getAsType()))
168       return X;
169
170     return DeducedTemplateArgument();
171
172   case TemplateArgument::Integral:
173     // If we deduced a constant in one case and either a dependent expression or
174     // declaration in another case, keep the integral constant.
175     // If both are integral constants with the same value, keep that value.
176     if (Y.getKind() == TemplateArgument::Expression ||
177         Y.getKind() == TemplateArgument::Declaration ||
178         (Y.getKind() == TemplateArgument::Integral &&
179          hasSameExtendedValue(X.getAsIntegral(), Y.getAsIntegral())))
180       return DeducedTemplateArgument(X,
181                                      X.wasDeducedFromArrayBound() &&
182                                      Y.wasDeducedFromArrayBound());
183
184     // All other combinations are incompatible.
185     return DeducedTemplateArgument();
186
187   case TemplateArgument::Template:
188     if (Y.getKind() == TemplateArgument::Template &&
189         Context.hasSameTemplateName(X.getAsTemplate(), Y.getAsTemplate()))
190       return X;
191
192     // All other combinations are incompatible.
193     return DeducedTemplateArgument();
194
195   case TemplateArgument::TemplateExpansion:
196     if (Y.getKind() == TemplateArgument::TemplateExpansion &&
197         Context.hasSameTemplateName(X.getAsTemplateOrTemplatePattern(),
198                                     Y.getAsTemplateOrTemplatePattern()))
199       return X;
200
201     // All other combinations are incompatible.
202     return DeducedTemplateArgument();
203
204   case TemplateArgument::Expression:
205     // If we deduced a dependent expression in one case and either an integral
206     // constant or a declaration in another case, keep the integral constant
207     // or declaration.
208     if (Y.getKind() == TemplateArgument::Integral ||
209         Y.getKind() == TemplateArgument::Declaration)
210       return DeducedTemplateArgument(Y, X.wasDeducedFromArrayBound() &&
211                                      Y.wasDeducedFromArrayBound());
212
213     if (Y.getKind() == TemplateArgument::Expression) {
214       // Compare the expressions for equality
215       llvm::FoldingSetNodeID ID1, ID2;
216       X.getAsExpr()->Profile(ID1, Context, true);
217       Y.getAsExpr()->Profile(ID2, Context, true);
218       if (ID1 == ID2)
219         return X;
220     }
221
222     // All other combinations are incompatible.
223     return DeducedTemplateArgument();
224
225   case TemplateArgument::Declaration:
226     // If we deduced a declaration and a dependent expression, keep the
227     // declaration.
228     if (Y.getKind() == TemplateArgument::Expression)
229       return X;
230
231     // If we deduced a declaration and an integral constant, keep the
232     // integral constant.
233     if (Y.getKind() == TemplateArgument::Integral)
234       return Y;
235
236     // If we deduced two declarations, make sure they they refer to the
237     // same declaration.
238     if (Y.getKind() == TemplateArgument::Declaration &&
239         isSameDeclaration(X.getAsDecl(), Y.getAsDecl()))
240       return X;
241
242     // All other combinations are incompatible.
243     return DeducedTemplateArgument();
244
245   case TemplateArgument::NullPtr:
246     // If we deduced a null pointer and a dependent expression, keep the
247     // null pointer.
248     if (Y.getKind() == TemplateArgument::Expression)
249       return X;
250
251     // If we deduced a null pointer and an integral constant, keep the
252     // integral constant.
253     if (Y.getKind() == TemplateArgument::Integral)
254       return Y;
255
256     // If we deduced two null pointers, make sure they have the same type.
257     if (Y.getKind() == TemplateArgument::NullPtr &&
258         Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType()))
259       return X;
260
261     // All other combinations are incompatible.
262     return DeducedTemplateArgument();
263
264   case TemplateArgument::Pack:
265     if (Y.getKind() != TemplateArgument::Pack ||
266         X.pack_size() != Y.pack_size())
267       return DeducedTemplateArgument();
268
269     for (TemplateArgument::pack_iterator XA = X.pack_begin(),
270                                       XAEnd = X.pack_end(),
271                                          YA = Y.pack_begin();
272          XA != XAEnd; ++XA, ++YA) {
273       // FIXME: Do we need to merge the results together here?
274       if (checkDeducedTemplateArguments(Context,
275                     DeducedTemplateArgument(*XA, X.wasDeducedFromArrayBound()),
276                     DeducedTemplateArgument(*YA, Y.wasDeducedFromArrayBound()))
277             .isNull())
278         return DeducedTemplateArgument();
279     }
280
281     return X;
282   }
283
284   llvm_unreachable("Invalid TemplateArgument Kind!");
285 }
286
287 /// \brief Deduce the value of the given non-type template parameter
288 /// from the given constant.
289 static Sema::TemplateDeductionResult
290 DeduceNonTypeTemplateArgument(Sema &S,
291                               NonTypeTemplateParmDecl *NTTP,
292                               llvm::APSInt Value, QualType ValueType,
293                               bool DeducedFromArrayBound,
294                               TemplateDeductionInfo &Info,
295                     SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
296   assert(NTTP->getDepth() == 0 &&
297          "Cannot deduce non-type template argument with depth > 0");
298
299   DeducedTemplateArgument NewDeduced(S.Context, Value, ValueType,
300                                      DeducedFromArrayBound);
301   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
302                                                      Deduced[NTTP->getIndex()],
303                                                                  NewDeduced);
304   if (Result.isNull()) {
305     Info.Param = NTTP;
306     Info.FirstArg = Deduced[NTTP->getIndex()];
307     Info.SecondArg = NewDeduced;
308     return Sema::TDK_Inconsistent;
309   }
310
311   Deduced[NTTP->getIndex()] = Result;
312   return Sema::TDK_Success;
313 }
314
315 /// \brief Deduce the value of the given non-type template parameter
316 /// from the given type- or value-dependent expression.
317 ///
318 /// \returns true if deduction succeeded, false otherwise.
319 static Sema::TemplateDeductionResult
320 DeduceNonTypeTemplateArgument(Sema &S,
321                               NonTypeTemplateParmDecl *NTTP,
322                               Expr *Value,
323                               TemplateDeductionInfo &Info,
324                     SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
325   assert(NTTP->getDepth() == 0 &&
326          "Cannot deduce non-type template argument with depth > 0");
327   assert((Value->isTypeDependent() || Value->isValueDependent()) &&
328          "Expression template argument must be type- or value-dependent.");
329
330   DeducedTemplateArgument NewDeduced(Value);
331   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
332                                                      Deduced[NTTP->getIndex()],
333                                                                  NewDeduced);
334
335   if (Result.isNull()) {
336     Info.Param = NTTP;
337     Info.FirstArg = Deduced[NTTP->getIndex()];
338     Info.SecondArg = NewDeduced;
339     return Sema::TDK_Inconsistent;
340   }
341
342   Deduced[NTTP->getIndex()] = Result;
343   return Sema::TDK_Success;
344 }
345
346 /// \brief Deduce the value of the given non-type template parameter
347 /// from the given declaration.
348 ///
349 /// \returns true if deduction succeeded, false otherwise.
350 static Sema::TemplateDeductionResult
351 DeduceNonTypeTemplateArgument(Sema &S,
352                             NonTypeTemplateParmDecl *NTTP,
353                             ValueDecl *D,
354                             TemplateDeductionInfo &Info,
355                             SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
356   assert(NTTP->getDepth() == 0 &&
357          "Cannot deduce non-type template argument with depth > 0");
358
359   D = D ? cast<ValueDecl>(D->getCanonicalDecl()) : nullptr;
360   TemplateArgument New(D, NTTP->getType());
361   DeducedTemplateArgument NewDeduced(New);
362   DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
363                                                      Deduced[NTTP->getIndex()],
364                                                                  NewDeduced);
365   if (Result.isNull()) {
366     Info.Param = NTTP;
367     Info.FirstArg = Deduced[NTTP->getIndex()];
368     Info.SecondArg = NewDeduced;
369     return Sema::TDK_Inconsistent;
370   }
371
372   Deduced[NTTP->getIndex()] = Result;
373   return Sema::TDK_Success;
374 }
375
376 static Sema::TemplateDeductionResult
377 DeduceTemplateArguments(Sema &S,
378                         TemplateParameterList *TemplateParams,
379                         TemplateName Param,
380                         TemplateName Arg,
381                         TemplateDeductionInfo &Info,
382                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
383   TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
384   if (!ParamDecl) {
385     // The parameter type is dependent and is not a template template parameter,
386     // so there is nothing that we can deduce.
387     return Sema::TDK_Success;
388   }
389
390   if (TemplateTemplateParmDecl *TempParam
391         = dyn_cast<TemplateTemplateParmDecl>(ParamDecl)) {
392     DeducedTemplateArgument NewDeduced(S.Context.getCanonicalTemplateName(Arg));
393     DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
394                                                  Deduced[TempParam->getIndex()],
395                                                                    NewDeduced);
396     if (Result.isNull()) {
397       Info.Param = TempParam;
398       Info.FirstArg = Deduced[TempParam->getIndex()];
399       Info.SecondArg = NewDeduced;
400       return Sema::TDK_Inconsistent;
401     }
402
403     Deduced[TempParam->getIndex()] = Result;
404     return Sema::TDK_Success;
405   }
406
407   // Verify that the two template names are equivalent.
408   if (S.Context.hasSameTemplateName(Param, Arg))
409     return Sema::TDK_Success;
410
411   // Mismatch of non-dependent template parameter to argument.
412   Info.FirstArg = TemplateArgument(Param);
413   Info.SecondArg = TemplateArgument(Arg);
414   return Sema::TDK_NonDeducedMismatch;
415 }
416
417 /// \brief Deduce the template arguments by comparing the template parameter
418 /// type (which is a template-id) with the template argument type.
419 ///
420 /// \param S the Sema
421 ///
422 /// \param TemplateParams the template parameters that we are deducing
423 ///
424 /// \param Param the parameter type
425 ///
426 /// \param Arg the argument type
427 ///
428 /// \param Info information about the template argument deduction itself
429 ///
430 /// \param Deduced the deduced template arguments
431 ///
432 /// \returns the result of template argument deduction so far. Note that a
433 /// "success" result means that template argument deduction has not yet failed,
434 /// but it may still fail, later, for other reasons.
435 static Sema::TemplateDeductionResult
436 DeduceTemplateArguments(Sema &S,
437                         TemplateParameterList *TemplateParams,
438                         const TemplateSpecializationType *Param,
439                         QualType Arg,
440                         TemplateDeductionInfo &Info,
441                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
442   assert(Arg.isCanonical() && "Argument type must be canonical");
443
444   // Check whether the template argument is a dependent template-id.
445   if (const TemplateSpecializationType *SpecArg
446         = dyn_cast<TemplateSpecializationType>(Arg)) {
447     // Perform template argument deduction for the template name.
448     if (Sema::TemplateDeductionResult Result
449           = DeduceTemplateArguments(S, TemplateParams,
450                                     Param->getTemplateName(),
451                                     SpecArg->getTemplateName(),
452                                     Info, Deduced))
453       return Result;
454
455
456     // Perform template argument deduction on each template
457     // argument. Ignore any missing/extra arguments, since they could be
458     // filled in by default arguments.
459     return DeduceTemplateArguments(S, TemplateParams,
460                                    Param->getArgs(), Param->getNumArgs(),
461                                    SpecArg->getArgs(), SpecArg->getNumArgs(),
462                                    Info, Deduced);
463   }
464
465   // If the argument type is a class template specialization, we
466   // perform template argument deduction using its template
467   // arguments.
468   const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
469   if (!RecordArg) {
470     Info.FirstArg = TemplateArgument(QualType(Param, 0));
471     Info.SecondArg = TemplateArgument(Arg);
472     return Sema::TDK_NonDeducedMismatch;
473   }
474
475   ClassTemplateSpecializationDecl *SpecArg
476     = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
477   if (!SpecArg) {
478     Info.FirstArg = TemplateArgument(QualType(Param, 0));
479     Info.SecondArg = TemplateArgument(Arg);
480     return Sema::TDK_NonDeducedMismatch;
481   }
482
483   // Perform template argument deduction for the template name.
484   if (Sema::TemplateDeductionResult Result
485         = DeduceTemplateArguments(S,
486                                   TemplateParams,
487                                   Param->getTemplateName(),
488                                TemplateName(SpecArg->getSpecializedTemplate()),
489                                   Info, Deduced))
490     return Result;
491
492   // Perform template argument deduction for the template arguments.
493   return DeduceTemplateArguments(S, TemplateParams,
494                                  Param->getArgs(), Param->getNumArgs(),
495                                  SpecArg->getTemplateArgs().data(),
496                                  SpecArg->getTemplateArgs().size(),
497                                  Info, Deduced);
498 }
499
500 /// \brief Determines whether the given type is an opaque type that
501 /// might be more qualified when instantiated.
502 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
503   switch (T->getTypeClass()) {
504   case Type::TypeOfExpr:
505   case Type::TypeOf:
506   case Type::DependentName:
507   case Type::Decltype:
508   case Type::UnresolvedUsing:
509   case Type::TemplateTypeParm:
510     return true;
511
512   case Type::ConstantArray:
513   case Type::IncompleteArray:
514   case Type::VariableArray:
515   case Type::DependentSizedArray:
516     return IsPossiblyOpaquelyQualifiedType(
517                                       cast<ArrayType>(T)->getElementType());
518
519   default:
520     return false;
521   }
522 }
523
524 /// \brief Retrieve the depth and index of a template parameter.
525 static std::pair<unsigned, unsigned>
526 getDepthAndIndex(NamedDecl *ND) {
527   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
528     return std::make_pair(TTP->getDepth(), TTP->getIndex());
529
530   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
531     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
532
533   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
534   return std::make_pair(TTP->getDepth(), TTP->getIndex());
535 }
536
537 /// \brief Retrieve the depth and index of an unexpanded parameter pack.
538 static std::pair<unsigned, unsigned>
539 getDepthAndIndex(UnexpandedParameterPack UPP) {
540   if (const TemplateTypeParmType *TTP
541                           = UPP.first.dyn_cast<const TemplateTypeParmType *>())
542     return std::make_pair(TTP->getDepth(), TTP->getIndex());
543
544   return getDepthAndIndex(UPP.first.get<NamedDecl *>());
545 }
546
547 /// \brief Helper function to build a TemplateParameter when we don't
548 /// know its type statically.
549 static TemplateParameter makeTemplateParameter(Decl *D) {
550   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(D))
551     return TemplateParameter(TTP);
552   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D))
553     return TemplateParameter(NTTP);
554
555   return TemplateParameter(cast<TemplateTemplateParmDecl>(D));
556 }
557
558 /// A pack that we're currently deducing.
559 struct clang::DeducedPack {
560   DeducedPack(unsigned Index) : Index(Index), Outer(nullptr) {}
561
562   // The index of the pack.
563   unsigned Index;
564
565   // The old value of the pack before we started deducing it.
566   DeducedTemplateArgument Saved;
567
568   // A deferred value of this pack from an inner deduction, that couldn't be
569   // deduced because this deduction hadn't happened yet.
570   DeducedTemplateArgument DeferredDeduction;
571
572   // The new value of the pack.
573   SmallVector<DeducedTemplateArgument, 4> New;
574
575   // The outer deduction for this pack, if any.
576   DeducedPack *Outer;
577 };
578
579 namespace {
580 /// A scope in which we're performing pack deduction.
581 class PackDeductionScope {
582 public:
583   PackDeductionScope(Sema &S, TemplateParameterList *TemplateParams,
584                      SmallVectorImpl<DeducedTemplateArgument> &Deduced,
585                      TemplateDeductionInfo &Info, TemplateArgument Pattern)
586       : S(S), TemplateParams(TemplateParams), Deduced(Deduced), Info(Info) {
587     // Compute the set of template parameter indices that correspond to
588     // parameter packs expanded by the pack expansion.
589     {
590       llvm::SmallBitVector SawIndices(TemplateParams->size());
591       SmallVector<UnexpandedParameterPack, 2> Unexpanded;
592       S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
593       for (unsigned I = 0, N = Unexpanded.size(); I != N; ++I) {
594         unsigned Depth, Index;
595         std::tie(Depth, Index) = getDepthAndIndex(Unexpanded[I]);
596         if (Depth == 0 && !SawIndices[Index]) {
597           SawIndices[Index] = true;
598
599           // Save the deduced template argument for the parameter pack expanded
600           // by this pack expansion, then clear out the deduction.
601           DeducedPack Pack(Index);
602           Pack.Saved = Deduced[Index];
603           Deduced[Index] = TemplateArgument();
604
605           Packs.push_back(Pack);
606         }
607       }
608     }
609     assert(!Packs.empty() && "Pack expansion without unexpanded packs?");
610
611     for (auto &Pack : Packs) {
612       if (Info.PendingDeducedPacks.size() > Pack.Index)
613         Pack.Outer = Info.PendingDeducedPacks[Pack.Index];
614       else
615         Info.PendingDeducedPacks.resize(Pack.Index + 1);
616       Info.PendingDeducedPacks[Pack.Index] = &Pack;
617
618       if (S.CurrentInstantiationScope) {
619         // If the template argument pack was explicitly specified, add that to
620         // the set of deduced arguments.
621         const TemplateArgument *ExplicitArgs;
622         unsigned NumExplicitArgs;
623         NamedDecl *PartiallySubstitutedPack =
624             S.CurrentInstantiationScope->getPartiallySubstitutedPack(
625                 &ExplicitArgs, &NumExplicitArgs);
626         if (PartiallySubstitutedPack &&
627             getDepthAndIndex(PartiallySubstitutedPack).second == Pack.Index)
628           Pack.New.append(ExplicitArgs, ExplicitArgs + NumExplicitArgs);
629       }
630     }
631   }
632
633   ~PackDeductionScope() {
634     for (auto &Pack : Packs)
635       Info.PendingDeducedPacks[Pack.Index] = Pack.Outer;
636   }
637
638   /// Move to deducing the next element in each pack that is being deduced.
639   void nextPackElement() {
640     // Capture the deduced template arguments for each parameter pack expanded
641     // by this pack expansion, add them to the list of arguments we've deduced
642     // for that pack, then clear out the deduced argument.
643     for (auto &Pack : Packs) {
644       DeducedTemplateArgument &DeducedArg = Deduced[Pack.Index];
645       if (!DeducedArg.isNull()) {
646         Pack.New.push_back(DeducedArg);
647         DeducedArg = DeducedTemplateArgument();
648       }
649     }
650   }
651
652   /// \brief Finish template argument deduction for a set of argument packs,
653   /// producing the argument packs and checking for consistency with prior
654   /// deductions.
655   Sema::TemplateDeductionResult finish(bool HasAnyArguments) {
656     // Build argument packs for each of the parameter packs expanded by this
657     // pack expansion.
658     for (auto &Pack : Packs) {
659       // Put back the old value for this pack.
660       Deduced[Pack.Index] = Pack.Saved;
661
662       // Build or find a new value for this pack.
663       DeducedTemplateArgument NewPack;
664       if (HasAnyArguments && Pack.New.empty()) {
665         if (Pack.DeferredDeduction.isNull()) {
666           // We were not able to deduce anything for this parameter pack
667           // (because it only appeared in non-deduced contexts), so just
668           // restore the saved argument pack.
669           continue;
670         }
671
672         NewPack = Pack.DeferredDeduction;
673         Pack.DeferredDeduction = TemplateArgument();
674       } else if (Pack.New.empty()) {
675         // If we deduced an empty argument pack, create it now.
676         NewPack = DeducedTemplateArgument(TemplateArgument::getEmptyPack());
677       } else {
678         TemplateArgument *ArgumentPack =
679             new (S.Context) TemplateArgument[Pack.New.size()];
680         std::copy(Pack.New.begin(), Pack.New.end(), ArgumentPack);
681         NewPack = DeducedTemplateArgument(
682             TemplateArgument(llvm::makeArrayRef(ArgumentPack, Pack.New.size())),
683             Pack.New[0].wasDeducedFromArrayBound());
684       }
685
686       // Pick where we're going to put the merged pack.
687       DeducedTemplateArgument *Loc;
688       if (Pack.Outer) {
689         if (Pack.Outer->DeferredDeduction.isNull()) {
690           // Defer checking this pack until we have a complete pack to compare
691           // it against.
692           Pack.Outer->DeferredDeduction = NewPack;
693           continue;
694         }
695         Loc = &Pack.Outer->DeferredDeduction;
696       } else {
697         Loc = &Deduced[Pack.Index];
698       }
699
700       // Check the new pack matches any previous value.
701       DeducedTemplateArgument OldPack = *Loc;
702       DeducedTemplateArgument Result =
703           checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
704
705       // If we deferred a deduction of this pack, check that one now too.
706       if (!Result.isNull() && !Pack.DeferredDeduction.isNull()) {
707         OldPack = Result;
708         NewPack = Pack.DeferredDeduction;
709         Result = checkDeducedTemplateArguments(S.Context, OldPack, NewPack);
710       }
711
712       if (Result.isNull()) {
713         Info.Param =
714             makeTemplateParameter(TemplateParams->getParam(Pack.Index));
715         Info.FirstArg = OldPack;
716         Info.SecondArg = NewPack;
717         return Sema::TDK_Inconsistent;
718       }
719
720       *Loc = Result;
721     }
722
723     return Sema::TDK_Success;
724   }
725
726 private:
727   Sema &S;
728   TemplateParameterList *TemplateParams;
729   SmallVectorImpl<DeducedTemplateArgument> &Deduced;
730   TemplateDeductionInfo &Info;
731
732   SmallVector<DeducedPack, 2> Packs;
733 };
734 } // namespace
735
736 /// \brief Deduce the template arguments by comparing the list of parameter
737 /// types to the list of argument types, as in the parameter-type-lists of
738 /// function types (C++ [temp.deduct.type]p10).
739 ///
740 /// \param S The semantic analysis object within which we are deducing
741 ///
742 /// \param TemplateParams The template parameters that we are deducing
743 ///
744 /// \param Params The list of parameter types
745 ///
746 /// \param NumParams The number of types in \c Params
747 ///
748 /// \param Args The list of argument types
749 ///
750 /// \param NumArgs The number of types in \c Args
751 ///
752 /// \param Info information about the template argument deduction itself
753 ///
754 /// \param Deduced the deduced template arguments
755 ///
756 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
757 /// how template argument deduction is performed.
758 ///
759 /// \param PartialOrdering If true, we are performing template argument
760 /// deduction for during partial ordering for a call
761 /// (C++0x [temp.deduct.partial]).
762 ///
763 /// \returns the result of template argument deduction so far. Note that a
764 /// "success" result means that template argument deduction has not yet failed,
765 /// but it may still fail, later, for other reasons.
766 static Sema::TemplateDeductionResult
767 DeduceTemplateArguments(Sema &S,
768                         TemplateParameterList *TemplateParams,
769                         const QualType *Params, unsigned NumParams,
770                         const QualType *Args, unsigned NumArgs,
771                         TemplateDeductionInfo &Info,
772                         SmallVectorImpl<DeducedTemplateArgument> &Deduced,
773                         unsigned TDF,
774                         bool PartialOrdering = false) {
775   // Fast-path check to see if we have too many/too few arguments.
776   if (NumParams != NumArgs &&
777       !(NumParams && isa<PackExpansionType>(Params[NumParams - 1])) &&
778       !(NumArgs && isa<PackExpansionType>(Args[NumArgs - 1])))
779     return Sema::TDK_MiscellaneousDeductionFailure;
780
781   // C++0x [temp.deduct.type]p10:
782   //   Similarly, if P has a form that contains (T), then each parameter type
783   //   Pi of the respective parameter-type- list of P is compared with the
784   //   corresponding parameter type Ai of the corresponding parameter-type-list
785   //   of A. [...]
786   unsigned ArgIdx = 0, ParamIdx = 0;
787   for (; ParamIdx != NumParams; ++ParamIdx) {
788     // Check argument types.
789     const PackExpansionType *Expansion
790                                 = dyn_cast<PackExpansionType>(Params[ParamIdx]);
791     if (!Expansion) {
792       // Simple case: compare the parameter and argument types at this point.
793
794       // Make sure we have an argument.
795       if (ArgIdx >= NumArgs)
796         return Sema::TDK_MiscellaneousDeductionFailure;
797
798       if (isa<PackExpansionType>(Args[ArgIdx])) {
799         // C++0x [temp.deduct.type]p22:
800         //   If the original function parameter associated with A is a function
801         //   parameter pack and the function parameter associated with P is not
802         //   a function parameter pack, then template argument deduction fails.
803         return Sema::TDK_MiscellaneousDeductionFailure;
804       }
805
806       if (Sema::TemplateDeductionResult Result
807             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
808                                                  Params[ParamIdx], Args[ArgIdx],
809                                                  Info, Deduced, TDF,
810                                                  PartialOrdering))
811         return Result;
812
813       ++ArgIdx;
814       continue;
815     }
816
817     // C++0x [temp.deduct.type]p5:
818     //   The non-deduced contexts are:
819     //     - A function parameter pack that does not occur at the end of the
820     //       parameter-declaration-clause.
821     if (ParamIdx + 1 < NumParams)
822       return Sema::TDK_Success;
823
824     // C++0x [temp.deduct.type]p10:
825     //   If the parameter-declaration corresponding to Pi is a function
826     //   parameter pack, then the type of its declarator- id is compared with
827     //   each remaining parameter type in the parameter-type-list of A. Each
828     //   comparison deduces template arguments for subsequent positions in the
829     //   template parameter packs expanded by the function parameter pack.
830
831     QualType Pattern = Expansion->getPattern();
832     PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
833
834     bool HasAnyArguments = false;
835     for (; ArgIdx < NumArgs; ++ArgIdx) {
836       HasAnyArguments = true;
837
838       // Deduce template arguments from the pattern.
839       if (Sema::TemplateDeductionResult Result
840             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, Pattern,
841                                                  Args[ArgIdx], Info, Deduced,
842                                                  TDF, PartialOrdering))
843         return Result;
844
845       PackScope.nextPackElement();
846     }
847
848     // Build argument packs for each of the parameter packs expanded by this
849     // pack expansion.
850     if (auto Result = PackScope.finish(HasAnyArguments))
851       return Result;
852   }
853
854   // Make sure we don't have any extra arguments.
855   if (ArgIdx < NumArgs)
856     return Sema::TDK_MiscellaneousDeductionFailure;
857
858   return Sema::TDK_Success;
859 }
860
861 /// \brief Determine whether the parameter has qualifiers that are either
862 /// inconsistent with or a superset of the argument's qualifiers.
863 static bool hasInconsistentOrSupersetQualifiersOf(QualType ParamType,
864                                                   QualType ArgType) {
865   Qualifiers ParamQs = ParamType.getQualifiers();
866   Qualifiers ArgQs = ArgType.getQualifiers();
867
868   if (ParamQs == ArgQs)
869     return false;
870        
871   // Mismatched (but not missing) Objective-C GC attributes.
872   if (ParamQs.getObjCGCAttr() != ArgQs.getObjCGCAttr() && 
873       ParamQs.hasObjCGCAttr())
874     return true;
875   
876   // Mismatched (but not missing) address spaces.
877   if (ParamQs.getAddressSpace() != ArgQs.getAddressSpace() &&
878       ParamQs.hasAddressSpace())
879     return true;
880
881   // Mismatched (but not missing) Objective-C lifetime qualifiers.
882   if (ParamQs.getObjCLifetime() != ArgQs.getObjCLifetime() &&
883       ParamQs.hasObjCLifetime())
884     return true;
885   
886   // CVR qualifier superset.
887   return (ParamQs.getCVRQualifiers() != ArgQs.getCVRQualifiers()) &&
888       ((ParamQs.getCVRQualifiers() | ArgQs.getCVRQualifiers())
889                                                 == ParamQs.getCVRQualifiers());
890 }
891
892 /// \brief Compare types for equality with respect to possibly compatible
893 /// function types (noreturn adjustment, implicit calling conventions). If any
894 /// of parameter and argument is not a function, just perform type comparison.
895 ///
896 /// \param Param the template parameter type.
897 ///
898 /// \param Arg the argument type.
899 bool Sema::isSameOrCompatibleFunctionType(CanQualType Param,
900                                           CanQualType Arg) {
901   const FunctionType *ParamFunction = Param->getAs<FunctionType>(),
902                      *ArgFunction   = Arg->getAs<FunctionType>();
903
904   // Just compare if not functions.
905   if (!ParamFunction || !ArgFunction)
906     return Param == Arg;
907
908   // Noreturn adjustment.
909   QualType AdjustedParam;
910   if (IsNoReturnConversion(Param, Arg, AdjustedParam))
911     return Arg == Context.getCanonicalType(AdjustedParam);
912
913   // FIXME: Compatible calling conventions.
914
915   return Param == Arg;
916 }
917
918 /// \brief Deduce the template arguments by comparing the parameter type and
919 /// the argument type (C++ [temp.deduct.type]).
920 ///
921 /// \param S the semantic analysis object within which we are deducing
922 ///
923 /// \param TemplateParams the template parameters that we are deducing
924 ///
925 /// \param ParamIn the parameter type
926 ///
927 /// \param ArgIn the argument type
928 ///
929 /// \param Info information about the template argument deduction itself
930 ///
931 /// \param Deduced the deduced template arguments
932 ///
933 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
934 /// how template argument deduction is performed.
935 ///
936 /// \param PartialOrdering Whether we're performing template argument deduction
937 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
938 ///
939 /// \returns the result of template argument deduction so far. Note that a
940 /// "success" result means that template argument deduction has not yet failed,
941 /// but it may still fail, later, for other reasons.
942 static Sema::TemplateDeductionResult
943 DeduceTemplateArgumentsByTypeMatch(Sema &S,
944                                    TemplateParameterList *TemplateParams,
945                                    QualType ParamIn, QualType ArgIn,
946                                    TemplateDeductionInfo &Info,
947                             SmallVectorImpl<DeducedTemplateArgument> &Deduced,
948                                    unsigned TDF,
949                                    bool PartialOrdering) {
950   // We only want to look at the canonical types, since typedefs and
951   // sugar are not part of template argument deduction.
952   QualType Param = S.Context.getCanonicalType(ParamIn);
953   QualType Arg = S.Context.getCanonicalType(ArgIn);
954
955   // If the argument type is a pack expansion, look at its pattern.
956   // This isn't explicitly called out
957   if (const PackExpansionType *ArgExpansion
958                                             = dyn_cast<PackExpansionType>(Arg))
959     Arg = ArgExpansion->getPattern();
960
961   if (PartialOrdering) {
962     // C++11 [temp.deduct.partial]p5:
963     //   Before the partial ordering is done, certain transformations are
964     //   performed on the types used for partial ordering:
965     //     - If P is a reference type, P is replaced by the type referred to.
966     const ReferenceType *ParamRef = Param->getAs<ReferenceType>();
967     if (ParamRef)
968       Param = ParamRef->getPointeeType();
969
970     //     - If A is a reference type, A is replaced by the type referred to.
971     const ReferenceType *ArgRef = Arg->getAs<ReferenceType>();
972     if (ArgRef)
973       Arg = ArgRef->getPointeeType();
974
975     if (ParamRef && ArgRef && S.Context.hasSameUnqualifiedType(Param, Arg)) {
976       // C++11 [temp.deduct.partial]p9:
977       //   If, for a given type, deduction succeeds in both directions (i.e.,
978       //   the types are identical after the transformations above) and both
979       //   P and A were reference types [...]:
980       //     - if [one type] was an lvalue reference and [the other type] was
981       //       not, [the other type] is not considered to be at least as
982       //       specialized as [the first type]
983       //     - if [one type] is more cv-qualified than [the other type],
984       //       [the other type] is not considered to be at least as specialized
985       //       as [the first type]
986       // Objective-C ARC adds:
987       //     - [one type] has non-trivial lifetime, [the other type] has
988       //       __unsafe_unretained lifetime, and the types are otherwise
989       //       identical
990       //
991       // A is "considered to be at least as specialized" as P iff deduction
992       // succeeds, so we model this as a deduction failure. Note that
993       // [the first type] is P and [the other type] is A here; the standard
994       // gets this backwards.
995       Qualifiers ParamQuals = Param.getQualifiers();
996       Qualifiers ArgQuals = Arg.getQualifiers();
997       if ((ParamRef->isLValueReferenceType() &&
998            !ArgRef->isLValueReferenceType()) ||
999           ParamQuals.isStrictSupersetOf(ArgQuals) ||
1000           (ParamQuals.hasNonTrivialObjCLifetime() &&
1001            ArgQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
1002            ParamQuals.withoutObjCLifetime() ==
1003                ArgQuals.withoutObjCLifetime())) {
1004         Info.FirstArg = TemplateArgument(ParamIn);
1005         Info.SecondArg = TemplateArgument(ArgIn);
1006         return Sema::TDK_NonDeducedMismatch;
1007       }
1008     }
1009
1010     // C++11 [temp.deduct.partial]p7:
1011     //   Remove any top-level cv-qualifiers:
1012     //     - If P is a cv-qualified type, P is replaced by the cv-unqualified
1013     //       version of P.
1014     Param = Param.getUnqualifiedType();
1015     //     - If A is a cv-qualified type, A is replaced by the cv-unqualified
1016     //       version of A.
1017     Arg = Arg.getUnqualifiedType();
1018   } else {
1019     // C++0x [temp.deduct.call]p4 bullet 1:
1020     //   - If the original P is a reference type, the deduced A (i.e., the type
1021     //     referred to by the reference) can be more cv-qualified than the
1022     //     transformed A.
1023     if (TDF & TDF_ParamWithReferenceType) {
1024       Qualifiers Quals;
1025       QualType UnqualParam = S.Context.getUnqualifiedArrayType(Param, Quals);
1026       Quals.setCVRQualifiers(Quals.getCVRQualifiers() &
1027                              Arg.getCVRQualifiers());
1028       Param = S.Context.getQualifiedType(UnqualParam, Quals);
1029     }
1030
1031     if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
1032       // C++0x [temp.deduct.type]p10:
1033       //   If P and A are function types that originated from deduction when
1034       //   taking the address of a function template (14.8.2.2) or when deducing
1035       //   template arguments from a function declaration (14.8.2.6) and Pi and
1036       //   Ai are parameters of the top-level parameter-type-list of P and A,
1037       //   respectively, Pi is adjusted if it is an rvalue reference to a
1038       //   cv-unqualified template parameter and Ai is an lvalue reference, in
1039       //   which case the type of Pi is changed to be the template parameter
1040       //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
1041       //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
1042       //   deduced as X&. - end note ]
1043       TDF &= ~TDF_TopLevelParameterTypeList;
1044
1045       if (const RValueReferenceType *ParamRef
1046                                         = Param->getAs<RValueReferenceType>()) {
1047         if (isa<TemplateTypeParmType>(ParamRef->getPointeeType()) &&
1048             !ParamRef->getPointeeType().getQualifiers())
1049           if (Arg->isLValueReferenceType())
1050             Param = ParamRef->getPointeeType();
1051       }
1052     }
1053   }
1054
1055   // C++ [temp.deduct.type]p9:
1056   //   A template type argument T, a template template argument TT or a
1057   //   template non-type argument i can be deduced if P and A have one of
1058   //   the following forms:
1059   //
1060   //     T
1061   //     cv-list T
1062   if (const TemplateTypeParmType *TemplateTypeParm
1063         = Param->getAs<TemplateTypeParmType>()) {
1064     // Just skip any attempts to deduce from a placeholder type.
1065     if (Arg->isPlaceholderType())
1066       return Sema::TDK_Success;
1067     
1068     unsigned Index = TemplateTypeParm->getIndex();
1069     bool RecanonicalizeArg = false;
1070
1071     // If the argument type is an array type, move the qualifiers up to the
1072     // top level, so they can be matched with the qualifiers on the parameter.
1073     if (isa<ArrayType>(Arg)) {
1074       Qualifiers Quals;
1075       Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
1076       if (Quals) {
1077         Arg = S.Context.getQualifiedType(Arg, Quals);
1078         RecanonicalizeArg = true;
1079       }
1080     }
1081
1082     // The argument type can not be less qualified than the parameter
1083     // type.
1084     if (!(TDF & TDF_IgnoreQualifiers) &&
1085         hasInconsistentOrSupersetQualifiersOf(Param, Arg)) {
1086       Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1087       Info.FirstArg = TemplateArgument(Param);
1088       Info.SecondArg = TemplateArgument(Arg);
1089       return Sema::TDK_Underqualified;
1090     }
1091
1092     assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
1093     assert(Arg != S.Context.OverloadTy && "Unresolved overloaded function");
1094     QualType DeducedType = Arg;
1095
1096     // Remove any qualifiers on the parameter from the deduced type.
1097     // We checked the qualifiers for consistency above.
1098     Qualifiers DeducedQs = DeducedType.getQualifiers();
1099     Qualifiers ParamQs = Param.getQualifiers();
1100     DeducedQs.removeCVRQualifiers(ParamQs.getCVRQualifiers());
1101     if (ParamQs.hasObjCGCAttr())
1102       DeducedQs.removeObjCGCAttr();
1103     if (ParamQs.hasAddressSpace())
1104       DeducedQs.removeAddressSpace();
1105     if (ParamQs.hasObjCLifetime())
1106       DeducedQs.removeObjCLifetime();
1107     
1108     // Objective-C ARC:
1109     //   If template deduction would produce a lifetime qualifier on a type
1110     //   that is not a lifetime type, template argument deduction fails.
1111     if (ParamQs.hasObjCLifetime() && !DeducedType->isObjCLifetimeType() &&
1112         !DeducedType->isDependentType()) {
1113       Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1114       Info.FirstArg = TemplateArgument(Param);
1115       Info.SecondArg = TemplateArgument(Arg);
1116       return Sema::TDK_Underqualified;      
1117     }
1118     
1119     // Objective-C ARC:
1120     //   If template deduction would produce an argument type with lifetime type
1121     //   but no lifetime qualifier, the __strong lifetime qualifier is inferred.
1122     if (S.getLangOpts().ObjCAutoRefCount &&
1123         DeducedType->isObjCLifetimeType() &&
1124         !DeducedQs.hasObjCLifetime())
1125       DeducedQs.setObjCLifetime(Qualifiers::OCL_Strong);
1126     
1127     DeducedType = S.Context.getQualifiedType(DeducedType.getUnqualifiedType(),
1128                                              DeducedQs);
1129     
1130     if (RecanonicalizeArg)
1131       DeducedType = S.Context.getCanonicalType(DeducedType);
1132
1133     DeducedTemplateArgument NewDeduced(DeducedType);
1134     DeducedTemplateArgument Result = checkDeducedTemplateArguments(S.Context,
1135                                                                  Deduced[Index],
1136                                                                    NewDeduced);
1137     if (Result.isNull()) {
1138       Info.Param = cast<TemplateTypeParmDecl>(TemplateParams->getParam(Index));
1139       Info.FirstArg = Deduced[Index];
1140       Info.SecondArg = NewDeduced;
1141       return Sema::TDK_Inconsistent;
1142     }
1143
1144     Deduced[Index] = Result;
1145     return Sema::TDK_Success;
1146   }
1147
1148   // Set up the template argument deduction information for a failure.
1149   Info.FirstArg = TemplateArgument(ParamIn);
1150   Info.SecondArg = TemplateArgument(ArgIn);
1151
1152   // If the parameter is an already-substituted template parameter
1153   // pack, do nothing: we don't know which of its arguments to look
1154   // at, so we have to wait until all of the parameter packs in this
1155   // expansion have arguments.
1156   if (isa<SubstTemplateTypeParmPackType>(Param))
1157     return Sema::TDK_Success;
1158
1159   // Check the cv-qualifiers on the parameter and argument types.
1160   CanQualType CanParam = S.Context.getCanonicalType(Param);
1161   CanQualType CanArg = S.Context.getCanonicalType(Arg);
1162   if (!(TDF & TDF_IgnoreQualifiers)) {
1163     if (TDF & TDF_ParamWithReferenceType) {
1164       if (hasInconsistentOrSupersetQualifiersOf(Param, Arg))
1165         return Sema::TDK_NonDeducedMismatch;
1166     } else if (!IsPossiblyOpaquelyQualifiedType(Param)) {
1167       if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
1168         return Sema::TDK_NonDeducedMismatch;
1169     }
1170     
1171     // If the parameter type is not dependent, there is nothing to deduce.
1172     if (!Param->isDependentType()) {
1173       if (!(TDF & TDF_SkipNonDependent)) {
1174         bool NonDeduced = (TDF & TDF_InOverloadResolution)?
1175                           !S.isSameOrCompatibleFunctionType(CanParam, CanArg) :
1176                           Param != Arg;
1177         if (NonDeduced) {
1178           return Sema::TDK_NonDeducedMismatch;
1179         }
1180       }
1181       return Sema::TDK_Success;
1182     }
1183   } else if (!Param->isDependentType()) {
1184     CanQualType ParamUnqualType = CanParam.getUnqualifiedType(),
1185                 ArgUnqualType = CanArg.getUnqualifiedType();
1186     bool Success = (TDF & TDF_InOverloadResolution)?
1187                    S.isSameOrCompatibleFunctionType(ParamUnqualType,
1188                                                     ArgUnqualType) :
1189                    ParamUnqualType == ArgUnqualType;
1190     if (Success)
1191       return Sema::TDK_Success;
1192   }
1193
1194   switch (Param->getTypeClass()) {
1195     // Non-canonical types cannot appear here.
1196 #define NON_CANONICAL_TYPE(Class, Base) \
1197   case Type::Class: llvm_unreachable("deducing non-canonical type: " #Class);
1198 #define TYPE(Class, Base)
1199 #include "clang/AST/TypeNodes.def"
1200       
1201     case Type::TemplateTypeParm:
1202     case Type::SubstTemplateTypeParmPack:
1203       llvm_unreachable("Type nodes handled above");
1204
1205     // These types cannot be dependent, so simply check whether the types are
1206     // the same.
1207     case Type::Builtin:
1208     case Type::VariableArray:
1209     case Type::Vector:
1210     case Type::FunctionNoProto:
1211     case Type::Record:
1212     case Type::Enum:
1213     case Type::ObjCObject:
1214     case Type::ObjCInterface:
1215     case Type::ObjCObjectPointer: {
1216       if (TDF & TDF_SkipNonDependent)
1217         return Sema::TDK_Success;
1218       
1219       if (TDF & TDF_IgnoreQualifiers) {
1220         Param = Param.getUnqualifiedType();
1221         Arg = Arg.getUnqualifiedType();
1222       }
1223             
1224       return Param == Arg? Sema::TDK_Success : Sema::TDK_NonDeducedMismatch;
1225     }
1226       
1227     //     _Complex T   [placeholder extension]  
1228     case Type::Complex:
1229       if (const ComplexType *ComplexArg = Arg->getAs<ComplexType>())
1230         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, 
1231                                     cast<ComplexType>(Param)->getElementType(), 
1232                                     ComplexArg->getElementType(),
1233                                     Info, Deduced, TDF);
1234
1235       return Sema::TDK_NonDeducedMismatch;
1236
1237     //     _Atomic T   [extension]
1238     case Type::Atomic:
1239       if (const AtomicType *AtomicArg = Arg->getAs<AtomicType>())
1240         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1241                                        cast<AtomicType>(Param)->getValueType(),
1242                                        AtomicArg->getValueType(),
1243                                        Info, Deduced, TDF);
1244
1245       return Sema::TDK_NonDeducedMismatch;
1246
1247     //     T *
1248     case Type::Pointer: {
1249       QualType PointeeType;
1250       if (const PointerType *PointerArg = Arg->getAs<PointerType>()) {
1251         PointeeType = PointerArg->getPointeeType();
1252       } else if (const ObjCObjectPointerType *PointerArg
1253                    = Arg->getAs<ObjCObjectPointerType>()) {
1254         PointeeType = PointerArg->getPointeeType();
1255       } else {
1256         return Sema::TDK_NonDeducedMismatch;
1257       }
1258
1259       unsigned SubTDF = TDF & (TDF_IgnoreQualifiers | TDF_DerivedClass);
1260       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1261                                      cast<PointerType>(Param)->getPointeeType(),
1262                                      PointeeType,
1263                                      Info, Deduced, SubTDF);
1264     }
1265
1266     //     T &
1267     case Type::LValueReference: {
1268       const LValueReferenceType *ReferenceArg =
1269           Arg->getAs<LValueReferenceType>();
1270       if (!ReferenceArg)
1271         return Sema::TDK_NonDeducedMismatch;
1272
1273       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1274                            cast<LValueReferenceType>(Param)->getPointeeType(),
1275                            ReferenceArg->getPointeeType(), Info, Deduced, 0);
1276     }
1277
1278     //     T && [C++0x]
1279     case Type::RValueReference: {
1280       const RValueReferenceType *ReferenceArg =
1281           Arg->getAs<RValueReferenceType>();
1282       if (!ReferenceArg)
1283         return Sema::TDK_NonDeducedMismatch;
1284
1285       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1286                              cast<RValueReferenceType>(Param)->getPointeeType(),
1287                              ReferenceArg->getPointeeType(),
1288                              Info, Deduced, 0);
1289     }
1290
1291     //     T [] (implied, but not stated explicitly)
1292     case Type::IncompleteArray: {
1293       const IncompleteArrayType *IncompleteArrayArg =
1294         S.Context.getAsIncompleteArrayType(Arg);
1295       if (!IncompleteArrayArg)
1296         return Sema::TDK_NonDeducedMismatch;
1297
1298       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1299       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1300                     S.Context.getAsIncompleteArrayType(Param)->getElementType(),
1301                     IncompleteArrayArg->getElementType(),
1302                     Info, Deduced, SubTDF);
1303     }
1304
1305     //     T [integer-constant]
1306     case Type::ConstantArray: {
1307       const ConstantArrayType *ConstantArrayArg =
1308         S.Context.getAsConstantArrayType(Arg);
1309       if (!ConstantArrayArg)
1310         return Sema::TDK_NonDeducedMismatch;
1311
1312       const ConstantArrayType *ConstantArrayParm =
1313         S.Context.getAsConstantArrayType(Param);
1314       if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
1315         return Sema::TDK_NonDeducedMismatch;
1316
1317       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1318       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1319                                            ConstantArrayParm->getElementType(),
1320                                            ConstantArrayArg->getElementType(),
1321                                            Info, Deduced, SubTDF);
1322     }
1323
1324     //     type [i]
1325     case Type::DependentSizedArray: {
1326       const ArrayType *ArrayArg = S.Context.getAsArrayType(Arg);
1327       if (!ArrayArg)
1328         return Sema::TDK_NonDeducedMismatch;
1329
1330       unsigned SubTDF = TDF & TDF_IgnoreQualifiers;
1331
1332       // Check the element type of the arrays
1333       const DependentSizedArrayType *DependentArrayParm
1334         = S.Context.getAsDependentSizedArrayType(Param);
1335       if (Sema::TemplateDeductionResult Result
1336             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1337                                           DependentArrayParm->getElementType(),
1338                                           ArrayArg->getElementType(),
1339                                           Info, Deduced, SubTDF))
1340         return Result;
1341
1342       // Determine the array bound is something we can deduce.
1343       NonTypeTemplateParmDecl *NTTP
1344         = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
1345       if (!NTTP)
1346         return Sema::TDK_Success;
1347
1348       // We can perform template argument deduction for the given non-type
1349       // template parameter.
1350       assert(NTTP->getDepth() == 0 &&
1351              "Cannot deduce non-type template argument at depth > 0");
1352       if (const ConstantArrayType *ConstantArrayArg
1353             = dyn_cast<ConstantArrayType>(ArrayArg)) {
1354         llvm::APSInt Size(ConstantArrayArg->getSize());
1355         return DeduceNonTypeTemplateArgument(S, NTTP, Size,
1356                                              S.Context.getSizeType(),
1357                                              /*ArrayBound=*/true,
1358                                              Info, Deduced);
1359       }
1360       if (const DependentSizedArrayType *DependentArrayArg
1361             = dyn_cast<DependentSizedArrayType>(ArrayArg))
1362         if (DependentArrayArg->getSizeExpr())
1363           return DeduceNonTypeTemplateArgument(S, NTTP,
1364                                                DependentArrayArg->getSizeExpr(),
1365                                                Info, Deduced);
1366
1367       // Incomplete type does not match a dependently-sized array type
1368       return Sema::TDK_NonDeducedMismatch;
1369     }
1370
1371     //     type(*)(T)
1372     //     T(*)()
1373     //     T(*)(T)
1374     case Type::FunctionProto: {
1375       unsigned SubTDF = TDF & TDF_TopLevelParameterTypeList;
1376       const FunctionProtoType *FunctionProtoArg =
1377         dyn_cast<FunctionProtoType>(Arg);
1378       if (!FunctionProtoArg)
1379         return Sema::TDK_NonDeducedMismatch;
1380
1381       const FunctionProtoType *FunctionProtoParam =
1382         cast<FunctionProtoType>(Param);
1383
1384       if (FunctionProtoParam->getTypeQuals()
1385             != FunctionProtoArg->getTypeQuals() ||
1386           FunctionProtoParam->getRefQualifier()
1387             != FunctionProtoArg->getRefQualifier() ||
1388           FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
1389         return Sema::TDK_NonDeducedMismatch;
1390
1391       // Check return types.
1392       if (Sema::TemplateDeductionResult Result =
1393               DeduceTemplateArgumentsByTypeMatch(
1394                   S, TemplateParams, FunctionProtoParam->getReturnType(),
1395                   FunctionProtoArg->getReturnType(), Info, Deduced, 0))
1396         return Result;
1397
1398       return DeduceTemplateArguments(
1399           S, TemplateParams, FunctionProtoParam->param_type_begin(),
1400           FunctionProtoParam->getNumParams(),
1401           FunctionProtoArg->param_type_begin(),
1402           FunctionProtoArg->getNumParams(), Info, Deduced, SubTDF);
1403     }
1404
1405     case Type::InjectedClassName: {
1406       // Treat a template's injected-class-name as if the template
1407       // specialization type had been used.
1408       Param = cast<InjectedClassNameType>(Param)
1409         ->getInjectedSpecializationType();
1410       assert(isa<TemplateSpecializationType>(Param) &&
1411              "injected class name is not a template specialization type");
1412       // fall through
1413     }
1414
1415     //     template-name<T> (where template-name refers to a class template)
1416     //     template-name<i>
1417     //     TT<T>
1418     //     TT<i>
1419     //     TT<>
1420     case Type::TemplateSpecialization: {
1421       const TemplateSpecializationType *SpecParam
1422         = cast<TemplateSpecializationType>(Param);
1423
1424       // Try to deduce template arguments from the template-id.
1425       Sema::TemplateDeductionResult Result
1426         = DeduceTemplateArguments(S, TemplateParams, SpecParam, Arg,
1427                                   Info, Deduced);
1428
1429       if (Result && (TDF & TDF_DerivedClass)) {
1430         // C++ [temp.deduct.call]p3b3:
1431         //   If P is a class, and P has the form template-id, then A can be a
1432         //   derived class of the deduced A. Likewise, if P is a pointer to a
1433         //   class of the form template-id, A can be a pointer to a derived
1434         //   class pointed to by the deduced A.
1435         //
1436         // More importantly:
1437         //   These alternatives are considered only if type deduction would
1438         //   otherwise fail.
1439         if (const RecordType *RecordT = Arg->getAs<RecordType>()) {
1440           // We cannot inspect base classes as part of deduction when the type
1441           // is incomplete, so either instantiate any templates necessary to
1442           // complete the type, or skip over it if it cannot be completed.
1443           if (!S.isCompleteType(Info.getLocation(), Arg))
1444             return Result;
1445
1446           // Use data recursion to crawl through the list of base classes.
1447           // Visited contains the set of nodes we have already visited, while
1448           // ToVisit is our stack of records that we still need to visit.
1449           llvm::SmallPtrSet<const RecordType *, 8> Visited;
1450           SmallVector<const RecordType *, 8> ToVisit;
1451           ToVisit.push_back(RecordT);
1452           bool Successful = false;
1453           SmallVector<DeducedTemplateArgument, 8> DeducedOrig(Deduced.begin(),
1454                                                               Deduced.end());
1455           while (!ToVisit.empty()) {
1456             // Retrieve the next class in the inheritance hierarchy.
1457             const RecordType *NextT = ToVisit.pop_back_val();
1458
1459             // If we have already seen this type, skip it.
1460             if (!Visited.insert(NextT).second)
1461               continue;
1462
1463             // If this is a base class, try to perform template argument
1464             // deduction from it.
1465             if (NextT != RecordT) {
1466               TemplateDeductionInfo BaseInfo(Info.getLocation());
1467               Sema::TemplateDeductionResult BaseResult
1468                 = DeduceTemplateArguments(S, TemplateParams, SpecParam,
1469                                           QualType(NextT, 0), BaseInfo,
1470                                           Deduced);
1471
1472               // If template argument deduction for this base was successful,
1473               // note that we had some success. Otherwise, ignore any deductions
1474               // from this base class.
1475               if (BaseResult == Sema::TDK_Success) {
1476                 Successful = true;
1477                 DeducedOrig.clear();
1478                 DeducedOrig.append(Deduced.begin(), Deduced.end());
1479                 Info.Param = BaseInfo.Param;
1480                 Info.FirstArg = BaseInfo.FirstArg;
1481                 Info.SecondArg = BaseInfo.SecondArg;
1482               }
1483               else
1484                 Deduced = DeducedOrig;
1485             }
1486
1487             // Visit base classes
1488             CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
1489             for (const auto &Base : Next->bases()) {
1490               assert(Base.getType()->isRecordType() &&
1491                      "Base class that isn't a record?");
1492               ToVisit.push_back(Base.getType()->getAs<RecordType>());
1493             }
1494           }
1495
1496           if (Successful)
1497             return Sema::TDK_Success;
1498         }
1499
1500       }
1501
1502       return Result;
1503     }
1504
1505     //     T type::*
1506     //     T T::*
1507     //     T (type::*)()
1508     //     type (T::*)()
1509     //     type (type::*)(T)
1510     //     type (T::*)(T)
1511     //     T (type::*)(T)
1512     //     T (T::*)()
1513     //     T (T::*)(T)
1514     case Type::MemberPointer: {
1515       const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
1516       const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
1517       if (!MemPtrArg)
1518         return Sema::TDK_NonDeducedMismatch;
1519
1520       QualType ParamPointeeType = MemPtrParam->getPointeeType();
1521       if (ParamPointeeType->isFunctionType())
1522         S.adjustMemberFunctionCC(ParamPointeeType, /*IsStatic=*/true,
1523                                  /*IsCtorOrDtor=*/false, Info.getLocation());
1524       QualType ArgPointeeType = MemPtrArg->getPointeeType();
1525       if (ArgPointeeType->isFunctionType())
1526         S.adjustMemberFunctionCC(ArgPointeeType, /*IsStatic=*/true,
1527                                  /*IsCtorOrDtor=*/false, Info.getLocation());
1528
1529       if (Sema::TemplateDeductionResult Result
1530             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1531                                                  ParamPointeeType,
1532                                                  ArgPointeeType,
1533                                                  Info, Deduced,
1534                                                  TDF & TDF_IgnoreQualifiers))
1535         return Result;
1536
1537       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1538                                            QualType(MemPtrParam->getClass(), 0),
1539                                            QualType(MemPtrArg->getClass(), 0),
1540                                            Info, Deduced, 
1541                                            TDF & TDF_IgnoreQualifiers);
1542     }
1543
1544     //     (clang extension)
1545     //
1546     //     type(^)(T)
1547     //     T(^)()
1548     //     T(^)(T)
1549     case Type::BlockPointer: {
1550       const BlockPointerType *BlockPtrParam = cast<BlockPointerType>(Param);
1551       const BlockPointerType *BlockPtrArg = dyn_cast<BlockPointerType>(Arg);
1552
1553       if (!BlockPtrArg)
1554         return Sema::TDK_NonDeducedMismatch;
1555
1556       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1557                                                 BlockPtrParam->getPointeeType(),
1558                                                 BlockPtrArg->getPointeeType(),
1559                                                 Info, Deduced, 0);
1560     }
1561
1562     //     (clang extension)
1563     //
1564     //     T __attribute__(((ext_vector_type(<integral constant>))))
1565     case Type::ExtVector: {
1566       const ExtVectorType *VectorParam = cast<ExtVectorType>(Param);
1567       if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1568         // Make sure that the vectors have the same number of elements.
1569         if (VectorParam->getNumElements() != VectorArg->getNumElements())
1570           return Sema::TDK_NonDeducedMismatch;
1571         
1572         // Perform deduction on the element types.
1573         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1574                                                   VectorParam->getElementType(),
1575                                                   VectorArg->getElementType(),
1576                                                   Info, Deduced, TDF);
1577       }
1578       
1579       if (const DependentSizedExtVectorType *VectorArg 
1580                                 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1581         // We can't check the number of elements, since the argument has a
1582         // dependent number of elements. This can only occur during partial
1583         // ordering.
1584
1585         // Perform deduction on the element types.
1586         return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1587                                                   VectorParam->getElementType(),
1588                                                   VectorArg->getElementType(),
1589                                                   Info, Deduced, TDF);
1590       }
1591       
1592       return Sema::TDK_NonDeducedMismatch;
1593     }
1594       
1595     //     (clang extension)
1596     //
1597     //     T __attribute__(((ext_vector_type(N))))
1598     case Type::DependentSizedExtVector: {
1599       const DependentSizedExtVectorType *VectorParam
1600         = cast<DependentSizedExtVectorType>(Param);
1601
1602       if (const ExtVectorType *VectorArg = dyn_cast<ExtVectorType>(Arg)) {
1603         // Perform deduction on the element types.
1604         if (Sema::TemplateDeductionResult Result
1605               = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1606                                                   VectorParam->getElementType(),
1607                                                    VectorArg->getElementType(),
1608                                                    Info, Deduced, TDF))
1609           return Result;
1610         
1611         // Perform deduction on the vector size, if we can.
1612         NonTypeTemplateParmDecl *NTTP
1613           = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1614         if (!NTTP)
1615           return Sema::TDK_Success;
1616
1617         llvm::APSInt ArgSize(S.Context.getTypeSize(S.Context.IntTy), false);
1618         ArgSize = VectorArg->getNumElements();
1619         return DeduceNonTypeTemplateArgument(S, NTTP, ArgSize, S.Context.IntTy,
1620                                              false, Info, Deduced);
1621       }
1622       
1623       if (const DependentSizedExtVectorType *VectorArg 
1624                                 = dyn_cast<DependentSizedExtVectorType>(Arg)) {
1625         // Perform deduction on the element types.
1626         if (Sema::TemplateDeductionResult Result
1627             = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1628                                                  VectorParam->getElementType(),
1629                                                  VectorArg->getElementType(),
1630                                                  Info, Deduced, TDF))
1631           return Result;
1632         
1633         // Perform deduction on the vector size, if we can.
1634         NonTypeTemplateParmDecl *NTTP
1635           = getDeducedParameterFromExpr(VectorParam->getSizeExpr());
1636         if (!NTTP)
1637           return Sema::TDK_Success;
1638         
1639         return DeduceNonTypeTemplateArgument(S, NTTP, VectorArg->getSizeExpr(),
1640                                              Info, Deduced);
1641       }
1642       
1643       return Sema::TDK_NonDeducedMismatch;
1644     }
1645       
1646     case Type::TypeOfExpr:
1647     case Type::TypeOf:
1648     case Type::DependentName:
1649     case Type::UnresolvedUsing:
1650     case Type::Decltype:
1651     case Type::UnaryTransform:
1652     case Type::Auto:
1653     case Type::DependentTemplateSpecialization:
1654     case Type::PackExpansion:
1655       // No template argument deduction for these types
1656       return Sema::TDK_Success;
1657   }
1658
1659   llvm_unreachable("Invalid Type Class!");
1660 }
1661
1662 static Sema::TemplateDeductionResult
1663 DeduceTemplateArguments(Sema &S,
1664                         TemplateParameterList *TemplateParams,
1665                         const TemplateArgument &Param,
1666                         TemplateArgument Arg,
1667                         TemplateDeductionInfo &Info,
1668                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1669   // If the template argument is a pack expansion, perform template argument
1670   // deduction against the pattern of that expansion. This only occurs during
1671   // partial ordering.
1672   if (Arg.isPackExpansion())
1673     Arg = Arg.getPackExpansionPattern();
1674
1675   switch (Param.getKind()) {
1676   case TemplateArgument::Null:
1677     llvm_unreachable("Null template argument in parameter list");
1678
1679   case TemplateArgument::Type:
1680     if (Arg.getKind() == TemplateArgument::Type)
1681       return DeduceTemplateArgumentsByTypeMatch(S, TemplateParams,
1682                                                 Param.getAsType(),
1683                                                 Arg.getAsType(),
1684                                                 Info, Deduced, 0);
1685     Info.FirstArg = Param;
1686     Info.SecondArg = Arg;
1687     return Sema::TDK_NonDeducedMismatch;
1688
1689   case TemplateArgument::Template:
1690     if (Arg.getKind() == TemplateArgument::Template)
1691       return DeduceTemplateArguments(S, TemplateParams,
1692                                      Param.getAsTemplate(),
1693                                      Arg.getAsTemplate(), Info, Deduced);
1694     Info.FirstArg = Param;
1695     Info.SecondArg = Arg;
1696     return Sema::TDK_NonDeducedMismatch;
1697
1698   case TemplateArgument::TemplateExpansion:
1699     llvm_unreachable("caller should handle pack expansions");
1700
1701   case TemplateArgument::Declaration:
1702     if (Arg.getKind() == TemplateArgument::Declaration &&
1703         isSameDeclaration(Param.getAsDecl(), Arg.getAsDecl()))
1704       return Sema::TDK_Success;
1705
1706     Info.FirstArg = Param;
1707     Info.SecondArg = Arg;
1708     return Sema::TDK_NonDeducedMismatch;
1709
1710   case TemplateArgument::NullPtr:
1711     if (Arg.getKind() == TemplateArgument::NullPtr &&
1712         S.Context.hasSameType(Param.getNullPtrType(), Arg.getNullPtrType()))
1713       return Sema::TDK_Success;
1714
1715     Info.FirstArg = Param;
1716     Info.SecondArg = Arg;
1717     return Sema::TDK_NonDeducedMismatch;
1718
1719   case TemplateArgument::Integral:
1720     if (Arg.getKind() == TemplateArgument::Integral) {
1721       if (hasSameExtendedValue(Param.getAsIntegral(), Arg.getAsIntegral()))
1722         return Sema::TDK_Success;
1723
1724       Info.FirstArg = Param;
1725       Info.SecondArg = Arg;
1726       return Sema::TDK_NonDeducedMismatch;
1727     }
1728
1729     if (Arg.getKind() == TemplateArgument::Expression) {
1730       Info.FirstArg = Param;
1731       Info.SecondArg = Arg;
1732       return Sema::TDK_NonDeducedMismatch;
1733     }
1734
1735     Info.FirstArg = Param;
1736     Info.SecondArg = Arg;
1737     return Sema::TDK_NonDeducedMismatch;
1738
1739   case TemplateArgument::Expression: {
1740     if (NonTypeTemplateParmDecl *NTTP
1741           = getDeducedParameterFromExpr(Param.getAsExpr())) {
1742       if (Arg.getKind() == TemplateArgument::Integral)
1743         return DeduceNonTypeTemplateArgument(S, NTTP,
1744                                              Arg.getAsIntegral(),
1745                                              Arg.getIntegralType(),
1746                                              /*ArrayBound=*/false,
1747                                              Info, Deduced);
1748       if (Arg.getKind() == TemplateArgument::Expression)
1749         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsExpr(),
1750                                              Info, Deduced);
1751       if (Arg.getKind() == TemplateArgument::Declaration)
1752         return DeduceNonTypeTemplateArgument(S, NTTP, Arg.getAsDecl(),
1753                                              Info, Deduced);
1754
1755       Info.FirstArg = Param;
1756       Info.SecondArg = Arg;
1757       return Sema::TDK_NonDeducedMismatch;
1758     }
1759
1760     // Can't deduce anything, but that's okay.
1761     return Sema::TDK_Success;
1762   }
1763   case TemplateArgument::Pack:
1764     llvm_unreachable("Argument packs should be expanded by the caller!");
1765   }
1766
1767   llvm_unreachable("Invalid TemplateArgument Kind!");
1768 }
1769
1770 /// \brief Determine whether there is a template argument to be used for
1771 /// deduction.
1772 ///
1773 /// This routine "expands" argument packs in-place, overriding its input
1774 /// parameters so that \c Args[ArgIdx] will be the available template argument.
1775 ///
1776 /// \returns true if there is another template argument (which will be at
1777 /// \c Args[ArgIdx]), false otherwise.
1778 static bool hasTemplateArgumentForDeduction(const TemplateArgument *&Args,
1779                                             unsigned &ArgIdx,
1780                                             unsigned &NumArgs) {
1781   if (ArgIdx == NumArgs)
1782     return false;
1783
1784   const TemplateArgument &Arg = Args[ArgIdx];
1785   if (Arg.getKind() != TemplateArgument::Pack)
1786     return true;
1787
1788   assert(ArgIdx == NumArgs - 1 && "Pack not at the end of argument list?");
1789   Args = Arg.pack_begin();
1790   NumArgs = Arg.pack_size();
1791   ArgIdx = 0;
1792   return ArgIdx < NumArgs;
1793 }
1794
1795 /// \brief Determine whether the given set of template arguments has a pack
1796 /// expansion that is not the last template argument.
1797 static bool hasPackExpansionBeforeEnd(const TemplateArgument *Args,
1798                                       unsigned NumArgs) {
1799   unsigned ArgIdx = 0;
1800   while (ArgIdx < NumArgs) {
1801     const TemplateArgument &Arg = Args[ArgIdx];
1802
1803     // Unwrap argument packs.
1804     if (Args[ArgIdx].getKind() == TemplateArgument::Pack) {
1805       Args = Arg.pack_begin();
1806       NumArgs = Arg.pack_size();
1807       ArgIdx = 0;
1808       continue;
1809     }
1810
1811     ++ArgIdx;
1812     if (ArgIdx == NumArgs)
1813       return false;
1814
1815     if (Arg.isPackExpansion())
1816       return true;
1817   }
1818
1819   return false;
1820 }
1821
1822 static Sema::TemplateDeductionResult
1823 DeduceTemplateArguments(Sema &S,
1824                         TemplateParameterList *TemplateParams,
1825                         const TemplateArgument *Params, unsigned NumParams,
1826                         const TemplateArgument *Args, unsigned NumArgs,
1827                         TemplateDeductionInfo &Info,
1828                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1829   // C++0x [temp.deduct.type]p9:
1830   //   If the template argument list of P contains a pack expansion that is not
1831   //   the last template argument, the entire template argument list is a
1832   //   non-deduced context.
1833   if (hasPackExpansionBeforeEnd(Params, NumParams))
1834     return Sema::TDK_Success;
1835
1836   // C++0x [temp.deduct.type]p9:
1837   //   If P has a form that contains <T> or <i>, then each argument Pi of the
1838   //   respective template argument list P is compared with the corresponding
1839   //   argument Ai of the corresponding template argument list of A.
1840   unsigned ArgIdx = 0, ParamIdx = 0;
1841   for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
1842        ++ParamIdx) {
1843     if (!Params[ParamIdx].isPackExpansion()) {
1844       // The simple case: deduce template arguments by matching Pi and Ai.
1845
1846       // Check whether we have enough arguments.
1847       if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
1848         return Sema::TDK_Success;
1849
1850       if (Args[ArgIdx].isPackExpansion()) {
1851         // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
1852         // but applied to pack expansions that are template arguments.
1853         return Sema::TDK_MiscellaneousDeductionFailure;
1854       }
1855
1856       // Perform deduction for this Pi/Ai pair.
1857       if (Sema::TemplateDeductionResult Result
1858             = DeduceTemplateArguments(S, TemplateParams,
1859                                       Params[ParamIdx], Args[ArgIdx],
1860                                       Info, Deduced))
1861         return Result;
1862
1863       // Move to the next argument.
1864       ++ArgIdx;
1865       continue;
1866     }
1867
1868     // The parameter is a pack expansion.
1869
1870     // C++0x [temp.deduct.type]p9:
1871     //   If Pi is a pack expansion, then the pattern of Pi is compared with
1872     //   each remaining argument in the template argument list of A. Each
1873     //   comparison deduces template arguments for subsequent positions in the
1874     //   template parameter packs expanded by Pi.
1875     TemplateArgument Pattern = Params[ParamIdx].getPackExpansionPattern();
1876
1877     // FIXME: If there are no remaining arguments, we can bail out early
1878     // and set any deduced parameter packs to an empty argument pack.
1879     // The latter part of this is a (minor) correctness issue.
1880
1881     // Prepare to deduce the packs within the pattern.
1882     PackDeductionScope PackScope(S, TemplateParams, Deduced, Info, Pattern);
1883
1884     // Keep track of the deduced template arguments for each parameter pack
1885     // expanded by this pack expansion (the outer index) and for each
1886     // template argument (the inner SmallVectors).
1887     bool HasAnyArguments = false;
1888     for (; hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs); ++ArgIdx) {
1889       HasAnyArguments = true;
1890
1891       // Deduce template arguments from the pattern.
1892       if (Sema::TemplateDeductionResult Result
1893             = DeduceTemplateArguments(S, TemplateParams, Pattern, Args[ArgIdx],
1894                                       Info, Deduced))
1895         return Result;
1896
1897       PackScope.nextPackElement();
1898     }
1899
1900     // Build argument packs for each of the parameter packs expanded by this
1901     // pack expansion.
1902     if (auto Result = PackScope.finish(HasAnyArguments))
1903       return Result;
1904   }
1905
1906   return Sema::TDK_Success;
1907 }
1908
1909 static Sema::TemplateDeductionResult
1910 DeduceTemplateArguments(Sema &S,
1911                         TemplateParameterList *TemplateParams,
1912                         const TemplateArgumentList &ParamList,
1913                         const TemplateArgumentList &ArgList,
1914                         TemplateDeductionInfo &Info,
1915                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
1916   return DeduceTemplateArguments(S, TemplateParams,
1917                                  ParamList.data(), ParamList.size(),
1918                                  ArgList.data(), ArgList.size(),
1919                                  Info, Deduced);
1920 }
1921
1922 /// \brief Determine whether two template arguments are the same.
1923 static bool isSameTemplateArg(ASTContext &Context,
1924                               const TemplateArgument &X,
1925                               const TemplateArgument &Y) {
1926   if (X.getKind() != Y.getKind())
1927     return false;
1928
1929   switch (X.getKind()) {
1930     case TemplateArgument::Null:
1931       llvm_unreachable("Comparing NULL template argument");
1932
1933     case TemplateArgument::Type:
1934       return Context.getCanonicalType(X.getAsType()) ==
1935              Context.getCanonicalType(Y.getAsType());
1936
1937     case TemplateArgument::Declaration:
1938       return isSameDeclaration(X.getAsDecl(), Y.getAsDecl());
1939
1940     case TemplateArgument::NullPtr:
1941       return Context.hasSameType(X.getNullPtrType(), Y.getNullPtrType());
1942
1943     case TemplateArgument::Template:
1944     case TemplateArgument::TemplateExpansion:
1945       return Context.getCanonicalTemplateName(
1946                     X.getAsTemplateOrTemplatePattern()).getAsVoidPointer() ==
1947              Context.getCanonicalTemplateName(
1948                     Y.getAsTemplateOrTemplatePattern()).getAsVoidPointer();
1949
1950     case TemplateArgument::Integral:
1951       return X.getAsIntegral() == Y.getAsIntegral();
1952
1953     case TemplateArgument::Expression: {
1954       llvm::FoldingSetNodeID XID, YID;
1955       X.getAsExpr()->Profile(XID, Context, true);
1956       Y.getAsExpr()->Profile(YID, Context, true);
1957       return XID == YID;
1958     }
1959
1960     case TemplateArgument::Pack:
1961       if (X.pack_size() != Y.pack_size())
1962         return false;
1963
1964       for (TemplateArgument::pack_iterator XP = X.pack_begin(),
1965                                         XPEnd = X.pack_end(),
1966                                            YP = Y.pack_begin();
1967            XP != XPEnd; ++XP, ++YP)
1968         if (!isSameTemplateArg(Context, *XP, *YP))
1969           return false;
1970
1971       return true;
1972   }
1973
1974   llvm_unreachable("Invalid TemplateArgument Kind!");
1975 }
1976
1977 /// \brief Allocate a TemplateArgumentLoc where all locations have
1978 /// been initialized to the given location.
1979 ///
1980 /// \param S The semantic analysis object.
1981 ///
1982 /// \param Arg The template argument we are producing template argument
1983 /// location information for.
1984 ///
1985 /// \param NTTPType For a declaration template argument, the type of
1986 /// the non-type template parameter that corresponds to this template
1987 /// argument.
1988 ///
1989 /// \param Loc The source location to use for the resulting template
1990 /// argument.
1991 static TemplateArgumentLoc
1992 getTrivialTemplateArgumentLoc(Sema &S,
1993                               const TemplateArgument &Arg,
1994                               QualType NTTPType,
1995                               SourceLocation Loc) {
1996   switch (Arg.getKind()) {
1997   case TemplateArgument::Null:
1998     llvm_unreachable("Can't get a NULL template argument here");
1999
2000   case TemplateArgument::Type:
2001     return TemplateArgumentLoc(Arg,
2002                      S.Context.getTrivialTypeSourceInfo(Arg.getAsType(), Loc));
2003
2004   case TemplateArgument::Declaration: {
2005     Expr *E
2006       = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2007           .getAs<Expr>();
2008     return TemplateArgumentLoc(TemplateArgument(E), E);
2009   }
2010
2011   case TemplateArgument::NullPtr: {
2012     Expr *E
2013       = S.BuildExpressionFromDeclTemplateArgument(Arg, NTTPType, Loc)
2014           .getAs<Expr>();
2015     return TemplateArgumentLoc(TemplateArgument(NTTPType, /*isNullPtr*/true),
2016                                E);
2017   }
2018
2019   case TemplateArgument::Integral: {
2020     Expr *E
2021       = S.BuildExpressionFromIntegralTemplateArgument(Arg, Loc).getAs<Expr>();
2022     return TemplateArgumentLoc(TemplateArgument(E), E);
2023   }
2024
2025     case TemplateArgument::Template:
2026     case TemplateArgument::TemplateExpansion: {
2027       NestedNameSpecifierLocBuilder Builder;
2028       TemplateName Template = Arg.getAsTemplate();
2029       if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
2030         Builder.MakeTrivial(S.Context, DTN->getQualifier(), Loc);
2031       else if (QualifiedTemplateName *QTN =
2032                    Template.getAsQualifiedTemplateName())
2033         Builder.MakeTrivial(S.Context, QTN->getQualifier(), Loc);
2034       
2035       if (Arg.getKind() == TemplateArgument::Template)
2036         return TemplateArgumentLoc(Arg, 
2037                                    Builder.getWithLocInContext(S.Context),
2038                                    Loc);
2039       
2040       
2041       return TemplateArgumentLoc(Arg, Builder.getWithLocInContext(S.Context),
2042                                  Loc, Loc);
2043     }
2044
2045   case TemplateArgument::Expression:
2046     return TemplateArgumentLoc(Arg, Arg.getAsExpr());
2047
2048   case TemplateArgument::Pack:
2049     return TemplateArgumentLoc(Arg, TemplateArgumentLocInfo());
2050   }
2051
2052   llvm_unreachable("Invalid TemplateArgument Kind!");
2053 }
2054
2055
2056 /// \brief Convert the given deduced template argument and add it to the set of
2057 /// fully-converted template arguments.
2058 static bool
2059 ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param,
2060                                DeducedTemplateArgument Arg,
2061                                NamedDecl *Template,
2062                                QualType NTTPType,
2063                                unsigned ArgumentPackIndex,
2064                                TemplateDeductionInfo &Info,
2065                                bool InFunctionTemplate,
2066                                SmallVectorImpl<TemplateArgument> &Output) {
2067   if (Arg.getKind() == TemplateArgument::Pack) {
2068     // This is a template argument pack, so check each of its arguments against
2069     // the template parameter.
2070     SmallVector<TemplateArgument, 2> PackedArgsBuilder;
2071     for (const auto &P : Arg.pack_elements()) {
2072       // When converting the deduced template argument, append it to the
2073       // general output list. We need to do this so that the template argument
2074       // checking logic has all of the prior template arguments available.
2075       DeducedTemplateArgument InnerArg(P);
2076       InnerArg.setDeducedFromArrayBound(Arg.wasDeducedFromArrayBound());
2077       if (ConvertDeducedTemplateArgument(S, Param, InnerArg, Template,
2078                                          NTTPType, PackedArgsBuilder.size(),
2079                                          Info, InFunctionTemplate, Output))
2080         return true;
2081
2082       // Move the converted template argument into our argument pack.
2083       PackedArgsBuilder.push_back(Output.pop_back_val());
2084     }
2085
2086     // Create the resulting argument pack.
2087     Output.push_back(
2088         TemplateArgument::CreatePackCopy(S.Context, PackedArgsBuilder));
2089     return false;
2090   }
2091
2092   // Convert the deduced template argument into a template
2093   // argument that we can check, almost as if the user had written
2094   // the template argument explicitly.
2095   TemplateArgumentLoc ArgLoc = getTrivialTemplateArgumentLoc(S, Arg, NTTPType,
2096                                                              Info.getLocation());
2097
2098   // Check the template argument, converting it as necessary.
2099   return S.CheckTemplateArgument(Param, ArgLoc,
2100                                  Template,
2101                                  Template->getLocation(),
2102                                  Template->getSourceRange().getEnd(),
2103                                  ArgumentPackIndex,
2104                                  Output,
2105                                  InFunctionTemplate
2106                                   ? (Arg.wasDeducedFromArrayBound()
2107                                        ? Sema::CTAK_DeducedFromArrayBound
2108                                        : Sema::CTAK_Deduced)
2109                                  : Sema::CTAK_Specified);
2110 }
2111
2112 /// Complete template argument deduction for a class template partial
2113 /// specialization.
2114 static Sema::TemplateDeductionResult
2115 FinishTemplateArgumentDeduction(Sema &S,
2116                                 ClassTemplatePartialSpecializationDecl *Partial,
2117                                 const TemplateArgumentList &TemplateArgs,
2118                       SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2119                                 TemplateDeductionInfo &Info) {
2120   // Unevaluated SFINAE context.
2121   EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2122   Sema::SFINAETrap Trap(S);
2123
2124   Sema::ContextRAII SavedContext(S, Partial);
2125
2126   // C++ [temp.deduct.type]p2:
2127   //   [...] or if any template argument remains neither deduced nor
2128   //   explicitly specified, template argument deduction fails.
2129   SmallVector<TemplateArgument, 4> Builder;
2130   TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2131   for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2132     NamedDecl *Param = PartialParams->getParam(I);
2133     if (Deduced[I].isNull()) {
2134       Info.Param = makeTemplateParameter(Param);
2135       return Sema::TDK_Incomplete;
2136     }
2137
2138     // We have deduced this argument, so it still needs to be
2139     // checked and converted.
2140
2141     // First, for a non-type template parameter type that is
2142     // initialized by a declaration, we need the type of the
2143     // corresponding non-type template parameter.
2144     QualType NTTPType;
2145     if (NonTypeTemplateParmDecl *NTTP
2146                                   = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2147       NTTPType = NTTP->getType();
2148       if (NTTPType->isDependentType()) {
2149         TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2150                                           Builder.data(), Builder.size());
2151         NTTPType = S.SubstType(NTTPType,
2152                                MultiLevelTemplateArgumentList(TemplateArgs),
2153                                NTTP->getLocation(),
2154                                NTTP->getDeclName());
2155         if (NTTPType.isNull()) {
2156           Info.Param = makeTemplateParameter(Param);
2157           // FIXME: These template arguments are temporary. Free them!
2158           Info.reset(TemplateArgumentList::CreateCopy(S.Context,
2159                                                       Builder.data(),
2160                                                       Builder.size()));
2161           return Sema::TDK_SubstitutionFailure;
2162         }
2163       }
2164     }
2165
2166     if (ConvertDeducedTemplateArgument(S, Param, Deduced[I],
2167                                        Partial, NTTPType, 0, Info, false,
2168                                        Builder)) {
2169       Info.Param = makeTemplateParameter(Param);
2170       // FIXME: These template arguments are temporary. Free them!
2171       Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2172                                                   Builder.size()));
2173       return Sema::TDK_SubstitutionFailure;
2174     }
2175   }
2176
2177   // Form the template argument list from the deduced template arguments.
2178   TemplateArgumentList *DeducedArgumentList
2179     = TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2180                                        Builder.size());
2181
2182   Info.reset(DeducedArgumentList);
2183
2184   // Substitute the deduced template arguments into the template
2185   // arguments of the class template partial specialization, and
2186   // verify that the instantiated template arguments are both valid
2187   // and are equivalent to the template arguments originally provided
2188   // to the class template.
2189   LocalInstantiationScope InstScope(S);
2190   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
2191   const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2192     = Partial->getTemplateArgsAsWritten();
2193   const TemplateArgumentLoc *PartialTemplateArgs
2194     = PartialTemplArgInfo->getTemplateArgs();
2195
2196   TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2197                                     PartialTemplArgInfo->RAngleLoc);
2198
2199   if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2200               InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2201     unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2202     if (ParamIdx >= Partial->getTemplateParameters()->size())
2203       ParamIdx = Partial->getTemplateParameters()->size() - 1;
2204
2205     Decl *Param
2206       = const_cast<NamedDecl *>(
2207                           Partial->getTemplateParameters()->getParam(ParamIdx));
2208     Info.Param = makeTemplateParameter(Param);
2209     Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2210     return Sema::TDK_SubstitutionFailure;
2211   }
2212
2213   SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2214   if (S.CheckTemplateArgumentList(ClassTemplate, Partial->getLocation(),
2215                                   InstArgs, false, ConvertedInstArgs))
2216     return Sema::TDK_SubstitutionFailure;
2217
2218   TemplateParameterList *TemplateParams
2219     = ClassTemplate->getTemplateParameters();
2220   for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2221     TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2222     if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2223       Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2224       Info.FirstArg = TemplateArgs[I];
2225       Info.SecondArg = InstArg;
2226       return Sema::TDK_NonDeducedMismatch;
2227     }
2228   }
2229
2230   if (Trap.hasErrorOccurred())
2231     return Sema::TDK_SubstitutionFailure;
2232
2233   return Sema::TDK_Success;
2234 }
2235
2236 /// \brief Perform template argument deduction to determine whether
2237 /// the given template arguments match the given class template
2238 /// partial specialization per C++ [temp.class.spec.match].
2239 Sema::TemplateDeductionResult
2240 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
2241                               const TemplateArgumentList &TemplateArgs,
2242                               TemplateDeductionInfo &Info) {
2243   if (Partial->isInvalidDecl())
2244     return TDK_Invalid;
2245
2246   // C++ [temp.class.spec.match]p2:
2247   //   A partial specialization matches a given actual template
2248   //   argument list if the template arguments of the partial
2249   //   specialization can be deduced from the actual template argument
2250   //   list (14.8.2).
2251
2252   // Unevaluated SFINAE context.
2253   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2254   SFINAETrap Trap(*this);
2255
2256   SmallVector<DeducedTemplateArgument, 4> Deduced;
2257   Deduced.resize(Partial->getTemplateParameters()->size());
2258   if (TemplateDeductionResult Result
2259         = ::DeduceTemplateArguments(*this,
2260                                     Partial->getTemplateParameters(),
2261                                     Partial->getTemplateArgs(),
2262                                     TemplateArgs, Info, Deduced))
2263     return Result;
2264
2265   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2266   InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2267                              Info);
2268   if (Inst.isInvalid())
2269     return TDK_InstantiationDepth;
2270
2271   if (Trap.hasErrorOccurred())
2272     return Sema::TDK_SubstitutionFailure;
2273
2274   return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2275                                            Deduced, Info);
2276 }
2277
2278 /// Complete template argument deduction for a variable template partial
2279 /// specialization.
2280 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2281 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
2282 ///        VarTemplate(Partial)SpecializationDecl with a new data
2283 ///        structure Template(Partial)SpecializationDecl, and
2284 ///        using Template(Partial)SpecializationDecl as input type.
2285 static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction(
2286     Sema &S, VarTemplatePartialSpecializationDecl *Partial,
2287     const TemplateArgumentList &TemplateArgs,
2288     SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2289     TemplateDeductionInfo &Info) {
2290   // Unevaluated SFINAE context.
2291   EnterExpressionEvaluationContext Unevaluated(S, Sema::Unevaluated);
2292   Sema::SFINAETrap Trap(S);
2293
2294   // C++ [temp.deduct.type]p2:
2295   //   [...] or if any template argument remains neither deduced nor
2296   //   explicitly specified, template argument deduction fails.
2297   SmallVector<TemplateArgument, 4> Builder;
2298   TemplateParameterList *PartialParams = Partial->getTemplateParameters();
2299   for (unsigned I = 0, N = PartialParams->size(); I != N; ++I) {
2300     NamedDecl *Param = PartialParams->getParam(I);
2301     if (Deduced[I].isNull()) {
2302       Info.Param = makeTemplateParameter(Param);
2303       return Sema::TDK_Incomplete;
2304     }
2305
2306     // We have deduced this argument, so it still needs to be
2307     // checked and converted.
2308
2309     // First, for a non-type template parameter type that is
2310     // initialized by a declaration, we need the type of the
2311     // corresponding non-type template parameter.
2312     QualType NTTPType;
2313     if (NonTypeTemplateParmDecl *NTTP =
2314             dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2315       NTTPType = NTTP->getType();
2316       if (NTTPType->isDependentType()) {
2317         TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2318                                           Builder.data(), Builder.size());
2319         NTTPType =
2320             S.SubstType(NTTPType, MultiLevelTemplateArgumentList(TemplateArgs),
2321                         NTTP->getLocation(), NTTP->getDeclName());
2322         if (NTTPType.isNull()) {
2323           Info.Param = makeTemplateParameter(Param);
2324           // FIXME: These template arguments are temporary. Free them!
2325           Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2326                                                       Builder.size()));
2327           return Sema::TDK_SubstitutionFailure;
2328         }
2329       }
2330     }
2331
2332     if (ConvertDeducedTemplateArgument(S, Param, Deduced[I], Partial, NTTPType,
2333                                        0, Info, false, Builder)) {
2334       Info.Param = makeTemplateParameter(Param);
2335       // FIXME: These template arguments are temporary. Free them!
2336       Info.reset(TemplateArgumentList::CreateCopy(S.Context, Builder.data(),
2337                                                   Builder.size()));
2338       return Sema::TDK_SubstitutionFailure;
2339     }
2340   }
2341
2342   // Form the template argument list from the deduced template arguments.
2343   TemplateArgumentList *DeducedArgumentList = TemplateArgumentList::CreateCopy(
2344       S.Context, Builder.data(), Builder.size());
2345
2346   Info.reset(DeducedArgumentList);
2347
2348   // Substitute the deduced template arguments into the template
2349   // arguments of the class template partial specialization, and
2350   // verify that the instantiated template arguments are both valid
2351   // and are equivalent to the template arguments originally provided
2352   // to the class template.
2353   LocalInstantiationScope InstScope(S);
2354   VarTemplateDecl *VarTemplate = Partial->getSpecializedTemplate();
2355   const ASTTemplateArgumentListInfo *PartialTemplArgInfo
2356     = Partial->getTemplateArgsAsWritten();
2357   const TemplateArgumentLoc *PartialTemplateArgs
2358     = PartialTemplArgInfo->getTemplateArgs();
2359
2360   TemplateArgumentListInfo InstArgs(PartialTemplArgInfo->LAngleLoc,
2361                                     PartialTemplArgInfo->RAngleLoc);
2362
2363   if (S.Subst(PartialTemplateArgs, PartialTemplArgInfo->NumTemplateArgs,
2364               InstArgs, MultiLevelTemplateArgumentList(*DeducedArgumentList))) {
2365     unsigned ArgIdx = InstArgs.size(), ParamIdx = ArgIdx;
2366     if (ParamIdx >= Partial->getTemplateParameters()->size())
2367       ParamIdx = Partial->getTemplateParameters()->size() - 1;
2368
2369     Decl *Param = const_cast<NamedDecl *>(
2370         Partial->getTemplateParameters()->getParam(ParamIdx));
2371     Info.Param = makeTemplateParameter(Param);
2372     Info.FirstArg = PartialTemplateArgs[ArgIdx].getArgument();
2373     return Sema::TDK_SubstitutionFailure;
2374   }
2375   SmallVector<TemplateArgument, 4> ConvertedInstArgs;
2376   if (S.CheckTemplateArgumentList(VarTemplate, Partial->getLocation(), InstArgs,
2377                                   false, ConvertedInstArgs))
2378     return Sema::TDK_SubstitutionFailure;
2379
2380   TemplateParameterList *TemplateParams = VarTemplate->getTemplateParameters();
2381   for (unsigned I = 0, E = TemplateParams->size(); I != E; ++I) {
2382     TemplateArgument InstArg = ConvertedInstArgs.data()[I];
2383     if (!isSameTemplateArg(S.Context, TemplateArgs[I], InstArg)) {
2384       Info.Param = makeTemplateParameter(TemplateParams->getParam(I));
2385       Info.FirstArg = TemplateArgs[I];
2386       Info.SecondArg = InstArg;
2387       return Sema::TDK_NonDeducedMismatch;
2388     }
2389   }
2390
2391   if (Trap.hasErrorOccurred())
2392     return Sema::TDK_SubstitutionFailure;
2393
2394   return Sema::TDK_Success;
2395 }
2396
2397 /// \brief Perform template argument deduction to determine whether
2398 /// the given template arguments match the given variable template
2399 /// partial specialization per C++ [temp.class.spec.match].
2400 /// TODO: Unify with ClassTemplatePartialSpecializationDecl version?
2401 ///       May require unifying ClassTemplate(Partial)SpecializationDecl and
2402 ///        VarTemplate(Partial)SpecializationDecl with a new data
2403 ///        structure Template(Partial)SpecializationDecl, and
2404 ///        using Template(Partial)SpecializationDecl as input type.
2405 Sema::TemplateDeductionResult
2406 Sema::DeduceTemplateArguments(VarTemplatePartialSpecializationDecl *Partial,
2407                               const TemplateArgumentList &TemplateArgs,
2408                               TemplateDeductionInfo &Info) {
2409   if (Partial->isInvalidDecl())
2410     return TDK_Invalid;
2411
2412   // C++ [temp.class.spec.match]p2:
2413   //   A partial specialization matches a given actual template
2414   //   argument list if the template arguments of the partial
2415   //   specialization can be deduced from the actual template argument
2416   //   list (14.8.2).
2417
2418   // Unevaluated SFINAE context.
2419   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2420   SFINAETrap Trap(*this);
2421
2422   SmallVector<DeducedTemplateArgument, 4> Deduced;
2423   Deduced.resize(Partial->getTemplateParameters()->size());
2424   if (TemplateDeductionResult Result = ::DeduceTemplateArguments(
2425           *this, Partial->getTemplateParameters(), Partial->getTemplateArgs(),
2426           TemplateArgs, Info, Deduced))
2427     return Result;
2428
2429   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2430   InstantiatingTemplate Inst(*this, Info.getLocation(), Partial, DeducedArgs,
2431                              Info);
2432   if (Inst.isInvalid())
2433     return TDK_InstantiationDepth;
2434
2435   if (Trap.hasErrorOccurred())
2436     return Sema::TDK_SubstitutionFailure;
2437
2438   return ::FinishTemplateArgumentDeduction(*this, Partial, TemplateArgs,
2439                                            Deduced, Info);
2440 }
2441
2442 /// \brief Determine whether the given type T is a simple-template-id type.
2443 static bool isSimpleTemplateIdType(QualType T) {
2444   if (const TemplateSpecializationType *Spec
2445         = T->getAs<TemplateSpecializationType>())
2446     return Spec->getTemplateName().getAsTemplateDecl() != nullptr;
2447
2448   return false;
2449 }
2450
2451 /// \brief Substitute the explicitly-provided template arguments into the
2452 /// given function template according to C++ [temp.arg.explicit].
2453 ///
2454 /// \param FunctionTemplate the function template into which the explicit
2455 /// template arguments will be substituted.
2456 ///
2457 /// \param ExplicitTemplateArgs the explicitly-specified template
2458 /// arguments.
2459 ///
2460 /// \param Deduced the deduced template arguments, which will be populated
2461 /// with the converted and checked explicit template arguments.
2462 ///
2463 /// \param ParamTypes will be populated with the instantiated function
2464 /// parameters.
2465 ///
2466 /// \param FunctionType if non-NULL, the result type of the function template
2467 /// will also be instantiated and the pointed-to value will be updated with
2468 /// the instantiated function type.
2469 ///
2470 /// \param Info if substitution fails for any reason, this object will be
2471 /// populated with more information about the failure.
2472 ///
2473 /// \returns TDK_Success if substitution was successful, or some failure
2474 /// condition.
2475 Sema::TemplateDeductionResult
2476 Sema::SubstituteExplicitTemplateArguments(
2477                                       FunctionTemplateDecl *FunctionTemplate,
2478                                TemplateArgumentListInfo &ExplicitTemplateArgs,
2479                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2480                                  SmallVectorImpl<QualType> &ParamTypes,
2481                                           QualType *FunctionType,
2482                                           TemplateDeductionInfo &Info) {
2483   FunctionDecl *Function = FunctionTemplate->getTemplatedDecl();
2484   TemplateParameterList *TemplateParams
2485     = FunctionTemplate->getTemplateParameters();
2486
2487   if (ExplicitTemplateArgs.size() == 0) {
2488     // No arguments to substitute; just copy over the parameter types and
2489     // fill in the function type.
2490     for (auto P : Function->params())
2491       ParamTypes.push_back(P->getType());
2492
2493     if (FunctionType)
2494       *FunctionType = Function->getType();
2495     return TDK_Success;
2496   }
2497
2498   // Unevaluated SFINAE context.
2499   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2500   SFINAETrap Trap(*this);
2501
2502   // C++ [temp.arg.explicit]p3:
2503   //   Template arguments that are present shall be specified in the
2504   //   declaration order of their corresponding template-parameters. The
2505   //   template argument list shall not specify more template-arguments than
2506   //   there are corresponding template-parameters.
2507   SmallVector<TemplateArgument, 4> Builder;
2508
2509   // Enter a new template instantiation context where we check the
2510   // explicitly-specified template arguments against this function template,
2511   // and then substitute them into the function parameter types.
2512   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2513   InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2514                              DeducedArgs,
2515            ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution,
2516                              Info);
2517   if (Inst.isInvalid())
2518     return TDK_InstantiationDepth;
2519
2520   if (CheckTemplateArgumentList(FunctionTemplate,
2521                                 SourceLocation(),
2522                                 ExplicitTemplateArgs,
2523                                 true,
2524                                 Builder) || Trap.hasErrorOccurred()) {
2525     unsigned Index = Builder.size();
2526     if (Index >= TemplateParams->size())
2527       Index = TemplateParams->size() - 1;
2528     Info.Param = makeTemplateParameter(TemplateParams->getParam(Index));
2529     return TDK_InvalidExplicitArguments;
2530   }
2531
2532   // Form the template argument list from the explicitly-specified
2533   // template arguments.
2534   TemplateArgumentList *ExplicitArgumentList
2535     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2536   Info.reset(ExplicitArgumentList);
2537
2538   // Template argument deduction and the final substitution should be
2539   // done in the context of the templated declaration.  Explicit
2540   // argument substitution, on the other hand, needs to happen in the
2541   // calling context.
2542   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2543
2544   // If we deduced template arguments for a template parameter pack,
2545   // note that the template argument pack is partially substituted and record
2546   // the explicit template arguments. They'll be used as part of deduction
2547   // for this template parameter pack.
2548   for (unsigned I = 0, N = Builder.size(); I != N; ++I) {
2549     const TemplateArgument &Arg = Builder[I];
2550     if (Arg.getKind() == TemplateArgument::Pack) {
2551       CurrentInstantiationScope->SetPartiallySubstitutedPack(
2552                                                  TemplateParams->getParam(I),
2553                                                              Arg.pack_begin(),
2554                                                              Arg.pack_size());
2555       break;
2556     }
2557   }
2558
2559   const FunctionProtoType *Proto
2560     = Function->getType()->getAs<FunctionProtoType>();
2561   assert(Proto && "Function template does not have a prototype?");
2562
2563   // Isolate our substituted parameters from our caller.
2564   LocalInstantiationScope InstScope(*this, /*MergeWithOuterScope*/true);
2565
2566   // Instantiate the types of each of the function parameters given the
2567   // explicitly-specified template arguments. If the function has a trailing
2568   // return type, substitute it after the arguments to ensure we substitute
2569   // in lexical order.
2570   if (Proto->hasTrailingReturn()) {
2571     if (SubstParmTypes(Function->getLocation(),
2572                        Function->param_begin(), Function->getNumParams(),
2573                        MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2574                        ParamTypes))
2575       return TDK_SubstitutionFailure;
2576   }
2577   
2578   // Instantiate the return type.
2579   QualType ResultType;
2580   {
2581     // C++11 [expr.prim.general]p3:
2582     //   If a declaration declares a member function or member function 
2583     //   template of a class X, the expression this is a prvalue of type 
2584     //   "pointer to cv-qualifier-seq X" between the optional cv-qualifer-seq
2585     //   and the end of the function-definition, member-declarator, or 
2586     //   declarator.
2587     unsigned ThisTypeQuals = 0;
2588     CXXRecordDecl *ThisContext = nullptr;
2589     if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Function)) {
2590       ThisContext = Method->getParent();
2591       ThisTypeQuals = Method->getTypeQualifiers();
2592     }
2593       
2594     CXXThisScopeRAII ThisScope(*this, ThisContext, ThisTypeQuals,
2595                                getLangOpts().CPlusPlus11);
2596
2597     ResultType =
2598         SubstType(Proto->getReturnType(),
2599                   MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2600                   Function->getTypeSpecStartLoc(), Function->getDeclName());
2601     if (ResultType.isNull() || Trap.hasErrorOccurred())
2602       return TDK_SubstitutionFailure;
2603   }
2604   
2605   // Instantiate the types of each of the function parameters given the
2606   // explicitly-specified template arguments if we didn't do so earlier.
2607   if (!Proto->hasTrailingReturn() &&
2608       SubstParmTypes(Function->getLocation(),
2609                      Function->param_begin(), Function->getNumParams(),
2610                      MultiLevelTemplateArgumentList(*ExplicitArgumentList),
2611                      ParamTypes))
2612     return TDK_SubstitutionFailure;
2613
2614   if (FunctionType) {
2615     *FunctionType = BuildFunctionType(ResultType, ParamTypes,
2616                                       Function->getLocation(),
2617                                       Function->getDeclName(),
2618                                       Proto->getExtProtoInfo());
2619     if (FunctionType->isNull() || Trap.hasErrorOccurred())
2620       return TDK_SubstitutionFailure;
2621   }
2622
2623   // C++ [temp.arg.explicit]p2:
2624   //   Trailing template arguments that can be deduced (14.8.2) may be
2625   //   omitted from the list of explicit template-arguments. If all of the
2626   //   template arguments can be deduced, they may all be omitted; in this
2627   //   case, the empty template argument list <> itself may also be omitted.
2628   //
2629   // Take all of the explicitly-specified arguments and put them into
2630   // the set of deduced template arguments. Explicitly-specified
2631   // parameter packs, however, will be set to NULL since the deduction
2632   // mechanisms handle explicitly-specified argument packs directly.
2633   Deduced.reserve(TemplateParams->size());
2634   for (unsigned I = 0, N = ExplicitArgumentList->size(); I != N; ++I) {
2635     const TemplateArgument &Arg = ExplicitArgumentList->get(I);
2636     if (Arg.getKind() == TemplateArgument::Pack)
2637       Deduced.push_back(DeducedTemplateArgument());
2638     else
2639       Deduced.push_back(Arg);
2640   }
2641
2642   return TDK_Success;
2643 }
2644
2645 /// \brief Check whether the deduced argument type for a call to a function
2646 /// template matches the actual argument type per C++ [temp.deduct.call]p4.
2647 static bool 
2648 CheckOriginalCallArgDeduction(Sema &S, Sema::OriginalCallArg OriginalArg, 
2649                               QualType DeducedA) {
2650   ASTContext &Context = S.Context;
2651   
2652   QualType A = OriginalArg.OriginalArgType;
2653   QualType OriginalParamType = OriginalArg.OriginalParamType;
2654   
2655   // Check for type equality (top-level cv-qualifiers are ignored).
2656   if (Context.hasSameUnqualifiedType(A, DeducedA))
2657     return false;
2658   
2659   // Strip off references on the argument types; they aren't needed for
2660   // the following checks.
2661   if (const ReferenceType *DeducedARef = DeducedA->getAs<ReferenceType>())
2662     DeducedA = DeducedARef->getPointeeType();
2663   if (const ReferenceType *ARef = A->getAs<ReferenceType>())
2664     A = ARef->getPointeeType();
2665   
2666   // C++ [temp.deduct.call]p4:
2667   //   [...] However, there are three cases that allow a difference:
2668   //     - If the original P is a reference type, the deduced A (i.e., the 
2669   //       type referred to by the reference) can be more cv-qualified than 
2670   //       the transformed A.
2671   if (const ReferenceType *OriginalParamRef
2672       = OriginalParamType->getAs<ReferenceType>()) {
2673     // We don't want to keep the reference around any more.
2674     OriginalParamType = OriginalParamRef->getPointeeType();
2675     
2676     Qualifiers AQuals = A.getQualifiers();
2677     Qualifiers DeducedAQuals = DeducedA.getQualifiers();
2678
2679     // Under Objective-C++ ARC, the deduced type may have implicitly
2680     // been given strong or (when dealing with a const reference)
2681     // unsafe_unretained lifetime. If so, update the original
2682     // qualifiers to include this lifetime.
2683     if (S.getLangOpts().ObjCAutoRefCount &&
2684         ((DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_Strong &&
2685           AQuals.getObjCLifetime() == Qualifiers::OCL_None) ||
2686          (DeducedAQuals.hasConst() &&
2687           DeducedAQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone))) {
2688       AQuals.setObjCLifetime(DeducedAQuals.getObjCLifetime());
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 play nicely with qualification 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(SourceLocation(), 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.
2753 Sema::TemplateDeductionResult
2754 Sema::FinishTemplateArgumentDeduction(FunctionTemplateDecl *FunctionTemplate,
2755                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
2756                                       unsigned NumExplicitlySpecified,
2757                                       FunctionDecl *&Specialization,
2758                                       TemplateDeductionInfo &Info,
2759         SmallVectorImpl<OriginalCallArg> const *OriginalCallArgs,
2760                                       bool PartialOverloading) {
2761   TemplateParameterList *TemplateParams
2762     = FunctionTemplate->getTemplateParameters();
2763
2764   // Unevaluated SFINAE context.
2765   EnterExpressionEvaluationContext Unevaluated(*this, Sema::Unevaluated);
2766   SFINAETrap Trap(*this);
2767
2768   // Enter a new template instantiation context while we instantiate the
2769   // actual function declaration.
2770   SmallVector<TemplateArgument, 4> DeducedArgs(Deduced.begin(), Deduced.end());
2771   InstantiatingTemplate Inst(*this, Info.getLocation(), FunctionTemplate,
2772                              DeducedArgs,
2773               ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution,
2774                              Info);
2775   if (Inst.isInvalid())
2776     return TDK_InstantiationDepth;
2777
2778   ContextRAII SavedContext(*this, FunctionTemplate->getTemplatedDecl());
2779
2780   // C++ [temp.deduct.type]p2:
2781   //   [...] or if any template argument remains neither deduced nor
2782   //   explicitly specified, template argument deduction fails.
2783   SmallVector<TemplateArgument, 4> Builder;
2784   for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
2785     NamedDecl *Param = TemplateParams->getParam(I);
2786
2787     if (!Deduced[I].isNull()) {
2788       if (I < NumExplicitlySpecified) {
2789         // We have already fully type-checked and converted this
2790         // argument, because it was explicitly-specified. Just record the
2791         // presence of this argument.
2792         Builder.push_back(Deduced[I]);
2793         // We may have had explicitly-specified template arguments for a
2794         // template parameter pack (that may or may not have been extended
2795         // via additional deduced arguments).
2796         if (Param->isParameterPack() && CurrentInstantiationScope) {
2797           if (CurrentInstantiationScope->getPartiallySubstitutedPack() ==
2798               Param) {
2799             // Forget the partially-substituted pack; its substitution is now
2800             // complete.
2801             CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2802           }
2803         }
2804         continue;
2805       }
2806       // We have deduced this argument, so it still needs to be
2807       // checked and converted.
2808
2809       // First, for a non-type template parameter type that is
2810       // initialized by a declaration, we need the type of the
2811       // corresponding non-type template parameter.
2812       QualType NTTPType;
2813       if (NonTypeTemplateParmDecl *NTTP
2814                                 = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2815         NTTPType = NTTP->getType();
2816         if (NTTPType->isDependentType()) {
2817           TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2818                                             Builder.data(), Builder.size());
2819           NTTPType = SubstType(NTTPType,
2820                                MultiLevelTemplateArgumentList(TemplateArgs),
2821                                NTTP->getLocation(),
2822                                NTTP->getDeclName());
2823           if (NTTPType.isNull()) {
2824             Info.Param = makeTemplateParameter(Param);
2825             // FIXME: These template arguments are temporary. Free them!
2826             Info.reset(TemplateArgumentList::CreateCopy(Context,
2827                                                         Builder.data(),
2828                                                         Builder.size()));
2829             return TDK_SubstitutionFailure;
2830           }
2831         }
2832       }
2833
2834       if (ConvertDeducedTemplateArgument(*this, Param, Deduced[I],
2835                                          FunctionTemplate, NTTPType, 0, Info,
2836                                          true, Builder)) {
2837         Info.Param = makeTemplateParameter(Param);
2838         // FIXME: These template arguments are temporary. Free them!
2839         Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2840                                                     Builder.size()));
2841         return TDK_SubstitutionFailure;
2842       }
2843
2844       continue;
2845     }
2846
2847     // C++0x [temp.arg.explicit]p3:
2848     //    A trailing template parameter pack (14.5.3) not otherwise deduced will
2849     //    be deduced to an empty sequence of template arguments.
2850     // FIXME: Where did the word "trailing" come from?
2851     if (Param->isTemplateParameterPack()) {
2852       // We may have had explicitly-specified template arguments for this
2853       // template parameter pack. If so, our empty deduction extends the
2854       // explicitly-specified set (C++0x [temp.arg.explicit]p9).
2855       const TemplateArgument *ExplicitArgs;
2856       unsigned NumExplicitArgs;
2857       if (CurrentInstantiationScope &&
2858           CurrentInstantiationScope->getPartiallySubstitutedPack(&ExplicitArgs,
2859                                                              &NumExplicitArgs)
2860             == Param) {
2861         Builder.push_back(TemplateArgument(
2862             llvm::makeArrayRef(ExplicitArgs, NumExplicitArgs)));
2863
2864         // Forget the partially-substituted pack; it's substitution is now
2865         // complete.
2866         CurrentInstantiationScope->ResetPartiallySubstitutedPack();
2867       } else {
2868         Builder.push_back(TemplateArgument::getEmptyPack());
2869       }
2870       continue;
2871     }
2872
2873     // Substitute into the default template argument, if available.
2874     bool HasDefaultArg = false;
2875     TemplateArgumentLoc DefArg
2876       = SubstDefaultTemplateArgumentIfAvailable(FunctionTemplate,
2877                                               FunctionTemplate->getLocation(),
2878                                   FunctionTemplate->getSourceRange().getEnd(),
2879                                                 Param,
2880                                                 Builder, HasDefaultArg);
2881
2882     // If there was no default argument, deduction is incomplete.
2883     if (DefArg.getArgument().isNull()) {
2884       Info.Param = makeTemplateParameter(
2885                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2886       Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2887                                                   Builder.size()));
2888       if (PartialOverloading) break;
2889
2890       return HasDefaultArg ? TDK_SubstitutionFailure : TDK_Incomplete;
2891     }
2892
2893     // Check whether we can actually use the default argument.
2894     if (CheckTemplateArgument(Param, DefArg,
2895                               FunctionTemplate,
2896                               FunctionTemplate->getLocation(),
2897                               FunctionTemplate->getSourceRange().getEnd(),
2898                               0, Builder,
2899                               CTAK_Specified)) {
2900       Info.Param = makeTemplateParameter(
2901                          const_cast<NamedDecl *>(TemplateParams->getParam(I)));
2902       // FIXME: These template arguments are temporary. Free them!
2903       Info.reset(TemplateArgumentList::CreateCopy(Context, Builder.data(),
2904                                                   Builder.size()));
2905       return TDK_SubstitutionFailure;
2906     }
2907
2908     // If we get here, we successfully used the default template argument.
2909   }
2910
2911   // Form the template argument list from the deduced template arguments.
2912   TemplateArgumentList *DeducedArgumentList
2913     = TemplateArgumentList::CreateCopy(Context, Builder.data(), Builder.size());
2914   Info.reset(DeducedArgumentList);
2915
2916   // Substitute the deduced template arguments into the function template
2917   // declaration to produce the function template specialization.
2918   DeclContext *Owner = FunctionTemplate->getDeclContext();
2919   if (FunctionTemplate->getFriendObjectKind())
2920     Owner = FunctionTemplate->getLexicalDeclContext();
2921   Specialization = cast_or_null<FunctionDecl>(
2922                       SubstDecl(FunctionTemplate->getTemplatedDecl(), Owner,
2923                          MultiLevelTemplateArgumentList(*DeducedArgumentList)));
2924   if (!Specialization || Specialization->isInvalidDecl())
2925     return TDK_SubstitutionFailure;
2926
2927   assert(Specialization->getPrimaryTemplate()->getCanonicalDecl() ==
2928          FunctionTemplate->getCanonicalDecl());
2929
2930   // If the template argument list is owned by the function template
2931   // specialization, release it.
2932   if (Specialization->getTemplateSpecializationArgs() == DeducedArgumentList &&
2933       !Trap.hasErrorOccurred())
2934     Info.take();
2935
2936   // There may have been an error that did not prevent us from constructing a
2937   // declaration. Mark the declaration invalid and return with a substitution
2938   // failure.
2939   if (Trap.hasErrorOccurred()) {
2940     Specialization->setInvalidDecl(true);
2941     return TDK_SubstitutionFailure;
2942   }
2943
2944   if (OriginalCallArgs) {
2945     // C++ [temp.deduct.call]p4:
2946     //   In general, the deduction process attempts to find template argument
2947     //   values that will make the deduced A identical to A (after the type A 
2948     //   is transformed as described above). [...]
2949     for (unsigned I = 0, N = OriginalCallArgs->size(); I != N; ++I) {
2950       OriginalCallArg OriginalArg = (*OriginalCallArgs)[I];
2951       unsigned ParamIdx = OriginalArg.ArgIdx;
2952       
2953       if (ParamIdx >= Specialization->getNumParams())
2954         continue;
2955       
2956       QualType DeducedA = Specialization->getParamDecl(ParamIdx)->getType();
2957       if (CheckOriginalCallArgDeduction(*this, OriginalArg, DeducedA))
2958         return Sema::TDK_SubstitutionFailure;
2959     }
2960   }
2961   
2962   // If we suppressed any diagnostics while performing template argument
2963   // deduction, and if we haven't already instantiated this declaration,
2964   // keep track of these diagnostics. They'll be emitted if this specialization
2965   // is actually used.
2966   if (Info.diag_begin() != Info.diag_end()) {
2967     SuppressedDiagnosticsMap::iterator
2968       Pos = SuppressedDiagnostics.find(Specialization->getCanonicalDecl());
2969     if (Pos == SuppressedDiagnostics.end())
2970         SuppressedDiagnostics[Specialization->getCanonicalDecl()]
2971           .append(Info.diag_begin(), Info.diag_end());
2972   }
2973
2974   return TDK_Success;
2975 }
2976
2977 /// Gets the type of a function for template-argument-deducton
2978 /// purposes when it's considered as part of an overload set.
2979 static QualType GetTypeOfFunction(Sema &S, const OverloadExpr::FindResult &R,
2980                                   FunctionDecl *Fn) {
2981   // We may need to deduce the return type of the function now.
2982   if (S.getLangOpts().CPlusPlus14 && Fn->getReturnType()->isUndeducedType() &&
2983       S.DeduceReturnType(Fn, R.Expression->getExprLoc(), /*Diagnose*/ false))
2984     return QualType();
2985
2986   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Fn))
2987     if (Method->isInstance()) {
2988       // An instance method that's referenced in a form that doesn't
2989       // look like a member pointer is just invalid.
2990       if (!R.HasFormOfMemberPointer) return QualType();
2991
2992       return S.Context.getMemberPointerType(Fn->getType(),
2993                S.Context.getTypeDeclType(Method->getParent()).getTypePtr());
2994     }
2995
2996   if (!R.IsAddressOfOperand) return Fn->getType();
2997   return S.Context.getPointerType(Fn->getType());
2998 }
2999
3000 /// Apply the deduction rules for overload sets.
3001 ///
3002 /// \return the null type if this argument should be treated as an
3003 /// undeduced context
3004 static QualType
3005 ResolveOverloadForDeduction(Sema &S, TemplateParameterList *TemplateParams,
3006                             Expr *Arg, QualType ParamType,
3007                             bool ParamWasReference) {
3008
3009   OverloadExpr::FindResult R = OverloadExpr::find(Arg);
3010
3011   OverloadExpr *Ovl = R.Expression;
3012
3013   // C++0x [temp.deduct.call]p4
3014   unsigned TDF = 0;
3015   if (ParamWasReference)
3016     TDF |= TDF_ParamWithReferenceType;
3017   if (R.IsAddressOfOperand)
3018     TDF |= TDF_IgnoreQualifiers;
3019
3020   // C++0x [temp.deduct.call]p6:
3021   //   When P is a function type, pointer to function type, or pointer
3022   //   to member function type:
3023
3024   if (!ParamType->isFunctionType() &&
3025       !ParamType->isFunctionPointerType() &&
3026       !ParamType->isMemberFunctionPointerType()) {
3027     if (Ovl->hasExplicitTemplateArgs()) {
3028       // But we can still look for an explicit specialization.
3029       if (FunctionDecl *ExplicitSpec
3030             = S.ResolveSingleFunctionTemplateSpecialization(Ovl))
3031         return GetTypeOfFunction(S, R, ExplicitSpec);
3032     }
3033
3034     return QualType();
3035   }
3036   
3037   // Gather the explicit template arguments, if any.
3038   TemplateArgumentListInfo ExplicitTemplateArgs;
3039   if (Ovl->hasExplicitTemplateArgs())
3040     Ovl->copyTemplateArgumentsInto(ExplicitTemplateArgs);
3041   QualType Match;
3042   for (UnresolvedSetIterator I = Ovl->decls_begin(),
3043          E = Ovl->decls_end(); I != E; ++I) {
3044     NamedDecl *D = (*I)->getUnderlyingDecl();
3045
3046     if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(D)) {
3047       //   - If the argument is an overload set containing one or more
3048       //     function templates, the parameter is treated as a
3049       //     non-deduced context.
3050       if (!Ovl->hasExplicitTemplateArgs())
3051         return QualType();
3052       
3053       // Otherwise, see if we can resolve a function type 
3054       FunctionDecl *Specialization = nullptr;
3055       TemplateDeductionInfo Info(Ovl->getNameLoc());
3056       if (S.DeduceTemplateArguments(FunTmpl, &ExplicitTemplateArgs,
3057                                     Specialization, Info))
3058         continue;
3059       
3060       D = Specialization;
3061     }
3062
3063     FunctionDecl *Fn = cast<FunctionDecl>(D);
3064     QualType ArgType = GetTypeOfFunction(S, R, Fn);
3065     if (ArgType.isNull()) continue;
3066
3067     // Function-to-pointer conversion.
3068     if (!ParamWasReference && ParamType->isPointerType() &&
3069         ArgType->isFunctionType())
3070       ArgType = S.Context.getPointerType(ArgType);
3071
3072     //   - If the argument is an overload set (not containing function
3073     //     templates), trial argument deduction is attempted using each
3074     //     of the members of the set. If deduction succeeds for only one
3075     //     of the overload set members, that member is used as the
3076     //     argument value for the deduction. If deduction succeeds for
3077     //     more than one member of the overload set the parameter is
3078     //     treated as a non-deduced context.
3079
3080     // We do all of this in a fresh context per C++0x [temp.deduct.type]p2:
3081     //   Type deduction is done independently for each P/A pair, and
3082     //   the deduced template argument values are then combined.
3083     // So we do not reject deductions which were made elsewhere.
3084     SmallVector<DeducedTemplateArgument, 8>
3085       Deduced(TemplateParams->size());
3086     TemplateDeductionInfo Info(Ovl->getNameLoc());
3087     Sema::TemplateDeductionResult Result
3088       = DeduceTemplateArgumentsByTypeMatch(S, TemplateParams, ParamType,
3089                                            ArgType, Info, Deduced, TDF);
3090     if (Result) continue;
3091     if (!Match.isNull()) return QualType();
3092     Match = ArgType;
3093   }
3094
3095   return Match;
3096 }
3097
3098 /// \brief Perform the adjustments to the parameter and argument types
3099 /// described in C++ [temp.deduct.call].
3100 ///
3101 /// \returns true if the caller should not attempt to perform any template
3102 /// argument deduction based on this P/A pair because the argument is an
3103 /// overloaded function set that could not be resolved.
3104 static bool AdjustFunctionParmAndArgTypesForDeduction(Sema &S,
3105                                           TemplateParameterList *TemplateParams,
3106                                                       QualType &ParamType,
3107                                                       QualType &ArgType,
3108                                                       Expr *Arg,
3109                                                       unsigned &TDF) {
3110   // C++0x [temp.deduct.call]p3:
3111   //   If P is a cv-qualified type, the top level cv-qualifiers of P's type
3112   //   are ignored for type deduction.
3113   if (ParamType.hasQualifiers())
3114     ParamType = ParamType.getUnqualifiedType();
3115
3116   //   [...] If P is a reference type, the type referred to by P is
3117   //   used for type deduction.
3118   const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>();
3119   if (ParamRefType)
3120     ParamType = ParamRefType->getPointeeType();
3121
3122   // Overload sets usually make this parameter an undeduced context,
3123   // but there are sometimes special circumstances.  Typically
3124   // involving a template-id-expr.
3125   if (ArgType == S.Context.OverloadTy) {
3126     ArgType = ResolveOverloadForDeduction(S, TemplateParams,
3127                                           Arg, ParamType,
3128                                           ParamRefType != nullptr);
3129     if (ArgType.isNull())
3130       return true;
3131   }
3132
3133   if (ParamRefType) {
3134     // If the argument has incomplete array type, try to complete its type.
3135     if (ArgType->isIncompleteArrayType()) {
3136       S.completeExprArrayBound(Arg);
3137       ArgType = Arg->getType();
3138     }
3139
3140     // C++0x [temp.deduct.call]p3:
3141     //   If P is an rvalue reference to a cv-unqualified template
3142     //   parameter and the argument is an lvalue, the type "lvalue
3143     //   reference to A" is used in place of A for type deduction.
3144     if (ParamRefType->isRValueReferenceType() &&
3145         !ParamType.getQualifiers() &&
3146         isa<TemplateTypeParmType>(ParamType) &&
3147         Arg->isLValue())
3148       ArgType = S.Context.getLValueReferenceType(ArgType);
3149   } else {
3150     // C++ [temp.deduct.call]p2:
3151     //   If P is not a reference type:
3152     //   - If A is an array type, the pointer type produced by the
3153     //     array-to-pointer standard conversion (4.2) is used in place of
3154     //     A for type deduction; otherwise,
3155     if (ArgType->isArrayType())
3156       ArgType = S.Context.getArrayDecayedType(ArgType);
3157     //   - If A is a function type, the pointer type produced by the
3158     //     function-to-pointer standard conversion (4.3) is used in place
3159     //     of A for type deduction; otherwise,
3160     else if (ArgType->isFunctionType())
3161       ArgType = S.Context.getPointerType(ArgType);
3162     else {
3163       // - If A is a cv-qualified type, the top level cv-qualifiers of A's
3164       //   type are ignored for type deduction.
3165       ArgType = ArgType.getUnqualifiedType();
3166     }
3167   }
3168
3169   // C++0x [temp.deduct.call]p4:
3170   //   In general, the deduction process attempts to find template argument
3171   //   values that will make the deduced A identical to A (after the type A
3172   //   is transformed as described above). [...]
3173   TDF = TDF_SkipNonDependent;
3174
3175   //     - If the original P is a reference type, the deduced A (i.e., the
3176   //       type referred to by the reference) can be more cv-qualified than
3177   //       the transformed A.
3178   if (ParamRefType)
3179     TDF |= TDF_ParamWithReferenceType;
3180   //     - The transformed A can be another pointer or pointer to member
3181   //       type that can be converted to the deduced A via a qualification
3182   //       conversion (4.4).
3183   if (ArgType->isPointerType() || ArgType->isMemberPointerType() ||
3184       ArgType->isObjCObjectPointerType())
3185     TDF |= TDF_IgnoreQualifiers;
3186   //     - If P is a class and P has the form simple-template-id, then the
3187   //       transformed A can be a derived class of the deduced A. Likewise,
3188   //       if P is a pointer to a class of the form simple-template-id, the
3189   //       transformed A can be a pointer to a derived class pointed to by
3190   //       the deduced A.
3191   if (isSimpleTemplateIdType(ParamType) ||
3192       (isa<PointerType>(ParamType) &&
3193        isSimpleTemplateIdType(
3194                               ParamType->getAs<PointerType>()->getPointeeType())))
3195     TDF |= TDF_DerivedClass;
3196
3197   return false;
3198 }
3199
3200 static bool
3201 hasDeducibleTemplateParameters(Sema &S, FunctionTemplateDecl *FunctionTemplate,
3202                                QualType T);
3203
3204 static Sema::TemplateDeductionResult DeduceTemplateArgumentByListElement(
3205     Sema &S, TemplateParameterList *TemplateParams, QualType ParamType,
3206     Expr *Arg, TemplateDeductionInfo &Info,
3207     SmallVectorImpl<DeducedTemplateArgument> &Deduced, unsigned TDF);
3208
3209 /// \brief Attempt template argument deduction from an initializer list
3210 ///        deemed to be an argument in a function call.
3211 static bool
3212 DeduceFromInitializerList(Sema &S, TemplateParameterList *TemplateParams,
3213                           QualType AdjustedParamType, InitListExpr *ILE,
3214                           TemplateDeductionInfo &Info,
3215                           SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3216                           unsigned TDF, Sema::TemplateDeductionResult &Result) {
3217
3218   // [temp.deduct.call] p1 (post CWG-1591)
3219   // If removing references and cv-qualifiers from P gives
3220   // std::initializer_list<P0> or P0[N] for some P0 and N and the argument is a
3221   // non-empty initializer list (8.5.4), then deduction is performed instead for
3222   // each element of the initializer list, taking P0 as a function template
3223   // parameter type and the initializer element as its argument, and in the
3224   // P0[N] case, if N is a non-type template parameter, N is deduced from the
3225   // length of the initializer list. Otherwise, an initializer list argument
3226   // causes the parameter to be considered a non-deduced context
3227
3228   const bool IsConstSizedArray = AdjustedParamType->isConstantArrayType();
3229
3230   const bool IsDependentSizedArray =
3231       !IsConstSizedArray && AdjustedParamType->isDependentSizedArrayType();
3232
3233   QualType ElTy;  // The element type of the std::initializer_list or the array.
3234
3235   const bool IsSTDList = !IsConstSizedArray && !IsDependentSizedArray &&
3236                          S.isStdInitializerList(AdjustedParamType, &ElTy);
3237
3238   if (!IsConstSizedArray && !IsDependentSizedArray && !IsSTDList)
3239     return false;
3240
3241   Result = Sema::TDK_Success;
3242   // If we are not deducing against the 'T' in a std::initializer_list<T> then
3243   // deduce against the 'T' in T[N].
3244   if (ElTy.isNull()) {
3245     assert(!IsSTDList);
3246     ElTy = S.Context.getAsArrayType(AdjustedParamType)->getElementType();
3247   }
3248   // Deduction only needs to be done for dependent types.
3249   if (ElTy->isDependentType()) {
3250     for (Expr *E : ILE->inits()) {
3251       if ((Result = DeduceTemplateArgumentByListElement(S, TemplateParams, ElTy,
3252                                                         E, Info, Deduced, TDF)))
3253         return true;
3254     }
3255   }
3256   if (IsDependentSizedArray) {
3257     const DependentSizedArrayType *ArrTy =
3258         S.Context.getAsDependentSizedArrayType(AdjustedParamType);
3259     // Determine the array bound is something we can deduce.
3260     if (NonTypeTemplateParmDecl *NTTP =
3261             getDeducedParameterFromExpr(ArrTy->getSizeExpr())) {
3262       // We can perform template argument deduction for the given non-type
3263       // template parameter.
3264       assert(NTTP->getDepth() == 0 &&
3265              "Cannot deduce non-type template argument at depth > 0");
3266       llvm::APInt Size(S.Context.getIntWidth(NTTP->getType()),
3267                        ILE->getNumInits());
3268
3269       Result = DeduceNonTypeTemplateArgument(
3270           S, NTTP, llvm::APSInt(Size), NTTP->getType(),
3271           /*ArrayBound=*/true, Info, Deduced);
3272     }
3273   }
3274   return true;
3275 }
3276
3277 /// \brief Perform template argument deduction by matching a parameter type
3278 ///        against a single expression, where the expression is an element of
3279 ///        an initializer list that was originally matched against a parameter
3280 ///        of type \c initializer_list\<ParamType\>.
3281 static Sema::TemplateDeductionResult
3282 DeduceTemplateArgumentByListElement(Sema &S,
3283                                     TemplateParameterList *TemplateParams,
3284                                     QualType ParamType, Expr *Arg,
3285                                     TemplateDeductionInfo &Info,
3286                               SmallVectorImpl<DeducedTemplateArgument> &Deduced,
3287                                     unsigned TDF) {
3288   // Handle the case where an init list contains another init list as the
3289   // element.
3290   if (InitListExpr *ILE = dyn_cast<InitListExpr>(Arg)) {
3291     Sema::TemplateDeductionResult Result;
3292  &nb