clang  15.0.0git
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 the current decl is in a lambda, we shouldn't consider this is a
125  // redefinition as lambda has its own scope.
126  if (S->getParent()->isControlScope() && !S->isFunctionScope()) {
127  S = S->getParent();
128  if (S->isDeclScope(D))
129  return true;
130  }
131  if (S->isFnTryCatchScope())
132  return S->getParent()->isDeclScope(D);
133  }
134  return false;
135  }
136 
137  // FIXME: If D is a local extern declaration, this check doesn't make sense;
138  // we should be checking its lexical context instead in that case, because
139  // that is its scope.
141  return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
142  : Ctx->Equals(DCtx);
143 }
144 
145 /// AddDecl - Link the decl to its shadowed decl chain.
147  DeclarationName Name = D->getDeclName();
148  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
149  updatingIdentifier(*II);
150 
151  void *Ptr = Name.getFETokenInfo();
152 
153  if (!Ptr) {
154  Name.setFETokenInfo(D);
155  return;
156  }
157 
158  IdDeclInfo *IDI;
159 
160  if (isDeclPtr(Ptr)) {
161  Name.setFETokenInfo(nullptr);
162  IDI = &(*IdDeclInfos)[Name];
163  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
164  IDI->AddDecl(PrevD);
165  } else
166  IDI = toIdDeclInfo(Ptr);
167 
168  IDI->AddDecl(D);
169 }
170 
172  DeclarationName Name = D->getDeclName();
173  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
174  updatingIdentifier(*II);
175 
176  void *Ptr = Name.getFETokenInfo();
177 
178  if (!Ptr) {
179  AddDecl(D);
180  return;
181  }
182 
183  if (isDeclPtr(Ptr)) {
184  // We only have a single declaration: insert before or after it,
185  // as appropriate.
186  if (Pos == iterator()) {
187  // Add the new declaration before the existing declaration.
188  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
189  RemoveDecl(PrevD);
190  AddDecl(D);
191  AddDecl(PrevD);
192  } else {
193  // Add new declaration after the existing declaration.
194  AddDecl(D);
195  }
196 
197  return;
198  }
199 
200  // General case: insert the declaration at the appropriate point in the
201  // list, which already has at least two elements.
202  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
203  if (Pos.isIterator()) {
204  IDI->InsertDecl(Pos.getIterator() + 1, D);
205  } else
206  IDI->InsertDecl(IDI->decls_begin(), D);
207 }
208 
209 /// RemoveDecl - Unlink the decl from its shadowed decl chain.
210 /// The decl must already be part of the decl chain.
212  assert(D && "null param passed");
213  DeclarationName Name = D->getDeclName();
214  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
215  updatingIdentifier(*II);
216 
217  void *Ptr = Name.getFETokenInfo();
218 
219  assert(Ptr && "Didn't find this decl on its identifier's chain!");
220 
221  if (isDeclPtr(Ptr)) {
222  assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
223  Name.setFETokenInfo(nullptr);
224  return;
225  }
226 
227  return toIdDeclInfo(Ptr)->RemoveDecl(D);
228 }
229 
230 /// begin - Returns an iterator for decls with name 'Name'.
233  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
234  readingIdentifier(*II);
235 
236  void *Ptr = Name.getFETokenInfo();
237  if (!Ptr) return end();
238 
239  if (isDeclPtr(Ptr))
240  return iterator(static_cast<NamedDecl*>(Ptr));
241 
242  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
243 
244  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
245  if (I != IDI->decls_begin())
246  return iterator(I-1);
247  // No decls found.
248  return end();
249 }
250 
251 namespace {
252 
253 enum DeclMatchKind {
254  DMK_Different,
255  DMK_Replace,
256  DMK_Ignore
257 };
258 
259 } // namespace
260 
261 /// Compare two declarations to see whether they are different or,
262 /// if they are the same, whether the new declaration should replace the
263 /// existing declaration.
264 static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
265  // If the declarations are identical, ignore the new one.
266  if (Existing == New)
267  return DMK_Ignore;
268 
269  // If the declarations have different kinds, they're obviously different.
270  if (Existing->getKind() != New->getKind())
271  return DMK_Different;
272 
273  // If the declarations are redeclarations of each other, keep the newest one.
274  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
275  // If we're adding an imported declaration, don't replace another imported
276  // declaration.
277  if (Existing->isFromASTFile() && New->isFromASTFile())
278  return DMK_Different;
279 
280  // If either of these is the most recent declaration, use it.
281  Decl *MostRecent = Existing->getMostRecentDecl();
282  if (Existing == MostRecent)
283  return DMK_Ignore;
284 
285  if (New == MostRecent)
286  return DMK_Replace;
287 
288  // If the existing declaration is somewhere in the previous declaration
289  // chain of the new declaration, then prefer the new declaration.
290  for (auto RD : New->redecls()) {
291  if (RD == Existing)
292  return DMK_Replace;
293 
294  if (RD->isCanonicalDecl())
295  break;
296  }
297 
298  return DMK_Ignore;
299  }
300 
301  return DMK_Different;
302 }
303 
305  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
306  readingIdentifier(*II);
307 
308  void *Ptr = Name.getFETokenInfo();
309 
310  if (!Ptr) {
311  Name.setFETokenInfo(D);
312  return true;
313  }
314 
315  IdDeclInfo *IDI;
316 
317  if (isDeclPtr(Ptr)) {
318  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
319 
320  switch (compareDeclarations(PrevD, D)) {
321  case DMK_Different:
322  break;
323 
324  case DMK_Ignore:
325  return false;
326 
327  case DMK_Replace:
328  Name.setFETokenInfo(D);
329  return true;
330  }
331 
332  Name.setFETokenInfo(nullptr);
333  IDI = &(*IdDeclInfos)[Name];
334 
335  // If the existing declaration is not visible in translation unit scope,
336  // then add the new top-level declaration first.
337  if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
338  IDI->AddDecl(D);
339  IDI->AddDecl(PrevD);
340  } else {
341  IDI->AddDecl(PrevD);
342  IDI->AddDecl(D);
343  }
344  return true;
345  }
346 
347  IDI = toIdDeclInfo(Ptr);
348 
349  // See whether this declaration is identical to any existing declarations.
350  // If not, find the right place to insert it.
351  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
352  IEnd = IDI->decls_end();
353  I != IEnd; ++I) {
354 
355  switch (compareDeclarations(*I, D)) {
356  case DMK_Different:
357  break;
358 
359  case DMK_Ignore:
360  return false;
361 
362  case DMK_Replace:
363  *I = D;
364  return true;
365  }
366 
367  if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
368  // We've found a declaration that is not visible from the translation
369  // unit (it's in an inner scope). Insert our declaration here.
370  IDI->InsertDecl(I, D);
371  return true;
372  }
373  }
374 
375  // Add the declaration to the end.
376  IDI->AddDecl(D);
377  return true;
378 }
379 
380 void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
381  if (II.isOutOfDate())
383 }
384 
385 void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
386  if (II.isOutOfDate())
388 
389  if (II.isFromAST())
391 }
392 
393 //===----------------------------------------------------------------------===//
394 // IdDeclInfoMap Implementation
395 //===----------------------------------------------------------------------===//
396 
397 /// Returns the IdDeclInfo associated to the DeclarationName.
398 /// It creates a new IdDeclInfo if one was not created before for this id.
399 IdentifierResolver::IdDeclInfo &
401  void *Ptr = Name.getFETokenInfo();
402 
403  if (Ptr) return *toIdDeclInfo(Ptr);
404 
405  if (CurIndex == POOL_SIZE) {
406  CurPool = new IdDeclInfoPool(CurPool);
407  CurIndex = 0;
408  }
409  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
410  Name.setFETokenInfo(reinterpret_cast<void*>(
411  reinterpret_cast<uintptr_t>(IDI) | 0x1)
412  );
413  ++CurIndex;
414  return *IDI;
415 }
416 
417 void IdentifierResolver::iterator::incrementSlowCase() {
418  NamedDecl *D = **this;
419  void *InfoPtr = D->getDeclName().getFETokenInfo();
420  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
421  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
422 
423  BaseIter I = getIterator();
424  if (I != Info->decls_begin())
425  *this = iterator(I-1);
426  else // No more decls.
427  *this = iterator();
428 }
clang::IdentifierResolver::AddDecl
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
Definition: IdentifierResolver.cpp:146
clang::IdentifierResolver::IdDeclInfoMap
IdDeclInfoMap - Associates IdDeclInfos with declaration names.
Definition: IdentifierResolver.cpp:36
clang::DeclContext
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1356
clang::IdentifierResolver::begin
iterator begin(DeclarationName Name)
begin - Returns an iterator for decls with the name 'Name'.
Definition: IdentifierResolver.cpp:232
clang::NamedDecl
This represents a decl that may have a name.
Definition: Decl.h:247
clang::IdentifierResolver::InsertDeclAfter
void InsertDeclAfter(iterator Pos, NamedDecl *D)
Insert the given declaration after the given iterator position.
Definition: IdentifierResolver.cpp:171
IdentifierResolver.h
clang::IdentifierResolver::iterator::BaseIter
IdDeclInfo::DeclsTy::iterator BaseIter
Definition: IdentifierResolver.h:84
clang::IdentifierInfo::isOutOfDate
bool isOutOfDate() const
Determine whether the information for this identifier is out of date with respect to the external sou...
Definition: IdentifierTable.h:414
clang::IdentifierResolver::RemoveDecl
void RemoveDecl(NamedDecl *D)
RemoveDecl - Unlink the decl from its shadowed decl chain.
Definition: IdentifierResolver.cpp:211
clang::IdentifierInfo::isFromAST
bool isFromAST() const
Return true if the identifier in its current state was loaded from an AST file.
Definition: IdentifierTable.h:384
clang::DeclarationName
The name of a declaration.
Definition: DeclarationName.h:144
Preprocessor.h
Decl.h
clang::DeclContext::InEnclosingNamespaceSetOf
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:1834
clang::IdentifierResolver::tryAddTopLevelDecl
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't alre...
Definition: IdentifierResolver.cpp:304
clang::IdentifierResolver::isDeclInScope
bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S=nullptr, bool AllowInlineNamespace=false) const
isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true if 'D' is in Scope 'S',...
Definition: IdentifierResolver.cpp:99
clang::Decl::getKind
Kind getKind() const
Definition: DeclBase.h:428
DeclBase.h
clang::Scope
Scope - A scope is a transient data structure that is used while parsing the program.
Definition: Scope.h:40
clang::IdentifierResolver::iterator::isIterator
bool isIterator() const
Definition: IdentifierResolver.h:98
LangOptions.h
clang::IdentifierResolver::IdDeclInfoMap::IdDeclInfoMap
IdDeclInfoMap()=default
clang::Decl::getCanonicalDecl
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:910
clang::IdentifierResolver::iterator::getIterator
BaseIter getIterator() const
Definition: IdentifierResolver.h:100
uintptr_t
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...
Definition: opencl-c-base.h:140
IdentifierTable.h
clang::DeclContext::isTranslationUnit
bool isTranslationUnit() const
Definition: DeclBase.h:1957
clang::Decl::redecls
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:981
clang::IdentifierResolver::end
iterator end()
end - Returns an iterator that has 'finished'.
Definition: IdentifierResolver.h:141
clang::NamedDecl::getMostRecentDecl
NamedDecl * getMostRecentDecl()
Definition: Decl.h:471
compareDeclarations
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New)
Compare two declarations to see whether they are different or, if they are the same,...
Definition: IdentifierResolver.cpp:264
clang::DeclContext::getRedeclContext
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1797
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::Decl::isFromASTFile
bool isFromASTFile() const
Determine whether this declaration came from an AST file (such as a precompiled header or module) rat...
Definition: DeclBase.h:725
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
Scope.h
clang::IdentifierInfo::setFETokenInfoChangedSinceDeserialization
void setFETokenInfoChangedSinceDeserialization()
Note that the frontend token information for this identifier has changed since it was loaded from an ...
Definition: IdentifierTable.h:408
clang::DeclarationName::getFETokenInfo
void * getFETokenInfo() const
Get and set FETokenInfo.
Definition: DeclarationName.h:501
clang::IdentifierResolver::IdDeclInfoMap::operator[]
IdDeclInfo & operator[](DeclarationName Name)
Returns the IdDeclInfo associated to the DeclarationName.
Definition: IdentifierResolver.cpp:400
clang::IdentifierInfo
One of these records is kept for each identifier that is lexed.
Definition: IdentifierTable.h:84
DeclarationName.h
clang
Definition: CalledOnceCheck.h:17
clang::ExternalPreprocessorSource::updateOutOfDateIdentifier
virtual void updateOutOfDateIdentifier(IdentifierInfo &II)=0
Update an out-of-date identifier.
clang::IdentifierResolver::IdDeclInfoMap::~IdDeclInfoMap
~IdDeclInfoMap()
Definition: IdentifierResolver.cpp:55
clang::NamedDecl::getDeclName
DeclarationName getDeclName() const
Get the actual, stored name of the declaration, which may be a special name.
Definition: Decl.h:311
clang::Preprocessor
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:130
clang::IdentifierResolver::iterator
iterator - Iterate over the decls of a specified declaration name.
Definition: IdentifierResolver.h:69
clang::DeclContext::isFunctionOrMethod
bool isFunctionOrMethod() const
Definition: DeclBase.h:1934
clang::Preprocessor::getExternalSource
ExternalPreprocessorSource * getExternalSource() const
Definition: Preprocessor.h:1023
clang::IdentifierResolver::~IdentifierResolver
~IdentifierResolver()
Definition: IdentifierResolver.cpp:92
clang::DeclContext::Equals
bool Equals(const DeclContext *DC) const
Determine whether this declaration context is equivalent to the declaration context DC.
Definition: DeclBase.h:2006
clang::IdentifierResolver::IdentifierResolver
IdentifierResolver(Preprocessor &PP)
Definition: IdentifierResolver.cpp:89
ExternalPreprocessorSource.h
clang::Decl::getDeclContext
DeclContext * getDeclContext()
Definition: DeclBase.h:434