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