IdentifierResolver.cpp revision 321f278db3405268e8644eb75f4fcf8900e0d09c 
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 <list>
19#include <vector>
20
21using namespace clang;
22
23namespace {
24
25class IdDeclInfo;
26
27/// Identifier's FETokenInfo contains a Decl pointer if lower bit == 0.
28static inline bool isDeclPtr(void *Ptr) {
29  return (reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 0;
30}
31
32/// Identifier's FETokenInfo contains a IdDeclInfo pointer if lower bit == 1.
33static inline IdDeclInfo *toIdDeclInfo(void *Ptr) {
34  return reinterpret_cast<IdDeclInfo*>(
35                  reinterpret_cast<uintptr_t>(Ptr) & ~0x1
36                                                          );
37}
38
39
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.
44class IdDeclInfo {
45  typedef llvm::SmallVector<NamedDecl *, 2> ShadowedTy;
46  ShadowedTy ShadowedDecls;
47
48public:
49  typedef ShadowedTy::iterator ShadowedIter;
50
51  inline ShadowedIter shadowed_begin() { return ShadowedDecls.begin(); }
52  inline ShadowedIter shadowed_end() { return ShadowedDecls.end(); }
53
54  /// Add a decl in the scope chain.
55  void PushShadowed(NamedDecl *D) {
56    assert(D && "Decl null");
57    ShadowedDecls.push_back(D);
58  }
59
60  /// Add the decl at the top of scope chain.
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
71} // end anonymous namespace
72
73
74/// IdDeclInfoMap - Associates IdDeclInfos with Identifiers.
75/// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each
76/// individual IdDeclInfo to heap.
77class IdentifierResolver::IdDeclInfoMap {
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;
82  unsigned int CurIndex;
83
84public:
85  IdDeclInfoMap() : CurIndex(VECTOR_SIZE) {}
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
93IdentifierResolver::IdentifierResolver() : IdDeclInfos(*new IdDeclInfoMap) {}
94IdentifierResolver::~IdentifierResolver() { delete &IdDeclInfos; }
95
96/// AddDecl - Link the decl to its shadowed decl chain.
97void 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
119/// AddGlobalDecl - Link the decl at the top of the shadowed decl chain.
120void 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
142/// RemoveDecl - Unlink the decl from its shadowed decl chain.
143/// The decl must already be part of the decl chain.
144void 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.
162NamedDecl *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.
191void IdDeclInfo::RemoveShadowed(NamedDecl *D) {
192  assert(D && "null decl passed");
193  assert(ShadowedDecls.size() > 0 &&
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.
215IdDeclInfo &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
224  if (CurIndex == VECTOR_SIZE) {
225    // Add a IdDeclInfo vector 'pool'
226    IDIVecs.resize(IDIVecs.size() + 1);
227    // Fill the vector
228    IDIVecs.back().resize(VECTOR_SIZE);
229    CurIndex = 0;
230  }
231  IdDeclInfo *IDI = &IDIVecs.back()[CurIndex];
232  II->setFETokenInfo(reinterpret_cast<void*>(
233                              reinterpret_cast<uintptr_t>(IDI) | 0x1)
234                                                                     );
235  ++CurIndex;
236  return *IDI;
237}
238