1 //===- SemaTemplate.h - C++ Templates ---------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 //===----------------------------------------------------------------------===// 7 // 8 // This file provides types used in the semantic analysis of C++ templates. 9 // 10 //===----------------------------------------------------------------------===// 11 12 #ifndef LLVM_CLANG_SEMA_TEMPLATE_H 13 #define LLVM_CLANG_SEMA_TEMPLATE_H 14 15 #include "clang/AST/DeclTemplate.h" 16 #include "clang/AST/DeclVisitor.h" 17 #include "clang/AST/TemplateBase.h" 18 #include "clang/AST/Type.h" 19 #include "clang/Basic/LLVM.h" 20 #include "clang/Sema/Sema.h" 21 #include "llvm/ADT/ArrayRef.h" 22 #include "llvm/ADT/DenseMap.h" 23 #include "llvm/ADT/PointerUnion.h" 24 #include "llvm/ADT/SmallVector.h" 25 #include <cassert> 26 #include <utility> 27 28 namespace clang { 29 30 class ASTContext; 31 class BindingDecl; 32 class CXXMethodDecl; 33 class Decl; 34 class DeclaratorDecl; 35 class DeclContext; 36 class EnumDecl; 37 class FunctionDecl; 38 class NamedDecl; 39 class ParmVarDecl; 40 class TagDecl; 41 class TypedefNameDecl; 42 class TypeSourceInfo; 43 class VarDecl; 44 45 /// Data structure that captures multiple levels of template argument 46 /// lists for use in template instantiation. 47 /// 48 /// Multiple levels of template arguments occur when instantiating the 49 /// definitions of member templates. For example: 50 /// 51 /// \code 52 /// template<typename T> 53 /// struct X { 54 /// template<T Value> 55 /// struct Y { 56 /// void f(); 57 /// }; 58 /// }; 59 /// \endcode 60 /// 61 /// When instantiating X<int>::Y<17>::f, the multi-level template argument 62 /// list will contain a template argument list (int) at depth 0 and a 63 /// template argument list (17) at depth 1. 64 class MultiLevelTemplateArgumentList { 65 /// The template argument list at a certain template depth 66 using ArgList = ArrayRef<TemplateArgument>; 67 68 /// The template argument lists, stored from the innermost template 69 /// argument list (first) to the outermost template argument list (last). 70 SmallVector<ArgList, 4> TemplateArgumentLists; 71 72 /// The number of outer levels of template arguments that are not 73 /// being substituted. 74 unsigned NumRetainedOuterLevels = 0; 75 76 public: 77 /// Construct an empty set of template argument lists. 78 MultiLevelTemplateArgumentList() = default; 79 80 /// Construct a single-level template argument list. 81 explicit 82 MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) { 83 addOuterTemplateArguments(&TemplateArgs); 84 } 85 86 /// Determine the number of levels in this template argument 87 /// list. 88 unsigned getNumLevels() const { 89 return TemplateArgumentLists.size() + NumRetainedOuterLevels; 90 } 91 92 /// Determine the number of substituted levels in this template 93 /// argument list. 94 unsigned getNumSubstitutedLevels() const { 95 return TemplateArgumentLists.size(); 96 } 97 98 /// Determine how many of the \p OldDepth outermost template parameter 99 /// lists would be removed by substituting these arguments. 100 unsigned getNewDepth(unsigned OldDepth) const { 101 if (OldDepth < NumRetainedOuterLevels) 102 return OldDepth; 103 if (OldDepth < getNumLevels()) 104 return NumRetainedOuterLevels; 105 return OldDepth - TemplateArgumentLists.size(); 106 } 107 108 /// Retrieve the template argument at a given depth and index. 109 const TemplateArgument &operator()(unsigned Depth, unsigned Index) const { 110 assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels()); 111 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size()); 112 return TemplateArgumentLists[getNumLevels() - Depth - 1][Index]; 113 } 114 115 /// Determine whether there is a non-NULL template argument at the 116 /// given depth and index. 117 /// 118 /// There must exist a template argument list at the given depth. 119 bool hasTemplateArgument(unsigned Depth, unsigned Index) const { 120 assert(Depth < getNumLevels()); 121 122 if (Depth < NumRetainedOuterLevels) 123 return false; 124 125 if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size()) 126 return false; 127 128 return !(*this)(Depth, Index).isNull(); 129 } 130 131 /// Clear out a specific template argument. 132 void setArgument(unsigned Depth, unsigned Index, 133 TemplateArgument Arg) { 134 assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels()); 135 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size()); 136 const_cast<TemplateArgument&>( 137 TemplateArgumentLists[getNumLevels() - Depth - 1][Index]) 138 = Arg; 139 } 140 141 /// Add a new outermost level to the multi-level template argument 142 /// list. 143 void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) { 144 addOuterTemplateArguments(ArgList(TemplateArgs->data(), 145 TemplateArgs->size())); 146 } 147 148 /// Add a new outmost level to the multi-level template argument 149 /// list. 150 void addOuterTemplateArguments(ArgList Args) { 151 assert(!NumRetainedOuterLevels && 152 "substituted args outside retained args?"); 153 TemplateArgumentLists.push_back(Args); 154 } 155 156 /// Add an outermost level that we are not substituting. We have no 157 /// arguments at this level, and do not remove it from the depth of inner 158 /// template parameters that we instantiate. 159 void addOuterRetainedLevel() { 160 ++NumRetainedOuterLevels; 161 } 162 163 /// Retrieve the innermost template argument list. 164 const ArgList &getInnermost() const { 165 return TemplateArgumentLists.front(); 166 } 167 }; 168 169 /// The context in which partial ordering of function templates occurs. 170 enum TPOC { 171 /// Partial ordering of function templates for a function call. 172 TPOC_Call, 173 174 /// Partial ordering of function templates for a call to a 175 /// conversion function. 176 TPOC_Conversion, 177 178 /// Partial ordering of function templates in other contexts, e.g., 179 /// taking the address of a function template or matching a function 180 /// template specialization to a function template. 181 TPOC_Other 182 }; 183 184 // This is lame but unavoidable in a world without forward 185 // declarations of enums. The alternatives are to either pollute 186 // Sema.h (by including this file) or sacrifice type safety (by 187 // making Sema.h declare things as enums). 188 class TemplatePartialOrderingContext { 189 TPOC Value; 190 191 public: 192 TemplatePartialOrderingContext(TPOC Value) : Value(Value) {} 193 194 operator TPOC() const { return Value; } 195 }; 196 197 /// Captures a template argument whose value has been deduced 198 /// via c++ template argument deduction. 199 class DeducedTemplateArgument : public TemplateArgument { 200 /// For a non-type template argument, whether the value was 201 /// deduced from an array bound. 202 bool DeducedFromArrayBound = false; 203 204 public: 205 DeducedTemplateArgument() = default; 206 207 DeducedTemplateArgument(const TemplateArgument &Arg, 208 bool DeducedFromArrayBound = false) 209 : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) {} 210 211 /// Construct an integral non-type template argument that 212 /// has been deduced, possibly from an array bound. 213 DeducedTemplateArgument(ASTContext &Ctx, 214 const llvm::APSInt &Value, 215 QualType ValueType, 216 bool DeducedFromArrayBound) 217 : TemplateArgument(Ctx, Value, ValueType), 218 DeducedFromArrayBound(DeducedFromArrayBound) {} 219 220 /// For a non-type template argument, determine whether the 221 /// template argument was deduced from an array bound. 222 bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; } 223 224 /// Specify whether the given non-type template argument 225 /// was deduced from an array bound. 226 void setDeducedFromArrayBound(bool Deduced) { 227 DeducedFromArrayBound = Deduced; 228 } 229 }; 230 231 /// A stack-allocated class that identifies which local 232 /// variable declaration instantiations are present in this scope. 233 /// 234 /// A new instance of this class type will be created whenever we 235 /// instantiate a new function declaration, which will have its own 236 /// set of parameter declarations. 237 class LocalInstantiationScope { 238 public: 239 /// A set of declarations. 240 using DeclArgumentPack = SmallVector<VarDecl *, 4>; 241 242 private: 243 /// Reference to the semantic analysis that is performing 244 /// this template instantiation. 245 Sema &SemaRef; 246 247 using LocalDeclsMap = 248 llvm::SmallDenseMap<const Decl *, 249 llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>; 250 251 /// A mapping from local declarations that occur 252 /// within a template to their instantiations. 253 /// 254 /// This mapping is used during instantiation to keep track of, 255 /// e.g., function parameter and variable declarations. For example, 256 /// given: 257 /// 258 /// \code 259 /// template<typename T> T add(T x, T y) { return x + y; } 260 /// \endcode 261 /// 262 /// when we instantiate add<int>, we will introduce a mapping from 263 /// the ParmVarDecl for 'x' that occurs in the template to the 264 /// instantiated ParmVarDecl for 'x'. 265 /// 266 /// For a parameter pack, the local instantiation scope may contain a 267 /// set of instantiated parameters. This is stored as a DeclArgumentPack 268 /// pointer. 269 LocalDeclsMap LocalDecls; 270 271 /// The set of argument packs we've allocated. 272 SmallVector<DeclArgumentPack *, 1> ArgumentPacks; 273 274 /// The outer scope, which contains local variable 275 /// definitions from some other instantiation (that may not be 276 /// relevant to this particular scope). 277 LocalInstantiationScope *Outer; 278 279 /// Whether we have already exited this scope. 280 bool Exited = false; 281 282 /// Whether to combine this scope with the outer scope, such that 283 /// lookup will search our outer scope. 284 bool CombineWithOuterScope; 285 286 /// If non-NULL, the template parameter pack that has been 287 /// partially substituted per C++0x [temp.arg.explicit]p9. 288 NamedDecl *PartiallySubstitutedPack = nullptr; 289 290 /// If \c PartiallySubstitutedPack is non-null, the set of 291 /// explicitly-specified template arguments in that pack. 292 const TemplateArgument *ArgsInPartiallySubstitutedPack; 293 294 /// If \c PartiallySubstitutedPack, the number of 295 /// explicitly-specified template arguments in 296 /// ArgsInPartiallySubstitutedPack. 297 unsigned NumArgsInPartiallySubstitutedPack; 298 299 public: 300 LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false) 301 : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope), 302 CombineWithOuterScope(CombineWithOuterScope) { 303 SemaRef.CurrentInstantiationScope = this; 304 } 305 306 LocalInstantiationScope(const LocalInstantiationScope &) = delete; 307 LocalInstantiationScope & 308 operator=(const LocalInstantiationScope &) = delete; 309 310 ~LocalInstantiationScope() { 311 Exit(); 312 } 313 314 const Sema &getSema() const { return SemaRef; } 315 316 /// Exit this local instantiation scope early. 317 void Exit() { 318 if (Exited) 319 return; 320 321 for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I) 322 delete ArgumentPacks[I]; 323 324 SemaRef.CurrentInstantiationScope = Outer; 325 Exited = true; 326 } 327 328 /// Clone this scope, and all outer scopes, down to the given 329 /// outermost scope. 330 LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) { 331 if (this == Outermost) return this; 332 333 // Save the current scope from SemaRef since the LocalInstantiationScope 334 // will overwrite it on construction 335 LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope; 336 337 LocalInstantiationScope *newScope = 338 new LocalInstantiationScope(SemaRef, CombineWithOuterScope); 339 340 newScope->Outer = nullptr; 341 if (Outer) 342 newScope->Outer = Outer->cloneScopes(Outermost); 343 344 newScope->PartiallySubstitutedPack = PartiallySubstitutedPack; 345 newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack; 346 newScope->NumArgsInPartiallySubstitutedPack = 347 NumArgsInPartiallySubstitutedPack; 348 349 for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end(); 350 I != E; ++I) { 351 const Decl *D = I->first; 352 llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = 353 newScope->LocalDecls[D]; 354 if (I->second.is<Decl *>()) { 355 Stored = I->second.get<Decl *>(); 356 } else { 357 DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>(); 358 DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack); 359 Stored = NewPack; 360 newScope->ArgumentPacks.push_back(NewPack); 361 } 362 } 363 // Restore the saved scope to SemaRef 364 SemaRef.CurrentInstantiationScope = oldScope; 365 return newScope; 366 } 367 368 /// deletes the given scope, and all otuer scopes, down to the 369 /// given outermost scope. 370 static void deleteScopes(LocalInstantiationScope *Scope, 371 LocalInstantiationScope *Outermost) { 372 while (Scope && Scope != Outermost) { 373 LocalInstantiationScope *Out = Scope->Outer; 374 delete Scope; 375 Scope = Out; 376 } 377 } 378 379 /// Find the instantiation of the declaration D within the current 380 /// instantiation scope. 381 /// 382 /// \param D The declaration whose instantiation we are searching for. 383 /// 384 /// \returns A pointer to the declaration or argument pack of declarations 385 /// to which the declaration \c D is instantiated, if found. Otherwise, 386 /// returns NULL. 387 llvm::PointerUnion<Decl *, DeclArgumentPack *> * 388 findInstantiationOf(const Decl *D); 389 390 void InstantiatedLocal(const Decl *D, Decl *Inst); 391 void InstantiatedLocalPackArg(const Decl *D, VarDecl *Inst); 392 void MakeInstantiatedLocalArgPack(const Decl *D); 393 394 /// Note that the given parameter pack has been partially substituted 395 /// via explicit specification of template arguments 396 /// (C++0x [temp.arg.explicit]p9). 397 /// 398 /// \param Pack The parameter pack, which will always be a template 399 /// parameter pack. 400 /// 401 /// \param ExplicitArgs The explicitly-specified template arguments provided 402 /// for this parameter pack. 403 /// 404 /// \param NumExplicitArgs The number of explicitly-specified template 405 /// arguments provided for this parameter pack. 406 void SetPartiallySubstitutedPack(NamedDecl *Pack, 407 const TemplateArgument *ExplicitArgs, 408 unsigned NumExplicitArgs); 409 410 /// Reset the partially-substituted pack when it is no longer of 411 /// interest. 412 void ResetPartiallySubstitutedPack() { 413 assert(PartiallySubstitutedPack && "No partially-substituted pack"); 414 PartiallySubstitutedPack = nullptr; 415 ArgsInPartiallySubstitutedPack = nullptr; 416 NumArgsInPartiallySubstitutedPack = 0; 417 } 418 419 /// Retrieve the partially-substitued template parameter pack. 420 /// 421 /// If there is no partially-substituted parameter pack, returns NULL. 422 NamedDecl * 423 getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr, 424 unsigned *NumExplicitArgs = nullptr) const; 425 }; 426 427 class TemplateDeclInstantiator 428 : public DeclVisitor<TemplateDeclInstantiator, Decl *> 429 { 430 Sema &SemaRef; 431 Sema::ArgumentPackSubstitutionIndexRAII SubstIndex; 432 DeclContext *Owner; 433 const MultiLevelTemplateArgumentList &TemplateArgs; 434 Sema::LateInstantiatedAttrVec* LateAttrs = nullptr; 435 LocalInstantiationScope *StartingScope = nullptr; 436 437 /// A list of out-of-line class template partial 438 /// specializations that will need to be instantiated after the 439 /// enclosing class's instantiation is complete. 440 SmallVector<std::pair<ClassTemplateDecl *, 441 ClassTemplatePartialSpecializationDecl *>, 4> 442 OutOfLinePartialSpecs; 443 444 /// A list of out-of-line variable template partial 445 /// specializations that will need to be instantiated after the 446 /// enclosing variable's instantiation is complete. 447 /// FIXME: Verify that this is needed. 448 SmallVector< 449 std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4> 450 OutOfLineVarPartialSpecs; 451 452 public: 453 TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner, 454 const MultiLevelTemplateArgumentList &TemplateArgs) 455 : SemaRef(SemaRef), 456 SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex), 457 Owner(Owner), TemplateArgs(TemplateArgs) {} 458 459 // Define all the decl visitors using DeclNodes.inc 460 #define DECL(DERIVED, BASE) \ 461 Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D); 462 #define ABSTRACT_DECL(DECL) 463 464 // Decls which never appear inside a class or function. 465 #define OBJCCONTAINER(DERIVED, BASE) 466 #define FILESCOPEASM(DERIVED, BASE) 467 #define IMPORT(DERIVED, BASE) 468 #define EXPORT(DERIVED, BASE) 469 #define LINKAGESPEC(DERIVED, BASE) 470 #define OBJCCOMPATIBLEALIAS(DERIVED, BASE) 471 #define OBJCMETHOD(DERIVED, BASE) 472 #define OBJCTYPEPARAM(DERIVED, BASE) 473 #define OBJCIVAR(DERIVED, BASE) 474 #define OBJCPROPERTY(DERIVED, BASE) 475 #define OBJCPROPERTYIMPL(DERIVED, BASE) 476 #define EMPTY(DERIVED, BASE) 477 #define LIFETIMEEXTENDEDTEMPORARY(DERIVED, BASE) 478 479 // Decls which use special-case instantiation code. 480 #define BLOCK(DERIVED, BASE) 481 #define CAPTURED(DERIVED, BASE) 482 #define IMPLICITPARAM(DERIVED, BASE) 483 484 #include "clang/AST/DeclNodes.inc" 485 486 enum class RewriteKind { None, RewriteSpaceshipAsEqualEqual }; 487 488 void adjustForRewrite(RewriteKind RK, FunctionDecl *Orig, QualType &T, 489 TypeSourceInfo *&TInfo, 490 DeclarationNameInfo &NameInfo); 491 492 // A few supplemental visitor functions. 493 Decl *VisitCXXMethodDecl(CXXMethodDecl *D, 494 TemplateParameterList *TemplateParams, 495 Optional<const ASTTemplateArgumentListInfo *> 496 ClassScopeSpecializationArgs = llvm::None, 497 RewriteKind RK = RewriteKind::None); 498 Decl *VisitFunctionDecl(FunctionDecl *D, 499 TemplateParameterList *TemplateParams, 500 RewriteKind RK = RewriteKind::None); 501 Decl *VisitDecl(Decl *D); 502 Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate, 503 ArrayRef<BindingDecl *> *Bindings = nullptr); 504 505 // Enable late instantiation of attributes. Late instantiated attributes 506 // will be stored in LA. 507 void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) { 508 LateAttrs = LA; 509 StartingScope = SemaRef.CurrentInstantiationScope; 510 } 511 512 // Disable late instantiation of attributes. 513 void disableLateAttributeInstantiation() { 514 LateAttrs = nullptr; 515 StartingScope = nullptr; 516 } 517 518 LocalInstantiationScope *getStartingScope() const { return StartingScope; } 519 520 using delayed_partial_spec_iterator = SmallVectorImpl<std::pair< 521 ClassTemplateDecl *, ClassTemplatePartialSpecializationDecl *>>::iterator; 522 523 using delayed_var_partial_spec_iterator = SmallVectorImpl<std::pair< 524 VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>>::iterator; 525 526 /// Return an iterator to the beginning of the set of 527 /// "delayed" partial specializations, which must be passed to 528 /// InstantiateClassTemplatePartialSpecialization once the class 529 /// definition has been completed. 530 delayed_partial_spec_iterator delayed_partial_spec_begin() { 531 return OutOfLinePartialSpecs.begin(); 532 } 533 534 delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() { 535 return OutOfLineVarPartialSpecs.begin(); 536 } 537 538 /// Return an iterator to the end of the set of 539 /// "delayed" partial specializations, which must be passed to 540 /// InstantiateClassTemplatePartialSpecialization once the class 541 /// definition has been completed. 542 delayed_partial_spec_iterator delayed_partial_spec_end() { 543 return OutOfLinePartialSpecs.end(); 544 } 545 546 delayed_var_partial_spec_iterator delayed_var_partial_spec_end() { 547 return OutOfLineVarPartialSpecs.end(); 548 } 549 550 // Helper functions for instantiating methods. 551 TypeSourceInfo *SubstFunctionType(FunctionDecl *D, 552 SmallVectorImpl<ParmVarDecl *> &Params); 553 bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl); 554 bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl); 555 556 bool SubstDefaultedFunction(FunctionDecl *New, FunctionDecl *Tmpl); 557 558 TemplateParameterList * 559 SubstTemplateParams(TemplateParameterList *List); 560 561 bool SubstQualifier(const DeclaratorDecl *OldDecl, 562 DeclaratorDecl *NewDecl); 563 bool SubstQualifier(const TagDecl *OldDecl, 564 TagDecl *NewDecl); 565 566 Decl *VisitVarTemplateSpecializationDecl( 567 VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos, 568 const TemplateArgumentListInfo &TemplateArgsInfo, 569 ArrayRef<TemplateArgument> Converted, 570 VarTemplateSpecializationDecl *PrevDecl = nullptr); 571 572 Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias); 573 ClassTemplatePartialSpecializationDecl * 574 InstantiateClassTemplatePartialSpecialization( 575 ClassTemplateDecl *ClassTemplate, 576 ClassTemplatePartialSpecializationDecl *PartialSpec); 577 VarTemplatePartialSpecializationDecl * 578 InstantiateVarTemplatePartialSpecialization( 579 VarTemplateDecl *VarTemplate, 580 VarTemplatePartialSpecializationDecl *PartialSpec); 581 void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern); 582 583 private: 584 template<typename T> 585 Decl *instantiateUnresolvedUsingDecl(T *D, 586 bool InstantiatingPackElement = false); 587 }; 588 589 } // namespace clang 590 591 #endif // LLVM_CLANG_SEMA_TEMPLATE_H 592