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