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