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