clang  14.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 (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 
251 enum DeclMatchKind {
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.
262 static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
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 
415 void IdentifierResolver::iterator::incrementSlowCase() {
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 }
clang::IdentifierResolver::AddDecl
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
Definition: IdentifierResolver.cpp:144
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:1347
clang::IdentifierResolver::begin
iterator begin(DeclarationName Name)
begin - Returns an iterator for decls with the name 'Name'.
Definition: IdentifierResolver.cpp:230
clang::NamedDecl
This represents a decl that may have a name.
Definition: Decl.h:249
clang::IdentifierResolver::InsertDeclAfter
void InsertDeclAfter(iterator Pos, NamedDecl *D)
Insert the given declaration after the given iterator position.
Definition: IdentifierResolver.cpp:169
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:209
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:145
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:1817
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:302
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:433
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:901
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:124
IdentifierTable.h
clang::DeclContext::isTranslationUnit
bool isTranslationUnit() const
Definition: DeclBase.h:1935
clang::Scope::ControlScope
@ ControlScope
The controlling scope in a if/switch/while/for statement.
Definition: Scope.h:62
clang::Decl::redecls
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:972
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:262
clang::DeclContext::getRedeclContext
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1780
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:716
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:89
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:492
clang::IdentifierResolver::IdDeclInfoMap::operator[]
IdDeclInfo & operator[](DeclarationName Name)
Returns the IdDeclInfo associated to the DeclarationName.
Definition: IdentifierResolver.cpp:398
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:313
clang::Scope::FnTryCatchScope
@ FnTryCatchScope
This is the scope for a function-level C++ try or catch scope.
Definition: Scope.h:104
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:1912
clang::Preprocessor::getExternalSource
ExternalPreprocessorSource * getExternalSource() const
Definition: Preprocessor.h:977
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:1984
clang::IdentifierResolver::IdentifierResolver
IdentifierResolver(Preprocessor &PP)
Definition: IdentifierResolver.cpp:89
ExternalPreprocessorSource.h
clang::Decl::getDeclContext
DeclContext * getDeclContext()
Definition: DeclBase.h:439