xref: /freebsd/contrib/llvm-project/clang/lib/Sema/IdentifierResolver.cpp (revision f126890ac5386406dadf7c4cfa9566cbb56537c5)
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 
14 #include "clang/Sema/IdentifierResolver.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclarationName.h"
18 #include "clang/Basic/IdentifierTable.h"
19 #include "clang/Basic/LangOptions.h"
20 #include "clang/Lex/ExternalPreprocessorSource.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.
36 class IdentifierResolver::IdDeclInfoMap {
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 
55   ~IdDeclInfoMap() {
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 
89 IdentifierResolver::IdentifierResolver(Preprocessor &PP)
90     : LangOpt(PP.getLangOpts()), PP(PP), IdDeclInfos(new IdDeclInfoMap) {}
91 
92 IdentifierResolver::~IdentifierResolver() {
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.
99 bool IdentifierResolver::isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S,
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.
144   DeclContext *DCtx = D->getDeclContext()->getRedeclContext();
145   return AllowInlineNamespace ? Ctx->InEnclosingNamespaceSetOf(DCtx)
146                               : Ctx->Equals(DCtx);
147 }
148 
149 /// AddDecl - Link the decl to its shadowed decl chain.
150 void IdentifierResolver::AddDecl(NamedDecl *D) {
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 
175 void IdentifierResolver::InsertDeclAfter(iterator Pos, NamedDecl *D) {
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.
215 void IdentifierResolver::RemoveDecl(NamedDecl *D) {
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 llvm::iterator_range<IdentifierResolver::iterator>
235 IdentifierResolver::decls(DeclarationName Name) {
236   return {begin(Name), end()};
237 }
238 
239 IdentifierResolver::iterator IdentifierResolver::begin(DeclarationName Name) {
240   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
241     readingIdentifier(*II);
242 
243   void *Ptr = Name.getFETokenInfo();
244   if (!Ptr) return end();
245 
246   if (isDeclPtr(Ptr))
247     return iterator(static_cast<NamedDecl*>(Ptr));
248 
249   IdDeclInfo *IDI = toIdDeclInfo(Ptr);
250 
251   IdDeclInfo::DeclsTy::iterator I = IDI->decls_end();
252   if (I != IDI->decls_begin())
253     return iterator(I-1);
254   // No decls found.
255   return end();
256 }
257 
258 namespace {
259 
260 enum DeclMatchKind {
261   DMK_Different,
262   DMK_Replace,
263   DMK_Ignore
264 };
265 
266 } // namespace
267 
268 /// Compare two declarations to see whether they are different or,
269 /// if they are the same, whether the new declaration should replace the
270 /// existing declaration.
271 static DeclMatchKind compareDeclarations(NamedDecl *Existing, NamedDecl *New) {
272   // If the declarations are identical, ignore the new one.
273   if (Existing == New)
274     return DMK_Ignore;
275 
276   // If the declarations have different kinds, they're obviously different.
277   if (Existing->getKind() != New->getKind())
278     return DMK_Different;
279 
280   // If the declarations are redeclarations of each other, keep the newest one.
281   if (Existing->getCanonicalDecl() == New->getCanonicalDecl()) {
282     // If we're adding an imported declaration, don't replace another imported
283     // declaration.
284     if (Existing->isFromASTFile() && New->isFromASTFile())
285       return DMK_Different;
286 
287     // If either of these is the most recent declaration, use it.
288     Decl *MostRecent = Existing->getMostRecentDecl();
289     if (Existing == MostRecent)
290       return DMK_Ignore;
291 
292     if (New == MostRecent)
293       return DMK_Replace;
294 
295     // If the existing declaration is somewhere in the previous declaration
296     // chain of the new declaration, then prefer the new declaration.
297     for (auto *RD : New->redecls()) {
298       if (RD == Existing)
299         return DMK_Replace;
300 
301       if (RD->isCanonicalDecl())
302         break;
303     }
304 
305     return DMK_Ignore;
306   }
307 
308   return DMK_Different;
309 }
310 
311 bool IdentifierResolver::tryAddTopLevelDecl(NamedDecl *D, DeclarationName Name){
312   if (IdentifierInfo *II = Name.getAsIdentifierInfo())
313     readingIdentifier(*II);
314 
315   void *Ptr = Name.getFETokenInfo();
316 
317   if (!Ptr) {
318     Name.setFETokenInfo(D);
319     return true;
320   }
321 
322   IdDeclInfo *IDI;
323 
324   if (isDeclPtr(Ptr)) {
325     NamedDecl *PrevD = static_cast<NamedDecl*>(Ptr);
326 
327     switch (compareDeclarations(PrevD, D)) {
328     case DMK_Different:
329       break;
330 
331     case DMK_Ignore:
332       return false;
333 
334     case DMK_Replace:
335       Name.setFETokenInfo(D);
336       return true;
337     }
338 
339     Name.setFETokenInfo(nullptr);
340     IDI = &(*IdDeclInfos)[Name];
341 
342     // If the existing declaration is not visible in translation unit scope,
343     // then add the new top-level declaration first.
344     if (!PrevD->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
345       IDI->AddDecl(D);
346       IDI->AddDecl(PrevD);
347     } else {
348       IDI->AddDecl(PrevD);
349       IDI->AddDecl(D);
350     }
351     return true;
352   }
353 
354   IDI = toIdDeclInfo(Ptr);
355 
356   // See whether this declaration is identical to any existing declarations.
357   // If not, find the right place to insert it.
358   for (IdDeclInfo::DeclsTy::iterator I = IDI->decls_begin(),
359                                   IEnd = IDI->decls_end();
360        I != IEnd; ++I) {
361 
362     switch (compareDeclarations(*I, D)) {
363     case DMK_Different:
364       break;
365 
366     case DMK_Ignore:
367       return false;
368 
369     case DMK_Replace:
370       *I = D;
371       return true;
372     }
373 
374     if (!(*I)->getDeclContext()->getRedeclContext()->isTranslationUnit()) {
375       // We've found a declaration that is not visible from the translation
376       // unit (it's in an inner scope). Insert our declaration here.
377       IDI->InsertDecl(I, D);
378       return true;
379     }
380   }
381 
382   // Add the declaration to the end.
383   IDI->AddDecl(D);
384   return true;
385 }
386 
387 void IdentifierResolver::readingIdentifier(IdentifierInfo &II) {
388   if (II.isOutOfDate())
389     PP.getExternalSource()->updateOutOfDateIdentifier(II);
390 }
391 
392 void IdentifierResolver::updatingIdentifier(IdentifierInfo &II) {
393   if (II.isOutOfDate())
394     PP.getExternalSource()->updateOutOfDateIdentifier(II);
395 
396   if (II.isFromAST())
397     II.setFETokenInfoChangedSinceDeserialization();
398 }
399 
400 //===----------------------------------------------------------------------===//
401 // IdDeclInfoMap Implementation
402 //===----------------------------------------------------------------------===//
403 
404 /// Returns the IdDeclInfo associated to the DeclarationName.
405 /// It creates a new IdDeclInfo if one was not created before for this id.
406 IdentifierResolver::IdDeclInfo &
407 IdentifierResolver::IdDeclInfoMap::operator[](DeclarationName Name) {
408   void *Ptr = Name.getFETokenInfo();
409 
410   if (Ptr) return *toIdDeclInfo(Ptr);
411 
412   if (CurIndex == POOL_SIZE) {
413     CurPool = new IdDeclInfoPool(CurPool);
414     CurIndex = 0;
415   }
416   IdDeclInfo *IDI = &CurPool->Pool[CurIndex];
417   Name.setFETokenInfo(reinterpret_cast<void*>(
418                               reinterpret_cast<uintptr_t>(IDI) | 0x1)
419                                                                      );
420   ++CurIndex;
421   return *IDI;
422 }
423 
424 void IdentifierResolver::iterator::incrementSlowCase() {
425   NamedDecl *D = **this;
426   void *InfoPtr = D->getDeclName().getFETokenInfo();
427   assert(!isDeclPtr(InfoPtr) && "Decl with wrong id ?");
428   IdDeclInfo *Info = toIdDeclInfo(InfoPtr);
429 
430   BaseIter I = getIterator();
431   if (I != Info->decls_begin())
432     *this = iterator(I-1);
433   else // No more decls.
434     *this = iterator();
435 }
436