IdentifierResolver.cpp revision eee242ff426bf79149f221798966e58688383c1e
1//===- IdentifierResolver.cpp - Lexical Scope Name lookup -------*- 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// 10// This file implements the IdentifierResolver class, which is used for lexical 11// scoped lookup, based on declaration names. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/Sema/IdentifierResolver.h" 16#include "clang/Sema/Scope.h" 17#include "clang/AST/Decl.h" 18#include "clang/AST/DeclObjC.h" 19#include "clang/Basic/LangOptions.h" 20#include "clang/Lex/ExternalPreprocessorSource.h" 21#include "clang/Lex/Preprocessor.h" 22 23using namespace clang; 24 25//===----------------------------------------------------------------------===// 26// IdDeclInfoMap class 27//===----------------------------------------------------------------------===// 28 29/// IdDeclInfoMap - Associates IdDeclInfos with declaration names. 30/// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each 31/// individual IdDeclInfo to heap. 32class IdentifierResolver::IdDeclInfoMap { 33 static const unsigned int POOL_SIZE = 512; 34 35 /// We use our own linked-list implementation because it is sadly 36 /// impossible to add something to a pre-C++0x STL container without 37 /// a completely unnecessary copy. 38 struct IdDeclInfoPool { 39 IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {} 40 41 IdDeclInfoPool *Next; 42 IdDeclInfo Pool[POOL_SIZE]; 43 }; 44 45 IdDeclInfoPool *CurPool; 46 unsigned int CurIndex; 47 48public: 49 IdDeclInfoMap() : CurPool(0), CurIndex(POOL_SIZE) {} 50 51 ~IdDeclInfoMap() { 52 IdDeclInfoPool *Cur = CurPool; 53 while (IdDeclInfoPool *P = Cur) { 54 Cur = Cur->Next; 55 delete P; 56 } 57 } 58 59 /// Returns the IdDeclInfo associated to the DeclarationName. 60 /// It creates a new IdDeclInfo if one was not created before for this id. 61 IdDeclInfo &operator[](DeclarationName Name); 62}; 63 64 65//===----------------------------------------------------------------------===// 66// IdDeclInfo Implementation 67//===----------------------------------------------------------------------===// 68 69/// RemoveDecl - Remove the decl from the scope chain. 70/// The decl must already be part of the decl chain. 71void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) { 72 for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) { 73 if (D == *(I-1)) { 74 Decls.erase(I-1); 75 return; 76 } 77 } 78 79 llvm_unreachable("Didn't find this decl on its identifier's chain!"); 80} 81 82bool 83IdentifierResolver::IdDeclInfo::ReplaceDecl(NamedDecl *Old, NamedDecl *New) { 84 for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) { 85 if (Old == *(I-1)) { 86 *(I - 1) = New; 87 return true; 88 } 89 } 90 91 return false; 92} 93 94 95//===----------------------------------------------------------------------===// 96// IdentifierResolver Implementation 97//===----------------------------------------------------------------------===// 98 99IdentifierResolver::IdentifierResolver(Preprocessor &PP) 100 : LangOpt(PP.getLangOptions()), PP(PP), 101 IdDeclInfos(new IdDeclInfoMap) { 102} 103 104IdentifierResolver::~IdentifierResolver() { 105 delete IdDeclInfos; 106} 107 108/// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true 109/// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns 110/// true if 'D' belongs to the given declaration context. 111bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx, 112 ASTContext &Context, Scope *S, 113 bool ExplicitInstantiationOrSpecialization) const { 114 Ctx = Ctx->getRedeclContext(); 115 116 if (Ctx->isFunctionOrMethod()) { 117 // Ignore the scopes associated within transparent declaration contexts. 118 while (S->getEntity() && 119 ((DeclContext *)S->getEntity())->isTransparentContext()) 120 S = S->getParent(); 121 122 if (S->isDeclScope(D)) 123 return true; 124 if (LangOpt.CPlusPlus) { 125 // C++ 3.3.2p3: 126 // The name declared in a catch exception-declaration is local to the 127 // handler and shall not be redeclared in the outermost block of the 128 // handler. 129 // C++ 3.3.2p4: 130 // Names declared in the for-init-statement, and in the condition of if, 131 // while, for, and switch statements are local to the if, while, for, or 132 // switch statement (including the controlled statement), and shall not be 133 // redeclared in a subsequent condition of that statement nor in the 134 // outermost block (or, for the if statement, any of the outermost blocks) 135 // of the controlled statement. 136 // 137 assert(S->getParent() && "No TUScope?"); 138 if (S->getParent()->getFlags() & Scope::ControlScope) 139 return S->getParent()->isDeclScope(D); 140 } 141 return false; 142 } 143 144 DeclContext *DCtx = D->getDeclContext()->getRedeclContext(); 145 return ExplicitInstantiationOrSpecialization 146 ? Ctx->InEnclosingNamespaceSetOf(DCtx) 147 : Ctx->Equals(DCtx); 148} 149 150/// AddDecl - Link the decl to its shadowed decl chain. 151void IdentifierResolver::AddDecl(NamedDecl *D) { 152 DeclarationName Name = D->getDeclName(); 153 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 154 updatingIdentifier(*II); 155 156 void *Ptr = Name.getFETokenInfo<void>(); 157 158 if (!Ptr) { 159 Name.setFETokenInfo(D); 160 return; 161 } 162 163 IdDeclInfo *IDI; 164 165 if (isDeclPtr(Ptr)) { 166 Name.setFETokenInfo(NULL); 167 IDI = &(*IdDeclInfos)[Name]; 168 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 169 IDI->AddDecl(PrevD); 170 } else 171 IDI = toIdDeclInfo(Ptr); 172 173 IDI->AddDecl(D); 174} 175 176void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) { 177 DeclarationName Name = D->getDeclName(); 178 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 179 updatingIdentifier(*II); 180 181 void *Ptr = Name.getFETokenInfo<void>(); 182 183 if (!Ptr) { 184 AddDecl(D); 185 return; 186 } 187 188 if (isDeclPtr(Ptr)) { 189 // We only have a single declaration: insert before or after it, 190 // as appropriate. 191 if (Pos == iterator()) { 192 // Add the new declaration before the existing declaration. 193 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 194 RemoveDecl(PrevD); 195 AddDecl(D); 196 AddDecl(PrevD); 197 } else { 198 // Add new declaration after the existing declaration. 199 AddDecl(D); 200 } 201 202 return; 203 } 204 205 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 206 if (II->isFromAST()) 207 II->setChangedSinceDeserialization(); 208 209 // General case: insert the declaration at the appropriate point in the 210 // list, which already has at least two elements. 211 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 212 if (Pos.isIterator()) { 213 IDI->InsertDecl(Pos.getIterator() + 1, D); 214 } else 215 IDI->InsertDecl(IDI->decls_begin(), D); 216} 217 218/// RemoveDecl - Unlink the decl from its shadowed decl chain. 219/// The decl must already be part of the decl chain. 220void IdentifierResolver::RemoveDecl(NamedDecl *D) { 221 assert(D && "null param passed"); 222 DeclarationName Name = D->getDeclName(); 223 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 224 updatingIdentifier(*II); 225 226 void *Ptr = Name.getFETokenInfo<void>(); 227 228 assert(Ptr && "Didn't find this decl on its identifier's chain!"); 229 230 if (isDeclPtr(Ptr)) { 231 assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); 232 Name.setFETokenInfo(NULL); 233 return; 234 } 235 236 return toIdDeclInfo(Ptr)->RemoveDecl(D); 237} 238 239bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) { 240 assert(Old->getDeclName() == New->getDeclName() && 241 "Cannot replace a decl with another decl of a different name"); 242 243 DeclarationName Name = Old->getDeclName(); 244 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 245 updatingIdentifier(*II); 246 247 void *Ptr = Name.getFETokenInfo<void>(); 248 249 if (!Ptr) 250 return false; 251 252 if (isDeclPtr(Ptr)) { 253 if (Ptr == Old) { 254 Name.setFETokenInfo(New); 255 return true; 256 } 257 return false; 258 } 259 260 return toIdDeclInfo(Ptr)->ReplaceDecl(Old, New); 261} 262 263/// begin - Returns an iterator for decls with name 'Name'. 264IdentifierResolver::iterator 265IdentifierResolver::begin(DeclarationName Name) { 266 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 267 readingIdentifier(*II); 268 269 void *Ptr = Name.getFETokenInfo<void>(); 270 if (!Ptr) return end(); 271 272 if (isDeclPtr(Ptr)) 273 return iterator(static_cast<NamedDecl*>(Ptr)); 274 275 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 276 277 IdDeclInfo::DeclsTy::iterator I = IDI->decls_end(); 278 if (I != IDI->decls_begin()) 279 return iterator(I-1); 280 // No decls found. 281 return end(); 282} 283 284namespace { 285 enum DeclMatchKind { 286 DMK_Different, 287 DMK_Replace, 288 DMK_Ignore 289 }; 290} 291 292/// \brief Compare two declarations to see whether they are different or, 293/// if they are the same, whether the new declaration should replace the 294/// existing declaration. 295static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) { 296 // If the declarations are identical, ignore the new one. 297 if (Existing == New) 298 return DMK_Ignore; 299 300 // If the declarations have different kinds, they're obviously different. 301 if (Existing->getKind() != New->getKind()) 302 return DMK_Different; 303 304 // If the declarations are redeclarations of each other, keep the newest one. 305 if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) { 306 // If the existing declaration is somewhere in the previous declaration 307 // chain of the new declaration, then prefer the new declaration. 308 for (Decl::redecl_iterator RD = New->redecls_begin(), 309 RDEnd = New->redecls_end(); 310 RD != RDEnd; ++RD) { 311 if (*RD == Existing) 312 return DMK_Replace; 313 314 if (RD->isCanonicalDecl()) 315 break; 316 } 317 318 return DMK_Ignore; 319 } 320 321 // If the declarations are both Objective-C classes, and one is a forward 322 // declaration and the other is not, take the full definition. 323 // FIXME: At some point, we'll actually have to detect collisions better. 324 // This logic, however, belongs in the AST reader, not here. 325 if (ObjCInterfaceDecl *ExistingIFace = dyn_cast<ObjCInterfaceDecl>(Existing)) 326 if (ObjCInterfaceDecl *NewIFace = dyn_cast<ObjCInterfaceDecl>(New)) 327 if (ExistingIFace->isForwardDecl() != NewIFace->isForwardDecl()) 328 return ExistingIFace->isForwardDecl()? DMK_Replace : DMK_Ignore; 329 330 return DMK_Different; 331} 332 333bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){ 334 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 335 updatingIdentifier(*II); 336 337 void *Ptr = Name.getFETokenInfo<void>(); 338 339 if (!Ptr) { 340 Name.setFETokenInfo(D); 341 return true; 342 } 343 344 IdDeclInfo *IDI; 345 346 if (isDeclPtr(Ptr)) { 347 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 348 349 switch (compareDeclarations(PrevD, D)) { 350 case DMK_Different: 351 break; 352 353 case DMK_Ignore: 354 return false; 355 356 case DMK_Replace: 357 Name.setFETokenInfo(D); 358 return true; 359 } 360 361 Name.setFETokenInfo(NULL); 362 IDI = &(*IdDeclInfos)[Name]; 363 364 // If the existing declaration is not visible in translation unit scope, 365 // then add the new top-level declaration first. 366 if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) { 367 IDI->AddDecl(D); 368 IDI->AddDecl(PrevD); 369 } else { 370 IDI->AddDecl(PrevD); 371 IDI->AddDecl(D); 372 } 373 return true; 374 } 375 376 IDI = toIdDeclInfo(Ptr); 377 378 // See whether this declaration is identical to any existing declarations. 379 // If not, find the right place to insert it. 380 for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(), 381 IEnd = IDI->decls_end(); 382 I != IEnd; ++I) { 383 384 switch (compareDeclarations(*I, D)) { 385 case DMK_Different: 386 break; 387 388 case DMK_Ignore: 389 return false; 390 391 case DMK_Replace: 392 *I = D; 393 return true; 394 } 395 396 if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) { 397 // We've found a declaration that is not visible from the translation 398 // unit (it's in an inner scope). Insert our declaration here. 399 IDI->InsertDecl(I, D); 400 return true; 401 } 402 } 403 404 // Add the declaration to the end. 405 IDI->AddDecl(D); 406 return true; 407} 408 409void IdentifierResolver::readingIdentifier(IdentifierInfo &II) { 410 if (II.isOutOfDate()) 411 PP.getExternalSource()->updateOutOfDateIdentifier(II); 412} 413 414void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) { 415 if (II.isOutOfDate()) 416 PP.getExternalSource()->updateOutOfDateIdentifier(II); 417 418 if (II.isFromAST()) 419 II.setChangedSinceDeserialization(); 420} 421 422//===----------------------------------------------------------------------===// 423// IdDeclInfoMap Implementation 424//===----------------------------------------------------------------------===// 425 426/// Returns the IdDeclInfo associated to the DeclarationName. 427/// It creates a new IdDeclInfo if one was not created before for this id. 428IdentifierResolver::IdDeclInfo & 429IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) { 430 void *Ptr = Name.getFETokenInfo<void>(); 431 432 if (Ptr) return *toIdDeclInfo(Ptr); 433 434 if (CurIndex == POOL_SIZE) { 435 CurPool = new IdDeclInfoPool(CurPool); 436 CurIndex = 0; 437 } 438 IdDeclInfo *IDI = &CurPool->Pool[CurIndex]; 439 Name.setFETokenInfo(reinterpret_cast<void*>( 440 reinterpret_cast<uintptr_t>(IDI) | 0x1) 441 ); 442 ++CurIndex; 443 return *IDI; 444} 445 446void IdentifierResolver::iterator::incrementSlowCase() { 447 NamedDecl *D = **this; 448 void *InfoPtr = D->getDeclName().getFETokenInfo<void>(); 449 assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?"); 450 IdDeclInfo *Info = toIdDeclInfo(InfoPtr); 451 452 BaseIter I = getIterator(); 453 if (I != Info->decls_begin()) 454 *this = iterator(I-1); 455 else // No more decls. 456 *this = iterator(); 457} 458