clang  16.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  // The names for HLSL cbuffer/tbuffers only used by the CPU-side
103  // reflection API which supports querying bindings. It will not have name
104  // conflict with other Decls.
105  if (LangOpt.HLSL && isa<HLSLBufferDecl>(D))
106  return false;
107  if (Ctx->isFunctionOrMethod() || (S && S->isFunctionPrototypeScope())) {
108  // Ignore the scopes associated within transparent declaration contexts.
109  while (S->getEntity() && S->getEntity()->isTransparentContext())
110  S = S->getParent();
111 
112  if (S->isDeclScope(D))
113  return true;
114  if (LangOpt.CPlusPlus) {
115  // C++ 3.3.2p3:
116  // The name declared in a catch exception-declaration is local to the
117  // handler and shall not be redeclared in the outermost block of the
118  // handler.
119  // C++ 3.3.2p4:
120  // Names declared in the for-init-statement, and in the condition of if,
121  // while, for, and switch statements are local to the if, while, for, or
122  // switch statement (including the controlled statement), and shall not be
123  // redeclared in a subsequent condition of that statement nor in the
124  // outermost block (or, for the if statement, any of the outermost blocks)
125  // of the controlled statement.
126  //
127  assert(S->getParent() && "No TUScope?");
128  // If the current decl is in a lambda, we shouldn't consider this is a
129  // redefinition as lambda has its own scope.
130  if (S->getParent()->isControlScope() && !S->isFunctionScope()) {
131  S = S->getParent();
132  if (S->isDeclScope(D))
133  return true;
134  }
135  if (S->isFnTryCatchScope())
136  return S->getParent()->isDeclScope(D);
137  }
138  return false;
139  }
140 
141  // FIXME: If D is a local extern declaration, this check doesn't make sense;
142  // we should be checking its lexical context instead in that case, because
143  // that is its scope.
145  return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
146  : Ctx->Equals(DCtx);
147 }
148 
149 /// AddDecl - Link the decl to its shadowed decl chain.
151  DeclarationName Name = D->getDeclName();
152  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
153  updatingIdentifier(*II);
154 
155  void *Ptr = Name.getFETokenInfo();
156 
157  if (!Ptr) {
158  Name.setFETokenInfo(D);
159  return;
160  }
161 
162  IdDeclInfo *IDI;
163 
164  if (isDeclPtr(Ptr)) {
165  Name.setFETokenInfo(nullptr);
166  IDI = &(*IdDeclInfos)[Name];
167  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
168  IDI->AddDecl(PrevD);
169  } else
170  IDI = toIdDeclInfo(Ptr);
171 
172  IDI->AddDecl(D);
173 }
174 
176  DeclarationName Name = D->getDeclName();
177  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
178  updatingIdentifier(*II);
179 
180  void *Ptr = Name.getFETokenInfo();
181 
182  if (!Ptr) {
183  AddDecl(D);
184  return;
185  }
186 
187  if (isDeclPtr(Ptr)) {
188  // We only have a single declaration: insert before or after it,
189  // as appropriate.
190  if (Pos == iterator()) {
191  // Add the new declaration before the existing declaration.
192  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
193  RemoveDecl(PrevD);
194  AddDecl(D);
195  AddDecl(PrevD);
196  } else {
197  // Add new declaration after the existing declaration.
198  AddDecl(D);
199  }
200 
201  return;
202  }
203 
204  // General case: insert the declaration at the appropriate point in the
205  // list, which already has at least two elements.
206  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
207  if (Pos.isIterator()) {
208  IDI->InsertDecl(Pos.getIterator() + 1, D);
209  } else
210  IDI->InsertDecl(IDI->decls_begin(), D);
211 }
212 
213 /// RemoveDecl - Unlink the decl from its shadowed decl chain.
214 /// The decl must already be part of the decl chain.
216  assert(D && "null param passed");
217  DeclarationName Name = D->getDeclName();
218  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
219  updatingIdentifier(*II);
220 
221  void *Ptr = Name.getFETokenInfo();
222 
223  assert(Ptr && "Didn't find this decl on its identifier's chain!");
224 
225  if (isDeclPtr(Ptr)) {
226  assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
227  Name.setFETokenInfo(nullptr);
228  return;
229  }
230 
231  return toIdDeclInfo(Ptr)->RemoveDecl(D);
232 }
233 
234 /// begin - Returns an iterator for decls with name 'Name'.
237  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
238  readingIdentifier(*II);
239 
240  void *Ptr = Name.getFETokenInfo();
241  if (!Ptr) return end();
242 
243  if (isDeclPtr(Ptr))
244  return iterator(static_cast<NamedDecl*>(Ptr));
245 
246  IdDeclInfo *IDI = toIdDeclInfo(Ptr);
247 
248  IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
249  if (I != IDI->decls_begin())
250  return iterator(I-1);
251  // No decls found.
252  return end();
253 }
254 
255 namespace {
256 
257 enum DeclMatchKind {
258  DMK_Different,
259  DMK_Replace,
260  DMK_Ignore
261 };
262 
263 } // namespace
264 
265 /// Compare two declarations to see whether they are different or,
266 /// if they are the same, whether the new declaration should replace the
267 /// existing declaration.
268 static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
269  // If the declarations are identical, ignore the new one.
270  if (Existing == New)
271  return DMK_Ignore;
272 
273  // If the declarations have different kinds, they're obviously different.
274  if (Existing->getKind() != New->getKind())
275  return DMK_Different;
276 
277  // If the declarations are redeclarations of each other, keep the newest one.
278  if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
279  // If we're adding an imported declaration, don't replace another imported
280  // declaration.
281  if (Existing->isFromASTFile() && New->isFromASTFile())
282  return DMK_Different;
283 
284  // If either of these is the most recent declaration, use it.
285  Decl *MostRecent = Existing->getMostRecentDecl();
286  if (Existing == MostRecent)
287  return DMK_Ignore;
288 
289  if (New == MostRecent)
290  return DMK_Replace;
291 
292  // If the existing declaration is somewhere in the previous declaration
293  // chain of the new declaration, then prefer the new declaration.
294  for (auto *RD : New->redecls()) {
295  if (RD == Existing)
296  return DMK_Replace;
297 
298  if (RD->isCanonicalDecl())
299  break;
300  }
301 
302  return DMK_Ignore;
303  }
304 
305  return DMK_Different;
306 }
307 
309  if (IdentifierInfo *II = Name.getAsIdentifierInfo())
310  readingIdentifier(*II);
311 
312  void *Ptr = Name.getFETokenInfo();
313 
314  if (!Ptr) {
315  Name.setFETokenInfo(D);
316  return true;
317  }
318 
319  IdDeclInfo *IDI;
320 
321  if (isDeclPtr(Ptr)) {
322  NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
323 
324  switch (compareDeclarations(PrevD, D)) {
325  case DMK_Different:
326  break;
327 
328  case DMK_Ignore:
329  return false;
330 
331  case DMK_Replace:
332  Name.setFETokenInfo(D);
333  return true;
334  }
335 
336  Name.setFETokenInfo(nullptr);
337  IDI = &(*IdDeclInfos)[Name];
338 
339  // If the existing declaration is not visible in translation unit scope,
340  // then add the new top-level declaration first.
341  if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
342  IDI->AddDecl(D);
343  IDI->AddDecl(PrevD);
344  } else {
345  IDI->AddDecl(PrevD);
346  IDI->AddDecl(D);
347  }
348  return true;
349  }
350 
351  IDI = toIdDeclInfo(Ptr);
352 
353  // See whether this declaration is identical to any existing declarations.
354  // If not, find the right place to insert it.
355  for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
356  IEnd = IDI->decls_end();
357  I != IEnd; ++I) {
358 
359  switch (compareDeclarations(*I, D)) {
360  case DMK_Different:
361  break;
362 
363  case DMK_Ignore:
364  return false;
365 
366  case DMK_Replace:
367  *I = D;
368  return true;
369  }
370 
371  if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
372  // We've found a declaration that is not visible from the translation
373  // unit (it's in an inner scope). Insert our declaration here.
374  IDI->InsertDecl(I, D);
375  return true;
376  }
377  }
378 
379  // Add the declaration to the end.
380  IDI->AddDecl(D);
381  return true;
382 }
383 
384 void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
385  if (II.isOutOfDate())
387 }
388 
389 void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
390  if (II.isOutOfDate())
392 
393  if (II.isFromAST())
395 }
396 
397 //===----------------------------------------------------------------------===//
398 // IdDeclInfoMap Implementation
399 //===----------------------------------------------------------------------===//
400 
401 /// Returns the IdDeclInfo associated to the DeclarationName.
402 /// It creates a new IdDeclInfo if one was not created before for this id.
403 IdentifierResolver::IdDeclInfo &
405  void *Ptr = Name.getFETokenInfo();
406 
407  if (Ptr) return *toIdDeclInfo(Ptr);
408 
409  if (CurIndex == POOL_SIZE) {
410  CurPool = new IdDeclInfoPool(CurPool);
411  CurIndex = 0;
412  }
413  IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
414  Name.setFETokenInfo(reinterpret_cast<void*>(
415  reinterpret_cast<uintptr_t>(IDI) | 0x1)
416  );
417  ++CurIndex;
418  return *IDI;
419 }
420 
421 void IdentifierResolver::iterator::incrementSlowCase() {
422  NamedDecl *D = **this;
423  void *InfoPtr = D->getDeclName().getFETokenInfo();
424  assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
425  IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
426 
427  BaseIter I = getIterator();
428  if (I != Info->decls_begin())
429  *this = iterator(I-1);
430  else // No more decls.
431  *this = iterator();
432 }
clang::IdentifierResolver::AddDecl
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
Definition: IdentifierResolver.cpp:150
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:1389
clang::IdentifierResolver::begin
iterator begin(DeclarationName Name)
begin - Returns an iterator for decls with the name 'Name'.
Definition: IdentifierResolver.cpp:236
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:175
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:415
clang::IdentifierResolver::RemoveDecl
void RemoveDecl(NamedDecl *D)
RemoveDecl - Unlink the decl from its shadowed decl chain.
Definition: IdentifierResolver.cpp:215
clang::IdentifierInfo::isFromAST
bool isFromAST() const
Return true if the identifier in its current state was loaded from an AST file.
Definition: IdentifierTable.h:385
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:1865
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:308
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:435
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:943
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:1998
clang::Decl::redecls
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:1014
clang::IdentifierResolver::end
iterator end()
end - Returns an iterator that has 'finished'.
Definition: IdentifierResolver.h:141
clang::NamedDecl::getMostRecentDecl
NamedDecl * getMostRecentDecl()
Definition: Decl.h:473
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:268
clang::DeclContext::getRedeclContext
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1828
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:751
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:409
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:404
clang::IdentifierInfo
One of these records is kept for each identifier that is lexed.
Definition: IdentifierTable.h:85
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:313
clang::Preprocessor
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:129
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:1975
clang::Preprocessor::getExternalSource
ExternalPreprocessorSource * getExternalSource() const
Definition: Preprocessor.h:1082
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:2047
clang::IdentifierResolver::IdentifierResolver
IdentifierResolver(Preprocessor &PP)
Definition: IdentifierResolver.cpp:89
ExternalPreprocessorSource.h
clang::Decl::getDeclContext
DeclContext * getDeclContext()
Definition: DeclBase.h:441