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