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