clang 19.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"
22#include "clang/Sema/Scope.h"
23#include "llvm/Support/ErrorHandling.h"
24#include <cassert>
25#include <cstdint>
26
27using 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
52public:
53 IdDeclInfoMap() = default;
54
56 IdDeclInfoPool *Cur = CurPool;
57 while (IdDeclInfoPool *P = Cur) {
58 Cur = Cur->Next;
59 delete P;
60 }
61 }
62
63 IdDeclInfoMap(const IdDeclInfoMap &) = delete;
65
66 /// Returns the IdDeclInfo associated to the DeclarationName.
67 /// It creates a new IdDeclInfo if one was not created before for this id.
68 IdDeclInfo &operator[](DeclarationName Name);
69};
70
71//===----------------------------------------------------------------------===//
72// IdDeclInfo Implementation
73//===----------------------------------------------------------------------===//
74
75/// RemoveDecl - Remove the decl from the scope chain.
76/// The decl must already be part of the decl chain.
77void IdentifierResolver::IdDeclInfo::RemoveDecl(NamedDecl *D) {
78 for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
79 if (D == *(I-1)) {
80 Decls.erase(I-1);
81 return;
82 }
83 }
84
85 llvm_unreachable("Didn't find this decl on its identifier's chain!");
86}
87
88//===----------------------------------------------------------------------===//
89// IdentifierResolver Implementation
90//===----------------------------------------------------------------------===//
91
93 : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {}
94
96 delete IdDeclInfos;
97}
98
99/// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true
100/// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns
101/// true if 'D' belongs to the given declaration context.
103 bool AllowInlineNamespace) const {
104 Ctx = Ctx->getRedeclContext();
105 // The names for HLSL cbuffer/tbuffers only used by the CPU-side
106 // reflection API which supports querying bindings. It will not have name
107 // conflict with other Decls.
108 if (LangOpt.HLSL && isa<HLSLBufferDecl>(D))
109 return false;
110 if (Ctx->isFunctionOrMethod() || (S && S->isFunctionPrototypeScope())) {
111 // Ignore the scopes associated within transparent declaration contexts.
112 while (S->getEntity() &&
113 (S->getEntity()->isTransparentContext() ||
114 (!LangOpt.CPlusPlus && isa<RecordDecl>(S->getEntity()))))
115 S = S->getParent();
116
117 if (S->isDeclScope(D))
118 return true;
119 if (LangOpt.CPlusPlus) {
120 // C++ 3.3.2p3:
121 // The name declared in a catch exception-declaration is local to the
122 // handler and shall not be redeclared in the outermost block of the
123 // handler.
124 // C++ 3.3.2p4:
125 // Names declared in the for-init-statement, and in the condition of if,
126 // while, for, and switch statements are local to the if, while, for, or
127 // switch statement (including the controlled statement), and shall not be
128 // redeclared in a subsequent condition of that statement nor in the
129 // outermost block (or, for the if statement, any of the outermost blocks)
130 // of the controlled statement.
131 //
132 assert(S->getParent() && "No TUScope?");
133 // If the current decl is in a lambda, we shouldn't consider this is a
134 // redefinition as lambda has its own scope.
135 if (S->getParent()->isControlScope() && !S->isFunctionScope()) {
136 S = S->getParent();
137 if (S->isDeclScope(D))
138 return true;
139 }
140 if (S->isFnTryCatchScope())
141 return S->getParent()->isDeclScope(D);
142 }
143 return false;
144 }
145
146 // FIXME: If D is a local extern declaration, this check doesn't make sense;
147 // we should be checking its lexical context instead in that case, because
148 // that is its scope.
150 return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
151 : Ctx->Equals(DCtx);
152}
153
154/// AddDecl - Link the decl to its shadowed decl chain.
156 DeclarationName Name = D->getDeclName();
157 if (IdentifierInfo *II = Name.getAsIdentifierInfo())
158 updatingIdentifier(*II);
159
160 void *Ptr = Name.getFETokenInfo();
161
162 if (!Ptr) {
163 Name.setFETokenInfo(D);
164 return;
165 }
166
167 IdDeclInfo *IDI;
168
169 if (isDeclPtr(Ptr)) {
170 Name.setFETokenInfo(nullptr);
171 IDI = &(*IdDeclInfos)[Name];
172 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
173 IDI->AddDecl(PrevD);
174 } else
175 IDI = toIdDeclInfo(Ptr);
176
177 IDI->AddDecl(D);
178}
179
181 DeclarationName Name = D->getDeclName();
182 if (IdentifierInfo *II = Name.getAsIdentifierInfo())
183 updatingIdentifier(*II);
184
185 void *Ptr = Name.getFETokenInfo();
186
187 if (!Ptr) {
188 AddDecl(D);
189 return;
190 }
191
192 if (isDeclPtr(Ptr)) {
193 // We only have a single declaration: insert before or after it,
194 // as appropriate.
195 if (Pos == iterator()) {
196 // Add the new declaration before the existing declaration.
197 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
198 RemoveDecl(PrevD);
199 AddDecl(D);
200 AddDecl(PrevD);
201 } else {
202 // Add new declaration after the existing declaration.
203 AddDecl(D);
204 }
205
206 return;
207 }
208
209 // General case: insert the declaration at the appropriate point in the
210 // list, which already has at least two elements.
211 IdDeclInfo *IDI = toIdDeclInfo(Ptr);
212 if (Pos.isIterator()) {
213 IDI->InsertDecl(Pos.getIterator() + 1, D);
214 } else
215 IDI->InsertDecl(IDI->decls_begin(), D);
216}
217
218/// RemoveDecl - Unlink the decl from its shadowed decl chain.
219/// The decl must already be part of the decl chain.
221 assert(D && "null param passed");
222 DeclarationName Name = D->getDeclName();
223 if (IdentifierInfo *II = Name.getAsIdentifierInfo())
224 updatingIdentifier(*II);
225
226 void *Ptr = Name.getFETokenInfo();
227
228 assert(Ptr && "Didn't find this decl on its identifier's chain!");
229
230 if (isDeclPtr(Ptr)) {
231 assert(D == Ptr && "Didn't find this decl on its identifier's chain!");
232 Name.setFETokenInfo(nullptr);
233 return;
234 }
235
236 return toIdDeclInfo(Ptr)->RemoveDecl(D);
237}
238
239llvm::iterator_range<IdentifierResolver::iterator>
241 return {begin(Name), end()};
242}
243
245 if (IdentifierInfo *II = Name.getAsIdentifierInfo())
246 readingIdentifier(*II);
247
248 void *Ptr = Name.getFETokenInfo();
249 if (!Ptr) return end();
250
251 if (isDeclPtr(Ptr))
252 return iterator(static_cast<NamedDecl*>(Ptr));
253
254 IdDeclInfo *IDI = toIdDeclInfo(Ptr);
255
256 IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
257 if (I != IDI->decls_begin())
258 return iterator(I-1);
259 // No decls found.
260 return end();
261}
262
263namespace {
264
265enum DeclMatchKind {
266 DMK_Different,
267 DMK_Replace,
268 DMK_Ignore
269};
270
271} // namespace
272
273/// Compare two declarations to see whether they are different or,
274/// if they are the same, whether the new declaration should replace the
275/// existing declaration.
276static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
277 // If the declarations are identical, ignore the new one.
278 if (Existing == New)
279 return DMK_Ignore;
280
281 // If the declarations have different kinds, they're obviously different.
282 if (Existing->getKind() != New->getKind())
283 return DMK_Different;
284
285 // If the declarations are redeclarations of each other, keep the newest one.
286 if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
287 // If we're adding an imported declaration, don't replace another imported
288 // declaration.
289 if (Existing->isFromASTFile() && New->isFromASTFile())
290 return DMK_Different;
291
292 // If either of these is the most recent declaration, use it.
293 Decl *MostRecent = Existing->getMostRecentDecl();
294 if (Existing == MostRecent)
295 return DMK_Ignore;
296
297 if (New == MostRecent)
298 return DMK_Replace;
299
300 // If the existing declaration is somewhere in the previous declaration
301 // chain of the new declaration, then prefer the new declaration.
302 for (auto *RD : New->redecls()) {
303 if (RD == Existing)
304 return DMK_Replace;
305
306 if (RD->isCanonicalDecl())
307 break;
308 }
309
310 return DMK_Ignore;
311 }
312
313 return DMK_Different;
314}
315
317 if (IdentifierInfo *II = Name.getAsIdentifierInfo())
318 readingIdentifier(*II);
319
320 void *Ptr = Name.getFETokenInfo();
321
322 if (!Ptr) {
323 Name.setFETokenInfo(D);
324 return true;
325 }
326
327 IdDeclInfo *IDI;
328
329 if (isDeclPtr(Ptr)) {
330 NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
331
332 switch (compareDeclarations(PrevD, D)) {
333 case DMK_Different:
334 break;
335
336 case DMK_Ignore:
337 return false;
338
339 case DMK_Replace:
340 Name.setFETokenInfo(D);
341 return true;
342 }
343
344 Name.setFETokenInfo(nullptr);
345 IDI = &(*IdDeclInfos)[Name];
346
347 // If the existing declaration is not visible in translation unit scope,
348 // then add the new top-level declaration first.
350 IDI->AddDecl(D);
351 IDI->AddDecl(PrevD);
352 } else {
353 IDI->AddDecl(PrevD);
354 IDI->AddDecl(D);
355 }
356 return true;
357 }
358
359 IDI = toIdDeclInfo(Ptr);
360
361 // See whether this declaration is identical to any existing declarations.
362 // If not, find the right place to insert it.
363 for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
364 IEnd = IDI->decls_end();
365 I != IEnd; ++I) {
366
367 switch (compareDeclarations(*I, D)) {
368 case DMK_Different:
369 break;
370
371 case DMK_Ignore:
372 return false;
373
374 case DMK_Replace:
375 *I = D;
376 return true;
377 }
378
379 if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
380 // We've found a declaration that is not visible from the translation
381 // unit (it's in an inner scope). Insert our declaration here.
382 IDI->InsertDecl(I, D);
383 return true;
384 }
385 }
386
387 // Add the declaration to the end.
388 IDI->AddDecl(D);
389 return true;
390}
391
392void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
393 if (II.isOutOfDate())
395}
396
397void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
398 if (II.isOutOfDate())
400
401 if (II.isFromAST())
403}
404
405//===----------------------------------------------------------------------===//
406// IdDeclInfoMap Implementation
407//===----------------------------------------------------------------------===//
408
409/// Returns the IdDeclInfo associated to the DeclarationName.
410/// It creates a new IdDeclInfo if one was not created before for this id.
411IdentifierResolver::IdDeclInfo &
413 void *Ptr = Name.getFETokenInfo();
414
415 if (Ptr) return *toIdDeclInfo(Ptr);
416
417 if (CurIndex == POOL_SIZE) {
418 CurPool = new IdDeclInfoPool(CurPool);
419 CurIndex = 0;
420 }
421 IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
422 Name.setFETokenInfo(reinterpret_cast<void*>(
423 reinterpret_cast<uintptr_t>(IDI) | 0x1)
424 );
425 ++CurIndex;
426 return *IDI;
427}
428
430 NamedDecl *D = **this;
431 void *InfoPtr = D->getDeclName().getFETokenInfo();
432 assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
433 IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
434
435 BaseIter I = getIterator();
436 if (I != Info->decls_begin())
437 *this = iterator(I-1);
438 else // No more decls.
439 *this = iterator();
440}
StringRef P
static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New)
Compare two declarations to see whether they are different or, if they are the same,...
Defines the clang::IdentifierInfo, clang::IdentifierTable, and clang::Selector interfaces.
Defines the clang::LangOptions interface.
Defines the clang::Preprocessor interface.
IdDeclInfoMap - Associates IdDeclInfos with declaration names.
IdDeclInfoMap(const IdDeclInfoMap &)=delete
IdDeclInfoMap & operator=(const IdDeclInfoMap &)=delete
IdDeclInfo & operator[](DeclarationName Name)
Returns the IdDeclInfo associated to the DeclarationName.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1432
bool Equals(const DeclContext *DC) const
Determine whether this declaration context is equivalent to the declaration context DC.
Definition: DeclBase.h:2191
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:1997
bool isTranslationUnit() const
Definition: DeclBase.h:2138
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1960
bool isFunctionOrMethod() const
Definition: DeclBase.h:2114
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
bool isFromASTFile() const
Determine whether this declaration came from an AST file (such as a precompiled header or module) rat...
Definition: DeclBase.h:780
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:1035
DeclContext * getDeclContext()
Definition: DeclBase.h:454
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:964
Kind getKind() const
Definition: DeclBase.h:448
The name of a declaration.
void * getFETokenInfo() const
Get and set FETokenInfo.
virtual void updateOutOfDateIdentifier(const IdentifierInfo &II)=0
Update an out-of-date identifier.
One of these records is kept for each identifier that is lexed.
bool isFromAST() const
Return true if the identifier in its current state was loaded from an AST file.
void setFETokenInfoChangedSinceDeserialization()
Note that the frontend token information for this identifier has changed since it was loaded from an ...
bool isOutOfDate() const
Determine whether the information for this identifier is out of date with respect to the external sou...
iterator - Iterate over the decls of a specified declaration name.
IdDeclInfo::DeclsTy::iterator BaseIter
iterator begin(DeclarationName Name)
Returns an iterator over decls with the name 'Name'.
void RemoveDecl(NamedDecl *D)
RemoveDecl - Unlink the decl from its shadowed decl chain.
IdentifierResolver(Preprocessor &PP)
void InsertDeclAfter(iterator Pos, NamedDecl *D)
Insert the given declaration after the given iterator position.
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...
iterator end()
Returns the end iterator.
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
llvm::iterator_range< iterator > decls(DeclarationName Name)
Returns a range of decls with the name 'Name'.
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',...
This represents a decl that may have a name.
Definition: Decl.h:249
DeclarationName getDeclName() const
Get the actual, stored name of the declaration, which may be a special name.
Definition: Decl.h:315
NamedDecl * getMostRecentDecl()
Definition: Decl.h:476
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
Definition: Preprocessor.h:128
ExternalPreprocessorSource * getExternalSource() const
Scope - A scope is a transient data structure that is used while parsing the program.
Definition: Scope.h:41
The JSON file list parser is used to communicate input to InstallAPI.
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...