IdentifierResolver.cpp revision b0212bdede2abd0ca5e893d90464f5b0f3ce9943
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 "IdentifierResolver.h" 16#include "clang/Basic/LangOptions.h" 17#include <list> 18#include <vector> 19 20using namespace clang; 21 22//===----------------------------------------------------------------------===// 23// IdDeclInfoMap class 24//===----------------------------------------------------------------------===// 25 26/// IdDeclInfoMap - Associates IdDeclInfos with declaration names. 27/// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each 28/// individual IdDeclInfo to heap. 29class IdentifierResolver::IdDeclInfoMap { 30 static const unsigned int VECTOR_SIZE = 512; 31 // Holds vectors of IdDeclInfos that serve as 'pools'. 32 // New vectors are added when the current one is full. 33 std::list< std::vector<IdDeclInfo> > IDIVecs; 34 unsigned int CurIndex; 35 36public: 37 IdDeclInfoMap() : CurIndex(VECTOR_SIZE) {} 38 39 /// Returns the IdDeclInfo associated to the DeclarationName. 40 /// It creates a new IdDeclInfo if one was not created before for this id. 41 IdDeclInfo &operator[](DeclarationName Name); 42}; 43 44 45//===----------------------------------------------------------------------===// 46// LookupContext Implementation 47//===----------------------------------------------------------------------===// 48 49/// getContext - Returns translation unit context for non ScopedDecls and 50/// for EnumConstantDecls returns the parent context of their EnumDecl. 51DeclContext *IdentifierResolver::LookupContext::getContext(Decl *D) { 52 DeclContext *Ctx; 53 54 if (CXXFieldDecl *FD = dyn_cast<CXXFieldDecl>(D)) 55 return FD->getParent(); 56 57 if (EnumConstantDecl *EnumD = dyn_cast<EnumConstantDecl>(D)) { 58 Ctx = EnumD->getDeclContext()->getParent(); 59 } else if (ScopedDecl *SD = dyn_cast<ScopedDecl>(D)) 60 Ctx = SD->getDeclContext(); 61 else if (OverloadedFunctionDecl *Ovl = dyn_cast<OverloadedFunctionDecl>(D)) 62 Ctx = Ovl->getDeclContext(); 63 else 64 return TUCtx(); 65 66 if (isa<TranslationUnitDecl>(Ctx)) 67 return TUCtx(); 68 69 return Ctx; 70} 71 72/// isEqOrContainedBy - Returns true of the given context is the same or a 73/// parent of this one. 74bool IdentifierResolver::LookupContext::isEqOrContainedBy( 75 const LookupContext &PC) const { 76 if (PC.isTU()) return true; 77 78 for (LookupContext Next = *this; !Next.isTU(); Next = Next.getParent()) 79 if (Next.Ctx == PC.Ctx) return true; 80 81 return false; 82} 83 84 85//===----------------------------------------------------------------------===// 86// IdDeclInfo Implementation 87//===----------------------------------------------------------------------===// 88 89/// FindContext - Returns an iterator pointing just after the decl that is 90/// in the given context or in a parent of it. The search is in reverse 91/// order, from end to begin. 92IdentifierResolver::IdDeclInfo::DeclsTy::iterator 93IdentifierResolver::IdDeclInfo::FindContext(const LookupContext &Ctx, 94 const DeclsTy::iterator &Start) { 95 for (DeclsTy::iterator I = Start; I != Decls.begin(); --I) { 96 if (Ctx.isEqOrContainedBy(LookupContext(*(I-1)))) 97 return I; 98 } 99 100 return Decls.begin(); 101} 102 103/// AddShadowed - Add a decl by putting it directly above the 'Shadow' decl. 104/// Later lookups will find the 'Shadow' decl first. The 'Shadow' decl must 105/// be already added to the scope chain and must be in the same context as 106/// the decl that we want to add. 107void IdentifierResolver::IdDeclInfo::AddShadowed(NamedDecl *D, 108 NamedDecl *Shadow) { 109 assert(LookupContext(D) == LookupContext(Shadow) && 110 "Decl and Shadow not in same context!"); 111 112 for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) { 113 if (Shadow == *(I-1)) { 114 Decls.insert(I-1, D); 115 return; 116 } 117 } 118 119 assert(0 && "Shadow wasn't in scope chain!"); 120} 121 122/// RemoveDecl - Remove the decl from the scope chain. 123/// The decl must already be part of the decl chain. 124void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) { 125 for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) { 126 if (D == *(I-1)) { 127 Decls.erase(I-1); 128 return; 129 } 130 } 131 132 assert(0 && "Didn't find this decl on its identifier's chain!"); 133} 134 135 136//===----------------------------------------------------------------------===// 137// IdentifierResolver Implementation 138//===----------------------------------------------------------------------===// 139 140IdentifierResolver::IdentifierResolver(const LangOptions &langOpt) 141 : LangOpt(langOpt), IdDeclInfos(new IdDeclInfoMap) { 142} 143IdentifierResolver::~IdentifierResolver() { 144 delete IdDeclInfos; 145} 146 147/// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true 148/// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns 149/// true if 'D' belongs to the given declaration context. 150bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx, 151 Scope *S) const { 152 if (Ctx->isFunctionOrMethod()) { 153 if (S->isDeclScope(D)) 154 return true; 155 if (LangOpt.CPlusPlus) { 156 // C++ 3.3.2p4: 157 // Names declared in the for-init-statement, and in the condition of if, 158 // while, for, and switch statements are local to the if, while, for, or 159 // switch statement (including the controlled statement), and shall not be 160 // redeclared in a subsequent condition of that statement nor in the 161 // outermost block (or, for the if statement, any of the outermost blocks) 162 // of the controlled statement. 163 // 164 assert(S->getParent() && "No TUScope?"); 165 if (S->getParent()->getFlags() & Scope::ControlScope) 166 return S->getParent()->isDeclScope(D); 167 } 168 return false; 169 } 170 171 return LookupContext(D) == LookupContext(Ctx); 172} 173 174/// AddDecl - Link the decl to its shadowed decl chain. 175void IdentifierResolver::AddDecl(NamedDecl *D) { 176 DeclarationName Name = D->getDeclName(); 177 void *Ptr = Name.getFETokenInfo<void>(); 178 179 if (!Ptr) { 180 Name.setFETokenInfo(D); 181 return; 182 } 183 184 IdDeclInfo *IDI; 185 186 if (isDeclPtr(Ptr)) { 187 Name.setFETokenInfo(NULL); 188 IDI = &(*IdDeclInfos)[Name]; 189 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 190 IDI->AddDecl(PrevD); 191 } else 192 IDI = toIdDeclInfo(Ptr); 193 194 IDI->AddDecl(D); 195} 196 197/// AddShadowedDecl - Link the decl to its shadowed decl chain putting it 198/// after the decl that the iterator points to, thus the 'Shadow' decl will be 199/// encountered before the 'D' decl. 200void IdentifierResolver::AddShadowedDecl(NamedDecl *D, NamedDecl *Shadow) { 201 assert(D->getDeclName() == Shadow->getDeclName() && "Different ids!"); 202 assert(LookupContext(D) == LookupContext(Shadow) && "Different context!"); 203 204 DeclarationName Name = D->getDeclName(); 205 void *Ptr = Name.getFETokenInfo<void>(); 206 assert(Ptr && "No decl from Ptr ?"); 207 208 IdDeclInfo *IDI; 209 210 if (isDeclPtr(Ptr)) { 211 Name.setFETokenInfo(NULL); 212 IDI = &(*IdDeclInfos)[Name]; 213 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr); 214 assert(PrevD == Shadow && "Invalid shadow decl ?"); 215 IDI->AddDecl(D); 216 IDI->AddDecl(PrevD); 217 return; 218 } 219 220 IDI = toIdDeclInfo(Ptr); 221 IDI->AddShadowed(D, Shadow); 222} 223 224/// RemoveDecl - Unlink the decl from its shadowed decl chain. 225/// The decl must already be part of the decl chain. 226void IdentifierResolver::RemoveDecl(NamedDecl *D) { 227 assert(D && "null param passed"); 228 DeclarationName Name = D->getDeclName(); 229 void *Ptr = Name.getFETokenInfo<void>(); 230 231 assert(Ptr && "Didn't find this decl on its identifier's chain!"); 232 233 if (isDeclPtr(Ptr)) { 234 assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); 235 Name.setFETokenInfo(NULL); 236 return; 237 } 238 239 return toIdDeclInfo(Ptr)->RemoveDecl(D); 240} 241 242/// begin - Returns an iterator for decls with name 'Name', starting at 243/// declaration context 'Ctx'. If 'LookInParentCtx' is true, it will walk the 244/// decls of parent declaration contexts too. 245IdentifierResolver::iterator 246IdentifierResolver::begin(DeclarationName Name, const DeclContext *Ctx, 247 bool LookInParentCtx) { 248 assert(Ctx && "null param passed"); 249 250 void *Ptr = Name.getFETokenInfo<void>(); 251 if (!Ptr) return end(); 252 253 LookupContext LC(Ctx); 254 255 if (isDeclPtr(Ptr)) { 256 NamedDecl *D = static_cast<NamedDecl*>(Ptr); 257 LookupContext DC(D); 258 259 if (( LookInParentCtx && LC.isEqOrContainedBy(DC)) || 260 (!LookInParentCtx && LC == DC)) 261 return iterator(D); 262 else 263 return end(); 264 } 265 266 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 267 268 IdDeclInfo::DeclsTy::iterator I; 269 if (LookInParentCtx) 270 I = IDI->FindContext(LC); 271 else { 272 for (I = IDI->decls_end(); I != IDI->decls_begin(); --I) 273 if (LookupContext(*(I-1)) == LC) 274 break; 275 } 276 277 if (I != IDI->decls_begin()) 278 return iterator(I-1, LookInParentCtx); 279 else // No decls found. 280 return end(); 281} 282 283/// PreIncIter - Do a preincrement when 'Ptr' is a BaseIter. 284void IdentifierResolver::iterator::PreIncIter() { 285 NamedDecl *D = **this; 286 LookupContext Ctx(D); 287 void *InfoPtr = D->getDeclName().getFETokenInfo<void>(); 288 assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?"); 289 IdDeclInfo *Info = toIdDeclInfo(InfoPtr); 290 291 BaseIter I = getIterator(); 292 if (LookInParentCtx()) 293 I = Info->FindContext(Ctx, I); 294 else { 295 if (I != Info->decls_begin() && LookupContext(*(I-1)) != Ctx) { 296 // The next decl is in different declaration context. 297 // Skip remaining decls and set the iterator to the end. 298 I = Info->decls_begin(); 299 } 300 } 301 302 if (I != Info->decls_begin()) 303 *this = iterator(I-1, LookInParentCtx()); 304 else // No more decls. 305 *this = end(); 306} 307 308 309//===----------------------------------------------------------------------===// 310// IdDeclInfoMap Implementation 311//===----------------------------------------------------------------------===// 312 313/// Returns the IdDeclInfo associated to the DeclarationName. 314/// It creates a new IdDeclInfo if one was not created before for this id. 315IdentifierResolver::IdDeclInfo & 316IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) { 317 void *Ptr = Name.getFETokenInfo<void>(); 318 319 if (Ptr) return *toIdDeclInfo(Ptr); 320 321 if (CurIndex == VECTOR_SIZE) { 322 // Add a IdDeclInfo vector 'pool' 323 IDIVecs.push_back(std::vector<IdDeclInfo>()); 324 // Fill the vector 325 IDIVecs.back().resize(VECTOR_SIZE); 326 CurIndex = 0; 327 } 328 IdDeclInfo *IDI = &IDIVecs.back()[CurIndex]; 329 Name.setFETokenInfo(reinterpret_cast<void*>( 330 reinterpret_cast<uintptr_t>(IDI) | 0x1) 331 ); 332 ++CurIndex; 333 return *IDI; 334} 335