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