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