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 
18 using namespace clang;
19 
20 //===----------------------------------------------------------------------===//
21 // IdDeclInfoMap class
22 //===----------------------------------------------------------------------===//
23 
24 /// IdDeclInfoMap - Associates IdDeclInfos with declaration names.
25 /// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each
26 /// individual IdDeclInfo to heap.
27 class IdentifierResolver::IdDeclInfoMap {
28   static const unsigned int POOL_SIZE = 512;
29 
30   /// We use our own linked-list implementation because it is sadly
31   /// impossible to add something to a pre-C++0x STL container without
32   /// a completely unnecessary copy.
33   struct IdDeclInfoPool {
34     IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
35 
36     IdDeclInfoPool *Next;
37     IdDeclInfo Pool[POOL_SIZE];
38   };
39 
40   IdDeclInfoPool *CurPool;
41   unsigned int CurIndex;
42 
43 public:
44   IdDeclInfoMap() : CurPool(0), CurIndex(POOL_SIZE) {}
45 
46   ~IdDeclInfoMap() {
47     IdDeclInfoPool *Cur = CurPool;
48     while (IdDeclInfoPool *P = Cur) {
49       Cur = Cur->Next;
50       delete P;
51     }
52   }
53 
54   /// Returns the IdDeclInfo associated to the DeclarationName.
55   /// It creates a new IdDeclInfo if one was not created before for this id.
56   IdDeclInfo &operator[](DeclarationName Name);
57 };
58 
59 
60 //===----------------------------------------------------------------------===//
61 // IdDeclInfo Implementation
62 //===----------------------------------------------------------------------===//
63 
64 /// RemoveDecl - Remove the decl from the scope chain.
65 /// The decl must already be part of the decl chain.
66 void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
67   for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
68     if (D == *(I-1)) {
69       Decls.erase(I-1);
70       return;
71     }
72   }
73 
74   assert(0 && "Didn't find this decl on its identifier's chain!");
75 }
76 
77 bool
78 IdentifierResolver::IdDeclInfo::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
79   for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
80     if (Old == *(I-1)) {
81       *(I - 1) = New;
82       return true;
83     }
84   }
85 
86   return false;
87 }
88 
89 
90 //===----------------------------------------------------------------------===//
91 // IdentifierResolver Implementation
92 //===----------------------------------------------------------------------===//
93 
94 IdentifierResolver::IdentifierResolver(const LangOptions &langOpt)
95     : LangOpt(langOpt), IdDeclInfos(new IdDeclInfoMap) {
96 }
97 IdentifierResolver::~IdentifierResolver() {
98   delete IdDeclInfos;
99 }
100 
101 /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
102 /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
103 /// true if 'D' belongs to the given declaration context.
104 bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx,
105                                        ASTContext &Context, Scope *S) const {
106   Ctx = Ctx->getLookupContext();
107 
108   if (Ctx->isFunctionOrMethod()) {
109     // Ignore the scopes associated within transparent declaration contexts.
110     while (S->getEntity() &&
111            ((DeclContext *)S->getEntity())->isTransparentContext())
112       S = S->getParent();
113 
114     if (S->isDeclScope(Action::DeclPtrTy::make(D)))
115       return true;
116     if (LangOpt.CPlusPlus) {
117       // C++ 3.3.2p3:
118       // The name declared in a catch exception-declaration is local to the
119       // handler and shall not be redeclared in the outermost block of the
120       // handler.
121       // C++ 3.3.2p4:
122       // Names declared in the for-init-statement, and in the condition of if,
123       // while, for, and switch statements are local to the if, while, for, or
124       // switch statement (including the controlled statement), and shall not be
125       // redeclared in a subsequent condition of that statement nor in the
126       // outermost block (or, for the if statement, any of the outermost blocks)
127       // of the controlled statement.
128       //
129       assert(S->getParent() && "No TUScope?");
130       if (S->getParent()->getFlags() & Scope::ControlScope)
131         return S->getParent()->isDeclScope(Action::DeclPtrTy::make(D));
132     }
133     return false;
134   }
135 
136   return D->getDeclContext()->getLookupContext()->Equals(Ctx);
137 }
138 
139 /// AddDecl - Link the decl to its shadowed decl chain.
140 void IdentifierResolver::AddDecl(NamedDecl *D) {
141   DeclarationName Name = D->getDeclName();
142   void *Ptr = Name.getFETokenInfo<void>();
143 
144   if (!Ptr) {
145     Name.setFETokenInfo(D);
146     return;
147   }
148 
149   IdDeclInfo *IDI;
150 
151   if (isDeclPtr(Ptr)) {
152     Name.setFETokenInfo(NULL);
153     IDI = &(*IdDeclInfos)[Name];
154     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
155     IDI->AddDecl(PrevD);
156   } else
157     IDI = toIdDeclInfo(Ptr);
158 
159   IDI->AddDecl(D);
160 }
161 
162 /// RemoveDecl - Unlink the decl from its shadowed decl chain.
163 /// The decl must already be part of the decl chain.
164 void IdentifierResolver::RemoveDecl(NamedDecl *D) {
165   assert(D && "null param passed");
166   DeclarationName Name = D->getDeclName();
167   void *Ptr = Name.getFETokenInfo<void>();
168 
169   assert(Ptr && "Didn't find this decl on its identifier's chain!");
170 
171   if (isDeclPtr(Ptr)) {
172     assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
173     Name.setFETokenInfo(NULL);
174     return;
175   }
176 
177   return toIdDeclInfo(Ptr)->RemoveDecl(D);
178 }
179 
180 bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
181   assert(Old->getDeclName() == New->getDeclName() &&
182          "Cannot replace a decl with another decl of a different name");
183 
184   DeclarationName Name = Old->getDeclName();
185   void *Ptr = Name.getFETokenInfo<void>();
186 
187   if (!Ptr)
188     return false;
189 
190   if (isDeclPtr(Ptr)) {
191     if (Ptr == Old) {
192       Name.setFETokenInfo(New);
193       return true;
194     }
195     return false;
196   }
197 
198   return toIdDeclInfo(Ptr)->ReplaceDecl(Old, New);
199 }
200 
201 /// begin - Returns an iterator for decls with name 'Name'.
202 IdentifierResolver::iterator
203 IdentifierResolver::begin(DeclarationName Name) {
204   void *Ptr = Name.getFETokenInfo<void>();
205   if (!Ptr) return end();
206 
207   if (isDeclPtr(Ptr))
208     return iterator(static_cast<NamedDecl*>(Ptr));
209 
210   IdDeclInfo *IDI = toIdDeclInfo(Ptr);
211 
212   IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
213   if (I != IDI->decls_begin())
214     return iterator(I-1);
215   // No decls found.
216   return end();
217 }
218 
219 void IdentifierResolver::AddDeclToIdentifierChain(IdentifierInfo *II,
220                                                   NamedDecl *D) {
221   void *Ptr = II->getFETokenInfo<void>();
222 
223   if (!Ptr) {
224     II->setFETokenInfo(D);
225     return;
226   }
227 
228   IdDeclInfo *IDI;
229 
230   if (isDeclPtr(Ptr)) {
231     II->setFETokenInfo(NULL);
232     IDI = &(*IdDeclInfos)[II];
233     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
234     IDI->AddDecl(PrevD);
235   } else
236     IDI = toIdDeclInfo(Ptr);
237 
238   IDI->AddDecl(D);
239 }
240 
241 //===----------------------------------------------------------------------===//
242 // IdDeclInfoMap Implementation
243 //===----------------------------------------------------------------------===//
244 
245 /// Returns the IdDeclInfo associated to the DeclarationName.
246 /// It creates a new IdDeclInfo if one was not created before for this id.
247 IdentifierResolver::IdDeclInfo &
248 IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
249   void *Ptr = Name.getFETokenInfo<void>();
250 
251   if (Ptr) return *toIdDeclInfo(Ptr);
252 
253   if (CurIndex == POOL_SIZE) {
254     CurPool = new IdDeclInfoPool(CurPool);
255     CurIndex = 0;
256   }
257   IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
258   Name.setFETokenInfo(reinterpret_cast<void*>(
259                               reinterpret_cast<uintptr_t>(IDI) | 0x1)
260                                                                      );
261   ++CurIndex;
262   return *IDI;
263 }
264