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