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