Template.h revision b5eb3f5bf383807103dc1377a124fd96ee21d02a
15e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)//===------- SemaTemplate.h - C++ Templates ---------------------*- C++ -*-===/ 25e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// 35e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// The LLVM Compiler Infrastructure 45e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// 55e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)// License. See LICENSE.TXT for details. 75e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)//===----------------------------------------------------------------------===/ 85e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// 95e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// This file provides types used in the semantic analysis of C++ templates. 105e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)// 115e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles)//===----------------------------------------------------------------------===/ 12ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#ifndef LLVM_CLANG_SEMA_TEMPLATE_H 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#define LLVM_CLANG_SEMA_TEMPLATE_H 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 15ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "clang/AST/DeclTemplate.h" 16ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include "clang/AST/DeclVisitor.h" 173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)#include "clang/Sema/Sema.h" 18effb81e5f8246d0db0270817048dc992db66e9fbBen Murdoch#include "llvm/ADT/SmallVector.h" 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#include <cassert> 20ca12bfac764ba476d6cd062bf1dde12cc64c3f40Ben Murdoch#include <utility> 215e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles) 22f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)namespace clang { 235e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles) /// \brief Data structure that captures multiple levels of template argument 245e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles) /// lists for use in template instantiation. 255e3f23d412006dc4db4e659864679f29341e113fTorne (Richard Coles) /// 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 public: 51 /// \brief Construct an empty set of template argument lists. 52 MultiLevelTemplateArgumentList() { } 53 54 /// \brief Construct a single-level template argument list. 55 explicit 56 MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) { 57 addOuterTemplateArguments(&TemplateArgs); 58 } 59 60 /// \brief Determine the number of levels in this template argument 61 /// list. 62 unsigned getNumLevels() const { return TemplateArgumentLists.size(); } 63 64 /// \brief Retrieve the template argument at a given depth and index. 65 const TemplateArgument &operator()(unsigned Depth, unsigned Index) const { 66 assert(Depth < TemplateArgumentLists.size()); 67 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size()); 68 return TemplateArgumentLists[getNumLevels() - Depth - 1][Index]; 69 } 70 71 /// \brief Determine whether there is a non-NULL template argument at the 72 /// given depth and index. 73 /// 74 /// There must exist a template argument list at the given depth. 75 bool hasTemplateArgument(unsigned Depth, unsigned Index) const { 76 assert(Depth < TemplateArgumentLists.size()); 77 78 if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size()) 79 return false; 80 81 return !(*this)(Depth, Index).isNull(); 82 } 83 84 /// \brief Clear out a specific template argument. 85 void setArgument(unsigned Depth, unsigned Index, 86 TemplateArgument Arg) { 87 assert(Depth < TemplateArgumentLists.size()); 88 assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size()); 89 const_cast<TemplateArgument&>( 90 TemplateArgumentLists[getNumLevels() - Depth - 1][Index]) 91 = Arg; 92 } 93 94 /// \brief Add a new outermost level to the multi-level template argument 95 /// list. 96 void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) { 97 addOuterTemplateArguments(ArgList(TemplateArgs->data(), 98 TemplateArgs->size())); 99 } 100 101 /// \brief Add a new outmost level to the multi-level template argument 102 /// list. 103 void addOuterTemplateArguments(const TemplateArgument *Args, 104 unsigned NumArgs) { 105 addOuterTemplateArguments(ArgList(Args, NumArgs)); 106 } 107 108 /// \brief Add a new outmost level to the multi-level template argument 109 /// list. 110 void addOuterTemplateArguments(ArgList Args) { 111 TemplateArgumentLists.push_back(Args); 112 } 113 114 /// \brief Retrieve the innermost template argument list. 115 const ArgList &getInnermost() const { 116 return TemplateArgumentLists.front(); 117 } 118 }; 119 120 /// \brief The context in which partial ordering of function templates occurs. 121 enum TPOC { 122 /// \brief Partial ordering of function templates for a function call. 123 TPOC_Call, 124 /// \brief Partial ordering of function templates for a call to a 125 /// conversion function. 126 TPOC_Conversion, 127 /// \brief Partial ordering of function templates in other contexts, e.g., 128 /// taking the address of a function template or matching a function 129 /// template specialization to a function template. 130 TPOC_Other 131 }; 132 133 // This is lame but unavoidable in a world without forward 134 // declarations of enums. The alternatives are to either pollute 135 // Sema.h (by including this file) or sacrifice type safety (by 136 // making Sema.h declare things as enums). 137 class TemplatePartialOrderingContext { 138 TPOC Value; 139 public: 140 TemplatePartialOrderingContext(TPOC Value) : Value(Value) {} 141 operator TPOC() const { return Value; } 142 }; 143 144 /// \brief Captures a template argument whose value has been deduced 145 /// via c++ template argument deduction. 146 class DeducedTemplateArgument : public TemplateArgument { 147 /// \brief For a non-type template argument, whether the value was 148 /// deduced from an array bound. 149 bool DeducedFromArrayBound; 150 151 public: 152 DeducedTemplateArgument() 153 : TemplateArgument(), DeducedFromArrayBound(false) { } 154 155 DeducedTemplateArgument(const TemplateArgument &Arg, 156 bool DeducedFromArrayBound = false) 157 : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { } 158 159 /// \brief Construct an integral non-type template argument that 160 /// has been deduced, possibly from an array bound. 161 DeducedTemplateArgument(ASTContext &Ctx, 162 const llvm::APSInt &Value, 163 QualType ValueType, 164 bool DeducedFromArrayBound) 165 : TemplateArgument(Ctx, Value, ValueType), 166 DeducedFromArrayBound(DeducedFromArrayBound) { } 167 168 /// \brief For a non-type template argument, determine whether the 169 /// template argument was deduced from an array bound. 170 bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; } 171 172 /// \brief Specify whether the given non-type template argument 173 /// was deduced from an array bound. 174 void setDeducedFromArrayBound(bool Deduced) { 175 DeducedFromArrayBound = Deduced; 176 } 177 }; 178 179 /// \brief A stack-allocated class that identifies which local 180 /// variable declaration instantiations are present in this scope. 181 /// 182 /// A new instance of this class type will be created whenever we 183 /// instantiate a new function declaration, which will have its own 184 /// set of parameter declarations. 185 class LocalInstantiationScope { 186 public: 187 /// \brief A set of declarations. 188 typedef SmallVector<Decl *, 4> DeclArgumentPack; 189 190 private: 191 /// \brief Reference to the semantic analysis that is performing 192 /// this template instantiation. 193 Sema &SemaRef; 194 195 typedef llvm::SmallDenseMap< 196 const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4> 197 LocalDeclsMap; 198 199 /// \brief A mapping from local declarations that occur 200 /// within a template to their instantiations. 201 /// 202 /// This mapping is used during instantiation to keep track of, 203 /// e.g., function parameter and variable declarations. For example, 204 /// given: 205 /// 206 /// \code 207 /// template<typename T> T add(T x, T y) { return x + y; } 208 /// \endcode 209 /// 210 /// when we instantiate add<int>, we will introduce a mapping from 211 /// the ParmVarDecl for 'x' that occurs in the template to the 212 /// instantiated ParmVarDecl for 'x'. 213 /// 214 /// For a parameter pack, the local instantiation scope may contain a 215 /// set of instantiated parameters. This is stored as a DeclArgumentPack 216 /// pointer. 217 LocalDeclsMap LocalDecls; 218 219 /// \brief The set of argument packs we've allocated. 220 SmallVector<DeclArgumentPack *, 1> ArgumentPacks; 221 222 /// \brief The outer scope, which contains local variable 223 /// definitions from some other instantiation (that may not be 224 /// relevant to this particular scope). 225 LocalInstantiationScope *Outer; 226 227 /// \brief Whether we have already exited this scope. 228 bool Exited; 229 230 /// \brief Whether to combine this scope with the outer scope, such that 231 /// lookup will search our outer scope. 232 bool CombineWithOuterScope; 233 234 /// \brief If non-NULL, the template parameter pack that has been 235 /// partially substituted per C++0x [temp.arg.explicit]p9. 236 NamedDecl *PartiallySubstitutedPack; 237 238 /// \brief If \c PartiallySubstitutedPack is non-null, the set of 239 /// explicitly-specified template arguments in that pack. 240 const TemplateArgument *ArgsInPartiallySubstitutedPack; 241 242 /// \brief If \c PartiallySubstitutedPack, the number of 243 /// explicitly-specified template arguments in 244 /// ArgsInPartiallySubstitutedPack. 245 unsigned NumArgsInPartiallySubstitutedPack; 246 247 // This class is non-copyable 248 LocalInstantiationScope( 249 const LocalInstantiationScope &) LLVM_DELETED_FUNCTION; 250 void operator=(const LocalInstantiationScope &) LLVM_DELETED_FUNCTION; 251 252 public: 253 LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false) 254 : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope), 255 Exited(false), CombineWithOuterScope(CombineWithOuterScope), 256 PartiallySubstitutedPack(0) 257 { 258 SemaRef.CurrentInstantiationScope = this; 259 } 260 261 ~LocalInstantiationScope() { 262 Exit(); 263 } 264 265 const Sema &getSema() const { return SemaRef; } 266 267 /// \brief Exit this local instantiation scope early. 268 void Exit() { 269 if (Exited) 270 return; 271 272 for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I) 273 delete ArgumentPacks[I]; 274 275 SemaRef.CurrentInstantiationScope = Outer; 276 Exited = true; 277 } 278 279 /// \brief Clone this scope, and all outer scopes, down to the given 280 /// outermost scope. 281 LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) { 282 if (this == Outermost) return this; 283 LocalInstantiationScope *newScope = 284 new LocalInstantiationScope(SemaRef, CombineWithOuterScope); 285 286 newScope->Outer = 0; 287 if (Outer) 288 newScope->Outer = Outer->cloneScopes(Outermost); 289 290 newScope->PartiallySubstitutedPack = PartiallySubstitutedPack; 291 newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack; 292 newScope->NumArgsInPartiallySubstitutedPack = 293 NumArgsInPartiallySubstitutedPack; 294 295 for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end(); 296 I != E; ++I) { 297 const Decl *D = I->first; 298 llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = 299 newScope->LocalDecls[D]; 300 if (I->second.is<Decl *>()) { 301 Stored = I->second.get<Decl *>(); 302 } else { 303 DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>(); 304 DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack); 305 Stored = NewPack; 306 newScope->ArgumentPacks.push_back(NewPack); 307 } 308 } 309 return newScope; 310 } 311 312 /// \brief deletes the given scope, and all otuer scopes, down to the 313 /// given outermost scope. 314 static void deleteScopes(LocalInstantiationScope *Scope, 315 LocalInstantiationScope *Outermost) { 316 while (Scope && Scope != Outermost) { 317 LocalInstantiationScope *Out = Scope->Outer; 318 delete Scope; 319 Scope = Out; 320 } 321 } 322 323 /// \brief Find the instantiation of the declaration D within the current 324 /// instantiation scope. 325 /// 326 /// \param D The declaration whose instantiation we are searching for. 327 /// 328 /// \returns A pointer to the declaration or argument pack of declarations 329 /// to which the declaration \c D is instantiataed, if found. Otherwise, 330 /// returns NULL. 331 llvm::PointerUnion<Decl *, DeclArgumentPack *> * 332 findInstantiationOf(const Decl *D); 333 334 void InstantiatedLocal(const Decl *D, Decl *Inst); 335 void InstantiatedLocalPackArg(const Decl *D, Decl *Inst); 336 void MakeInstantiatedLocalArgPack(const Decl *D); 337 338 /// \brief Note that the given parameter pack has been partially substituted 339 /// via explicit specification of template arguments 340 /// (C++0x [temp.arg.explicit]p9). 341 /// 342 /// \param Pack The parameter pack, which will always be a template 343 /// parameter pack. 344 /// 345 /// \param ExplicitArgs The explicitly-specified template arguments provided 346 /// for this parameter pack. 347 /// 348 /// \param NumExplicitArgs The number of explicitly-specified template 349 /// arguments provided for this parameter pack. 350 void SetPartiallySubstitutedPack(NamedDecl *Pack, 351 const TemplateArgument *ExplicitArgs, 352 unsigned NumExplicitArgs); 353 354 /// \brief Reset the partially-substituted pack when it is no longer of 355 /// interest. 356 void ResetPartiallySubstitutedPack() { 357 assert(PartiallySubstitutedPack && "No partially-substituted pack"); 358 PartiallySubstitutedPack = 0; 359 ArgsInPartiallySubstitutedPack = 0; 360 NumArgsInPartiallySubstitutedPack = 0; 361 } 362 363 /// \brief Retrieve the partially-substitued template parameter pack. 364 /// 365 /// If there is no partially-substituted parameter pack, returns NULL. 366 NamedDecl *getPartiallySubstitutedPack( 367 const TemplateArgument **ExplicitArgs = 0, 368 unsigned *NumExplicitArgs = 0) const; 369 }; 370 371 class TemplateDeclInstantiator 372 : public DeclVisitor<TemplateDeclInstantiator, Decl *> 373 { 374 Sema &SemaRef; 375 Sema::ArgumentPackSubstitutionIndexRAII SubstIndex; 376 DeclContext *Owner; 377 const MultiLevelTemplateArgumentList &TemplateArgs; 378 Sema::LateInstantiatedAttrVec* LateAttrs; 379 LocalInstantiationScope *StartingScope; 380 381 /// \brief A list of out-of-line class template partial 382 /// specializations that will need to be instantiated after the 383 /// enclosing class's instantiation is complete. 384 SmallVector<std::pair<ClassTemplateDecl *, 385 ClassTemplatePartialSpecializationDecl *>, 4> 386 OutOfLinePartialSpecs; 387 388 public: 389 TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner, 390 const MultiLevelTemplateArgumentList &TemplateArgs) 391 : SemaRef(SemaRef), 392 SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex), 393 Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(0), StartingScope(0) 394 { } 395 396 // FIXME: Once we get closer to completion, replace these manually-written 397 // declarations with automatically-generated ones from 398 // clang/AST/DeclNodes.inc. 399 Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D); 400 Decl *VisitLabelDecl(LabelDecl *D); 401 Decl *VisitNamespaceDecl(NamespaceDecl *D); 402 Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D); 403 Decl *VisitTypedefDecl(TypedefDecl *D); 404 Decl *VisitTypeAliasDecl(TypeAliasDecl *D); 405 Decl *VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D); 406 Decl *VisitVarDecl(VarDecl *D); 407 Decl *VisitAccessSpecDecl(AccessSpecDecl *D); 408 Decl *VisitFieldDecl(FieldDecl *D); 409 Decl *VisitMSPropertyDecl(MSPropertyDecl *D); 410 Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D); 411 Decl *VisitStaticAssertDecl(StaticAssertDecl *D); 412 Decl *VisitEnumDecl(EnumDecl *D); 413 Decl *VisitEnumConstantDecl(EnumConstantDecl *D); 414 Decl *VisitFriendDecl(FriendDecl *D); 415 Decl *VisitFunctionDecl(FunctionDecl *D, 416 TemplateParameterList *TemplateParams = 0); 417 Decl *VisitCXXRecordDecl(CXXRecordDecl *D); 418 Decl *VisitCXXMethodDecl(CXXMethodDecl *D, 419 TemplateParameterList *TemplateParams = 0, 420 bool IsClassScopeSpecialization = false); 421 Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D); 422 Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D); 423 Decl *VisitCXXConversionDecl(CXXConversionDecl *D); 424 ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D); 425 Decl *VisitClassTemplateDecl(ClassTemplateDecl *D); 426 Decl *VisitClassTemplatePartialSpecializationDecl( 427 ClassTemplatePartialSpecializationDecl *D); 428 Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D); 429 Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D); 430 Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D); 431 Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D); 432 Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D); 433 Decl *VisitUsingDecl(UsingDecl *D); 434 Decl *VisitUsingShadowDecl(UsingShadowDecl *D); 435 Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D); 436 Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D); 437 Decl *VisitClassScopeFunctionSpecializationDecl( 438 ClassScopeFunctionSpecializationDecl *D); 439 Decl *VisitOMPThreadPrivateDecl(OMPThreadPrivateDecl *D); 440 441 // Base case. FIXME: Remove once we can instantiate everything. 442 Decl *VisitDecl(Decl *D) { 443 unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID( 444 DiagnosticsEngine::Error, 445 "cannot instantiate %0 yet"); 446 SemaRef.Diag(D->getLocation(), DiagID) 447 << D->getDeclKindName(); 448 449 return 0; 450 } 451 452 // Enable late instantiation of attributes. Late instantiated attributes 453 // will be stored in LA. 454 void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) { 455 LateAttrs = LA; 456 StartingScope = SemaRef.CurrentInstantiationScope; 457 } 458 459 // Disable late instantiation of attributes. 460 void disableLateAttributeInstantiation() { 461 LateAttrs = 0; 462 StartingScope = 0; 463 } 464 465 LocalInstantiationScope *getStartingScope() const { return StartingScope; } 466 467 typedef 468 SmallVectorImpl<std::pair<ClassTemplateDecl *, 469 ClassTemplatePartialSpecializationDecl *> > 470 ::iterator 471 delayed_partial_spec_iterator; 472 473 /// \brief Return an iterator to the beginning of the set of 474 /// "delayed" partial specializations, which must be passed to 475 /// InstantiateClassTemplatePartialSpecialization once the class 476 /// definition has been completed. 477 delayed_partial_spec_iterator delayed_partial_spec_begin() { 478 return OutOfLinePartialSpecs.begin(); 479 } 480 481 /// \brief Return an iterator to the end of the set of 482 /// "delayed" partial specializations, which must be passed to 483 /// InstantiateClassTemplatePartialSpecialization once the class 484 /// definition has been completed. 485 delayed_partial_spec_iterator delayed_partial_spec_end() { 486 return OutOfLinePartialSpecs.end(); 487 } 488 489 // Helper functions for instantiating methods. 490 TypeSourceInfo *SubstFunctionType(FunctionDecl *D, 491 SmallVectorImpl<ParmVarDecl *> &Params); 492 bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl); 493 bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl); 494 495 TemplateParameterList * 496 SubstTemplateParams(TemplateParameterList *List); 497 498 bool SubstQualifier(const DeclaratorDecl *OldDecl, 499 DeclaratorDecl *NewDecl); 500 bool SubstQualifier(const TagDecl *OldDecl, 501 TagDecl *NewDecl); 502 503 Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias); 504 ClassTemplatePartialSpecializationDecl * 505 InstantiateClassTemplatePartialSpecialization( 506 ClassTemplateDecl *ClassTemplate, 507 ClassTemplatePartialSpecializationDecl *PartialSpec); 508 void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern); 509 }; 510} 511 512#endif // LLVM_CLANG_SEMA_TEMPLATE_H 513