Bug Summary

File:tools/clang/lib/Sema/SemaTemplateDeduction.cpp
Warning:line 753, column 23
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-eagerly-assume -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 -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-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/tools/clang/lib/Sema -I /build/llvm-toolchain-snapshot-7~svn326246/tools/clang/lib/Sema -I /build/llvm-toolchain-snapshot-7~svn326246/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/tools/clang/include -I /build/llvm-toolchain-snapshot-7~svn326246/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn326246/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.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-7~svn326246/build-llvm/tools/clang/lib/Sema -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fno-common -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-02-28-041547-14988-1 -x c++ /build/llvm-toolchain-snapshot-7~svn326246/tools/clang/lib/Sema/SemaTemplateDeduction.cpp

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

/build/llvm-toolchain-snapshot-7~svn326246/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 bool isSmall() const {
96 return X & uintptr_t(1);
97 }
98
99 BitVector *getPointer() const {
100 assert(!isSmall())(static_cast <bool> (!isSmall()) ? void (0) : __assert_fail
("!isSmall()", "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 100, __extension__ __PRETTY_FUNCTION__))
;
101 return reinterpret_cast<BitVector *>(X);
102 }
103
104 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
105 X = 1;
106 setSmallSize(NewSize);
107 setSmallBits(NewSmallBits);
108 }
109
110 void switchToLarge(BitVector *BV) {
111 X = reinterpret_cast<uintptr_t>(BV);
112 assert(!isSmall() && "Tried to use an unaligned pointer")(static_cast <bool> (!isSmall() && "Tried to use an unaligned pointer"
) ? void (0) : __assert_fail ("!isSmall() && \"Tried to use an unaligned pointer\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 112, __extension__ __PRETTY_FUNCTION__))
;
113 }
114
115 // Return all the bits used for the "small" representation; this includes
116 // bits for the size as well as the element bits.
117 uintptr_t getSmallRawBits() const {
118 assert(isSmall())(static_cast <bool> (isSmall()) ? void (0) : __assert_fail
("isSmall()", "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 118, __extension__ __PRETTY_FUNCTION__))
;
119 return X >> 1;
120 }
121
122 void setSmallRawBits(uintptr_t NewRawBits) {
123 assert(isSmall())(static_cast <bool> (isSmall()) ? void (0) : __assert_fail
("isSmall()", "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 123, __extension__ __PRETTY_FUNCTION__))
;
124 X = (NewRawBits << 1) | uintptr_t(1);
125 }
126
127 // Return the size.
128 size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
129
130 void setSmallSize(size_t Size) {
131 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
132 }
133
134 // Return the element bits.
135 uintptr_t getSmallBits() const {
136 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137 }
138
139 void setSmallBits(uintptr_t NewBits) {
140 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
141 (getSmallSize() << SmallNumDataBits));
142 }
143
144public:
145 /// Creates an empty bitvector.
146 SmallBitVector() = default;
147
148 /// Creates a bitvector of specified number of bits. All bits are initialized
149 /// to the specified value.
150 explicit SmallBitVector(unsigned s, bool t = false) {
151 if (s <= SmallNumDataBits)
38
Assuming 's' is > SmallNumDataBits
39
Taking false branch
152 switchToSmall(t ? ~uintptr_t(0) : 0, s);
153 else
154 switchToLarge(new BitVector(s, t));
40
Memory is allocated
155 }
156
157 /// SmallBitVector copy ctor.
158 SmallBitVector(const SmallBitVector &RHS) {
159 if (RHS.isSmall())
160 X = RHS.X;
161 else
162 switchToLarge(new BitVector(*RHS.getPointer()));
163 }
164
165 SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
166 RHS.X = 1;
167 }
168
169 ~SmallBitVector() {
170 if (!isSmall())
171 delete getPointer();
172 }
173
174 using const_set_bits_iterator = const_set_bits_iterator_impl<SmallBitVector>;
175 using set_iterator = const_set_bits_iterator;
176
177 const_set_bits_iterator set_bits_begin() const {
178 return const_set_bits_iterator(*this);
179 }
180
181 const_set_bits_iterator set_bits_end() const {
182 return const_set_bits_iterator(*this, -1);
183 }
184
185 iterator_range<const_set_bits_iterator> set_bits() const {
186 return make_range(set_bits_begin(), set_bits_end());
187 }
188
189 /// Tests whether there are no bits in this bitvector.
190 bool empty() const {
191 return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
192 }
193
194 /// Returns the number of bits in this bitvector.
195 size_t size() const {
196 return isSmall() ? getSmallSize() : getPointer()->size();
197 }
198
199 /// Returns the number of bits which are set.
200 size_type count() const {
201 if (isSmall()) {
202 uintptr_t Bits = getSmallBits();
203 return countPopulation(Bits);
204 }
205 return getPointer()->count();
206 }
207
208 /// Returns true if any bit is set.
209 bool any() const {
210 if (isSmall())
211 return getSmallBits() != 0;
212 return getPointer()->any();
213 }
214
215 /// Returns true if all bits are set.
216 bool all() const {
217 if (isSmall())
218 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
219 return getPointer()->all();
220 }
221
222 /// Returns true if none of the bits are set.
223 bool none() const {
224 if (isSmall())
225 return getSmallBits() == 0;
226 return getPointer()->none();
227 }
228
229 /// Returns the index of the first set bit, -1 if none of the bits are set.
230 int find_first() const {
231 if (isSmall()) {
232 uintptr_t Bits = getSmallBits();
233 if (Bits == 0)
234 return -1;
235 return countTrailingZeros(Bits);
236 }
237 return getPointer()->find_first();
238 }
239
240 int find_last() const {
241 if (isSmall()) {
242 uintptr_t Bits = getSmallBits();
243 if (Bits == 0)
244 return -1;
245 return NumBaseBits - countLeadingZeros(Bits);
246 }
247 return getPointer()->find_last();
248 }
249
250 /// Returns the index of the first unset bit, -1 if all of the bits are set.
251 int find_first_unset() const {
252 if (isSmall()) {
253 if (count() == getSmallSize())
254 return -1;
255
256 uintptr_t Bits = getSmallBits();
257 return countTrailingOnes(Bits);
258 }
259 return getPointer()->find_first_unset();
260 }
261
262 int find_last_unset() const {
263 if (isSmall()) {
264 if (count() == getSmallSize())
265 return -1;
266
267 uintptr_t Bits = getSmallBits();
268 return NumBaseBits - countLeadingOnes(Bits);
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
305 /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
306 int find_prev(unsigned PriorTo) const {
307 if (isSmall()) {
308 if (PriorTo == 0)
309 return -1;
310
311 --PriorTo;
312 uintptr_t Bits = getSmallBits();
313 Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
314 if (Bits == 0)
315 return -1;
316
317 return NumBaseBits - countLeadingZeros(Bits) - 1;
318 }
319 return getPointer()->find_prev(PriorTo);
320 }
321
322 /// Clear all bits.
323 void clear() {
324 if (!isSmall())
325 delete getPointer();
326 switchToSmall(0, 0);
327 }
328
329 /// Grow or shrink the bitvector.
330 void resize(unsigned N, bool t = false) {
331 if (!isSmall()) {
332 getPointer()->resize(N, t);
333 } else if (SmallNumDataBits >= N) {
334 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
335 setSmallSize(N);
336 setSmallBits(NewBits | getSmallBits());
337 } else {
338 BitVector *BV = new BitVector(N, t);
339 uintptr_t OldBits = getSmallBits();
340 for (size_t i = 0, e = getSmallSize(); i != e; ++i)
341 (*BV)[i] = (OldBits >> i) & 1;
342 switchToLarge(BV);
343 }
344 }
345
346 void reserve(unsigned N) {
347 if (isSmall()) {
348 if (N > SmallNumDataBits) {
349 uintptr_t OldBits = getSmallRawBits();
350 size_t SmallSize = getSmallSize();
351 BitVector *BV = new BitVector(SmallSize);
352 for (size_t i = 0; i < SmallSize; ++i)
353 if ((OldBits >> i) & 1)
354 BV->set(i);
355 BV->reserve(N);
356 switchToLarge(BV);
357 }
358 } else {
359 getPointer()->reserve(N);
360 }
361 }
362
363 // Set, reset, flip
364 SmallBitVector &set() {
365 if (isSmall())
366 setSmallBits(~uintptr_t(0));
367 else
368 getPointer()->set();
369 return *this;
370 }
371
372 SmallBitVector &set(unsigned Idx) {
373 if (isSmall()) {
374 assert(Idx <= static_cast<unsigned>((static_cast <bool> (Idx <= static_cast<unsigned>
( std::numeric_limits<uintptr_t>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 376, __extension__ __PRETTY_FUNCTION__))
375 std::numeric_limits<uintptr_t>::digits) &&(static_cast <bool> (Idx <= static_cast<unsigned>
( std::numeric_limits<uintptr_t>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 376, __extension__ __PRETTY_FUNCTION__))
376 "undefined behavior")(static_cast <bool> (Idx <= static_cast<unsigned>
( std::numeric_limits<uintptr_t>::digits) && "undefined behavior"
) ? void (0) : __assert_fail ("Idx <= static_cast<unsigned>( std::numeric_limits<uintptr_t>::digits) && \"undefined behavior\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 376, __extension__ __PRETTY_FUNCTION__))
;
377 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
378 }
379 else
380 getPointer()->set(Idx);
381 return *this;
382 }
383
384 /// Efficiently set a range of bits in [I, E)
385 SmallBitVector &set(unsigned I, unsigned E) {
386 assert(I <= E && "Attempted to set backwards range!")(static_cast <bool> (I <= E && "Attempted to set backwards range!"
) ? void (0) : __assert_fail ("I <= E && \"Attempted to set backwards range!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 386, __extension__ __PRETTY_FUNCTION__))
;
387 assert(E <= size() && "Attempted to set out-of-bounds range!")(static_cast <bool> (E <= size() && "Attempted to set out-of-bounds range!"
) ? void (0) : __assert_fail ("E <= size() && \"Attempted to set out-of-bounds range!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 387, __extension__ __PRETTY_FUNCTION__))
;
388 if (I == E) return *this;
389 if (isSmall()) {
390 uintptr_t EMask = ((uintptr_t)1) << E;
391 uintptr_t IMask = ((uintptr_t)1) << I;
392 uintptr_t Mask = EMask - IMask;
393 setSmallBits(getSmallBits() | Mask);
394 } else
395 getPointer()->set(I, E);
396 return *this;
397 }
398
399 SmallBitVector &reset() {
400 if (isSmall())
401 setSmallBits(0);
402 else
403 getPointer()->reset();
404 return *this;
405 }
406
407 SmallBitVector &reset(unsigned Idx) {
408 if (isSmall())
409 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
410 else
411 getPointer()->reset(Idx);
412 return *this;
413 }
414
415 /// Efficiently reset a range of bits in [I, E)
416 SmallBitVector &reset(unsigned I, unsigned E) {
417 assert(I <= E && "Attempted to reset backwards range!")(static_cast <bool> (I <= E && "Attempted to reset backwards range!"
) ? void (0) : __assert_fail ("I <= E && \"Attempted to reset backwards range!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 417, __extension__ __PRETTY_FUNCTION__))
;
418 assert(E <= size() && "Attempted to reset out-of-bounds range!")(static_cast <bool> (E <= size() && "Attempted to reset out-of-bounds range!"
) ? void (0) : __assert_fail ("E <= size() && \"Attempted to reset out-of-bounds range!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 418, __extension__ __PRETTY_FUNCTION__))
;
419 if (I == E) return *this;
420 if (isSmall()) {
421 uintptr_t EMask = ((uintptr_t)1) << E;
422 uintptr_t IMask = ((uintptr_t)1) << I;
423 uintptr_t Mask = EMask - IMask;
424 setSmallBits(getSmallBits() & ~Mask);
425 } else
426 getPointer()->reset(I, E);
427 return *this;
428 }
429
430 SmallBitVector &flip() {
431 if (isSmall())
432 setSmallBits(~getSmallBits());
433 else
434 getPointer()->flip();
435 return *this;
436 }
437
438 SmallBitVector &flip(unsigned Idx) {
439 if (isSmall())
440 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
441 else
442 getPointer()->flip(Idx);
443 return *this;
444 }
445
446 // No argument flip.
447 SmallBitVector operator~() const {
448 return SmallBitVector(*this).flip();
449 }
450
451 // Indexing.
452 reference operator[](unsigned Idx) {
453 assert(Idx < size() && "Out-of-bounds Bit access.")(static_cast <bool> (Idx < size() && "Out-of-bounds Bit access."
) ? void (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 453, __extension__ __PRETTY_FUNCTION__))
;
454 return reference(*this, Idx);
455 }
456
457 bool operator[](unsigned Idx) const {
458 assert(Idx < size() && "Out-of-bounds Bit access.")(static_cast <bool> (Idx < size() && "Out-of-bounds Bit access."
) ? void (0) : __assert_fail ("Idx < size() && \"Out-of-bounds Bit access.\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 458, __extension__ __PRETTY_FUNCTION__))
;
459 if (isSmall())
460 return ((getSmallBits() >> Idx) & 1) != 0;
461 return getPointer()->operator[](Idx);
462 }
463
464 bool test(unsigned Idx) const {
465 return (*this)[Idx];
466 }
467
468 /// Test if any common bits are set.
469 bool anyCommon(const SmallBitVector &RHS) const {
470 if (isSmall() && RHS.isSmall())
471 return (getSmallBits() & RHS.getSmallBits()) != 0;
472 if (!isSmall() && !RHS.isSmall())
473 return getPointer()->anyCommon(*RHS.getPointer());
474
475 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
476 if (test(i) && RHS.test(i))
477 return true;
478 return false;
479 }
480
481 // Comparison operators.
482 bool operator==(const SmallBitVector &RHS) const {
483 if (size() != RHS.size())
484 return false;
485 if (isSmall())
486 return getSmallBits() == RHS.getSmallBits();
487 else
488 return *getPointer() == *RHS.getPointer();
489 }
490
491 bool operator!=(const SmallBitVector &RHS) const {
492 return !(*this == RHS);
493 }
494
495 // Intersection, union, disjoint union.
496 SmallBitVector &operator&=(const SmallBitVector &RHS) {
497 resize(std::max(size(), RHS.size()));
498 if (isSmall())
499 setSmallBits(getSmallBits() & RHS.getSmallBits());
500 else if (!RHS.isSmall())
501 getPointer()->operator&=(*RHS.getPointer());
502 else {
503 SmallBitVector Copy = RHS;
504 Copy.resize(size());
505 getPointer()->operator&=(*Copy.getPointer());
506 }
507 return *this;
508 }
509
510 /// Reset bits that are set in RHS. Same as *this &= ~RHS.
511 SmallBitVector &reset(const SmallBitVector &RHS) {
512 if (isSmall() && RHS.isSmall())
513 setSmallBits(getSmallBits() & ~RHS.getSmallBits());
514 else if (!isSmall() && !RHS.isSmall())
515 getPointer()->reset(*RHS.getPointer());
516 else
517 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
518 if (RHS.test(i))
519 reset(i);
520
521 return *this;
522 }
523
524 /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
525 bool test(const SmallBitVector &RHS) const {
526 if (isSmall() && RHS.isSmall())
527 return (getSmallBits() & ~RHS.getSmallBits()) != 0;
528 if (!isSmall() && !RHS.isSmall())
529 return getPointer()->test(*RHS.getPointer());
530
531 unsigned i, e;
532 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
533 if (test(i) && !RHS.test(i))
534 return true;
535
536 for (e = size(); i != e; ++i)
537 if (test(i))
538 return true;
539
540 return false;
541 }
542
543 SmallBitVector &operator|=(const SmallBitVector &RHS) {
544 resize(std::max(size(), RHS.size()));
545 if (isSmall())
546 setSmallBits(getSmallBits() | RHS.getSmallBits());
547 else if (!RHS.isSmall())
548 getPointer()->operator|=(*RHS.getPointer());
549 else {
550 SmallBitVector Copy = RHS;
551 Copy.resize(size());
552 getPointer()->operator|=(*Copy.getPointer());
553 }
554 return *this;
555 }
556
557 SmallBitVector &operator^=(const SmallBitVector &RHS) {
558 resize(std::max(size(), RHS.size()));
559 if (isSmall())
560 setSmallBits(getSmallBits() ^ RHS.getSmallBits());
561 else if (!RHS.isSmall())
562 getPointer()->operator^=(*RHS.getPointer());
563 else {
564 SmallBitVector Copy = RHS;
565 Copy.resize(size());
566 getPointer()->operator^=(*Copy.getPointer());
567 }
568 return *this;
569 }
570
571 SmallBitVector &operator<<=(unsigned N) {
572 if (isSmall())
573 setSmallBits(getSmallBits() << N);
574 else
575 getPointer()->operator<<=(N);
576 return *this;
577 }
578
579 SmallBitVector &operator>>=(unsigned N) {
580 if (isSmall())
581 setSmallBits(getSmallBits() >> N);
582 else
583 getPointer()->operator>>=(N);
584 return *this;
585 }
586
587 // Assignment operator.
588 const SmallBitVector &operator=(const SmallBitVector &RHS) {
589 if (isSmall()) {
590 if (RHS.isSmall())
591 X = RHS.X;
592 else
593 switchToLarge(new BitVector(*RHS.getPointer()));
594 } else {
595 if (!RHS.isSmall())
596 *getPointer() = *RHS.getPointer();
597 else {
598 delete getPointer();
599 X = RHS.X;
600 }
601 }
602 return *this;
603 }
604
605 const SmallBitVector &operator=(SmallBitVector &&RHS) {
606 if (this != &RHS) {
607 clear();
608 swap(RHS);
609 }
610 return *this;
611 }
612
613 void swap(SmallBitVector &RHS) {
614 std::swap(X, RHS.X);
615 }
616
617 /// Add '1' bits from Mask to this vector. Don't resize.
618 /// This computes "*this |= Mask".
619 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
620 if (isSmall())
621 applyMask<true, false>(Mask, MaskWords);
622 else
623 getPointer()->setBitsInMask(Mask, MaskWords);
624 }
625
626 /// Clear any bits in this vector that are set in Mask. Don't resize.
627 /// This computes "*this &= ~Mask".
628 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
629 if (isSmall())
630 applyMask<false, false>(Mask, MaskWords);
631 else
632 getPointer()->clearBitsInMask(Mask, MaskWords);
633 }
634
635 /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
636 /// This computes "*this |= ~Mask".
637 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
638 if (isSmall())
639 applyMask<true, true>(Mask, MaskWords);
640 else
641 getPointer()->setBitsNotInMask(Mask, MaskWords);
642 }
643
644 /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
645 /// This computes "*this &= Mask".
646 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
647 if (isSmall())
648 applyMask<false, true>(Mask, MaskWords);
649 else
650 getPointer()->clearBitsNotInMask(Mask, MaskWords);
651 }
652
653private:
654 template <bool AddBits, bool InvertMask>
655 void applyMask(const uint32_t *Mask, unsigned MaskWords) {
656 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!")(static_cast <bool> (MaskWords <= sizeof(uintptr_t) &&
"Mask is larger than base!") ? void (0) : __assert_fail ("MaskWords <= sizeof(uintptr_t) && \"Mask is larger than base!\""
, "/build/llvm-toolchain-snapshot-7~svn326246/include/llvm/ADT/SmallBitVector.h"
, 656, __extension__ __PRETTY_FUNCTION__))
;
657 uintptr_t M = Mask[0];
658 if (NumBaseBits == 64)
659 M |= uint64_t(Mask[1]) << 32;
660 if (InvertMask)
661 M = ~M;
662 if (AddBits)
663 setSmallBits(getSmallBits() | M);
664 else
665 setSmallBits(getSmallBits() & ~M);
666 }
667};
668
669inline SmallBitVector
670operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
671 SmallBitVector Result(LHS);
672 Result &= RHS;
673 return Result;
674}
675
676inline SmallBitVector
677operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
678 SmallBitVector Result(LHS);
679 Result |= RHS;
680 return Result;
681}
682
683inline SmallBitVector
684operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
685 SmallBitVector Result(LHS);
686 Result ^= RHS;
687 return Result;
688}
689
690} // end namespace llvm
691
692namespace std {
693
694/// Implement std::swap in terms of BitVector swap.
695inline void
696swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) {
697 LHS.swap(RHS);
698}
699
700} // end namespace std
701
702#endif // LLVM_ADT_SMALLBITVECTOR_H