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