DeclBase.cpp revision 6ed40e351a7c1fb3084434f1db19216b79623cf0
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/DeclObjC.h" 16#include "clang/AST/DeclCXX.h" 17#include "clang/AST/ASTContext.h" 18#include "clang/AST/Type.h" 19#include "llvm/ADT/DenseMap.h" 20#include <algorithm> 21#include <functional> 22#include <vector> 23using namespace clang; 24 25//===----------------------------------------------------------------------===// 26// Statistics 27//===----------------------------------------------------------------------===// 28 29// temporary statistics gathering 30static unsigned nFuncs = 0; 31static unsigned nVars = 0; 32static unsigned nParmVars = 0; 33static unsigned nOriginalParmVars = 0; 34static unsigned nSUC = 0; 35static unsigned nCXXSUC = 0; 36static unsigned nEnumConst = 0; 37static unsigned nEnumDecls = 0; 38static unsigned nNamespaces = 0; 39static unsigned nOverFuncs = 0; 40static unsigned nTypedef = 0; 41static unsigned nFieldDecls = 0; 42static unsigned nInterfaceDecls = 0; 43static unsigned nClassDecls = 0; 44static unsigned nMethodDecls = 0; 45static unsigned nProtocolDecls = 0; 46static unsigned nForwardProtocolDecls = 0; 47static unsigned nCategoryDecls = 0; 48static unsigned nIvarDecls = 0; 49static unsigned nAtDefsFieldDecls = 0; 50static unsigned nObjCImplementationDecls = 0; 51static unsigned nObjCCategoryImpl = 0; 52static unsigned nObjCCompatibleAlias = 0; 53static unsigned nObjCPropertyDecl = 0; 54static unsigned nObjCPropertyImplDecl = 0; 55static unsigned nLinkageSpecDecl = 0; 56static unsigned nFileScopeAsmDecl = 0; 57static unsigned nBlockDecls = 0; 58 59static bool StatSwitch = false; 60 61// This keeps track of all decl attributes. Since so few decls have attrs, we 62// keep them in a hash map instead of wasting space in the Decl class. 63typedef llvm::DenseMap<const Decl*, Attr*> DeclAttrMapTy; 64 65static DeclAttrMapTy *DeclAttrs = 0; 66 67const char *Decl::getDeclKindName() const { 68 switch (DeclKind) { 69 default: assert(0 && "Unknown decl kind!"); 70 case Namespace: return "Namespace"; 71 case OverloadedFunction: return "OverloadedFunction"; 72 case Typedef: return "Typedef"; 73 case Function: return "Function"; 74 case Var: return "Var"; 75 case ParmVar: return "ParmVar"; 76 case OriginalParmVar: return "OriginalParmVar"; 77 case EnumConstant: return "EnumConstant"; 78 case ObjCIvar: return "ObjCIvar"; 79 case ObjCInterface: return "ObjCInterface"; 80 case ObjCImplementation: return "ObjCImplementation"; 81 case ObjCClass: return "ObjCClass"; 82 case ObjCMethod: return "ObjCMethod"; 83 case ObjCProtocol: return "ObjCProtocol"; 84 case ObjCProperty: return "ObjCProperty"; 85 case ObjCPropertyImpl: return "ObjCPropertyImpl"; 86 case ObjCForwardProtocol: return "ObjCForwardProtocol"; 87 case Record: return "Record"; 88 case CXXRecord: return "CXXRecord"; 89 case Enum: return "Enum"; 90 case Block: return "Block"; 91 } 92} 93 94bool Decl::CollectingStats(bool Enable) { 95 if (Enable) 96 StatSwitch = true; 97 return StatSwitch; 98} 99 100void Decl::PrintStats() { 101 fprintf(stderr, "*** Decl Stats:\n"); 102 fprintf(stderr, " %d decls total.\n", 103 int(nFuncs+nVars+nParmVars+nOriginalParmVars+nFieldDecls+nSUC+nCXXSUC+ 104 nEnumDecls+nEnumConst+nTypedef+nInterfaceDecls+nClassDecls+ 105 nMethodDecls+nProtocolDecls+nCategoryDecls+nIvarDecls+ 106 nAtDefsFieldDecls+nNamespaces+nOverFuncs)); 107 fprintf(stderr, " %d namespace decls, %d each (%d bytes)\n", 108 nNamespaces, (int)sizeof(NamespaceDecl), 109 int(nNamespaces*sizeof(NamespaceDecl))); 110 fprintf(stderr, " %d overloaded function decls, %d each (%d bytes)\n", 111 nOverFuncs, (int)sizeof(OverloadedFunctionDecl), 112 int(nOverFuncs*sizeof(OverloadedFunctionDecl))); 113 fprintf(stderr, " %d function decls, %d each (%d bytes)\n", 114 nFuncs, (int)sizeof(FunctionDecl), int(nFuncs*sizeof(FunctionDecl))); 115 fprintf(stderr, " %d variable decls, %d each (%d bytes)\n", 116 nVars, (int)sizeof(VarDecl), 117 int(nVars*sizeof(VarDecl))); 118 fprintf(stderr, " %d parameter variable decls, %d each (%d bytes)\n", 119 nParmVars, (int)sizeof(ParmVarDecl), 120 int(nParmVars*sizeof(ParmVarDecl))); 121 fprintf(stderr, " %d original parameter variable decls, %d each (%d bytes)\n", 122 nOriginalParmVars, (int)sizeof(ParmVarWithOriginalTypeDecl), 123 int(nOriginalParmVars*sizeof(ParmVarWithOriginalTypeDecl))); 124 fprintf(stderr, " %d field decls, %d each (%d bytes)\n", 125 nFieldDecls, (int)sizeof(FieldDecl), 126 int(nFieldDecls*sizeof(FieldDecl))); 127 fprintf(stderr, " %d @defs generated field decls, %d each (%d bytes)\n", 128 nAtDefsFieldDecls, (int)sizeof(ObjCAtDefsFieldDecl), 129 int(nAtDefsFieldDecls*sizeof(ObjCAtDefsFieldDecl))); 130 fprintf(stderr, " %d struct/union/class decls, %d each (%d bytes)\n", 131 nSUC, (int)sizeof(RecordDecl), 132 int(nSUC*sizeof(RecordDecl))); 133 fprintf(stderr, " %d C++ struct/union/class decls, %d each (%d bytes)\n", 134 nCXXSUC, (int)sizeof(CXXRecordDecl), 135 int(nCXXSUC*sizeof(CXXRecordDecl))); 136 fprintf(stderr, " %d enum decls, %d each (%d bytes)\n", 137 nEnumDecls, (int)sizeof(EnumDecl), 138 int(nEnumDecls*sizeof(EnumDecl))); 139 fprintf(stderr, " %d enum constant decls, %d each (%d bytes)\n", 140 nEnumConst, (int)sizeof(EnumConstantDecl), 141 int(nEnumConst*sizeof(EnumConstantDecl))); 142 fprintf(stderr, " %d typedef decls, %d each (%d bytes)\n", 143 nTypedef, (int)sizeof(TypedefDecl),int(nTypedef*sizeof(TypedefDecl))); 144 // Objective-C decls... 145 fprintf(stderr, " %d interface decls, %d each (%d bytes)\n", 146 nInterfaceDecls, (int)sizeof(ObjCInterfaceDecl), 147 int(nInterfaceDecls*sizeof(ObjCInterfaceDecl))); 148 fprintf(stderr, " %d instance variable decls, %d each (%d bytes)\n", 149 nIvarDecls, (int)sizeof(ObjCIvarDecl), 150 int(nIvarDecls*sizeof(ObjCIvarDecl))); 151 fprintf(stderr, " %d class decls, %d each (%d bytes)\n", 152 nClassDecls, (int)sizeof(ObjCClassDecl), 153 int(nClassDecls*sizeof(ObjCClassDecl))); 154 fprintf(stderr, " %d method decls, %d each (%d bytes)\n", 155 nMethodDecls, (int)sizeof(ObjCMethodDecl), 156 int(nMethodDecls*sizeof(ObjCMethodDecl))); 157 fprintf(stderr, " %d protocol decls, %d each (%d bytes)\n", 158 nProtocolDecls, (int)sizeof(ObjCProtocolDecl), 159 int(nProtocolDecls*sizeof(ObjCProtocolDecl))); 160 fprintf(stderr, " %d forward protocol decls, %d each (%d bytes)\n", 161 nForwardProtocolDecls, (int)sizeof(ObjCForwardProtocolDecl), 162 int(nForwardProtocolDecls*sizeof(ObjCForwardProtocolDecl))); 163 fprintf(stderr, " %d category decls, %d each (%d bytes)\n", 164 nCategoryDecls, (int)sizeof(ObjCCategoryDecl), 165 int(nCategoryDecls*sizeof(ObjCCategoryDecl))); 166 167 fprintf(stderr, " %d class implementation decls, %d each (%d bytes)\n", 168 nObjCImplementationDecls, (int)sizeof(ObjCImplementationDecl), 169 int(nObjCImplementationDecls*sizeof(ObjCImplementationDecl))); 170 171 fprintf(stderr, " %d class implementation decls, %d each (%d bytes)\n", 172 nObjCCategoryImpl, (int)sizeof(ObjCCategoryImplDecl), 173 int(nObjCCategoryImpl*sizeof(ObjCCategoryImplDecl))); 174 175 fprintf(stderr, " %d compatibility alias decls, %d each (%d bytes)\n", 176 nObjCCompatibleAlias, (int)sizeof(ObjCCompatibleAliasDecl), 177 int(nObjCCompatibleAlias*sizeof(ObjCCompatibleAliasDecl))); 178 179 fprintf(stderr, " %d property decls, %d each (%d bytes)\n", 180 nObjCPropertyDecl, (int)sizeof(ObjCPropertyDecl), 181 int(nObjCPropertyDecl*sizeof(ObjCPropertyDecl))); 182 183 fprintf(stderr, " %d property implementation decls, %d each (%d bytes)\n", 184 nObjCPropertyImplDecl, (int)sizeof(ObjCPropertyImplDecl), 185 int(nObjCPropertyImplDecl*sizeof(ObjCPropertyImplDecl))); 186 187 fprintf(stderr, "Total bytes = %d\n", 188 int(nFuncs*sizeof(FunctionDecl)+ 189 nVars*sizeof(VarDecl)+nParmVars*sizeof(ParmVarDecl)+ 190 nOriginalParmVars*sizeof(ParmVarWithOriginalTypeDecl)+ 191 nFieldDecls*sizeof(FieldDecl)+nSUC*sizeof(RecordDecl)+ 192 nCXXSUC*sizeof(CXXRecordDecl)+ 193 nEnumDecls*sizeof(EnumDecl)+nEnumConst*sizeof(EnumConstantDecl)+ 194 nTypedef*sizeof(TypedefDecl)+ 195 nInterfaceDecls*sizeof(ObjCInterfaceDecl)+ 196 nIvarDecls*sizeof(ObjCIvarDecl)+ 197 nClassDecls*sizeof(ObjCClassDecl)+ 198 nMethodDecls*sizeof(ObjCMethodDecl)+ 199 nProtocolDecls*sizeof(ObjCProtocolDecl)+ 200 nForwardProtocolDecls*sizeof(ObjCForwardProtocolDecl)+ 201 nCategoryDecls*sizeof(ObjCCategoryDecl)+ 202 nObjCImplementationDecls*sizeof(ObjCImplementationDecl)+ 203 nObjCCategoryImpl*sizeof(ObjCCategoryImplDecl)+ 204 nObjCCompatibleAlias*sizeof(ObjCCompatibleAliasDecl)+ 205 nObjCPropertyDecl*sizeof(ObjCPropertyDecl)+ 206 nObjCPropertyImplDecl*sizeof(ObjCPropertyImplDecl)+ 207 nLinkageSpecDecl*sizeof(LinkageSpecDecl)+ 208 nFileScopeAsmDecl*sizeof(FileScopeAsmDecl)+ 209 nNamespaces*sizeof(NamespaceDecl)+ 210 nOverFuncs*sizeof(OverloadedFunctionDecl))); 211 212} 213 214void Decl::addDeclKind(Kind k) { 215 switch (k) { 216 case Namespace: nNamespaces++; break; 217 case OverloadedFunction: nOverFuncs++; break; 218 case Typedef: nTypedef++; break; 219 case Function: nFuncs++; break; 220 case Var: nVars++; break; 221 case ParmVar: nParmVars++; break; 222 case OriginalParmVar: nOriginalParmVars++; break; 223 case EnumConstant: nEnumConst++; break; 224 case Field: nFieldDecls++; break; 225 case Record: nSUC++; break; 226 case Enum: nEnumDecls++; break; 227 case ObjCInterface: nInterfaceDecls++; break; 228 case ObjCClass: nClassDecls++; break; 229 case ObjCMethod: nMethodDecls++; break; 230 case ObjCProtocol: nProtocolDecls++; break; 231 case ObjCForwardProtocol: nForwardProtocolDecls++; break; 232 case ObjCCategory: nCategoryDecls++; break; 233 case ObjCIvar: nIvarDecls++; break; 234 case ObjCAtDefsField: nAtDefsFieldDecls++; break; 235 case ObjCImplementation: nObjCImplementationDecls++; break; 236 case ObjCCategoryImpl: nObjCCategoryImpl++; break; 237 case ObjCCompatibleAlias: nObjCCompatibleAlias++; break; 238 case ObjCProperty: nObjCPropertyDecl++; break; 239 case ObjCPropertyImpl: nObjCPropertyImplDecl++; break; 240 case LinkageSpec: nLinkageSpecDecl++; break; 241 case FileScopeAsm: nFileScopeAsmDecl++; break; 242 case Block: nBlockDecls++; break; 243 case ImplicitParam: 244 case TranslationUnit: break; 245 246 case CXXRecord: nCXXSUC++; break; 247 // FIXME: Statistics for C++ decls. 248 case TemplateTypeParm: 249 case NonTypeTemplateParm: 250 case CXXMethod: 251 case CXXConstructor: 252 case CXXDestructor: 253 case CXXConversion: 254 case CXXClassVar: 255 break; 256 } 257} 258 259//===----------------------------------------------------------------------===// 260// Decl Implementation 261//===----------------------------------------------------------------------===// 262 263// Out-of-line virtual method providing a home for Decl. 264Decl::~Decl() { 265 if (!HasAttrs) 266 return; 267 268 DeclAttrMapTy::iterator it = DeclAttrs->find(this); 269 assert(it != DeclAttrs->end() && "No attrs found but HasAttrs is true!"); 270 271 // release attributes. 272 delete it->second; 273 invalidateAttrs(); 274} 275 276void Decl::addAttr(Attr *NewAttr) { 277 if (!DeclAttrs) 278 DeclAttrs = new DeclAttrMapTy(); 279 280 Attr *&ExistingAttr = (*DeclAttrs)[this]; 281 282 NewAttr->setNext(ExistingAttr); 283 ExistingAttr = NewAttr; 284 285 HasAttrs = true; 286} 287 288void Decl::invalidateAttrs() { 289 if (!HasAttrs) return; 290 291 HasAttrs = false; 292 (*DeclAttrs)[this] = 0; 293 DeclAttrs->erase(this); 294 295 if (DeclAttrs->empty()) { 296 delete DeclAttrs; 297 DeclAttrs = 0; 298 } 299} 300 301const Attr *Decl::getAttrs() const { 302 if (!HasAttrs) 303 return 0; 304 305 return (*DeclAttrs)[this]; 306} 307 308void Decl::swapAttrs(Decl *RHS) { 309 bool HasLHSAttr = this->HasAttrs; 310 bool HasRHSAttr = RHS->HasAttrs; 311 312 // Usually, neither decl has attrs, nothing to do. 313 if (!HasLHSAttr && !HasRHSAttr) return; 314 315 // If 'this' has no attrs, swap the other way. 316 if (!HasLHSAttr) 317 return RHS->swapAttrs(this); 318 319 // Handle the case when both decls have attrs. 320 if (HasRHSAttr) { 321 std::swap((*DeclAttrs)[this], (*DeclAttrs)[RHS]); 322 return; 323 } 324 325 // Otherwise, LHS has an attr and RHS doesn't. 326 (*DeclAttrs)[RHS] = (*DeclAttrs)[this]; 327 (*DeclAttrs).erase(this); 328 this->HasAttrs = false; 329 RHS->HasAttrs = true; 330} 331 332 333void Decl::Destroy(ASTContext& C) { 334 if (ScopedDecl* SD = dyn_cast<ScopedDecl>(this)) { 335 336 // Observe the unrolled recursion. By setting N->NextDeclarator = 0x0 337 // within the loop, only the Destroy method for the first ScopedDecl 338 // will deallocate all of the ScopedDecls in a chain. 339 340 ScopedDecl* N = SD->getNextDeclarator(); 341 342 while (N) { 343 ScopedDecl* Tmp = N->getNextDeclarator(); 344 N->NextDeclarator = 0x0; 345 N->Destroy(C); 346 N = Tmp; 347 } 348 } 349 350 this->~Decl(); 351 C.getAllocator().Deallocate((void *)this); 352} 353 354Decl *Decl::castFromDeclContext (const DeclContext *D) { 355 return DeclContext::CastTo<Decl>(D); 356} 357 358DeclContext *Decl::castToDeclContext(const Decl *D) { 359 return DeclContext::CastTo<DeclContext>(D); 360} 361 362//===----------------------------------------------------------------------===// 363// DeclContext Implementation 364//===----------------------------------------------------------------------===// 365 366const DeclContext *DeclContext::getParent() const { 367 if (const ScopedDecl *SD = dyn_cast<ScopedDecl>(this)) 368 return SD->getDeclContext(); 369 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(this)) 370 return BD->getParentContext(); 371 else 372 return NULL; 373} 374 375const DeclContext *DeclContext::getLexicalParent() const { 376 if (const ScopedDecl *SD = dyn_cast<ScopedDecl>(this)) 377 return SD->getLexicalDeclContext(); 378 return getParent(); 379} 380 381// FIXME: We really want to use a DenseSet here to eliminate the 382// redundant storage of the declaration names, but (1) it doesn't give 383// us the ability to search based on DeclarationName, (2) we really 384// need something more like a DenseMultiSet, and (3) it's 385// implemented in terms of DenseMap anyway. However, this data 386// structure is really space-inefficient, so we'll have to do 387// something. 388typedef llvm::DenseMap<DeclarationName, std::vector<ScopedDecl*> > 389 StoredDeclsMap; 390 391DeclContext::~DeclContext() { 392 unsigned Size = LookupPtr.getInt(); 393 if (Size == LookupIsMap) { 394 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 395 delete Map; 396 } else { 397 ScopedDecl **Array = static_cast<ScopedDecl**>(LookupPtr.getPointer()); 398 delete [] Array; 399 } 400} 401 402void DeclContext::DestroyDecls(ASTContext &C) { 403 for (decl_iterator D = Decls.begin(); D != Decls.end(); ++D) { 404 if ((*D)->getLexicalDeclContext() == this) 405 (*D)->Destroy(C); 406 } 407} 408 409DeclContext *DeclContext::getPrimaryContext(ASTContext &Context) { 410 switch (DeclKind) { 411 case Decl::Block: 412 case Decl::TranslationUnit: 413 // There is only one DeclContext for these entities. 414 return this; 415 416 case Decl::Namespace: 417 // The original namespace is our primary context. 418 return static_cast<NamespaceDecl*>(this)->getOriginalNamespace(); 419 420 case Decl::Enum: 421 // The declaration associated with the enumeration type is our 422 // primary context. 423 return Context.getTypeDeclType(static_cast<EnumDecl*>(this)) 424 ->getAsEnumType()->getDecl(); 425 426 case Decl::Record: 427 case Decl::CXXRecord: { 428 // The declaration associated with the type is be our primary 429 // context. 430#if 0 431 // FIXME: This is what we expect to do. However, it doesn't work 432 // because ASTContext::setTagDefinition changes the result of 433 // Context.getTypeDeclType, meaning that our "primary" declaration 434 // of a RecordDecl/CXXRecordDecl will change, and we won't be able 435 // to find any values inserted into the earlier "primary" 436 // declaration. We need better tracking of redeclarations and 437 // definitions. 438 QualType Type = Context.getTypeDeclType(static_cast<RecordDecl*>(this)); 439 return Type->getAsRecordType()->getDecl(); 440#else 441 // FIXME: This hack will work for now, because the declaration we 442 // create when we're defining the record is the one we'll use as 443 // the definition later. 444 return this; 445#endif 446 } 447 448 case Decl::ObjCMethod: 449 return this; 450 451 case Decl::ObjCInterface: 452 // FIXME: Can Objective-C interfaces be forward-declared? 453 return this; 454 455 default: 456 assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast && 457 "Unknown DeclContext kind"); 458 return this; 459 } 460} 461 462DeclContext *DeclContext::getNextContext() { 463 switch (DeclKind) { 464 case Decl::Block: 465 case Decl::TranslationUnit: 466 case Decl::Enum: 467 case Decl::Record: 468 case Decl::CXXRecord: 469 case Decl::ObjCMethod: 470 case Decl::ObjCInterface: 471 // There is only one DeclContext for these entities. 472 return 0; 473 474 case Decl::Namespace: 475 // Return the next namespace 476 return static_cast<NamespaceDecl*>(this)->getNextNamespace(); 477 478 default: 479 assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast && 480 "Unknown DeclContext kind"); 481 return 0; 482 } 483} 484 485void DeclContext::addDecl(ASTContext &Context, ScopedDecl *D, bool AllowLookup) { 486 Decls.push_back(D); 487 if (AllowLookup) 488 D->getDeclContext()->insert(Context, D); 489} 490 491DeclContext::lookup_result 492DeclContext::lookup(ASTContext &Context, DeclarationName Name) { 493 DeclContext *PrimaryContext = getPrimaryContext(Context); 494 if (PrimaryContext != this) 495 return PrimaryContext->lookup(Context, Name); 496 497 /// If there is no lookup data structure, build one now by walking 498 /// all of the linked DeclContexts (in declaration order!) and 499 /// inserting their values. 500 if (LookupPtr.getPointer() == 0) { 501 for (DeclContext *DCtx = this; DCtx; DCtx = DCtx->getNextContext()) 502 for (decl_iterator D = DCtx->decls_begin(); D != DCtx->decls_end(); ++D) 503 insertImpl(*D); 504 } 505 506 if (isLookupMap()) { 507 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 508 StoredDeclsMap::iterator Pos = Map->find(Name); 509 if (Pos != Map->end()) 510 return lookup_result(&Pos->second.front(), 511 &Pos->second.front() + Pos->second.size()); 512 return lookup_result(0, 0); 513 } 514 515 // We have a small array. Look into it. 516 unsigned Size = LookupPtr.getInt(); 517 ScopedDecl **Array = static_cast<ScopedDecl**>(LookupPtr.getPointer()); 518 for (unsigned Idx = 0; Idx != Size; ++Idx) 519 if (Array[Idx]->getDeclName() == Name) { 520 unsigned Last = Idx + 1; 521 while (Last != Size && Array[Last]->getDeclName() == Name) 522 ++Last; 523 return lookup_result(&Array[Idx], &Array[Last]); 524 } 525 526 return lookup_result(0, 0); 527} 528 529DeclContext::lookup_const_result 530DeclContext::lookup(ASTContext &Context, DeclarationName Name) const { 531 return const_cast<DeclContext*>(this)->lookup(Context, Name); 532} 533 534void DeclContext::insert(ASTContext &Context, ScopedDecl *D) { 535 DeclContext *PrimaryContext = getPrimaryContext(Context); 536 if (PrimaryContext != this) { 537 PrimaryContext->insert(Context, D); 538 return; 539 } 540 541 // If we already have a lookup data structure, perform the insertion 542 // into it. Otherwise, be lazy and don't build that structure until 543 // someone asks for it. 544 if (LookupPtr.getPointer()) 545 insertImpl(D); 546} 547 548void DeclContext::insertImpl(ScopedDecl *D) { 549 bool MayBeRedeclaration = true; 550 551 if (!isLookupMap()) { 552 unsigned Size = LookupPtr.getInt(); 553 554 // The lookup data is stored as an array. Search through the array 555 // to find the insertion location. 556 ScopedDecl **Array; 557 if (Size == 0) { 558 Array = new ScopedDecl*[LookupIsMap - 1]; 559 LookupPtr.setPointer(Array); 560 } else { 561 Array = static_cast<ScopedDecl **>(LookupPtr.getPointer()); 562 } 563 564 // We always keep declarations of the same name next to each other 565 // in the array, so that it is easy to return multiple results 566 // from lookup(). 567 unsigned FirstMatch; 568 for (FirstMatch = 0; FirstMatch != Size; ++FirstMatch) 569 if (Array[FirstMatch]->getDeclName() == D->getDeclName()) 570 break; 571 572 unsigned InsertPos = FirstMatch; 573 if (FirstMatch != Size) { 574 // We found another declaration with the same name. First 575 // determine whether this is a redeclaration of an existing 576 // declaration in this scope, in which case we will replace the 577 // existing declaration. 578 unsigned LastMatch = FirstMatch; 579 for (; LastMatch != Size; ++LastMatch) { 580 if (Array[LastMatch]->getDeclName() != D->getDeclName()) 581 break; 582 583 if (D->declarationReplaces(Array[LastMatch])) { 584 // D is a redeclaration of an existing element in the 585 // array. Replace that element with D. 586 Array[LastMatch] = D; 587 return; 588 } 589 } 590 591 // [FirstMatch, LastMatch) contains the set of declarations that 592 // have the same name as this declaration. Determine where the 593 // declaration D will be inserted into this range. 594 if (D->getIdentifierNamespace() == Decl::IDNS_Tag) 595 InsertPos = LastMatch; 596 else if (Array[LastMatch-1]->getIdentifierNamespace() == Decl::IDNS_Tag) 597 InsertPos = LastMatch - 1; 598 else 599 InsertPos = LastMatch; 600 } 601 602 if (Size < LookupIsMap - 1) { 603 // The new declaration will fit in the array. Insert the new 604 // declaration at the position Match in the array. 605 for (unsigned Idx = Size; Idx > InsertPos; --Idx) 606 Array[Idx] = Array[Idx-1]; 607 608 Array[InsertPos] = D; 609 LookupPtr.setInt(Size + 1); 610 return; 611 } 612 613 // We've reached capacity in this array. Create a map and copy in 614 // all of the declarations that were stored in the array. 615 StoredDeclsMap *Map = new StoredDeclsMap(16); 616 LookupPtr.setPointer(Map); 617 LookupPtr.setInt(LookupIsMap); 618 for (unsigned Idx = 0; Idx != LookupIsMap - 1; ++Idx) 619 insertImpl(Array[Idx]); 620 delete [] Array; 621 622 // Fall through to perform insertion into the map. 623 MayBeRedeclaration = false; 624 } 625 626 // Insert this declaration into the map. 627 StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer()); 628 StoredDeclsMap::iterator Pos = Map->find(D->getDeclName()); 629 if (Pos != Map->end()) { 630 if (MayBeRedeclaration) { 631 // Determine if this declaration is actually a redeclaration. 632 std::vector<ScopedDecl *>::iterator Redecl 633 = std::find_if(Pos->second.begin(), Pos->second.end(), 634 std::bind1st(std::mem_fun(&ScopedDecl::declarationReplaces), 635 D)); 636 if (Redecl != Pos->second.end()) { 637 *Redecl = D; 638 return; 639 } 640 } 641 642 // Put this declaration into the appropriate slot. 643 if (D->getIdentifierNamespace() == Decl::IDNS_Tag || Pos->second.empty()) 644 Pos->second.push_back(D); 645 else if (Pos->second.back()->getIdentifierNamespace() == Decl::IDNS_Tag) { 646 ScopedDecl *TagD = Pos->second.back(); 647 Pos->second.back() = D; 648 Pos->second.push_back(TagD); 649 } else 650 Pos->second.push_back(D); 651 } else { 652 (*Map)[D->getDeclName()].push_back(D); 653 } 654} 655