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