Bug Summary

File:tools/clang/lib/Sema/SemaTemplateDeduction.cpp
Warning:line 757, column 3
Potential leak of memory pointed to by 'SawIndices.X'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name SemaTemplateDeduction.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -relaxed-aliasing -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-8/lib/clang/8.0.0 -D CLANG_VENDOR="Debian " -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/tools/clang/lib/Sema -I /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/lib/Sema -I /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn350071/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/8.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-8~svn350071/build-llvm/tools/clang/lib/Sema -fdebug-prefix-map=/build/llvm-toolchain-snapshot-8~svn350071=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-27-042839-1215-1 -x c++ /build/llvm-toolchain-snapshot-8~svn350071/tools/clang/lib/Sema/SemaTemplateDeduction.cpp -faddrsig

/build/llvm-toolchain-snapshot-8~svn350071/tools/clang/lib/Sema/SemaTemplateDeduction.cpp

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

/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h

1//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the SmallBitVector class.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ADT_SMALLBITVECTOR_H
15#define LLVM_ADT_SMALLBITVECTOR_H
16
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/Support/MathExtras.h"
20#include <algorithm>
21#include <cassert>
22#include <climits>
23#include <cstddef>
24#include <cstdint>
25#include <limits>
26#include <utility>
27
28namespace llvm {
29
30/// This is a 'bitvector' (really, a variable-sized bit array), optimized for
31/// the case when the array is small. It contains one pointer-sized field, which
32/// is directly used as a plain collection of bits when possible, or as a
33/// pointer to a larger heap-allocated array when necessary. This allows normal
34/// "small" cases to be fast without losing generality for large inputs.
35class SmallBitVector {
36 // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
37 // unnecessary level of indirection. It would be more efficient to use a
38 // pointer to memory containing size, allocation size, and the array of bits.
39 uintptr_t X = 1;
40
41 enum {
42 // The number of bits in this class.
43 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT8,
44
45 // One bit is used to discriminate between small and large mode. The
46 // remaining bits are used for the small-mode representation.
47 SmallNumRawBits = NumBaseBits - 1,
48
49 // A few more bits are used to store the size of the bit set in small mode.
50 // Theoretically this is a ceil-log2. These bits are encoded in the most
51 // significant bits of the raw bits.
52 SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
53 NumBaseBits == 64 ? 6 :
54 SmallNumRawBits),
55
56 // The remaining bits are used to store the actual set in small mode.
57 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
58 };
59
60 static_assert(NumBaseBits == 64 || NumBaseBits == 32,
61 "Unsupported word size");
62
63public:
64 using size_type = unsigned;
65
66 // Encapsulation of a single bit.
67 class reference {
68 SmallBitVector &TheVector;
69 unsigned BitPos;
70
71 public:
72 reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
73
74 reference(const reference&) = default;
75
76 reference& operator=(reference t) {
77 *this = bool(t);
78 return *this;
79 }
80
81 reference& operator=(bool t) {
82 if (t)
83 TheVector.set(BitPos);
84 else
85 TheVector.reset(BitPos);
86 return *this;
87 }
88
89 operator bool() const {
90 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
91 }
92 };
93
94private:
95 BitVector *getPointer() const {
96 assert(!isSmall())((!isSmall()) ? static_cast<void> (0) : __assert_fail (
"!isSmall()", "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 96, __PRETTY_FUNCTION__))
;
97 return reinterpret_cast<BitVector *>(X);
98 }
99
100 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
101 X = 1;
102 setSmallSize(NewSize);
103 setSmallBits(NewSmallBits);
104 }
105
106 void switchToLarge(BitVector *BV) {
107 X = reinterpret_cast<uintptr_t>(BV);
108 assert(!isSmall() && "Tried to use an unaligned pointer")((!isSmall() && "Tried to use an unaligned pointer") ?
static_cast<void> (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\""
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 108, __PRETTY_FUNCTION__))
;
109 }
110
111 // Return all the bits used for the "small" representation; this includes
112 // bits for the size as well as the element bits.
113 uintptr_t getSmallRawBits() const {
114 assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 114, __PRETTY_FUNCTION__))
;
115 return X >> 1;
116 }
117
118 void setSmallRawBits(uintptr_t NewRawBits) {
119 assert(isSmall())((isSmall()) ? static_cast<void> (0) : __assert_fail ("isSmall()"
, "/build/llvm-toolchain-snapshot-8~svn350071/include/llvm/ADT/SmallBitVector.h"
, 119, __PRETTY_FUNCTION__))
;
120 X = (NewRawBits << 1) | uintptr_t(1);
121 }
122
123 // Return the size.
124 size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
125
126 void setSmallSize(size_t Size) {
127 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
128 }
129
130 // Return the element bits.
131 uintptr_t getSmallBits() const {
132 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
133 }
134
135 void setSmallBits(uintptr_t NewBits) {
136 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
137 (getSmallSize() << SmallNumDataBits));
138 }
139
140public:
141 /// Creates an empty bitvector.
142 SmallBitVector() = default;
143
144 /// Creates a bitvector of specified number of bits. All bits are initialized
145 /// to the specified value.
146 explicit SmallBitVector(unsigned s, bool t = false) {
147 if (s <= SmallNumDataBits)
16
Assuming 's' is > SmallNumDataBits
17
Taking false branch
148 switchToSmall(t ? ~uintptr_t(0) : 0, s);
149 else
150 switchToLarge(new BitVector(s, t));
18
Memory is allocated
151 }
152
153 /// SmallBitVector copy ctor.
154 SmallBitVector(const SmallBitVector &RHS) {
155 if (RHS.isSmall())
156 X = RHS.X;
157 else
158 switchToLarge(new BitVector(*RHS.getPointer()));
159 }
160
161 SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
162 RHS.X = 1;
163 }
164
165 ~SmallBitVector() {
166 if (!isSmall())
167 delete getPointer();
168 }
169
170 using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
171 using set_iterator = const_set_bits_iterator;
172
173 const_set_bits_iterator set_bits_begin() const {
174 return const_set_bits_iterator(*this);
175 }
176
177 const_set_bits_iterator set_bits_end() const {
178 return const_set_bits_iterator(*this, -1);
179 }
180
181 iterator_range<const_set_bits_iterator> set_bits() const {
182 return make_range(set_bits_begin(), set_bits_end());
183 }
184
185 bool isSmall() const { return X & uintptr_t(1); }
186
187 /// Tests whether there are no bits in this bitvector.
188 bool empty() const {
189 return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
190 }
191
192 /// Returns the number of bits in this bitvector.
193 size_t size() const {
194 return isSmall() ? getSmallSize() : getPointer()->size();
195 }
196
197 /// Returns the number of bits which are set.
198 size_type count() const {
199 if (isSmall()) {
200 uintptr_t Bits = getSmallBits();
201 return countPopulation(Bits);
202 }
203 return getPointer()->count();
204 }
205
206 /// Returns true if any bit is set.
207 bool any() const {
208 if (isSmall())
209 return getSmallBits() != 0;
210 return getPointer()->any();
211 }
212
213 /// Returns true if all bits are set.
214 bool all() const {
215 if (isSmall())
216 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
217 return getPointer()->all();
218 }
219
220 /// Returns true if none of the bits are set.
221 bool none() const {
222 if (isSmall())
223 return getSmallBits() == 0;
224 return getPointer()->none();
225 }
226
227 /// Returns the index of the first set bit, -1 if none of the bits are set.
228 int find_first() const {
229 if (isSmall()) {
230 uintptr_t Bits = getSmallBits();
231 if (Bits == 0)
232 return -1;
233 return countTrailingZeros(Bits);
234 }
235 return getPointer()->find_first();
236 }
237
238 int find_last() const {
239 if (isSmall()) {
240 uintptr_t Bits = getSmallBits();
241 if (Bits == 0)
242 return -1;
243 return NumBaseBits - countLeadingZeros(Bits) - 1;
244 }
245 return getPointer()->find_last();
246 }
247
248 /// Returns the index of the first unset bit, -1 if all of the bits are set.
249 int find_first_unset() const {
250 if (isSmall()) {
251 if (count() == getSmallSize())
252 return -1;
253
254 uintptr_t Bits = getSmallBits();
255 return countTrailingOnes(Bits);
256 }
257 return getPointer()->find_first_unset();
258 }
259
260 int find_last_unset() const {
261 if (isSmall()) {
262 if (count() == getSmallSize())
263 return -1;
264
265 uintptr_t Bits = getSmallBits();
266 // Set unused bits.
267 Bits |= ~uintptr_t(0) << getSmallSize();
268 return NumBaseBits - countLeadingOnes(Bits) - 1;
269 }
270 return getPointer()->find_last_unset();
271 }
272
273 /// Returns the index of the next set bit following the "Prev" bit.
274 /// Returns -1 if the next set bit is not found.
275 int find_next(unsigned Prev) const {
276 if (isSmall()) {
277 uintptr_t Bits = getSmallBits();
278 // Mask off previous bits.
279 Bits &= ~uintptr_t(0) << (Prev + 1);
280 if (Bits == 0 || Prev + 1 >= getSmallSize())
281 return -1;
282 return countTrailingZeros(Bits);
283 }
284 return getPointer()->find_next(Prev);
285 }
286
287 /// Returns the index of the next unset bit following the "Prev" bit.
288 /// Returns -1 if the next unset bit is not found.
289 int find_next_unset(unsigned Prev) const {
290 if (isSmall()) {
291 ++Prev;
292 uintptr_t Bits = getSmallBits();
293 // Mask in previous bits.
294 uintptr_t Mask = (1 << Prev) - 1;
295 Bits |= Mask;
296
297 if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
298 return -1;
299 return countTrailingOnes(Bits);
300 }
301 return getPointer()->find_next_unset(Prev);
302 }
303
304 /// find_prev - Returns the index of the first set bit that precedes the