IdentifierResolver.cpp revision 7bc198fb47a498e327a9ceb2d17612dcb3d15095
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 "clang/Basic/IdentifierTable.h" 17#include "clang/AST/Decl.h" 18#include "clang/Parse/Scope.h" 19#include <list> 20#include <vector> 21 22using namespace clang; 23 24namespace { 25 26class IdDeclInfo; 27 28/// Identifier's FETokenInfo contains a Decl pointer if lower bit == 0. 29static inline bool isDeclPtr(void *Ptr) { 30 return (reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 0; 31} 32 33/// Identifier's FETokenInfo contains a IdDeclInfo pointer if lower bit == 1. 34static inline IdDeclInfo *toIdDeclInfo(void *Ptr) { 35 return reinterpret_cast<IdDeclInfo*>( 36 reinterpret_cast<uintptr_t>(Ptr) & ~0x1 37 ); 38} 39 40 41/// IdDeclInfo - Keeps track of information about decls associated to a 42/// particular identifier. IdDeclInfos are lazily constructed and assigned 43/// to an identifier the first time a decl with that identifier is shadowed 44/// in some scope. 45class IdDeclInfo { 46 typedef llvm::SmallVector<NamedDecl *, 2> ShadowedTy; 47 ShadowedTy ShadowedDecls; 48 49public: 50 typedef ShadowedTy::iterator ShadowedIter; 51 52 inline ShadowedIter shadowed_begin() { return ShadowedDecls.begin(); } 53 inline ShadowedIter shadowed_end() { return ShadowedDecls.end(); } 54 55 /// Add a decl in the scope chain. 56 void PushShadowed(NamedDecl *D) { 57 assert(D && "Decl null"); 58 ShadowedDecls.push_back(D); 59 } 60 61 /// Add the decl at the top of scope chain. 62 void PushGlobalShadowed(NamedDecl *D) { 63 assert(D && "Decl null"); 64 ShadowedDecls.insert(ShadowedDecls.begin(), D); 65 } 66 67 /// RemoveShadowed - Remove the decl from the scope chain. 68 /// The decl must already be part of the decl chain. 69 void RemoveShadowed(NamedDecl *D); 70}; 71 72 73/// IdDeclInfoMap - Associates IdDeclInfos with Identifiers. 74/// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each 75/// individual IdDeclInfo to heap. 76class IdDeclInfoMap { 77 static const unsigned int VECTOR_SIZE = 512; 78 // Holds vectors of IdDeclInfos that serve as 'pools'. 79 // New vectors are added when the current one is full. 80 std::list< std::vector<IdDeclInfo> > IDIVecs; 81 unsigned int CurIndex; 82 83public: 84 IdDeclInfoMap() : CurIndex(VECTOR_SIZE) {} 85 86 /// Returns the IdDeclInfo associated to the IdentifierInfo. 87 /// It creates a new IdDeclInfo if one was not created before for this id. 88 IdDeclInfo &operator[](IdentifierInfo *II); 89}; 90 91} // end anonymous namespace 92 93 94IdentifierResolver::IdentifierResolver() : IdDeclInfos(new IdDeclInfoMap) {} 95IdentifierResolver::~IdentifierResolver() { 96 delete static_cast<IdDeclInfoMap*>(IdDeclInfos); 97} 98 99/// AddDecl - Link the decl to its shadowed decl chain. 100void IdentifierResolver::AddDecl(NamedDecl *D, Scope *S) { 101 assert(D && S && "null param passed"); 102 IdentifierInfo *II = D->getIdentifier(); 103 void *Ptr = II->getFETokenInfo<void>(); 104 105 if (!Ptr) { 106 II->setFETokenInfo(D); 107 return; 108 } 109 110 IdDeclInfo *IDI; 111 112 if (isDeclPtr(Ptr)) { 113 II->setFETokenInfo(NULL); 114 IdDeclInfoMap &Map = *static_cast<IdDeclInfoMap*>(IdDeclInfos); 115 IDI = &Map[II]; 116 IDI->PushShadowed(static_cast<NamedDecl*>(Ptr)); 117 } else 118 IDI = toIdDeclInfo(Ptr); 119 120 // C++ [basic.scope]p4: 121 // -- exactly one declaration shall declare a class name or 122 // enumeration name that is not a typedef name and the other 123 // declarations shall all refer to the same object or 124 // enumerator, or all refer to functions and function templates; 125 // in this case the class name or enumeration name is hidden. 126 if (isa<TagDecl>(D)) { 127 // We are pushing the name of a tag (enum or class). 128 IdDeclInfo::ShadowedIter TopIter = IDI->shadowed_end() - 1; 129 if (S->isDeclScope(*TopIter)) { 130 // There is already a declaration with the same name in the same 131 // scope. It must be found before we find the new declaration, 132 // so swap the order on the shadowed declaration stack. 133 NamedDecl *Temp = *TopIter; 134 *TopIter = D; 135 D = Temp; 136 } 137 } 138 139 IDI->PushShadowed(D); 140} 141 142/// AddGlobalDecl - Link the decl at the top of the shadowed decl chain. 143void IdentifierResolver::AddGlobalDecl(NamedDecl *D) { 144 assert(D && "null param passed"); 145 IdentifierInfo *II = D->getIdentifier(); 146 void *Ptr = II->getFETokenInfo<void>(); 147 148 if (!Ptr) { 149 II->setFETokenInfo(D); 150 return; 151 } 152 153 IdDeclInfo *IDI; 154 155 if (isDeclPtr(Ptr)) { 156 II->setFETokenInfo(NULL); 157 IdDeclInfoMap &Map = *static_cast<IdDeclInfoMap*>(IdDeclInfos); 158 IDI = &Map[II]; 159 IDI->PushShadowed(static_cast<NamedDecl*>(Ptr)); 160 } else 161 IDI = toIdDeclInfo(Ptr); 162 163 IDI->PushGlobalShadowed(D); 164} 165 166/// RemoveDecl - Unlink the decl from its shadowed decl chain. 167/// The decl must already be part of the decl chain. 168void IdentifierResolver::RemoveDecl(NamedDecl *D) { 169 assert(D && "null param passed"); 170 IdentifierInfo *II = D->getIdentifier(); 171 void *Ptr = II->getFETokenInfo<void>(); 172 173 assert(Ptr && "Didn't find this decl on its identifier's chain!"); 174 175 if (isDeclPtr(Ptr)) { 176 assert(D == Ptr && "Didn't find this decl on its identifier's chain!"); 177 II->setFETokenInfo(NULL); 178 return; 179 } 180 181 return toIdDeclInfo(Ptr)->RemoveShadowed(D); 182} 183 184/// Lookup - Find the non-shadowed decl that belongs to a particular 185/// Decl::IdentifierNamespace. 186NamedDecl *IdentifierResolver::Lookup(const IdentifierInfo *II, unsigned NS) { 187 assert(II && "null param passed"); 188 void *Ptr = II->getFETokenInfo<void>(); 189 190 if (!Ptr) return NULL; 191 192 if (isDeclPtr(Ptr)) { 193 NamedDecl *D = static_cast<NamedDecl*>(Ptr); 194 return (D->getIdentifierNamespace() & NS) ? D : NULL; 195 } 196 197 IdDeclInfo *IDI = toIdDeclInfo(Ptr); 198 199 // ShadowedDecls are ordered from most shadowed to less shadowed. 200 // So we do a reverse iteration from end to begin. 201 for (IdDeclInfo::ShadowedIter SI = IDI->shadowed_end(); 202 SI != IDI->shadowed_begin(); --SI) { 203 NamedDecl *D = *(SI-1); 204 if (D->getIdentifierNamespace() & NS) 205 return D; 206 } 207 208 // we didn't find the decl. 209 return NULL; 210} 211 212/// RemoveShadowed - Remove the decl from the scope chain. 213/// The decl must already be part of the decl chain. 214void IdDeclInfo::RemoveShadowed(NamedDecl *D) { 215 assert(D && "null decl passed"); 216 assert(!ShadowedDecls.empty() && 217 "Didn't find this decl on its identifier's chain!"); 218 219 // common case 220 if (D == ShadowedDecls.back()) { 221 ShadowedDecls.pop_back(); 222 return; 223 } 224 225 for (ShadowedIter SI = ShadowedDecls.end()-1; 226 SI != ShadowedDecls.begin(); --SI) { 227 if (*(SI-1) == D) { 228 ShadowedDecls.erase(SI-1); 229 return; 230 } 231 } 232 233 assert(false && "Didn't find this decl on its identifier's chain!"); 234} 235 236/// Returns the IdDeclInfo associated to the IdentifierInfo. 237/// It creates a new IdDeclInfo if one was not created before for this id. 238IdDeclInfo &IdDeclInfoMap::operator[](IdentifierInfo *II) { 239 assert (II && "null IdentifierInfo passed"); 240 void *Ptr = II->getFETokenInfo<void>(); 241 242 if (Ptr) { 243 assert(!isDeclPtr(Ptr) && "didn't clear decl for FEToken"); 244 return *toIdDeclInfo(Ptr); 245 } 246 247 if (CurIndex == VECTOR_SIZE) { 248 // Add a IdDeclInfo vector 'pool' 249 IDIVecs.push_back(std::vector<IdDeclInfo>()); 250 // Fill the vector 251 IDIVecs.back().resize(VECTOR_SIZE); 252 CurIndex = 0; 253 } 254 IdDeclInfo *IDI = &IDIVecs.back()[CurIndex]; 255 II->setFETokenInfo(reinterpret_cast<void*>( 256 reinterpret_cast<uintptr_t>(IDI) | 0x1) 257 ); 258 ++CurIndex; 259 return *IDI; 260} 261