DeclBase.cpp revision bd6c80037626a37ce3936a36d9ae287f475845b7
1//===--- DeclBase.cpp - Declaration AST Node Implementation ---------------===// 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// 10// This file implements the Decl and DeclContext classes. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/AST/DeclBase.h" 15#include "clang/AST/Decl.h" 16#include "clang/AST/DeclCXX.h" 17#include "clang/AST/DeclObjC.h" 18#include "clang/AST/DeclTemplate.h" 19#include "clang/AST/ASTContext.h" 20#include "clang/AST/Type.h" 21#include "llvm/ADT/DenseMap.h" 22#include <algorithm> 23#include <functional> 24#include <vector> 25using namespace clang; 26 27//===----------------------------------------------------------------------===// 28// Statistics 29//===----------------------------------------------------------------------===// 30 31#define DECL(Derived, Base) static int n##Derived##s = 0; 32#include "clang/AST/DeclNodes.def" 33 34static bool StatSwitch = false; 35 36// This keeps track of all decl attributes. Since so few decls have attrs, we 37// keep them in a hash map instead of wasting space in the Decl class. 38typedef llvm::DenseMap<const Decl*, Attr*> DeclAttrMapTy; 39 40static DeclAttrMapTy *DeclAttrs = 0; 41 42const char *Decl::getDeclKindName() const { 43 switch (DeclKind) { 44 default: assert(0 && "Declaration not in DeclNodes.def!"); 45#define DECL(Derived, Base) case Derived: return #Derived; 46#include "clang/AST/DeclNodes.def" 47 } 48} 49 50const char *DeclContext::getDeclKindName() const { 51 switch (DeclKind) { 52 default: assert(0 && "Declaration context not in DeclNodes.def!"); 53#define DECL(Derived, Base) case Decl::Derived: return #Derived; 54#include "clang/AST/DeclNodes.def" 55 } 56} 57 58bool Decl::CollectingStats(bool Enable) { 59 if (Enable) 60 StatSwitch = true; 61 return StatSwitch; 62} 63 64void Decl::PrintStats() { 65 fprintf(stderr, "*** Decl Stats:\n"); 66 67 int totalDecls = 0; 68#define DECL(Derived, Base) totalDecls += n##Derived##s; 69#include "clang/AST/DeclNodes.def" 70 fprintf(stderr, " %d decls total.\n", totalDecls); 71 72 int totalBytes = 0; 73#define DECL(Derived, Base) \ 74 if (n##Derived##s > 0) { \ 75 totalBytes += (int)(n##Derived##s * sizeof(Derived##Decl)); \ 76 fprintf(stderr, " %d " #Derived " decls, %d each (%d bytes)\n", \ 77 n##Derived##s, (int)sizeof(Derived##Decl), \ 78 (int)(n##Derived##s * sizeof(Derived##Decl))); \ 79 } 80#include "clang/AST/DeclNodes.def" 81 82 fprintf(stderr, "Total bytes = %d\n", totalBytes); 83} 84 85void Decl::addDeclKind(Kind k) { 86 switch (k) { 87 default: assert(0 && "Declaration not in DeclNodes.def!"); 88#define DECL(Derived, Base) case Derived: ++n##Derived##s; break; 89#include "clang/AST/DeclNodes.def" 90 } 91} 92 93//===----------------------------------------------------------------------===// 94// Decl Implementation 95//===----------------------------------------------------------------------===// 96 97void Decl::setDeclContext(DeclContext *DC) { 98 if (isOutOfSemaDC()) 99 delete getMultipleDC(); 100 101 DeclCtx = reinterpret_cast<uintptr_t>(DC); 102} 103 104void Decl::setLexicalDeclContext(DeclContext *DC) { 105 if (DC == getLexicalDeclContext()) 106 return; 107 108 if (isInSemaDC()) { 109 MultipleDC *MDC = new MultipleDC(); 110 MDC->SemanticDC = getDeclContext(); 111 MDC->LexicalDC = DC; 112 DeclCtx = reinterpret_cast<uintptr_t>(MDC) | 0x1; 113 } else { 114 getMultipleDC()->LexicalDC = DC; 115 } 116} 117 118// Out-of-line virtual method providing a home for Decl. 119Decl::~Decl() { 120 if (isOutOfSemaDC()) 121 delete getMultipleDC(); 122 123 if (!HasAttrs) 124 return; 125 126 DeclAttrMapTy::iterator it = DeclAttrs->find(this); 127 assert(it != DeclAttrs->end() && "No attrs found but HasAttrs is true!"); 128 129 // release attributes. 130 delete it->second; 131 invalidateAttrs(); 132} 133 134void Decl::addAttr(Attr *NewAttr) { 135 if (!DeclAttrs) 136 DeclAttrs = new DeclAttrMapTy(); 137 138 Attr *&ExistingAttr = (*DeclAttrs)[this]; 139 140 NewAttr->setNext(ExistingAttr); 141 ExistingAttr = NewAttr; 142 143 HasAttrs = true; 144} 145 146void Decl::invalidateAttrs() { 147 if (!HasAttrs) return; 148 149 HasAttrs = false; 150 (*DeclAttrs)[this] = 0; 151 DeclAttrs->erase(this); 152 153 if (DeclAttrs->empty()) { 154 delete DeclAttrs; 155 DeclAttrs = 0; 156 } 157} 158 159const Attr *Decl::getAttrs() const { 160 if (!HasAttrs) 161 return 0; 162 163 return (*DeclAttrs)[this]; 164} 165 166void Decl::swapAttrs(Decl *RHS) { 167 bool HasLHSAttr = this->HasAttrs; 168 bool HasRHSAttr = RHS->HasAttrs; 169 170 // Usually, neither decl has attrs, nothing to do. 171 if (!HasLHSAttr && !HasRHSAttr) return; 172 173 // If 'this' has no attrs, swap the other way. 174 if (!HasLHSAttr) 175 return RHS->swapAttrs(this); 176 177 // Handle the case when both decls have attrs. 178 if (HasRHSAttr) { 179 std::swap((*DeclAttrs)[this], (*DeclAttrs)[RHS]); 180 return; 181 } 182 183 // Otherwise, LHS has an attr and RHS doesn't. 184 (*DeclAttrs)[RHS] = (*DeclAttrs)[this]; 185 (*DeclAttrs).erase(this); 186 this->HasAttrs = false; 187 RHS->HasAttrs = true; 188} 189 190 191void Decl::Destroy(ASTContext& C) { 192#if 0 193 // FIXME: Once ownership is fully understood, we can enable this code 194 if (DeclContext *DC = dyn_cast<DeclContext>(this)) 195 DC->decls_begin()->Destroy(C); 196 197 // Observe the unrolled recursion. By setting N->NextDeclInScope = 0x0 198 // within the loop, only the Destroy method for the first Decl 199 // will deallocate all of the Decls in a chain. 200 201 Decl* N = NextDeclInScope; 202 203 while (N) { 204 Decl* Tmp = N->NextDeclInScope; 205 N->NextDeclInScope = 0; 206 N->Destroy(C); 207 N = Tmp; 208 } 209 210 this->~Decl(); 211 C.Deallocate((void *)this); 212#endif 213} 214 215Decl *Decl::castFromDeclContext (const DeclContext *D) { 216 Decl::Kind DK = D->getDeclKind(); 217 switch(DK) { 218#define DECL_CONTEXT(Name) \ 219 case Decl::Name: \ 220 return static_cast<Name##Decl*>(const_cast<DeclContext*>(D)); 221#define DECL_CONTEXT_BASE(Name) 222#include "clang/AST/DeclNodes.def" 223 default: 224#define DECL_CONTEXT_BASE(Name) \ 225 if (DK >= Decl::Name##First && DK <= Decl::Name##Last) \ 226 return static_cast<Name##Decl*>(const_cast<DeclContext*>(D)); 227#include "clang/AST/DeclNodes.def" 228 assert(false && "a decl that inherits DeclContext isn't handled"); 229 return 0; 230 } 231} 232 233DeclContext *Decl::castToDeclContext(const Decl *D) { 234 Decl::Kind DK = D->getKind(); 235 switch(DK) { 236#define DECL_CONTEXT(Name) \ 237 case Decl::Name: \ 238 return static_cast<Name##Decl*>(const_cast<Decl*>(D)); 239#define DECL_CONTEXT_BASE(Name) 240#include "clang/AST/DeclNodes.def" 241 default: 242#define DECL_CONTEXT_BASE(Name) \ 243 if (DK >= Decl::Name##First && DK <= Decl::Name##Last) \ 244 return static_cast<Name##Decl*>(const_cast<Decl*>(D)); 245#include "clang/AST/DeclNodes.def" 246 assert(false && "a decl that inherits DeclContext isn't handled"); 247 return 0; 248 } 249} 250 251//===----------------------------------------------------------------------===// 252// DeclContext Implementation 253//===----------------------------------------------------------------------===// 254 255bool DeclContext::classof(const Decl *D) { 256 switch (D->getKind()) { 257#define DECL_CONTEXT(Name) case Decl::Name: 258#define DECL_CONTEXT_BASE(Name) 259#include "clang/AST/DeclNodes.def" 260 return true; 261 default: 262#define DECL_CONTEXT_BASE(Name) \ 263 if (D->getKind() >= Decl::Name##First && \ 264 D->getKind() <= Decl::Name##Last) \ 265 return true; 266#include "clang/AST/DeclNodes.def" 267 return false; 268 } 269} 270 271// FIXME: We really want to use a DenseSet here to eliminate the 272// redundant storage of the declaration names, but (1) it doesn't give 273// us the ability to search based on DeclarationName, (2) we really 274// need something more like a DenseMultiSet, and (3) it's 275// implemented in terms of DenseMap anyway. However, this data 276// structure is really space-inefficient, so we'll have to do 277// something. 278typedef llvm::DenseMap<DeclarationName, std::vector<NamedDecl*> > 279 StoredDeclsMap; 280 281DeclContext::~DeclContext() { 282 unsigned Size = LookupPtr.getInt(); 283 if (Size == LookupIsMap) { 284 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 285 delete Map; 286 } else { 287 NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer()); 288 delete [] Array; 289 } 290} 291 292void DeclContext::DestroyDecls(ASTContext &C) { 293 for (decl_iterator D = decls_begin(); D != decls_end(); ) 294 (*D++)->Destroy(C); 295} 296 297bool DeclContext::isTransparentContext() const { 298 if (DeclKind == Decl::Enum) 299 return true; // FIXME: Check for C++0x scoped enums 300 else if (DeclKind == Decl::LinkageSpec) 301 return true; 302 else if (DeclKind == Decl::Record || DeclKind == Decl::CXXRecord) 303 return cast<RecordDecl>(this)->isAnonymousStructOrUnion(); 304 else if (DeclKind == Decl::Namespace) 305 return false; // FIXME: Check for C++0x inline namespaces 306 307 return false; 308} 309 310DeclContext *DeclContext::getPrimaryContext() { 311 switch (DeclKind) { 312 case Decl::TranslationUnit: 313 case Decl::LinkageSpec: 314 case Decl::Block: 315 // There is only one DeclContext for these entities. 316 return this; 317 318 case Decl::Namespace: 319 // The original namespace is our primary context. 320 return static_cast<NamespaceDecl*>(this)->getOriginalNamespace(); 321 322 case Decl::ObjCMethod: 323 return this; 324 325 case Decl::ObjCInterface: 326 case Decl::ObjCProtocol: 327 case Decl::ObjCCategory: 328 // FIXME: Can Objective-C interfaces be forward-declared? 329 return this; 330 331 case Decl::ObjCImplementation: 332 case Decl::ObjCCategoryImpl: 333 return this; 334 335 default: 336 if (DeclKind >= Decl::TagFirst && DeclKind <= Decl::TagLast) { 337 // If this is a tag type that has a definition or is currently 338 // being defined, that definition is our primary context. 339 if (TagType *TagT 340 = cast_or_null<TagType>(cast<TagDecl>(this)->TypeForDecl)) 341 if (TagT->isBeingDefined() || 342 (TagT->getDecl() && TagT->getDecl()->isDefinition())) 343 return TagT->getDecl(); 344 return this; 345 } 346 347 assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast && 348 "Unknown DeclContext kind"); 349 return this; 350 } 351} 352 353DeclContext *DeclContext::getNextContext() { 354 switch (DeclKind) { 355 case Decl::Namespace: 356 // Return the next namespace 357 return static_cast<NamespaceDecl*>(this)->getNextNamespace(); 358 359 default: 360 return 0; 361 } 362} 363 364void DeclContext::addDecl(Decl *D) { 365 assert(D->getLexicalDeclContext() == this && "Decl inserted into wrong lexical context"); 366 assert(!D->NextDeclInScope && D != LastDecl && 367 "Decl already inserted into a DeclContext"); 368 369 if (FirstDecl) { 370 LastDecl->NextDeclInScope = D; 371 LastDecl = D; 372 } else { 373 FirstDecl = LastDecl = D; 374 } 375 376 if (NamedDecl *ND = dyn_cast<NamedDecl>(D)) 377 ND->getDeclContext()->makeDeclVisibleInContext(ND); 378} 379 380/// buildLookup - Build the lookup data structure with all of the 381/// declarations in DCtx (and any other contexts linked to it or 382/// transparent contexts nested within it). 383void DeclContext::buildLookup(DeclContext *DCtx) { 384 for (; DCtx; DCtx = DCtx->getNextContext()) { 385 for (decl_iterator D = DCtx->decls_begin(), DEnd = DCtx->decls_end(); 386 D != DEnd; ++D) { 387 // Insert this declaration into the lookup structure 388 if (NamedDecl *ND = dyn_cast<NamedDecl>(*D)) 389 makeDeclVisibleInContextImpl(ND); 390 391 // If this declaration is itself a transparent declaration context, 392 // add its members (recursively). 393 if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D)) 394 if (InnerCtx->isTransparentContext()) 395 buildLookup(InnerCtx->getPrimaryContext()); 396 } 397 } 398} 399 400DeclContext::lookup_result 401DeclContext::lookup(DeclarationName Name) { 402 DeclContext *PrimaryContext = getPrimaryContext(); 403 if (PrimaryContext != this) 404 return PrimaryContext->lookup(Name); 405 406 /// If there is no lookup data structure, build one now by walking 407 /// all of the linked DeclContexts (in declaration order!) and 408 /// inserting their values. 409 if (LookupPtr.getPointer() == 0) 410 buildLookup(this); 411 412 if (isLookupMap()) { 413 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 414 StoredDeclsMap::iterator Pos = Map->find(Name); 415 if (Pos != Map->end()) 416 return lookup_result(&Pos->second.front(), 417 &Pos->second.front() + Pos->second.size()); 418 return lookup_result(0, 0); 419 } 420 421 // We have a small array. Look into it. 422 unsigned Size = LookupPtr.getInt(); 423 NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer()); 424 for (unsigned Idx = 0; Idx != Size; ++Idx) 425 if (Array[Idx]->getDeclName() == Name) { 426 unsigned Last = Idx + 1; 427 while (Last != Size && Array[Last]->getDeclName() == Name) 428 ++Last; 429 return lookup_result(&Array[Idx], &Array[Last]); 430 } 431 432 return lookup_result(0, 0); 433} 434 435DeclContext::lookup_const_result 436DeclContext::lookup(DeclarationName Name) const { 437 return const_cast<DeclContext*>(this)->lookup(Name); 438} 439 440const DeclContext *DeclContext::getLookupContext() const { 441 const DeclContext *Ctx = this; 442 // Skip through transparent contexts. 443 while (Ctx->isTransparentContext()) 444 Ctx = Ctx->getParent(); 445 return Ctx; 446} 447 448void DeclContext::makeDeclVisibleInContext(NamedDecl *D) { 449 // FIXME: This feels like a hack. Should DeclarationName support 450 // template-ids, or is there a better way to keep specializations 451 // from being visible? 452 if (isa<ClassTemplateSpecializationDecl>(D)) 453 return; 454 455 DeclContext *PrimaryContext = getPrimaryContext(); 456 if (PrimaryContext != this) { 457 PrimaryContext->makeDeclVisibleInContext(D); 458 return; 459 } 460 461 // If we already have a lookup data structure, perform the insertion 462 // into it. Otherwise, be lazy and don't build that structure until 463 // someone asks for it. 464 if (LookupPtr.getPointer()) 465 makeDeclVisibleInContextImpl(D); 466 467 // If we are a transparent context, insert into our parent context, 468 // too. This operation is recursive. 469 if (isTransparentContext()) 470 getParent()->makeDeclVisibleInContext(D); 471} 472 473void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) { 474 // Skip unnamed declarations. 475 if (!D->getDeclName()) 476 return; 477 478 // FIXME: This feels like a hack. Should DeclarationName support 479 // template-ids, or is there a better way to keep specializations 480 // from being visible? 481 if (isa<ClassTemplateSpecializationDecl>(D)) 482 return; 483 484 bool MayBeRedeclaration = true; 485 486 if (!isLookupMap()) { 487 unsigned Size = LookupPtr.getInt(); 488 489 // The lookup data is stored as an array. Search through the array 490 // to find the insertion location. 491 NamedDecl **Array; 492 if (Size == 0) { 493 Array = new NamedDecl*[LookupIsMap - 1]; 494 LookupPtr.setPointer(Array); 495 } else { 496 Array = static_cast<NamedDecl **>(LookupPtr.getPointer()); 497 } 498 499 // We always keep declarations of the same name next to each other 500 // in the array, so that it is easy to return multiple results 501 // from lookup(). 502 unsigned FirstMatch; 503 for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch) 504 if (Array[FirstMatch]->getDeclName() == D->getDeclName()) 505 break; 506 507 unsigned InsertPos = FirstMatch; 508 if (FirstMatch != Size) { 509 // We found another declaration with the same name. First 510 // determine whether this is a redeclaration of an existing 511 // declaration in this scope, in which case we will replace the 512 // existing declaration. 513 unsigned LastMatch = FirstMatch; 514 for (; LastMatch != Size; ++LastMatch) { 515 if (Array[LastMatch]->getDeclName() != D->getDeclName()) 516 break; 517 518 if (D->declarationReplaces(Array[LastMatch])) { 519 // D is a redeclaration of an existing element in the 520 // array. Replace that element with D. 521 Array[LastMatch] = D; 522 return; 523 } 524 } 525 526 // [FirstMatch, LastMatch) contains the set of declarations that 527 // have the same name as this declaration. Determine where the 528 // declaration D will be inserted into this range. 529 if (D->getKind() == Decl::UsingDirective || 530 D->getIdentifierNamespace() == Decl::IDNS_Tag) 531 InsertPos = LastMatch; 532 else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag) 533 InsertPos = LastMatch - 1; 534 else 535 InsertPos = LastMatch; 536 } 537 538 if (Size < LookupIsMap - 1) { 539 // The new declaration will fit in the array. Insert the new 540 // declaration at the position Match in the array. 541 for (unsigned Idx = Size; Idx > InsertPos; --Idx) 542 Array[Idx] = Array[Idx-1]; 543 544 Array[InsertPos] = D; 545 LookupPtr.setInt(Size + 1); 546 return; 547 } 548 549 // We've reached capacity in this array. Create a map and copy in 550 // all of the declarations that were stored in the array. 551 StoredDeclsMap *Map = new StoredDeclsMap(16); 552 LookupPtr.setPointer(Map); 553 LookupPtr.setInt(LookupIsMap); 554 for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx) 555 makeDeclVisibleInContextImpl(Array[Idx]); 556 delete [] Array; 557 558 // Fall through to perform insertion into the map. 559 MayBeRedeclaration = false; 560 } 561 562 // Insert this declaration into the map. 563 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 564 StoredDeclsMap::iterator Pos = Map->find(D->getDeclName()); 565 if (Pos == Map->end()) { 566 (*Map)[D->getDeclName()].push_back(D); 567 return; 568 } 569 570 if (MayBeRedeclaration) { 571 // Determine if this declaration is actually a redeclaration. 572 std::vector<NamedDecl *>::iterator Redecl 573 = std::find_if(Pos->second.begin(), Pos->second.end(), 574 std::bind1st(std::mem_fun(&NamedDecl::declarationReplaces), 575 D)); 576 if (Redecl != Pos->second.end()) { 577 *Redecl = D; 578 return; 579 } 580 } 581 582 // Put this declaration into the appropriate slot. 583 if (D->getKind() == Decl::UsingDirective || 584 D->getIdentifierNamespace() == Decl::IDNS_Tag 585 || Pos->second.empty()) 586 Pos->second.push_back(D); 587 else if (Pos->second.back()->getIdentifierNamespace() == Decl::IDNS_Tag) { 588 NamedDecl *TagD = Pos->second.back(); 589 Pos->second.back() = D; 590 Pos->second.push_back(TagD); 591 } else 592 Pos->second.push_back(D); 593} 594 595/// Returns iterator range [First, Last) of UsingDirectiveDecls stored within 596/// this context. 597DeclContext::udir_iterator_range DeclContext::getUsingDirectives() const { 598 lookup_const_result Result = lookup(UsingDirectiveDecl::getName()); 599 return udir_iterator_range(reinterpret_cast<udir_iterator>(Result.first), 600 reinterpret_cast<udir_iterator>(Result.second)); 601} 602 603