Bug Summary

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

Annotated Source Code

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

/build/llvm-toolchain-snapshot-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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)
14
Assuming 's' is > SmallNumDataBits
15
Taking false branch
152 switchToSmall(t ? ~uintptr_t(0) : 0, s);
153 else
154 switchToLarge(new BitVector(s, t));
16
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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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-6.0~svn318693/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