clang 17.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 /// 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.
74void 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
255namespace {
256
257enum 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.
268static 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.
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
384void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
385 if (II.isOutOfDate())
387}
388
389void 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.
403IdentifierResolver::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
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}
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.
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:1393
bool Equals(const DeclContext *DC) const
Determine whether this declaration context is equivalent to the declaration context DC.
Definition: DeclBase.h:2057
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:1878
bool isTranslationUnit() const
Definition: DeclBase.h:2008
DeclContext * getRedeclContext()
getRedeclContext - Retrieve the context in which an entity conflicts with other entities of the same ...
Definition: DeclBase.cpp:1841
bool isFunctionOrMethod() const
Definition: DeclBase.h:1985
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:751
redecl_range redecls() const
Returns an iterator range for all the redeclarations of the same decl.
Definition: DeclBase.h:1014
DeclContext * getDeclContext()
Definition: DeclBase.h:441
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:943
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)
begin - Returns an iterator for 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()
end - Returns an iterator that has 'finished'.
void AddDecl(NamedDecl *D)
AddDecl - Link the decl to its shadowed decl chain.
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:471
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...