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