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