DeclBase.cpp revision 3d7641e090cf113dec64306a1597d3e4523e2a55
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 271const DeclContext *DeclContext::getParent() const { 272 if (const Decl *D = dyn_cast<Decl>(this)) 273 return D->getDeclContext(); 274 275 return NULL; 276} 277 278const DeclContext *DeclContext::getLexicalParent() const { 279 if (const Decl *D = dyn_cast<Decl>(this)) 280 return D->getLexicalDeclContext(); 281 282 return getParent(); 283} 284 285// FIXME: We really want to use a DenseSet here to eliminate the 286// redundant storage of the declaration names, but (1) it doesn't give 287// us the ability to search based on DeclarationName, (2) we really 288// need something more like a DenseMultiSet, and (3) it's 289// implemented in terms of DenseMap anyway. However, this data 290// structure is really space-inefficient, so we'll have to do 291// something. 292typedef llvm::DenseMap<DeclarationName, std::vector<NamedDecl*> > 293 StoredDeclsMap; 294 295DeclContext::~DeclContext() { 296 unsigned Size = LookupPtr.getInt(); 297 if (Size == LookupIsMap) { 298 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 299 delete Map; 300 } else { 301 NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer()); 302 delete [] Array; 303 } 304} 305 306void DeclContext::DestroyDecls(ASTContext &C) { 307 for (decl_iterator D = decls_begin(); D != decls_end(); ) 308 (*D++)->Destroy(C); 309} 310 311bool DeclContext::isTransparentContext() const { 312 if (DeclKind == Decl::Enum) 313 return true; // FIXME: Check for C++0x scoped enums 314 else if (DeclKind == Decl::LinkageSpec) 315 return true; 316 else if (DeclKind == Decl::Record || DeclKind == Decl::CXXRecord) 317 return cast<RecordDecl>(this)->isAnonymousStructOrUnion(); 318 else if (DeclKind == Decl::Namespace) 319 return false; // FIXME: Check for C++0x inline namespaces 320 321 return false; 322} 323 324DeclContext *DeclContext::getPrimaryContext() { 325 switch (DeclKind) { 326 case Decl::TranslationUnit: 327 case Decl::LinkageSpec: 328 case Decl::Block: 329 // There is only one DeclContext for these entities. 330 return this; 331 332 case Decl::Namespace: 333 // The original namespace is our primary context. 334 return static_cast<NamespaceDecl*>(this)->getOriginalNamespace(); 335 336 case Decl::Enum: 337 case Decl::Record: 338 case Decl::CXXRecord: 339 // If this is a tag type that has a definition or is currently 340 // being defined, that definition is our primary context. 341 if (TagType *TagT = cast_or_null<TagType>(cast<TagDecl>(this)->TypeForDecl)) 342 if (TagT->isBeingDefined() || 343 (TagT->getDecl() && TagT->getDecl()->isDefinition())) 344 return TagT->getDecl(); 345 return this; 346 347 case Decl::ObjCMethod: 348 return this; 349 350 case Decl::ObjCInterface: 351 case Decl::ObjCProtocol: 352 case Decl::ObjCCategory: 353 // FIXME: Can Objective-C interfaces be forward-declared? 354 return this; 355 356 case Decl::ObjCImplementation: 357 case Decl::ObjCCategoryImpl: 358 return this; 359 360 default: 361 assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast && 362 "Unknown DeclContext kind"); 363 return this; 364 } 365} 366 367DeclContext *DeclContext::getNextContext() { 368 switch (DeclKind) { 369 case Decl::TranslationUnit: 370 case Decl::Enum: 371 case Decl::Record: 372 case Decl::CXXRecord: 373 case Decl::ObjCMethod: 374 case Decl::ObjCInterface: 375 case Decl::ObjCCategory: 376 case Decl::ObjCProtocol: 377 case Decl::ObjCImplementation: 378 case Decl::ObjCCategoryImpl: 379 case Decl::LinkageSpec: 380 case Decl::Block: 381 // There is only one DeclContext for these entities. 382 return 0; 383 384 case Decl::Namespace: 385 // Return the next namespace 386 return static_cast<NamespaceDecl*>(this)->getNextNamespace(); 387 388 default: 389 assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast && 390 "Unknown DeclContext kind"); 391 return 0; 392 } 393} 394 395void DeclContext::addDecl(Decl *D) { 396 assert(D->getLexicalDeclContext() == this && "Decl inserted into wrong lexical context"); 397 assert(!D->NextDeclInScope && D != LastDecl && 398 "Decl already inserted into a DeclContext"); 399 400 if (FirstDecl) { 401 LastDecl->NextDeclInScope = D; 402 LastDecl = D; 403 } else { 404 FirstDecl = LastDecl = D; 405 } 406 407 if (NamedDecl *ND = dyn_cast<NamedDecl>(D)) 408 ND->getDeclContext()->makeDeclVisibleInContext(ND); 409} 410 411/// buildLookup - Build the lookup data structure with all of the 412/// declarations in DCtx (and any other contexts linked to it or 413/// transparent contexts nested within it). 414void DeclContext::buildLookup(DeclContext *DCtx) { 415 for (; DCtx; DCtx = DCtx->getNextContext()) { 416 for (decl_iterator D = DCtx->decls_begin(), DEnd = DCtx->decls_end(); 417 D != DEnd; ++D) { 418 // Insert this declaration into the lookup structure 419 if (NamedDecl *ND = dyn_cast<NamedDecl>(*D)) 420 makeDeclVisibleInContextImpl(ND); 421 422 // If this declaration is itself a transparent declaration context, 423 // add its members (recursively). 424 if (DeclContext *InnerCtx = dyn_cast<DeclContext>(*D)) 425 if (InnerCtx->isTransparentContext()) 426 buildLookup(InnerCtx->getPrimaryContext()); 427 } 428 } 429} 430 431DeclContext::lookup_result 432DeclContext::lookup(DeclarationName Name) { 433 DeclContext *PrimaryContext = getPrimaryContext(); 434 if (PrimaryContext != this) 435 return PrimaryContext->lookup(Name); 436 437 /// If there is no lookup data structure, build one now by walking 438 /// all of the linked DeclContexts (in declaration order!) and 439 /// inserting their values. 440 if (LookupPtr.getPointer() == 0) 441 buildLookup(this); 442 443 if (isLookupMap()) { 444 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 445 StoredDeclsMap::iterator Pos = Map->find(Name); 446 if (Pos != Map->end()) 447 return lookup_result(&Pos->second.front(), 448 &Pos->second.front() + Pos->second.size()); 449 return lookup_result(0, 0); 450 } 451 452 // We have a small array. Look into it. 453 unsigned Size = LookupPtr.getInt(); 454 NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer()); 455 for (unsigned Idx = 0; Idx != Size; ++Idx) 456 if (Array[Idx]->getDeclName() == Name) { 457 unsigned Last = Idx + 1; 458 while (Last != Size && Array[Last]->getDeclName() == Name) 459 ++Last; 460 return lookup_result(&Array[Idx], &Array[Last]); 461 } 462 463 return lookup_result(0, 0); 464} 465 466DeclContext::lookup_const_result 467DeclContext::lookup(DeclarationName Name) const { 468 return const_cast<DeclContext*>(this)->lookup(Name); 469} 470 471const DeclContext *DeclContext::getLookupContext() const { 472 const DeclContext *Ctx = this; 473 // Skip through transparent contexts. 474 while (Ctx->isTransparentContext()) 475 Ctx = Ctx->getParent(); 476 return Ctx; 477} 478 479void DeclContext::makeDeclVisibleInContext(NamedDecl *D) { 480 DeclContext *PrimaryContext = getPrimaryContext(); 481 if (PrimaryContext != this) { 482 PrimaryContext->makeDeclVisibleInContext(D); 483 return; 484 } 485 486 // If we already have a lookup data structure, perform the insertion 487 // into it. Otherwise, be lazy and don't build that structure until 488 // someone asks for it. 489 if (LookupPtr.getPointer()) 490 makeDeclVisibleInContextImpl(D); 491 492 // If we are a transparent context, insert into our parent context, 493 // too. This operation is recursive. 494 if (isTransparentContext()) 495 getParent()->makeDeclVisibleInContext(D); 496} 497 498void DeclContext::makeDeclVisibleInContextImpl(NamedDecl *D) { 499 // Skip unnamed declarations. 500 if (!D->getDeclName()) 501 return; 502 503 bool MayBeRedeclaration = true; 504 505 if (!isLookupMap()) { 506 unsigned Size = LookupPtr.getInt(); 507 508 // The lookup data is stored as an array. Search through the array 509 // to find the insertion location. 510 NamedDecl **Array; 511 if (Size == 0) { 512 Array = new NamedDecl*[LookupIsMap - 1]; 513 LookupPtr.setPointer(Array); 514 } else { 515 Array = static_cast<NamedDecl **>(LookupPtr.getPointer()); 516 } 517 518 // We always keep declarations of the same name next to each other 519 // in the array, so that it is easy to return multiple results 520 // from lookup(). 521 unsigned FirstMatch; 522 for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch) 523 if (Array[FirstMatch]->getDeclName() == D->getDeclName()) 524 break; 525 526 unsigned InsertPos = FirstMatch; 527 if (FirstMatch != Size) { 528 // We found another declaration with the same name. First 529 // determine whether this is a redeclaration of an existing 530 // declaration in this scope, in which case we will replace the 531 // existing declaration. 532 unsigned LastMatch = FirstMatch; 533 for (; LastMatch != Size; ++LastMatch) { 534 if (Array[LastMatch]->getDeclName() != D->getDeclName()) 535 break; 536 537 if (D->declarationReplaces(Array[LastMatch])) { 538 // D is a redeclaration of an existing element in the 539 // array. Replace that element with D. 540 Array[LastMatch] = D; 541 return; 542 } 543 } 544 545 // [FirstMatch, LastMatch) contains the set of declarations that 546 // have the same name as this declaration. Determine where the 547 // declaration D will be inserted into this range. 548 if (D->getKind() == Decl::UsingDirective || 549 D->getIdentifierNamespace() == Decl::IDNS_Tag) 550 InsertPos = LastMatch; 551 else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag) 552 InsertPos = LastMatch - 1; 553 else 554 InsertPos = LastMatch; 555 } 556 557 if (Size < LookupIsMap - 1) { 558 // The new declaration will fit in the array. Insert the new 559 // declaration at the position Match in the array. 560 for (unsigned Idx = Size; Idx > InsertPos; --Idx) 561 Array[Idx] = Array[Idx-1]; 562 563 Array[InsertPos] = D; 564 LookupPtr.setInt(Size + 1); 565 return; 566 } 567 568 // We've reached capacity in this array. Create a map and copy in 569 // all of the declarations that were stored in the array. 570 StoredDeclsMap *Map = new StoredDeclsMap(16); 571 LookupPtr.setPointer(Map); 572 LookupPtr.setInt(LookupIsMap); 573 for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx) 574 makeDeclVisibleInContextImpl(Array[Idx]); 575 delete [] Array; 576 577 // Fall through to perform insertion into the map. 578 MayBeRedeclaration = false; 579 } 580 581 // Insert this declaration into the map. 582 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 583 StoredDeclsMap::iterator Pos = Map->find(D->getDeclName()); 584 if (Pos != Map->end()) { 585 if (MayBeRedeclaration) { 586 // Determine if this declaration is actually a redeclaration. 587 std::vector<NamedDecl *>::iterator Redecl 588 = std::find_if(Pos->second.begin(), Pos->second.end(), 589 std::bind1st(std::mem_fun(&NamedDecl::declarationReplaces), 590 D)); 591 if (Redecl != Pos->second.end()) { 592 *Redecl = D; 593 return; 594 } 595 } 596 597 // Put this declaration into the appropriate slot. 598 if (D->getKind() == Decl::UsingDirective || 599 D->getIdentifierNamespace() == Decl::IDNS_Tag 600 || Pos->second.empty()) 601 Pos->second.push_back(D); 602 else if (Pos->second.back()->getIdentifierNamespace() == Decl::IDNS_Tag) { 603 NamedDecl *TagD = Pos->second.back(); 604 Pos->second.back() = D; 605 Pos->second.push_back(TagD); 606 } else 607 Pos->second.push_back(D); 608 } else { 609 (*Map)[D->getDeclName()].push_back(D); 610 } 611} 612 613/// Returns iterator range [First, Last) of UsingDirectiveDecls stored within 614/// this context. 615DeclContext::udir_iterator_range DeclContext::getUsingDirectives() const { 616 lookup_const_result Result = lookup(UsingDirectiveDecl::getName()); 617 return udir_iterator_range(reinterpret_cast<udir_iterator>(Result.first), 618 reinterpret_cast<udir_iterator>(Result.second)); 619} 620 621