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/AST/DeclObjC.h"
19#include "clang/Basic/LangOptions.h"
20#include "clang/Lex/ExternalPreprocessorSource.h"
21#include "clang/Lex/Preprocessor.h"
22
23using namespace clang;
24
25//===----------------------------------------------------------------------===//
26// IdDeclInfoMap class
27//===----------------------------------------------------------------------===//
28
29/// IdDeclInfoMap - Associates IdDeclInfos with declaration names.
30/// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each
31/// individual IdDeclInfo to heap.
32class IdentifierResolver::IdDeclInfoMap {
33  static const unsigned int POOL_SIZE = 512;
34
35  /// We use our own linked-list implementation because it is sadly
36  /// impossible to add something to a pre-C++0x STL container without
37  /// a completely unnecessary copy.
38  struct IdDeclInfoPool {
39    IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
40
41    IdDeclInfoPool *Next;
42    IdDeclInfo Pool[POOL_SIZE];
43  };
44
45  IdDeclInfoPool *CurPool;
46  unsigned int CurIndex;
47
48public:
49  IdDeclInfoMap() : CurPool(0), CurIndex(POOL_SIZE) {}
50
51  ~IdDeclInfoMap() {
52    IdDeclInfoPool *Cur = CurPool;
53    while (IdDeclInfoPool *P = Cur) {
54      Cur = Cur->Next;
55      delete P;
56    }
57  }
58
59  /// Returns the IdDeclInfo associated to the DeclarationName.
60  /// It creates a new IdDeclInfo if one was not created before for this id.
61  IdDeclInfo &operator[](DeclarationName Name);
62};
63
64
65//===----------------------------------------------------------------------===//
66// IdDeclInfo Implementation
67//===----------------------------------------------------------------------===//
68
69/// RemoveDecl - Remove the decl from the scope chain.
70/// The decl must already be part of the decl chain.
71void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
72  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
73    if (D == *(I-1)) {
74      Decls.erase(I-1);
75      return;
76    }
77  }
78
79  llvm_unreachable("Didn't find this decl on its identifier's chain!");
80}
81
82bool
83IdentifierResolver::IdDeclInfo::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
84  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
85    if (Old == *(I-1)) {
86      *(I - 1) = New;
87      return true;
88    }
89  }
90
91  return false;
92}
93
94
95//===----------------------------------------------------------------------===//
96// IdentifierResolver Implementation
97//===----------------------------------------------------------------------===//
98
99IdentifierResolver::IdentifierResolver(Preprocessor &PP)
100  : LangOpt(PP.getLangOpts()), PP(PP),
101    IdDeclInfos(new IdDeclInfoMap) {
102}
103
104IdentifierResolver::~IdentifierResolver() {
105  delete IdDeclInfos;
106}
107
108/// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
109/// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
110/// true if 'D' belongs to the given declaration context.
111bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx,
112                                       ASTContext &Context, Scope *S,
113                             bool ExplicitInstantiationOrSpecialization) const {
114  Ctx = Ctx->getRedeclContext();
115
116  if (Ctx->isFunctionOrMethod() || S->isFunctionPrototypeScope()) {
117    // Ignore the scopes associated within transparent declaration contexts.
118    while (S->getEntity() &&
119           ((DeclContext *)S->getEntity())->isTransparentContext())
120      S = S->getParent();
121
122    if (S->isDeclScope(D))
123      return true;
124    if (LangOpt.CPlusPlus) {
125      // C++ 3.3.2p3:
126      // The name declared in a catch exception-declaration is local to the
127      // handler and shall not be redeclared in the outermost block of the
128      // handler.
129      // C++ 3.3.2p4:
130      // Names declared in the for-init-statement, and in the condition of if,
131      // while, for, and switch statements are local to the if, while, for, or
132      // switch statement (including the controlled statement), and shall not be
133      // redeclared in a subsequent condition of that statement nor in the
134      // outermost block (or, for the if statement, any of the outermost blocks)
135      // of the controlled statement.
136      //
137      assert(S->getParent() && "No TUScope?");
138      if (S->getParent()->getFlags() & Scope::ControlScope)
139        return S->getParent()->isDeclScope(D);
140    }
141    return false;
142  }
143
144  DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
145  return ExplicitInstantiationOrSpecialization
146           ? Ctx->InEnclosingNamespaceSetOf(DCtx)
147           : Ctx->Equals(DCtx);
148}
149
150/// AddDecl - Link the decl to its shadowed decl chain.
151void IdentifierResolver::AddDecl(NamedDecl *D) {
152  DeclarationName Name = D->getDeclName();
153  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
154    updatingIdentifier(*II);
155
156  void *Ptr = Name.getFETokenInfo<void>();
157
158  if (!Ptr) {
159    Name.setFETokenInfo(D);
160    return;
161  }
162
163  IdDeclInfo *IDI;
164
165  if (isDeclPtr(Ptr)) {
166    Name.setFETokenInfo(NULL);
167    IDI = &(*IdDeclInfos)[Name];
168    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
169    IDI->AddDecl(PrevD);
170  } else
171    IDI = toIdDeclInfo(Ptr);
172
173  IDI->AddDecl(D);
174}
175
176void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
177  DeclarationName Name = D->getDeclName();
178  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
179    updatingIdentifier(*II);
180
181  void *Ptr = Name.getFETokenInfo<void>();
182
183  if (!Ptr) {
184    AddDecl(D);
185    return;
186  }
187
188  if (isDeclPtr(Ptr)) {
189    // We only have a single declaration: insert before or after it,
190    // as appropriate.
191    if (Pos == iterator()) {
192      // Add the new declaration before the existing declaration.
193      NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
194      RemoveDecl(PrevD);
195      AddDecl(D);
196      AddDecl(PrevD);
197    } else {
198      // Add new declaration after the existing declaration.
199      AddDecl(D);
200    }
201
202    return;
203  }
204
205  // General case: insert the declaration at the appropriate point in the
206  // list, which already has at least two elements.
207  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
208  if (Pos.isIterator()) {
209    IDI->InsertDecl(Pos.getIterator() + 1, D);
210  } else
211    IDI->InsertDecl(IDI->decls_begin(), D);
212}
213
214/// RemoveDecl - Unlink the decl from its shadowed decl chain.
215/// The decl must already be part of the decl chain.
216void IdentifierResolver::RemoveDecl(NamedDecl *D) {
217  assert(D && "null param passed");
218  DeclarationName Name = D->getDeclName();
219  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
220    updatingIdentifier(*II);
221
222  void *Ptr = Name.getFETokenInfo<void>();
223
224  assert(Ptr && "Didn't find this decl on its identifier's chain!");
225
226  if (isDeclPtr(Ptr)) {
227    assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
228    Name.setFETokenInfo(NULL);
229    return;
230  }
231
232  return toIdDeclInfo(Ptr)->RemoveDecl(D);
233}
234
235bool IdentifierResolver::ReplaceDecl(NamedDecl *Old, NamedDecl *New) {
236  assert(Old->getDeclName() == New->getDeclName() &&
237         "Cannot replace a decl with another decl of a different name");
238
239  DeclarationName Name = Old->getDeclName();
240  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
241    updatingIdentifier(*II);
242
243  void *Ptr = Name.getFETokenInfo<void>();
244
245  if (!Ptr)
246    return false;
247
248  if (isDeclPtr(Ptr)) {
249    if (Ptr == Old) {
250      Name.setFETokenInfo(New);
251      return true;
252    }
253    return false;
254  }
255
256  return toIdDeclInfo(Ptr)->ReplaceDecl(Old, New);
257}
258
259/// begin - Returns an iterator for decls with name 'Name'.
260IdentifierResolver::iterator
261IdentifierResolver::begin(DeclarationName Name) {
262  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
263    readingIdentifier(*II);
264
265  void *Ptr = Name.getFETokenInfo<void>();
266  if (!Ptr) return end();
267
268  if (isDeclPtr(Ptr))
269    return iterator(static_cast<NamedDecl*>(Ptr));
270
271  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
272
273  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
274  if (I != IDI->decls_begin())
275    return iterator(I-1);
276  // No decls found.
277  return end();
278}
279
280namespace {
281  enum DeclMatchKind {
282    DMK_Different,
283    DMK_Replace,
284    DMK_Ignore
285  };
286}
287
288/// \brief Compare two declarations to see whether they are different or,
289/// if they are the same, whether the new declaration should replace the
290/// existing declaration.
291static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
292  // If the declarations are identical, ignore the new one.
293  if (Existing == New)
294    return DMK_Ignore;
295
296  // If the declarations have different kinds, they're obviously different.
297  if (Existing->getKind() != New->getKind())
298    return DMK_Different;
299
300  // If the declarations are redeclarations of each other, keep the newest one.
301  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
302    // If the existing declaration is somewhere in the previous declaration
303    // chain of the new declaration, then prefer the new declaration.
304    for (Decl::redecl_iterator RD = New->redecls_begin(),
305                            RDEnd = New->redecls_end();
306         RD != RDEnd; ++RD) {
307      if (*RD == Existing)
308        return DMK_Replace;
309
310      if (RD->isCanonicalDecl())
311        break;
312    }
313
314    return DMK_Ignore;
315  }
316
317  return DMK_Different;
318}
319
320bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
321  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
322    readingIdentifier(*II);
323
324  void *Ptr = Name.getFETokenInfo<void>();
325
326  if (!Ptr) {
327    Name.setFETokenInfo(D);
328    return true;
329  }
330
331  IdDeclInfo *IDI;
332
333  if (isDeclPtr(Ptr)) {
334    NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
335
336    switch (compareDeclarations(PrevD, D)) {
337    case DMK_Different:
338      break;
339
340    case DMK_Ignore:
341      return false;
342
343    case DMK_Replace:
344      Name.setFETokenInfo(D);
345      return true;
346    }
347
348    Name.setFETokenInfo(NULL);
349    IDI = &(*IdDeclInfos)[Name];
350
351    // If the existing declaration is not visible in translation unit scope,
352    // then add the new top-level declaration first.
353    if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
354      IDI->AddDecl(D);
355      IDI->AddDecl(PrevD);
356    } else {
357      IDI->AddDecl(PrevD);
358      IDI->AddDecl(D);
359    }
360    return true;
361  }
362
363  IDI = toIdDeclInfo(Ptr);
364
365  // See whether this declaration is identical to any existing declarations.
366  // If not, find the right place to insert it.
367  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
368                                  IEnd = IDI->decls_end();
369       I != IEnd; ++I) {
370
371    switch (compareDeclarations(*I, D)) {
372    case DMK_Different:
373      break;
374
375    case DMK_Ignore:
376      return false;
377
378    case DMK_Replace:
379      *I = D;
380      return true;
381    }
382
383    if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
384      // We've found a declaration that is not visible from the translation
385      // unit (it's in an inner scope). Insert our declaration here.
386      IDI->InsertDecl(I, D);
387      return true;
388    }
389  }
390
391  // Add the declaration to the end.
392  IDI->AddDecl(D);
393  return true;
394}
395
396void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
397  if (II.isOutOfDate())
398    PP.getExternalSource()->updateOutOfDateIdentifier(II);
399}
400
401void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
402  if (II.isOutOfDate())
403    PP.getExternalSource()->updateOutOfDateIdentifier(II);
404
405  if (II.isFromAST())
406    II.setChangedSinceDeserialization();
407}
408
409//===----------------------------------------------------------------------===//
410// IdDeclInfoMap Implementation
411//===----------------------------------------------------------------------===//
412
413/// Returns the IdDeclInfo associated to the DeclarationName.
414/// It creates a new IdDeclInfo if one was not created before for this id.
415IdentifierResolver::IdDeclInfo &
416IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
417  void *Ptr = Name.getFETokenInfo<void>();
418
419  if (Ptr) return *toIdDeclInfo(Ptr);
420
421  if (CurIndex == POOL_SIZE) {
422    CurPool = new IdDeclInfoPool(CurPool);
423    CurIndex = 0;
424  }
425  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
426  Name.setFETokenInfo(reinterpret_cast<void*>(
427                              reinterpret_cast<uintptr_t>(IDI) | 0x1)
428                                                                     );
429  ++CurIndex;
430  return *IDI;
431}
432
433void IdentifierResolver::iterator::incrementSlowCase() {
434  NamedDecl *D = **this;
435  void *InfoPtr = D->getDeclName().getFETokenInfo<void>();
436  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
437  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
438
439  BaseIter I = getIterator();
440  if (I != Info->decls_begin())
441    *this = iterator(I-1);
442  else // No more decls.
443    *this = iterator();
444}
445