IdentifierResolver.cpp revision c4027c82ad4a61f2da1b893ac8fe47bf11e5d50d
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.getLangOpts()), 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() || S->isFunctionPrototypeScope()) { 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->getFlags() & Scope::FnTryScope) 139 return S->getParent()->isDeclScope(D); 140 if (S->getParent()->getFlags() & Scope::ControlScope) { 141 if (S->getParent()->getFlags() & Scope::FnCatchScope) 142 S = S->getParent(); 143 return S->getParent()->isDeclScope(D); 144 } 145 } 146 return false; 147 } 148 149 DeclContext *DCtx = D->getDeclContext()->getRedeclContext(); 150 return ExplicitInstantiationOrSpecialization 151 ? Ctx->InEnclosingNamespaceSetOf(DCtx) 152 : Ctx->Equals(DCtx); 153} 154 155/// AddDecl - Link the decl to its shadowed decl chain. 156void IdentifierResolver::AddDecl(NamedDecl *D) { 157 DeclarationName Name = D->getDeclName(); 158 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 159 updatingIdentifier(*II); 160 161 void *Ptr = Name.getFETokenInfo<void>(); 162 163 if (!Ptr) { 164 Name.setFETokenInfo(D); 165 return; 166 } 167 168 IdDeclInfo *IDI; 169 170 if (isDeclPtr(Ptr)) { 171 Name.setFETokenInfo(NULL); 172 IDI = &(*IdDeclInfos)[Name]; 173 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 174 IDI->AddDecl(PrevD); 175 } else 176 IDI = toIdDeclInfo(Ptr); 177 178 IDI->AddDecl(D); 179} 180 181void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) { 182 DeclarationName Name = D->getDeclName(); 183 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 184 updatingIdentifier(*II); 185 186 void *Ptr = Name.getFETokenInfo<void>(); 187 188 if (!Ptr) { 189 AddDecl(D); 190 return; 191 } 192 193 if (isDeclPtr(Ptr)) { 194 // We only have a single declaration: insert before or after it, 195 // as appropriate. 196 if (Pos == iterator()) { 197 // Add the new declaration before the existing declaration. 198 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 199 RemoveDecl(PrevD); 200 AddDecl(D); 201 AddDecl(PrevD); 202 } else { 203 // Add new declaration after the existing declaration. 204 AddDecl(D); 205 } 206 207 return; 208 } 209 210 // General case: insert the declaration at the appropriate point in the 211 // list, which already has at least two elements. 212 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 213 if (Pos.isIterator()) { 214 IDI->InsertDecl(Pos.getIterator() + 1, D); 215 } else 216 IDI->InsertDecl(IDI->decls_begin(), D); 217} 218 219/// RemoveDecl - Unlink the decl from its shadowed decl chain. 220/// The decl must already be part of the decl chain. 221void IdentifierResolver::RemoveDecl(NamedDecl *D) { 222 assert(D && "null param passed"); 223 DeclarationName Name = D->getDeclName(); 224 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 225 updatingIdentifier(*II); 226 227 void *Ptr = Name.getFETokenInfo<void>(); 228 229 assert(Ptr && "Didn't find this decl on its identifier's chain!"); 230 231 if (isDeclPtr(Ptr)) { 232 assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); 233 Name.setFETokenInfo(NULL); 234 return; 235 } 236 237 return toIdDeclInfo(Ptr)->RemoveDecl(D); 238} 239 240bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) { 241 assert(Old->getDeclName() == New->getDeclName() && 242 "Cannot replace a decl with another decl of a different name"); 243 244 DeclarationName Name = Old->getDeclName(); 245 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 246 updatingIdentifier(*II); 247 248 void *Ptr = Name.getFETokenInfo<void>(); 249 250 if (!Ptr) 251 return false; 252 253 if (isDeclPtr(Ptr)) { 254 if (Ptr == Old) { 255 Name.setFETokenInfo(New); 256 return true; 257 } 258 return false; 259 } 260 261 return toIdDeclInfo(Ptr)->ReplaceDecl(Old, New); 262} 263 264/// begin - Returns an iterator for decls with name 'Name'. 265IdentifierResolver::iterator 266IdentifierResolver::begin(DeclarationName Name) { 267 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 268 readingIdentifier(*II); 269 270 void *Ptr = Name.getFETokenInfo<void>(); 271 if (!Ptr) return end(); 272 273 if (isDeclPtr(Ptr)) 274 return iterator(static_cast<NamedDecl*>(Ptr)); 275 276 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 277 278 IdDeclInfo::DeclsTy::iterator I = IDI->decls_end(); 279 if (I != IDI->decls_begin()) 280 return iterator(I-1); 281 // No decls found. 282 return end(); 283} 284 285namespace { 286 enum DeclMatchKind { 287 DMK_Different, 288 DMK_Replace, 289 DMK_Ignore 290 }; 291} 292 293/// \brief Compare two declarations to see whether they are different or, 294/// if they are the same, whether the new declaration should replace the 295/// existing declaration. 296static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) { 297 // If the declarations are identical, ignore the new one. 298 if (Existing == New) 299 return DMK_Ignore; 300 301 // If the declarations have different kinds, they're obviously different. 302 if (Existing->getKind() != New->getKind()) 303 return DMK_Different; 304 305 // If the declarations are redeclarations of each other, keep the newest one. 306 if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) { 307 // If the existing declaration is somewhere in the previous declaration 308 // chain of the new declaration, then prefer the new declaration. 309 for (Decl::redecl_iterator RD = New->redecls_begin(), 310 RDEnd = New->redecls_end(); 311 RD != RDEnd; ++RD) { 312 if (*RD == Existing) 313 return DMK_Replace; 314 315 if (RD->isCanonicalDecl()) 316 break; 317 } 318 319 return DMK_Ignore; 320 } 321 322 return DMK_Different; 323} 324 325bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){ 326 if (IdentifierInfo *II = Name.getAsIdentifierInfo()) 327 readingIdentifier(*II); 328 329 void *Ptr = Name.getFETokenInfo<void>(); 330 331 if (!Ptr) { 332 Name.setFETokenInfo(D); 333 return true; 334 } 335 336 IdDeclInfo *IDI; 337 338 if (isDeclPtr(Ptr)) { 339 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 340 341 switch (compareDeclarations(PrevD, D)) { 342 case DMK_Different: 343 break; 344 345 case DMK_Ignore: 346 return false; 347 348 case DMK_Replace: 349 Name.setFETokenInfo(D); 350 return true; 351 } 352 353 Name.setFETokenInfo(NULL); 354 IDI = &(*IdDeclInfos)[Name]; 355 356 // If the existing declaration is not visible in translation unit scope, 357 // then add the new top-level declaration first. 358 if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) { 359 IDI->AddDecl(D); 360 IDI->AddDecl(PrevD); 361 } else { 362 IDI->AddDecl(PrevD); 363 IDI->AddDecl(D); 364 } 365 return true; 366 } 367 368 IDI = toIdDeclInfo(Ptr); 369 370 // See whether this declaration is identical to any existing declarations. 371 // If not, find the right place to insert it. 372 for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(), 373 IEnd = IDI->decls_end(); 374 I != IEnd; ++I) { 375 376 switch (compareDeclarations(*I, D)) { 377 case DMK_Different: 378 break; 379 380 case DMK_Ignore: 381 return false; 382 383 case DMK_Replace: 384 *I = D; 385 return true; 386 } 387 388 if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) { 389 // We've found a declaration that is not visible from the translation 390 // unit (it's in an inner scope). Insert our declaration here. 391 IDI->InsertDecl(I, D); 392 return true; 393 } 394 } 395 396 // Add the declaration to the end. 397 IDI->AddDecl(D); 398 return true; 399} 400 401void IdentifierResolver::readingIdentifier(IdentifierInfo &II) { 402 if (II.isOutOfDate()) 403 PP.getExternalSource()->updateOutOfDateIdentifier(II); 404} 405 406void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) { 407 if (II.isOutOfDate()) 408 PP.getExternalSource()->updateOutOfDateIdentifier(II); 409 410 if (II.isFromAST()) 411 II.setChangedSinceDeserialization(); 412} 413 414//===----------------------------------------------------------------------===// 415// IdDeclInfoMap Implementation 416//===----------------------------------------------------------------------===// 417 418/// Returns the IdDeclInfo associated to the DeclarationName. 419/// It creates a new IdDeclInfo if one was not created before for this id. 420IdentifierResolver::IdDeclInfo & 421IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) { 422 void *Ptr = Name.getFETokenInfo<void>(); 423 424 if (Ptr) return *toIdDeclInfo(Ptr); 425 426 if (CurIndex == POOL_SIZE) { 427 CurPool = new IdDeclInfoPool(CurPool); 428 CurIndex = 0; 429 } 430 IdDeclInfo *IDI = &CurPool->Pool[CurIndex]; 431 Name.setFETokenInfo(reinterpret_cast<void*>( 432 reinterpret_cast<uintptr_t>(IDI) | 0x1) 433 ); 434 ++CurIndex; 435 return *IDI; 436} 437 438void IdentifierResolver::iterator::incrementSlowCase() { 439 NamedDecl *D = **this; 440 void *InfoPtr = D->getDeclName().getFETokenInfo<void>(); 441 assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?"); 442 IdDeclInfo *Info = toIdDeclInfo(InfoPtr); 443 444 BaseIter I = getIterator(); 445 if (I != Info->decls_begin()) 446 *this = iterator(I-1); 447 else // No more decls. 448 *this = iterator(); 449} 450