clang  6.0.0svn
IdentifierResolver.cpp
Go to the documentation of this file.
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 
16 #include "clang/AST/Decl.h"
19 #include "clang/Lex/Preprocessor.h"
20 #include "clang/Sema/Scope.h"
21 
22 using namespace clang;
23 
24 //===----------------------------------------------------------------------===//
25 // IdDeclInfoMap class
26 //===----------------------------------------------------------------------===//
27 
28 /// IdDeclInfoMap - Associates IdDeclInfos with declaration names.
29 /// Allocates 'pools' (vectors of IdDeclInfos) to avoid allocating each
30 /// individual IdDeclInfo to heap.
32  static const unsigned int POOL_SIZE = 512;
33 
34  /// We use our own linked-list implementation because it is sadly
35  /// impossible to add something to a pre-C++0x STL container without
36  /// a completely unnecessary copy.
37  struct IdDeclInfoPool {
38  IdDeclInfoPool(IdDeclInfoPool *Next) : Next(Next) {}
39 
40  IdDeclInfoPool *Next;
41  IdDeclInfo Pool[POOL_SIZE];
42  };
43 
44  IdDeclInfoPool *CurPool;
45  unsigned int CurIndex;
46 
47 public:
48  IdDeclInfoMap() : CurPool(nullptr), CurIndex(POOL_SIZE) {}
49 
51  IdDeclInfoPool *Cur = CurPool;
52  while (IdDeclInfoPool *P = Cur) {
53  Cur = Cur->Next;
54  delete P;
55  }
56  }
57 
58  /// Returns the IdDeclInfo associated to the DeclarationName.
59  /// It creates a new IdDeclInfo if one was not created before for this id.
60  IdDeclInfo &operator[](DeclarationName Name);
61 };
62 
63 
64 //===----------------------------------------------------------------------===//
65 // IdDeclInfo Implementation
66 //===----------------------------------------------------------------------===//
67 
68 /// RemoveDecl - Remove the decl from the scope chain.
69 /// The decl must already be part of the decl chain.
70 void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
71  for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
72  if (D == *(I-1)) {
73  Decls.erase(I-1);
74  return;
75  }
76  }
77 
78  llvm_unreachable("Didn't find this decl on its identifier's chain!");
79 }
80 
81 //===----------------------------------------------------------------------===//
82 // IdentifierResolver Implementation
83 //===----------------------------------------------------------------------===//
84 
86  : LangOpt(PP.getLangOpts()), PP(PP),
87  IdDeclInfos(new IdDeclInfoMap) {
88 }
89 
91  delete IdDeclInfos;
92 }
93 
94 /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
95 /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
96 /// true if 'D' belongs to the given declaration context.
98  bool AllowInlineNamespace) const {
99  Ctx = Ctx->getRedeclContext();
100 
101  if (Ctx->isFunctionOrMethod() || (S && S->isFunctionPrototypeScope())) {
102  // Ignore the scopes associated within transparent declaration contexts.
103  while (S->getEntity() && S->getEntity()->isTransparentContext())
104  S = S->getParent();
105 
106  if (S->isDeclScope(D))
107  return true;
108  if (LangOpt.CPlusPlus) {
109  // C++ 3.3.2p3:
110  // The name declared in a catch exception-declaration is local to the
111  // handler and shall not be redeclared in the outermost block of the
112  // handler.
113  // C++ 3.3.2p4:
114  // Names declared in the for-init-statement, and in the condition of if,
115  // while, for, and switch statements are local to the if, while, for, or
116  // switch statement (including the controlled statement), and shall not be
117  // redeclared in a subsequent condition of that statement nor in the
118  // outermost block (or, for the if statement, any of the outermost blocks)
119  // of the controlled statement.
120  //
121  assert(S->getParent() && "No TUScope?");
122  if (S->getParent()->getFlags() & Scope::ControlScope) {
123  S = S->getParent();
124  if (S->isDeclScope(D))
125  return true;
126  }
127  if (S->getFlags() & Scope::FnTryCatchScope)
128  return S->getParent()->isDeclScope(D);
129  }
130  return false;
131  }
132 
133  // FIXME: If D is a local extern declaration, this check doesn't make sense;
134  // we should be checking its lexical context instead in that case, because
135  // that is its scope.
137  return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
138  : Ctx->Equals(DCtx);
139 }
140 
141 /// AddDecl - Link the decl to its shadowed decl chain.
143  DeclarationName Name = D->getDeclName();
144  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
145  updatingIdentifier(*II);
146 
147  void *Ptr = Name.getFETokenInfo<void>();
148 
149  if (!Ptr) {
150  Name.setFETokenInfo(D);
151  return;
152  }
153 
154  IdDeclInfo *IDI;
155 
156  if (isDeclPtr(Ptr)) {
157  Name.setFETokenInfo(nullptr);
158  IDI = &(*IdDeclInfos)[Name];
159  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
160  IDI->AddDecl(PrevD);
161  } else
162  IDI = toIdDeclInfo(Ptr);
163 
164  IDI->AddDecl(D);
165 }
166 
168  DeclarationName Name = D->getDeclName();
169  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
170  updatingIdentifier(*II);
171 
172  void *Ptr = Name.getFETokenInfo<void>();
173 
174  if (!Ptr) {
175  AddDecl(D);
176  return;
177  }
178 
179  if (isDeclPtr(Ptr)) {
180  // We only have a single declaration: insert before or after it,
181  // as appropriate.
182  if (Pos == iterator()) {
183  // Add the new declaration before the existing declaration.
184  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
185  RemoveDecl(PrevD);
186  AddDecl(D);
187  AddDecl(PrevD);
188  } else {
189  // Add new declaration after the existing declaration.
190  AddDecl(D);
191  }
192 
193  return;
194  }
195 
196  // General case: insert the declaration at the appropriate point in the
197  // list, which already has at least two elements.
198  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
199  if (Pos.isIterator()) {
200  IDI->InsertDecl(Pos.getIterator() + 1, D);
201  } else
202  IDI->InsertDecl(IDI->decls_begin(), D);
203 }
204 
205 /// RemoveDecl - Unlink the decl from its shadowed decl chain.
206 /// The decl must already be part of the decl chain.
208  assert(D && "null param passed");
209  DeclarationName Name = D->getDeclName();
210  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
211  updatingIdentifier(*II);
212 
213  void *Ptr = Name.getFETokenInfo<void>();
214 
215  assert(Ptr && "Didn't find this decl on its identifier's chain!");
216 
217  if (isDeclPtr(Ptr)) {
218  assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
219  Name.setFETokenInfo(nullptr);
220  return;
221  }
222 
223  return toIdDeclInfo(Ptr)->RemoveDecl(D);
224 }
225 
226 /// begin - Returns an iterator for decls with name 'Name'.
229  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
230  readingIdentifier(*II);
231 
232  void *Ptr = Name.getFETokenInfo<void>();
233  if (!Ptr) return end();
234 
235  if (isDeclPtr(Ptr))
236  return iterator(static_cast<NamedDecl*>(Ptr));
237 
238  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
239 
240  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
241  if (I != IDI->decls_begin())
242  return iterator(I-1);
243  // No decls found.
244  return end();
245 }
246 
247 namespace {
249  DMK_Different,
250  DMK_Replace,
251  DMK_Ignore
252  };
253 }
254 
255 /// \brief Compare two declarations to see whether they are different or,
256 /// if they are the same, whether the new declaration should replace the
257 /// existing declaration.
259  // If the declarations are identical, ignore the new one.
260  if (Existing == New)
261  return DMK_Ignore;
262 
263  // If the declarations have different kinds, they're obviously different.
264  if (Existing->getKind() != New->getKind())
265  return DMK_Different;
266 
267  // If the declarations are redeclarations of each other, keep the newest one.
268  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
269  // If we're adding an imported declaration, don't replace another imported
270  // declaration.
271  if (Existing->isFromASTFile() && New->isFromASTFile())
272  return DMK_Different;
273 
274  // If either of these is the most recent declaration, use it.
275  Decl *MostRecent = Existing->getMostRecentDecl();
276  if (Existing == MostRecent)
277  return DMK_Ignore;
278 
279  if (New == MostRecent)
280  return DMK_Replace;
281 
282  // If the existing declaration is somewhere in the previous declaration
283  // chain of the new declaration, then prefer the new declaration.
284  for (auto RD : New->redecls()) {
285  if (RD == Existing)
286  return DMK_Replace;
287 
288  if (RD->isCanonicalDecl())
289  break;
290  }
291 
292  return DMK_Ignore;
293  }
294 
295  return DMK_Different;
296 }
297 
299  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
300  readingIdentifier(*II);
301 
302  void *Ptr = Name.getFETokenInfo<void>();
303 
304  if (!Ptr) {
305  Name.setFETokenInfo(D);
306  return true;
307  }
308 
309  IdDeclInfo *IDI;
310 
311  if (isDeclPtr(Ptr)) {
312  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
313 
314  switch (compareDeclarations(PrevD, D)) {
315  case DMK_Different:
316  break;
317 
318  case DMK_Ignore:
319  return false;
320 
321  case DMK_Replace:
322  Name.setFETokenInfo(D);
323  return true;
324  }
325 
326  Name.setFETokenInfo(nullptr);
327  IDI = &(*IdDeclInfos)[Name];
328 
329  // If the existing declaration is not visible in translation unit scope,
330  // then add the new top-level declaration first.
331  if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
332  IDI->AddDecl(D);
333  IDI->AddDecl(PrevD);
334  } else {
335  IDI->AddDecl(PrevD);
336  IDI->AddDecl(D);
337  }
338  return true;
339  }
340 
341  IDI = toIdDeclInfo(Ptr);
342 
343  // See whether this declaration is identical to any existing declarations.
344  // If not, find the right place to insert it.
345  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
346  IEnd = IDI->decls_end();
347  I != IEnd; ++I) {
348 
349  switch (compareDeclarations(*I, D)) {
350  case DMK_Different:
351  break;
352 
353  case DMK_Ignore:
354  return false;
355 
356  case DMK_Replace:
357  *I = D;
358  return true;
359  }
360 
361  if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
362  // We've found a declaration that is not visible from the translation
363  // unit (it's in an inner scope). Insert our declaration here.
364  IDI->InsertDecl(I, D);
365  return true;
366  }
367  }
368 
369  // Add the declaration to the end.
370  IDI->AddDecl(D);
371  return true;
372 }
373 
374 void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
375  if (II.isOutOfDate())
377 }
378 
379 void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
380  if (II.isOutOfDate())
382 
383  if (II.isFromAST())
385 }
386 
387 //===----------------------------------------------------------------------===//
388 // IdDeclInfoMap Implementation
389 //===----------------------------------------------------------------------===//
390 
391 /// Returns the IdDeclInfo associated to the DeclarationName.
392 /// It creates a new IdDeclInfo if one was not created before for this id.
393 IdentifierResolver::IdDeclInfo &
395  void *Ptr = Name.getFETokenInfo<void>();
396 
397  if (Ptr) return *toIdDeclInfo(Ptr);
398 
399  if (CurIndex == POOL_SIZE) {
400  CurPool = new IdDeclInfoPool(CurPool);
401  CurIndex = 0;
402  }
403  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
404  Name.setFETokenInfo(reinterpret_cast<void*>(
405  reinterpret_cast<uintptr_t>(IDI) | 0x1)
406  );
407  ++CurIndex;
408  return *IDI;
409 }
410 
412  NamedDecl *D = **this;
413  void *InfoPtr = D->getDeclName().getFETokenInfo<void>();
414  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
415  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
416 
417  BaseIter I = getIterator();
418  if (I != Info->decls_begin())
419  *this = iterator(I-1);
420  else // No more decls.
421  *this = iterator();
422 }
bool tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name)
Try to add the given declaration to the top level scope, if it (or a redeclaration of it) hasn&#39;t alre...
bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S=nullptr, bool AllowInlineNamespace=false) const
isDeclInScope - If &#39;Ctx&#39; is a function/method, isDeclInScope returns true if &#39;D&#39; is in Scope &#39;S&#39;...
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
StringRef P
bool isOutOfDate() const
Determine whether the information for this identifier is out of date with respect to the external sou...
bool isFromAST() const
Return true if the identifier in its current state was loaded from an AST file.
iterator begin(DeclarationName Name)
begin - Returns an iterator for decls with the name &#39;Name&#39;.
DeclarationName getDeclName() const
getDeclName - Get the actual, stored name of the declaration, which may be a special name...
Definition: Decl.h:291
One of these records is kept for each identifier that is lexed.
bool Equals(const DeclContext *DC) const
Determine whether this declaration context is equivalent to the declaration context DC...
Definition: DeclBase.h:1451
iterator end()
end - Returns an iterator that has &#39;finished&#39;.
The controlling scope in a if/switch/while/for statement.
Definition: Scope.h:61
bool isFunctionPrototypeScope() const
isFunctionPrototypeScope - Return true if this scope is a function prototype scope.
Definition: Scope.h:377
void RemoveDecl(NamedDecl *D)
RemoveDecl - Unlink the decl from its shadowed decl chain.
Scope - A scope is a transient data structure that is used while parsing the program.
Definition: Scope.h:39
IdDeclInfoMap - Associates IdDeclInfos with declaration names.
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:865
unsigned getFlags() const
getFlags - Return the flags for this scope.
Definition: Scope.h:216
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New)
Compare two declarations to see whether they are different or, if they are the same, whether the new declaration should replace the existing declaration.
Defines the clang::LangOptions interface.
bool isDeclScope(Decl *D)
isDeclScope - Return true if this is the scope that the specified decl is declared in...
Definition: Scope.h:315
DeclContext * getEntity() const
Definition: Scope.h:319
Defines the clang::Preprocessor interface.
bool InEnclosingNamespaceSetOf(const DeclContext *NS) const
Test if this context is part of the enclosing namespace set of the context NS, as defined in C++0x [n...
Definition: DeclBase.cpp:1675
DeclContext * getDeclContext()
Definition: DeclBase.h:425
IdentifierInfo * getAsIdentifierInfo() const
getAsIdentifierInfo - Retrieve the IdentifierInfo * stored in this declaration name, or NULL if this declaration name isn&#39;t a simple identifier.
bool isFunctionOrMethod() const
Definition: DeclBase.h:1380
T * getFETokenInfo() const
getFETokenInfo/setFETokenInfo - The language front-end is allowed to associate arbitrary metadata wit...
ExternalPreprocessorSource * getExternalSource() const
Definition: Preprocessor.h:833
void setFETokenInfoChangedSinceDeserialization()
Note that the frontend token information for this identifier has changed since it was loaded from an ...
IdDeclInfo & operator[](DeclarationName Name)
Returns the IdDeclInfo associated to the DeclarationName.
bool isFromASTFile() const
Determine whether this declaration came from an AST file (such as a precompiled header or module) rat...
Definition: DeclBase.h:694
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:936
Dataflow Directional Tag Classes.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1252
IdentifierResolver(Preprocessor &PP)
const Scope * getParent() const
getParent - Return the scope that this is nested in.
Definition: Scope.h:224
DeclarationName - The name of a declaration.
Kind getKind() const
Definition: DeclBase.h:419
void InsertDeclAfter(iterator Pos, NamedDecl *D)
Insert the given declaration after the given iterator position.
This is the scope for a function-level C++ try or catch scope.
Definition: Scope.h:103
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
virtual void updateOutOfDateIdentifier(IdentifierInfo &II)=0
Update an out-of-date identifier.
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1648
IdDeclInfo::DeclsTy::iterator BaseIter
NamedDecl * getMostRecentDecl()
Definition: Decl.h:437
NamedDecl - This represents a decl with a name.
Definition: Decl.h:245
bool isTranslationUnit() const
Definition: DeclBase.h:1401
iterator - Iterate over the decls of a specified declaration name.
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:127
bool isTransparentContext() const
isTransparentContext - Determines whether this context is a "transparent" context, meaning that the members declared in this context are semantically declared in the nearest enclosing non-transparent (opaque) context but are lexically declared in this context.
Definition: DeclBase.cpp:1058