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