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