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