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